Почему в Хаскелле нет неявного параллелизма?

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

рассмотрим этот тривиальный пример:

f = do
  a <- Just 1
  b <- Just $ Just 2
  -- ^ The above line does not utilize an `a` variable, so it can be safely
  -- executed in parallel with the preceding line
  c <- b
  -- ^ The above line references a `b` variable, so it can only be executed
  -- sequentially after it
  return (a, c)
  -- On the exit from a monad scope we wait for all computations to finish and 
  -- gather the results

схематично план выполнения можно описать так:

               do
                |
      +---------+---------+
      |                   |
  a <- Just 1      b <- Just $ Just 2
      |                   |
      |                 c <- b
      |                   |
      +---------+---------+
                |
           return (a, c)

почему в компиляторе с флагом или прагмой еще нет такой функциональности? Каковы практические причины?

5 53
haskell concurrency parallel-processing compiler-optimization

5 ответов:

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

таким образом, вы в конечном итоге тратите усилия на ведение бухгалтерского учета, а не запускаете вещи быстрее.

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

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

обратите внимание, что для некоторых подмножеств (например, обработка массива) существуют полностью автоматические библиотеки распараллеливания с жесткими моделями затрат.

дополнительные сведения об этом см., http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf, где они вводят автоматизированный подход к вставке par в произвольных программ на Haskell.

74

хотя ваш блок кода может быть не лучшим примером из-за неявных данных зависимость между a и b стоит отметить, что эти два привязки коммутируют в этом

f = do
  a <- Just 1
  b <- Just $ Just 2
  ...

даст те же результаты

f = do
  b <- Just $ Just 2
  a <- Just 1
  ...

таким образом, это все еще может быть распараллелено спекулятивным образом. Стоит отметить, что это не должно иметь ничего общего с монадами. Мы могли бы, например, оценить все независимые выражения в let-блок параллельно или мы могли бы ввести версия let что бы это сделать. Элемент библиотека lparallel для Common Lisp делает это.

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

тогда это не всегда быстрее бросить больше ядер на проблему. Даже когда явное распараллеливание проблемы со многими доступными библиотеками Haskell, вы будете часто не вижу большого ускорения, просто оценивая выражения параллельно из-за тяжелого выделения и использования памяти и напряжения, которое это накладывает на мусор коллектор и кэш процессора. В конечном итоге вам понадобится хорошая компактная компоновка памяти и чтобы пройти ваши данные разумно. Имея 16 потоков пересекать связанные списки будет просто узкое место вы на шине памяти и может на самом деле сделать вещи медленнее.

по крайней мере, какие выражения могут быть эффективно распараллелен-это то, что не очевидно для многих программистов (по крайней мере, это не для этого), поэтому получение компилятора сделать это эффективно нетривиально.

24

короткий ответ: иногда запуск вещей параллельно оказывается медленнее, а не быстрее. И выяснение того, когда это так, а когда это не очень хорошая идея, является нерешенной исследовательской проблемой.

тем не менее, вы все еще можете "внезапно использовать все эти ядра, не беспокоясь о потоках, тупиках и условиях гонки". Она не автоматическая, нужно просто дать компилятору некоторые подсказки о том, где это сделать! :- D

6

одна из причин заключается в том, что Haskell не является строгим и по умолчанию ничего не оценивает. Вообще компилятор не знает, что вычисление a и b завершается, следовательно, пытаясь вычислить его было бы пустой тратой ресурсов:

x :: Maybe ([Int], [Int])
x = Just undefined
y :: Maybe ([Int], [Int])
y = Just (undefined, undefined)
z :: Maybe ([Int], [Int])
z = Just ([0], [1..])
a :: Maybe ([Int], [Int])
a = undefined
b :: Maybe ([Int], [Int])
b = Just ([0], map fib [0..])
    where fib 0 = 1
          fib 1 = 1
          fib n = fib (n - 1) + fib (n - 2)

рассмотрим его для следующих функций

main1 x = case x of
              Just _ -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

(a, b) часть не нуждается в оценке. Как только вы получите, что x = просто _ вы можете перейти к ветке-следовательно, он будет работать для всех значений, но a

main2 x = case x of
              Just (_, _) -> putStrLn "Just"
              Nothing -> putStrLn "Nothing"

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

main3 x = case x of
              Just (a, b) -> print a >> print b
              Nothing -> putStrLn "Nothing"

эта функция сначала напечатает первый список, а затем второй. Это будет работать для z (что приводит к печати бесконечного потока чисел, но Haskell может справиться с этим). b в конечном итоге закончится память.

теперь в целом вы не знаете, если вычисление завершается или нет, и сколько ресурсов он будет поглощать. Бесконечные списки прекрасно подходят в Haskell:

main = maybe (return ()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers

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

кроме того - что было упомянуто другими ответами - трудно предсказать, стоит ли привлекать накладные расходы дополнительного потока. Несмотря на то, что GHC не порождает новые потоки для искр, используя зеленую резьбу (с фиксированным количеством потоков ядра - за исключением нескольких исключений), вам все равно нужно перемещать данные из одного ядра в другое и синхронизировать между ними, что может быть довольно дорогой.

однако Хаскелл действительно руководил параллелизацией, не нарушая чистоту языка par и похожие функции.

4

на самом деле была такая попытка, но не на обычном оборудовании из-за низкого доступного количества ядер. Проект называется Reduceron. Он запускает код Haskell с высоким уровнем параллелизма. В случае, если он когда-либо был выпущен как правильное ядро ASIC 2 ГГц, у нас был бы серьезный прорыв в скорости выполнения Haskell.

2