Параллельная обработка данных 14.12.2000 В.А. Фисун /ВМиК МГУ/ СОДЕРЖАНИЕ Параллельные алгоритмы 1. Введение 2. Измерения вычислительных алгоритмов 2.1. Мера параллелизма 3. Параллельный алгоритм суммирования 4. Параллельные формы рекурсивных алгоритмов 5. Каскадное суммирование 6. Согласованность параллельных алгоритмов 7. Циклическая редукция для решения уравнения рекурсии 1 порядка 8. Параллельные алгоритмы и производительность ЭВМ Вычисления на ЭВМ 1. Источники вычислительных погрешностей 2. Погрешности исходных данных 3. Формы представления чисел в ЭВМ 4. Числа с плавающей запятой 4.1. Представление систем с плавающей точкой в ЭВМ 5. Особенности арифметики с плавающей запятой 5.1. Нарушение алгебраических законов в плавающей арифметике 6. Точность плавающей арифметики 7. Погрешности округления при вычислениях 7.1. Погрешности выполнения арифметических операций 8. Оптимизационные преобразования программ 1. Балансировка дерева вычислений 2. Исключение общих подвыражений 3. Разворачивание циклов 9. Блокировка оптимизационных преобразований 10. Особенности вычисления выражений в Фортране 90 11. Погрешности асинхронного распараллеливания Параллельные алгоритмы 1. Введение Одно из формальных определений алгоритма следующее. Алгоритм - процесс последовательной обработки структур данных, протекающий в дискретном времени так, что в каждый следующий момент времени структура данных получается по заданным правилам по структуре данных величин, имевшихся в предыдущий момент. Структура элементарных шагов в определении алгоритма не оговари- вается, поэтому, правила преобразования величин могут допускать или предписывать параллельную их обработку. Алгоритм может быть параллель- ным, когда некоторые шаги обработки могут выполняются параллельно. Так, алгоритм сложения векторов может быть представлен как последова- тельный, в виде: Ci = Ai + Bi для i=1,2..n, или в матричной записи: C = A + B, семантика которого допускает параллельную обработку элементов векторов. 2. Измерения вычислительных алгоритмов Основной единицей измерения вычислительных алгоритмов является число операций над числами с плавающей запятой "флопов" (flop). Для реализации алгоритмов на параллельных вычислительных системах особый интерес представляет измерения параллелизма алгоритмов. 2.1. Мера параллелизма "Реальному миру присущ параллельный характер, в то же время наше математическое восприятие в течении 300 лет находилось под воздействи- ем, главным образом, последовательной математики, 50 лет - под воз- действием создания последовательных алгоритмов, 15 лет - под воздейс- твием программирования на последовательном Фортране." /К. Тербер 1976 г./ При реализации на современных вычислительных системах вычисли- тельных алгоритмов доля их параллельных вычислений непосредственно влияет на время их работы. "Степень параллелизма" /параллельная сложность/ численного алго- ритма называется число его операций, которые можно выполнить парал- лельно. Степень параллелизма алгоритма сложения векторов равна n. Операции, которые всегда могут быть выполнены на идеальной ЭВМ параллельно независимо от их количества, иногда называют операциями фиксированной глубины. Последовательный алгоритм сложения чисел: S = A1, S = S + Ai, i=2,..n имеет нулевую степень параллелизма. 3. Параллельный алгоритм суммирования Параллельно суммирование последовательности 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 Порядком суммирования можно управлять, используя принцип сохране- ния скобок: компилятор не должен менять последовательность вычислений, предписанных пользователем. Например: запись выражение в виде: (((((((A+B)+C)+D)+E)+F)+G)+H) запрещает суммирование сдваиванием. Замечание 3 Алгоритм сдваивания является примером широкого класса параллель- ных алгоритмов, называемых редукционными алгоритмами, иногда, операци- ями логарифмической глубины. / Редукция - упрощение, в биологии, уменьшение размера органа вплоть до его полного исчезновения./ В некоторых работах алгоритм суммирования методом сдваивания на- зываются также алгоритмом каскадных сумм. 4. Параллельные формы рекурсивных алгоритмов Рекурсия - последовательность вычислений, при котором, значение самого последнего терма в последовательности зависит от одного или несколько ранее вычисленных термов. Пусть группа вычислений может про- изводиться параллельно, использую результаты вычислений, выполненных на предыдущих этапах (полученных в виде начальных данных). Тогда, каж- дая группа вычислений называется "ярусом" параллельной формы, число групп - "высотой", максимальное число операций в группе "шириной" па- раллельной формы. Один и тот же алгоритм может иметь несколько предс- тавлений в виде параллельных форм, различающиеся как шириной, так и высотой. Редукционный алгоритм сдваивания для суммирования чисел с получением частных сумм может иметь вид: Данные А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 Высота параллельной формы равна трем, ширина - четырем, причем загрузка вычислителей (четырех) полная. В данном алгоритме производится вычисления пяти 'лишних' чисел по сравнению с последовательным алгоритмом. 5. Каскадное суммирование Примером параллельных алгоритмов, ориентированных на векторные вы- числители, может служить метод вычисления каскадных сумм (алгоритм ре- курсивного удвоения) для распареллеливания операций суммирования. Пусть необходимо просуммировать 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 левых элементов заполнены нулями. Практическая реализация алгоритма может исключить излишние операции сложения с нулем, однако, и после этого, по сравнению с последовательным алгоритмом, данный - требует лишние операции. Замечание: Такие параллельные формы можно строить также для любых ассоциа- тивных операций, например, умножения, поиск минимакса, умножения мат- риц. 6. "Согласованность" параллельных алгоритмов При конструировании параллельных алгоритмов следует иметь вви- ду, что они не эквивалентны с точки зрения машинных вычислений, устой- чивость параллельных алгоритмов хуже устойчивости последовательных. Для некоторых скалярных алгоритмов аналогичные параллельные могут быть выгодными только для задачи малой размерности, с ростом порядка задачи время работы параллельной версии может превзойти скалярный рас- - 6 - чет. Пусть число арифметических операций в параллельном алгоритме Р(n), а в эквивалентном ему наилучшим последовательном - S(n). Тогда, парал- лельный алгоритм, решающий задачу порядка n, "согласован" с последова- тельным алгоритмом для той же задачи, если отношений P(n)/S(n) остает- ся ограниченным при n -> @. Параллельный алгоритм не согласован, если P(n)/S(n) -> @ при n -> @. (@-бесконечность). Алгоритм рекурсивного удвоения (метод каскадных сумм) не согласо- ван, так как число операций в параллельной версии равно n * log n - n + 1 против n-1 последовательных операций, и (n*log n-n)/n -> @ при n -> @. Однако, для некоторых вычислителей данный алгоритм не бесполезен. Пусть сложение векторов длины n производится за время T = s+yn, а скалярная операция за m. Тогда, каскадное вычисление n-1 сумм производится за время s * log n + (y(n*logn -n+1), а последовательное - m(n-1). И если s=1000, y = 10, m = 200 наносекунд, скалярный алгоритм эф- фективней векторного при n 2**21. Некоторые времена: n t=P(n) t=S(n) 8 3170 1400 32 6190 6200 128 15*10**3 25*10**3 1024 0.1*10**6 0.2*10**6 2**21 419*10**6 415*10**6 7.Циклическая редукция для решения уравнения рекурсии 1 порядка Редукция - упрощение, в биологии уменьшение размера органа вплоть до его полного исчезновения. Циклическая редукция - алгоритмы числен- ного анализа для распараллеливания последовательных алгоритмов, осно- ванный на последовательном, циклическом применении параллельных вычис- лений, число которых на каждом этапе уменьшается (делится) пополам. Линейной рекурсией 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 Это система эквивалентна двухдиагональной системе уравнений Ax=d, где ┌ ─┐ ┌─ ─┐ │ 1 │ │ d1 │ A = │ -a2 1 │ d = │ . │ │ ....... │ │ │ │ -an 1 │ │ dn │ └ ┘ └─ ─┘ Последовательный алгоритм вычислений может быть записан так: X(1) = A(1) + D(1) DO i = 1,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 8. Параллельные алгоритмы и производительность ЭВМ В общем случае, ускорение параллельного алгоритма как мера парал- лелизма может быть определено как отношение Sp = <время выполнения ал- горитма на одном процессоре> / <время выполнение алгоритма на N про- цессорах>. Очевидно, что ускорение алгоритма сложения двух векторов размерности: Ci = Ai + Bi, i = 1,..,N с "идеальным" параллелизмом равно N. Однако, реальные задачи, кроме вычислений, которые могут выполнять- ся параллельно, содержат и чисто последовательный вычисления. С другой стороны, для практики представляет интерес не параллелизм, присущий алгоритму, а ускорение, реально получаемое при реализации алгоритма на конкретном оборудовании. Для грубой оценки ускорения с учетом степени параллелизма программы и числа мультипроцессоров используется формула, известная как закон Амдала. Закон Амдала показывает коэффициент уско- рения выполнения программы на параллельных системах в зависимости от степени распараллеливания программы. Пусть: N - число процессоров системы, P - доля распараллеливае- мой части программы, а S = 1-P - доля операций программы, выпол- няемых без совмещения по времени.( S+P = 1 , S,P >= 0) Тогда, по Амдалу, общее время выполнения программы на однопроцес- сорном вычислителе S+P, на мультипроцессоре: S+P/N, а ускорение при этом есть функция P: Sp = (S+P)/(S+P/N) = 1/(S+P/N) Из формулы закона Амдала следует,что при: P = 0 S = 1 - ускорения вычисления нет, а P = 1 S = 0 - ускорение вычислений в N раз Если P = S = 0.5, то даже при бесконечном числе процессоров уско- рение не может быть более чем в 2 раза. Однако, практика показала, что независимость N и P условна, ибо в ряде случаев можно для повышения P перепрограммировать задачу, напри- мер, увеличить ее размерность. Густавсон предложил версию масштабируемого или модифицированного за- кона Амдала: Sp = S + P*N Тогда, при P = S = 0.5 Sp = 0.5N + 0.5 Замечание: N - представленное как число процессоров мультисистемы, может быть:числом АЛУ в микропроцессоре, числом конвейерных степеней в АЛУ. Литература Хокни Р., Джессхоуп К. Параллельные ЗВМ. М.: Радио и связь, 1986.-392 с. Ортега Дж. Введение в параллельные и векторные методы решения ли- нейных систем. М. Мир 1991.-367 с. Вычисления на ЭВМ 1. Источники вычислительных погрешностей Первоначально вычислительные машины разрабатывались и использова- лись для автоматизации исключительно вычислительных работ (COMPUTER - вычислитель), т.е. для выполнения над действительными (целыми) числами четырех арифметических действий: +,-,*,/. Сейчас под вычислениями по- нимаются и обработка текстовой, графической информации, исчисления множеств, работа с графами, а доля чисто арифметических вычислений до- вольно небольшая. Тем не менее предметная область с арифметическими вычислениями была и остается одной из важнейших сфер применения ЭВМ. При этом имеет место парадокс /Г.К.Боровин/: современные ЭВМ из всего спектра задач менее всего приспособлены для выполнения арифмети- ческих вычислений из за способа представления чисел в памяти ЭВМ. ЭВМ допускают корректное представления только конечных и конструктивных объектов, т.е. таких объектов, которые могут быть представлены после- довательностью конечной длины, например, символами некоторого, также конечного, алфавита. Другое дело - работа с числами. Так, в машине нельзя представить не только все трансцендентные и иррациональные чис- ла, но даже все рациональные числа. Даже действительные числа могут быть представлено только конечным, хотя может быть и очень большим подмножеством. Обычно. в ЭВМ используются две формы представления чи- сел: в форме чисел с плавающей запятой и в форме чисел с фиксированной запятой. Над этими множествами чисел и определен класс вычислений, на- зываемый - "вычислениями на ЭВМ". Некорректные в общем случае, и неу- бедительные с точки зрения "чистой математики", эти вычисления обеспе- чивают интерпретацию отображений общих представлений об окружающем ми- ре в виде конкретных моделей и алгоритмов. В общем случае, источники ошибок, возникающие при решении вычис- лительных задач на ЭВМ, можно условно разделить на: А. Ошибки, возникающие при формализации задач предметной области - неточности используемой математической модели, - погрешности используемого приближенного метода, - устойчивость вычислительных алгоритмов. B. Ошибки вычислительных операций - ошибки в исходных данных, - погрешности выполнения арифметических операций. - погрешности округления при вычислениях, С. Погрешности параллельных вычислений - погрешности параллельного аппаратного оборудования, - погрешности программного обеспечения. 2. Погрешности исходных данных Исходные данные, выражающие, обычно значения тех или иных физи- ческих величин, носят приближенный характер, содержат ошибку измере- ния. Число x, которое принимается принимается за истинным значением величины X, называется ее приближенным значением, абсолютная величина разности между ними - "абсолютная погрешность" (ошибку): Dx = |X-x|. Так как истинное значение x обычно неизвестно, под Dx понимается пре- дельная абсолютная погрешность, число, не меньшее абсолютной погреш- ности. "Относительная погрешность" данных определяется как величина: d =Dx/X. Для приближенного числа pi = 3.14 предельная абсолютная погреш- ность равна 0.0016, относительная - 0.00051 или 0.05%. Абсолютная пог- решность приближенного числа определяется числом десятичных знаков в его записи, относительная - количеством значащих цифр в числе. (Знача- щими цифрами являются все цифры числа, кроме тех нулей, которые упот- ребляются для определения места других цифр в десятичной дробе или же замещают неизвестные цифры. Так, в записи 0.040 значащими цифрами яв- ляются 40) 3. Формы представления чисел в ЭВМ Формы представления чисел в ЭВМ определяются правилами апроксима- ции действительных чисел посредством конечных множеств машинных предс- тавлений. Формы представления чисел могут отличаться диапазоном и точ- ностью представления чисел. Диапазон представления характеризуется са- - 11 - мым большим (M) и самым малым (m) по абсолютной величине из машинных чисел. (В качестве диапазона, иногда, рассматривают величину: v = log(b) (M/m), где b - основание логарифма, равное базе системы счисле- ния. Здесь предполагается использование позиционной системы счисления для представления чисел. ). Точность представления оценивается абсо- лютной разностью машинных чисел: D = |a2-a1| и относительной: d = |(a2-a1)/a1|, где a1,a2 - значения двух последовательных машинных чи- сел, таких, что a1=/=0 и |a2|>|a1|. 4. Числа с плавающей запятой Подмножество вещественных чисел, которое может быть представлено в ЭВМ в форме чисел с плавающей запятой, принято обозначать буквой F и определять его элементы для конкретной архитектуры - "машинные числа", (по Форсайту и др.) четырмя целочисленными параметрами: базой b, точ- ностью t и интервалом значений показателя [L,U]. Множество F содержит число нуль и все f числа вида: f = (+/-).d1d2...dt * b**e, где е назы- вается показателем, число .d1d2...dt = (d1/b+ ....+dt/(b**t)) - дроб- ной частью - мантиссой, причем: 0<=di Задача. Написать программу, определяющую количество разрядов, ис- пользуемых для представления мантиссы чисел с плавающей запятой. (Пусть на испытываемой ЭВМ мантисса числа хранится в нормализованном виде 1A2A3...An). 7. Погрешности округления при вычислениях При выполнении арифметических операций на ЭВМ могут появляться числа с большим количеством значащих цифр, чем у исходных чисел. и большим, чем может быть представимо на данной ЭВМ. Например, при умно- жении, число значащих цифр может удвоиться. Поэтому необходимо прово- дить округление результата вычислений. Простейший способ округления состоит в отбрасывания младших разря- дов. Пусть при вычиcлении получен неотрицательный результат (q-ичная дробь): X = 0.An A(n-1) A(n-2)....As A(s-1) A(s-2)....A1 . Тогда,округленное число есть: Xs= 0.An A(n-1)A(n-2)....As , а ошибка округления (абсолютная):Dx=|Xs-X|<=q**(-[n-(s-1)]), где n-(s-1) число значащих цифр в Xs. Максимально возможная относительная ошибка при этом будет равна: dx = Dx/X <= (q**(-[n-(s-1)]))/(1/q) = q**(-(n-s)). Другим общепринятым способом округления считается "симметричное" округление, при котором: Xs = Xs + q**(-(n-s)), если |Xs-X| >= 0.5**q(-(n-s)) и Xs = Xs, если |Xs-X| < 0.5**q(-(n-s)) При этом способе округления максимально возможное значение относитель- ной ошибки: dx <= 0.5*q**(-(n-s)+1). 7.1. Погрешности выполнения арифметических операций Формулы оценки абсолютной и относительной погрешности арифметичес- ких операций. 1. Сложение: X=X1+X2 X1>0 , X2>0 Абсолютная погрешность: Dx = Dx1 + Dx2 , относительная: dx = dx1 + dx2 2. Вычитание: X=X1-X2 X1>X2>0 Абсолютная погрешность:Dx=Dx1 + Dx2, относительная:dx=(X1*dx1 + X2*dx2)/X Если X1 >> (много больше) X2, то dx (почти равно) dx1. Если X1 (почти равно) X2, то dx будет очень велико. При вычитании близких по величине чисел получается большая потеря верных знаков. 3. Произведение: X = X1+X2 Погрешности: Dx = (X/X1)*Dx1 + (X/X2)*Dx2 dx = dx1 + dx2 4. Частное двух величин: X = X1/X2 Погрешности:Dx = (|X2|*Dx1 + |X1|*Dx2)/X2**2 , dx = dx1 + dx2 Формулы дают выражения для определения ошибки результата каждого из 4 арифметических действий как функции от величины чисел, участвую- щих в операциях, и абсолютных ошибок для них (например, погрешностей исходных данных). Для определения полной ошибки результата нужно к этим ошибкам отдельно добавить ошибки округления. Пример расчета полной ошибки для суммирования положительных чисел (Г.К. Боровин). Формула полной ошибки для суммирования положительных чисел Ai(i=1,..,n) имеет вид: Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , где dai - относительные ошибки представления чисел в ЭВМ, а di - относи- тельные ошибки округления чисел при каждой следующей операции сложе- ния. Пусть: все dai = da и di = d , a Ks = A1+A2+..+An, тогда: Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An] Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, сум- мируемые вначале. Следовательно, если суммируемые положительные числа упорядочить по возрастанию, максимально возможная ошибка суммы будет минимальной. Изменяя порядок суммирования чисел можно получать различ- ные результаты. Но если даже слагаемые отличаются друг от друга незна- чительно, на точность результата может оказать влияние способ суммиро- вания. Пусть суммируются 15 положительных чисел, тогда ошибка резуль- тата: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15). Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается. Пусть слагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em = max(ei), d - ошибка округления при вы- полнении арифметической операции сложения. Если провести суммирование этих чисел по группам (три группы по четыре числа и одна группа из трех чисел), то ошибки частных сумм име- ют вид: Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em) Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em) Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em) Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em) а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньше Dss. Итак суммирование по группам дает меньшую ошибку результата. Например, разделив процесс суммирования массива положительных чи- сел на параллельные процессы, и затем получив сумму частных сумм, мож- но получить результат, отличный от последовательного суммирования в одном процесс. 8. Оптимизационные преобразования программ Оптимизационные преобразования программ для их оптимального вы- полнения на конвейерных вычислителях могут проводиться системами прог- раммирования. Эти преобразования, алгебраически эквивалентные, могут нарушить порядок вычислений, предписанный исходным текстом программы. Последствия таких преобразований обсуждались выше. Наиболее характер- ные преобразования следующие. 1. Балансировка дерева вычислений Балансировка дерева вычислений (tree-height reduction or balan- cing) выражений позволяют использовать конвейерное АУ без пропуска рабочих тактов. Так, вычисление суммы вещественных чисел: A+B+C+D+E+F+G+H, будет запрограммировано как последовательность опера- ций: (((A+B)+(C+D))+((E+F)+(G+H))); это нарушает заданную по-умолчанию последовательность вычислений с накоплением одной частной суммы и мо- жет повлиять на результат. 2. Исключение общих подвыражений Алгоритмы исключения общих подвыражений (Common subexpession elimi- nation) также могут изменить порядок вычислений. Если компилятор распознает в выражениях повторяющееся вычисление, то это вычисление производятся один раз, его результат сохраняется на регистре, и в дальнейшем используется этот регистр. Тем самым исключа- ется избыточность вычислений. X = A + B + C + D ----> REG = B + C Y = B + E + C X = A + D + REG Y = E + REG 3. Разворачивание циклов Разворачивание циклов (loop unrolling) - расписывание цикла пос- ледовательностью операторов присваивания: либо полностью, либо размно- жение тела цикла с некоторым коэффициентом (фактором) размножения. Производится частичное или полное разворачивание цикла в последо- вательный участок кода. При частичном разворачивании используется так называемый фактор разворачивания (который можно задавать в директиве компилятору). DO I=1,100 DO I=1,100,4 A(I) = B(I) + C(I) A(I) = B(I) + C(I) ENDDO A(I+1) = B(I+1) + C(I+1) A(I+2) = B(I+2) + C(I+2) A(I+3) = B(I+3) + C(I+3) ENDDO При этом преобразовании снижается количество анализов итерацион- ной переменной. Данный алгоритм также может привести к нарушению пред- писанного первоначально порядка вычислений. Например: DO I=1,10 DO I=1,10,2 S = S + A(I) S = S + A(I) ENDDO S1 = S1 + A(A+1) ENDDO S = S + S1 Здесь, суммирование проводится отдельно для четных и нечетных эле- ментов с последующем сложением частных сумм. 9. Блокировка оптимизационных преобразований Для блокировки оптимизационных преобразования в компиляторах, обычно, предусматриваются опции (режимы), "флаги" , которые можно ис- пользовать при получении объектного кода. Некоторые предупредительные указания предусматриваются в стиле написания программ, так, в Фортране 90 концепция сохранения скобок оговорена стандартом языка. 10. Особенности вычисления выражений в Фортране 90 (стандарт) 7.1.7. Выполнение операций "При вычислении выражения А+В, где А,В - массивы, процессор может вы- полнять по-элементные операции сложения в любом порядке" 7.1.7.1. Вычисление операндов "Процессор не обязательно вычисляет все операнды выражения или пол- ностью каждый операнд, если значения можно определить без этого. Так в выражении: X .GT. Y .OR. L(Z) не надо вычислять функцию L(Z), если X больше Y." 7.1.7.2. Целостность скобок "Для выражения: A+(B+C) процессор на должен вычислять математически эквивалентное выражения: (A+B)+C." 7.1.7.3. Выполнение числовых встроенных операций "... процессор может вычислять любое математически эквивалентное выражение при условии, что целостность скобок не нарушается." В стандарте языка Фортран 90 приводятся допустимые и не допустимые альтернативных формы преобразования выражений: Для целых i,j;вещественных и комплексных a,b,c; произвольных x,y,z разрешаются преобразования: и запрещаются: x+y -> y+x i/2 -> 0.5 *i x*y -> y*x x*i/j -> x*(i/j) -x+y -> y-x (x+y)+z -> (x+y+z) x+z+y -> y+(x+z) i/j/a -> i/(j*a) x*a/z -> x*(a/z) (x+y)+z -> x+(y+z) a/b/c -> a/(b*c) (x*y)-(x*z) -> x*(y-z) a/5.0 -> 0.2*a x*(y-z) -> x*y-x*z 11. Погрешности асинхронного распараллеливания При распределении вычислительной работы последовательной программы в среде параллельных асинхронных вычислителях также возможны погреш- ности, например, результат суммирование элементов массива, выполненное по частям с последующим суммированием частных сумм может отличаться от результата прямого суммирования. Литература Форсайт Дж., Малькольм М., Молер К. Машинные методы математичес- ких вычислений.-М.:Мир,1980 Голуб Дж., Ван Лоун Ч., Матричные вычисления.-М.:Мир,1999.-548с. Боровин Г.К., Комаров М.М., Ярошевский В.С. Ошибки-ловушки при программировании на фортране. М.: Наука. 1987.-144с. Вирт Н. Систематическое программирование. Введение.М.: Мир.1977