Какие промежуточные представления можно использовать для обоснования параллелизма?

12

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

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

  • Решение о том, стоит ли накладные расходы от раскручивания потоков, учитывая степень параллелизма, доступную в коде

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

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


источник
Если вы напишите свой код функционально, вам не придется беспокоиться о состоянии гонки или побочных эффектах.
Роберт Харви
4
Это не совсем отвечает на ваш вопрос, но вас могут заинтересовать исчисления процессов, которые можно использовать для анализа параллельного кода. Самым известным примером может быть исчисление Пи . Однако автоматическое распараллеливание по-прежнему остается в значительной степени нерешенной проблемой, и ее лучше всего решить путем разработки языков, специально предназначенных для предоставления компилятору определенных гарантий, или с помощью специальных аннотаций.
Амон
4
В документе, который служит фоном для Intel Concurrent Collections (CnC), перечислены восемь фундаментальных параллельных шаблонов, таких как Producer-Consumer. Эти параллельные шаблоны, в свою очередь, зависят от ряда свойств, таких как неизменяемость и отсутствие побочных эффектов. (Буду признателен, если кто-нибудь сможет обобщить эту статью и опубликовать здесь ответ.)
rwong
Один из теоретических инструментов называется «Динамическое одиночное назначение (DSA)», построенный поверх SSA.
rwong
@ rwong: можете ли вы предоставить явную ссылку?
Ира Бакстер

Ответы:

5

Можно предположить, что моделирование параллелизма явно в промежуточном представлении (IR) было необходимым требованием. Таким образом, одним из ответов будет «любой IR, используемый для последовательных программ с добавлением некоторых операций параллелизма», например, «fork and join», «параллельный x y». Добавление этих данных позволяет рассуждать о некоторых видах параллелизма, но не обязательно легко. Также не очевидно, как обеспечить определенные свойства (свободу передачи данных), не переходя к полностью функциональному представлению (что затрудняет полезное моделирование параллелизма).

Аргументированные цветные сети Петри (CPN) - хороший выбор для представления программ с параллелизмом. (Токены в CPN являются «цветными» [имеют тип] и могут нести значения; «переходы» в состояния могут выполнять произвольную арифметику с входящими токенами для получения токена разного цвета с вычисленным значением в «месте»). Если вы рассматриваете места как вычисляемые результаты и переходы как операторы моделирования (включая специальный для доступа к памяти), это дает вам то, что представляет собой граф потока данных, с помощью которого можно моделировать программы. Вы можете легко использовать это, чтобы дать формальную интерпретацию классическим представлениям компилятора, таким как тройки [оператор, вход1, вход2, выход].

Существует множество инструментов для анализа таких графиков CPN, в том числе вычислительные свойства, такие как свобода взаимоблокировок, ограниченность числа токенов в местах и ​​т. Д. Heirarchical CPN позволяют моделировать функции и процедуры, а также понятие «вызовов».

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

Ира Бакстер
источник