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