вс, 22 мар. 2020 г., 15:37 Eisymont Leonid verger-lk_AT_yandex.ru < refal@botik.ru>:
> Аркадий точно пояснил проблему с малыми временами выполнения функций. В > диссертации 1983-го года я предложил частичное инженерное решение - вставил > в правые части рефал-предложений условные конструкции. Там действительно > проблема "накачки" времени выполнения рефал-функции была обозначена и > решалась. Это касается и аппаратуры. Насколько помню, в одной из разработок > коллектива под руководством В.Далли (Стэнфордский университет) на машине с > экспериментальной потоковой архитектурой был поставлен рекорд по > "минимальному кванту распараллеливания" - 70 наносекунд. > Если работы по распараллеливанию будут ставиться всерьез, то мы имеющиеся > данные, конечно, предоставим. Распараллеливание Рефала рассматриваем как > одно из фундаментальных направлений по ЭКБ для суперкомпьютеров. Подробнее > - направление 5.1 в поставленных главных направлениях работ по ЭКБ статьи в > журнале "Вопросы кибербезопасности", N4, 2019 года. В сети есть, это первая > статья номера. > Леонид, спасибо! Почитаю. Вот ссылка на станицу выпуска, где первые 4 страницы твои: https://cyberrus.com/archives/2220 Андрей Л.Эйсымонт > > 22.03.2020, 12:03, "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 > <http://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 > <http://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 как *катаморфизм > <https://traditio.wiki/%D0%9A%D0%B0%D1%82%D0%B0%D0%BC%D0%BE%D1%80%D1%84%D0%B8%D0%B7%D0%BC>* > этой структуры данных — термин из теории категорий. Для функций обработки > строк (и выражений Рефала), где есть ассоциативная операция конкатенации, > это будет катаморфизм для свободного моноида, который также можно > рассматривать как гомоморфизм моноида конкатенации в некоторый другой > моноид. > > Под строками в докладе будут пониматься однородные последовательности > произвольных значений, которые могут быть пустыми и для которых определены > конкатенация и итерация с обеих сторон. Для сравнения: в лисповских списках > определено добавление одного элемента в начало (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 > <https://groups.google.com/d/msgid/metacomputation-ru/CAM7HiMnG8AfcNM%2BUG3ufHWeKX_0qs-Mbx_nWp7Eq2DWMVP-tSw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > > > -- > Вы получили это сообщение, поскольку подписаны на группу "Метавычисления и > специализация программ". > Чтобы отменить подписку на эту группу и больше не получать от нее > сообщения, отправьте письмо на электронный адрес > metacomputation-ru+unsubscr...@googlegroups.com. > Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке > https://groups.google.com/d/msgid/metacomputation-ru/0af601d5efdc%240145e8a0%2403d1b9e0%24%40mail.ru > <https://groups.google.com/d/msgid/metacomputation-ru/0af601d5efdc%240145e8a0%2403d1b9e0%24%40mail.ru?utm_medium=email&utm_source=footer> > . > > > >