понедельник, 31 мая 2010 г.

Обновленная документация к Айвике

Если кому интересно, то я сегодня выложил обновленную версию свой библиотеки моделирования Айвика [http://sourceforge.net/projects/aivika/]. Там содержится более полная документация. Я описал то, как реализуются в Айвике activity-oriented и event-oriented парадигмы дискретно-событийного моделирования (DES). Также есть краткая информация о монаде DynamicsCont, которая лежит в основе моей реализации process-oriented парадигмы DES. В общем, среди парадигм теперь осталось осветить этот самый process-oriented DES и агентное моделирование (agent-based modeling).

Удивительное дело получается. Сплав методов функционального программирования и имитационного моделирования. Наиболее поразительны результаты в области DES. Тут и две монады, одна из которых является монадным трансформером, параметризованным по другой монаде. Тут еще computation expressions, которые являются в F# синтаксическим сахаром для монад и моноидов. Они делают сочинение моделей DES довольно приятным занятием. Тут же замыкания, которые используются для передачи данных вместе с событиями. Само событие у меня – это просто значение (), обернутое в монаду Dynamics. В общем, красота.

Что несколько удручает, так это большая нагрузка на систему управления памятью (GC). Монады означают, что создается во время моделирования до черта кратко-живущих функций с замыканиями (модуль системной динамики этим не страдает). Но дотнетовский GC неплох, очень неплох. Его двойник в Mono оказался на одной модельке намного тормознее.

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

воскресенье, 23 мая 2010 г.

Aivika версии 2.0

В ходе разработки моей небольшой библиотеки моделирования Айвика на языке F# произошел ряд важных прорывных событий. Во-первых, я значительно ускорил модуль системной динамики. Обсчет модели по методу Рунге-Кутта стал в раз 5 быстрее. Потом я добавил агентное моделирование (АМ), как его понял после прочтения статьи Андрея Борщева (одного из создателей системы AnyLogic). Для этого я переписал очередь событий модуля дискретно-событийного моделирования (DES), который стал на порядки производительнее. В общем, теперь охватываются все три основные парадигмы имитационного моделирования (ИМ), и в целом я доволен скоростью имитации. Также создал каталог с примерами моделей, каждая из которых снабжена справочной информацией и ссылками. Теперь более подробно.

Модуль системной динамики (SD)

Мне удалось значительно ускорить этот модуль за счет отказа от функций нескольких аргументов. После компиляции такие функции вызываются в конечном итоге через метод InvokeFast, который вопреки своему названию совершенно не быстр. Там используется RTTI, что делает каждый такой вызов достаточно медленным. Если же функция имеет всего один аргумент, то тогда вызывается напрямую абстрактный метод Invoke, минуя RTTI. Вызов Invoke очень эффективен.

Поэтому я переписал внутренности модуля так, чтобы везде использовалась функция одного аргумента. Теперь монада Dynamics стала просто частным случаем монады Reader с небольшим исключением: некоторые функции создают жестко контролируемый побочный эффект. Мне кажется, это можно как-то записать и в хаскеле, но там придется программировать на Си, реализуя местами функциональность монады ST.

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

Еще я лучше осознал смысл термина комбинатор. Оказывается, что все функции eDSL системной динамики являются у меня комбинаторами. Причем выглядят они почти так же как в специализированных системах Simtegra MapSys, ithink или Vensim. Но у меня функции, которые принимают одни функции и создают другие, обладая свойством замыкания.

Агентное моделирование (АМ)

Система AnyLogic использует карты состояний (statecharts) для описания агентов. Я придумал API, которое позволяет достаточно декларативно задавать агенты и их состояния так, как если бы мы использовали эти самые карты состояний. Получается кратко и наглядно. Все действия задаются в монаде Dynamics. Широко используются такие возможности F# как взаимно-рекурсивные определения через let rec и объектные выражения (object expressions). Благодаря монаде Dynamics агенты легко интегрируются с модулем системной динамики.

Дискретно-событийное моделирование (DES)

Агентное моделирование реализовано поверх очереди событий, которая является сердцем DES.

В предыдущей версии очередь была реализована как proof-of-concept, т.е. через двусторонний список… Тормоза стали особенно заметны после добавления АМ. Сначала я переписал очередь через иммутабельный хип, описанный в одной замечательной книге по хаскелю. Но функции добавления и удаления по-прежнему продолжали висеть в списке десяти самых тормозных функций, показываемых профайлером SharpDevelop. Тогда я переписал очередь через императивный бинарный хип, реализованный на основе массива. Функции работы c очередью ушли из списка. Агентное моделирование просто взлетело.

Примеры моделей

Я создал аналоги моделей, используемых в системах Simtegra MapSys (SD), Berkeley&Madonna (SD), AnyLogic (АМ) и SimPy (DES). Также реализовал пару моделей, описанных в книге Ильи Труба “Объектно-ориентированное моделирование на C++”.

Планы

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

Сейчас в документации достаточно полно освещен модуль системной динамики. Теперь нужно описать модули дискретно-событийного моделирования (DES) и агентного моделирования (АМ). Думаю, что можно заняться продвижением. Важно, что библиотеку можно использовать и из C#, но наиболее полно возможности доступны только через F#.

суббота, 1 мая 2010 г.

Релиз MapSim версии 4.1

Сегодня выложил релиз версии 4.1 движка моделирования MapSim для системной динамики. Он используется в визуальной среде для моделирования Simtegra MapSys, также разработанном мною в сотрудничестве со своим партнером. Основная новая возможность – можно менять параметры во время симуляции. Это нужно для проигрывания симуляций в MapSys. Все написано на C#.

Работа над ошибками

Выпустил новую версию 1.0.4.0 библиотеки моделирования Aivika на F#. В прежней версии обнаружил ошибку в реализации блоков try-finally и try-with для вычислительного выражения dynamicscont. По своей сути это частный случай монадного трансформера, построенного на основе продолжения. Дело в том, что фактически надо хранить два продолжения, а не одно. Первое продолжение используется для основной ветки вычислений. Второе продолжение - для обработки исключительных ситуаций.

Обновленный тип выглядит так:

type DynamicsCont<'a> = Dynamics<('a -> unit) * (exn -> unit)> -> Dynamics<unit>

Выводится из следующего типа Cont с учетом одного упрощения, характерного именно для монадного типа Dynamics:

type Cont<'a> = ('a -> unit) * (exn -> unit) -> unit

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

Сначала я составил необходимые функции для Cont. Потом сверил с реализацией стандартного async. Убедился, что все правильно. Затем перенес на тип DynamicsCont.

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