Автоматическое распараллеливание
Что является Вашим мнением относительно проекта, который попытается взять код и разделить его к потокам автоматически (возможно, время компиляции, вероятно, во времени выполнения).
Смотрите на код ниже:
for(int i=0;i<100;i++)
sum1 += rand(100)
for(int j=0;j<100;j++)
sum2 += rand(100)/2
Этот вид кода может автоматически быть разделен к 2 различным потокам, которые работают параллельно. Вы думаете, что это даже возможно? У меня есть чувство, что теоретически это невозможно (это напоминает мне проблема остановки), но я не могу выровнять по ширине эту мысль.
Вы думаете, что это - полезный проект? есть ли что-нибудь как он?
5 ответов
Возможно ли в общем случае узнать, можно ли распараллелить часть кода, на самом деле не имеет значения, потому что даже если ваш алгоритм не может обнаружить все варианты, которые можно распараллелить, возможно, он сможет обнаружить некоторые из них.
Это не значит, что это было бы полезно. Примите во внимание следующее:
- Прежде всего, чтобы сделать это во время компиляции, вы должны проверить все пути кода, которые вы потенциально можете достичь внутри конструкции, которую вы хотите распараллелить.Это может быть сложно для чего угодно, кроме простых вычислений.
- Во-вторых, вы должны каким-то образом решить, что можно распараллеливать, а что нет. Вы не можете тривиально разбить цикл, который изменяет одно и то же состояние, например, на несколько потоков. Вероятно, это очень сложная задача, и во многих случаях вы не будете уверены - две переменные могут фактически ссылаться на один и тот же объект.
- Даже если бы вы смогли этого добиться, это сбило бы пользователя с толку. Было бы очень сложно объяснить, почему его код нельзя распараллеливать и как его следует изменить.
Я думаю, что если вы хотите добиться этого на Java, вам нужно написать больше как библиотеку, и позволить пользователю решать, что распараллеливать (функции библиотеки вместе с аннотациями? Просто размышляя вслух). Функциональные языки больше подходят для этого.
Мелочь: во время курса параллельного программирования нам нужно было проверить код и решить, можно ли его распараллеливать или нет. Я не могу вспомнить подробностей (что-то о свойстве «не больше одного раза»? Кто-нибудь меня подскажет?), Но мораль этой истории заключается в том, что это было чрезвычайно сложно даже для, казалось бы, тривиальных случаев.
Это называется автоматическим распараллеливанием. Если вы ищете какую-нибудь программу, которая сделает это за вас, то ее еще не существует. Но может со временем. Это сложная проблема, и в ней ведутся активные исследования. Если вам все еще интересно ...
Можно автоматически разбить ваш пример на несколько потоков, но не так, как вы думаете. Некоторые современные методы пытаются запустить каждую итерацию для -цикла в своем собственном потоке. Один поток получит четные индексы (i = 0, i = 2, ...), другой получит нечетные индексы (i = 1, i = 3, ...). Как только этот для -цикла будет выполнен, можно будет начинать следующий. Другие методы могут стать еще более безумными, выполняя приращение i ++ в одном потоке и rand () в отдельном потоке.
Как отмечали другие, существует истинная зависимость между итерациями, потому что rand () имеет внутреннее состояние. Само по себе это не препятствует распараллеливанию. Компилятор может распознать зависимость от памяти, и измененное состояние rand () может быть перенаправлено от одного потока к другому.Но это, вероятно, ограничивает вас всего несколькими параллельными потоками. Без зависимостей вы можете запустить это на любом количестве ядер, которое у вас есть.
Если вы действительно интересуетесь этой темой и не возражаете просеять исследовательские работы:
Есть некоторые проекты, которые пытаются упростить распараллеливание - например, Cilk. Однако это не всегда работает так хорошо.
Это, конечно, возможно, но это невероятно трудная задача. Это было центральным направлением исследований компиляторов в течение нескольких десятилетий. Основная проблема заключается в том, что мы не можем создать инструмент, способный найти наилучшее разбиение на потоки для java-кода (это эквивалентно проблеме остановки).
Вместо этого нам нужно ослабить нашу цель - найти наилучшее разбиение на потоки в некотором разделе кода. В общем случае это все еще очень сложно. Поэтому нам нужно найти способы упростить проблему, один из которых - забыть об общем коде и начать рассматривать конкретные типы программ. Если у вас простой поток управления (постоянные ограниченные for-петли, ограниченное ветвление....), то вы сможете продвинуться гораздо дальше.
Другим упрощением является уменьшение количества параллельных блоков, которые вы пытаетесь занять. Если вы объедините оба этих упрощения вместе, то получите современное состояние автоматической векторизации (особый тип параллелизации, который используется для генерации кода в стиле MMX / SSE). Достижение этой стадии заняло десятилетия, но если вы посмотрите на компиляторы, подобные Intel, то производительность начинает становиться довольно высокой.
Если вы переходите от векторных инструкций внутри одного потока к нескольким потокам в рамках одного процесса, то возникает огромное увеличение задержки при перемещении данных между различными точками кода. Это означает, что параллелизация должна быть намного лучше, чтобы выиграть у коммуникационных накладных расходов. В настоящее время это очень актуальная тема для исследований, но нет автоматических инструментов, ориентированных на пользователя. Если вы сможете написать такой инструмент, который будет работать, это будет очень интересно для многих людей.
Для вашего конкретного примера, если предположить, что rand() является параллельной версией, так что вы можете вызывать ее независимо из разных потоков, то довольно легко увидеть, что код может быть разделен на два. Компилятору достаточно провести анализ зависимостей, чтобы убедиться, что ни один из циклов не использует данные другого и не влияет на него. Таким образом, порядок между ними в коде пользовательского уровня - это ложная зависимость, которую можно разделить (т.е. поместить каждый в отдельный поток).
Но это не совсем то, как вы хотели бы распараллелить код. Похоже, что каждая итерация цикла зависит от предыдущей, поскольку sum1 += rand(100) - это то же самое, что sum1 = sum1 + rand(100), где sum1 в правой части - это значение из предыдущей итерации. Однако единственной операцией является сложение, которое является ассоциативным, поэтому мы переписываем сумму разными способами.
sum1 = (((rand_0 + rand_1) + rand_2) + rand_3) ....
sum1 = (rand_0 + rand_1) + (rand_2 + rand_3) ...
Преимущество второго способа в том, что каждое отдельное сложение в скобках может вычисляться параллельно со всеми остальными. Когда у вас есть 50 результатов, их можно объединить в еще 25 сложений и так далее... Таким образом, вы выполняете больше работы 50+25+13+7+4+2+1 = 102 дополнения против 100 в оригинале, но последовательных шагов всего 7, так что, не считая параллельного форкинга/соединения и коммуникационных накладных расходов, процесс выполняется в 14 раз быстрее. Это дерево сложений называется операцией сбора в параллельных архитектурах и, как правило, является самой дорогой частью вычислений.
На очень параллельной архитектуре, такой как GPU, приведенное выше описание будет лучшим способом распараллелить код. Если вы используете потоки внутри процесса, это будет убито накладными расходами.
Подводя итоги: невозможно сделать идеально, очень трудно сделать хорошо, есть много активных исследований, чтобы выяснить, как много мы можем сделать.
Это практически невозможно.
Проблема в том, что вам нужно знать заранее гораздо больше информации, чем доступно компилятору или даже среде выполнения, чтобы эффективно распараллеливать.
Хотя можно было бы распараллелить очень простые циклы, даже в этом случае существует риск. Например, приведенный выше код можно было бы распараллелить только в том случае, если rand () является потокобезопасным, а многие процедуры генерации случайных чисел - нет. (Однако Java Math.random () синхронизируется для вас.)
Попытка выполнить этот тип автоматического распараллеливания, по крайней мере, на данный момент, непрактична для любого «реального» приложения.