рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Возведение в степень блочно-диагональных матриц

Работа сделанна в 2000 году

Возведение в степень блочно-диагональных матриц - раздел Математика, - 2000 год - Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры Возведение В Степень Блочно-Диагональных Матриц. Пусть Матрица А Имеет Блочно...

Возведение в степень блочно-диагональных матриц. Пусть матрица А имеет блочно-диагональный вид, т.е. где А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

– Конец работы –

Эта тема принадлежит разделу:

Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

Производительности современных ЭВМ недостаточно для обеспечения требуемого решения многих задач. Один из наиболее эффективных способов повышения производительности заключается… В параллельном программировании, так же как и в последовательном, существует много различных средств для создания…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Возведение в степень блочно-диагональных матриц

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Модель вычислений
Модель вычислений. Система FLOWer базируется на модели управления потоком данных. В данной модели вычислений программа представляется в виде ГПД. Вершины ГПД соответствуют отдельным процесса

Умножение матрицы на вектор
Умножение матрицы на вектор. Пусть А матрица mn, а х вектор длины n. Тогда произведение можно записать двумя способами или, где аi i-я строка матрицы А, аi i-й столбец матрицы А, а x, y скалярное п

Матричное умножение
Матричное умножение. Аналогично рассматриваются алгоритмы умножения матриц А и В. Пусть матрицы разбиты на блоки Пусть число процессоров р равно числу st блоков матрицы С. Тогда все блоки можно выч

Прямые методы решения линейных систем
Прямые методы решения линейных систем. Рассмотрим систему линейных уравнений Ax b с невырожденной матрицей А размера nn . 2.1. LU-разложение Постановка задачи Построим разложение мтрицы A LU, где L

Решение треугольных систем
Решение треугольных систем. Постановка задачи После выполнения LU-разложения нужно решать треугольные системы. Ly b, Ux y Процесс их решения назывантся прямой и обратной подстановками. Рассм

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги