Содержание к диссертации
Введение
ГЛАВА 1. Распараллеливащие/оптимизирующие преобразования программ 19
1.1 Об исследованиях распараллеливания программ 20
1.2. Информационная зависимость в программе 29
I .3. Корректность преобразований 35
1.4. Преобразования программ. 38
1.4.1. Перестановка фрагментов 38
1.4.2 Канонизация циклов 40
1.4.3. Раскрутка цикла. 42
1.4.4. Расщепление одномерного цикла, 44
1.4.5. Разрыв итераций, гнездование цикла и подобные им преобразования 46
1.4.6. Развертка цикла 50
1.4.7. Расщепление вершин (Введение временных массивов) 52
1.4.8. Растягивание скаляров (Замена переменной массивом) 53
1.4.9. Разбиение цикла 54
1.4.10. Слияние циклов 56
1.4.11. Приведение цикла к разбиваемому виду , 58
1.5. Преобразования индексных переменных в многомерных циклах 66
1.5.1. Информационная зависимость в многомерных циклах 67
1.5.2. Расщепление многомерных циклов 70
1.5.3. Подстановка вперед 72
1.5.4. Подстановка 76
1.5.5. Переименование переменных 80
Выводы к первой главе 93
ГЛАВА 2. Распараллеливание рекуррентных циклов 94
2.1. Циклы с рекуррентно вычисляемыми переменными 96
2.2. Распараллеливание линейных рекуррентных циклов и решение слау с треугольными ленточными матрицами 100
2.3. Циклы с нелинейной рекуррентной зависимостью 106
2.4. Постоянные линейные рекуррентные зависимости 109
2.5. Принцип сдваивания для вычисления рекуррентных циклов 116
2.6. Параллельное вычисление рекуррентных циклов с опережающим вычислением коэффициентов 125
2.7. Распараллеливание рекуррентных циклов с условными операторами 133
2.7.1. Частично рекуррентные циклы с условными операторами 134
2.7.2. Вычисление суперпозиции условных операторов 138
2.7.3. Обобщение вычисления минимального элемента массива 142
Выводы ко второй главе 149
ГЛАВА 3. Влияние пересылок данных на эффективность параллельных вычислений 150
3.1. Об оптимальном количестве процессоров при параллельном вычислении программных циклов 150
3.1.1. Устройства для обменов данными 151
3.1.2. Размещение массивов ,..„ 154
3.1.3. Рекуррентное вычисление массивов данных 155
3.1.4. Вычисление циклов при горизонтальном размещении данных 157
3.1.5. Вычисление скалярных переменных . 159
3.1.6. Остальные циклы и программы 161
3.1.7. Возможность вычислений без пересылок данных при параллельном решении матричных задач 163
3.2. Оптимальные параллельные переразмещения многомерных массивов 168
3.2.1. Пересылки данных .172
3.2.2. Вспомогательные теоретико-числовые результаты 174
3.2.3. Преобразования циклов 177
3.2.4. Преобразования массива на суперкомпьютере с универсальным коммутатором 179
3.2.5. Преобразования массива на суперкомпьютере с кольцевой сетью... 181
Выводы к третьей главе 185
ГЛАВА 4. Распараллеливание программ для суперкомпьютеров с архитектурой перестраиваемого конвейера 187
4.1. Автоматическая синхронизация конвейера при распараллеливании циклов 190
4.1.1. Граф вычислений программы 190
4.1.2. Граф вычислений и информационные зависимости 192
4.1.3. Отображение цикла на архитектуру компьютера 198
4.1.4. Синхронизация конвейера 199
4.2. Отображение программных циклов на перестраиваемый конвейер 208
4.2.1. Предварительные преобразования перед конвейеризацией 208
4.2.2. Разбиение программы на кадры 215
4.2.3. Двумерная конвейеризация , , 217
4.2.4. Распараллеливание рекуррентных циклов для суперкомпьютера со структурно-процедурной реализацией вычислений 223
4.3. Бесконфликтные размещения массивов для суперкомпьютеров со структурно-процедурной организацией вычислений 229
4.3.1. Определения, обозначения и постановка задачи 230
4.3.2. Размещение массивов для оптимального выполнения циклов 234
4.3.3. Размещение массивов для оптимального выполнения развертки цикла 239
4.3.4. Размещение массивов в пересекающихся множествах сегментов памяти.. 242
4.3.5. Расширение класса индексных выражений 245
4.3.6. Основной алгоритм размещения данных ..248
4.3.7. Улучшения разбиения множества массивов 250
4.3.8. Вычисление множества бесконфликтных размещений массива с самим собой , 252
4.3.9. Совместные бесконфликтные размещения двух массивов 255
4.3.10. Совместные бесконфликтные размещения нескольких массивов 256
Выводы к четвертой главе 259
ГЛАВА 5. Открытая распараллеливающая система 261
5.1 Структура открытой распараллеливающей системы 262
5.1.1. Библиотека преобразований программ 264
5.1.2. Архитектурно ориентированные комбинации преобразований 267
5.1.3. Внутреннее представление 275
5.1.4. Анализ информационных зависимостей .277
5.1.5. Размещение данных и разбивка программы 280
5.1.6. Канонический вид операторов и выражений 280
5.2 Другие элементы и особенности системы 2s3
5.2Л. Отладка и тестирование модулей системы 283
5.2.2. Метол проб и ошибок при автоматическом распараллеливании 284
5.2.3. Программная реализация 290
5.2.4. Полуавтоматическое распараллеливание 292
5.2.5. Обучающая программа на основе ОРС 296
5.2.6. Сравнение ОРС с системой POLARIS 297
5.2.7. Дополнительные возможности ОРС 299
Выводы к пятой главе 304
Заключение 306
Список литературы
- Корректность преобразований
- Циклы с нелинейной рекуррентной зависимостью
- Рекуррентное вычисление массивов данных
- Отображение цикла на архитектуру компьютера
Введение к работе
С каждым годом все большую роль в прогрессе общества играют суперкомпьютеры. Высокопроизводительные вычисления давно используются многими важными отраслями хозяйства [25]. Создание самолетов, автомобилей, ядерных энергетических систем, исследование семантики ДНК, прогноз погоды и изменений климата, проведение вычислительных экспериментов вместо опасных или дорогих натурных экспериментов невозможно без применения суперЭВМ. Такие вычисления обеспечивают получение возможности успешнее участвовать в конкуренции, быстрее организовать производственные циклы, раньше выйти на рынок. Область применения суперкомпьютеров постоянно пополняется задачами криптографии, гидроакустики, радиолокации, моделирования зрения и слуха, распознавания образов, экономического планирования, задачами математической физики и связанными с ними вычислительными экспериментами, расчетами оптимальных конструкций и математическим моделированием сложных систем. Проблемы обороны, промышленности и науки пополняют список приложений суперЭВМ каждый год. Применяются параллельные вычисления и в задачах целочисленной оптимизации [132]. Многие фундаментальные математические исследования в области многомерных интегральных уравнений остаются на уровне разработки методов и не доводятся до численного решения ввиду большого объема вычислений. Автору данной диссертации это знакомо в связи с работами [147] - [155], в частности, в [149, с. 286] решена проблема, поставленная математиками из ФРГ на международной конференции по приложениям чистой математики к механике (Meister Е., Speck F.-O. Some multi-dimensional Winner-Hopf equations with applications of Pure Mathematics to Mechanics, Kozbunik, Poland, 12-17 September, 1977 - препринт). Мировая гонка в повышении производительности суперкомпьютеров отражается в Интернете на сайте top500 [210]. И наряду с развитием передовых по производительности вычислений суперкомпьютеров в различных университетах и НИИ исследователи для повышения быстродействия используют параллельные вычисления на кластерах имеющихся в их распоряжении локальных сетей. Современные технологии производства приводят к использованию принципов параллельных вычислений на однокристальных процессорах.
Повышение быстроты вычислений приводит к необходимости использования параллельной памяти, чтобы обращаться ко многим данным одновременно. Но наличие параллельной памяти создает проблемы для программирования. Возникают задачи размещения данных, переразмещения данных во время исполнения программы, минимизации количества пересылок.
Параллельная память (много модулей памяти) позволяет считывать одновременно много данных - по одному из каждого модуля памяти. Наиболее просто эта возможность реализуется в суперкомпьютерах с распределенной памятью. Такими являются кластерные системы, n-Cube, Connection Machine, мультитранспьютерные системы, отечественные суперкомпьютеры МВС-і 000 и МВС 100, распространенная в свое время в нашей стране система ПС-2000 и многие другие. Но в таких компьютерах получение процессором данных из модуля памяти другого процессора (межпроцессорная пересылка) оказывается очень длительной операцией.
По-другому организован доступ к параллельной памяти у суперкомпьютеров со структурно процедурной организацией вычислений. Такие компьютеры разрабатываются в НИИ МВС при ТРТУ в г. Таганроге на основе идей академика РАН А.В. Каляева. У суперкомпьютеров такого типа время доступа каждого процессора к любому модулю памяти одинаково. При этом каждый процессор может одновременно получить два аргумента для бинарной операции. А сами процессоры с помощью коммутатора могут соединяться в конвейер в соответствии с любым графом вычислений. Для задач слабо связанных» то есть таких, которые разбиваются на семейства самостоятельных подзадач, не предполагающих частые обмены данными, суперкомпьютеры с распределенной памятью достаточно эффективны. Суперкомпьютеры со структурно-процедурной организацией вычислений способны решать и широкий класс регулярных сильно связанных задач. Но и в том и в другом случае разработка программного обеспечения оказывается очень дорогой.
Следует отметить относительность понятия «суперкомпьютер», поскольку многие идеи параллельных вычислений сегодня закладываются в однокристальные микропроцессоры. Процессоры компании Intel Pentium4 и Itanium используют технологию Hyper Treading, компания AMD готовит к выпуску двуядерный процессор, и дальнейшую перспективу увеличения производительности эти компании видят не в увеличении частоты, а в использовании параллелизма. ПЛИСы при соответствующей запрограммированности, могут работать, как несколько процессоров.
Распараллеливание можно разделить на ручное (человек пишет параллельную программу) и автоматическое (компилятор преобразуют последовательную программу в параллельную). Оба подхода сосуществуют в течение многих лет, обогащая друг друга. С одной стороны, приемы автоматического распараллеливания можно использовать при ручном распараллеливании. С другой стороны, многие приемы ручного распараллеливания могут быть заложены в распараллеливающий компилятор.
В многочисленных статьях приводятся методы автоматического распараллеливания на суперкомпьютеры с общей памятью: скалярных, векторных, VLIW, SMP архитектур. Для таких компьютеров разрабатываются и эффективные распараллеливающие компиляторы, например, компиляторы Intel для Pentium4 Hyper Threading и Itanium2 или распараллеливающие компиляторы для SMP компьютеров на основе системы POLARIS. Для суперкомпьютеров с распределенной памятью либо предлагаются методы ручного распараллеливания, либо системы с частично автоматическим распараллеливанием. Нет методов автоматического распараллеливания на суперкомпьютеры с параллельной, но не распределенной, памятью, такой, как у суперкомпьютера RP-3 [173] или суперкомпьютеров со структурно-процедурной организацией вычислений [71].
Для компьютеров с параллельной памятью на сегодняшний день теория автоматического распараллеливания развита недостаточно, систем с эффективной автоматизацией распараллеливания нет.
Из всего выше сказанного вытекает важная проблема, состоящая в разработке новых методов автоматического распараллеливания программ для различных суперкомпьютеров, в том числе и с параллельной памятью, которые могли бы повысить эффективность использования параллельных компьютеров, понизить требования к квалификации программистов, уменьшить время разработки, повысить надежность и удешевить параллельное программное обеспечение.
Корректность преобразований
При преобразованиях программ следует контролировать сохранение синтаксической и семантической корректности. Например, если в фортра-новской программе поменять местами заголовок цикла и последний оператор тела цикла, то результирующая программ будет содержать нарушения синтаксиса языка. Если скопировать фрагмент программы, содержащий оператор с меткой, то в результирующем фрагменте получится два оператора с одинаковой меткой, что нарушает семантическую корректность.
Для отслеживания такой корректности часто используется управляющий граф программы [53], [69], [70].
В программе от оператора 1 к оператору 2 передается управление, если при некотором исполнении программы в некоторый момент исполнения за исполнением оператора 1 следует исполнение оператора 2.
Управляющий граф программы — это граф, вершинами которого являются исполнимые операторы программы, а дуги - передачи управления.
Используются понятия ВХОД и ВЫХОД фрагмента программы. Под этими понятиями понимаются передачи управления. При конкатенации операторов управление передается от предыдущего оператора к последующему. Условный оператор и оператор цикла имеют по две передачи управления.
В следующем примере у фрагмента, состоящего из одного оператора 999, по крайней мере, два входа: Пример 7, IFBOOLEXPRTHEN А = 1 999 X = Определим понятие фрагмента программы, как такой части программы, над которой проводятся преобразования. Это понятие интуитивно используется практически во всех источниках по преобразованиям программ. В данной работе программа понимается, как некоторая программа на одном из трех языков ФОРТРАН, ПАСКАЛЬ и С, причем в очень узкой их части. Допускаются оператор присваивания, цикла, условный if, безусловный переход, операторные скобки и пустой оператор. Все преобразования рассматриваются в рамках одной процедуры. Исполнимая часть программы выглядит, как последовательность операторов, т.е. у каждого оператора можно мыслить свой порядковый номер. Фрагмент программы — часть этой последовательности операторов с подряд идущими номерами, обладающая следующим свойством: если эту часть операторов заключить в операторные скобки, то полученная программа будет эквивалентна исходной. Такое определение не допускает, чтобы фрагмент, например, содержал заголовок цикла, а последний оператор тела цикла не содержал. В этом смысле программный цикл от заголовка до последнего оператора тела цикла всегда является фрагментом. Несмотря на это определение, иногда будем писать о возможности заключения фрагмента в скобки.
Иногда перед выполнением преобразования рассматриваемый фрагмент необходимо заключать в операторные скоби. В работе [180] преобразуемые циклы приводятся к такому виду, в котором перед заголовком и после тела ставятся пустые операторы с метками, которые перехватывают передачи управления рассматриваемого цикла.
Иногда будет использоваться понятие линейного участка программы. Это такой фрагмент, который состоит только из операторов присваивания и пустых операторов, который имеет единственный вход и единственный выход. Управляющий граф линейного участка - простой путь («линия»).
Отметим, что управляющий граф и граф информационных связей могут быть не достаточны для контроля над корректностью и эквивалентностью преобразований. Рассмотрим следующий пример. Пример 8. 1 GOTO 2 2 Х=1 3 Y = 2 4 Z = 3
В этом примере все операторы информационно независимы. Управление передается от каждого предыдущего оператора к последующему. Но операторы 3 и 4 можно менять местами, а операторы 1 и 2 - нельзя. Заметим, что перестановка операторов 1 и 2 приводит к программе синтаксически и семантически корректной, но не эквивалентной исходной. По этой причине иногда приходиться оговаривать, какие именно операторы входят в рассматриваемый фрагмент.
Строгое определение корректности преобразования программ обсуждается в [54]. В данной работе исследуются эквивалентность или эффективность рассматриваемых преобразований программ. Корректность преобразований если не оговаривается, то подразумевается.
В генераторах компиляторов алгоритмы разбора текста рассчитаны на целый класс языков программирования. Хотелось бы иметь и языково-независимую библиотеку преобразований. Но преобразования программ связаны не только с синтаксисом языка, который может быть описан формами Бэкуса-Наура, но и зависят от трудно формализуемой семантики. Поэтому пока преобразования программ автоматически не генерируются.
Большинство публикаций по распараллеливающим преобразованиям программ ориентированы на ФОРТРАН. Это оправдано тем, что в ФОР-ТРАНе данные хранятся в виде массивов, к элементам которых можно об ращаться независимо, а единственный оператор цикла имеет счетчик распараллеливание такого цикла часто выглядит, как одновременное выполнение различных итераций (пронумерованных счетчиком). Поэтому и в данной работе рассматриваются фрагменты программ языка ФОРТРАН, хотя можно рассматривать и такие фрагменты на языках ПАСКАЛЬ и С, в которых данные представлены массивами, а циклы имеют счетчик (может быть и не явно, но распознаваемо).
Следует отметить, что, поскольку преобразования программ проводятся, как правило, в некотором древовидном внутреннем представлении, а не в исходном высокоуровневом языке, многие проверки корректности отпадают сами собой. Например, нет необходимости заключать в операторные скобки часть программы, образующую ветку на дереве. Не нужны скобки и для определения приоритета операций.
Циклы с нелинейной рекуррентной зависимостью
В некоторых частных случаях вычисление рекуррентных циклов может быть ускорено. Особенно часто встречающийся на практике случай -цикл с линейной рекуррентной зависимостью, в котором вхождения ре-куррентно вычисляемой переменной имеют постоянные (не зависящие от счетчика цикла) множители. Такой цикл можно заменить циклом без ре куррентных зависимостей, все итерации которого могут выполняться одновременно.
Пример 60. Вычисление суммы N элементов массива А. D099I = 1,N 99 Х(К) = Х(К)+А(1)
Пример 61. Вычисление N частичных сумм N элементов массива А. Эта задача, как уже упоминалось раньше, сводится к решению системы уравнений с двухдиагональной матрицей. DO 99 I = 1, N 99 X(I) = Х(1-1)+А(1) Пример 62. DO 99 I = 2, N 99 X(I) = X(I-1)+A
Вычисление сумм элементов арифметической прогрессии с разностью А. Такой цикл равносилен следующему не рекуррентному циклу, все итерации которого можно выполнять одновременно D099I = 2,N 99 X(I) = Х(1)+А (1-1)
В частном случае, когда А= 1, такое преобразование рассматривалось в [202]. Пример 63. D099I = 1,N 99 X(I) = Х(І-1)+А(0)+А(1) І+А(2) Г2+....+ А(к) Ілк этот цикл вьиисляет сумму элементов последовательности, общий член которой определяется многочленом k-ой степени. Такая сумма выражается многочленом (к+1)-ой степени, коэффициенты которого можно вычислять методом неопределенных коэффициентов. Но можно заранее завести массив заготовок для небольших степеней к S(N,k) = 1лк+2лк+Злк+...+Ылк
Тогда исходный цикл будет равносилен следующему не рекуррентному DO 99 I - 1, N 99 X(I) = X(l)+A(0) S(I,0)+A(l)!,!S(I,l)+A(2) S(I,2)+....+ A(k) S(I,k) Вот такая таблица для начальных значений k = 0,1, 2,3. S(N,0) = N S(N,1) = N (N-l)/2 S(N,2) = (2 N 3+3 NA2+N)/6 S(N,3) = (N (N-1)/2)A2 Рассмотрим следующий рекуррентный цикл D099I = 1,N 99 X(I) = a X(I-l) + b
Несложно проверить методом математической индукции, что этот цикл эквивалентен следующему циклу без рекуррентной зависимости DO 99 к =1, N Т = аЛк 99 Х(к) = Т Х(0) + Ь (Т - 1)/(а-1) Пример 64. Рекуррентный цикл DO 99 I = 1, N 99 Х(1) = 3 Х(Ы)-2 равносилен не рекуррентному циклу DO 99 I = 1, N 99 Х(І) = 3ЛІ Х(0)-3ЛІ + 1 Рассмотрим цикл с линейной рекуррентной зависимостью и постоянными коэффициентами при вхождениях вычисляемого массива. D0 99I = k+l,N 99 X(I) = A(l) X(I-1)+A(2) X(I-2)+....+ А(к) Х(1-к)
Пусть характеристическое уравнение A(l) ХА(к-1)+А(2) ХЛ(к-2)+.,.,+ А(к) = Хлк Обладает различными корнями XI, Х2, ..., Хк. Тогда рассматриваемый цикл эквивалентен следующему не рекуррентному циклу D0 99I = k+l,N 99 Х(1) = В(1) ХП+В(2) X2AI+..„+ В(к) ХкЛ Числа В(1), В(2),..., В(к) вычисляются методом неопределенных коэффициентов, опираясь на начальные значения массива Х(1), Х(2),..., Х(к). Более точно, коэффициенты B(l), В(2),..., В(к) вычисляются из следующей системы уравнений Х(0) = В(1)+В(2)-К...+ В(к) Х(1) = В(1) Х1+В(2) Х2+....+ В(к) Хк Х(2) = В(1) ХГ2+В(2) Х2Л2+....+В(к) ХкЛ2 Х(к-1) = В(1) Х1л(к-1)+В(2) Х2л(к-1)+....+В(к) Хкл(к-1)
Следует отметить, что корни характеристического уравнения XI, Х2, ..., Хк могут оказаться дробными, иррациональными и даже комплексными, но, если начальные значения массива X и коэффициенты В(1), В(2),..., В(к) были целыми, то в результате работы преобразованного цикла значения массива X всегда будут получаться целые. Более подробно об этом и о случае кратных корней характеристического уравнения можно найти информацию, например, в [46], [103].
Целесообразность замены рассматриваемых рекуррентных циклов циклами без рекуррентности надо проверять для каждой конкретной вычислительной системы отдельно. С одной стороны, возведение в степень — длительная операция. Но с другой стороны, если вычисляемый массив X размещается в распределенной памяти так, что элемент Х(1) должен быть в модуле памяти с номером Г mod р , то выполнение: исходного рекуррентного цикла потребует пересылки данных (тоже длительные операции), а результирующий цикл, не содержащий рекуррентностей, может быть выполнен без пересылок.
Рекуррентное вычисление массивов данных
Размещением m-мерного массива Xfl..Nl;l..N2;...;l..Nm] будем называть функцию, которая каждому набору индексов 1=(11,12,.,.,Im), (l Il Nl,...,l Im Nm) ставит в соответствие номер сектора памяти, в котором должен находится элемент массива X(Il,„.,Im). Размещение данных в отличие от распределения данных не указывает, в какую именно ячейку сектора памяти попадает данный элемент массива.
Размещение массива A[l..Nl;l..N2;.„;l..Nm] будем называть вертикальным тогда и только тогда, когда для любого I=(Il,I2,..Im), (l Il Nl,...,l Im Nm) элемент массива A[Il,I2,..Im] находится в секторе памяти с номером ]Il/]Nl/p[[. Далее, если особо не оговорено, будем иметь дело с вертикально размещенными массивами.
Пример 79. Возьмем массив X из предыдущего определения со следующими значениями параметров: р=4, т=2, N1=10, N2=2. Тогда размещение элементов этого массива будет иметь следующий вид: номер ПЭ 12 3 4 Х(1Д) Х(4Д) Х(7Д) Х(ЮД) список Х(2,1) Х(5Д) Х(8Д) Х(ЗД) Х(6Д) Х(9,1) элементов Х(1,2) Х(4,2) Х(7,2) Х(10,2) Х(2,2) Х(5,2) Х(8,2) Х(3,2) Х(6,2) Х(9,2) Размещение массива - А[ 1. .N1; 1. .N2;...; 1. .Nm] будем: называть горизонтальным тогда и только тогда, когда для любого I=(H,I2,..Im), (l Il Nl,...,l Im Nm) элемент массива A[Il,I2,..Im] находится в секторе памяти с номером II mod р.
Пример 80. Возьмем массив X из предыдущего примера с теми же значениями параметров: р=4, т=2, N1=10, N2=2. Тогда размещение элементов этого массива будет иметь следующий вид: номер ПЭ 12 3 4 Х(1Д) Х(2Д) Х(ЗД) Х(4Д) список Х(5Д) Х(6Д) Х(7Д) Х(8Д) Х(9Д) Х(ЮД) элементов Х(1,2) Х(2,2) Х(3,2) Х(4,2) Х(5,2) Х(6,2) Х(7,2) Х(8,2) Х(9,2) Х(10,2)
Такие способы размещения массивов рассматривались, например, в [204]. В [126] кроме этих способов допускаются еще диагональное и антидиагональное (скошенное [113]) размещение. Значительно более широкое множество способов размещения данных описано в [106]. В данной главе ограничимся рассмотрением горизонтального и вертикального размещений, поскольку здесь рассматриваются лишь одномерные циклы.
В этом параграфе для краткости время вычисления суперпозиции двух отображений будем обозначать Тсуперпюнции Та, а, время вычисления отображения от аргумента Тфун1тии.= То.
Вернемся к рассмотрению рекуррентного цикла (18). Для вычисления этого цикла воспользуемся следующим алгоритмом, предполагающим вертикальное размещение массивов:
1. В каждом ПЭ с номером к вычисляем ]N/p[ следующих суперпозиций Ни = Gk ]№P[.i+i o.,.oGtk-i) jN/p[+i Это потребует QN/p[-l) Та. времени.
2. Пользуясь принципом сдваивания [40, с.34], вычисляем все суперпозиции W, = Нц W2 =Н21оНп Wk = Hti 0...0Н21 оНп Wn = Hni о... оН21 оНп
Это потребует log2p шагов, на каждом из которых вычисляется одна операция суперпозиции и одна межпроцессорная пересылка отображения Hki. Для универсальных коммутаторов и гиперкуба здесь понадобится log2p ( Та.+Т0) тактов, а для m-мерной решетки - log2p (Ta.+Tl)+T2 k ( "tfp 1) тактов (в частности, для кольцевой коммутационной сети - Iog2p ( Та.+Т1)+Т2 (р-1) ).
3. Одновременно за 1 шаг в каждом ПЭ с номером к вычисляем Wk(X(0)). Это отнимет ТЬ времени.
4. Одновременно за ]N/p[ шагов в каждом ПЭ с номером к вычисляем значения Gj(Wk(X(0))) для всех индексов Ї, для которых G находится в этом ПЭ. Это требует ]N/p[ Tb времени.
5. Конец.
Итак, для МВС с универсальным коммутатором или с архитектурой гиперкуба время работы оценивается величиной F(P) = QN/p[ - l) Ta+Iog (p) (Ta+T0)+(]N/p[+l) Tb.= ]N/p[ (Ta+Tb)+log (p) (Ta+T0)+(Tba), оптимальное количество ПЭ равно р = N (Ta+Tb) ln2/(Ta+T0), минимальное время работы равно (Та+Т0) 1Дп2+1п((Та+ТЬ) 1п2/(Та+Т0))+ТЬ-Та. Для MB С с m-мерной решеткой время работы оценивается величиной F(P) = (]N/p[-l) Ta+log (p) (Ta+Tl)+m ( p -1) T2+(]N/p[+l) Tb = ]N/p[ (Ta+Tb)+log (p) (Ta+Tl)+m ( mfc - l) T2+(Tba), оптимальное количество ПЭ вычисляется из уравнения р1+1/т Т2 + р (Та+Т1)Лп(2) - N (Ta+Tb).« О . Это уравнение подстановкой у = р 1/ш сводится к полиномиальному ym+1 N (Ta+Tb) - у (Та+Т1)/1п(2) - Т2 = 0 . В частности, для МВС с кольцевой сетью время оценивается величиной F(p) = ]N/p[ (Ta+Tb)+log (p) (Ta+Tl)+(p-l) T2+(Tba), оптимальное количество ПЭ равно р=(-(Та+Т1)+ V(Ta + ТІ) + 4N (Та + Tb) Т2 In 2 /(2 T2 ln2) - VN TVTT и минимальное время работы равно VN ((Та+ТЬ) VT№ +VT№ )+ln(N) (Ta+Tl)/2+ (Та+Т1)/2 In(Ta/T2)2+Tba.
Отображение цикла на архитектуру компьютера
Свернутым графом цикла будем называть граф вычислений тела цикла, преобразованный циклически независимыми и циклически порожденными out-in и in-in склеиваниями. Заметим, что у свернутого графа из вершины выходит более одной ду ги в двух случаях. В первом случае эта вершина является результатом склейки нескольких вершин, связанных с чтением данных. В другом слу чае, такая вершина является результатом out-in склейки, — одна из выхо дящих дуг связана с записью данных, а остальные с чтением. Для конвейерного выполнения программного цикла следует каждой операции, встречающейся в цикле, сопоставить устройство суперкомпьютера, в котором эта операция будет выполняться. Операциям чтения и записи данных сопоставляется модуль памяти, в котором это данное должно находится.
Все операции тела цикла находятся во взаимно однозначном соответствии с вершинами свернутого графа цикла. Поэтому достаточно построить отображение вершин этого графа во множество элементарных процессоров суперкомпьютера. Ясно, что это отображение должно быть инъективно.
Если результат одной операции используется, как аргумент другой операции, то с помощью коммутатора выход первого процессора должен быть соединен с входом второго. Но все пары операций, в которых результат одной является аргументом для другой, находятся во взаимно однозначном соответствии с дугами свернутого графа. Следовательно, по дугам свернутого графа можно определить задание для коммутатора — какие устройства между собой следует соединять.
Но для правильной работы конвейера недостаточно соединить устройства суперкомпьютера по указанной схеме. Может случиться так, что, двигаясь по такой схеме, разные аргументы какой-то операции придут в соответствующий процессор в разное время, ввиду того, что пути прохождения могут оказаться разной длины. Для решения этой проблемы конвейер следует синхронизировать. Синхронизация выполняется с помощью буферов, которые задерживают данные перед их поступлением в процессор на необходимое время. Рассмотрим алгоритм определения значений буферов для различных случаев с нарастанием их общности и сложности.
Один оператор. Индексы без сдвигов. Пример 95. DO 99 1=3, N Y(I) = X(I) + B(I) X(I) 99 CONTINUE В + у Рис. 11. Склейка с циклически порожденной in-in зависимостью На рисунке 11 один и тот же элемент Х(1) должен поступить в складывающий процессор на один так позже, чем в умножающий.
Добавим к графу дополнительную вершину S, из которой построим дуги в источники исходного графа. Для полученного бесконтурного графа с одним источником можно построить дерево самых длинных путей с корнем S по аналогии с известным деревом кратчайших путей в бесконтурном графе [91].
Алгоритм синхронизации конвейера. 1. По свернутому графу цикла строим дерево самых длинных путей. 2. Каждой вершине графа х ставим в соответствие число f(x) , равное длине пути от описанной выше вершины S до х . 3. Для каждой дуги (у, х) определяем значение буфера, как величину f(x)-f(y)-l. ... ... 4. Для каждой вершины графа х момент начала работы соответст вующего процессора определим величиной f(x).
Несложно убедиться, что в результате определения величин f(x) и значений буферов f(x) — f(y) — 1 , для любых двух вершин время движения по любым путям между этими вершинами (с учетом задержек в буферах) одинаково. Это и означает синхронизацию конвейера, т.е. что в каждый процессор нужные данные будут поступать одновременно. Один оператор. Индексы со сдвигами. Граф без контуров. Пример 96. D0 99I=3,N Y(I) = X(I-2) + B(I) X(I) 99 CONTINUE
Граф для этого примера выглядит таким же образом, как и для предыдущего. В этом случае на дуге (Х,+) перед изначально пустым буфером, построенным в предыдущем пункте, должно быть установлено еще две ячейки буфера с начальными данными Х(1)иХ(2) (рис. 12).
В этом случае с дугами, которые связаны с out-in склейками, поступаем так же, как и с дугами, связанными с in-in склейками. Аналогичным образом на такие дуги могут быть поставлены и ячейки буфера с начальными данными.
Один оператор. Индексы со сдвигами. Одна обратная дуга.
Рассмотрим случай, когда у свернутого графа цикла есть контуры, но удаление одной дуги делает этот граф бесконтурным. Будем считать, что эта дуга соответствует циклически порожденной out-in зависимости, и эту дугу будем называть обратной.
Обозначим рассматриваемую обратную дугу (уо, XQ). Таким образом, данные на какой-то начальной итерации поступают на обработку сначала в элементарный процессор Хо » затем проходят обработку, двигаясь по некоторой цепочке процессоров, после чего, на какой-то из последующих итераций, по дуге (уо, хо) опять приходят в процессор Хо .
Может так случиться, что процессор Хо , выполняющий бинарную операцию, по обратной дуге (уо, хо) получает аргумент после того, как уже пришел другой аргумент этой операции.
