Автоматическое распараллеливание

Question

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

Посмотрите на код ниже:

for(int i=0;i<100;i++)
   sum1 += rand(100)
for(int j=0;j<100;j++)
   sum2 += rand(100)/2

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

Как вы думаете, это полезный проект? есть что-нибудь подобное?

Answer 1

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

Возможно автоматически разбить ваш пример на несколько потоков, но не так, как вы думаете. Некоторые современные методы пытаются запустить каждую итерацию для -loop в своем собственном потоке. Один поток получит четные индикаторы (i = 0, i = 2, ...), другой получит нечетные индексы (i = 1, i = 3, ...). Как только этот для -петля закончен, можно запустить следующий. Другие методы могут стать более сумасшедшими, выполняя приращение i++ в одном потоке и rand() в отдельном потоке.

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

Если вы действительно интересуетесь этой темой и не возражаете проанализировать исследовательские работы:

1. Автоматическое извлечение нитей с разделенной программной конвейерной обработкой (2005) Дж. Оттони.
2. Спекулятивное распараллеливание с использованием программных многопоточных транзакций (2010) А. Рамана.

Answer 2

Это практически невозможно.

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

Хотя было бы возможно распараллелить очень простые циклы, даже тогда существует риск. Например, приведенный выше код может быть распараллелен только в том случае, если rand() поточно-ориентирован, а многие подпрограммы генерации случайных чисел - нет. (Java Math.random () синхронизирован для вас - однако.)

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

Answer 3

Это, конечно, возможно, но это невероятно сложная задача.Это было центральным направлением исследований компиляторов в течение нескольких десятилетий.Основная проблема заключается в том, что мы не можем создать инструмент, который может найти лучший раздел на потоки для кода 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 раз быстрее.Это дерево дополнений называется операцией сбора в параллельных архитектурах и, как правило, является дорогостоящей частью вычислений.

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

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

Answer 4

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

Это не значит, что это было бы полезно. Учтите следующее:

1. Прежде всего, чтобы сделать это во время компиляции, вы должны проверить все пути кода, которые вы потенциально можете найти внутри конструкции, которую вы хотите распараллелить. Это может быть сложно для всего, кроме простых вычислений.
2. Во-вторых, вы должны как-то решить, что распараллеливать, а что нет. Например, вы не можете просто разбить цикл, который изменяет одно и то же состояние на несколько потоков. Это, вероятно, очень сложная задача, и во многих случаях вы в конечном итоге не будете уверены - две переменные могут фактически ссылаться на один и тот же объект.
3. Даже если бы вы могли достичь этого, это могло бы привести пользователя в замешательство. Было бы очень трудно объяснить, почему его код нельзя распараллелить и как его следует изменить.

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

Как мелочь: во время курса параллельного программирования мы должны были проверить код и решить, был ли он распараллелен или нет. Я не могу вспомнить специфику (что-то в отношении свойства «по крайней мере, однажды»? Кто-то меня заполнил?), Но мораль этой истории заключается в том, что это было чрезвычайно трудно даже для того, что казалось тривиальными случаями.

Answer 5

Есть несколько проектов, которые пытаются упростить распараллеливание - например, Cilk .Однако это не всегда хорошо работает.

Answer 6

Языком программирования является Java, а Java - это виртуальная машина. Так что нельзя ли выполнять код во время выполнения в разных потоках, принадлежащих виртуальной машине. Так как вся память и т. Д. Обрабатывается таким образом, это не может привести к повреждению. Вы можете увидеть код как набор инструкций, оценивающих время выполнения, а затем распределить его по массиву потоков, каждый из которых имеет стек выполнения приблизительно одного и того же времени. Это может быть опасно, хотя некоторые графические объекты, такие как немедленный режим OpenGL, должны поддерживать порядок и в большинстве случаев не должны содержать нити.