Параллельная симуляция. Часть 1. Последовательные основы

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

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

Современные вычислительные комплексы достаточно сложны в своём устройстве: во-первых, они состоят из множества независимых устройств, большинство которых сильно отличается от ЦПУ по принципам своей работы (и, как мы дальше увидим, их симуляция также производится другим образом); во-вторых, в одной системе может быть больше одного процессора. В реальности все устройства работают одновременно, тогда как их модели исполняются последовательно в одном потоке (вопросы создания параллельных моделей составляют отдельную объёмную тему и будут рассмотрены во второй части).

Дискретная модель событий

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

Дискретность событий и времени

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

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

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

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

Уточним дополнительно понятие «событие»: изменение состояния системы или порождение одного или более новых событий, которые запланированы произойти в будущем. Например, некоторый таймер, будучи включённым, генерирует прерывание каждые 10 тактов. Тогда событие этого устройства заключается в изменении состояния сигнальной шины и создании следующего события, отдалённого на 10 тактов в будущее.

Симуляция с фиксированным шагом

Симуляция с фиксированным шагом (time stepped) [3] — наверное, самая первая идея, которая приходит на ум. Интуитивно понятно, что для цифровых систем, управляемых тактовым генератором с фиксированной частотой, существует минимальный интервал времени Δ t, разделяющий события. В таком случае алгоритм состоит в том, чтобы продвигать симулируемое время скачками Δ t, на каждом шаге исполняя все события, случившиеся на этом шаге, если их число больше нуля.

Это последнее обстоятельство играет существенную роль. В реальности далеко не на каждом такте происходят какие-либо события, требующие симуляции. Большую часть времени симулятор будет останавливаться только для того, чтобы обнаружить, что на текущем такте ему делать нечего. Конечно, это обстоятельство ограничивает скорость симуляции.

Отметим, что моделирование процессоров с помощью интерпретации является примером симуляции с фиксированным шагом, равным длительности одной инструкции.

Симуляция, управляемая событиями

Рассмотрим более эффективную схему симуляции, иногда характеризуемую как управляемая событиями (event driven). Продвижение симулируемого времени при этом делается «скачками» от одного события до следующего.

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

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

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

Добавление новых событий.

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

Введённая методика моделирования получила название симуляции дискретных событий (discrete event simulation, DES) [1,2,5], которая является достаточно общей: с её помощью можно описать и исследовать поведение очень широкого класса вычислительных устройств, а также любых других систем, никак не связанных с компьютерами. Важным её преимуществом является разделение архитектурного состояния симуляции, хранимого в составе модельных объектов, и порядка вызова обработчиков этого состояния, определяемого единой очередью.

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

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

  • Порождаемые события не могут попасть в прошлое, т.е. иметь метку времени меньше, чем текущее время.
  • Обработка событий может не только порождать события в будущем, но и отменять некоторые из них (ещё не обработанные). Пример: описанный ранее таймер с периодом работы 10 тактов получил сигнал о полном выключении на 5-м такте своей работы. Обработка этого события заключается в изменении внутреннего состояния устройства, а также отмене ранее запланированного события, так как оно уже не произойдёт.
  • Несколько событий могут иметь одинаковую метку времени. Чаще всего придерживаются правила, что они будут обработаны в порядке их добавления в очередь.
  • В модели может существовать больше одной очереди. Например, можно иметь одну очередь, хранящую события, привязанные к инструкциям процессора, а другую — к фронтам тактового генератора. Другой вариант — многопроцессорные системы, в которых с каждым ЦПУ связана своя очередь. Обработка событий из всех очередей происходит в порядке, определяемом принципами работы и требованиями на очерёдность исполнения событий модели.

Два класса моделей

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

  1. Внутренние факторы, заложенные в саму модель устройства. Интерпретатор, двоичный транслятор и метод прямого исполнения выполняют шаг за шагом до тех пор, пока не будут остановлены или внешним воздействием (прерыванием, установкой флага исключения и т.п.), или окончанием входных данных (достижение лимита числа исполненных инструкций, времени симуляции и т.п.). Такие модели мы будем называть исполняющими, или управляемыми исполнением (execution driven)
  2. Внешние факторы, стимулирующие модель изменить однократно своё состояние и затем вернуть управление. Любое устройство, входящее в схему DES, является примером такого подхода. Соответствующие им модели — неисполняющие, или управляемые событиями (event driven).

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

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

  1. Определяется длительность интервала, в течение которого в моделируемой системе не произойдёт никаких событий. Эта величина равна расстоянию от текущего момента до самого раннего ещё не обработанного события в очереди.
  2. Управление передаётся в модель процессора, которая исполняется некоторое время, не превышающее найденное в первом пункте значение. Затем она останавливается и возвращает управление симулятору.
  3. Симулируемое время продвигается на число тактов, потраченных процессором. События обрабатываются по модели DES. Затем мы переходим к первому шагу.

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

Рис. 2. Симуляция исполняющего устройства, перемежающаяся с обработкой дискретных событий

В каких случаях следует использовать модели каждого из описанных типов? Устройство выгодно представлять исполняющей моделью, если для него верно следующее:

  • Оно меняет своё состояние каждый или почти каждый такт.
  • События к нему от сторонних устройств приходят в среднем редко (раз в 100–1000 тактов).
  • Интерес для исследователя представляют внутренние процессы устройства [4].

Устройство следует симулировать как неисполняющее, если ему присущи следующие свойства.

  • Изменение его состояния происходит в среднем редко и асинхронно по отношению к остальным устройствам.
  • Характер взаимодействия с другими агентами представлятся в виде «запрос–отклик».
  • Оно может быть представлено как «чёрный ящик» без внутренней структуры.

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

Рис. 3. Косимуляция моделей исполняющих устройств и DES. При каждой передаче управления соответствующая модель сообщает другой о том, насколько было продвинуто симулируемое время

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

Моделирование многопроцессорных систем

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

Самое очевидное решение — чередовать исполнение всех процессоров на каждом шаге. В таком случае их состояние и «локальное» симулируемое время всегда будут отличаться не более чем на один такт.

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

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

Отрезок времени, выделяемый устройству на исполнение, именуется квотой (другие названия — квант времени, quota, quantum, time slice). Устройство, находящееся в процессе исполнения в рамках своей квоты, считается текущим. Процесс исполнения многопроцессорной системы проиллюстрирован на рис. 4 и 5.

Рис. 4. Совместная симуляция нескольких процессоров. Отдельные интервалы симуляции чередуются на хозяйском процессоре

Рис. 5. Совместная симуляция нескольких процессоров. В контексте моделируемой системы процесс выглядит как параллельная непрерывная работа

Замечания к предложенной схеме

  • Процессор может исполнить меньше инструкций, чем содержится в выданной ему квоте. Пример причины для ранней остановки — событие во внешнем устройстве, которое необходимо обработать согласно его метке времени. После обработки всех событий, «мешавших» продвижению текущей модели, она либо может продолжить исполнение остатка своей квоты, либо передать управление другому устройству — это зависит от деталей алгоритма планировщика.
  • Не следует увлекаться излишне большими квотами, пытаясь ускорить исполнение — это может негативно повлиять на точность модели, потому что моменты прерывания работы исполняющих моделей являются точками синхронизации состояния всей системы. Между ними каждое устройство работает в полной изоляции, в то время как остальные заморожены и не могут посылать ему никакие сигналы. Если программа, исполняемая в модели, ожидает сообщений от других систем в течение ограниченного времени, то квота не должна превышать это время тайм-аута.
  • В духе модели DES операция переключения текущего исполняющего устройства может быть реализована как псевдособытие, периодически вставляемое в очередь и при своей обработке вызывающее деактивацию текущего и выбор следующего активного процессора.

Литература

  1. Albrecht M. C. (Mike) Introduction to Discrete Event Simulation. — 2010. — URL: http://www.albrechts.com/mike/DES/Introduction%20to%20DES.pdf .
  2. Cain Harold W. Precise and Accurate Processor Simulation. —2002. — URL: http://pages.cs.wisc.edu/~cain/pubs/caecw2002_final.pdf .
  3. Ferscha Alois. Parallel and Distributed Simulation of Discrete Event Systems. — 1995. — URL: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0D07CB3110B890F247E12489F3264E62?doi=10.1.1.19.6226&rep=rep1&type=pdf 
  4. Fritzson P.A. Principles of object-oriented modeling and simulation with Modelica 2.1. — IEEE Press, 2004. — ISBN: 9780471471639. — URL: http://ieeexplore.ieee.org/search/srchabstract.jsp?arnumber=5264347 .
  5. Fujimoto Richard M. Parallel and Distributed Simulation Systems. — New York, NY, USA: John Wiley & Sons, Inc., 2000. — ISBN: 0471183830.
For more complete information about compiler optimizations, see our Optimization Notice.