4. 6.6.4. Результаты вычислительных экспериментов

Вычислительные экспериментыдля оценкиэффективностипараллельного алгоритма умножения матрицы на вектор при разбиении данных по столбцам проводились при условиях, указанных в п. 6.5.5. Результатывычислительных экспериментовприведены втаблице 6.3.

Размер матрицы	Последовательный алгоритм	Параллельный алгоритм
		2 процессора		4 процессора		8 процессоров
		Время	Ускорение	Время	Ускорение	Время	Ускорение
1000	0,0041	0,0022	1,8352	0,0015	3,1538	0,0008	4,9409
2000	0,016	0,0085	1,8799	0,0046	3,4246	0,0029	5,4682
3000	0,031	0,019	1,6315	0,0095	3,2413	0,0055	5,5456
4000	0,062	0,0331	1,8679	0,0168	3,6714	0,0090	6,8599
5000	0,11	0,0518	2,1228	0,0265	4,1361	0,0136	8,0580

Сравнение экспериментального времени выполнения эксперимента и времениT_p, вычисленного по соотношениям (6.14), (6.15), представлено втаблице 6.4и на рис.6.6и6.7. Теоретическое времявычисляется согласно (6.14), а теоретическое время– в соответствии с (6.15).

Рис. 6.6.  График зависимости теоретического и экспериментального времени выполнения параллельного алгоритма на четырех процессорах от объема исходных данных (ленточное разбиение матрицы по столбцам)

Размер матрицы	2 процессора			4 процессора			8 процессоров
1000	0,0022	0,0021	0,0021	0,0013	0,0013	0,0014	0,0008	0,0011	0,0015
2000	0,0085	0,0082	0,0080	0,0046	0,0044	0,0044	0,0029	0,0027	0,0031
3000	0,019	0,0177	0,0177	0,0095	0,0094	0,0094	0,0055	0,0054	0,0056
4000	0,0331	0,0313	0,0313	0,0168	0,0163	0,0162	0,0090	0,0090	0,0091
5000	0,0518	0,0487	0,0487	0,0265	0,0251	0,0251	0,0136	0,0135	0,0136

Рис. 6.7.  Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (ленточное разбиение матрицы по столбцам) для разных размеров матриц

7. 6.7. Умножение матрицы на вектор при блочном разделении данных

Рассмотрим теперь параллельный алгоритм умножения матрицы на вектор, который основан на ином способе разделения данных – на разбиении матрицы на прямоугольные фрагменты (блоки).

1. 6.7.1. Определение подзадач

Блочная схема разбиения матриц подробно рассмотрена в подразделе 6.1. При таком способе разделения данных исходная матрица Aпредставляется в виде набора прямоугольных блоков:

где A_ij, 0i<s, 0j<q, есть блок матрицы:

(здесь, как и ранее, предполагается, что p=s·q, количество строк матрицы является кратным s, а количество столбцов – кратным q, то есть m=k·s и n=l·q).

При использовании блочного представления матрицы Aбазовые подзадачи целесообразно определить на основе вычислений, выполняемых над матричными блоками. Для нумерации подзадач могут применяться индексы располагаемых в подзадачах блоков матрицыA, т.е. подзадача(i,j)содержит блокA_ij. Помимо блока матрицыAкаждая подзадача должна содержать также и блок вектораb. При этом для блоков одной и той же подзадачи должны соблюдаться определенные правила соответствия – операция умножения блока матрицыA _ijможет быть выполнена только, если блок вектораb'(i,j) имеет вид