СКИПОДы 2007 полная версия (1127795), страница 46
Текст из файла (страница 46)
В определенных случаях в тело цикла входят150операторы, которые могут допускать параллельное выполнение. Рассмотрим следующийцикл:FORI = 1 TO 4 DOA(I)=B(I)+C(I);Этот цикл суммирует соответствующие элементы массивов В и С и помещает суммы этихэлементов в массив А. По данному программному циклу последовательный процессорвыполняет поочередно следующие операции:А(1)=В(1)+С(1);А(2)=В(2)+С(2);А(3)=В(3)+С(3);А(4)=В(4)+С(4);В мультипроцессорной системе эти операторы можно выполнять параллельно при помощичетырех процессоров, благодаря чему существенно уменьшится время выполнения всегоцикла.
Компилятор, осуществляющий автоматическое распараллеливание, можетпреобразовать приведенный выше цикл в следующую форму:COBEGIN;А(1)=В(1)+С(1);А(2)=В(2)+С(2);А(3)=В(3)+С(3);А(4)=В(4)+С(4);COEND;Тем самым он указывает вычислительной системе на возможность параллельноговыполнения операторов. Этот способ называется расщеплением, или разбиениемпрограммного цикла на параллельные цепочки, и его относительно легко реализовать.Естественно, что во многих программных циклах число повторений гораздо большечетырех, как в данном примере, поэтому метод разбиения цикла обычно дает болеевысокую степень параллелизма, чем количество имеющихся процессоров.
Операционнаясистема и аппаратные средства компьютера должны затем решить, какое подмножествопараллельных ветвей будет выполняться одновременно.11.6.2 Редукция высоты дереваПрименяя ассоциативные, коммутативные и дистрибутивные свойства арифметики,компиляторы могут обнаруживать неявный параллелизм в алгебраических выражениях игенерировать объектный код для мультипроцессорных систем с указанием операций,которые можно выполнять одновременно. Компиляторы должны действовать всоответствии со старшинством операций. Не все компиляторы используют одинаковыеправила старшинства, однако во многих случаях применяются примерно следующиеправила:1.
Прежде всего выполняются операции, указанные во вложенных скобках, и, в частности,те операции, которые имеют более глубокий уровень вложенности.2. Затем выполняются операции в скобках.3. Затем выполняются операции возведения в степень.4. Затем выполняются операции умножения и деления.5. Затем выполняются операции сложения и вычитания.1516. Если операции, которые можно выполнить следующими, имеют одинаковоестаршинство, то они выполняются слева направо.Применение таких правил старшинства операций дает компилятору возможностьустанавливать однозначный последовательный порядок действий для алгебраическоговыражения, а затем переходить к генерации машинного кода, реализующего вычислениеэтого выражения.Зачастую однозначность и последовательность порядка действий при вычислениях необязательны.
Например, поскольку операции сложения и умножения являютсякоммутативными, компилятор, генерирующий код для перемножения p и q, может выдатьлибо p*q, либо q*p; результаты вычислений будут, естественно, одинаковыми. Аналогично,сложение p и q можно выполнить либо как p+q, либо как p+q. Используя свойствокоммутативности, а также ассоциативности и дистрибутивности, компилятор можетдовольно гибко перестраивать выражения, делая их более удобными для параллельныхвычислений.На рис, 11.2 показано, как обычный компилятор оттранслировал бы алгебраическоевыражение и как оно могло бы быть обработано распараллеливающим компилятором.Левая диаграмма на этом рисунке — структура дерева, показывающего, каким образомобычный компилятор может генерировать код программы для выполнения приведенныхопераций.
Цифры 1, 2 и 3 показывают порядок,Рис. 11.2 Уменьшение высоты дерева за счет ассоциативности.в котором должны выполняться эти операции. Используя ассоциативность сложения,можно преобразовать выражение ((p+q)+r)+s в выражение вида (p+q)+(r+s), которое болееприспособлено для параллельных вычислений. Структуре первого выражениясоответствует трехуровневое дерево, в то время как структуре второго — лишьдвухуровневое, и поэтому его можно выполнить гораздо быстрее на мультипроцессорнойсистеме.Цель многих систем новых поколений будет заключаться в том, чтобы производитьвычисления в минимально возможное время, независимо от того, сколько процессоровпридется использовать для выполнения этой работы. Поэтому новые вычислительныесистемы будут содержать специальные механизмы, которые будут преобразовыватьпоследовательные алгоритмы в параллельные, разлагая их на шаги, которые можно было бывыполнять одновременно на многих процессорах системы.152На рис.
11.3 показано, каким образом благодаря коммутативности сложения можнопреобразовать последовательную цепь операций, изображаемую трехуровневым деревом, впараллельный вариант, требующий всего лишь двух уровней. На рис. 11.4 показано, какимобразом дистрибутивность умножения и сложения может быть использована дляуменьшения числа уровней дерева с четырех до трех.Рис. 11.3 Уменьшение высоты дерева за счет коммутативности.Рис. 11.4 Уменьшение высоты дерева за счет дистрибутивности.Применение указанных методов компиляции с целью оптимизации программ длявыполнения на мультипроцессорных системах не обходится бесплатно.
Дело в том, что зауменьшение количества времени выполнения, затрачиваемого на данное вычисление,приходится платить увеличенными затратами времени и ресурсов в период компиляции.Такую взаимосвязь необходимо учитывать, тщательно оценивая необходимые затраты ивозможные выгоды в каждом индивидуальном случае. Например, для производственногосчета целесообразно добиваться минимального времени выполнения программ.
Однако вусловиях разработки, когда программа, возможно, будет выполняться всего один или двараза до внесения очередных изменений и повторной компиляции, затраты на оптимизациюмогут значительно превысить получаемые выгоды.Семантика циклов, выполняемых параллельно на ОКМД системах.Не уверен, что это самое то, но близко…Классы задач, которые можно эффективно векторизовать или распараллелить153Обработка массивовОдномерные массивыДанные задачи встречаются довольно часто. Если значения элементов массиваопределяются довольно сложным выражением, а вычислять их надо многократно, товекторизация или распараллеливание цикла для вычисления элементов массива можетоказаться очень эффективным.
В отдельный параграф мы вынесли решение системдифференциальных уравнений, что по своей сути также является обработкой массивовфункций, производных и т.д. Но на самом деле эффективными могут также бытьвычисления сверток, сумм, функций от каждого элемента массива и т.п.Конечно, не имеет смысл векторизовать или распараллеливать действия надкороткими массивами кроме тех случаев, когда собственно вычисления каждого элементазанимают большое время.Двумерные массивыПри исполнении вложенных циклов эффективно распараллеливаются самыевнешние циклы, а векторизуются только внутренние.
Однако практически все действия сматрицами (сложение, умножение, умножение на вектор, прямое произведение) могут бытьвыполнены быстро на супер-ЭВМ. Многие алгоритмы линейной алгебры (но не все) могутбыть эффективно векторизованы и распараллелены. Некоторые библиотеки подпрограмм(например, LAPACK(?)) существуют для параллельных и векторных машин.Совершенно неэффективно использовать векторные ЭВМ для работы с матрицамиразмерности 3x3. Но можно переписать алгоритм для одновременной обработки нескольких(к примеру 1000) матриц - обращение, поиск собственных чисел и т.д.При увеличении размера матриц растет эффективность работы программы, но растети размер требуемой памяти для хранения матриц.
При работе на векторной машине снебольшим (128-512 Мбайт) объемом ОЗУ это может стать причиной общего снижения еебыстродействия из-за частого обращения к дискам при записи/чтении данных.Вычисления в узлах сеток и решетокИнженерные и научные задачиВо многих областях знания встречаются задачи, которые сводятся к вычислениюэволюции объектов, расположенных в дискретных точках и взаимодействующих сближайшими соседями. Простейшей и, наверно, наиболее широко известной такой задачейявляется игра "жизнь".Все игровое поле представляет двумерную сетку с квадратными ячейками.
Каждаяячейка может быть в одном из двух состояний - пустая или живая. Если на каком-то шагеигры вокруг пустого поля существуют ровно три живых поля, то на следующем шаге игры вэтом поле рождается жизнь. Если число живых полей вокруг пустого поля не равно трем, тов это поле остается пустым. Если вокруг живого поля существуют два или три другихживых поля, то жизнь в в этом поле продолжается. Если число живых соседей отлично отдвух или трех, то поле погибает (становится пустым).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
