Возведение в степень блочно-диагональных матриц. Пусть матрица А имеет блочно-диагональный вид, т.е. где Аii квадратная матрица.
Очевидно, что Аn можно вычислить следующим образом Тогда вполне естественно приписать каждый блок отдельному процессору. При этом, если размерности блоков сильно отличаются, возникает проблема балансировки нагрузки. Данную проблему можно разрешить при помощи динамического распределения блоков между процессами. Пусть все Аii матрицы размерности mm, тогда в системе из ps процессоров Положим p4, m10 и построим график Spn при различных значениях отношения TsendTmul. Видно, что рост производительности параллельной системы наблюдается как при больших значениях m, так и при больших значениях n. Вычислим оптимальное число процессоров p и построим график Spn, m при n5000, m10. Значение p определяется из уравнения, p 1 Отсюда Результаты эксперимента mt1n, m, секtpn, m, p2, секSpn10002131,1621097,9711,94111002235, 1781142,7291,95612003764,3201931,4111,94 913004898,5642506,9421,954 1.4. Ленточные матрицы Матрица А порядка n называется ленточной, если aij 0, i j 1, j i 2 Далее будем рассматривать лишь матрицы с симметричной лентой, для которых 1 2 . Таким образом, ненулевые элементы матрицы расположены только на главной диагонали и на 2 диагоналях, прилегающих к главной сверху и снизу.
Заметим, что если полуширина ленты для А равна, а для В равна, то полуширина ленты для АВ в общем случае будет равна. Пусть А матрица размерности nn с полушириной ленты , В матрица размерности nn с полушириной ленты. Причем А разбита на блоков Число ненулевых элементов матрицы B не превышает 21n, в блоке Ai 21m. В результирующей матрице будет не более 41n ненулевых элементов. В системе из p процессоров построим вычисление по следующей схеме первый процессор вычисляет А1В, второй А2В и т.д. Соответственно, матрицу А выгодно хранить по строкам, а матрицу В по столбцам.
В результате умножения получим матрицу, которая будет храниться в памяти по строкам.
На вычисление одного ненулевого элемента матрицы АВ затрачивается время не более 2 1Tmul. Тогда Видно, что ускорение Sp зависит от полуширины ленты и не зависит от n. Теперь вычислим оптимальное значение числа процессоров p и построим график функции Sp при 500. Значение p определяется из уравнения Отсюда Г Л А В А 2