Русский     English

Айвика - конструктор общецелевых библиотек имитационного моделирования

Aivika - это платформа, состоящая из программных библиотек для имитационного моделирования. Написана на языке программирования Haskell. Выбор языка связан с реализованным методом моделирования, который по всей своей сути основан на идеях функционального программирования.

Основная версия

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

Соответствующий пакет называется aivika. Его можно установить с Hackage DB.

В основе метода лежит представление моделируемых активностей как неких вычислений.

Например, обработчик дискретного события представлен вычислением Event:

newtype Event a = Event (Point -> IO a)

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

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

Любая программа на языке Haskell начинается с того, что она запускается в рамках вычисления IO. Без этого программа не смогла бы выполнить ни одного побочного эффекта, а это часто именно то, что требуется от программы.

Основная версия Айвики использует это стандартное вычисление IO. Порождаемый код достаточно эффективен. Выполняется быстро. Монада IO позволяет делать очень многое. Поэтому API основной версии практически не обременено дополнительными ограничениями.

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

enqueueEvent :: Double -> Event () -> Event ()

Здесь видно, что функция enqueueEvent не имеет ограничений. Это - общее правило для основной версии Айвики.

Обобщенная версия

Другая часть платформы основана на обобщенной версии Айвики. Основная идея заключается в том, что мы можем заменить стандартное вычисление IO произвольным вычислением m. Тогда у нас Event становится монадическим трансформером:

newtype Event m a = Event (Point m -> m a)

Что это дает в практическом плане?

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

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

Именно такой библиотекой и является обобщенная версия Айвики. На уровне кода она во многом совпадает с основной версией, как по форме, так и по содержанию. Здесь мы оперируем обобщенными вычислениями типа Event m, где m - произвольное вычисление.

Соответствующий пакет в Hackage DB называется aivika-transformers.

Для определения ограничений, которым должно удовлетворять произвольное вычисление m, удобно использовать классы типов:

class (Monad m, ...) => MonadSD m
class (Monad m, ...) => MonadDES m

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

Для класса MonadDES главными требованиями являются две вещи:

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

class EventQueueing m where

    enqueueEvent :: Double 
                    -> Event m () 
                    -> Event m ()

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

Удовлетворив требованиям MonadDES, мы фактически получаем общецелевую библиотеку дискретно-событийного моделирования. То есть, обобщенную версию можно воспринимать как конструктор по созданию библиотек имитационного моделирования.

Вложенное моделирование

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

Таким случаем является вложенное моделирование. Суть в том, что мы должны уметь эффективно создавать ответвления текущего состояния модели. Например, это позволило бы заглянуть "в будущее" модели, а затем вернуться "в настоящее" с полученной информацией. Такое может быть полезно для финансового моделирования.

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

В пакете aivika-branches такое вычисление называется BrIO:

instance MonadDES BrIO

Его особенным свойством является функция, которая позволяет запустить заданное вычисление в будущем и вернуть результат в текущее вычисление, не трогая и никак не меняя текущее состояние имитационной модели:

futureEvent :: Double 
               -> Event BrIO a 
               -> Event BrIO a

Как это достигается?

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

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

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

Очередь обработчиков событий реализуется на основе неизменяемой (англ. immutable) структуры данных, которая помещается в изменяемую ячейку памяти. Каждый раз, когда кладется обработчик нового события или удаляется обработчик с минимальным временем, мы создаем новую версию очереди, которая физически может разделять до 99,99% процентов от старой очереди, но при этом которая будет являться совершенно другим практически независимым объектом. Существующие алгоритмы позволяют делать это достаточно эффективно, при этом только запрашивается новая память. Затем новую очередь кладем в заданную ячейку памяти вместо старого значения очереди.

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

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

Параллельное распределенное моделирование

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

В Айвике это будет пакет aivika-distributed. Он реализует оптимистичную стратегию на основе метода деформации времени (англ. time warp). При получении узлом просроченного сообщения, т.е. если локальное модельное время узла больше времени, в которое должно было быть обработано входящее сообщение, то тогда происходит прозрачный откат до времени, необходимого, чтобы обработать заданное сообщение. При этом отменяются все другие сообщения, которые были посланы узлом и стали недопустимыми. Откаты могут быть каскадными, охватывая множество узлов.

Как и прежде, здесь реализуется вычисление, которое удовлетворяет требованиям класса типов MonadDES. Соответствующее вычисление называется DIO:

instance MonadDES DIO

Для отсылки сообщений другим узлам можно использовать следующие функции:

sendMessage :: forall a. P.Serializable a 
               => P.ProcessId a 
               -> a 
               -> Event DIO ()

enqueueMessage :: forall a. P.Serializable a 
                  => P.ProcessId a 
                  -> Double 
                  -> a 
                  -> Event DIO ()

Здесь префикс P означает импорт из пакета distributed-process. Вторая функция позволяет назначить точное модельное время, в которое должно быть обработано заданное сообщение. Первая функция задает то, что сообщение должно быть обработано в то же время, в которое было послано, что потенциально может привести к зацикливанию в случае каскадных откатов. Поэтому рекомендуется использовать вторую функцию, пусть с совсем небольшим зазором по времени.

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

messageReceived :: forall a. P.Serializable a 
                   => Signal DIO a

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

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

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

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

Для этого в обобщенной версии Айвики определена следующая функция:

retryEvent :: MonadException m 
              => String 
              -> Event m a

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

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

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

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

class EventIOQueueing m where

    enqueueEventIO :: Double 
                      -> Event m () 
                      -> Event m ()

Эта функция имеет смысл и для вычисления DIO, которое реализует заданный класс типов.

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