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

[Александр Гусев gusev_aleksandr_AT_mail . ru]

Добрый день!
 
Как я понимаю, параллелизм может быть нескольких видов:
*  Распараллеливание внутри одной операции, например, поиска по большому 
массиву. Это может быть сделано вне языковой сущности Рефала — с помощью 
«железа» или СУБД;
*  Распараллеливание на уровне ветвей при вычислении одного выражения, с учётом 
функций или без;
*  Распараллеливание на уровне алгоритма — создание параллельных потоков, 
решающих по-сути разные задачи.
Пункт 1 работает хорошо и понятно, только не даёт глобального выигрыша, так как 
применим в ограниченном количестве случаев.
Пункт 2 представляет наибольший интерес для автоматизации распараллеливания, 
только реализации реальной пока не видно, хотя серьёзные исследования были. 
Почему? Трудоёмко и эффективность непредсказуема. Для получения как-нибудь 
ясной картины я предлагаю опираться на статистику, которая должна 
вырабатываться на предварительно обрабатываемых наборах данных. В зависимости 
от решаемых задач эти наборы могут отличаться. Такого рода оптимизация уже 
делается в серверных решениях для СУБД. Называется «план запроса». На эту тему 
создано достаточное количество практических решений, позволяющих этим серверам 
работать в меняющихся и совсем разных условиях. Почему бы не применить эту 
технологию для Рефала? Требуется разработка, конечно.
Пункт 3 тоже из области серверного мышления: нет необходимости всю большую 
задачу «забивать» в один поток. При наличии возможности межпотокового 
взаимодействия сложная задача обычно выигрывает от такого разбиения.
 
Это я к чему: если принять Рефал — систему изначально параллельной, параллелизм 
выполнения придёт. Однако, для этого нужно начинать не с переделки популярных 
однопользовательских и однозадачных решений, а «с нуля». Тогда всё получится 
быстрее, чем за 20 лет.
 
В связи с этим я готов выразить удивление, что мой проект по созданию как раз 
серверного решения не вызвал видимого интереса за прошедшие полгода с момента 
его обнародования. Даже не сам проект, поскольку меня в сообществе немногие и 
знают. Сама идея не находит ожидаемого отражения. Или я этого не вижу. А проект 
продвигается в меру моих возможностей. Не быстро, к сожалению. Но будущее как 
раз за такими решениями — серверными и обязательно тиражными, если уж оно есть. 
Тиражность фактически закончилась после завершения эпохи использования у нас 
«взрослых» компьютеров — БЭСМ-6 и серии ЕС ЭВМ. 
>Воскресенье, 22 марта 2020, 12:03 +03:00 от Arkady Klimov 
>arkady.klimov_AT_gmail.com <refal@botik.ru>:
> 
>Немного встряну про параллелизм.
>Имхо существенное ускорения получается там и тогда, когда единицы 
>распараллеливания достаточно крупны (при том, что их достаточно много).
>Сегодня это не менее 10 мкс или 10 Кфлоп. Собственно, об этом упоминал Леонид 
>(проблемы функций с малыми временами, накладные расходы).
>Поэтому что для чистого, что для грязного, все равно надо укрупнять шаги, 1мкс 
>это мало. 
>Но от компилятора этого ждать трудно. Придется получать эту инфу от 
>программиста, ему-то виднее.
>Хотя какое-то рантайм-профилирование может быть полезным (но не по операторам 
>отождествления-замены, а по функциям).
>А "умный" компилятор или рантайм пусть использует результаты. Кто-то пытался 
>так делать?
>Аркадий  
>сб, 21 мар. 2020 г. в 18:32, Eisymont Leonid verger-lk_AT_yandex.ru < 
>refal@botik.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 ;  Al exander 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
>>>>>> .
>  
 
 
С уважением,
Александр Гусев
gusev_aleksa...@mail.ru