Методические указания к лабораторным работам для студентов 1-го курса фпми составители (стр. 2 из 5)
4. С помощью инструкции cpuid определить название процессора (Дополнительное задание – 2 балла).
5. Крайний срок сдачи – 1 апреля 2011 года.
Варианты.
1. Целое число –12, вещественное число 12.5.
2. Целое число –23, вещественное число 12.125.
3. Целое число –56, вещественное число 12.25.
4. Целое число –78, вещественное число 12.75.
5. Целое число –89, вещественное число 12.625.
6. Целое число –90, вещественное число 24.5.
7. Целое число –21, вещественное число 24.125.
8. Целое число –45, вещественное число 24.25.
9. Целое число –78, вещественное число 24.75.
10. Целое число –86, вещественное число 24.625.
Лабораторная работа № 2
Исследование кэш-памяти и обхода памяти
Цель работы. Сравнение различных способов обхода памяти, программное определение размера и степени ассоциативности кэш-памяти различных уровней.
Методические указания.
1. Кэш-память
Кэш-память является промежуточным хранилищем данных между процессором и оперативной памятью. Она содержит копии наиболее часто используемых блоков данных из оперативной памяти. Размер кэш-памяти составляет от нескольких килобайт до нескольких мегабайт, а скорость доступа к ней в несколько раз превосходит скорость доступа к оперативной памяти, но уступает скорости обращения к регистрам. Каждый раз, когда к ячейке оперативной памяти происходит обращение (чтение или запись), ее копия заносится в кэш-память, вытеснив при этом оттуда копию другой ячейки. Поэтому повторное обращение к той же ячейке произойдет быстрее. Значения переменных программы и небольшие массивы, для которых не нашлось места в регистрах, обычно располагаются в кэш-памяти. Большие массивы могут поместиться в кэш-память только частично. Допустим, некоторая программа производит многократную обработку элементов массива. Если построить график зависимости времени обработки массива от размера массива, то он должен иметь нелинейный характер. При превышении размера кэш-памяти время обращения к элементам массива несколько возрастет (на графике будет наблюдаться скачок). Данные из оперативной памяти в кэш-память (и обратно) считываются целыми строками. Размер кэш-строки в большинстве распространенных процессоров составляет 16, 32, 64, 128 байт. При последовательном обходе попытка чтения первого элемента кэш-строки вызывает копирование всей строки из медленной оперативной памяти в кэш. Чтение нескольких последующих элементов выполняется намного быстрее, т.к. они уже находятся в быстрой кэш-памяти. В большинстве современных микропроцессорах реализована аппаратная предвыборка данных. Ее суть состоит в том, что при последовательном обходе очередные кэш-строки копируются из оперативной памяти в кэш-память еще до того, как к ним произошло обращение. За счет этого скорость последовательного обхода данных еще возрастает.
Большинство современных микропроцессоров имеют множественно-ассоциативную (наборно-ассоциативную) организацию кэш-памяти. При множественно-ассоциативной организации кэш-память разделена на несколько банков, и каждый блок данных из оперативной памяти может быть помещен в одну из определенного множества (набора) строк кэш-памяти. Число строк в множестве определяется числом банков. Схема кэш-памяти данных первого уровня на Pentium III (16 Кб):
Рисунок 5.
В какой конкретный элемент множества строка будет записана, определяется алгоритмом замещения (циклический, случайный, LRU, псевдо-LRU, …). Таким образом, блоки, отстоящие на определенное расстояние в памяти (в примере: на 212 B = 4096 B = 4 KB), помещаются в одно и то же множество строк. Число элементов в каждом множестве (число банков) называется степенью ассоциативности кэш-памяти. Например, кэш данных L1 в Pentium III имеет объем 16 KB, степень ассоциативности 4 (4-way set-associative), размер строки 32B:
16KB = 4-way * 4 KB = 4-way * 128 множеств * 32B
Данные, расположенные в памяти с шагом на расстоянии 4KB приходятся на одно множество. На все эти данные приходится всего 4 кэш-строки, т.е. 4 * 32 = 128 B. Если выполнять обход данных с шагом 4 KB, то из всех 16 KB кэша L1 будет использоваться всего 128 B, которые будут постоянно перезаписываться (эффект «буксования» кэша). Производительность при этом будет такая же, как при отсутствии кэш-памяти. Если вычислительная система имеет несколько уровней кэш-памяти, то у каждого уровня может быть своя степень ассоциативности. Определить степени ассоциативности кэш-памяти можно следующим способом. Выполняется обход N блоков данных суммарным объемом BlockSize, отстоящих друг от друга на величину Offset:
Рисунок 6.
BlockSize должен быть не больше объема исследуемого уровня кэш-памяти. Offset должно быть кратно величине «размер кэша» / «ассоциативность», т.е. кратно размеру банка ассоциативности. Как правило, это степени двоек, так что можно взять заведомо кратное такому значению расстояние (например, 1MB). Изменяя число частей N, мы увидим, как меняется время обхода. Когда N превысит число банков, время обхода сильно возрастет.
Обход элементов следует производить в таком порядке:
Рисунок 7.
2. Функции замера времени
Для замера времени небольших операций (несколько сотен инструкций) используется инструкция процессора 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;
}
3. Процедура умножения матриц
Самым быстрым способом обхода является прямой последовательный. Это значит, что после обращения в программе к некоторому элементу происходит обращение к элементу, следующему в памяти прямо за ним. Рассмотрим размещение в памяти двумерного массива в программе на языке Си.
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 в программах на языках С/С++.
Методические указания.
1. SIMD-расширения архитектуры x86
SIMD-расширения (Single Instruction Multiple Data) были введены в архитектуру x86 с целью повышения скорости обработки потоковых данных. Основная идея заключается в одновременной обработке нескольких элементов данных за одну инструкцию.
1.1. Расширение 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: