Донецкий национальный технический университет Автореферат магистерской выпускной работы по теме: "Исследование методов распределенного логического моделирования" автор: Онищенко Денис Викторович (специальность “Программное обеспечение вычислительной техники и автоматизированных систем”) E-mail: onischenko@hotmail.com руководитель: кандидат технических наук, доцент кафедры ПМиИ Ладыженский Юрий Валентинович Донецк 2002

Общая характеристика работы

    В последние годы увеличение потребности в быстром проектировании интегральных схем привело к возникновению многих исследований в области проектирования микроэлектроники и аппаратных устройств. В частности, проблемы возникают из-за увеличения количества транзисторов, которые могут быть размещены на одной микросхеме. В связи с этим темой многих исследований являются методологии проектирования схем, такие как компоновка элементов, разводка проводников и др. Другой более важной проблемой является верификация схем, состоящих из большого количества элементов. “Действительно ли финальный продукт будет функционировать так, как ожидалось?” является наиболее важным вопросом, возникающим при проектировании таких больших схем. Поэтому моделирование функционирования проектируемых схем является важным этапом их разработки и позволяет избежать производства схем, содержащих дефекты и ошибки проектирования.

    Моделирование цифровых схем в основном используется для того, чтобы избежать серьёзных ошибок, возникающих в процессе проектирования схемы, и которые могут сделать дорогостоящий процесс её разработки бесполезным. Это является очень важным, поскольку процесс проектирования схем может длиться несколько месяцев, или даже годы. Другой важной задачей моделирования является проверка соответствия проектируемой схемы её спецификациям.

    Моделирование проектируемых схем позволяет обнаружить многие проблемы, которые могут возникнуть при её функционировании. Обычно, процесс проектирования схемы состоит из нескольких итераций. На каждой итерации, начиная с начальной, должно выполняться моделирование функционирования прототипа разрабатываемой схемы. В случае обнаружения ошибок при моделировании, перед переходом к следующей итерации происходит их исправление, до тех пор, пока не будет реализован весь проект.

    Таким образом, моделирования логических схем является очень важным этапом разработки СБИС. Увеличение размеров разрабатываемых схем требует применения более эффективных стратегий для ускорения моделирования. Одним из подходов к ускорению моделирования схем является параллельное логическое моделирование [1,2].

    За последние годы было сделано несколько различных работ в этом направлении, от создания специализированных аппаратных устройств, специально предназначенных для логического моделирования (таких как устройства, управляющие очередью событий), до различных классов программных систем логического моделирования.

    Целью данной работы является исследование различных подходов к реализации систем параллельного логического моделирования, исследования стратегий разбиения схем и балансировки нагрузки при параллельном моделировании, а также исследования влияния характеристик самих схем на ускорение при параллельном логическом моделировании.

    В  соответствии с поставленными целями основными задачами исследования являются:

• сравнение различных подходов к параллельному логическому моделированию;

• сравнение различных стратегий синхронизации при параллельном логическом моделировании, и исследование их влияния на ускорение, получаемое при параллельном моделировании;

• сравнение различных стратегий разбиения схем, и исследование их влияния на ускорение, получаемое при параллельном моделировании;

• исследование влияния характеристик моделируемых схем на ускорение, получаемое при параллельном моделировании;

• исследование зависимостей между вычислительными и коммуникационными затратами при параллельном логическом моделировании.

    Научная новизна рассматриваемой работы заключается в получении новых экспериментальных результатов по оценке влияния различных стратегий параллельного моделирования и стратегий разбиения схем на ускорение логического моделирования.

    Для исследования различных стратегий параллельного логического моделирования разработана программа, осуществляющая параллельное логическое моделирование с применением различных стратегий синхронизации, разбиения схем и балансировки нагрузки.

Содержание работы

СРЕДА И СТРУКТУРНАЯ МОДЕЛЬ ДЛЯ ЛОГИЧЕСКОГО МОДЕЛИРОВАНИЯ

     Для моделирования процесса функционирования логической схемы, её описание, полученное во время разработки, вместе с начальными значениями входных сигналов схемы подаётся на вход системе моделирования. Начальные значения входных сигналов могут генерироваться случайно или определяться исходя из спецификаций моделируемой схемы. В процессе моделирования определяются значения сигналов на выходах схемы. Это позволяет определить, соответствуют ли результаты функционирования схемы и скорость её работы спецификациям и ожидаемым результатам.

    Основные действия, производимые при логическом моделировании идентичны для всех уровней абстракции моделируемых схем и моделей дискретного времени. Каждый элемент схемы имеет, по крайней мере, один вход и, по крайней мере, один выход, а также своё внутреннее состояние, зависящее от времени. Входы и выходы различных элементов схемы соединены между собой проводниками, по которым распространяются значения сигналов на входах и выходах элементов. Значения сигналов могут изменяться в дискретные моменты времени. Проводники в системе моделирования реализуются как узлы, в которых хранится текущее значение сигнала проводника и, возможно, будущее изменение этого сигнала. На значение сигнала в проводнике могут оказывать влияние выходы сразу нескольких элементов схемы, соединённые с этим проводником. По этой причине, узел должен отделять значения сигналов подаваемых на выходы связанных с ним элементов от входов связанных с ним элементов, как показано на рис. 1. Это необходимо, поскольку:

• Различные элементы схемы, соединённые с одним узлом через свои выходы могут одновременно подавать на этот узел различные значения сигнала, и
• Значения входов и выходов не должны изменяться до тех пор, пока не завершится моделирование всех элементов схемы для текущего момента времени. Новые значения сигналов, появляющиеся на выходе для будущего времени, не должны передаваться на любой из входов до тех пор, пока связанные с ним элементы не будут промоделированы для текущего временного шага.

            Рисунок.1 – Простая схема модели на уровне логических элементов

    Следовательно, для того чтобы отделить функционирование входов и выходов элементов,  узлы должны быть вставлены. Они могут также реализовывать так называемую функцию разрешения. В случае, если несколько элементов схемы могут одновременно оказывать влияние на значение сигнала, функция разрешения определяет значение, подаваемое на вход элементу схемы управляемого этим сигналом.

    Для простоты, внешние входы элементов (контакты микросхемы) рассматриваются как узлы, которые управляют соединёнными с ними элементами схемы, подавая на них значения сигналов с внешних выводов.

ОСНОВНАЯ СХЕМА МОДЕЛИРОВАНИЯ

     Моделирование логической схемы представляет собой циклический процесс, которому предшествует фаза инициализации (рис. 2). При инициализации происходит установка начальных значений сигналов на внешних входах схемы, после чего элементы схемы, связанные с её внешними входами планируются на моделирование для определения их внутреннего состояния и значений сигналов на выходах.

            Каждый цикл моделирования состоит из трёх шагов. На первом шаге происходит моделирование запланированных элементов схемы, и определение их нового состояния. Изменения состояний элементов могут привести к изменениям на выходах элементов, которые соединены с входами других элементов через промежуточные узлы. В этом случае на втором шаге, когда входов всех элементов схемы известны, согласно функции разрешения определяются новые значения сигналов  узлов. На третьем шаге происходит планирование элементов схемы для повторного моделирования. В частности, планируются для последующего моделирования те элементы схемы, которые управляются узлами, на которых изменилось значение сигнала на предыдущем шаге.

            Рисунок 2 – Основная процедура моделирования.

    Моделирование схемы заканчивается только тогда, когда на очередном цикле моделирования не произошло никаких изменений, или когда выполняется предопределённое условие завершения (например, время моделирования достигнет некоторого предельного значения).

    Структуры данных, используемые для реализации таких систем моделирования, в основном состоят из списка элементов со своими входами, выходами, и текущим состоянием, и из списка узлов, управляющих и управляемых элементами схемы. Часто частью системы моделирования является также очередь сообщений, которая используется для планирования элементов, для которых были изменены значения сигналов на входах. Во время каждой итерации, описанного выше цикла моделирования, над элементами схемы, узлами и очередью событий выполняются соответствующие операции, в результате которых происходит обновление структур данных в соответствии с моделью моделирования.

 ПОСЛЕДОВАТЕЛЬНЫЕ СТРАТЕГИИ МОДЕЛИРОВАНИЯ

    Основным критерием, по которому отличают различные стратегии моделирования, является способ, которым осуществляется продвижение по модельному времени. В соответствии с этим все методы моделирования можно разделить на два класса:

• Моделирование, управляемое временем может рассматриваться как быстрое или медленное изменение моделируемой системы. Основываясь на заданной дискретизации модельного времени, моделируются последовательно все временные шаги. Управляемое временем моделирование также известно как моделирование в компилированном режиме, так как стратегия, по которой на каждом временном шаге происходит моделирование элементов схемы, определяется один раз во время компиляции модели и не может динамически подстраиваться во время моделирования.

    Этот метод является наиболее простым способом моделирования. Продвижение по модельному времени при таком способе моделирования, как правило, осуществляется на одинаковые интервалы. Для каждого такого интервала модельного времени происходит моделирование всех элементов схемы. Новые состояния элементов и значения сигналов сохраняются в переменных, и которые будут использоваться на следующем шаге модельного времени в качестве старых состояний элементов и значений сигналов. Третий этап цикла моделирования основной схемы вырождается в планирование на моделирование всех элементов схемы. Однако, эта стратегия может быть  оптимизирована, путём моделирования только тех элементов схемы, для которых значения сигналов на входах были изменены на предыдущем шаге модельного времени. Эта оптимизированная стратегия также известна как синхронное моделирование, управляемое событиями.

    Размер шага модельного времени зависит от требуемой точности моделирования. Для фиксированных и переменных задержек он выбирается таким образом, чтобы порядок происходящих процессов в реальной системе отражался модельным временем, т.е. два процесса происходящие в различное время в схеме моделировались в двух различных шагах модельного времени. В конце каждого цикла моделирования модельное время увеличивается на размер выбранного шага модельного времени.

•  Моделирование, управляемое событиями: Основным недостатком моделирования, управляемого временем является существование множества холостых шагов модельного времени (в течение которых не происходило никаких изменений в состояниях элементов или значений сигналов). Поэтому много времен расходуется на моделирование элементов, которые не изменяют своё состояние и значения сигналов, и на проверку того, произошли ли в схеме изменения, по сравнению с предыдущим шагом, или нет. Этот недостаток устраняется при моделировании, управляемом событиями, при котором изменения сигналов моделируются как события, связанные с определёнными шагами модельного времени. Шаги модельного времени указывают, на то, когда должны произойти эти события. Для сохранения последовательности событий во времени при моделировании, управляемом событиями, события всегда моделируются в порядке увеличения модельного времени. Таким образом, интервалы модельного времени, в течение которых не происходит никаких изменений в схеме, не моделируются, что обычно приводит к более быстрому моделированию.

МЕТОДЫ РАСПАРАЛЛЕЛИВАНИЯ ЛОГИЧЕСКОГО МОДЕЛИРОВАНИЯ

    Все методы распараллеливания логического моделирования могут быть разделены на два класса: методы синхронного и асинхронного параллельного логического моделирования.

 МЕТОДЫ СИНХРОННОГО ПАРАЛЛЕЛЬНОГО ЛОГИЧЕСКОГО МОДЕЛИРОВАНИЯ

     В методах синхронного параллельного логического моделирования все параллельно работающие процессоры выполняют моделирование элементов логической схемы в одинаковом для всех процессоров модельном времени. Примером синхронного моделирования является моделирование, управляемое времем. На каждом цикле синхронного параллельного моделирования все запланированные на моделирование элементы схемы  распределяются между несколькими процессорами, на которых происходит их моделирование. После окончания моделирования всех элементов происходит обновление их состояний и значений сигналов. На основании изменения состояний и сигналов элементов схемы формируется список событий для следующего цикла моделирования. Элементы схемы, для которых были сформированы новые события, планируются на моделирование в следующем цикле. Этот процесс происходит до тех пор, пока не будут промоделированы все запланированные элементы схемы. Этот метод схематически изображён на рис. 3.

Рисунок 3 – Синхронный параллелизм с шагом блокировки для логического моделирования.

Таким образом, после каждого цикла синхронного моделирования происходит синхронизация всех моделирующих процессоров. Следовательно, получаемое при синхронном параллельном моделировании ускорение зависит от скорости моделирования отдельных элементов схемы. Скорость увеличения модельного времени относительно реального времени определяется элементами схемы моделируемыми медленнее всех. Это может быть особенно проблематичным при моделировании схем содержащих как простые логические элементы, так и целые АЛУ или ЦПУ.

Методы асинхронного параллельного логического моделирования

    Основным механизмом при асинхронном параллельном моделировании является управляемое событиями дискретное моделирование. В методах асинхронного параллельного моделирования модель разбивается на несколько непересекающихся друг с другом подмоделей, и каждый процессор занимается моделированием одной или нескольких подмоделей. Процесс моделирования такой подмодели называется логическим процессом (ЛП), и выполняется как обычное последовательное моделирование. Каждый логический процесс может взаимодействовать с другими логическими процессами, в случае если изменения, происходящие в моделируемой им подмодели, могут оказать влияние на функционирование других подмоделей, моделируемых другими логическими процессами.

    Каждый логический процесс содержит данные, описывающие локальное состояние соответствующей части схемы. Все действия, происходящие в подмодели, реализуются как события, которые имеют определённое время наступления и могут вызывать изменения в локальном состоянии подмодели. Каждый ЛП также имеет локальное модельное время, скорость продвижения по которому зависит только от локальных событий, которые могут выполняться только в порядке времени их наступления (Рис. 4). При асинхронном логическом моделировании не существует понятия глобального модельного времени или глобального состояния. Локальные модельные времена в различных логических процессах обычно различаются и ЛП работают асинхронно.

    Для поддержания требуемого порядка обработки событий все события помещаются в очередь событий в порядке увеличения времени их наступления. ЛП всегда выбирает из очереди событий событие с самым маленьким временем наступления и обрабатывает его. При обработке очередного события локальное модельное время увеличивается до времени наступления этого события. Обработка очередного события также может привести к созданию нескольких новых событий, которые наступят в следующие моменты модельного времени. Если новое событие оказывает влияние на элементы локальной части схемы, то оно просто помещается в локальную очередь событий.

            Рисунок 4 – Структура распределённой системы моделирования.

    События, которые были сгенерированы для элементов схемы обрабатываемых другими логическими процессами, так называемые удалённые события, посылаются этим логическим процессам с помощью сообщений. При получении такого сообщения логический процесс создаёт локальное событие, отражающее удалённое событие, и вставляет это новое событие в локальную очередь событий. Для поддержания правильного порядка наступления локальных и удалённых событий, каждое посылаемое сообщение содержит значение локального модельного времени отправителя сообщения, в которое это сообщение было создано, и значение времени, которое указывает получателю, когда должно произойти событие. Вся эта процедура обычно называется планированием удалённых событий.

    В случае параллельного логического моделирования, события отражают изменения сигналов, которые управляют или управляются элементами схемы. Так как обычно сигналы реализуются как узлы, то изменения сигналов, которые оказывают влияние на другие части схемы, должны также распространяться через узлы. Это означает, что узлы сами могут быть распределенными, если их входы и выходы соединяют части схемы, обрабатываемые различными ЛП (5). Таким образом, в качестве таких распределённых узлов выступают создаваемые и пересылаемые сообщения для передачи изменений сигналов на удалённые части схемы.

            Рисунок 5 – Схема распределённой модели на уровне логических элементов.

    Мы обычно подразумеваем что узел и все элементы схемы, связанные с этим узлом, находятся в одном и том же ЛП. Если узлы и связанные с ними элементы схемы были помещены в различные логические процессы, то должна быть проделана дополнительная работа для сохранения состояний узлов. Это выполняется с помощью сообщений. Следовательно,  узлы, связывающие элементы схемы разных ЛП могут рассматриваться как специальные типы элементов схемы, пропускающие сигнал от одного ЛП к другому.

    Способ реализации распределённых узлов и сообщений зависит от организации доступа к памяти (общая или распределённая память) и от механизма передачи сообщений.

 Синхронизация логических процессов

    Отсутствие общего модельного времени для всех ЛП приводит к проблеме синхронизации различных ЛП. При последовательном моделировании все события моделируются в порядке времени их наступления. В случае отсутствия неопределённостей, два выполнения последовательного моделирования всегда будут иметь одинаковые результаты для одной и той же модели. Такое поведение ожидается и при параллельном моделировании.

    При последовательном моделировании событие с временем наступления t₁ не может обрабатываться раньше события с временем наступления t₂ если t₂ < t₁. Т.е. при последовательном моделировании порядок обработки событий соответствует времени их наступления. Это означает, что все события e_i, которые могут оказать влияние на событие e_j, обрабатываются перед обработкой события e_j. Таким образом, при моделировании соблюдаются последовательность событий и зависимости между ними имеющие место в реальной системе. Для событий имеющих одинаковое время наступления должны использоваться подходы, гарантирующие определённость и повторяемость. Для простоты далее будет подразумеваться, что при моделировании не может возникнуть двух событий с одинаковыми временами наступления.

    В параллельной среде, где каждый ЛП имеет своё собственное локальное модельное время и локальное состояние, глобальное состояние не доступно. В связи с этим, логическому процессу сложно предсказать, произойдёт ли в другом логическом процессе удалённое событие для данного логического процесса, которое имеет время наступление меньше чем времена наступления всех событий в его локальной очереди событий. Если произойдёт такое удалённое событие, то оно должно быть обработано перед обработкой всех локальных событий данного ЛП для поддержания требуемого порядка обработки событий. Решение о том, обрабатывать ли локальные события или ждать наступления удалённого события должно приниматься только на основе доступной информации о локальном состоянии данного ЛП.

    В связи с отсутствием информации о глобальном состоянии, каждый ЛП должен принимать соответствующие меры, чтобы быть уверенным в том, что все события моделируются в правильном порядке. Для достижения этого существуют два основных принципа [3,4], описанные далее.

 Консервативный подход

    При консервативном подходе, локальные события обрабатываются только в том случае, когда ЛП точно уверен в том, что для него не поступят прошедшие удалённые события с других ЛП (т.е. удалённые события, имеющие время наступления меньше чем  локальное модельное время). Это может быть достигнуто с помощью установления логических каналов между логическими процессами, которые могут планировать удалённые события друг для друга. Каждый раз, когда логический процесс планирует удалённое событие для другого логического процесса, часы канала устанавливаются на наименьшее значение локального модельного времени для обоих логических процессов. Так как логические процессы обрабатывают события только в порядке увеличения времени их наступления, и запланированные удалённые сообщения всегда имеют время наступления большее времени установленного в логическом канале, то значение часов логического канала не может уменьшаться. В случае, если логические каналы не получают сообщения в порядке FIFO, должны быть предусмотрены дополнительные действия для предотвращения уменьшения значения часов логического канала, так как это может нарушить консервативный подход. Перед обработкой очередного события логический процесс сверяет время наступления этого события с показаниями часов связанных с ним логических каналов. Если время наступления события является наименьшим, то данному логическому процессу не может быть запланировано более раннее удалённое событие, и ЛП обрабатывает очередное событие. В противном случае, логическому процессу может быть запланировано более раннее удалённое событие, и логический процесс должен быть заблокирован до тех пор, пока значения часов всех его каналов не станут больше времени наступления очередного события.

    Блокировки, свойственные консервативному подходу, почти всегда к появлению тупиков во время моделирования схем, содержащих обратные связи. Для решения этой проблемы, логические процессы должны собирать дополнительную информацию для выявления и разрешения тупиков, или должны использовать методы позволяющие избежать тупики (например используя так называемые пустые сообщения) Проблема тупиков иногда приводит к серьёзным дополнительным затратам при параллельном распределённом моделировании.

Оптимистические методы

    Второй класс алгоритмов моделирования называется оптимистическим. При оптимистическом подходе каждый логический процесс обрабатывает все события, находящиеся в его локальной очереди событий, в порядке времени их наступления. В случае, если для данного ЛП появиться прошедшее удаленное событие, то локальное модельное время и локальное состояние этого ЛП установятся в прежнее состояние, гарантирующее обработку всех событий в правильном порядке. Эта процедура называется откатом, поскольку локальное время и локальное состояние при этом возвращается к прежним значениям. Очереди событий также возвращаются в прежнее состояние, и обработанные события должны быть обработаны снова, после обработки пришедшего удалённого сообщения.

    С этой целью каждый ЛП периодически должен сохранять своё состояние, для того, чтобы он мог восстановить его в случае отката. Так как при обработке локальных событий могут быть выполнены ошибочные вычисления, то результаты этих вычислений должны также сбрасываться в прежнее состояние при откате. Это необходимо для отмены изменений в других ЛП, вызванных этими ошибочными вычислениями.

    Наиболее известным примером оптимистического метода является метод Деформации Времени (Time Warp).  Этот метод был разработан для случая, когда несколько ЛП взаимодействуют между собой при помощи сообщений. Во время отката изменения, сделанные в удалённых логических процессах, отменяются с помощью посылки им антисообщений для неверных удалённых событий, Локальные процессы сохраняют список своих входных сообщений до тех пор, пока не обработаются события, связанные с этими сообщениями. Если антисообщение находит соответствующее ему необработанное сообщение, то оба сообщения удаляются. Если сообщение, соответствующее полученному антисообщению, уже обработано, то необходимо также выполнить откат ЛП, получившего это антисообщение. Это может привести к последовательности откатов. Существует несколько методов оптимизации для избегания слишком длинных цепочек откатов, которые могут сделать оптимистический подход неэффективным.

    Необходимо отметить, что время, затраченное на обработку предполагаемых событий при оптимистическом подходе, может быть бесполезно потрачено при консервативном подходе из-за блокировки, вызванной ожиданием новых событий или тупиками и их разрешением.

Основные результаты работы

• изучены и систематизированы основные подходы к параллельному логическому моделированию;

• разработана программная система для оценки различных стратегий параллельного логического моделирования, а также стратегий разбиения схем и балансировки нагрузки;

• с помощью разработанной программы проведено исследования различных стратегий параллельного логического моделирования и стратегий разбиения схем;

• проанализированы результаты исследования различных стратегий параллельного логического моделирования;

• получены новые экспериментальные результаты по оценке времени параллельного логического моделирования.

Перечень публикаций

Библиографические ссылки

© 2002 Онищенко Денис