среда, 16 августа 2017 г.

Трансляция модели из Python в Haskell

Вспомнив известные слова про гору и Магомета, решил сделать свои наработки более доступными. Создал для языка программирования Python пакет aivika-modeler, который позволяет создавать дискретно-событийные модели. а затем запускать основанные на них имитационные эксперименты по методу Монте-Карло с тысячами запусков в серии и более.

Пакет больше предназначен быть неким клеем, с помощью которого на языке Python можно соединять и объединять готовые компоненты в единую модель, причем сами компоненты предполагается создавать уже на языке Haskell. Однако, во многих случаях должно хватить существующего набора компонент, и поэтому часто можно ограничиться одним языком Python. В планах добавить поддержку GPSS-подобного DSL.

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

Итак, модель описывается на языке Python. По ней автоматически создается соответствующий код на языке Haskell. Более того, создается готовый проект на основе системы сборки Stack. Собственно, это главное техническое требование - на системе пользователя должен быть установлен Stack. Здесь предвижу некоторые возможные трудности с пакетом old-time на некоторых системах Windows, но надеюсь, что со временем они благополучно разрешатся.

Так вот, автоматически созданный проект на Stack собирается, а потом запускается на исполнение. В случае успеха в самом конце открывается веб-браузер с результатами имитационного эксперимента. Там могут быть графики, гистограммы, ссылки на таблицы в формате CSV, сводная статистика и прочая информация. Вид и формат желаемых итоговых результатов задается также на языке Python.

Мне был довольно интересен такой эксперимент по использованию Haskell из Python. Может быть, кто-нибудь возьмет идею на вооружение

понедельник, 20 марта 2017 г.

GPSS на Haskell

Если кто еще не знает, GPSS - это один из самых известных специализированных языков дискретно-событийного моделирования. Так вот, я добавил в AivikaSim [http://www.aivikasoft.com/ru/products/aivikasim.html] поддержку GPSS-подобного предметного-ориентированного языка. Это пакет aivikasim-gpss [https://github.com/dsorokin/aivikasim-gpss]. Вот здесь находится работающий тестовый пример [https://github.com/dsorokin/aivikasim-gpss-test].

Постарался охватить основные моделирующие блоки, такие как SEIZE, PREEMPT, GATHER, ASSEMBLE, MATCH. Другие либо имеют явные аналоги у меня, либо требуют небольшого программирования как в случае блоков LINK и UNLINK. Не гарантируется точного совпадения результатов с GPSS World, так как логика работы с транзактами у меня совершенно иная, но в некоторых случаях результаты получаются очень близкими.

Вот, здесь примеры моделей [https://github.com/dsorokin/aivikasim-gpss/tree/master/examples] из красной книги Шрайбера по GPSS. Там в начале каждого примера приводится соответствующий код модели на языке GPSS World. Можно сличить результаты.

Example2A.hs означает, что это пример 2A из книги, а вот Example7-26.hs означает, что это соответствует модели на рисунке 7.26. Модели с окончанием Trans, такие как Example2BTrans.hs, означают, что там используется обобщенная версия AivikaSim. Фактически это означает, что приведенный код готов для использования в распределенной имитации.

Более того, пример Example7-26Distributed.hs непосредственно запускается через модуль распределенного моделирования. В данном случае это формально последовательная модель, но запускается она фактически в виде распределенной, т.е. она готова для кластера компьютеров. Используется оптимистичный алгоритм деформации времени.

Сразу напишу, что хотя для приведенных моделей удалось добиться очень хорошего соответствия с GPSS, то вот для примера 5D из книги Шрайбера такого близкого соответствия, скорее всего, не получится. Сейчас совпадение идет в 9 случаях против одного, где модель будет уже другой. Причем, совпадает даже на очень нетривиальных моделях, где важен порядок обработки транзактов.

Касательно скорости моделирования. Модуль GPSS-подобного языка последовательной версии AivikaSim моделирует примерно в 5-7 раз медленнее, чем GPSS World, но зато позволяет использовать разные методы в рамках одной модели, например, агенты и события. Для сравнения, распределенный модуль AivikaSim на последовательных задачах медленнее в раз 6-9, чем последовательная версия AivikaSim, но зато распределенную версию можно запустить много раз на разных узлах в рамках одной модели. Например, можно запустить 7 параллельно работающих локальных процессов на одной системе с 8-ядерным процессором.

Если кто захочет проверить результаты, то вот руководство по установке AivikaSim [https://github.com/dsorokin/aivikasim-installer].

суббота, 18 февраля 2017 г.

Демо-тест распределенной имитации на монадах

Создал тестовый демонстрационный пример распределенной дискретно-событийной имитации на основе своего нового продукта AivikaSim. Тест легко воспроизвести по приведенной инструкции:

https://github.com/dsorokin/aivikasim-distributed-test

Код написан на языке Haskell, но для воспроизведения теста язык программирования знать не требуется.

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

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

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

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

Только стоит заметить, что восстановление имитации на Linux и macOS работает как часы, а вот на Windows немного похрамывает, но, видимо, это связано с тем, что у Haskell-сообщества Unix-системы приоритетнее, что скорее хорошо.

По приведенной ссылке лишь скромный небольшой демонстрационный пример, показывающий возможности системы AivikaSim. 

вторник, 29 ноября 2016 г.

Сетевое моделирование с Айвикой

Давно присматриваюсь к сетевому моделированию (англ. network simulation). Нахожу, что многое можно моделировать с помощью моей Айвики уже сейчас, в том числе, моделировать распределенно на кластере или параллельно на суперкомпьютере.

Основная идея такая. Обычно говорят о портах - источниках данных. В Айвике источники могут быть как активными, так и пассивными. Активный источник сам проталкивает данные дальше для обработки. Это у меня тип Signal a (или Signal m a в обобщенной версии). Тогда каналом будет просто преобразование одного сигнала в другой. Модуль будет функцией, отображающей входные сигналы на выходные.

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

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

Пассивные источники данных у меня в Айвике представлены потоками Stream a (или Stream m a в обобщенной версии). Их нужно запрашивать, чтобы вытянуть из них данные. Их можно распараллеливать для обработки, а потом снова сливать в один поток.

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

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

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


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

Распределенное моделирование c Айвикой

Обновил версию aivika-distributed, которую можно использовать для распределенного и параллельного моделирования. Реализована оптимистичная стратегия по методу Time Warp. В этой версии значительно улучшена синхронизация глобального времени. Используется алгоритм Самади. В общем, если соединения между узлами достаточно надежные, то распределенная имитация должна вполне хорошо работать.

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

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

Собственно, все! В следующем сообщении напишу, как это можно применить к сетевому моделированию (англ. network simulation)

вторник, 7 июня 2016 г.

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

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

пятница, 29 апреля 2016 г.

Айвика для кластера и суперкомпьютера

В прошлую субботу выпустил первую версию [5] своей Айвики, которая позволяет создавать и обсчитывать параллельные распределенные дискретно-событийные модели на кластере и/или суперкомпьютере.

В общем, идея такая. 

У меня есть основная версия [2] обще-целевой библиотеки, о которой я много писал у себя в блоге. Она построена на основе стандартного вычисления IO. Самая быстрая версия. Можно автоматизировать вывод графиков и таблиц. Есть документация [1] в формате PDF. Много примеров.

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

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

Так родилась версия [4] для вложенных имитаций. Это когда из «настоящего» мы можем относительно дешево и быстро заглядывать в «будущее» модели столько раз, сколько необходимо, а потом на основе полученной информации принимать решения уже в «настоящем». Конек в относительной дешевизне создания вложенных имитаций и в том, что это по-прежнему обще-целевая библиотека имитационного моделирования.

Теперь же воплотил в жизнь еще и версию [5] для параллельного распределенного имитационного моделирования. Тоже обще-целевая библиотека моделирования. Здесь независимые узлы могут обмениваться друг с другом асинхронными сообщениями, привязанными к временным меткам. Если на узле уже «будущее», а приходит сообщение в «прошлое», то происходит прозрачный откат до «прошлого» модели. Все сообщения, которые были посланы узлом и стали устаревшими, отменяются, и, соответственно, рассылаются так называемые «анти-сообщения». Короче, реализована оптимистичная стратегия с прозрачными, возможно, каскадными откатами на основе идей метода «деформации времени» (англ. «time warp»), датируемого началом 80-х.

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