Добрый день, Аркадий!
А ведь ключевым новшеством параллельного Рефала-05 является распараллеливание с
сохранением порядка нечистых функций. Решилось практически ТРИЗовское
противоречие: функции должны выполняться параллельно для производительности,
функции должны выполняться последовательно из-за побочного эффекта.
Причём распараллеливание сугубо динамическое — до вызова функции неизвестно,
чистая она или нет.
PutLog {
NoLog e.Message = /* ничего не делаем */;
s.Log e.Message = <Putout s.Log <Time> ': ' e.Message>;
}
F {
… s.Log … = … <PutLog s.Log 'Starting…'> …
}
В зависимости от значения s.Log, которое может передаваться откуда-то извне,
функция PutLog является либо чистой, либо нечистой. И, если программа работает
с отключённым логом (в функции передаётся NoLog) вычисления распараллеливаться
будут. Если лог включить (будет передаваться номер открытого файла), то
параллелизм сразу же просядет, т.к. в лог будет писаться последовательно.
ИЛИ-параллелизм ставит новое противоречие (тоже в духе ТРИЗ): отменённые
вычисления не должны выполняться ради производительности, отменённые вычисления
должны выполняться ради побочного эффекта. Как разрешить противоречие — пока не
понятно. ТРИЗ учит нас, что если задачу решить не получается, можно попробовать
подняться на ступеньку выше. Действительно, «отменённая» задача — это деталь
реализации.
Попробую сформулировать постановку задачи для Рефала-05. Формулировка Аркадия
не очень хорошо подходит, т.к. в Рефале-05 нет неуспехов (и не планируется).
Можно описать такой примитив:
<OR (s.Func1 e.Arg1) (s.Func2 e.Arg2)
== /* пусто */
== t.Res
<s.Func1 e.Arg1>
== /* пусто */
== t.Res
<s.Func2 e.Arg2>
== /* пусто */
== t.Res
Функция OR принимает два указателя на функции с их аргументами. Каждая из этих
функций может или вернуть пустоту, или терм. Если обе функции вернули пустоту,
то OR возвращает пустоту. Если хотя бы одна из функций вернула терм, то
возвращается терм. Если обе функции вернули по терму, то возвращается какой-то
из двух. Псевдокод:
OR {
(s.Func1 e.Arg1) (s.Func2 e.Arg2)
= <OR-Select <Mu s.Func1 e.Arg1> <Mu s.Func2 e.Arg2>>;
}
OR-Select {
/* пусто */ = /* пусто */;
t.OneTerm = t.OneTerm;
t.Term1 t.Term2 = <RandomOf t.Term1 t.Term2>;
}
В параллельной реализации обе функции, разумеется, должны вычисляться
параллельно. Можно вызывать OR не с двумя функциями с аргументами, а с
произвольным количеством, это не принципиально.
Иногда различают параллельное и конкурентное программирование. Параллельность —
задачи выполняются одновременно, независимо и не взаимодействуют между собой.
Пример: вычисление на GPU, векторные машинные инструкции. Конкурентность —
имеем несколько потоков управления, которые могут выполняться
поочерёдно/одновременно, побочные эффекты их перемежаются. Чуть подробнее
почитать можно, например, здесь <https://eax.me/haskell-parallel/> .
То, что реализовано в Рефале-05, это параллельное программирование. Если
добавить в язык примитив для запуска нового потока, примитивы синхронизации
вроде мьютексов, каналов, мониторов и т.д., то это уже средства конкурентного
программирования.
В рамках конкурентного программирования ИЛИ-параллелизм вполне осуществим. Для
этого нужен канал, глобальный флаг и вспомогательный поток. Вспомогательный
поток сидит на канале и ждёт, когда в нём что-то появится. Как только
появилось, он устанавливает глобальный флаг. Рабочие потоки периодически
проверяют глобальный флаг, если он выставлен, то себя завершают, если нет,
продолжают работать. Когда рабочий поток вычислил значение, он его кладёт в
канал. Таким образом, из канала будет прочитано значение, положенное в него тем
потоком, который завершился раньше. Глобальный флаг нужен для оптимизации,
чтобы досрочно завершить другие рабочие потоки. Но это слишком низкоуровнево.
Хотелось бы иметь высокоуровневый примитив вроде OR, записанного выше.
Противоречие на ступеньку выше — при вызове OR должна вычисляться только одна
из двух функций (т.к. требуется только один результат), и должны вычисляться
обе функции, т.к. у них обоих могут быть побочные эффекты. Не знаю, разрешима
ли эта задача.
С уважением,
Александр Коновалов
From: Arkady Klimov arkady.klimov_AT_gmail.com [mailto:refal@botik.ru]
Sent: Tuesday, May 26, 2020 6:59 PM
To: refal@botik.ru
Subject: Об ИЛИ-параллелизме (Re: Re[2]: Семинар по метавычислениям ...)
Да, конечно, это непросто. Я обычно предполагал, что при порождении ИЛИ-группы
будет создаваться некий общий объект типа Bool, который сбрасывается, когда
кто-то закончит, и он всем по ссылке передается, чтобы поглядывали, и если он
сброшен, то пора отменяться. Насчет вложенности особо не думал пока.
Аркадий
вт, 26 мая 2020 г. в 00:07, Александр Коновалов a.v.konovalov87_AT_mail.ru
<http://a.v.konovalov87_AT_mail.ru> <refal@botik.ru <mailto:refal@botik.ru> >:
Доброй ночи, Аркадий!
В архитектуру Рефала-05, который мы тогда обсуждали на семинаре, добавить
ИЛИ-параллелизм просто не получится. Т.к. в случае ИЛИ-параллелизма нужно будет
информацию распространять обратно — от отложенной конкретизации, которая была
отменена, к вызовам функций, от которых она зависела, чтобы их тоже отменить. А
как делать это эффективно, я не представляю. Можно, конечно, при каждой отмене
задачи уведомлять все активные задачи, для каждой из них прослеживать цепочку
предков — если среди них есть отменённая задача, то отмениться и самому. Так
себе решение, но других очевидных сравнительно эффективных подходов я не вижу.
Плюс ещё нужна эффективная реализация барьера для параллельных задач — финишную
ленточку порвать может только один, а остальные должны отмениться.
С уважением,
Александр Коновалов
From: Arkady Klimov arkady.klimov_AT_gmail.com
<http://arkady.klimov_AT_gmail.com> [mailto:refal@botik.ru
<mailto:refal@botik.ru> ]
Sent: Monday, March 23, 2020 5:38 PM
To: Александр Гусев <gusev_aleksa...@mail.ru <mailto:gusev_aleksa...@mail.ru>
>; refal@botik.ru <mailto:refal@botik.ru>
Subject: Re: Re[2]: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ
Я бы упомянул еще один вид параллелизма - ИЛИ-параллелизм. В строгом смысле в
рефале места для него сейчас нет.
Было бы, если бы кроме отождествления "слева" и "справа" добавить "любое" -
подходит любой вариант
длины открытой е-переменной. Или если ввести "машинную операцию" типа
<Map-Select tF eX> =
применять tF к термам eX в любом порядке или параллельно, и если есть хотя бы
один,
где результат не неуспех, то его и выбрать (любой), иначе неуспех.
Этот вид встречается в задачах типа поиска доказательств. Также в
суперкомпиляции.
Он не сводится к обычному И-параллелизму, поскольку в нем нужно убивать
запущенные подпроцессы,
чего в И-параллелизме не бывает.
Аркадий
