WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 || 4 |

Такой подход обладает важными достоинствами. Во-первых, по мере увеличения производительности инструментальных ЭВМ можно увеличивать и количество перспективных схем. Во-вторых, прогнозирование времен и других характеристик выполнения программы очень полезно для объяснения программисту, почему выбрана та или иная схема распараллеливания.

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

Отбор схем начинается с отбора вариантов распределения данных.

Отбор перспективных вариантов распределения данных Перспективность того или иного варианта распределения данных определяется эффективностью последующего распределения вычислений (распределения витков циклов между процессорами) и организации коммуникаций.

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

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

Поясним выше сказанное на примере.

Пример распределения данных и вычислений.

DO 1 I = 2, DO 1 J = 2, B(I,J) = A(I,J) D(I)= MAX(D(I), A(I,J)) 1 CONTINUE Рассмотрим для данного примера использование двумерного распределения витков цикла на 4 процессора. Тогда • первый процессор будет выполнять витки по I от 2 до 50 и J от 2 до 50, • второй процессор по I от 2 до 50, а по J от 51 до 99, • третий по I от 51 до 99, а по J от 2 до 50, • четвертый по I от 51 до 99, а по J от 51 до 99.

Для эффективного параллельного выполнения такого цикла все процессоры должны иметь данные, в которые необходимо произвести присваивания, а именно:

• на первом процессоре элементы массива B с индексами по первому измерению от 2 до 50 и по второму измерению от 2 до 50, и элементы массива D с индексами от 2 до 50;

• на втором процессоре элементы массива B с индексами по первому измерению от 2 до 50 и по второму измерению от 51 до 99, и элементы массива D с индексами от 2 до 50;

• на третьем процессоре элементы массива B с индексами по первому измерению от 51 до 99 и по второму измерению от 2 до 50, и элементы массива D с индексами от 51 до 99;

• на четвертом процессоре элементы массива B с индексами по первому измерению от 51 до 99 и по второму измерению от 51 до 99, и элементы массива D с индексами от 51 до 99.

Заметим, что элементы массива D размножены.

Кроме того, для распределения витков цикла между процессорами требуется, чтобы в обращениях к модифицируемым элементам массивов использовались индексные выражения, которые линейно зависят от одной итерационной переменной – параметра цикла. В таком цикле не должно быть также операторов ввода-вывода и операторов выхода из цикла.

При распределении данных и вычислений необходимо минимизировать объем удаленных данных для каждого процессора, пытаясь распределять на каждый процессор все те данные, которые ему нужны для выполнения витков цикла. Для данного примера можно распределить массив A по процессорам так же как и массив В, тогда для каждого процессора не будет удаленных данных.

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

Покажем, что количество всевозможных вариантов распределения данных очень велико. Пусть сумма всех измерений по всем массивам равна Nd, тогда если строить варианты только по правилу, распределять ли очередное измерение или не распределять, то количество вариантов будет 2Nd. При использовании многомерных распределений получается, что для каждого измерения массива нужно указать, на какое измерение процессорной решетки его распределить. Поэтому, если размерность процессорной решетки равна K, то каждое из М измерений массива можно либо не распределять, либо распределить не более чем K способами, поскольку разные измерения одного массива не могут быть распределены на одно измерение процессорной решетки. Общее количество таких вариантов распределения всех массивов можно грубо оценить как (K+1)Nd. Т.е. количество вариантов огромно, и необходимо применение эвристик для его сокращения.

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

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

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

Также при построении групп применяется другая эвристика: не добавлять измерение массива ни в одну группу, если элементы этого измерения не индексируются нигде по переменным цикла. В этом случае распределять такое измерение имеет смысл только для сокращения памяти, а никакого ускорения выполнения программы не будет, поскольку нельзя будет соответствующим образом распределить витки какого-либо цикла. Такая ситуация часто возникает в программах на языке Фортран 77, поскольку там нет другого способа объединить разные физические величины, относящиеся к одной точке пространства, кроме выделения для них специального измерения массива.

Отметим, что эти эвристики приводят к существенному сокращению количества вариантов распределения данных. Например, в тестах NAS (LU, BT и SP) Nd изменяется от 64 до 76. А при объединении в группы, получается 5-групп измерений, что позволяет уменьшить количество вариантов с 376 до при размерности процессорной решетки К=2.

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

Во-первых, два разных измерения одного массива не могут быть отображены на одно и то же измерение процессорной решетки. Такой способ распределения смысла не имеет и поэтому запрещен и в DVM-системе и в других языках, таких как HPF.

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

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

Пример возможных противоречий и способов их разрешения *************Гнездо циклов 1 - циклы 1i и 1j DO 1 I = 2, DO 1 J = 2, B(I,J) = A(I,J) D(I)= MAX(D(I), A(I,J)) 1 CONTINUE ************* Гнездо циклов 2 - циклы 2i и 2j DO 2 I = 2, DO 2 J = 2, A(I,J) = B(I-1,J) 2 CONTINUE ************* Гнездо циклов 3 - циклы 3i и 3j DO 3 I = 2, DO 3 J = 2, D(J)= MAX(D(J), A(I,J)) 3 CONTINUE Цикл 1i требует расположить I-ую строку матрицы A вместе с I-ой строкой матрицы B и вместе с I-ым элементом вектора D. Обозначим эти требования “A(I, )-B(I, )”, “A(I, )-D(I)”, “D(I)-B(I, )”. При этом требование D(I)B(I, ) является “жестким” (имеющим очень большой вес) - если оно не будет выполнено, то цикл должен выполнятся последовательно, поскольку при его параллельном выполнении будет нарушено правило собственных вычислений.

Цикл 1j требует расположить J-ый столбец матрицы A вместе с J-ым столбцом матрицы B. Требований к расположению элементов вектора D от этого цикла нет, поскольку вектор D не индексируется переменной цикла J.

Противоречий в требованиях циклов 1i и 1j нет.

Цикл 2i требует расположить I-ую строку матрицы A вместе с (I-1)-ой строкой матрицы B. Это требование противоречит требованию цикла 1i – нельзя задать два разные взаимные расположения строк двух массивов.

Нарушение этого требования в этом цикле приведет к коммуникациям и пересылке элементов массива В. К такого рода коммуникациям приведет и нарушение требования в цикле 1i. Поэтому победит то взаимное расположение, которое приведет к минимальным затратам для всей программы.

Цикл 2j требует расположить J-ый столбец матрицы А вместе с J-ым столбцом матрицы В. Что не противоречит требованиям циклов 1i, 2i, 1j.

Требований к взаимному расположению элементов вектора D и элементов матрицы А от цикла 3i нет, поскольку вектор D не индексируется по переменной цикла I.

Цикл 3j требует расположить J-ый элемент вектора D вместе с J-ым столбцом матрицы A (обозначим D(J)-A(,J)). Это требование противоречит требованию цикла 1i, поскольку из них вытекает, что должны быть одинаково расположены строки и столбцы матрицы А, что невозможно осуществить. В данном примере три требования вступили в противоречие. Каждое требование имеет вес. Вес требования D(I)-B(I, ) велик, а веса требований A(I, )-B(I, ) и D(J)-A(,J) основаны на затратах на коммуникации. Поэтому будет отброшено скорее всего либо A(I, )-B(I, ), либо D(J)-A(,J). Но возможны случаи, когда коммуникационные издержки в программе слишком велики, и тогда выгоднее пренебречь распараллеливанием циклов. В таком случае будет отброшено требование D(I)-B(I, ).

После разрешения всех противоречий формируются перспективные варианты распределения данных (они отличаются друг от друга тем, что каждая группа связанных измерений либо распределяется по измерению процессорной решетки, либо не распределяется) и строятся соответствующие DVMдирективы, задающие распределение массивов между процессорами.

Распределение вычислений и организация коммуникаций Дальнейшее построение схемы распараллеливания начинается с того, что для каждого варианта распределения данных определяются потенциально параллельные циклы. Такими циклами могут быть циклы без зависимостей по данным, циклы с редукционными зависимостями, зависимостями по приватным переменным и регулярными зависимостями по массиву (для них возможно конвейерное выполнение). Для параллельного цикла в DVM должно соблюдаться правило собственных вычислений. Это правило фактически определяет принятие решения о распараллеливании цикла – все решает распределение модифицируемых в цикле данных (весь виток цикла будет выполняться на том процессоре, на котором находятся модифицируемые данные).

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

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

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

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

Для параллельных циклов сначала выбирается одно из измерений массива, в соответствии с распределением которого будет проводиться распределение витков цикла. Это может быть модифицируемый массив, либо используемый только на чтение (если нет модифицируемых массивов). Причем, при выборе такого массива предпочтение отдается массиву, по которому есть регулярная зависимость.

Для всех редукционных зависимостей этого многомерного цикла строится спецификация REDUCTION и дописывается к текущей директиве объявления параллельного цикла.

Далее анализируются все операции чтения элементов массивов в этом цикле для обнаружения обращений к удаленным данным.

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

Если используемые элементы массива распределены с некоторым (константным) смещением относительно витков цикла и в цикле нет обращений к рассматриваемому массиву на запись, то доступ к удаленным данным осуществляется через теневые грани, обновление которых перед циклом задается директивой SHADOW_RENEW.

Pages:     | 1 | 2 || 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»