Параллельный Рефал

Подход первый. Явный параллелизм.

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

Функция порождения нити - аналогична Apply, только ничего не возвращает.
$func ParApply s.func e.args = ;

Send-Receive

И нужны явные конструкции для синхронизации/передачи сообщений. Можно сделать как в MPI или как в Erlang'е - идентификация номерами, но мне видится, что для Рефала+ более подходящим будет специальный почтовый ящик MsgBox.Чем-то похож на Рефал+'овский ящик, в которой одни кладут, другие - достают. (Об этом тоже можно порассуждать в отчете ;))

В итоге нужны функции заведения ящика, посылки и приема:
$func MsgBox = s.mbox;
$func Send s.mbox e.letter = ; // Посылка сообщения
$func Recv s.mbox = e.letter; // Блокирующий прием сообщения
$func? IRecv s.mbox = e.letter; // Неблокирующий прием сообщения
Функций приема две - блокирующая и неблокирующая. Если сообщений в ящике нет, то первая засыпает и ждет, вторая - возвращает $fail.
Семантика Send/Recv - ровно как в MPI: каждой посылке, вызову Send'а, соответствует ровно один успешный прием.

Отмечу, что с ящиком могут работать сразу много нитей: все дружно могут писать и читать. Например, чтобы реализовать парадигму Мастер/Раб, когда куча процессов-рабов что-то делают, а один мастер раздает им работу и собирает результаты достаточно двух ящиков:
  1. В один мастер кладет невыполненные задания, а все рабы из этого ящика берут невыполненные задания, когда освободятся.
  2. В другой рабы кладут результаты, которые мастер собирает.Замечу, что это получается библиотека! В самом Рефале+ поверх Явы ничего менять не нужно. Было бы время, то можно было б посадить студента - и разберется, и сделает.
Ну или сделать самим на полдня (или даже быстрее ;)). Почтовый ящик можно реализовать через Рефал+'овский ящик, только нужно, чтобы функции Send/Receive с одним ящиком не работали одновременно:
MsgBox = <Box.Box>;
Send s.mbox e.letter = <Box.Put s.mbox (e.letter)>;
IRecv s.mbox = <Box.Get s.mbox> : (e.letter) e.other, <Box.Store s.mbox e.other>, e.letter;
Receive - как IReceive, только умеет спать, если в ящике ничего нет.

Монотонные объекты

Идеология Send-Receive не слишком вписывается в функциональную парадигму:
  1. Вызов функции Receive с одинаковыми аргументами приводит к разным ответам.
  2. В зависимости от порядка параллельных вычислений может получаться разный ответ.
В качестве решения указанных проблем для синхронизации нитей можно использовать монотонные объекты, точнее store-once ящики (SOBox):
  1. При создании SOBox'а он не инициализирован;
  2. Есть читать неинициализированный ящик, то нить засыпает до записи.
  3. В неинициализированный ящик можно записать что угодно.
  4. В инициализированный ящик можно записать только то, что там уже лежит.
$func SOBox = s.sobox;
$func Get s.sobox = e.expr;
$func Store s.sobox e.expr = ;

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

Одним из наиболее часто используемый способ использоваться SOBox - передача через них результата функции. Для этого определим функцию
$func FutureApply s.func e.arg = s.sobox;
которая
  1. Создает SOBox.
  2. Запускает вычисление <s.func e.arg> в отдельной нити, результат вычисления будет записан в созданный SOBox (в вызываемой нити).
  3. Возвращает созданный SOBox в качестве результата (в вызывающей нити).

Подход второй. Неявный параллелизм.

Этот подход навеян Т-системой и прочими неявными параллелизмами в функциональных языках. А так же явной схемой с монотонными объектами

Идея 1 - любой вызов функции можно запустить в параллель (или не считать в ленивых языках), пока результаты функции реально не потребовались.
Идея 2 - сделать монотонные объекты неявнями (по сравнению со схемой с монотонными объектами).

Над общей памятью этот поход реализуется гораздо проще, чем в OpenTS, поскольку не нужно думать о распределении данных. И, для начала, использовать Явовские нити (примерно как в TSim использует системные, а OpenTS наоборот - свои). Возможно, что Явовских нитей окажется достаточно. Есть мечта поставить куда-нибудь Solaris для экспериментов - в нем есть несколько интересных вещей, которых нет в мире Linux. Одна из них - легкие нити.

Чтобы такой подход реализовать нужно в представление данный добавить понятие неготового выражения. Как и в версии над OpenTS, пусть оно будет неготово в глубину. Конечно, можно помечтать о том, чтобы выражение могло быть некоторым в ширину: например, самый левый (и, может одновременно и самый правый) терм известен, а остальные - нет. Но это сложнее и требует существенно менять текущую реализацию выражение - это можно в планах/мечтах писать, но не обещать ;).

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

Далее потребуется добавить в язык понятие параллельного вызова. При параллельном вызове заводится новая нить, в которой производятся вычисления вызываемой функции. А в вызываемой нити управление возвращается сразу и в качестве результатов возвращаются неготовые выражения. При обращении к некоторым выражениям нить засыпает. Есть два способа добавить параллельный вызов в язык:
  1. Декларация параллельной функции: $parfunc или $par $func, как $public $func - для функций, все вызовы которой запускаются в новой нити.
  2. Конструкция параллельного вызова функции: например <| Func e.agrs |> . Только такие вызовы запускаются в новой нити.
Как лучше - не ясно. Надо посмотреть и сначала сделать, что проще.

Независимо от выбранного подхода придется менять компилятор. Это уже студенту тяжело поручить - долго разбираться будет, но нам с Антоном это сделать несложно (пара дней?).

Атомарные операции

Кроме порождения нитей и передачи данных, часто в программирование нужны атомарные операции - функции, вычисление которых в разных нитях не может перекрываться во времени. Классические атомарные операции: CompareAndStore, CompareAndSwap и т.п.

В Рефале+ атомарные операции нужны над изменяемыми ячейками - ящиками, векторами, таблицами и пр.

Для выполнения атомарной операции над ящиками заведена функция
$func? AtomicApply s.func s.box e.arg = e.res;

Она выполняет <s.func s.box e.arg> над ящиком s.box, т.е. при ее выполнени другие вызовы AtomicApply с тем же s.box не начинают работу до заверщения первого вызова. В каждый момент времени только один вызов AtomicApply для данного s.box
работает и он не может прерываться другими вызовами AtomicApply для этого же s.box.

Например, если нужно выполнить атомарно Put - добавления выражения в ящик (например, для реализации Send в схеме Send-Receive), то для этого нужно заменить вызов <Put ...> на <AtomicApply &Put ...> :
<Put s.box e.data>    ->    <AtomicApply &Put s.box e.data>

Примеры

Comments