Александр, добрый день!
Очень интересная идея, спасибо!
Мне она не приходила в голову.
Аркадий
чт, 4 февр. 2021 г. в 11:23, Александр Коновалов a.v.konovalov87_AT_mail.ru
<refal@botik.ru>:
> Доброе утро, Аркадий!
>
> *«Есть и другой вариант — использовать модель стека в форме слова
> в некотором алфавите. Мощность алфавита должна быть не меньше наибольшего
> числа „параллельных“ (рекурсивных) вызовов в рамках одной функции.
> Слово-стек легко кодировать целым числом, только длина его в битах будет
> расти линейно с глубиной рекурсии. Как-то так.»*
>
> В прошлом году Станислав Санталов (мой ученик) читал в ИПМ доклад
> о попытке распараллелить вычисления в Рефале. В обсуждаемой реализации
> распараллеливанию подвергались только чистые функции.
>
> Вы тогда заметили, что на практике широко распространены «почти чистые»
> функции — функции, которые могли быть чистыми, но используют единственную
> недетерминированную функцию — генератор «свежих» имён/индексов. Например,
> если программа является компилятором и ей нужно порождать в ассемблерном
> листинге имена для меток.
>
> Такую программу можно сделать чистой следующим образом. Функции, которым
> нужны свежие индексы, должны будут принимать число, номер очередного
> индекса, и возвращать число. Но тогда между по смыслу независимыми вызовами
> возникнет зависимость по данным и эти вызовы перестанут быть
> «параллельными».
>
> Я об этом думал, и тоже пришёл к предложенной Вами схеме: индексом сделать
> строку в некотором алфавите и наращивать её разными символами при передаче
> в разные дочерние вызовы:
>
> F {
> …
> … (e.ID) … = … <G … (e.ID 'A') …> … <H … (e.ID 'B') …> …;
> …
> }
>
> Но, при дополнительном анализе кода и изменении схемы наращения строки
> можно добиться и логарифмической длины во многих практических случаях. Для
> этого нужно один из вызовов функции в правой части назначить «циклическим».
> При передаче строки-идентификатора в циклический вызов, к строке
> приписывается число, либо, если число уже приписано, оно инкрементируется.
> В остальные вызовы к строке будет приписываться символ-нечисло. Очевидно,
> циклическим вызовом должен быть рекурсивный вызов (если таковых в правой
> части несколько — то только один из них):
>
> *F* {
> …
> … (e.ID) … = … <G … (e.ID 'A') …> … *<F* … (<Inc e.ID>) …*>* …;
> …
> }
>
> Inc {
> e.Str '0' = e.Str '1';
> e.Str '1' = <Inc e.Str> '0';
> e.Str = e.Str '0';
> }
>
> Для нескольких рекурсивных вызовов в правой части циклический можно
> назначить либо произвольно, либо с учётом алгоритма — тот, по которому
> рекурсия ожидается глубже. В качестве эвристики можно различать хвостовые
> и нехвостовые вызовы.
>
>
>
> *«…вся память „ассоциативная“, или „content-addressаble“.»*
>
> Вопрос только в производительности этой памяти и скорости обмена с ней.
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
>
>
> *From:* Arkady Klimov arkady.klimov_AT_gmail.com [mailto:refal@botik.ru]
> *Sent:* Tuesday, February 2, 2021 8:32 PM
> *To:* refal@botik.ru
> *Subject:* Re: Конференция МЭС - 2020
>
>
>
> Александр, добрый день!
>
> Тоже извиняюсь за задержку, затерялось Ваше письмо.
>
> Вопрос хороший, я постоянно (время от времени) подумываю насчет реализации
> Рефала в этой модели. Да, видимо тут нельзя предложить какой-то общей
> интерпретации индексов. В обычных задачах у нас индексы имеют
> содержательный прикладной смысл. Здесь же, видимо, это будет, как в обычных
> реализациях рефала и функц. языков, некий "свежий указатель", разница лишь
> в том, что тут не нужна какая-то память, с ним связанная, просто в силу
> того, что вся память "ассоциативная", или "content-addressаble". И если в
> обычных системах для порождения "свежего указателя" мы используем реальный
> пул свободных ячеек с адресами, то здесь нужны только сами "адреса". А для
> их порождения (и освобождения) можно вполне использовать такой же реальный
> пул ячеек (звеньев), размер которых должен быть достаточен лишь для
> размещения ссылок для организации списка свободных ячеек (адресов).
>
> Есть и другой вариант - использовать модель стека в форме слова в
> некотором алфавите. Мощность алфавита должна быть не меньше наибольшего
> числа "параллельных" (рекурсивных) вызовов в рамках одной функции.
> Слово-стек легко кодировать целым числом, только длина его в битах будет
> расти линейно с глубиной рекурсии. Как-то так.
>
> Аркадий
>
>
>
> чт, 21 янв. 2021 г. в 12:25, Александр Коновалов
> a.v.konovalov87_AT_mail.ru <refal@botik.ru>:
>
> Добрый день, Аркадий!
>
> Прошу прощения за поздний ответ, только сейчас я наконец добрался до этого
> письма.
>
> Вы написали в рассылку refal@botik.ru, и поэтому у меня к Вам вопрос:
> а можно ли применить этот подход к распараллеливанию программ на Рефале?
> Или он применим только к массивам однородных вычислений вроде
> рассмотренного перемножения матриц?
>
> Если брать Рефал Плюс, то у конкретизаций есть несколько входных
> и выходных аргументов, которые тоже можно представлять токенами в этой
> модели. Но проблема будет в том, что множество конкретизаций во время
> выполнения не известно заранее и назначить им индекс статически невозможно.
> Или всё-таки можно что-то придумать?
>
>
>
> С уважением,
> Александр Коновалов
>
>
>
> *From:* Arkady Klimov arkady.klimov_AT_gmail.com [mailto:refal@botik.ru]
> *Sent:* Wednesday, September 16, 2020 11:44 PM
> *To:* refal@botik.ru; metacomputation...@googlegroups.com
> *Subject:* Re: Конференция МЭС - 2020
>
>
>
> Сообщаю интересующимся, что наконец залил презентацию своего доклада (в
> формате pptx).
>
> Надеюсь теперь будет понятнее, а то статья получилась сумбурная и потому
> трудно читаемая.
>
> Ее, как и статью, можно найти среди докладов (скажем, по фамилии автора) в
> разделе *Доклады* сайта конференции
>
> http://www.mes-conference.ru/
>
> Туда же можно попасть по прямой ссылке
>
> http://www.mes-conference.ru/index.php?page=reportsV3
>
>
>
> Название моего доклада:
>
> *Средства верификации распределения вычислений в потоковой архитектуре
> ППВС «Буран»*
> <http://www.mes-conference.ru/data/year2020/pdf/D107.pdf?t=1600275592>
>
> Хотя вопрос довольно частный, но кажется получилось интересно. И относится
> он скорее не к конкретной архитектуре, а к ее абстрактной модели вычислений.
>
> Надеюсь скоро озвучку выставить. (В принципе текст озвучки уже введен в
> виде комментариев к слайдам).
>
> С уважением,
>
> Аркадий
>
>
>
> PS. Просматривать вроде можно и без регистрации (кроме обсуждения), а для
> комментирования (обсуждения) надо зарегистрироваться.
>
> Буду рад комментариям.
>
>
>
>
>
> чт, 16 июл. 2020 г. в 10:14, Arkady Klimov <arkady.kli...@gmail.com>:
>
> Отвечая на просьбу организаторов конференции, сообщаю коллегам о том, что
> проводится в режиме заочного интернет-форума
>
>
>
> Всероссийская с международным участием научно-техническая конференция
> *"Проблемы разработки перспективных микро- и наноэлектронных систем"*
>
> *МЭС-2020*
>
>
>
> Зарегистрировавшись на портале
>
> http://www.mes-conference.ru/ ,
>
> можно читать выставленные статьи (в разделе *Доклады*) и участвовать в их
> обсуждении.
>
> Спасибо за участие!
>
> --
>
> _______________
>
>
>
>
>
