СКИПОДы 2007 полная версия (1127795), страница 52
Текст из файла (страница 52)
Один и тот жепараметр не может быть одновременно исходным и результатом: это приводит кпереприсваиванию значений переменным (повторному присваиванию), что запрещено вНорме. В разделе-функции ключевое слово RESULT не используется: результатвычисления функции связывается с именем и типом функции.В теле раздела могут быть заданы описания, операторы и итерации (порядок ихрасположения, вообще говоря, произвольный - возможные ограничения определяются приописании входного языка транслятора).Система Норма состоит из следующих компонентов:-Декларативный язык Норма-Компилятор с языка Норма-Конфигуратор программ на языке Норма-Отладчик программ на языке Норма-Пользовательский Windows-интерфейсОсобенности выполнения арифметических выражения на ЭВМ.Распараллеливание вычислительных алгоритмов.
Методраспараллеливания алгоритма общей рекурсии 1-го порядка.Распараллеливание алгоритмов сложения методом редукцииПараллельно суммирование последовательности n чисел можно произвести так: напервом этапе складываются соседние числа. Полученные суммы также складываютсяпопарно, и т.д. Для n = 2**q алгоритм состоит из q = log n этапов, на первом этапевыполняются n/2 сложений (степень параллельности этапа n/2), на втором - n/4 и т. д. Такойалгоритм называется сложение методом сдваивания, он имеет различную степеньпараллелизма на разных этапах вычислений.
Граф, описывающий последовательностьопераций сложения, граф сдваивания (по Д. Ортега "fan-in grafh.") представляет собойдвоичное дерево, соответственно, выполняемые операции можно называть операциями надереве.174Способ реализации процедуры суммирования данным методом зависит от архитектурывычислительной системы. При наличии 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 A10A1A2 A1 A12 0 A12 0A12A3 A2 A23 A1 A123 0A123A4 + A3 = A34 + A12 = A1234 + 0 = A1234A5 A4 A45 A23 A2345 A1A12345175A6 A5 A56A7 A6 A67A8 A7 A78A34 A3456 A12A123456A45 A4567 A123 A1234567A56 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=DDO L = 1,LOG2(N)X = X + SHIFTR(X,2**(L-1))ENDDOРезультат векторной функции SHIFTR(A,l) есть массив (вектор), полученный из А ,элементы которого сдвинуты на L позиций вправо, а L левых элементов заполнены нулями.Практическая реализация алгоритма может исключить излишние операции сложения снулем, однако, и после этого, по сравнению с последовательным алгоритмом, данный требует лишние операции.Метод распараллеливания алгоритма общей рекурсии 1-го порядка.Редукция - упрощение, в биологии уменьшение размера органа вплоть до его полногоисчезновения.
Циклическая редукция - алгоритмы численного анализа дляраспараллеливания последовательных алгоритмов, основанный на последовательном,циклическом применении параллельных вычислений, число которых на каждом этапеуменьшается (делится пополам).Общей линейной рекурсией первого порядка называется система уравнений вида:X1 = D1X2 = X1 * A2 + D2Xi = Xi-1 * Ai + DiXn = Xn-1 * An + Dnв общем виде: Xi = Xi-1 * Ai + Di, i = 2,3,...n, X1 = D1Последовательный алгоритм вычислений может быть записан так:X(1) = A(1) + D(1)DO i = 2,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 необходимо модифицироватьалгоритм, например, по аналогии с алгоритмами суммирования.176Очевидно, что вычисления 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 = DiЕсли индекс 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))ENDDOПредставление машинных чисел.Для хранения и обработки данных в ЭВМ используется двоичная система, так как онатребует наименьшего количества аппаратуры по сравнению с другими системами.
Всеостальные системы счисления применяются только для удобства пользователей.Перевод числа из одной системы в другую выполняется по универсальному алгоритму,заключающемуся в последовательном делении целой части числа и образующихся целыхчастных на основание новой системы счисления, записанное в исходной системе счисления,и в последующем умножении дробной части и дробных частей получающихсяпроизведений на то же основание, записанное в исходной системе счисления.Разряд двоичного числа представляется в ЭВМ некоторым техническим устройством,например, триггером, двум различным состояниям которого приписываются значения 0 и 1.Группа таких устройств, предназначенная для представления в машине многоразрядногочисла, называется регистром.Структура двоичного регистра, представляющего в машине n-разрядное слово:n-1n-2...10Отдельные запоминающие элементы пронумерованы от 0 до n-1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
