Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 10
Текст из файла (страница 10)
Всякий сегмент может работать только с одной паройоперандов, а в целом на конвейере в текущий момент времени могут находиться шесть пар операндов. Преимущество подобной сегментации в том,что результаты выдаются в 6 раз быстрее (а в общем случае в K, где K —число сегментов сумматора), чем в скалярном процессоре, который, получивпару операндов, не принимает новой пары, пока не вычислит результат дляпервой пары. Для реализации этой возможности ускорения нужно подаватьданные из памяти в процессор достаточно быстро, чтобы конвейер был всевремя загружен данными и работой.Параллельные компьютеры. В основе такого компьютера лежитидея использовать несколько процессоров, работающих сообща для решения одной задачи. Параллельный компьютер может иметь в своем составелибо очень простые процессоры, пригодные только для малых или ограниченных задач, либо набор полноценных процессоров, либо весьма мощныевекторые процессоры.
Все процессоры параллельного компьютера в каждыймомент времени выполняют одну и ту же команду (или все простаивают) подуправление главного процессора, называемого контроллером.Распараллеливание. Независимо от того, на какой аппаратуре реализуется тот или иной вычислительный алгоритм, он обладает собственной,ему присущей характеристикой, показывающей возможности его распараллеливания.Определение 3.2.
Степенью параллелизма численной задачи называется число ее операций, которые можно выполнять параллельно.563.2 Распараллеливание вычисленийПример 3.1. Пусть требуется сложить два n-мерных вектора a и b.Сложения их элементовai + bi ,i = 1, . . . , n(3.3)независимы и потому могут выполняться параллельно. Степень параллелизма этого алгоритма равна n.Пример 3.2. Пусть требуется сложить n чисел a1 , . . . , an . Обычныйпоследовательный алгоритмs := a1 ,s := s + ai ,i = 1, .
. . , nне пригоден для параллельных вычислений. Однако в самой задаче заключен немалый параллелизм. Можно разбить операнды на «двойки», т. е. складывать их по двое на каждом этапе операции. Полностью эффект этой идеипроявляется, когда число операндов равно степени двойки, т.е. n = 2q . Если,например, q = 3, то все сложение займет q = 3 этапа, на каждом этапе действия выполняются параллельно, как показано на рис. 3.3.a1a2a1 + a2a3a4a3 + a4a1 + a2 + a3 + a4a5a6a5 + a6a7a8a7 + a8a5 + a6 + a7 + a8a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8Рис.
3.3. Сложение n чисел методом сдваивания для n = 8 [8]Очевидно, на первом этапе степень параллелизма равна n/2, на второмn/4 и т. д. В связи с этим приходим к обновленному определению.Определение 3.3. Средней степенью параллелизма численной задачиназывается отношение общего числа операций ее вычислительного алгоритма к числу последовательных этапов алгоритма.573 Векторно-ориентированные алгоритмы LU-разложенияДля приведенного примера 3.2 алгоритма сдваивания в задаче сложенияn чисел средняя степень параллелизма равна 2q − 1 n − 11 n n+ + ··· + 1 ==,q 2 4qlog nтогда как в предыдущем примере 3.1 средняя степень параллелизма максимальна. Этот алгоритм (3.3) обладает «идеальным» параллелизмом, в товремя как для алгоритма на рис. 3.3 средняя степень параллелизма в log nраз меньше идеальной.3.3Параллельное умножение матрицы на векторПусть A — матрица размера (m × n), а x — вектор длины n.
Тогда(a1, x)Ax = · · · ,(3.4)(am , x)где ai — i-я строка матрицы A, а (ai , x) — обычное скалярное произведениевекторов ai и x. Каждое из m имеющихся здесь скалярных произведений,как известно, требует суммирования n поэлементных произведений aij xj .Как показано в предыдущем подразделе, такое суммирование можно распараллеливать сдваиванием, но такой параллелизм вычисления каждого отдельного скалярного произведения так или иначе неидеален. Однако m скалярных произведений в (3.4) можно вычислять параллельно. Другой способумножения матрицы на вектор дается формулойAx =nXx j aj ,(3.5)j=1где aj теперь обозначает j-й столбец матрицы A.Различие представлений (3.4) и (3.5) можно рассматривать как различиедвух способов доступа к данным в памяти, что показывают две программына рис.
3.4. Программа слева на рис. 3.4 реализует метод (3.4), тогда какпрограмма справа реализует метод (3.5), и различие здесь только в порядкеиндексов для циклов. Алгоритм, основанный на представлении (3.5), записывается так:y = 0,58для j от 1 до n выполнить y = y + xj aj .3.4 Параллельное LU-разложениеyi = 0Для i = 1 до mДля j = 1 до nyi = yi + aij xjyi = 0Для j = 1 до nДля i = 1 до myi = yi + aij xjРис.
3.4. ij (слева) и ji (справа) формы матрично-векторного умножения [8]Как выше (в подразд. 3.1) говорилось, такая операция типа «вектор плюспроизведение вектора на число», называется триадой (или операцией saxpy);некоторые векторные компьютеры выполняют ее особенно эффективно.Сравнение приведенных способов умножения матрицы на вектор показывает, что на одних векторных компьютерах предпочтителен один способ,на других — другой; многое определяется также и способом хранения данных в памяти.
Предположим, что матрица A хранится по столбцам; такоесоглашение в отношении двумерных массивов принято в Фортране. (В других языках, например в Паскале, двумерные массивы хранятся по строкам.)Тогда векторы, требуемые для алгоритма (3.5), располагаются в последовательно адресуемых ячейках памяти, в то время как для алгоритма (3.5)строки будут представлять векторы с шагом m. Однако в векторных компьютерах часто существует ограничение на доступ к векторам: в качествеоперандов для векторных команд допускаются только векторы с шагом 1(т. е.
такие, которые располагаются в последовательно адресуемых ячейкахпамяти). Поэтому, если матрица A хранится по столбцам, то эти соображения, связанные с памятью, усиливают аргументацию в пользу алгоритма(3.5). Если же матрица A хранится по строкам, то предпочтительней можетоказаться алгоритм (3.4). Только детальный анализ может показать, какойвыбор следует сделать для конкретной машины.3.4Параллельное LU -разложениеДля распараллеленных вычислений нужны соответствующие параллельные или векторые компьютеры. С середины 70-х годов 20-го столетия фирмаCRAY Research, Inc.
производит векторные компьютеры, которые могут служить примером процессоров типа «регистр–регистр». Под этим подразумевается, что существуют векторные команды, для которых операндами являются векторы. Эти команды получают свои операнды из очень быстрой памяти, именуемой векторными регистрами, и запоминают результаты опять593 Векторно-ориентированные алгоритмы LU-разложениятаки в векторных регистрах.
Для операции сложения векторов это показанона рис. 3.5.Памятьc=a+bba+КонвейерВекторные регистрыРис. 3.5. Операция сложения в компьютере типа «регистр–регистр» [8]Предполагается, что каждый векторный регистр состоит из некоторогочисла слов. Например, в машинах CRAY имеется восемь векторных регистров, каждый емкостью в 64 числа с плавающей точкой. До начала сложения операнды загружаются из оперативной памяти в регистры. Послезавершения сложения векторный результат переписывается из регистровойпамяти в оперативную память. Для таких машин желателен иной подход корганизации LU -разложения.Исследуем вначале характер обменов во внутреннем цикле столбцовогоалгоритма LU -разложения на рис.
3.2. Для простоты предположим, чтостолбец матрицы A полностью вкладывается в векторный регистр, и начнем с рассмотрения случая, когда на фоне вычислений может выполнятьсятолько загрузка или только запись в память. Несколько первых операцийуказаны в следующем списке:Сформировать первый столбец матрицы L.Загрузить второй столбец матрицы A.(Модифицировать второй столбец матрицы A;загрузить третий столбец матрицы A.Записать в память модифицированный второй столбец.(Модифицировать третий столбец матрицы A;загрузить четвертый столбец матрицы A.(3.6)(3.7)(3.8)..................Согласно (3.6), загрузка следующего столбца матрицы A совмещаетсяс модификацией текущего столбца.
Но затем возникает задержка при записи модифицированного второго столбца из регистра в память. Можно так603.4 Параллельное LU-разложениемодифицировать алгоритм, чтобы устранить задержку, вызванную записьюв память (3.7). Идея состоит в том, чтобы выполнять необходимую обработку для j-го столбца полностью, прежде чем переходить к (j + 1)-мустолбцу. При этом обработка каждого из остальных столбцов матрицы Aоткладывается до тех пор, пока не наступит время придать этому столбцуокончательный вид. Псевдокод данного алгоритма приведен на рис. 3.6.Для j = 2 до nДля s = j до nls,j−1 = as,j−1 /aj−1,j−1Для k = 1 до j − 1Для i = k + 1 до naij = aij − lik akjРис. 3.6. Столбцово ориентированная схема L̄U-разложения с отложенными модификациями (jki-алгоритм, см.
с. 64) [8]Опишем несколько первых операций j-го шага вычислений, показываятаким образом характер обменов с памятью:Загрузить первый столбец матрицы L.Загрузить j-й столбец матрицы A.(Модифицировать j-й столбец матрицы A; загрузить второй столбец матрицы L.(3.9)(Модифицировать j-й столбец матрицы A; загрузить третий столбец матрицы L...................Заметим, что в алгоритме (3.9) не производится записей в память, покався работа с j-м столбцом матрицы A не завершена. Столбцы матрицы Lвсе время должны загружаться в регистры, но эти загрузки идут на фоневычислений. Только в начале и в конце каждого шага происходят задержкидля загрузок и(или) записей.
Вполне вероятно, что транслятор не сумеетраспознать возможности оставить текущий j-й столбец в регистре; в этомслучае результат, требуемый от алгоритма на рис. 3.6, либо достигается спереходом к программированию на языке ассемблера, либо аппроксимируется путем развертывания циклов. Еще одна потенциальная проблема приреализации данного алгоритма заключается в том, что длины векторов при613 Векторно-ориентированные алгоритмы LU-разложениямодификациях непостоянны: на j-м шаге мы модифицируем j-й столбец,используя n − 1 последних элементов столбца 1, далее n − 2 последних элементов столбца 2 и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
