ПОД (пособие) (1184372), страница 46
Текст из файла (страница 46)
Это замечание верно и для передачи сообщений без ожидания.Адаптация последовательных программ к параллельнымархитектурам. Векторизация и распараллеливание циклов.Методы координат, гиперплоскостей.Автоматическое распараллеливание последовательных программ.11.6 Автоматическое распараллеливаниеМультипроцессорныекомплексыпозволяютвоспользоватьсяпреимуществамипараллелизма. Большинство программ пишутся для последовательного выполнения.Вычислительные системы получают больше пользы от параллельной обработки благодарямультипрограммному выполнению нескольких процессов, чем используя параллелизм в149рамках одного процесса. Обнаружение параллелизма (распараллеливание), выполняемоепрограммистами, языковыми трансляторами, аппаратными средствами или операционнымисистемами — это сложная проблема, вызывающая сегодня особый интерес. Независимо оттого, каким образом в конце концов будет обнаруживаться параллелизм,мультипроцессорные системы позволяют с успехом использовать его, одновременновыполняя параллельные ветви вычислений.Параллелизм в программах может быть либо явным, либо неявным (скрытым).
Явныйпараллелизм программист указывает в своей программе при помощи специальнойконструкции, обозначающей параллельное вычисление, например COBEGIN/COEND,следующим образом:COBEGIN;оператор-1;оператор-2;…оператор-n;COEND;В мультипроцессорной системе, рассчитанной на реализацию параллелизма, каждый изпрограммных операторов может выполнять отдельный процессор, с тем, чтобы всевычисления завершались быстрее, чем при чисто последовательной работе.Явное указание параллелизма налагает определенную ответственность на программиста.Это достаточно трудоемкая процедура, причем в ряде случаев программист можетошибочно указать, что определенные операции можно выполнять параллельно, в то времякак в действительности этого делать нельзя.
Программист может упустить многиеситуации, допускающие распараллеливание. Весьма вероятно, что программист обнаружитпараллелизм и закодирует его явным образом в наиболее очевидных ситуациях. Однакомногие случаи параллелизма вручную в алгоритмах обнаружить трудно, поэтому они будутпросто пропускаться.Одно из довольно неприятных последствий явного указания параллелизма заключается втом, что программы могут оказаться более сложными для модификации.
При внесенииизменений в программу, имеющую большое число явных параллельных конструкций, легкоможно допустить ошибки, причем, вообще говоря, довольно тонкие.Реально, на что можно надеяться при решении подобной проблемы,— это наавтоматическое обнаружение неявного параллелизма, т. е. параллелизма, присущегоалгоритму, но не указанного явно программистом. В компиляторы, операционные системыи аппаратные средства компьютеров необходимо включать специальные механизмыраспараллеливания. Это с гораздо большей вероятность, чем явное указание параллелизма,обеспечит создание быстро выполняющихся и корректных программ.Два распространенных способа, реализуемых в компиляторах для использования неявногопараллелизма программ,— это расщепление цикла и редукция высоты дерева.11.6.1 Расщепление циклаПрограммный цикл предполагает многократное выполнение некоторой последовательностиоператоров, называемой телом цикла, до тех пор, пока не станет истиннымсоответствующее условие завершения.
В определенных случаях в тело цикла входят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Обработка массивовОдномерные массивыДанные задачи встречаются довольно часто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
