[Haskellъ] Почему нет распараллеливающих компиляторов?

ФП-программисты просто ленивы :)

http://www.macs.hw.ac.uk/~dsg/gph/ ?

> http://www.macs.hw.ac.uk/~dsg/gph/ ?

Несмешно, блин. К Хаскелю прикрутили par и seq от Оккама. Так в чём тогда профит хаскелевской чистоты?

Не написали - значит, не нужен.

> прикрутили par и seq от Оккама

Ибо Оккам труЪ.

http://research.microsoft.com/~tharris/papers/2005-haskell.pdf ?

То, о чём идёт речь по ссылке, давно идёт в GHC искаропки. Речь идёт всего лишь о раскидывании нитей из Control.Concurrent на разные процессоры, кого этим удивишь?

Аффтору видимо это нужно:

http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell

> http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell

Аффтору нужен _прозрачный_, _автоматический_ параллелизм. Чтобы, грубо говоря, умный компилятор мог в выражении a + b вычислять параллельно a и b, пользуясь чистотой и ссылочной прозрачностью. А ваши параллельные функции и массивы вовсю клепают и для явы с плюсами. Хотя это уже лучше, чем явное создание нитей, конечно.

Да, мне тоже было бы такое интересно...

> Аффтору нужен _прозрачный_, _автоматический_ параллелизм. Чтобы, грубо говоря, умный компилятор мог в выражении a + b вычислять параллельно a и b, пользуясь чистотой и ссылочной прозрачностью. А ваши параллельные функции и массивы вовсю клепают и для явы с плюсами. Хотя это уже лучше, чем явное создание нитей, конечно.

a + b = par b ((Prelude.+) a b)

сделать это автоматически правильно имхо нетривиально, ибо если паралеллизм будет везде пихатся бездумно то будет гораздо тормознее, Если 2 + 3 паралеллить то будет только тормознее...

> если паралеллизм будет везде пихатся бездумно то будет гораздо тормознее

Ну так никто и не обещал, что будет легко. Просто постоянно слышно, что "ФП решит проблему использования многоядерников", а на деле никому это особо и не нужно.

> Если 2 + 3 паралеллить

ИМХО, это не запараллелить никак :)

> Аффтору нужен _прозрачный_, _автоматический_ параллелизм.

А может еще и программы за анонимусов писать? Не бывает такого

http://bmdfm.com/home.html ?

>Ну так никто и не обещал, что будет легко. Просто постоянно слышно, что "ФП решит проблему использования многоядерников", а на деле никому это особо и не нужно.

Так оно и решает - par, стратегии, STM, nested parallelism. Основная проблема сейчас что GC однопоточный, нужно сделать хороший асинхронный GC.

> http://bmdfm.com/home.html ?

Ну ладно,

... на практике

:-)

К тому же, кажется, тут те же проблемы:

> BMDFM exploits fine-grain parallelism. All instructions of an application will be processed in parallel. In addition, it is possible to exploit coarse-grain parallelism that will decrease costs spent on dynamic scheduling. To achieve this a portion of C code can be defined as a user function, which will be treated by the dynamic scheduler as one seamless instruction.

> http://bmdfm.com/home.html ?

Эта ссылка как бы намекает на то, что чистота и отсутствие побочных эффектов, вопреки рекламным обещаниям, ни разу не облегчают распараллеливание, лол?

> А может еще и программы за анонимусов писать? Не бывает такого

Узко мыслишь, дуралей. Программы, которые пишут программы, хакеры научились писать ещё в 60-е годы. Если не раньше.

> par, стратегии, STM, nested parallelism

Хм. PAR - это оккамовский конструктор процессов? :D Насчет остального - это всё _потенциальные источники_ параллелизма, которые существующие компиляторы автоматически не параллелят (поправь, если ошибаюсь).

> Узко мыслишь, дуралей. Программы, которые пишут программы, хакеры научились писать ещё в 60-е годы. Если не раньше.

Ага, может быть нам программа и какой-нибудь параллельный алгоритм за ученых придумает?

Чтобы компилятор делал то что хочет автор ему имхо нужно знать время вычисления каждого выражения, а это только в рантайме известно. Потом можно решить задачу минимизации этого времени путем распределения высилений подвыражений (зная время их вычисления) между процессорами + учитывая зависимость вычислений от результатов предидущих. В нашем примере если например b зависит от a то нет смысла его пытаться вычислить паралелльно с а. То есть чтобы оптимально такую задачу решить нужен пробный прогон в профайлере с измерением времени вычисления всех конструкций + анализ зависимостей. Но не факт что потом такая прога будет оптимально работать на другом железе / другом количестве процов.

>А ваши параллельные функции и массивы вовсю клепают и для явы с плюсами.

Там не в паралелльных массивах дело.

Nested data parallelism _extends_ the programming model of flat data parallelism, as known from parallel Fortran dialects, _to irregular parallel computations_ (such as divide-and-conquer algorithms) and _irregular data structures_ (such as sparse matrices and tree structures).

> Nested data parallelism _extends_ the programming model of flat data parallelism, as known from parallel Fortran dialects

Это замечательно. Но где ускорение от этого самого nested data parallelism? Оно не нужно, или его не так уж просто извлечь?

автоматически распареллеливать не эффективно, т.к придется применься очень сложные эвристики для достижения результата, гораздо проще отмечать те куски которые надо распареллелить, что с успехом делает (p)seq & par. так же надо ввести хороший механизм message passing'а, к примеру π-calculus...

ps: бесплатный сыр...

> Это замечательно. Но где ускорение от этого самого nested data parallelism? Оно не нужно, или его не так уж просто извлечь?

Будет ускорение вот тут доступно расписано: http://research.microsoft.com/~simonpj/papers/ndp/ndpslides.pdf

Просто они пока vectorization не реализовали. В NESL'е говорят реализовано:

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/CMU-CS-95-...

The examples include algorithms for median finding, sorting, string searching, finding prime numbers, and finding a planar convex hull. NESL currently compiles to an intermediate language called VCODE, which runs on vector multiprocessors (the CRAY C90 and J90), distributed memory machines (the IBM SP2, Intel Paragon, and Connection Machine CM-5), and sequential workstations. For many algorithms, the current implementation gives performance close to optimized machine-specific code for these machines.

Научиться не научились, но параллелизм с использованием Control.Parallel.Strategies получается простой и, на взгляд, неплохой. Мы тут на него немного смотрели на последней SPbHUG.

> Возник вдруг вопрос, почему чисто функциональный Хаскель так и не научились прозрачно распараллеливать? И это при том, что распараллеливающие компиляторы Фортрана промышленно используются ещё с 19лохматых годов. Или нас цинично на@бывают, когда говорят, что за ФП будущее?

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

Чтобы прога сама раскидывала по процессам, это ты сильно губу раскатал.

На данный момент наиболее точно к этому вопросу подошел Эрланг. Он в основу своего программирования положил многопоточность. Тоесть ты сразу пишешь программу многопоточно. При этом во много проще чем в однопоточном программировании.

Сейчас наиболее интересные варианты паралеллизма - Актор, то что сделано в Эрланге и STM - то что сейчас микрософт пилит для Хаскелля.

PS: Кстати, следующий GC для Хаскелля будет многопоточный.

>Узко мыслишь, дуралей. Программы, которые пишут программы, хакеры научились писать ещё в 60-е годы. Если не раньше.

Почему хакеры? :) Я товарищу ещё в ~1994-м на qbasic писал самопишущуюся софтину для обсчёта серий экспериментальных данных для дисера. Бралась серия, аппроксимировалась по широкому спектру разнородных функций, для полученной функции писалась программа поиска экстремума, запускалась, найденные экстремумы сбрасывались в файл, потом по этому файлу ещё одна аппроксимация, уже по фиксированной функции... :)

> PS: Кстати, следующий GC для Хаскелля будет многопоточный.

Когда релиз?

> В нашем примере если например b зависит от a то нет смысла его пытаться вычислить паралелльно с а.

А откуда это в чистом функциональном языке возьмется эта зависимость?

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

> На данный момент наиболее точно к этому вопросу подошел Эрланг

Эрланг - это неправильно понятый Оккам. скрещенный с Прологом :)

> Сейчас наиболее интересные варианты паралеллизма - Актор

Что, та самая модель, которой уже лет 30?

>А откуда это в чистом функциональном языке возьмется эта зависимость?

Из за ленивости, например если b = 2*a , а а - нечто долговычисляемое. При последовательном вычислении оно будет вычислятся только один раз, а если запустить паралелльное вычисление a и b то a может 2 раза вычислятся.