Привет. Кто-нибудь занимался моделированием дискретных динамических систем на Haskell, OCaml и/или Erlang? Ну, типа, когда у вас разные элементы связаны связями, и обмениваются по этим связям информацией, с дискретным временем (по шагам). Например, это может быть высокоуровневая модель микропроцессора, как у нас .
Интересно обсудиь общий подход к построению системы, может мы что-то пропустили. Может, мысли у кого какие будут — велкам. Критерий успеха — чем короче и проще код, тем лучше.
ЗЫ: Интерес не праздный, связан с нашими проектами. У нас парни уже почти написали модель процессора MIPS на Хаскеле (элементы замкнуты через ленивые списки, ленивость в этой задаче рулит со страшной силой). Для Эрланга я сейчас в фоновом режиме пробую написать тест — по одному процессу на элемент, с полностью асинхронным взаимодействием. Такая схема должна хорошо параллелиться, и замечательно работать на SMP машинах, возможно, будет хорошо и на кластерах, надо проверить. Посмотрим, что получится.
Здравствуйте, Gaperton, Вы писали:
G>Привет. Кто-нибудь занимался моделированием дискретных динамических систем на Haskell, OCaml и/или Erlang? Ну, типа, когда у вас разные элементы связаны связями, и обмениваются по этим связям информацией, с дискретным временем (по шагам). Например, это может быть высокоуровневая модель микропроцессора, как у нас .
G>Интересно обсудиь общий подход к построению системы, может мы что-то пропустили. Может, мысли у кого какие будут — велкам. Критерий успеха — чем короче и проще код, тем лучше.
Здравствуйте, Изя Рнет, Вы писали:
G>>Интересно обсудиь общий подход к построению системы, может мы что-то пропустили. Может, мысли у кого какие будут — велкам. Критерий успеха — чем короче и проще код, тем лучше.
ИР>Я так понимаю, что http://citeseer.ist.psu.edu/ermedahl95discrete.html ты уже прочитал.
Здравствуйте, Изя Рнет, Вы писали:
G>>Интересно обсудиь общий подход к построению системы, может мы что-то пропустили. Может, мысли у кого какие будут — велкам. Критерий успеха — чем короче и проще код, тем лучше.
ИР>Я так понимаю, что http://citeseer.ist.psu.edu/ermedahl95discrete.html ты уже прочитал.
Погодь. Или я чего-то не понимаю, или там сделано через страшенную задницу.
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Изя Рнет, Вы писали:
G>>>Интересно обсудиь общий подход к построению системы, может мы что-то пропустили. Может, мысли у кого какие будут — велкам. Критерий успеха — чем короче и проще код, тем лучше.
ИР>>Я так понимаю, что http://citeseer.ist.psu.edu/ermedahl95discrete.html ты уже прочитал.
G>Погодь. Или я чего-то не понимаю, или там сделано через страшенную задницу.
Есть немного
Но ты же просил подходы. Вот тебе и такой подход.
Здравствуйте, Изя Рнет, Вы писали:
ИР>>>Я так понимаю, что http://citeseer.ist.psu.edu/ermedahl95discrete.html ты уже прочитал.
G>>Погодь. Или я чего-то не понимаю, или там сделано через страшенную задницу.
ИР>Есть немного ИР>Но ты же просил подходы. Вот тебе и такой подход.
Вот это — двухвходовой сумматор. Модель событий с именоваными входами и выходами, с асинхронной посылкой и блокирующим получением, с множественной подпиской. Подписка на входы делается так
connect( Source, Out, Destination, In )
где имена входов и выходов — атомы. Что, впрочем, не обязательно .
кусочек фреймворка для in/out выглядит примерно так:
%% receive message on specified input
in( Name ) ->
put( [ Name | get( inputs ) ] ),
receive { Name, Msg } -> Msg end.
%%
out( Name, Msg ) ->
case get( Name ) of
undefined -> not_connected;
[ touched | Subscribers ] -> bcast( Msg, Subscribers );
Subscribers -> bcast( Msg, Subscribers ),
put( Name, [ touched |Subscribers ] )
end.
%% broadcast message to the list of subscribers
%%% send message w/o translation
bcast( Msg, [ { Proc, In } | T ] ) ->
Proc ! { In, Msg },
bcast( Msg, T );
%%% send message with translation
bcast( Msg, [ { Proc, In, F } | T ] ) ->
Proc ! { In, F( Msg ) },
bcast( Msg, T );
%%% send empty message (bubble) and ignore translation
bcast( nil, [ { Proc, In, _ } | T ] ) ->
Proc ! { In, nil },
bcast( Msg, T );
%%% exit
bcast( _, [ undefined ] ) -> ok.
G>Вот это — двухвходовой сумматор. Модель событий с именоваными входами и выходами, с асинхронной посылкой и блокирующим получением, с множественной подпиской. Подписка на входы делается так
G>
G>connect( Source, Out, Destination, In )
G>
G>где имена входов и выходов — атомы. Что, впрочем, не обязательно . G>...
Интересный подход. Что-то наподобие dataflow переменных получается. Так может имеет смысл взглянуть на язык где эти перемнные уже реализованы. Например Mozart\Oz. В CTM кстати есть пример подобного симулятора цифровых цепей. Собственно вот код оттуда:
fun {GateMaker F}
fun {$ Xs Ys}
fun {GateLoop Xs Ys}
case Xs#Ys of {X|Xr}#{Y|Yr} then {F X Y}|{GateLoop Xr Yr} end
end
in
thread {GateLoop Xs Ys} end
end
end
AndG = {GateMaker fun {$ X Y} X*Y end}
OrG = {GateMaker fun {$ X Y} X+Y-X*Y end}
XorG = {GateMaker fun {$ X Y} X+Y-2*X*Y end}
% Теперь можно описать схему состоящую из нескольких элементов. Например сумматор. Он имеет три входа и два выхода.
proc {FullAdder X Y Z ?C ?S}
K L M
in
K = {AndG X Y}
L = {AndG Y Z}
M = {AndG X Z}
C = {OrG K {OrG L M}
S = {XorG Z {XorG X Y}}
end
% Использование
declare
X=1|1|0|_
Y=0|1|0|_
Z=1|1|1|_
{FullAdder X Y Z C S}
{Browse inp(X Y Z)#sum(C S)}
Тут каждый элемент работает в своем изолированном потоке (логическом — аналог процессов в Erlang), а для обмена данными используются dataflow переменные. Т.е. когда вычисление натыкается на переменную которой еще не присвоено значение, поток временно приостанавливается, а когда переменная получает значение (в другом потоке, конечно) то вычисление автоматически возобновляется. Связи между элементами описываются вполне наглядно — просто одна и таже переменная в одном случае служит выходом, а в другом входом.
MK>Тут каждый элемент работает в своем изолированном потоке (логическом — аналог процессов в Erlang), а для обмена данными используются dataflow переменные. Т.е. когда вычисление натыкается на переменную которой еще не присвоено значение, поток временно приостанавливается, а когда переменная получает значение (в другом потоке, конечно) то вычисление автоматически возобновляется. Связи между элементами описываются вполне наглядно — просто одна и таже переменная в одном случае служит выходом, а в другом входом.
Это со-процедуры по-другому называется, или есть отличия?
Здравствуйте, DenisY, Вы писали:
MK>>Тут каждый элемент работает в своем изолированном потоке (логическом — аналог процессов в Erlang), а для обмена данными используются dataflow переменные. Т.е. когда вычисление натыкается на переменную которой еще не присвоено значение, поток временно приостанавливается, а когда переменная получает значение (в другом потоке, конечно) то вычисление автоматически возобновляется. Связи между элементами описываются вполне наглядно — просто одна и таже переменная в одном случае служит выходом, а в другом входом.
DY>Это со-процедуры по-другому называется, или есть отличия?
Как я понимаю, со-программы соответствуют невытесняющей многозадачности. Т.е. планирование происходит на уровне приложения и каждая со-программа должна явно возвращать управление. В Mozart\Oz потоки переключаются полностью автоматически. Кстати в первых версиях Oz потоки были неявными, т.е. любое выражение исполнялось в отдельном потоке. Но в последствии они от такой схемы отказались. Так как сильно усложнился анализ и отладка программ. Сейчас чтобы выражение выполнилось в отдельном потоке его нужно явно обернуть в thread...end .
Интересный эффект такого подхода — результат работы программы не зависит от порядка выражений. Например код:
A = 10
B = 20
C = B + A
D = C + A
{Browse D}
выдаст точно такой же результат, что и
B = 20
thread D = C + A end
thread C = B + A end
A = 10
{Browse D}
Данная модель полностью декларативна и детерминирована. Т.е. результат вычисления зависит только от значений которые в конце-концов принимают переменные. Повторное присваивание невозможно. И нет никакой возможности определить, присвоено ли значение данной переменной или нет.
В библиотеке Mozart\Oz есть модуль Thread, который позволяет реализовать сопрограммы. Там имеются функции, которые явно останавливают поток, передают управление другому потоку и т.п. Вот реализация примитивов для сопрограмм из все той же CTM:
fun {Spawn P}
PId in
thread
PId={Thread.this}
{Thread.suspend PId}
{P}
end
PId
end
proc {Resume Id}
{Thread.resume Id}
{Thread.suspend {Thread.This}}
end
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Mikl Kurkov, Вы писали:
G>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Gaperton, Вы писали:
G>>Здравствуйте, Mikl Kurkov, Вы писали:
G>>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
G>Понятно — похоже, что никто .
Боюсь, что так оно и есть. По качеству компилятора, думаю что у той небольшой команды, которая занимается этим проектом на какую-то мощную оптимизацию ресурсов не хватит. Но кстати совсем недавно вышла новая версия 1.3.2 В основном исправлены баги правда.
Еще обновились недавно программы на http://shootout.alioth.debian.org для Mozart\Oz. В тесте с 500 процессами в кольце, он даже вышел на первое место, обогнав Erlang c GHC.
Здравствуйте, Mikl Kurkov, Вы писали:
MK>Здравствуйте, Gaperton, Вы писали:
G>>Здравствуйте, Gaperton, Вы писали:
G>>>Здравствуйте, Mikl Kurkov, Вы писали:
G>>>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
G>>Понятно — похоже, что никто .
MK>Боюсь, что так оно и есть. По качеству компилятора, думаю что у той небольшой команды, которая занимается этим проектом на какую-то мощную оптимизацию ресурсов не хватит. Но кстати совсем недавно вышла новая версия 1.3.2 В основном исправлены баги правда.
А насколько часто maintenance релизы выходят? Плюс, есть ли поддержка SMP и распределенной работы на сетке (кластере)?
На самом деле, у Elrang для этой задачи есть пара плюсов:
1) Так как фреймворк OTP и компилятор работает в составе промышленных систем высокой надежности (пять девяток и выше), это дает близкую к 100%-ю гарантию отсутствия багов-showstoppers.
2) Тут есть нюансы. У меня подписка не совсем простая — например, я засылаю "пузыри" на те выходы, которые не были затронуты в процессе обработки цикла. И забираю данные со входов, к которым не обращались в течении цикла. Это позволяет мне писать относительно безопасно, не налетев на ошибку синхронизации. И думается мне, для этого придется так или иначе писать свой фреймворк, даже для Моцарта.
Плюс, — сейчас у меня в модели нет тактовой частоты, она асинхронна. А что, если я захочу сделать схему тактированной (вполне вероятно, кстати)? В Эрланге это — без проблем, я спущу тактовую частоту вниз по иерархии процессов-функциональных блоков, спрятав всю обработку (или ее часть) во фреймворк. Что будет с Моцартом? Я имею в виду — не придется ли там докручивать сопоставимого размера (гхм — ну строк 100-150 ) фреймворк? И где тогда бенефит?
MK>Еще обновились недавно программы на http://shootout.alioth.debian.org для Mozart\Oz. В тесте с 500 процессами в кольце, он даже вышел на первое место, обогнав Erlang c GHC.
500 — мало, столько тредов оперсистема держит без проблем. Я бы проверил на чем-нибудь реальном — например, тысяч эдак 10000. Правда, тогда список был бы практически пуст , у большинства было бы error или timeout.
Здравствуйте, Gaperton, Вы писали:
G>>>>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
G>>>Понятно — похоже, что никто .
MK>>Боюсь, что так оно и есть. По качеству компилятора, думаю что у той небольшой команды, которая занимается этим проектом на какую-то мощную оптимизацию ресурсов не хватит. Но кстати совсем недавно вышла новая версия 1.3.2 В основном исправлены баги правда.
G>А насколько часто maintenance релизы выходят? Плюс, есть ли поддержка SMP и распределенной работы на сетке (кластере)?
Ну я не особенно слежу за происходящим там. Похоже это и есть maintenance. Судя по CVS предыдущая версия 1.3.1 была выпущена 2 года назад. Т.е. процесс не очень-то быстрый. Или так все было хорошо написано, что обновления не понадобились. .
G>На самом деле, у Elrang для этой задачи есть пара плюсов: G>1) Так как фреймворк OTP и компилятор работает в составе промышленных систем высокой надежности (пять девяток и выше), это дает близкую к 100%-ю гарантию отсутствия багов-showstoppers.
Тут я думаю Erlang вне конкуренции. Хотя и проскакивают сообщения об использовании Mozart\Oz, но сравнивать тут нечего даже.
G>2) Тут есть нюансы. У меня подписка не совсем простая — например, я засылаю "пузыри" на те выходы, которые не были затронуты в процессе обработки цикла. И забираю данные со входов, к которым не обращались в течении цикла. Это позволяет мне писать относительно безопасно, не налетев на ошибку синхронизации. И думается мне, для этого придется так или иначе писать свой фреймворк, даже для Моцарта.
Не вполне понял идею. Возможно ты тут как раз с асинхронностью борешься. Или что какой-то элемент получит дважды один и тот же сигнал? В Mozart такой проблемы нет. По крайней мере в тех примерах что я приводил. Там все полностью сихронизировано. Управление потоками, слежение за состоянием переменных обеспечивает сама среда.
G>Плюс, — сейчас у меня в модели нет тактовой частоты, она асинхронна. А что, если я захочу сделать схему тактированной (вполне вероятно, кстати)? В Эрланге это — без проблем, я спущу тактовую частоту вниз по иерархии процессов-функциональных блоков, спрятав всю обработку (или ее часть) во фреймворк. Что будет с Моцартом? Я имею в виду — не придется ли там докручивать сопоставимого размера (гхм — ну строк 100-150 ) фреймворк? И где тогда бенефит?
Та модель которая использовалась в примерах полностью синхронизирована. Т.е. усилия придется приложить чтобы сделать ее асинхронной. Хотя может я не до конца представляю что такое асинхронная логическая цепь. Или асинхронность есть только на уровне модели? А тактирование можно сэмулировать постпенно добавляя элементы к входным спискам (X Y Z в том примере) по мере увеличения входных списков будут увеличиваться и выходные. Обратимся снова в CTM:
fun {Clock}
fun {Loop B}
{Delay 1000} B | {Loop B}
end
in
thread {Loop 1} end
end
Эта функция генерирует входной поток с определенным временным интервалом.
Кстати там же есть еще один интересный пример — защелка (latch) триггер с двумя состояниями и возможностью запоминания последнего значения. Для его реализации нужно завести выход всей схемы на вход одного из элементов, т.е. что-то типа обратной связи. Понятно что напрямую это сделать нельзя так как возникнет дедлок. Так вот понадобилась всего лишь одна простейшая функция — задержка.
%собствеено элемент - задержка
fun {DelayG Xs}
0|Xs
end
%а это модель двухстабильного триггера
fun {Latch C DI}
DO X Y Z F
in
F={DelayG DO}
X={AndG F C}
Z={NotG C}
Y={AndG Z DI}
DO={OrG X Y}
DO
end
Защелка имеет два входа и пока на входе С — 0, то выход DO просто копирует выход DI. А когда С становится 1, то на выходе фиксируется последнее значение DI. А задержка просто сдвигает входной поток на один элемент и вместо первого (которого у нас еще нет) вставляет 0.
MK>>Еще обновились недавно программы на http://shootout.alioth.debian.org для Mozart\Oz. В тесте с 500 процессами в кольце, он даже вышел на первое место, обогнав Erlang c GHC.
G>500 — мало, столько тредов оперсистема держит без проблем. Я бы проверил на чем-нибудь реальном — например, тысяч эдак 10000. Правда, тогда список был бы практически пуст , у большинства было бы error или timeout.
Думаю что Моцарт тоже справится. Кстати разработчики Erlang и Mozart как я понял сотрудничают и относятся друг к другу с большим уважением. В Эрланговской рассылке как-то даже проскочила мысль о "шведской школе" параллельного программирования. А в CTM большая глава посвящена Erlang и его подходу.
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Mikl Kurkov, Вы писали:
G>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
Здравствуйте, Mikl Kurkov, Вы писали:
G>>2) Тут есть нюансы. У меня подписка не совсем простая — например, я засылаю "пузыри" на те выходы, которые не были затронуты в процессе обработки цикла. И забираю данные со входов, к которым не обращались в течении цикла. Это позволяет мне писать относительно безопасно, не налетев на ошибку синхронизации. И думается мне, для этого придется так или иначе писать свой фреймворк, даже для Моцарта. MK>Не вполне понял идею. Возможно ты тут как раз с асинхронностью борешься. MK> Или что какой-то элемент получит дважды один и тот же сигнал?
Эта ситуация невозможна в рамках моей модели. Опасна другая ситуация — когда в одной из веток функции цикла ты "забываешь" отправить сообщение по одному из выходов. Это может привести к блокировке модели, поэтому у меня на такие выходы отправляется nil.
Другими словами, у меня не тактовой частоты, а сигналом к началу такта является наличие данных по всем входам компонента. При этом, если в одной из веток функции цикла ты пропустил какой-то вход, система должна "дождаться" его, и проигнорировать.
MK> В Mozart такой проблемы нет. По крайней мере в тех примерах что я приводил. Там все полностью сихронизировано. Управление потоками, слежение за состоянием переменных обеспечивает сама среда.
G>>Плюс, — сейчас у меня в модели нет тактовой частоты, она асинхронна. А что, если я захочу сделать схему тактированной (вполне вероятно, кстати)? В Эрланге это — без проблем, я спущу тактовую частоту вниз по иерархии процессов-функциональных блоков, спрятав всю обработку (или ее часть) во фреймворк. Что будет с Моцартом? Я имею в виду — не придется ли там докручивать сопоставимого размера (гхм — ну строк 100-150 ) фреймворк? И где тогда бенефит?
MK>Та модель которая использовалась в примерах полностью синхронизирована. Т.е. усилия придется приложить чтобы сделать ее асинхронной. Хотя может я не до конца представляю что такое асинхронная логическая цепь. Или асинхронность есть только на уровне модели? А тактирование можно сэмулировать постпенно добавляя элементы к входным спискам (X Y Z в том примере) по мере увеличения входных списков будут увеличиваться и выходные. Обратимся снова в CTM:
Синхронная — когда все узлы дружно обмениваются информацией по сингалам единого источника тактовой частоты. Триггер — слишком мелкий узел, чтобы на его примере это прочувствовать.
Пример — конвейр рабора команд микропроцессора. Выборка кодманды — Декодирование — Выборка операндов — выполнение — сохранение операндов.
У тебя на выборке читаются данные из регистров, а на сохранении — пишутся. Вся эта цепочка срабатывает одновременно, при получении синхроимпульсов от единого генератора тактовой частоты.
У меня в схеме нет генераторов тактовой частоты, узлы срабатывают по готовности данных на входах. Так как блоки работают асинхронно — мне осталось доказать, что модель сохранит корректность при отсутствии тактовой частоты — например, записи в регистровый файл не запоздают, и подоспеют с положенной задержкой ровно в два такта. Собственно, для этого я и ввожу "пустые" сообщения nil, которые выполняют роль синхроимпульсов. Короче, тут такая фигня — объяснить тяжело, где грабли, но они повсюду.
На Моцарте это будет прикольно выглядеть, наверно, и не так опасно. Жаль у меня времени нет.
MK>Кстати там же есть еще один интересный пример — защелка (latch) триггер с двумя состояниями и возможностью запоминания последнего значения. Для его реализации нужно завести выход всей схемы на вход одного из элементов, т.е. что-то типа обратной связи. Понятно что напрямую это сделать нельзя так как возникнет дедлок. Так вот понадобилась всего лишь одна простейшая функция — задержка.
Да, известный пример. Я с этим намереваюсь бороться по-другому — при добавлении связи (connect) засылать в "провод" сигнал nil (это вообще всегда надо делать в моей модели, иначе ни одна схема с обратной связью просто не заработает). А потом нужно "научить" элементы два-и-не на него адекватно реагировать — вот и будет триггер.
MK>Думаю что Моцарт тоже справится. Кстати разработчики Erlang и Mozart как я понял сотрудничают и относятся друг к другу с большим уважением. В Эрланговской рассылке как-то даже проскочила мысль о "шведской школе" параллельного программирования. А в CTM большая глава посвящена Erlang и его подходу.
Здравствуйте, z00n, Вы писали:
G>>Очень просто и симпатично. И очень интересно. Кто-нибудь на Mozart/Oz пишет? Какого качества компилятор?
Z>Современный вариант Mozart/Oz называется Alice, реализован как ML с расширениями: Z>http://www.ps.uni-sb.de/alice/
Фьючерсы — это круто . Унификация ленивости и параллелизма. Вот оно, щастье.
Здравствуйте, Gaperton, Вы писали:
G>Привет. Кто-нибудь занимался моделированием дискретных динамических систем на Haskell, OCaml и/или Erlang? Ну, типа, когда у вас разные элементы связаны связями, и обмениваются по этим связям информацией, с дискретным временем (по шагам). Например, это может быть высокоуровневая модель микропроцессора, как у нас .
Я случайно наткнулся на ссылку, которая на вид весьма релевантна (Haskell):
Здравствуйте, z00n, Вы писали:
Z>Здравствуйте, Gaperton, Вы писали:
G>>Привет. Кто-нибудь занимался моделированием дискретных динамических систем на Haskell, OCaml и/или Erlang? Ну, типа, когда у вас разные элементы связаны связями, и обмениваются по этим связям информацией, с дискретным временем (по шагам). Например, это может быть высокоуровневая модель микропроцессора, как у нас .
Z>Я случайно наткнулся на ссылку, которая на вид весьма релевантна (Haskell):
Z>The Lava Hardware Description Language Z>Lava-related papers
Смотрели уже, спасибо. Это чуточку другая штука — т.н. синтезируемое описание, оно более подробно, и может быть отсинтезировано в ПЛИС или ASIC. Оно более подробно, но принцип
Мы сейчас другим озабочены. Как сделать описания на базе Haskell читаемыми для неспециалистов. Думаю, конкурс чтоли объявить на RSDN, с призом баксов в 500 . Как считаете?