ПОД (пособие) (1184372), страница 52
Текст из файла (страница 52)
N)));Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода,чистку циклов, слияние общих подвыражений, перенос участков повторяемости дляобеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла,втягивание константных вычислений, уменьшение силы операций, удаление копийагрегатных конструкций и др.Система программирования Норма.Язык Норма является специализированным языком и предназначен для спецификациичисленных методов решения задач математической физики. Изначально он былориентирован на решение задач математической физики разностными методами, однако,как показала практика, может быть использован для решения более широкого классавычислительных задач.Первоначально термин Норма расшифровывался следующим образом: НепроцедурноеОписание Разностных Моделей Алгоритмов.
Сейчас мы считаем уместной и другуютрактовку - это Нормальный уровень общения прикладного математика с ЭВМ: расчетныеформулы, полученные им в процессе решения прикладной задачи, почти непосредственноиспользуются для ввода в вычислительную систему и проведения счета.В записи на Норме не требуется никакой информации о порядке счета, способахорганизации вычислительных (циклических) процессов. Порядок предложений языкаможет быть произвольным -- информационные взаимосвязи выявляются и учитываютсятранслятором при организации вычислительного процесса.
Программа на языке Нормаможет рассматриваться как описание запроса на вычисление, а реализация этого запроса сучетом архитектуры ЭВМ и возможностей выходного языка - то есть синтез выходнойпрограммы - возлагается на транслятор.Выбор уровня языка Норма определяет характерную его черту - это язык с однократнымприсваиванием, то есть каждая переменная может принимать значение только один раз.Такие понятия, как память, побочный эффект, оператор присваивания, управляющиеоператоры в языке Норма отсутствуют по определению.Эти свойства, и некоторые другие ограничения (в первую очередь, на вид индексныхвыражений и способы описания индексных пространств), позволяют строго обосноватьразрешимость задачи синтеза выходной программы [2,3], так как в достаточно общейпостановке решение этой задачи приводит к значительным математическим трудностям она может оказаться NP-полной либо вообще неразрешимой.
С другой стороны,исследования, связанные с разработкой и применением языка Норма показывают, чтоимеющиеся ограничения приемлемы с практической точки зрения [5].173Программа на Норме состоит из одного или нескольких разделов. Разделы могут быть трехвидов - главный раздел, простой раздел и раздел-функция, вид раздела определяетсяключевыми словами MAIN PART, PART, FUNCTION соответственно.Разделы могут вызывать друг друга по имени и передавать данные при помощи механизмаформальных и фактических параметров, или через внешние файлы при помощи описанийINPUT и OUTPUT. Для каждого раздела справедливо правило локализации: имена,описанные в разделе, локализованы в этом разделе; понятие глобальных переменных вязыке отсутствует.Главный раздел обязательно должен присутствовать в программе на Норме и бытьединственным; формальных параметров он не имеет.
Вызовы главного раздела, а такжерекурсивные вызовы разделов запрещены. В заголовке раздела указывается имя раздела исписок формальных параметров. Формальные параметры должны быть описаны в телераздела при помощи declaration-of-scalar-variables, declaration-of-variables-on-domains илиdeclaration-of-externalПараметры-величины, указанные до ключевого слова RESULT в списке формальныхпараметров, являются исходными данными для вычислений, описываемых в разделе;параметры, перечисленные после - являются результатами вычислений. Один и тот жепараметр не может быть одновременно исходным и результатом: это приводит кпереприсваиванию значений переменным (повторному присваиванию), что запрещено вНорме.
В разделе-функции ключевое слово 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-го порядка.Редукция - упрощение, в биологии уменьшение размера органа вплоть до его полногоисчезновения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
