Ответы 190 страниц (1184228), страница 33
Текст из файла (страница 33)
При передаче сообщений асинхронным способом сообщения при отправлении помечаются целым числом - тегом. Эта разметка дает возможность абонентам идентифицировать сообщения от разных операторов передачи сообщений одного процесса. Получив сообщение с заданным тегом, процесс может узнать имя отправителя, через аппарат SENDERов. Это замечание верно и для передачи сообщений без ожидания.
Адаптация последовательных программ к параллельным архитектурам. Векторизация и распараллеливание циклов. Методы координат, гиперплоскостей.
Автоматическое распараллеливание последовательных программ.
11.6 Автоматическое распараллеливание
Мультипроцессорные комплексы позволяют воспользоваться преимуществами параллелизма. Большинство программ пишутся для последовательного выполнения. Вычислительные системы получают больше пользы от параллельной обработки благодаря мультипрограммному выполнению нескольких процессов, чем используя параллелизм в рамках одного процесса. Обнаружение параллелизма (распараллеливание), выполняемое программистами, языковыми трансляторами, аппаратными средствами или операционными системами — это сложная проблема, вызывающая сегодня особый интерес. Независимо от того, каким образом в конце концов будет обнаруживаться параллелизм, мультипроцессорные системы позволяют с успехом использовать его, одновременно выполняя параллельные ветви вычислений.
Параллелизм в программах может быть либо явным, либо неявным (скрытым). Явный параллелизм программист указывает в своей программе при помощи специальной конструкции, обозначающей параллельное вычисление, например COBEGIN/COEND, следующим образом:
COBEGIN;
оператор-1;
оператор-2;
…
оператор-n;
COEND;
В мультипроцессорной системе, рассчитанной на реализацию параллелизма, каждый из программных операторов может выполнять отдельный процессор, с тем, чтобы все вычисления завершались быстрее, чем при чисто последовательной работе.
Явное указание параллелизма налагает определенную ответственность на программиста. Это достаточно трудоемкая процедура, причем в ряде случаев программист может ошибочно указать, что определенные операции можно выполнять параллельно, в то время как в действительности этого делать нельзя. Программист может упустить многие ситуации, допускающие распараллеливание. Весьма вероятно, что программист обнаружит параллелизм и закодирует его явным образом в наиболее очевидных ситуациях. Однако многие случаи параллелизма вручную в алгоритмах обнаружить трудно, поэтому они будут просто пропускаться.
Одно из довольно неприятных последствий явного указания параллелизма заключается в том, что программы могут оказаться более сложными для модификации. При внесении изменений в программу, имеющую большое число явных параллельных конструкций, легко можно допустить ошибки, причем, вообще говоря, довольно тонкие.
Реально, на что можно надеяться при решении подобной проблемы,— это на автоматическое обнаружение неявного параллелизма, т. е. параллелизма, присущего алгоритму, но не указанного явно программистом. В компиляторы, операционные системы и аппаратные средства компьютеров необходимо включать специальные механизмы распараллеливания. Это с гораздо большей вероятность, чем явное указание параллелизма, обеспечит создание быстро выполняющихся и корректных программ.
Два распространенных способа, реализуемых в компиляторах для использования неявного параллелизма программ,— это расщепление цикла и редукция высоты дерева.
11.6.1 Расщепление цикла
Программный цикл предполагает многократное выполнение некоторой последовательности операторов, называемой телом цикла, до тех пор, пока не станет истинным соответствующее условие завершения. В определенных случаях в тело цикла входят операторы, которые могут допускать параллельное выполнение. Рассмотрим следующий цикл:
FORI = 1 TO 4 DO
A(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. Затем выполняются операции сложения и вычитания.
6. Если операции, которые можно выполнить следующими, имеют одинаковое старшинство, то они выполняются слева направо.
Применение таких правил старшинства операций дает компилятору возможность устанавливать однозначный последовательный порядок действий для алгебраического выражения, а затем переходить к генерации машинного кода, реализующего вычисление этого выражения.
Зачастую однозначность и последовательность порядка действий при вычислениях не обязательны. Например, поскольку операции сложения и умножения являются коммутативными, компилятор, генерирующий код для перемножения 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), которое более приспособлено для параллельных вычислений. Структуре первого выражения соответствует трехуровневое дерево, в то время как структуре второго — лишь двухуровневое, и поэтому его можно выполнить гораздо быстрее на мультипроцессорной системе.
Цель многих систем новых поколений будет заключаться в том, чтобы производить вычисления в минимально возможное время, независимо от того, сколько процессоров придется использовать для выполнения этой работы. Поэтому новые вычислительные системы будут содержать специальные механизмы, которые будут преобразовывать последовательные алгоритмы в параллельные, разлагая их на шаги, которые можно было бы выполнять одновременно на многих процессорах системы.
На рис. 11.3 показано, каким образом благодаря коммутативности сложения можно преобразовать последовательную цепь операций, изображаемую трехуровневым деревом, в параллельный вариант, требующий всего лишь двух уровней. На рис. 11.4 показано, каким образом дистрибутивность умножения и сложения может быть использована для уменьшения числа уровней дерева с четырех до трех.
Рис. 11.3 Уменьшение высоты дерева за счет коммутативности.
Рис. 11.4 Уменьшение высоты дерева за счет дистрибутивности.
Применение указанных методов компиляции с целью оптимизации программ для выполнения на мультипроцессорных системах не обходится бесплатно. Дело в том, что за уменьшение количества времени выполнения, затрачиваемого на данное вычисление, приходится платить увеличенными затратами времени и ресурсов в период компиляции. Такую взаимосвязь необходимо учитывать, тщательно оценивая необходимые затраты и возможные выгоды в каждом индивидуальном случае. Например, для производственного счета целесообразно добиваться минимального времени выполнения программ. Однако в условиях разработки, когда программа, возможно, будет выполняться всего один или два раза до внесения очередных изменений и повторной компиляции, затраты на оптимизацию могут значительно превысить получаемые выгоды.
Семантика циклов, выполняемых параллельно на ОКМД системах.
Не уверен, что это самое то, но близко…
Классы задач, которые можно эффективно векторизовать или распараллелить
Обработка массивов
Одномерные массивы
Данные задачи встречаются довольно часто. Если значения элементов массива определяются довольно сложным выражением, а вычислять их надо многократно, то векторизация или распараллеливание цикла для вычисления элементов массива может оказаться очень эффективным. В отдельный параграф мы вынесли решение систем дифференциальных уравнений, что по своей сути также является обработкой массивов функций, производных и т.д. Но на самом деле эффективными могут также быть вычисления сверток, сумм, функций от каждого элемента массива и т.п.
Конечно, не имеет смысл векторизовать или распараллеливать действия над короткими массивами кроме тех случаев, когда собственно вычисления каждого элемента занимают большое время.
Двумерные массивы
При исполнении вложенных циклов эффективно распараллеливаются самые внешние циклы, а векторизуются только внутренние. Однако практически все действия с матрицами (сложение, умножение, умножение на вектор, прямое произведение) могут быть выполнены быстро на супер-ЭВМ. Многие алгоритмы линейной алгебры (но не все) могут быть эффективно векторизованы и распараллелены. Некоторые библиотеки подпрограмм (например, LAPACK(?)) существуют для параллельных и векторных машин.
Совершенно неэффективно использовать векторные ЭВМ для работы с матрицами размерности 3x3. Но можно переписать алгоритм для одновременной обработки нескольких (к примеру 1000) матриц - обращение, поиск собственных чисел и т.д.
При увеличении размера матриц растет эффективность работы программы, но растет и размер требуемой памяти для хранения матриц. При работе на векторной машине с небольшим (128-512 Мбайт) объемом ОЗУ это может стать причиной общего снижения ее быстродействия из-за частого обращения к дискам при записи/чтении данных.
Вычисления в узлах сеток и решеток
Инженерные и научные задачи
Во многих областях знания встречаются задачи, которые сводятся к вычислению эволюции объектов, расположенных в дискретных точках и взаимодействующих с ближайшими соседями. Простейшей и, наверно, наиболее широко известной такой задачей является игра "жизнь".
Все игровое поле представляет двумерную сетку с квадратными ячейками. Каждая ячейка может быть в одном из двух состояний - пустая или живая. Если на каком-то шаге игры вокруг пустого поля существуют ровно три живых поля, то на следующем шаге игры в этом поле рождается жизнь. Если число живых полей вокруг пустого поля не равно трем, то в это поле остается пустым. Если вокруг живого поля существуют два или три других живых поля, то жизнь в в этом поле продолжается. Если число живых соседей отлично от двух или трех, то поле погибает (становится пустым). Начальная конфигурация выбирается произвольным образом. Игровое поле может иметь края или может быть свернуто в тор. Вот пример конфигурации:
o o o Обозначения:
o x o Oo - пустые
O X O Xx - живые
o x o O - родится, o - останется
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
