XXI Зарубин B.C. Математическое моделирование в технике (1081441), страница 58
Текст из файла (страница 58)
Напомним*, что действительное число х в памяти ЭВМ представлено в виде х = хд Лр, где  — основание системы счисления (для двоичной системы А = 2, для десятеричной Л = 10 и т.п.), д е [1/ль, 1) — правильнал дробь, называемая мантиссой числа х, р Е Ж вЂ” целое число, называемое порядком числа х. Такая форма записи числа носит название представления с плавающей запятой (или с плавающей точкой), причем на каждое число отведено определенное количество битов (элементов, принимающих только одно из двух значений — 0 или 1), образующих машинное слово.
384 7. АЛГОРИТМИЗАЦИЛ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ Рассмотрим сначала этапы выполнения операции сложения двух чисел х = д Вр* и у = др Лрв, которой соответствует формула хну — Н (Чх+йр'Н" ). х Сравнение Рл Р 9 порядков х Сдвиг Сложение я+9 Нормали- х+ плавающей у мангиоо эация эапято Рис. 7.2 При выполнении отдельно взятой операции сложения двух чисел в каждый текущий момент времени занято и активно работает лишь одно из четырех рассмотренных устройств. При этом производительность зависит от суммарного времени прохождения информации через все четыре устройства.
Время т выполнения каждого этапа обычно одинаково и носит название тактового периода. Например, при сложении двух векторов с п координатами потребуется время 1,(п) = япт, где я— число тактов при выполнении сложения одной пары координат (в данном случае л = 4). Об ЭВМ, выполняющей вычисления описанным способом, говорят, что она имеет последовательнуго архитектуру. Эта операция состоит из четырех этапов, каждый из которых выполняет специальное устройство. На первом этапе оба числа поступают в устройство, в котором происходит сравнение их порядков, например, по разности р — рр (рис.
7.2). На втором этапе осуществляется сдвиг плавающей запятой, например, у числа х таким образом, чтобы складываемые числа имели одинаковый порядок (запись числа х принимает вид х). После этого на третьем этапе происходит сложение мантисс, а на четвертом результат подвергается так называемой нормализации, состоящей в приведении его мантиссы к допустимому промежутку значений.
7.3. Алгоритмы векторно-конвейерных вычислений 385 ава+Ь а,+Ьг, ге1 ам а Сравнение Ра, Ра СДвиг '+' плавающей порндаов Сложение мантисс Нормали- аацил ЬИ2 Рис. 7.3 !3 — 9102 При конвейерном сложении координат двух векторов а и 6 все четыре устройства работают одновременно (рис. 7.3). Пока первое устройство сравнивает порядки координат а;+2 и Ьеьз этих векторов, второе устройство сдвигает плавающую запятую у одной из (1+ 1)-х координат (например, у а!+1, переводя ее запись в форму о;+1), третье складывает мантиссы чисел о! и Ь,, а четвертое нормализует сумму а; 1+6, 1.
В зто же время происходит запись результата с; 2 = а; 2+ Ь, 2, являющегося (1 — 2)-й координатой вектора с = а+ Ь, а на входе в первое устройство уже подготовлены координаты аг рз и Ьеьз складываемых векторов. Таким образом, в данном случае на выполнение одного сложения требуется один тактовый период вместо четырех при последовательной архитектуре ЭВМ, а для сложения двух векторов с 92 координатами потребуется время 1*(22) = лт+ (22 — 1) т (слагаемое лт равно времени получения первой суммы, после чего все четыре устройства начнут работать как конвейер).
При гг » л из сравнения 1*(92) с 1,(92) следует, что производительность ЭВМ в данном случае возрастает в в раз. Несложно представить таким же образом последовательность работы и взаимодействие устройств при выполнении скалярного умножения векторов или операции умножения вектора на число и сложения с другим вектором (см. пример 7.1). Эти устройства входят в состав векторных регистров, обменивающихся информацией с памятью компьютера при помощи инструкций загрузки вектора в регистр и записи вектора в память.
Архитектуру ЭВМ, выполняющей вычисления по такой схеме, называют гсонвейернон. 386 7. АЛГОРИТМИЗАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ Пусть векторный регистр одновременно может выполнять 1 этапов некоторой конвейеризованной векторной операции, причем выполнение любого из этапов соответствует одному такту. Если векторная операция является п-мерной, т.е. ее результат — это вектор с и координатами, и п < 1, то для ее выполнения потребуется время 1[п) = [д + п)т, где д— число тактов, необходимое для начальной загрузки векторного регистра.
Но при п > 1 загружаемые в регистр векторы должны быть представлены в виде нескольких кортежей длиной не более 1. Тогда получим [7.1) 1[п) = [и+ д[п/1]')т, где [и/1]' — наименьшее натуральное число, равное числу и/1 или большее его. Если для вычисления каждой координаты итогового результата требуется р флоп, то эффективная скорость векторноконвейерных вычислений равна е[п) = — = дп д ~[п) г(1+ х[п/1]') При измерении т в секундах получим е[п) в флопах в секун- ду [флоп/с). Пример 7.5. Рассмотрим процедуру векторно-конвейерных вычислений применительно к умножению матрицы А размера т х т на матрицу В размера т х и. Если при этом учитывать затраты времени лишь на вычисление скалярных произведений векторов с т координатами, то время, требуемое для перемножения этих матриц, в соответствии с [7.1) равно 1„= тпп[т+ д[т/1]')т.
Но алгоритм перемножения матриц можно построить иначе. Например, при фиксированных значениях у = 1, и и й = 1, т во внутреннем цикле по г = 1, т можно конвейеризовать опера- 7.3. Алгоритмы векторно-конвейерных вычислений 387 цию с!7 =с;7+а,ьбв вычисления элемента с; матрицы С =АВ с использованием операций умножения вектора на число и сложения результата с другим вектором (см. пример 7.1). Тогда получим 1 = пг(т+ !7[т/1]*)т. Если же в аналогичном алгоритме внутренний цикл провести по у' = 1, и, то будем иметь 1„= тт(п+ с7[п/1]*) т.
Ясно, что из трех рассмотренных алгоритмов следует выбрать оптимальный, соответствующий наименьшему из значений тп[т/!]', пт[т/1]* или тт[п/1]*. Сравнивая эти значения между собой, можно заключить, что в случае, когда 1 больше каждого из значений т, и и г, оптимальным будет алгоритм с наибольшей длиной внутреннего цикла. Если же 1 существенно меньше каждого из значений тп, и и г, то различие в затратах времени на перемножение матриц при использовании этих алгоритмов невелико. Оценка (7.1) не учитывает затраты времени на перемещение данных между памятью и регистрами в обоих направлениях. Важно, чтобы при таком перемещении эти данные занимали непрерывную область. Для вектора это означает, что расстояние между его последовательными координатами, измеренное в ячейках памяти, минимально. Это расстояние называют шаеом выборки.
Элементы матрицы обычно располагают в памяти по столбцам. Поэтому доступ к последовательным элементам в столбце матрицы можно осуществить наиболее рационально, т.е. с единичным шагом выборки, а доступ к последовательным элементам в строке уже не будет операцией с таким шагом. Так, среди рассмотренных в примере 7.5 алгоритмов лишь во внутреннем цикле по г = 1, т второго алгоритма выборка элементов а!е и с," матриц А и С происходит с единичным шагом (элемент бв матрицы В во внутреннем цикле фиксирован). Ясно, что при оценке суммарных затрат времени на перемножение матриц необходимо учитывать его затраты на перемещение данных, тем более если эти перемещения происходят не с единичным шагом выборки.
388 7. АЛГОРИТМИЗАЦИЯ МА ТЕМА ТИЧЕСКИХ МОДЕЛЕЙ 7.4. О распараллеливании матричных вычислений С возможностью распараллеливания алгоритмов связано повышение производительности ЭВМ, имеющих несколько процессоров и специальную архитектуру, обычно называемую матричной архитектурой. Объединение этих процессоров называют мультипроцессором (или матрицей процессороа).
Они имеют доступ либо к общей памяти ЭВМ, либо к своей локальной, называемой в этом случае распределенной памятью ЭВМ. Одновременное выполнение несколькими процессорами вычислений, относящихся к одной задаче, при соответствующей организации вычислений может ускорить решение этой задачи.
Распределение функций между процессорами зависит как от структуры алгоритма, так и от системы связи между процессорами. При сложении п чисел алгоритм вычислений наряду с последовательным суммированием слагаемых допускает несколько вариантов распараллеливания. Например, при п = 2, т Е 1ч', можно складывать слагаемые попарно, затем проводить по- парное сложение полученных результатов и т.д. Нетрудно установить, что общее число операций сложения равно и — 1 = = 2 — 1, т.е. совпадает с числом операций сложения при последовательном суммировании слагаемых.
Поэтому такой вариант распараллеливания, называемый каскадной схемой, не дает экономии времени при использовании ЭВМ с последовательной архитектурой. Но для мультипроцессора, состоящего всего из двух параллельно работающих процессоров, каскадную схему алгоритма сложения можно реализовать за т последовательньгх этапов. Применительно к операции сложения двух векторов си координатами (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
