Может ли компилятор автоматически распараллеливать код, поддерживающий распараллеливание?

Question

Вместо добавления оператора расширения PLinq AsParallel () не мог бы компилятор выяснить это для нас автоматически? Существуют ли примеры, когда вы специально не хотите распараллеливания, если код поддерживает это?

Answer 1

Автоматическое распараллеливание сложнее, чем может показаться на первый взгляд. Это та часть «если код поддерживает это», которая вас и получает. Рассмотрим что-то вроде

counter = 0

f(i) 
{
   counter = counter + 1
   return i + counter
}

result = map(f, {1,2,3,4})

Если компилятор просто решит распараллелить карту здесь, вы можете получить разные результаты при каждом запуске программы. Конечно, очевидно, что f на самом деле не поддерживает использование таким образом, потому что у него есть глобальная переменная. Однако, если f находится в другой сборке, компилятор не может знать, что распараллеливать его небезопасно. Он может проанализировать сборку, в которой находится f во время выполнения, и затем принять решение, но тогда возникает вопрос: «Достаточно ли быстр самоанализ и достаточно ли динамическое распараллеливание, чтобы не свести на нет преимущества от этого?» И иногда это может оказаться невозможным для самоанализа, f может быть функцией P / Invoked, которая на самом деле может идеально подходить для распараллеливания, но, поскольку среда выполнения / компилятор не может знать, что она должна предполагать, что она не может быть , Это только верхушка айсберга.

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

Answer 2

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

Проблема с нечистыми языками, такими как C #, обычно заключается в том, что не хватает параллелизма.На нечистом языке человеку очень трудно и почти невозможно для программы выяснить, взаимодействуют ли два фрагмента кода друг с другом или со средой.

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

ДляНапример, на чистом, ссылочно-прозрачном, функциональном языке, если у меня есть что-то вроде этого:

if a <= b + c
  foo
else
  bar
end

Я мог бы запустить пять потоков и вычислить a, b, c, foo и bar параллельно, затем я вычисляю +, а затем <= и, наконец, я вычисляю if, что просто означает отбрасывание результата либо foo или bar, которые обауже были вычислены.(Обратите внимание, как это зависит от функциональности: на нечистом языке вы не можете просто вычислить обе ветви if и затем выбросить одну. Что, если обе распечатать что-то? Как бы вы «распечатали» это?)

Но если a, b, c, foo и bar действительно дешевы, то накладные расходы этих пяти потоков будут намного больше, чем сами вычисления.

Answer 3

Я занимаюсь исследованиями в области автоматического распараллеливания. Это очень сложная тема, которая является предметом многих кандидатов наук. диссертаций. Статический анализ кода и автоматическое распараллеливание были выполнены с большим успехом для таких языков, как Fortran, но есть ограничения в способности компилятора анализировать межрегиональные зависимости. Большинство людей не желают жертвовать гарантией правильности кода в обмен на потенциальное увеличение параллельной производительности, поэтому компилятор должен быть достаточно консервативным в том, что касается вставки параллельных маркеров.

Итог: да, компилятор может распараллеливать код. Но человек часто может распараллелить это лучше, и компилятор выяснит, куда поместить маркеры, может быть очень, очень, очень сложно. На эту тему доступны десятки исследовательских работ, например, фоновая работа для распараллеливающего компилятора Mitosis или работа D-MPI.