В данном разделе рассматриваются подходы к оптимизации вычислений для однопроцессорных компьютерных систем на базе процессора Intel® Pentium 4, особенности архитектуры и системы команд которых позволяют решать в режиме реального времени в числе прочих такие сложные расчетные задачи, как обработка сигналов, 3D графика,обработка видео и звука и др.

Целью выполненных вычислительных экспериментов являлось определение способов эффективной реализации алгоритмов и сравнение временных характеристик программ для различных С++ компиляторов на примере задачи умножения случайно генерируемых квадратных матриц.

Необходимым условием для создания эффективных программ является наличие оптимизирующих компиляторов для наиболее распространенных языков программирования высокого уровня. В частности, в настоящее время для С++ активно используются компиляторы Intel C++ Compiler, Microsoft 32-bit C/C++ Optimizing Compiler, Borland C++ for Win32 Compiler.

1. Соглашения и обозначения. При описании результатов использовались обозначения:

-            A, B – исходные матрицы размерности N x N, заполненные случайными числами типа double;

-            С – матрица-результат,

-            T – время работы алгоритма.

2. Используемые средства.

Аппаратное обеспечение: PC на основе Intel Pentium 4 1300 MHz, RAM 256 Mb.

Платформа: Microsoft Windows 2000 Professional.

Среды разработки: 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.

3. Базовый алгоритм. Перемножение матриц выполняется в соответствии с известным выражением:

4. Оценка производительности. Производительность вычислительной системы обычно измеряется в количестве операций, выполняемый за некоторый фиксированный период времени (как правило, за 1 сек.). Общее количество операций с плавающей запятой при перемножении матриц пропорционально 2*N³; как результат, производительность может быть оценена согласно следующему соотношению

5. Реализация 1.Рассмотрим следующий фрагмент кода:

for(i=0; i N;i++)
    for(j=0; j N;j++)
         for(k=0;k N;k++)
            C[i][j]+=A[i][k]*B[k][j];

Время выполнения программы для разных размеров матрицы приведено в таблице 2.1.

Таблица 2.1.

Размер Компиляторы	Время T (сек)
	N=1000	N=1500
Borland C++ for Win32 Compiler 5.5	50,67	145,53
Microsoft 32-bit C/C++ Optimizing Compiler	37,91	94,52
Intel C++ Compiler 5.0 (включены оптимизирующие опции)	39,15	93,50

Данная реализация имеет следующие показатели (в зависимости от компилятора): Rmin=39,5 Mflops (миллионов операций с плавающей запятой в сек.), Rmax=72,2 Mflops. К очевидным недостаткам алгоритма следует отнести:

-       большое количество итераций циклов (проблемы с ветвлениями);

-       наличие в качестве тела цикла сложного выражения (явно зависящего от всех трех переменных цикла);

-       зависимость текущей итерации от предыдущей итерации (нельзя распараллелить);

-       отсутствие ориентации на принципы работы встроенной кэш-памяти IntelÒ PentiumÒ 4.

6. Реализация 2. Рассмотрим другую реализацию операции перемножения матриц:

for(i=0, i1=1, i2=2; i N; i+= 3,i1+=3, i2+= 3){
    for(j= 0;jN; 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 N; k++){
            temp=p[k];     
            ci[k]+= tmp*temp;ci1[k]+=tmp1*temp; ci2[k]+=tmp2*temp;
        }
    }
}

Временные характеристики данного варианта программы сведены в таблице 2.2.

Таблица 2.2.

Размер Компиляторы	Время T (сек)
	N=1002	N=1500
Borland C++ for Win32 Compiler 5.5	22,44	75,21
MicrosoftÒ 32-bit C/C++ Optimizing Compiler	6,70	22,89
Intel C++ Compiler 5.0 (включены оптимизирующие опции)	3,36	10,33

Данная реализация имеет лучшие показатели (в зависимости от компилятора) по сравнению с предыдущей: Rmin=89,1Mflops, Rmax=653 Mflops. К достоинствам алгоритма следует отнести:

-    устранение зависимостей от внешних индексов во внутреннем цикле;

-    возможность распараллеливания команд во внутреннем цикле;

-    ориентацию на принципы работы встроенной кэш-памяти Intel Pentium 4.

7. Реализация 3. Рассмотрим еще один вариант реализации операции перемножения матриц:

for(k=0;k N; k+= 10) {
 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; iM; 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;jM; 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];
    }
  }
}

Временные характеристики данного варианта программы сведены в таблице 2.3.

Таблица 2.3.

Размер Компиляторы	Время T (сек)
	N=1000	N=1500
Borland C++ for Win32 Compiler 5.5	9,60	32,47
Microsoft 32-bit C/C++ Optimizing Compiler	3,76	13,86
Intel C++ Compiler 5.0 (включены оптимизирующие опции)	1,50	4,99

Данная реализация имеет следующие показатели (в зависимости от компилятора): Rmin=208MFp, Rmax=1353MFp. К достоинствам алгоритма можно отнести:

-     устранение зависимостей от внешних индексов во внутреннем цикле;

-     уменьшение количества итераций цикла (“разворачивание цикла”);

-     обращение по индексу ровно столько раз, сколько необходимо;

-     возможность распараллеливания команд во внутреннем цикле;

-     ориентацию на принципы работы встроенной кэш-памяти IntelÒ PentiumÒ 4.

Наилучшие результаты достигаются, прежде всего, из-за эффективного использования кэш-памяти и ориентации на векторизацию внутреннего цикла при использовании IntelÒ C++ Compiler 5.0.

8. Использование библиотеки PLAPACK. Для оценки достигнутых показателей производительности были выполнены вычислительные эксперименты по перемножению матриц при использовании процедур библиотеки PLAPACK (см. раздел 1). Полученные временные характеристики приведены в таблице 2.4.

Таблица 2.4.

Размер Компиляторы	Время T (сек)
	N=1000	N=1500
Intel C++ Compiler 5.0	2,66	8,87

9. Основные выводы. При реализации алгоритмов необходимо обращать внимание на эффективное использование встроенной кэш-памяти Intel Pentium 4, а также программировать таким образом, чтобы позволить оптимизирующему компилятору применить векторизацию. При таком подходе становится возможным получение существенного прироста производительности при использовании Intel Pentium 4.

Intel C++ Compiler 5.0 проявил себя наилучшим образом при решении задачи умножения квадратных матриц в плане использования возможностей аппаратуры и системы команд.

Применение оптимизационных решений позволяет получить лучшие результаты по сравнению с PLAPACK 3.0.

Среда Microsoft Visual Studio позволяет легко встраивать оптимизирующие компиляторы.

<< вернуться  |   Документ от: 08.09.2005 14:41