Пока в отпуске написал статью о том, как функциональное программирование может быть применено к задачам вложенного моделирования и задачам параллельного распределенного моделирования на примере моей Айвики. Раскрыты некоторые ключевые детали реализации для более полного понимания того, как работает Айвика.
вторник, 7 июня 2016 г.
пятница, 29 апреля 2016 г.
Айвика для кластера и суперкомпьютера
В прошлую субботу выпустил первую версию [5] своей Айвики, которая позволяет создавать и обсчитывать параллельные распределенные дискретно-событийные модели на кластере и/или суперкомпьютере.
В общем, идея такая.
У меня есть основная версия [2] обще-целевой библиотеки, о которой я много писал у себя в блоге. Она построена на основе стандартного вычисления IO. Самая быстрая версия. Можно автоматизировать вывод графиков и таблиц. Есть документация [1] в формате PDF. Много примеров.
Потом я обобщил эту версию для произвольных вычислений, которые должны удовлетворять небольшому числу ограничений, в числе которых возможность создавать изменяемые ссылки и возможность иметь очередь событий. Так родилась обобщенная версия [3] библиотеки. Это тоже обще-целевая библиотека с возможностью формулировать модели в терминах событий, дискретных процессов, очередей, ресурсов, потоков транзактов, процессоров и т.п., но в рамках задаваемого извне типа вычислений. Практически совпадает с основной версией на уровне реализации, в том числе, в названиях, но типы и сигнатуры функций другие.
Дальше идут приложения. Создаю частные случаи вычислений, удовлетворяющие требованиям обобщенной версии Айвики, но добавляющие те или иные желаемые свойства.
Так родилась версия [4] для вложенных имитаций. Это когда из «настоящего» мы можем относительно дешево и быстро заглядывать в «будущее» модели столько раз, сколько необходимо, а потом на основе полученной информации принимать решения уже в «настоящем». Конек в относительной дешевизне создания вложенных имитаций и в том, что это по-прежнему обще-целевая библиотека имитационного моделирования.
Теперь же воплотил в жизнь еще и версию [5] для параллельного распределенного имитационного моделирования. Тоже обще-целевая библиотека моделирования. Здесь независимые узлы могут обмениваться друг с другом асинхронными сообщениями, привязанными к временным меткам. Если на узле уже «будущее», а приходит сообщение в «прошлое», то происходит прозрачный откат до «прошлого» модели. Все сообщения, которые были посланы узлом и стали устаревшими, отменяются, и, соответственно, рассылаются так называемые «анти-сообщения». Короче, реализована оптимистичная стратегия с прозрачными, возможно, каскадными откатами на основе идей метода «деформации времени» (англ. «time warp»), датируемого началом 80-х.
В распределенной версии экспериментальная реализация механизма синхронизации времени. Есть разные параметры, которые можно настраивать. Правда, с документацией немного туговато, да и требуется хорошее знание Haskell, но там очень мало отличий от основной версии, для которой уже есть документация. Если есть желающие, то пробуйте в своих университетах! :)
воскресенье, 31 января 2016 г.
Айвика: ветвящееся дискретно-событийное моделирование на Haskell
На днях сделал анонс своих новых наработок на Haskell Cafe. Повторю и здесь.
Выпустил три новых релиза. Это входит в серию библиотек, которую я условно называю Айвикой [1, 2, 3]. Главная новинка - пакет aivika-branches [3], который позволяет делать то, что я для себя назвал «ветвящимся дискретно-событийным моделированием» (англ. «branching discrete event simulation») с возможностью запускать вложенные имитации внутри имитации для предсказания и оценки будущего поведения системы на этапе самой имитации. Сейчас попробую описать подробнее.
Допустим, что у нас есть достаточно общая библиотека, которая позволяет реализовывать дискретно-событийные модели. Там могут быть потоки случайных заданий (требований, они же, тразакты). Могут быть ограниченные ресурсы, за которые идет конкурентная борьба дискретных процессов. Есть глобальная очередь событий. Есть просто очереди сущностей. Есть активности, привязанные к обработке событий и т.п. В общем, все то, что реализовано в моем пакете aivika [1].
Мой метод заключается в том, что мы описываем поведение имитационной модели с помощью абстрактных вычислений. Во время своего запуска основное вычисление имеет состояние, которое сводится к состоянию очереди обработчиков будущих событий и к состоянию всех ссылок (они же, переменные), которые используются в модели.
Теперь главная новинка. Представим, что мы умеем достаточно эффективно клонировать состояние модели, порождая производную ветвь модели в текущий момент времени. То есть, мы клонируем и очередь всех обработчиков будущих событий, которые должны еще отработать в будущем. Мы также клонируем состояние всех изменяемых ссылок для новой ветки модели.
Тогда мы можем запросить из текущего времени будущее значение заданного под-вычисления, как если бы мы продолжили текущую имитацию, но без фактического изменения самой имитации!
Именно это умеет делать следующая функция из нового пакета aivika-branches [3]:
futureEvent :: Double -> Event BrIO a -> Event BrIO a
Здесь мы создаем новую ветку имитационной модели и запускаем заданное под-вычисление в желаемое время в будущем или настоящем, причем текущая имитационная модель остается нетронутой. В порожденной ветке отрабатывают все ожидающие выполнения обработчики событий вплоть до заданного времени.
Что касается типов, то здесь появляются монадные трансоформеры из другого пакета aivika-transformers [2], который является обобщение пакета aivika. На самом деле, пакет aivika-transformers я подготовил для реализации распределенного и параллельного дискретно-событийного моделирования, но он получился таким общим и гибким, что я смог его применить и к ветвящемуся дискретно-событийному моделированию.
Как я уже написал, фишка в том, что функция futureEvent относительно дешевая. Мы можем относительно быстро клонировать состояние целого мира имитационной модели! Это стало возможным во многом благодаря повсеместному использованию приемов функционального программирования (тут в скобках замечу, что очень забавно со стороны смотрятся те, кто наивно полагает по своему неразумению, что монада IO не относится к функциональному программированию. Просто не понимают, что функциональное и императивное программирование - это разные, но совсем не антагонистичные и не исключающие друг друга взгляды на то, как можно писать компьютерные программы. Эти оба взгляда вполне могут сосуществовать). Еще там используются такие вещи, как слабые ссылки для того, чтобы не было утечки пространства (англ. space leak) при разветвлении состояния ссылок, чтобы вовремя подчищалась память.
Фактически получаем дерево имитаций, которое нужно ограничивать или по уровню вложенности или с помощью метода ветвей и границ. Что-то похожее встречается в финансовом моделировании.
Вообще, мне кажется, что ветвящееся дискретно-событийное моделирование может быть полезно для описания систем, которые моделируют поведение человека, который способен предвидеть будущее, самообучаться и сообразно менять свое поведение на ходу. Мне кажется, что это очень интересная и перспективная область.
[1] http://hackage.haskell.org/package/aivika
[2] http://hackage.haskell.org/package/aivika-transformers
[3] http://hackage.haskell.org/package/aivika-branches
Выпустил три новых релиза. Это входит в серию библиотек, которую я условно называю Айвикой [1, 2, 3]. Главная новинка - пакет aivika-branches [3], который позволяет делать то, что я для себя назвал «ветвящимся дискретно-событийным моделированием» (англ. «branching discrete event simulation») с возможностью запускать вложенные имитации внутри имитации для предсказания и оценки будущего поведения системы на этапе самой имитации. Сейчас попробую описать подробнее.
Допустим, что у нас есть достаточно общая библиотека, которая позволяет реализовывать дискретно-событийные модели. Там могут быть потоки случайных заданий (требований, они же, тразакты). Могут быть ограниченные ресурсы, за которые идет конкурентная борьба дискретных процессов. Есть глобальная очередь событий. Есть просто очереди сущностей. Есть активности, привязанные к обработке событий и т.п. В общем, все то, что реализовано в моем пакете aivika [1].
Мой метод заключается в том, что мы описываем поведение имитационной модели с помощью абстрактных вычислений. Во время своего запуска основное вычисление имеет состояние, которое сводится к состоянию очереди обработчиков будущих событий и к состоянию всех ссылок (они же, переменные), которые используются в модели.
Теперь главная новинка. Представим, что мы умеем достаточно эффективно клонировать состояние модели, порождая производную ветвь модели в текущий момент времени. То есть, мы клонируем и очередь всех обработчиков будущих событий, которые должны еще отработать в будущем. Мы также клонируем состояние всех изменяемых ссылок для новой ветки модели.
Тогда мы можем запросить из текущего времени будущее значение заданного под-вычисления, как если бы мы продолжили текущую имитацию, но без фактического изменения самой имитации!
Именно это умеет делать следующая функция из нового пакета aivika-branches [3]:
futureEvent :: Double -> Event BrIO a -> Event BrIO a
Здесь мы создаем новую ветку имитационной модели и запускаем заданное под-вычисление в желаемое время в будущем или настоящем, причем текущая имитационная модель остается нетронутой. В порожденной ветке отрабатывают все ожидающие выполнения обработчики событий вплоть до заданного времени.
Что касается типов, то здесь появляются монадные трансоформеры из другого пакета aivika-transformers [2], который является обобщение пакета aivika. На самом деле, пакет aivika-transformers я подготовил для реализации распределенного и параллельного дискретно-событийного моделирования, но он получился таким общим и гибким, что я смог его применить и к ветвящемуся дискретно-событийному моделированию.
Как я уже написал, фишка в том, что функция futureEvent относительно дешевая. Мы можем относительно быстро клонировать состояние целого мира имитационной модели! Это стало возможным во многом благодаря повсеместному использованию приемов функционального программирования (тут в скобках замечу, что очень забавно со стороны смотрятся те, кто наивно полагает по своему неразумению, что монада IO не относится к функциональному программированию. Просто не понимают, что функциональное и императивное программирование - это разные, но совсем не антагонистичные и не исключающие друг друга взгляды на то, как можно писать компьютерные программы. Эти оба взгляда вполне могут сосуществовать). Еще там используются такие вещи, как слабые ссылки для того, чтобы не было утечки пространства (англ. space leak) при разветвлении состояния ссылок, чтобы вовремя подчищалась память.
Фактически получаем дерево имитаций, которое нужно ограничивать или по уровню вложенности или с помощью метода ветвей и границ. Что-то похожее встречается в финансовом моделировании.
Вообще, мне кажется, что ветвящееся дискретно-событийное моделирование может быть полезно для описания систем, которые моделируют поведение человека, который способен предвидеть будущее, самообучаться и сообразно менять свое поведение на ходу. Мне кажется, что это очень интересная и перспективная область.
[1] http://hackage.haskell.org/package/aivika
[2] http://hackage.haskell.org/package/aivika-transformers
[3] http://hackage.haskell.org/package/aivika-branches
пятница, 20 ноября 2015 г.
Релиз системы моделирования VisualAivika 5
Всем привет! Недавно выпустил версию своей визуальной системы моделирования для системной динамики VisualAivika.
Функциональное программирование здесь при том, что на конечном этапе исходная система диффуров преобразуется в модель в терминах моей библиотеки Айвика, которая написана на языке F#, который, как говорят его создатели, functional first.
Может быть интересна история создания Айвики. Первоначальная идея возникла при изучении Haskell, но я очень быстро переключился реализовывать идею на F#. Первая версия на F# была ужасна. Ее до сих пор можно найти на простора интернета, но я не хочу давать ссылку на нее - пусть останется для истории.
Мне всегда было очень интересно реализовать Айвику на Haskell. И попытка переписать с F# на Haskell была неудачной. Нарвался на то, что компилятор Haskell предполагает ссылочную прозрачность, и соответственно оптимизирует код. Это решается с помощью прагм, что некрасиво, но главная нехорошесть была в другом. У меня там возникал вложенный двухэтажный одноименный тип в сигнатурах, что было прямым указанием на какую-то логическую ошибку.
Прояснение пришло не сразу. Сначала я пытался все выразить в рамках одного вычисления, т.е. монады. Все кардинально упростилось, когда я понял, что мне нужно ввести несколько вычислений. В итоге полностью избавился от нехорошего unsafePerformIO, сигнатуры функций стали понятными с первого взгляда, код целиком стал ссылочно-прозрачным. Просто красота! Так родилась версия Айвики для Haskell.
Потом я уже переписал обратно c Haskell на F#. Пришлось пойти не некоторые упрощения и хитрости, но в целом, версия Айвики на F# примерно соответствует своей старшей сестрице, хотя и будет немного слабее. Именно переписанная версия теперь используется у меня в визуальной системе моделирования.
Возвращаясь к исходной теме. Даже если имитационное моделирование не входит в область ваших интересов, то может быть интересно то, что VisualAivika позволяет создавать так называемые Casual Loop Diagrams (CLD), область применения которых довольно широка. Это Systems Thinking или системное мышление.
Ниже показан пример такой диаграммы, которую я накидал в своей VisualAivika за минуту-две.
Здесь знак плюса указывает на положительную связь, знак минуса - на отрицательную. Видим, что приведенный цикл является устойчивым. Нет ни бурного роста, ни активного падения.
Функциональное программирование здесь при том, что на конечном этапе исходная система диффуров преобразуется в модель в терминах моей библиотеки Айвика, которая написана на языке F#, который, как говорят его создатели, functional first.
Может быть интересна история создания Айвики. Первоначальная идея возникла при изучении Haskell, но я очень быстро переключился реализовывать идею на F#. Первая версия на F# была ужасна. Ее до сих пор можно найти на простора интернета, но я не хочу давать ссылку на нее - пусть останется для истории.
Мне всегда было очень интересно реализовать Айвику на Haskell. И попытка переписать с F# на Haskell была неудачной. Нарвался на то, что компилятор Haskell предполагает ссылочную прозрачность, и соответственно оптимизирует код. Это решается с помощью прагм, что некрасиво, но главная нехорошесть была в другом. У меня там возникал вложенный двухэтажный одноименный тип в сигнатурах, что было прямым указанием на какую-то логическую ошибку.
Прояснение пришло не сразу. Сначала я пытался все выразить в рамках одного вычисления, т.е. монады. Все кардинально упростилось, когда я понял, что мне нужно ввести несколько вычислений. В итоге полностью избавился от нехорошего unsafePerformIO, сигнатуры функций стали понятными с первого взгляда, код целиком стал ссылочно-прозрачным. Просто красота! Так родилась версия Айвики для Haskell.
Потом я уже переписал обратно c Haskell на F#. Пришлось пойти не некоторые упрощения и хитрости, но в целом, версия Айвики на F# примерно соответствует своей старшей сестрице, хотя и будет немного слабее. Именно переписанная версия теперь используется у меня в визуальной системе моделирования.
Возвращаясь к исходной теме. Даже если имитационное моделирование не входит в область ваших интересов, то может быть интересно то, что VisualAivika позволяет создавать так называемые Casual Loop Diagrams (CLD), область применения которых довольно широка. Это Systems Thinking или системное мышление.
Ниже показан пример такой диаграммы, которую я накидал в своей VisualAivika за минуту-две.
Здесь знак плюса указывает на положительную связь, знак минуса - на отрицательную. Видим, что приведенный цикл является устойчивым. Нет ни бурного роста, ни активного падения.
пятница, 12 июня 2015 г.
Обновленная Aivika for .NET
Открыл по лицензии GNU дополнительные компоненты к версии своей библиотеки имитационного моделирования Айвика, написанной на языке F#. Теперь по открытой лицензии доступны не только разработка и запуск модели в Visual Studio или Xamarin Studio, но можно также сохранять результаты, строить графики и т.п. Все это удовольствие автоматизируется несколькими дополнительными строками кода.
В дополнение к существующей документации в формате PDF выложил исходники примеров, которые охватывают наиболее известные области имитационного моделирования: системная динамика, дискретно-событийное моделирование (управляемое временем, событиями и процессами), базовое агентное моделирование.
Здесь замечу, что версия на Haskell по-прежнему остается более функциональной, и она имеет более чистый дизайн. В случае с F# пришлось пойти на некоторые упрощения. Зато доступна Visual Studio с IntelliSense, хотя лично я предпочитаю Aquamacs и runghc / cabal в терминале :)
понедельник, 4 мая 2015 г.
Зарелизил Aivika for .NET
Выпустил движок имитационного моделирования Aivika for .NET по двойной лицензии: GPLv3 и коммерческая. Коммерческая версия имеет дополнительные плюшки в виде модулей для быстрого и удобного возвращения результатов, обработки и анализа. Но сам движок полностью самодостаточен, и он лежит теперь на гитхабе:
https://github.com/dsorokin/aivika-fsharp-ce
https://github.com/dsorokin/aivika-fsharp-ce
пятница, 1 мая 2015 г.
Айвика для .NET Framework и Mono
Айвика для .NET Framework и Mono
Портировал свою библиотеку имитационного моделирования Айвику на .NET Framework и Mono. Если кратко, это такая библиотека, которая поддерживает большинство известных парадигм имитационного моделирования. Звучит очень амбициозно, но это действительно так. Можете проверить, взяв открытую версию для Haskell. Код доступен. Есть примеры. Есть документация. Даже Google очень уважает мою библиотеку по поисковой фразе «simulation library», хотя замечу, что его выдача бывает нестабильной и зависит от многих факторов.
Теперь есть порт для .NET и Mono. Написано на F#. В отличие от открытой версии для Haskell, этот порт закрыт, но доступна документация в формате PDF по ссылке в конце приведенной выше страницы Wiki. Больше 100 страниц с описанием основного API, примерами, графиками и т.п.
Что может дать новая версия?
Как и в случае Haskell, можно составлять имитационные модели практически любой степени сложности и нетривиальности, используя очень простую концепцию, где основные моделируемые активности представлены как вычисления. По сути, это функциональное программирование в чистом виде: монады, потоки, стрелки и т.п., но этим можно особо не заморачиваться, поскольку F# создает иллюзию простоты, насколько возможно.
Все настолько топорно устроено, что не может не работать. Чем больше проверяю на разных примерах, тем больше убеждаюсь, что метод работает. Иногда вношу неточности в примеры моделей, но потом обычно исправляюсь. Получаю такие же результаты, как в других источниках литературы, хотя последние иногда грешат :)
Библиотека охватывает такие вещи, как обыкновенные диффуры, так и вытесняющую многопроцессность для систем массового обслуживания. Например, вытеснение ресурса позволяет с легкостью моделировать поломку станков. А потоки с мультиплексированием позволяют моделировать станки параллельно.
По модели можно запустить вычислительный эксперимент и получить итоговую страницу HTML с графиками, гистограммами, таблицами в формате CSV и прочим, что позволяет проводить быстрый анализ модели, если нужно, экспортируя результаты в R для более детального изучения.
Теперь это все доступно на платформах .NET Framework и Mono. Работает на Windows, OS X и Linux. Можно составлять модели в удобном редакторе Visual Studio или Xamarin Studio с подсветкой типов и автодополнением. Возможно создание интерактивных тренажеров. Можно интегрировать с существующими решениями, использующими .NET.
Подписаться на:
Сообщения (Atom)
