ПОД конспект (1184369), страница 22
Текст из файла (страница 22)
Наличие таких понятий в традиционных языках программирования объясняетсянеобходимостью формулировки конкретного алгоритма с учетом вопросов экономии и распределенияпамяти, порядка выполнения операторов и т.п. Норма - это язык с однократным присваиванием Побочныйэффект в языке Норма отсутствует по определению.Понятно, что многие из этих вопросов появляются снова на этапе синтеза рабочей программы.
Однако,здесь они решаются автоматически по строгим правилам, гарантирующим правильность синтезируемойпрограммы.Высокий уровень языка обеспечивает дружественный интерфейс с пользователем, причем даже ошибки,которые обнаруживаются транслятором-синтезатором, также фиксируются в терминах предметной области.Автоматический синтез целевой программы по исходной Норма-программе гарантирует правильностьцелевой программы (с точностью до правильности работы транслятора-синтезатора).Запись на таком языке может помещаться в библиотеку исходных описаний решения задачи.
Если при этомимеется описание непрерывного уравнения и указывается метод дискретизации, то текст Норма-программыдостаточно легко понять, так как он содержит только математические (долго живущие) понятия.Важно отметить, что в записи на Норме отсутствуют избыточные связи, которые обычно накладываютсяпри программировании, особенно при оптимизации алгоритмов.
Эти связи часто ограничиваютвозможности распараллеливания. Например, конструкция 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 , то он должен быть приравнен кнулю.
Тогда , при l = log2n в уравнениях: Xi = Ali * Xi-2**l + Dli индекс Xi-2**l = Xi-n находится внедиапазона, и, следовательно, решением системы уравнений будет вектор: Xi = DliНотация Хокни для данного алгоритма:X = DDO L = 1,LOG2(N)X = A * SHIFTR(X,2**(L-1)) + XA = A * SHIFTR(A,2**(L-1))ENDDO74. Представление машинных чисел.Подмножество вещественных чисел, которое может быть представлено в ЭВМ в форме чисел сплавающей запятой, принято обозначать буквой F и определять его элементы для конкретнойархитектуры - "машинные числа", (по Форсайту и др.) четырьмя целочисленными параметрами: базойb, точностью t и интервалом значений показателя [L,U].
Множество F содержит число нуль и все fчисла вида: f = (+/-).d1d2...dt * b**e, где е называется показателем, число .d1d2...dt = (d1/b+....+dt/(b**t)) - дробной частью - мантиссой, причем: 0<=di<b, L<=e<=U. Каноническая илинормализованная форма F определяется дополнительным соотношением d1 =/= 0; это условиепозволяет устранить неоднозначность представления одинаковых чисел, дает наивысшую возможнуюточность представления чисел. Особенности F: для каждого ненулевого f верно: m<=|f|<=M, где m = b**(L-1), M = (b**U) * (1-b**(-t)); множество F конечно и содержит 2*(b-1)*(b**(t-1))*(U-L+1)+1 чисел, которые отстоят друг отдруга на числовой оси на неравные промежутки.75.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
