Ответы 190 страниц (1184228), страница 38
Текст из файла (страница 38)
-Декларативный язык Норма
-Компилятор с языка Норма
-Конфигуратор программ на языке Норма
-Отладчик программ на языке Норма
-Пользовательский Windows-интерфейс
Особенности выполнения арифметических выражения на ЭВМ. Распараллеливание вычислительных алгоритмов. Метод распараллеливания алгоритма общей рекурсии 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-го порядка.
Редукция - упрощение, в биологии уменьшение размера органа вплоть до его полного исчезновения. Циклическая редукция - алгоритмы численного анализа для распараллеливания последовательных алгоритмов, основанный на последовательном, циклическом применении параллельных вычислений, число которых на каждом этапе уменьшается (делится пополам).
Общей линейной рекурсией первого порядка называется система уравнений вида: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
Последовательный алгоритм вычислений может быть записан так:
X(1) = A(1) + D(1)
DO i = 2,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, Векторная нотация Хокни для данного алгоритма: X = D
DO L = 1,LOG2(N)
X = A * SHIFTR(X,2**(L-1)) + X
A = A * SHIFTR(A,2**(L-1))
ENDDO
Представление машинных чисел.
Для хранения и обработки данных в ЭВМ используется двоичная система, так как она требует наименьшего количества аппаратуры по сравнению с другими системами. Все остальные системы счисления применяются только для удобства пользователей.
Перевод числа из одной системы в другую выполняется по универсальному алгоритму, заключающемуся в последовательном делении целой части числа и образующихся целых частных на основание новой системы счисления, записанное в исходной системе счисления, и в последующем умножении дробной части и дробных частей получающихся произведений на то же основание, записанное в исходной системе счисления.
Разряд двоичного числа представляется в ЭВМ некоторым техническим устройством, например, триггером, двум различным состояниям которого приписываются значения 0 и 1. Группа таких устройств, предназначенная для представления в машине многоразрядного числа, называется регистром.
Структура двоичного регистра, представляющего в машине n-разрядное слово:
n-1 n-2 ... 1 0
Отдельные запоминающие элементы пронумерованы от 0 до n-1. Количество разрядов регистра определяет точность представления чисел. Путем соответствующего увеличения числа разрядов регистра может быть получена любая точность вычислений, однако это сопряжено с увеличением количества аппаратуры (в лучшем случае зависимость линейная, в худшем - квадратичная).
В ЭВМ применяются две основные формы представления чисел: полулогарифмическая с плавающей запятой и естественная с фиксированным положением запятой.
При представлении чисел с фиксированной запятой положение запятой закрепляется в определенном месте относительно разрядов числа и сохраняется неизменным для всех чисел, изображаемых в данной разрядной сетке. Обычно запятая фиксируется перед старшим разрядом или после младшего. В первом случае в разрядной сетке могут быть представлены только числа, которые по модулю меньше 1, во втором - только целые числа.
Для кодирования знака числа используется старший ("знаковый") разряд.
При выполнении арифметических действий над правильными дробями могут получаться двоичные числа, по абсолютной величине больше или равные единице, что называется переполнением разрядной сетки. Для исключения возможности переполнения приходится масштабировать величины, участвующие в вычислениях.
Диапазон представления правильных двоичных дробей:
2-(x-1) < A < 1 - 2-(x-1).
Числа, которые по абсолютной величине меньше единицы младшего разряда разрядной сетки, называются машинным нулем.
Диапазон представления целых двоичных чисел со знаком в n-разрядной сетке:
0 < A < 2-(x-1)-1.
Использование представления чисел с фиксированной запятой позволяет упростить схемы машины, повысить ее быстродействие, но представляет определенные трудности при программировании. В настоящее время представление чисел с фиксированной запятой используется как основное только в микроконтроллерах.
В универсальных ЭВМ основным является представление чисел с плавающей запятой. Представление числа с плавающей запятой в общем случае имеет вид:
A = m * N p,
где N - основание системы счисления,
p - целое число, называемое порядком числа A,
m - мантисса числа A (¦m¦<1).
Так как в ЭВМ применяется двоичная система счисления, то
A = m * 2 p,
причем порядок и мантисса представлены в двоичной форме.
Двоичное число называется нормализованным, если его мантисса удовлетворяет неравенству
1/2< ¦ m ¦ < 1 .
Неравенство показывает, что двоичное число является нормализованным, если в старшем разряде мантиссы стоит единица. Например, число 0,110100*10100 - нормализованное, а 0,001101*10110 - ненормализованное.
Ситуация, когда в процессе вычислений получено число с ¦m¦>1 называется переполнением разрядной сетки.
Нормализованное представление чисел позволяет сохранить в разрядной сетке большее количество значащих цифр и, следовательно, повышает точность вычислений. Однако современные ЭВМ позволяют, при необходимости, выполнять операции также и над ненормализованными числами.
Диапазон представления нормализованных двоичных чисел, взятых по абсолютному значению, удовлетворяет неравенству:
2-1*2-(2k-1) < A < (1 - 2-l)*22k-1,
где l - число разрядов мантиссы;
k - число разрядов порядка;
2-1 - наименьшее значение нормализованной мантиссы;
1 - 2-l - наибольшее значение нормализованной мантиссы.
Широкий диапазон представления чисел с плавающей запятой удобен для научных и инженерных расчетов. Для повышения точности вычислений во многих ЭВМ предусмотрена возможность использования формата двойной длины, однако при этом происходит увеличение затрат памяти на хранение данных и замедляются вычисления.
Представление отрицательных чисел в ЭВМ.
Для кодирования знака двоичного числа используется старший ("знаковый") разряд (ноль соответствует плюсу, единица - минусу). Такая форма представления числа называется прямым кодом. Формула для образования прямого кода правильной дроби имеет вид:
Примеры:
A = 0,110111 --> [A]пр = 0,110111
A = -0,110111 --> [A]пр = 1 - (-0,110111) = 1,110111
Прямой код целого числа получается по формуле:
где 10 - число 2 в двоичной системе счисления,
n - количество позиций в разрядной сетке.
Например, при n=8
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
