Методы распараллеливания циклов

Методы распараллеливания циклов

This paper deals with ways to find data dependences in nested loops. The algorithms of loop transformations permitting nested loops with loop-carried dependences to be parallelized are presented.

Gespeichert in:
Bibliographische Detailangaben
Datum:2009
Hauptverfasser: Полуян, Ю.А., Чемерис, А.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2009
Schriftenreihe:Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/27079
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Методы распараллеливания циклов / Ю.А. Полуян, А.А. Чемерис // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-27079
record_format dspace
spelling irk-123456789-270792011-09-28T12:39:53Z Методы распараллеливания циклов Полуян, Ю.А. Чемерис, А.А. This paper deals with ways to find data dependences in nested loops. The algorithms of loop transformations permitting nested loops with loop-carried dependences to be parallelized are presented. 2009 Article Методы распараллеливания циклов / Ю.А. Полуян, А.А. Чемерис // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 8 назв. — рос. XXXX-0067 http://dspace.nbuv.gov.ua/handle/123456789/27079 004.4'242 ru Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description This paper deals with ways to find data dependences in nested loops. The algorithms of loop transformations permitting nested loops with loop-carried dependences to be parallelized are presented.
format Article
author Полуян, Ю.А.
Чемерис, А.А.
spellingShingle Полуян, Ю.А.
Чемерис, А.А.
Методы распараллеливания циклов
Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України
author_facet Полуян, Ю.А.
Чемерис, А.А.
author_sort Полуян, Ю.А.
title Методы распараллеливания циклов
title_short Методы распараллеливания циклов
title_full Методы распараллеливания циклов
title_fullStr Методы распараллеливания циклов
title_full_unstemmed Методы распараллеливания циклов
title_sort методы распараллеливания циклов
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate 2009
url http://dspace.nbuv.gov.ua/handle/123456789/27079
citation_txt Методы распараллеливания циклов / Ю.А. Полуян, А.А. Чемерис // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 8 назв. — рос.
series Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України
work_keys_str_mv AT poluânûa metodyrasparallelivaniâciklov
AT čemerisaa metodyrasparallelivaniâciklov
first_indexed 2025-07-02T22:19:52Z
last_indexed 2025-07-02T22:19:52Z
_version_ 1836575403523702784
fulltext УДК 004.4'242 Ю.А.Полуян, НТУУ «КПИ», Киев А.А. Чемерис, к.т.н., ИПМЭ им. Г.Е.Пухова НАНУ, Киев МЕТОДЫ РАСПАРАЛЛЕЛИВАНИЯ ЦИКЛОВ This paper deals with ways to find data dependences in nested loops. The algorithms of loop transformations permitting nested loops with loop-carried dependences to be parallelized are presented. Введение. Существует три основных подхода к обеспечению эффективной эксплуатации суперкомпьютеров, как машин с параллельной архитектурой: использование параллельных языков, использование библиотек и распараллеливание программ. Все три направления интенсивно развиваются, но наиболее привлекательным остается третий подход, поскольку решает проблему переносимости старых последовательных программ на суперкомпьютеры. Ввиду того, что написание «с нуля» сложных вычислительных программ с использованием модели параллельного программирования требует большого количества времени и средств, наиболее оправданным является применение алгоритмов трансформации к уже написанным последовательным программам. Алгоритмы распараллеливания циклов – это весьма важный класс трансформирующих преобразований, так как на выполнение циклических операций уходит большая часть времени выполнения программы. Они особенно привлекательны тем, что их применение не требует знания целевой архитектуры. Эти алгоритмы можно рассматривать как завершающую стадию машинно-независимой части процесса генерации параллельного кода соответствующим компилятором. Трансформация циклов позволяет обнаружить параллелизм и выявить те зависимости, которые ответственны за изначально «последовательное» состояние некоторых операций исходной программы. Данная работа посвящена изучению различных алгоритмов обнаружения параллелизма в гнездах циклов (выявлению зависимостей и методам трансформации программ). Понятие зависимостей и их классификация. Основополагающим понятием в теории параллельного программирования является зависимость между выражениями S1 и S2 [2,4]. В общем случае такая зависимость обозначается 21 SS  (1) По типу возникновения зависимости делятся на зависимости по управлению и зависимости по данным [2]. Зависимость по данным определяется нарушением условия Бернштейна [2,4]: False)O(S)O(S)I(S)O(S)O(S)I(S  ][][][ 212121 (2) где I(S) – набор прочитанных ячеек памяти, O(S) – набор записанных в память ячеек. Зависимости по данным делятся на четыре типа: прямая зависимость, обратная зависимость, зависимость по входу, зависимость по выходу. В [2,4,5] приведено подробное описание этих типов зависимостей. Для циклических участков программ кроме зависимостей в теле цикла существуют межитерационные зависимости. Пусть имеется некоторый вложенный цикл do I1=a1,b1 do I2=a2,b2 do In=an,bn S1 enddo enddo enddo Итерационным вектором i  для некоторого выражения S1 называется набор целых значений, который содержит номера итераций каждого из циклов в порядке их вложенности },...,,{ 21 niiii   [1,2]. Если выполнение выражения S1 на некоторой итерации i  предшествует выполнению выражения S2 на итерации j  , то говорят, что итерация i  предшествует итерации j  и обозначают ji   [2]. Если существуют два итерационных вектора i  и j  , связанных с выполнением S1 и S2 соответственно, таких что 1) ji   или ji   и существует выполнимый путь от выражения S1 к S2; 2) выражения S1 и S2 осуществляют операции доступа к памяти, и хотя бы одна из этих операций является записью, то говорят о циклической зависимости от S1 к S2 [2,4]. Если такая циклическая зависимость существует, дистанционный вектор ),( jid [6] длины n для данной зависимости определяется выражением (3): ,),( kikjkjid  (3) а вектор направления зависимости D(I,j) – выражением (4) [6].          0),(,"" 0),(,"" 0),(,"" ),( k k k k jid jid jid jiD (4) Методы исследования циклов на наличие зависимостей. Если два выражения S1 и S2 в теле некоторого цикла L не используют индексных переменных цикла, то если между этими выражениями существует зависимость, то это будет зависимость с нулевыми индексными переменными [2]. Для данного типа зависимостей, никаких дополнительных тестов не производится, проверяется только возможность доступа к одной ячейке памяти и на основании этого делается заключение о наличии зависимости. Выражения, использующие только одну индексную переменную, разделяются на строгие и нестрогие зависимости [2]. Для строгих зависимостей типа  21; ciacai дистанционный вектор будет равен ii a ccd    21 . Зависимость может существовать только при условии, что d – целое число, модуль которого лежит внутри границ цикла, то есть: LUd  , где U и L - соответственно верхняя и нижняя границы цикла. На рис. 1 и 2 изображено пространство итераций, где ось i представляет собой счетчик в цикле, f(i) и g(i) определяют индексы переменных в выражениях в теле цикла, у – значения этих индексов внутри цикла на некоторой определенной итерации, d – дистанционный вектор. Рис. 1 иллюстрирует строгие зависимости и позволяет графически отыскать значение дистанционного вектора. Рис. 1 – Графическая интерпретация строгого теста Нестрогий тест производится для зависимостей типа  2211 ; ciacia . Наличие зависимости возможно, если функции 11)( ciaif  и 22)( ciaig  пересекаются на целочисленной сетке в пределах границ цикла. Графическая интерпретация представлена на рис. 2. Если функции f(i) и g(i) пересекаются при целых и не выходящих за границы цикла i и y, то зависимость существует. Пусть есть некоторый вложенный цикл L с индексами },...,,{ 21 niiii   и пусть ))(( ifX  и ))(( igX  определяют две переменные в теле цикла, где f и g – функции индексов. Оба выражения будут осуществлять доступ к одной и той же ячейке памяти, если y f(i) g(i) d -c1/a1 -c2/a2 i )()( jgif   . (5) Предположим, что f – линейная функция aAiif  )( , где А и a  - константная матрица и константный вектор соответственно. Тогда уравнение (5) можно записать в виде: iA a jB b     . (6) Уравнение (6) представляет собой систему Диофантовых уравнений, то есть уравнений, решения которых должны быть целочисленными. Рис. 2 – Графическая интерпретация нестрогого теста Для решения такого рода уравнений существует множество различных способов, а также готовых программных продуктов, таких, например, как Mathematica. Классические способы трансформации циклов. Основные методы трансформации циклов представлены в [4]. К ним относят, как правило, следующие методы. 1. Вынос переменной за границы цикла. Суть трансформации иллюстрирует пример. p=10 for(i=0;i<10;++i){ y[i] = x[i] + x[p]; p = i; } a)До трансформации y[1] = x[1] + x[10]; for(i=1;i<10;++i){ y[i] = x[i] + x[i-1]; } p=10; б)После трансформации Рис. 3. Пример выноса переменной за границы цикла Несложно заметить, что только на первой итерации p = 10, на всех остальных итерациях p = i – 1. Вынесем переменную р за тело цикла 2. Раскрутка цикла (увеличение шага итерации). Целью данной трансформации является увеличение скорости работы за счет уменьшения количества циклических операций. При параллельном выполнении «раскрученного цикла» увеличение скорости поясняется y f(i) g(i) -c1/a1 -c2/a2 i уменьшением операций пересылки данных между процессорами. Недостатком этого метода является увеличение громоздкости кода. 3. Объединение циклов. Если два цикла выполняются в одних и тех же пределах индексных переменных, и нет ограничений, обусловленных зависимостями между выражениями в теле этих циклов, целесообразно объединить циклы в один. 4. Разделение циклов Данный метод является противоположным к объединению циклов, рассмотренному выше. Здесь стоит заметить, что целесообразность методов разделения–объединения необходимо проверять опытным путем, замеряя время, необходимое на выполнение исходного и преобразованного циклов. 5. Реверсия индексных переменных Данный метод позволяет избавиться от порождаемых циклических зависимостей. 6. Выравнивание циклов Также позволяет избавиться от порождаемых циклических зависимостей. 7. Унимодулярные трансформации Более подробно рассмотрим унимодулярную трансформацию, которая суть взаимно однозначное соответствие между двумя итерационными векторами i  и i   одинаковой размерности, определяемая выражением iMi   , (7) где М – унимодулярная матрица, то есть матрица М квадратная, а ее определитель равен  1 [6]. Необходимость использования унимодулярных матриц состоит в том, что, переходя к новым индексным переменным в цикле, мы получаем целочисленный вектор тогда, когда исходный вектор индексных переменных целочисленный, и — наоборот. Преобразованный цикл будет состоять из тех же экземпляров операторов, но экземпляры в новом цикле будут исполняться в порядке возрастания новых индексных переменных. В случае с целочисленными матрицами операции сложения, вычитания, умножения, скалярного умножения на целое число и транспонирования всегда приводят к целочисленной матрице. Однако вычисление обратной матрицы не всегда приводит к целочисленной матрице. Важным же свойством унимодулярной матрицы является то, что обратная к ней матрица — также целочисленная и унимодулярная. Если имеются два итерационных вектора 1i  и 2i  такие, что      , , 21 21 ii ii   то унимодулярные трансформации ,11 iMi   ,22 iMi   должны быть такими, чтобы 21 ii   . Это требование обусловлено тем, что корректность трансформации (7) возможна, только если преобразованный вектор зависимости 0d  [2]. Если взять в качестве элементарной матрицы единичную матрицу, также являющуюся унимодулярной, то можно получить элементарные матрицы унимодулярных преобразований. Существуют следующие классы унимодулярных матриц размерностью 2×2, которые непосредственно используются в преобразованиях [6]:             10 01 10 01 и - реверсивные матрицы;       01 10 - перестановочная матрица;             1 01 10 1 p и p - множество соответственно верхних и нижних скашивающих матриц, где р – фактор искажения. Унимодулярная матрица может быть выражена как произведение обращающей, перестановочной и верхней скашивающий матриц. Пусть, например, имеется некоторый цикл do i=1,n do j=1,n … enddo enddo Применим унимодулярное преобразование с помощью нижней скашивающей матрицы: .,, 01 11 ijjii j i j i                     . Так как ,,1 nji  то nji 2,2  . Тогда трансформированный цикл будет выглядеть следующим образом: do i’=2,2n do j’=max(1,i-n),min(n,i-1) … еnddo enddo Алгоритмы распараллеливания программ. В этом разделе упомянуты некоторые алгоритмы распараллеливания программ, которые используются в современных компиляторах. 1. Алгоритм Аллена—Кеннеди Алгоритм Аллена—Кеннеди [4] был первоначально разработан для векторизации циклов. Затем он был расширен с тем, чтобы максимизировать количество параллельных циклов и минимизировать количество синхронизаций в преобразованном коде. Алгоритм принимает на входе сокращенный уровневый граф зависимостей (СУГЗ). Алгоритм базируется на следующих фактах. 1. Цикл является параллельным, если он не содержит циклически порождаемых зависимостей. 2. Все итерации оператора S1 могут быть осуществлены перед любой итерацией оператора S2, если в СУГЗ не существует зависимости из S2 в S1. Извлечение параллелизма производится посредством разделения циклов. Для каждого оператора исходного кода алгоритм Аллена—Кеннеди обнаруживает столько объемлющих параллельных циклов, сколько вообще возможно. Более точно, рассмотрим оператор S исходного кода, и пусть Li — один из объемлющих циклов. Тогда Li будет помечен как параллельный только в том случае, когда не существует зависимости на уровне i между двумя экземплярами S. Однако этот результат показывает только то, что алгоритм Аллена—Кеннеди является оптимальным среди тех распараллеливающих алгоритмов, которые рассматривают в преобразованном коде экземпляры S в точно тех же циклах, что и в исходном коде. 2. Алгоритм Вольфа—Лэма Вольф и Лэм [7] предложили алгоритм, использующий в качестве входа векторы направления. Их работа объединяет все предыдущие алгоритмы, основанные на операциях с элементарными матрицами, такие как выравнивание цикла, перестановка циклов, обращение цикла, в единую структуру: структуру допустимых унимодулярных преобразований. Алгоритм Вольфа—Лэма строит максимальное множество самых внешних полностью переставляемых циклов. Затем он рекурсивно просматривает оставшиеся размерности и зависимости, не задействованные этими циклами. Версия, представленная в [6], строит множество циклов с помощью анализа более простых случаев, полагаясь на эвристики для гнезд циклов с глубиной 6 и более. 3. Алгоритм Дарте—Вивьена В этом разделе рассматривается третий распараллеливающий алгоритм, который принимает на входе многогранные сокращенные графы зависимостей. В [6] рассмотрены два распараллеливающих алгоритма, которые генерируют на выходе последовательный код для программы, в которой другой алгоритм обнаружит некоторый параллелизм. Это обусловливает необходимость поиска нового алгоритма, объединяющего достоинства алгоритмов Вольфа—Лэма и Аллена—Кеннеди. Чтобы достичь такой цели, можно представить себе комбинацию алгоритмов, которая одновременно использует структуру СУГЗ и структуру векторов направления. Такая стратегия позволяет выявить большее количество параллелизма, комбинируя унимодулярные преобразования и распределение циклов. 4. Алгоритм Фотрие В своей работе Пол Фотрие предложил алгоритм планирования статических управляющих программ с аффинными зависимостями. Этот алгоритм использует точный анализ зависимостей, который всегда является осуществимым для таких типов программ [6]. В этом его отличие от трех ранее рассмотренных алгоритмов (Аллена—Кеннеди, Вольфа—Лэма, Дарте—Вивьена), которые работают с теми или другими аппроксимациями зависимостей. Алгоритм Фотрие принимает на входе сокращенный граф зависимостей G, в котором дуга e: Si → Sj помечена множеством пар (I, J) таких, что Sj(J) зависит от Si(I). Далее он рекурсивно строит многомерный аффинный план для каждого оператора гнезда циклов. Заключение. В статье рассмотрены основополагающие понятия теории параллельного программирования, способы выявления зависимостей и классические методы трансформации циклов. Рассмотрены наиболее распространенные автоматические алгоритмы распараллеливания программ, построенные на базе классических трансформаций. Эти алгоритмы не всегда обеспечивают наилучший уровень параллелизма, более того, применение различных алгоритмов к одному и тому же программному коду может дать совершенно разные результаты. Приведенные в статье классические методы трансформации являются базовой основой для разработки и улучшения распараллеливающих алгоритмов и позволяют разработчику добиться необходимого уровня параллелизма путем изменения отдельно взятых циклов. 1. P.Boulet, A.Darte, G.Silber, F.Vivien. Loop parallelization algorithms: from parallelism extraction to code generation. – France: Research Report №97-17, June 1997. 2. M.Kaufmann. Optimizing compilers for modern architectures. A dependence-based approach. - San Francisco: ISBN, 2001. 3. V.Beletsky, M.Poliwoda. Parallelizing perfectly nested loops with non-uniform dependences. Ninth international multi-conference on Advanced Computer Systems 2002. – Poland: Miedzyzdroje, 2002. 4. J.Allen, K.Kennedy. Automatic translation of Fortran programs to vector form. – USA : ACM, 1987. - P.491-542 5. S.Carr,K.Kennedy. Compiler block ability of numerical algorithms. In Proceedings Supercomputing ’92. - Minneapolis: ACM/IEEE conference on Supercomputing, November 1992. – P.114-125. 6. Касьянов В. Н., Мирзуитова И. Л. Реструктурирующие преобразования: Алгоритмы распараллеливания циклов. В кн.: Программные средства и математические основы информатики.,- Новосибирск: ИСИ СО РАН, 2004 - с.142-188. 7. Wolf M.E., Lam M.S. A loop transformation theory and an algorithm to maximize parallelism. – USA: IEEE Trans. Parallel Distributed Systems, 1991. P.452–471 8. Feautrier P. Dataflow analysis of array and scalar references. – USA: Int. J. Parallel Programming,1991. P. 23–51.

Ähnliche Einträge