СКИПОДы конспект лекций (1127769), страница 22

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

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

Возможно применение для иных задач (нет более подробных данных).Высокий уровень абстракции языка позволяет описывать задачи в нотации, близкой к исходной постановкипроблемы математиком (программирование без программиста), получать описание не ориентированное наконкретную архитектуру и/или конкретные методы организации параллельного выполнения. Язык несодержит традиционные конструкции языков программирования, фиксирующие порядок вычисления и/илииным образом "скрывающие/ограничивающие" параллелизм (например, COMMON-блоки).После двух фаз компиляции (анализ информационных зависимостей и генерация ярусно-параллельногографа алгоритма) вывод результирующей программы возможен в следующих форматах:Фортран 77-для выполнения на последовательных ЭВМ;Фортран/PVM-для выполнения на любых системах с Фортран/PVM;Фортран/GNS-для выполнения на МВС-100 и других системах с Фортран/GNS-см. проектИПМ/GNS;Фортран/Convex-для выполнения на HP Convex SPP-100 и других системах с Фортран/Convex;(в разработке) Фортран/MPI-для выполнения на любых системах с Фортран/MPI;http://parallel.ru/tech/norma/Непроцедурный язык Норма предназначен для записи численных методов решения задач математическойфизики разностными методами.

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

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

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

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

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

Распараллеливание алгоритмов сложения методом редукцииПараллельно суммирование последовательности n чисел можно произвести так: на первом этапескладываются соседние числа. Полученные суммы также складываются попарно, и т.д. Для n = 2**qалгоритм состоит из q = log n этапов, на первом этапе выполняются n/2 сложений (степень параллельностиэтапа n/2), на втором - n/4 и т. д.

Такой алгоритм называется сложение методом сдваивания, он имеетразличную степень параллелизма на разных этапах вычислений. Граф, описывающий последовательностьопераций сложения, граф сдваивания (по Д. Ортега "fan-in grafh.") представляет собой двоичное дерево,соответственно, выполняемые операции можно называть операциями на дереве.55Способ реализации процедуры суммирования данным методом зависит от архитектуры вычислительнойсистемы. При наличии 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А1А2А3А4А1+А2А3+А4А12+А3А12+А34А1234+А5 А1234+А56А5А6А7А8А5+А6А7+А8А56+А7А56+А78А1234+А567 А1234+А5678Высота параллельной формы равна трем, ширина - четырем, причем загрузка вычислителей (четырех)полная.В данном алгоритме производится вычисления пяти 'лишних' чисел по сравнению с последовательнымалгоритмом.Каскадное суммированиеПримером параллельных алгоритмов, ориентированных на векторные вычислители, может служить методвычисления каскадных сумм (алгоритм рекурсивного удвоения) для распараллеливания операцийсуммирования.

Пусть необходимо просуммировать n чисел с сохранением промежуточных сумм: Si = Si-1+ Ai i = 2,..n, S1 = A1. Исходный вектор А поэлементно складывается с вектором Аs, полученный изисходного со сдвигом на один элемент и заполнением позиции элемента А0 нулем. Для вектора результатапроцедура повторяется, но сдвиг - на 2 позиции. Если n = 2**k, то через k операций получается векторрезультата.Для i=8:A10A10A10A1A2A1A120A120A12A3A2A23A1A1230A123A4 + A3 = A34 + A12 = A1234 + 0= A1234A5A4A45A23A2345A1A12345A6A5A56A34A3456A12A123456A7A6A67A45A4567A123A1234567A8A7A78A56A5678A1234A12345678Алгебра данного метода может быть записана в виде вычисления (возможно, параллельного) частныхсумм вида: 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 = DDO L = 1,LOG2(N)56X = X + SHIFTR(X,2**(L-1))ENDDOРезультат векторной функции SHIFTR(A,l) есть массив (вектор), полученный из А , элементы которогосдвинуты на L позиций вправо, а L левых элементов заполнены нулями.

Практическая реализацияалгоритма может исключить излишние операции сложения с нулем, однако, и после этого, по сравнениюс последовательным алгоритмом, данный - требует лишние операции.73. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.Редукция - упрощение, в биологии уменьшение размера органа вплоть до его полного исчезновения.Циклическая редукция - алгоритмы численного анализа для распараллеливания последовательныхалгоритмов, основанный на последовательном, циклическом применении параллельных вычислений, числокоторых на каждом этапе уменьшается (делится) пополам.Линейной рекурсией 1 порядка называется система уравнений вида:X1 = D1X2 = 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,nX(i) = X(i-1) * A(i) + D(i)ENDDOРекурсивная зависимость итераций цикла не позволяет ускорить вычисления за счет параллельной работыоборудования.Преобразуем данный алгоритмв параллельный методом циклической редукции.Рассмотрим два соседних уравнения:Xi-1 = Xi-2 * Ai-1 + Di-1Xi = 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,..,nAli = Al-1i * Al-1(i-2**l-1)Dli = Al-1i * Dl-1(i-2**l-1) + Dl-1iНачальные данные: A0i = Ai, D0i = Di57Если индекс i у любого Ali, Dli и Xi попадает вне диапазона 1 <= i <= n , то он должен быть приравнен кнулю.

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

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