2020-01-15
171
Для замера времени небольших операций (несколько сотен инструкций) используется инструкция процессора rdtsc, которая лежит в основе функций WinAPI QueryPerformanceFrequency и QueryPerformanceCounter. Пример использования этих функций приведён ниже:
#include <stdio.h>
#include <windows.h>
int main()
{
LARGE_INTEGER b_start,b_stop,b_time,freq;
double time, pi;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&b_start);
pi = pi_calculate();
QueryPerformanceCounter(&b_stop);
b_time.QuadPart = b_stop.QuadPart - b_start.QuadPart;
printf("Time: %lf sec Pi = %lf\n",
(double)(b_time.QuadPart)/(double)(freq.QuadPart),pi);
return 0;
}
Процедура умножения матриц
Самым быстрым способом обхода является прямой последовательный. Это значит, что после обращения в программе к некоторому элементу происходит обращение к элементу, следующему в памяти прямо за ним. Рассмотрим размещение в памяти двумерного массива в программе на языке Си.
float A[N][N];
Известно, что в языке Си массивы располагаются в памяти по строкам (сначала идут элементы первой строки, затем элементы второй строки и т.д.). Значит, в памяти он разместится следующим образом:
|
|
|
| … | A0,0 | A0,1 | A0,2 | … | A0,N-1 | A1,0 | A1,1 | A1,2 | … | A1,N-1 | … | AN-1,0 | AN-1,1 | AN-1,2 | … | AN-1,N-1 | … |
Получается два варианта перебора элементов массива:
| Быстро: for (i=0;i<N;i++) for (j=0;j<N;j++) A[i][j]=x; | Медленно: for (j=0;j<N;j++) for (i=0;i<N;i++) A[i][j]=x; |
Рассмотрим задачу перемножения двух квадратных матриц N×N. Если напрямую запрограммировать известную формулу: 
, например, на языке Си, получим следующий фрагмент программы:
for (i=0;i<N;i++)
for (k=0;k<N;k++)
for (j=0;j<N;j++) C[i][k]+=A[i][j]*B[j][k];
Заметим, что в этом случае массив A перебирается по строкам, а массив B – по столбцам (смотрим на внутренний цикл). Зная, что массивы в языке Си хранятся по строкам, приходим к выводу, что элементы массива A перебираются последовательно, а элементы массива B – нет. В данном случае порядок обхода массива C практически не важен, поскольку между обращениями к различным его элементам проходит довольно много времени. Чтобы ускорить программу, нужно, чтобы, по крайней мере, во внутреннем цикле элементы массивов перебирались последовательно. Для этого необходимо либо заранее транспонировать массив B, либо переставить циклы следующим образом:
for (i=0;i<N;i++)
for (j=0;j<N;j++)
for (k=0;k<N;k++) C[i][k]+=A[i][j]*B[j][k];
Задание.
1. Реализовать прямой обход памяти (Обязательное задание – 1 балла).
2. Реализовать обратный обход памяти (Обязательное задание – 1 балла).
3. Реализовать случайный обход памяти (Обязательное задание – 1 балла).
4. Определить степень ассоциативности кэш-памяти (Обязательное задание – 2 балла).
5. Сравнить умножение двух квадратных матриц с использованием стандартного алгоритма и алгоритма с учётом прямого обхода памяти (Дополнительное задание – 5 баллов).
|
|
|
6. Крайний срок сдачи – 15 апреля 2011 года.
Лабораторная работа № 3
Использование SIMD-расширений архитектуры x86
Цель работы. Научиться использовать SIMD-расширения архитектуры x86 в программах на языках С/С++.
Методические указания.
SIMD-расширения архитектуры x86
SIMD-расширения (Single Instruction Multiple Data) были введены в архитектуру x86 с целью повышения скорости обработки потоковых данных. Основная идея заключается в одновременной обработке нескольких элементов данных за одну инструкцию.
Расширение MMX
Первой SIMD-расширение в свой x86-процессор ввела фирма Intel – это расширение MMX. Оно стало использоваться в процессорах Pentium MMX (расширение архитектуры Pentium или P5) и Pentium II (расширение архитектуры Pentium Pro или P6). Расширение MMX работает с 64-битными регистрами MM0-MM7, физически расположенными на регистрах сопроцессора, и включает 57 новых инструкций для работы с ними. 64-битные регистры логически могут представляться как одно 64-битное, два 32-битных, четыре 16-битных или восемь 8-битных упакованных целых. Еще одна особенность технологии MMX – это арифметика с насыщением. При этом переполнение не является циклическим, как обычно, а фиксируется минимальное или максимальное значение. Например, для 8-битного беззнакового целого x:
обычная арифметика: x=254; x+=3; // результат x=1
арифметика с насыщением: x=254; x+=3; // результат x=255
1.2. Расширение 3DNow!
Технология 3DNow! была введена фирмой AMD в процессорах K6-2. Это была первая технология, выполняющая потоковую обработку вещественных данных. Расширение работает с регистрами 64-битными MMX, которые представляются как два 32-битных вещественных числа с одинарной точностью. Система команд расширена 21 новой инструкцией, среди которых есть команда выборки данных в кэш L1. В процессорах Athlon и Duron набор инструкций 3DNow! был несколько дополнен новыми инструкциями для работы с вещественными числами, а также инструкциями MMX и управления кэшированием.
Расширение SSE
С процессором Intel Pentium III впервые появилось расширение SSE (Streaming SIMD Extension). Это расширение работает с независимым блоком из восьми 128-битных регистров XMM0-XMM7. Каждый регистр XMM представляет собой четыре упакованных 32-битных вещественных числа с одинарной точностью. Команды блока XMM позволяют выполнять как векторные (над всеми четырьмя значениями регистра), так и скалярные операции (только над одним самым младшим значением). Кроме инструкций с блоком XMM в расширение SSE входят и дополнительные целочисленные инструкции с регистрами MMX, а также инструкции управления кэшированием.
Расширение SSE2
В процессоре Intel Pentium 4 набор инструкций получил очередное расширение – SSE2. Оно позволяет работать с 128-битными регистрами XMM как с парой упакованных 64-битных вещественных чисел двойной точности, а также с упакованными целыми числами: 16 байт, 8 слов, 4 двойных слова или 2 учетверенных (64-битных) слова. Введены новые инструкции вещественной арифметики двойной точности, инструкции целочисленной арифметики, 128-разрядные для регистров XMM и 64-разрядные для регистров MMX. Ряд старых инструкций MMX распространили и на XMM (в 128-битном варианте). Кроме того, расширена поддержка управления кэшированием и порядком исполнения операций с памятью.
Расширение SSE3
Дальнейшее расширение системы команд – SSE3 – вводится в процессоре Intel Pentium 4 с ядром Prescott. Это набор из 13 новых инструкций, работающих с блоками XMM, FPU, в том числе двух инструкций, повышающих эффективность синхронизации потоков, в частности, при использовании технологии Hyper-Threading.
