Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с

114 
Среды  разработки: Borland
 C++ Builder 5.0, Microsoft Visual 
Studio 6.0. 
Компиляторы: Borland
 C++ for Win32 Compiler 5.5, Microsoft 
32-bit C/C++ Optimizing Compiler, Intel
 C++ Compiler 5.0. 
Дополнительные средства: библиотека PLAPACK 3.0. 
Базовый алгоритм 
N
j
N
i
B
A
C
N
k
kj
ik
ij
,
,
,
,
1
1
1
=
=
=
∑
=
 
Оценка производительности 
Будем оценивать производительность по формуле R = (2*N
3
)/T. 
Реализация 1. 
Рассмотрим  следующую  простейшую  реализацию  алгоритма  ум-
ножения матриц: 
for (i=0;i  for (j=0;j    for (k=0;k       C[i][j]+=A[i][k]*B[k][j]; 
В  результате  проведенных  вычислительных  экспериментов  были 
получены следующие временные характеристики (время счета): 
                                Размер 
Компиляторы 
N=1000 N=1500 
Borland
 C++ for Win32 Compiler 5.5 
50,67 c 
145,53 c 
Microsoft
 32-bit C/C++ Optimizing Compiler 
37,91 c 
94,52 c 
Intel
 C++ Compiler 5.0 (включены оптими-
зирующие опции) 
39,15 c 
93,50 c 
 
Данная реализация имеет следующие показатели (в зависимости от 
компилятора):  минимальная  производительность Rmin = 39,5MFp, 
максимальная производительность Rmax = 72,2MFp. 
К очевидным недостаткам алгоритма следует отнести: 
•  большое количество итераций циклов (проблемы с ветвлениями); 
•  наличие  в  качестве  тела  цикла  сложного  выражения  (явно 
зависящего от всех трех переменных цикла); 
•  зависимость  текущей  итерации  от  предыдущей  итерации  (нельзя 
распараллелить); 
•  отсутствие  ориентации  на  принципы  работы  встроенной  кэш-
памяти Intel
 Pentium 4. 

 
115 
Реализация 2. 
Следующая реализация предлагает решение, устраняющее часть из 
вышеперечисленых  недостатков  и  позволяющее  использовать 
механизм  автоматического  распараллеливания  циклов  (векторизации) 
компилятором Intel
 C++ Compiler 5.0. 
for(i=0,i1=1,i2=2;i  for(j=0;j    p=&B[j][0]; 
    tmp=A[i][j]; tmp1=A[i1][j]; tmp2=A[i2][j]; 
    ci=&C[i][0]; ci1=&C[i1][0]; ci2=&C[i2][0]; 
    for(k=0;k       temp=p[k]; 
       ci[k]+=tmp*temp; 
       ci1[k]+=tmp1*temp; 
       ci2[k]+=tmp2*temp; 
}}} 
Временные характеристики: 
                         Размер 
Компиляторы 
N=1002 N=1500 
Borland
 C++ for Win32 Compiler 5.5 
22,44 c 
75,21 c 
Microsoft
 32-bit C/C++ Optimizing 
Compiler 
6,70 c 
22,89 c 
Intel
 C++ Compiler 5.0 (включены 
оптимизирующие опции) 
3,36 c 
10.33 c 
 
Данная  реализация  имеет  лучшие  показатели  (в  зависимости  от 
компилятора) 
по 
сравнению 
с 
предыдущей: 
минимальная 
производительность Rmin=89,1MFp, максимальная  производитель-
ность Rmax=653MFp. К достоинствам алгоритма следует отнести: 
•  устранение  зависимостей  от  внешних  индексов  во  внутреннем 
цикле; 
•  возможность распараллеливания команд во внутреннем цикле; 
•  ориентацию  на  принципы  работы  встроенной  кэш-памяти Intel 
Pentium
 4. 
 
Реализация 3. 
Следующая  реализация  является  наиболее  эффективной  среди 
рассмотренных. 

116 
for(k=0;k    b1=&B[k][0];  b2=&B[k+1][0]; 
    b3=&B[k+2][0]; b4=&B[k+3][0]; 
    b5=&B[k+4][0]; b6=&B[k+5][0]; 
    b7=&B[k+6][0]; b8=&B[k+7][0]; 
    b9=&B[k+8][0]; b10=&B[k+9][0]; 
    for(i=0;i      q=&C[i][0]; 
      t1=A[i][k]; t2=A[i][k+1]; 
      t3=A[i][k+2]; t4=A[i][k+3]; 
      t5=A[i][k+4]; t6=A[i][k+5]; 
      t7=A[i][k+6]; t8=A[i][k+7]; 
      t9=A[i][k+8]; t10=A[i][k+9]; 
        for(j=0;j           q[j]+=t1*b1[j]+t2*b2[j]+t3*b3[j]+t4*b4[j]+ 
                 t5*b5[j]+ t6*b6[j]+t7*b7[j]+t8*b8[j]+ 
                 t9*b9[j]+t10*b10[j]; 
}}} 
 
Временные характеристики: 
                                 Размер 
Компиляторы 
N=1000 N=1500 
Borland
 C++ for Win32 Compiler 5.5 
9.60 c 
32.47 c 
Microsoft
 32-bit C/C++ Optimizing Com-
piler 
3.76 c 
13.86 c 
Intel
 C++ Compiler 5.0 (включены опти-
мизирующие опции) 
1.50 c 
4.99 c 
 
Данная реализация имеет следующие показатели (в зависимости от 
компилятора):  минимальная  производительность Rmin=208MFp, 
максимальная  производительность Rmax=1353MFp. К  достоинствам 
алгоритма можно отнести: 
•  устранение  зависимостей  от  внешних  индексов  во  внутреннем 
цикле; 
•  уменьшение  количества  итераций  цикла («разворачивание 
цикла»); 
•  обращение по индексу ровно столько раз, сколько необходимо; 
•  возможность распараллеливания команд во внутреннем цикле; 

 
117 
•  ориентацию  на  принципы  работы  встроенной  кэш-памяти Intel 
Pentium
 4. 
Наилучшие  результаты  достигаются,  прежде  всего,  из-за  эффек-
тивного  использования  кэш-памяти  и  ориентации  на  векторизацию 
внутреннего цикла при использовании Intel
 C++ Compiler 5.0. 
 
PLAPACK 3.0 
Для  оценки  эффективности  приведенных  реализаций  их 
результаты  были  сопоставлены  с  результатами,  полученными  в 
вычислительных  экспериментах,  проведенных  на  базе  стандартного 
теста – библиотеки PLAPACK. 
 
Временные характеристики 
                                          Размер 
Компиляторы 
N=1000 N=1500 
Intel
 C++ Compiler 5.0 
2,66 c 
8,87 c 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: