КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Формы параллелизма
Параллелизм — это возможность одновременного выполнения более од- ной арифметико-логической операции или программной ветви. Возможность параллельного выполнения этих операций определяется правилом Рассела, ко- торое состоит в следующем: Программные объекты A и B (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие: (InB OutA)(InA OutB) (OutA OutB) = Ø, (1.1)
где In(A) — набор входных, а Out(A) — набор выходных переменных объекта A. Если условие (1.1) не выполняется, то между A и B существует зависимость и они не могут выполняться параллельно. Если условие (1.1) нарушается в первом терме, то такая зависимость назы вается прямой. Приведем пример: A: R = R1 + R2 B: Z = R + C Здесь операторы A и B не могут выполняться одновременно, так как результат A является операндом B. Если условие нарушено во втором терме, то такая зависимость называется обратной: A: R = R1 + R2 B: R1 = C1 + C2 Здесь операторы A и B не могут выполняться одновременно, так как выполнение B вызывает изменение операнда в A. Если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной: A: R = R1 + R2 B: R = C1 + C2 Здесь одновременное выполнение дает неопределенный результат. Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей. Наиболее общей формой представления этих зависимостей является ин- формационный граф задачи (ИГ). Пример ИГ, описывающего логику конкрет- ной задачи, точнее порядок выполнения операций в задаче В своей первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.
Более определенной формой представления параллелизма является яруснопараллельная форма (ЯПФ): алгоритм вычислений представляется в виде яру
сов, причем в нулевой ярус входят операторы (ветви), не зависящие друг от друга, в первый ярус — операторы, зависящие только от нулевого яруса, во второй — от первого яруса и т. д. Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: b i — ширина i -го яруса; B — ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из b i, i = 1, 2,...); li — длина яруса (время операций) и L длина графа; ε — коэффициент заполнения ярусов; θ — коэффициент разброса указанных параметров и т. д. Главной задачей настоящего издания является изучение связи между клас сами задач и классами параллельных ЭВМ. Форма параллелизма обычно достаточно просто характеризует некоторый класс прикладных задач и предъявляет определенные требования к структуре, необходимой для решения этого класса задач параллельной ЭВМ. Изучение ряда алгоритмов и программ показало, что можно выделить сле дующие основные формы параллелизма: • Мелкозернистый параллелизм (он же параллелизм смежных операций или скалярный параллелизм). • Крупнозернистый параллелизм, который включает: векторный паралле- лизм и параллелизм независимых ветвей..
Мелкозернистый параллелизм ( Fine Grain) При исполнении программы регулярно встречаются ситуации, когда исходные данные для i -й операции вырабатываются заранее, например, при выпол нении (i - 2)-й или (i - 3)-й операции. Тогда при соответствующем построении вычислительной системы можно совместить во времени выполнение i -й опера- ции с выполнением (i - 1)-й, (i - 2)-й,... операций. В таком понимании скаляр- ный параллелизм похож на параллелизм независимых ветвей, однако они очень отличаются длиной ветвей и требуют разных вычислительных систем.
Рассмотрим пример. Пусть имеется программа для расчета ширины запрещенной зоны транзистора, и в этой программе есть участок — определение энергии примесей по формуле
Тогда последовательная программа для вычисления E будет такой: F1 = M * Q ** 4* P ** 2 F2 = 8 * E0 ** 2* E ** 2 * H** 2 E = F1/F2 Здесь имеется параллелизм, но при записи на Фортране или Ассемблере у нас нет возможности явно отразить его. Явное представление параллелизма для вычисления E задается ЯПФ Ширина параллелизма первого яруса этой ЯПФ (первый такт) сильно зависит от числа операций, включаемых в состав ЯПФ. Так, в примере для l 1 = 4 параллелизм первого такта равен двум, для l 1 = 12 параллелизм равен пяти. Поскольку это параллелизм очень коротких ветвей и с помощью операторов FORK и JOIN описан быть не может (вся программа будет состоять в основ ном из этих операторов), данный вид параллелизма должен автоматически вы- являться аппаратурой ЭВМ в процессе выполнения машинной программы.
Для скалярного параллелизма часто используют термин мелкозернистый параллелизм (МЗП), в отличие от крупнозернистого параллелизма (КЗП), к ко- торому относят векторный параллелизм и параллелизм независимых ветвей.
Крупнозернистый параллелизм (coarse grain) Векторный параллелизм. Наиболее распространенной в обработке структур данных является векторная операция (естественный параллелизм). Вектор— одномерный массив, который образуется из многомерного массива, если один из индексов не фиксирован и пробегает все значения в диапазоне его изменения. В параллельных языках этот индекс обычно обозначается знаком *. Пусть, например, A, B, C — двумерные массивы. Рассмотрим следующий цикл: DO 1 I = 1,N 1 C(I,J) = A(I,J) + B(I,J)
Нетрудно видеть, что при фиксированном J операции сложения для всех I можно выполнять параллельно, поскольку ЯПФ этого цикла имеет один ярус. По существу этот цикл соответствует сложению столбца J матриц А и В с записью результата в столбец J матрицы С. Этот цикл на параллельном яэыке записывается в виде такой векторной операции: C (*, j) = A (*, j) + B (*, j).
Возможны операции и большей размерности, чем векторные: над матрицами и многомерными массивами. Однако в параллельные ЯВУ включаются только векторные операции (сложение, умножение, сравнение и т. д.), потому что они носят универсальный характер, тогда как операции более высокого уровня специфичны.
Области применения векторных операций над массивами обширны: цифровая обработка цифровая обработка сигналов (цифровые фильтры), механика, моделирование сплошных сред, метеорология, оптимизация, задачи движения и т.д. Рассмотрим решение линейной системы уравнений:
Для решения таких систем уравнений при положительно определенной матрице коэффициентов используется метод простой итерации:
Пусть C(N,N) — матрица коэффициентов ci,j системы уравнений; D (N) — вектор d 1, d 2,..., dn; XK(N) — вектор (в исходный момент хранит начальное приближение); XK1(N) — вектор ; ε — заданная по- грешность вычислений. Тогда программа для параллельной ЭВМ может выгля- деть следующим образом:
DIMENSION C(N,N), D(N), XK1(N), XK(N) XK(*) = начальные значения XK1(*) = D(*) 4 DO 1 I = 1,N 1 XK1(*) = XK1(*) + C(*,I)*XK(I) IF (ABS(XK1(*)-XK(*))-ε) 2,2,3 3 XK(*) = XK1(*) GO TO 4 2 Вывод XK1(*) STOP
В этой программе многократно использована параллельная обработка эле ментов векторов (практически во всех строках программы). Цикл по I соответ- ствует перебору столбцов матрицы С, которые выступают в качестве векторов
Дата добавления: 2014-01-07; Просмотров: 1094; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |