Re: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

[Eisymont Leonid verger-lk_AT_yandex . ru]

Автоматическое распараллеливание с учетом побочного эффекта можно и оставить, но это не должно повредить основному, о чем я говорил для чистого рефала без побочного эффекта. Абзац в ответе по поводу автоматического распараллеливания в Вашем письме я не понял. Мы параллелили компиляцию (выполняемую компилятором на Рефале) на уровне операторов исходной программы, а исходная программа  на фортрано-подобном языке.

Статистику по основным затратам при выполнении разных рефал-программ делали. Затраты на открытые переменные - это миф. Я же пересылал Вам материалы, там есть расклад. Измерения были достаточно точные, поскольку выполнялись на микропрограммной реализации Рефала. Это была разработка ИПМ тех лет.

Диссертации моей в электронном виде у меня нет, тогда еще этого не было. У меня только в оригинале. М.б. есть в сети, кто-то отсканировал.

Дипломная работа Александра Фролова и статьи уже 2000-х годов у меня есть, но я ведь статьи и презентации пересылал. Надо повторить?

Л.Эйсымонт

 

 

21.03.2020, 18:03, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Добрый вечер, Леонид!

Текст диссертации, препринт и дипломная работа доступны в электронном виде? Я бы почитал.

 

«Оставьте затею с решением побочного эффекта на автомате.»

Имеем программу для обычного последовательного Рефала.

Если компилятор поддерживает распараллеливание на автомате, то для параллельного выполнения в идеале ничего делать не надо: оно само распараллелится. Чтобы обеспечить бо́льшую степень параллелизма, нужно в программу добавить больше независимых чистых вычислений. Например, если это компилятор, то можно сначала загрузить в память несколько исходных файлов, потом их всех в памяти откомпилировать в целевой код, потом (если не было ошибок) записать скомпилированный код в целевые файлы. Компиляция на втором этапе может быть полностью чистой, при этом отдельные исходники транслируются независимо. А значит, будут параллелиться. При этом программу по-прежнему можно будет откомпилировать и запустить на обычной последовательной реализации Рефала.

А если компилятор не поддерживает автоматическое распараллеливание? Что тогда делать?

 

«Рекомендую решать проблему распараллеливания только для чистого Рефала, там есть чем заняться для минимизации накладных расходов и по балансировке параллельных вычислений.»

Согласен, есть чем заняться. В имеющейся реализации балансировка очень примитивная с высокими накладными расходами.

 

«Ещё там есть проблема функций с малыми временами выполнения, их лучше последовательно выполнять, но для этого их надо уметь выявлять.»

Я вообще исходил из предположения, что все функции Рефала имеют малое время выполнения. Исходная последовательная версия Рефала-05 компилирует себя за 1,9 секунд, при этом делает 2 244 201 шаг. Т.е. 1 шаг занимает в среднем 0,85 микросекунд.

Но о том, что разные шаги выполняются разное относительное время, я не задумывался. Любопытно это проверить экспериментально. Можно предположить, что функции, в которых нет открытых e-переменных, повторных и копируемых e- и t-переменных, будут выполняться быстрее. Но это надо проверять. Подопытный Рефал-05 имеет классическую списковую реализацию.

Т.е. экспериментально любопытно проверить следующее: есть ли значимое отличие между функциями, которые выполняются «быстро», и функциями, которые выполняются «медленно». Есть ли вообще такой феномен, как «функция с малым временем выполнения».

 

С уважением,
Александр Коновалов

 

From: Eisymont Leonid verger-lk_AT_yandex.ru <refal@botik.ru>
Sent: Saturday, March 21, 2020 4:05 PM
To: refal@botik.ru; Alexander Frolov <fro...@nicevt.ru>
Subject: Re: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

 

Александр, по поводу первого доклада. Эти проблемы с побочными эффектами мы исследовали сорок лет назад. Элементы были включены в мою диссертацию, которую я защищал в ИПМ в мае 1983 года. Была "спешная" защита, поскольку я был включен в группу сотрудников ИПМ для работ по Бурану. И было ясно, что к этой тематике мне не вернуться. Еще был препринт ИПМ по распарараллеливанию одного модельного компилятора. Я с Андреем Валентиновичем эти исторические моменты уже вспоминал и обсуждал. Не понимаю, почему он Вам это не передал, либо передал?

Вы ломитесь в открытую дверь. Практический совет такой. Оставьте затею с решением побочного эффекта на автомате. Рекомендую решать проблему распараллеливания только для чистого Рефала, там есть чем заняться для минимизации накладных расходов и по балансировке параллельных вычислений. Еще там есть проблема функций с малыми временами выполнения, их лучше последовательно выполнять, но для этого их надо уметь выявлять. Это уже в компиляторе Рефала. При этом проблемы побочных эффектов решать через машинные операции. Это типа мониторов Хоара. Собственно говоря, именно так мы и решили сорок лет назад проблему распараллеливания компилятора, а там много было побочных эффектов. Это и было описано в упомянутых работах.

Чистый рефал распараллеливал в свое время Александр Фролов, это была его дипломная работа в МИФИ, лет 15 назад. Сейчас он начальник отдела в НИЦЭВТ-е, другими делами занимается, но интерес, как понимаю, сохранился. В то время не было таких возможностей аппаратуры и накладные расходы оказались большими. Сейчас - другое дело. Советую не терять напрасно время, поступайте именно так.

Успехов.

Л.Эйсымонт

 

21.03.2020, 14:25, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Добрый день всем!

Я, прежде чем ответить, ждал презентацию от Станислава (мы договаривались, что он скинет её в рассылку), но он что-то не отсылал и я ответить на письмо забыл. Извините, что так долго.

 

Прозвучало два доклада. Первым был доклад Станислава про распараллеливание Рефала, вторым был доклад Максима Кривчикова про промежуточное представление Рефала и его использование для верификации.

 

Про первый доклад. Станислав рассказывал про свою курсовую работу по курсу «Операционные системы» на тему распараллеливания Рефала (научный руководитель — я). Про распараллеливание.

Из плюсов: предложен подход к параллельному вычислению функций в «грязном» языке программирования. Когда все функции чистые, проще — есть зависимости только по данным. А Рефал — «грязный» язык, в нём есть недетерминированные функции или функции с побочным эффектом (ввод, вывод, копилка). И нужен механизм, который (а) обеспечивал бы параллельные вычисления для чистых функций и (б) обеспечивал правильный порядок выполнения «грязных» функций.

Такой механизм предложен, ждём, когда Станислав скинет его в рассылку.

Из минусов: не распараллеливается. Красивого прироста производительности от большего числа потоков получить не удалось. Нам во время доклада подсказали, что надо было использовать work stealing для балансировки задач между потоками.

 

Про второй доклад. Максим разработал новый диалект Рефала и планирует его использовать для верификации типов в динамически типизированных языках при помощи прогонки (суперкомпиляции). Эту идею верификации я понял не до конца, другие идеи автора мне показались интересными. Доклад был незапланированным, поэтому прошёл без слайдов — в рассылку скидывать нечего.

Андрей Валентинович, второго докладчика Вы добавляли в рассылку?

 

С уважением,
Александр Коновалов

 

From: Eisymont Leonid verger-lk_AT_yandex.ru <refal@botik.ru>
Sent: Monday, March 2, 2020 2:33 PM
To: refal@botik.ru
Subject: Re: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

 

Андрей, очень хотел попасть на семинар, но сижу дома со статьей по ЭКБ для ИИ. Очень тяжело идет, а завтра надо бы отдать коллегам на анализ. Жду презентацию, вопросов у меня уже сейчас много, ведь мы этим занимались 15 лет назад, еще в НИЦЭВТ-е, тогда не пошло, а потом не до этого было. Сейчас интерес есть, даже Рреализацию на односвязных списках Рефала-2 на сервере Модуля установили, она с машинными операциями под MPI, да и вообще испытанная и самая практически продвинутая. Вручную распараллеливать можно, даже пробовали еще в НИЦЭВТ-е. Это в НИР Вектор с Квантом - 2004 год.

Успехов, завидую вашему участию в работе такого семинара.

Л.Эйсымонт

 

02.03.2020, 08:03, "Andrei Klimov andrei_AT_klimov.net" <refal@botik.ru>:

Александр, доброе утро!

 

Жаль, но что ж делать...

Если параллелизм нас так не затянет, что первый доклад с обсуждением займет намного больше времени, чем думали, то есть такие соображения для полезных рефал-обсуждений после него:

• Новый участник семинара Максим Кривчиков может дать у доски аннотацию его статьи, а мы обсудим:

·          

• • Vasenin, V.A., Krivchikov, M.A. Intermediate Representation of Programs with Type Specification Based on Pattern Matching. Program Comput Soft 46, 57–66 (2020). https://doi.org/10.1134/S0361768820010077
  • Это журнал "Программирование", но файл статьи на русском дают только за деньги (или у автора), а у Шпрингера можно взять бесплатно из академических институтов и, наверно, из части университетов. (А есть способы и не только из институтов.:-))

• У меня есть затравочные вопросы по (отсутствующему, но потенциальному) месту Рефала в мире и его (гипотетическому) развитию в соответствующем направлении, которых на доклад недостаточно, но дискуссию могу разжечь. Вот этот доклад и статья доклад Сергея Романенко в ту же сторону, но есть что добавить:

·          

• • С.А. Романенко. Рефал и Агда как воплощения идеи “метаалгоритмического языка” // Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции (18-23 сентября 2017 г., г. Новороссийск). — М.: ИПМ им. М.В.Келдыша, 2017. — С. 417-424 . — http://doi.org/10.20948/abrau-2017-63
  • Файл статьи доступен по этой ссылке.

До встречи!

 

Всего наилучшего,

Андрей Климов

 

 

On Sun, Mar 1, 2020 at 6:13 PM 'Александр Коновалов' via Метавычисления и специализация программ <metacomputation...@googlegroups.com> wrote:

Добрый вечер всем!

Я не успеваю подготовить доклад к завтрашнему семинару, поэтому снимаю завтрашнее выступление.

Поэтому слушать завтра будем только доклад Станислава.

Но я думаю, что мы найдём достаточно тем для обсуждения и без моего выступления.

Простите, что так выходит.

 

С уважением,
Александр Коновалов

 

 

From: Andrei Klimov [mailto:and...@klimov.net]
Sent: Friday, February 28, 2020 2:04 PM
To: metacomputation-ru <metacomputation...@googlegroups.com>; refal@botik.ru
Subject: Семинар по метавычислениям в понедельник 2 марта 2020 в ИПМ

 

Добрый день всем!

В понедельник 2 марта 2020 в 15 часов соберемся в 416 комнате ИПМ им. М.В. Келдыша РАН на семинар, чтобы послушать два доклада, связанных с языком Рефал:

• Станислав Санталов (МГТУ им. Н.Э. Баумана)
  Параллельное выполнение функций в Рефале-05

Основная идея — рассмотреть возможность вычисления функций в Рефале-05 независимо, в различных потоках. Предлагается способ распределения нагрузки между потоками, сохранения порядка вычисления функций и доступа к глобальному полю зрения. Для реализации поставленных задач вводится новая сущность — а-терм, экземпляры которой организуются в дерево с атомарными счетчиками и специальный глобальный потокобезопасный безблокировочный список. Также создается несколько очередей а-термов: общая глобальная и по одной локальной для каждого потока. В конце приводятся результаты тестирования и анализ полученной схемы.

• Александр Коновалов (МГТУ им. Н.Э. Баумана)
  Алгоритм вывода свёрточной формы для функций обработки строк

Под свёрточной формой мы будем подразумевать представление функции, потребляющей некоторую структуру данных с помощью операции, знакомой функциональным программистам под именем foldr для лисповских списков, а в общем случае для типизированных языков типа ML и Haskell как катаморфизм этой структуры данных — термин из теории категорий. Для функций обработки строк (и выражений Рефала), где есть ассоциативная операция конкатенации, это будет катаморфизм для свободного моноида, который также можно рассматривать как гомоморфизм моноида конкатенации в некоторый другой моноид.

Под строками в докладе будут пониматься однородные последовательности произвольных значений, которые могут быть пустыми и для которых определены конкатенация и итерация с обеих сторон. Для сравнения: в лисповских списках определено добавление одного элемента в начало (cons) и итерация только слева-направо.

Представление функций, потребляющих строки, в свёрточной форме даёт некоторые преимущества:

• Появляется возможность выполнять слияние (fusion) с функциями, порождающими строки — в результирующей функции промежуточная строка даже не будет создаваться. Это вообще верно для любого катаморфизма и является основой сокращённой дефорестации (shortcut deforestation).
• Появляется возможность распараллеливать вычисление функции — строку можно разделить на части, свернуть независимо и результаты их свёрток скомбинировать в искомое значение. Это свойство верно только для свёрточной формы строковых функций.
• Можно менять направление обработки строк — из свёрточной формы можно получить функцию, читающую строку как слева-направо, так и справа-налево. Например, это позволяет преобразовать наивную функцию, вычисляющую значение многочлена, в схему Горнера.

На семинаре 29 октября 2019 года рассматривалась сокращённая дефорестация и способ её реализации для языка Рефал. На нём было введено понятие свёрточной формы для строковых функций в терминах Рефала и были рассмотрены некоторые примеры функций в этой форме. Способ построения свёрточной формы на том семинаре не давался.

В докладе 2 марта 2020 года мы определим свёрточную форму уже без использования терминологии Рефала, а также рассмотрим алгоритм перевода функций в свёрточную форму. Входом алгоритма будет функция, анализирующая строку по одному элементу слева-направо (или справа-налево), выходом будет свёрточная форма либо сообщение о том, что алгоритм не может её вывести.

Алгоритм применим для ограниченного класса функций, т.е. не для любой функции, представимой в свёрточной форме, эту форму можно вывести. Однако, этот класс достаточно широк, что будет продемонстрировано на нескольких примерах.

Вывод свёрточной формы использует ограниченную суперкомпиляцию на некоторых этапах своей работы. Ограниченность выражается в допустимых вариантах обобщения похожих конфигураций. Если в процессе требуется выполнить недопустимое обобщение, то или преобразуемая функция не представима в свёрточной форме, или она слишком сложна для этого алгоритма.

В отличие от доклада 29.10.2019 для понимания этого доклада знания Рефала не требуется.

---

Гости ИПМ, которым нужен разовый пропуск, напишите мне по email или пошлите смс-ку с ФИО и НОМЕРОМ ПАСПОРТА на моб. +7 985 364 3536 до 12 час в день семинара. Пропуск получите либо в бюро пропусков в окошке слева от вахтера в главной проходной ("стеклянной", со стороны Миусской площади), либо непосредственно у вахтера. Я вам сообщу, какой вид пропуска будет оформлен.

С ноутбуком, не зарегистрированным в списке на вахте на пронос в ИПМ, лучше не приходить, чтобы не споткнуться о ситуацию, когда не пропустят, а соответствующего начальства, чтобы подписать материальный пропуск на внос-вынос, не окажется на месте.

---

До встречи!

Андрей Климов

--
Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и специализация программ".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес metacomputation-ru+unsubscr...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/metacomputation-ru/CAM7HiMnG8AfcNM%2BUG3ufHWeKX_0qs-Mbx_nWp7Eq2DWMVP-tSw%40mail.gmail.com.

 

--
Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и специализация программ".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес metacomputation-ru+unsubscr...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/metacomputation-ru/0af601d5efdc%240145e8a0%2403d1b9e0%24%40mail.ru.