Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Высокий уровень абстракции языка позволяет описывать задачи в нотации, близкой к исходной постановки проблемы математиком (программирование без программиста), получать описание не ориентированное на конкретную архитектуру и/или конкретные методы организации параллельного выполнения. Язык не содержит традиционные конструкции языков программирования, фиксирующие порядок вычисления и/или иным образом "скрывающие/ограничивающие" параллелизм (например, COMMON-блоки).

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

• Фортран 77-для выполнения на последовательных ЭВМ;

• Фортран/PVM-для выполнения на любых системах с Фортран/PVM;

• Фортран/GNS-для выполнения на МВС-100 и других системах с Фортран/GNS-см. проект ИПМ/GNS;

• Фортран/Convex-для выполнения на HP Convex SPP-100 и других системах с Фортран/Convex;

• (в разработке) Фортран/MPI-для выполнения на любых системах с Фортран/MPI;

http://parallel.ru/tech/norma/

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

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

• Выбирается пространственно-временная сетка и производится дискретизация уравнений с помощью одного из разностных методов.

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

• Полученные формулы программируются на некотором языке, который обеспечивает решение задачи на вычислительной машине.

Главная идея, положенная в основу языка Норма, заключается в том, что полученное на третьем этапе описание решения задачи, почти непосредственно используется для ввода его в вычислительную систему и проведения счета.

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

Запись на языке Норма - это, по существу, строгая запись численных методов решения математической задачи, запись еще не алгоритмов, а просто расчетных формул и остальной необходимой информации, которую необходимо знать, чтобы написать программу для ЭВМ.

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

Выбор уровня языка Норма определяет характерную его черту - в этом языке нет необходимости вводить такие понятия, как оператор присваивания и возможность переприсваивания значений (типа Х:=Х+1) и операторы перехода. Наличие таких понятий в традиционных языках программирования объясняется необходимостью формулировки конкретного алгоритма с учетом вопросов экономии и распределения памяти, порядка выполнения операторов и т.п. Норма - это язык с однократным присваиванием Побочный эффект в языке Норма отсутствует по определению.

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

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

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

Важно отметить, что в записи на Норме отсутствуют избыточные связи, которые обычно накладываются при программировании, особенно при оптимизации алгоритмов. Эти связи часто ограничивают возможности распараллеливания. Например, конструкция COMMON языка Фортран обычно ограничивает автоматическое распараллеливание программ.

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

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

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

1. Распараллеливание алгоритмов сложения методом редукции

Параллельно суммирование последовательности n чисел можно произвести так: на первом этапе складываются соседние числа. Полученные суммы также складываются попарно, и т.д. Для n = 2**q алгоритм состоит из q = log n этапов, на первом этапе выполняются n/2 сложений (степень параллельности этапа n/2), на втором - n/4 и т. д. Такой алгоритм называется сложение методом сдваивания, он имеет различную степень параллелизма на разных этапах вычислений. Граф, описывающий последовательность операций сложения, граф сдваивания (по Д. Ортега "fan-in grafh.") представляет собой двоичное дерево, соответственно, выполняемые операции можно называть операциями на дереве.

Способ реализации процедуры суммирования данным методом зависит от архитектуры вычислительной системы. При наличии n/2 процессоров эту работу можно выполнить так: на первом этапе одновременно получить суммы четных/нечетных соседних элементов последовательности Ai, т.е. (A1+A2), (A3+A4),...(An-1+An); затем такая процедура повторяется для суммирования полученных частных сумм и так далее. Если n = 2**q, то через q = log2n шагов получается искомая сумма. Однако, потери на синхронизацию вычислений, на пересылки частных сумм могут оказаться сравнимы с временем вычисления суммы двух чисел в каждом процессоре.

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

Алгоритм сдваивания реализуются также в блоках оптимизации компиляторов последовательных ЭВМ для полной загрузки конвейерных вычислителей. Так алгоритм оптимизация "балансировка дерева вычислений" (tree-height reduction or balancing) будет трактовать вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, как последовательность операций: (((A+B)+(C+D))+((E+F)+(G+H))).

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

Данные А1 А2 А3 А4 А5 А6 А7 А8

Ярус 1 А1+А2 А3+А4 А5+А6 А7+А8

Ярус 2 А12+А3 А12+А34 А56+А7 А56+А78

Ярус 3 А1234+А5 А1234+А56 А1234+А567 А1234+А5678

Высота параллельной формы равна трем, ширина - четырем, причем загрузка вычислителей (четырех) полная.

В данном алгоритме производится вычисления пяти 'лишних' чисел по сравнению с последовательным алгоритмом.

Каскадное суммирование

Примером параллельных алгоритмов, ориентированных на векторные вычислители, может служить метод вычисления каскадных сумм (алгоритм рекурсивного удвоения) для распараллеливания операций суммирования. Пусть необходимо просуммировать n чисел с сохранением промежуточных сумм: Si = Si-1 + Ai i = 2,..n, S1 = A1. Исходный вектор А поэлементно складывается с вектором Аs, полученный из исходного со сдвигом на один элемент и заполнением позиции элемента А0 нулем. Для вектора результата процедура повторяется, но сдвиг - на 2 позиции. Если n = 2**k, то через k операций получается вектор результата.

Для i=8:

A1 0 A1 0 A1 0 A1

A2 A1 A12 0 A12 0 A12

A3 A2 A23 A1 A123 0 A123

A4 + A3 = A34 + A12 = A1234 + 0 = A1234

A5 A4 A45 A23 A2345 A1 A12345

A6 A5 A56 A34 A3456 A12 A123456

A7 A6 A67 A45 A4567 A123 A1234567

A8 A7 A78 A56 A5678 A1234 A12345678

Алгебра данного метода может быть записана в виде вычисления (возможно, параллельного) частных сумм вида: Si = Ali, где Ali = A(l-1)i + A(l-1)(i-2**(l-1)), A0i = Ai для i = 1,2,...n.

Вычисления проводятся l = 0,1,...,log2n раз, причем, если у Ali индекс i выходит из интервала 1<= i <= n то он принимается равным нулю.

Хокни предлагает элегантную векторную форму записи алгоритма каскадного суммирования массива D(n):

X = D

DO L = 1,LOG2(N)

X = X + SHIFTR(X,2**(L-1))

ENDDO

Результат векторной функции SHIFTR(A,l) есть массив (вектор), полученный из А , элементы которого сдвинуты на L позиций вправо, а L левых элементов заполнены нулями. Практическая реализация алгоритма может исключить излишние операции сложения с нулем, однако, и после этого, по сравнению с последовательным алгоритмом, данный - требует лишние операции.

1. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.

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

Линейной рекурсией 1 порядка называется система уравнений вида:

X1 = D1

X2 = X1 * A2 + D2

.................

Xi = Xi-1 * Ai + Di

.................

Xn = Xn-1 * An + Dn

в общем виде: Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 = D1

Это система эквивалентна двухдиагональной системе уравнений Ax=d, где

┌ ─┐ ┌─ ─┐

│ 1 │ │ d1 │

A = │ -a2 1 │ d = │ . │

│ ....... │ │ │

│ -an 1 │ │ dn │

└ ┘ └─ ─┘

Последовательный алгоритм вычислений может быть записан так:

X(1) = A(1) + D(1)

DO i = 1,n

X(i) = X(i-1) * A(i) + D(i)

ENDDO

Рекурсивная зависимость итераций цикла не позволяет ускорить вычисления за счет параллельной работы оборудования. Преобразуем данный алгоритм в параллельный методом циклической редукции. Рассмотрим два соседних уравнения:

Xi-1 = Xi-2 * Ai-1 + Di-1

Xi = Xi-1 * Ai + Di

и подставив первое во второе, получаем:

Xi = (Xi-2 * Ai-1 + Di-1) * Ai + Di = Xi-2 * A1i + D1i , где

A1i = Ai * Ai-1 ,

D1i = Ai * Di-1 + Di

Тогда, проведя эту операцию для всей системы уравнений, получим систему уравнений порядка n/2. Если повторить процедуру l раз (если n = 2**l), то в результате получается значение: Xn = Dnl. Для получения полного вектора X необходимо модифицировать алгоритм, например, по аналогии с алгоритмами суммирования.

Очевидно, что вычисления Aji и Dji можно проводить параллельно методом каскадных сумм с сохранением частных сумм. Приведенные уравнения для уровня i имеют вид:

Xi = Ali * Xi-2**l + Dli , где l = 0,1,..,log2n , i = 1,2,..,n

Ali = Al-1i * Al-1(i-2**l-1)

Dli = Al-1i * Dl-1(i-2**l-1) + Dl-1i

Начальные данные: A0i = Ai, D0i = Di

Если индекс i у любого Ali, Dli и Xi попадает вне диапазона 1 <= i <= n , то он должен быть приравнен к нулю. Тогда , при l = log2n в уравнениях: Xi = Ali * Xi-2**l + Dli индекс Xi-2**l = Xi-n находится вне диапазона, и, следовательно, решением системы уравнений будет вектор: Xi = Dli

Характеристики

Список файлов лекций