Методические указания к лабораторным работам для студентов 1-го курса фпми составители

Министерство образования и науки Российской Федерации

Новосибирский государственный технический университет

АРХИТЕКТУРА ЭВМ И ВС

Методические указания к лабораторным работам

для студентов 1-го курса ФПМИ

Составители:

Доцент кафедры ПВТ к.т.н. Маркова В.П.

Ассистент кафедры ПВТ к.ф.-м.н. Куликов И.М.

Новосибирск 2011

Введение

Целями лабораторных работ являются приобретение практических знаний по:

- идентификации оборудования и программного окружения ЭВМ,

- представлению вещественных чисел в ЭВМ,

- сравнению различных способов обхода памяти,

- программному определению размера и степени ассоциативности кэш-памяти различных уровней,

- использованию SIMD-расширения архитектуры x86,

- использованию интерфейса OpenMP для программирования простых многопоточных приложений.

Порядок выполнения работ

Лабораторные работы 1, 2 и 3 являются обязательными для выполнения, лабораторная работа 4 является дополнительной. За лабораторные работы 1 и 2 выставляются максимум по 10 баллов, за лабораторную работу 3 выставляется максимум 20 баллов, лабораторная работа 4 оценивается максимум 40 баллов. Количество баллов, полученных за выполнение каждой из лабораторных работ, определяется по выполненным заданиям к лабораторной работе в соответствии с баллом такого задания и сроком сдачи. В случае сдачи лабораторной работы после крайней даты сдачи дополнительные задания не засчитываются и соответствующие баллы за них не выставляются. Базовые задания первых трёх лабораторных работ должны быть выполнены обязательно, без них лабораторная работа считается не сданной.

Отчёт по лабораторной работе нужно подготавливать в электронном виде и высылать на e-mail преподавателя kulikov@ssd.sscc.ru, по результатам сдачи отчёта студент при необходимости приглашается на защиту. В отчёт необходимо включить титульный лист; список выполненных заданий по лабораторной работе; текст программы; необходимые тесты, графики зависимостей, результаты замера времени и т. п.; выводы, сделанные на основании выполнения лабораторной работы.

Студенты, сдавшие четыре лабораторные работы и получившие в сумме максимальный балл (80 баллов
) претендуют на получение зачёта «автоматом» с максимальным баллом по предмету (100 баллов
). Для допуска к зачёту необходимо набрать 31 балл
за лабораторные работы.

Лабораторная работа № 1

Представление чисел и определения типа оборудования

Цель работы.

Идентификация оборудования и программного окружения ЭВМ, изучение представления вещественных чисел в ЭВМ.

Методические указания.

1. Представление беззнаковых целых чисел

Для представления беззнаковых целых чисел необходимо перевести из десятичной системы исчисления в двоичную. Например, число можно представить в виде суперпозиции по степеням двойки:

,

где единицы в двоичном представлении числа стоят на позиции соответствующих степеней двоек. Для простоты рассмотрим беззнаковый однобайтовый тип данных (тип unsigned
char
в языках С/С++). Для записи числа в такой тип данных необходимо дополнить двоичное представление до 8 знаков и записать полученные значения в соответствующие биты:

Рисунок 1.

2. Представление знаковых целых чисел

В случае знаковых типов данных старший бит отвечает за знак числа (1 – отрицательное число, 0 – положительное число). Основной проблемой является представление отрицательных чисел. Для такого представления существует следующий алгоритм:

1. нахождение двоичного представления модуля числа,

2. нахождение двоичного дополнения числа,

3. прибавление единицы.

Рассмотрим алгоритм на примере. Представим число в знаковом однобайтном типе данных (тип char
в языках С/С++):

1. Двоичное представление ,

2. Для нахождения двоичного представления инвертируем все биты числа ,

3. Прибавляем единицу .

После этого записываем полученные значения в соответствующие биты:

Рисунок 2.

3. Представление вещественных чисел

Основной интерес в вычислениях представляют вещественные типы данных и погрешности округления, связанные с ними. По стандарту IEEE 754 вещественное число представляется в виде:

Рисунок 3.

Где – однобитовый знак числа, – нормализованная мантисса, – показатель степени двойки. В случае типа float
под мантиссу выделяется 23 бита, экспоненту 8 бит, в случае типа double
52 бита, экспоненту 11 бит.

Приведём пример представления вещественного числа в типе float
. Основной задачей является запись числа в виде . Число можно записать в виде , в данном случае мантисса имеет вид нормализация мантиссы позволяет отбросить единицу и записывать только дробную часть. Таким образом . Далее записываем показатель степени двойки. При этом нужно учитывать, что эта степень может быть как отрицательной так и положительной. Для этого показатель степени имеет вид:

,

где – количество бит на показатель степени двойки. В результате число представимо в виде:

Рисунок 4.

В завершении описания представления вещественных чисел нужно отметить, что для стандартных типов данных (float
и double
) имеют место следующие значения:

Таблица 1.

Тип	Минимальный порядок*	Максимальный порядок	Число значащих знаков
float	– 45	38	7
double	– 323	308	15

(*) Стоит отметить, что мантисса может быть ненормализованной, что и приводит к таким значениям минимального порядка.

4. Идентификация оборудования и программного окружения

Средствами операционной системы Windows можно узнать достаточно много информации об оборудовании, памяти (функция GlobalMemoryStatus
), жёстких дисках (функция GetDiskFreeSpace
), сети и мониторе (функция GetSystemMetrics
при различных параметрах), программном окружении (функции GetComputerName
и GetUserName
) и о многом другом. Подробное описание функций и примеры их использования можно найти в справочной системе MSDN.

Для определения таких параметров процессора, как фирма производитель, наличие расширений, количества и параметров кэшей команд и данных, TLB и других параметров в случае архитектур x86 используется инструкция процессора cpuid
, которая имеет интерфейс на языке С/С++ __cpuid
. Так для определения идентификатора процессора имеет место следующий код:

#include <intrin.h> // подключение описания функции __cpuid

…

int CPUInfo[4];

char CPUString[32];

__cpuid(CPUInfo, 0);

memset(CPUString, 0, sizeof(CPUString));

*((int*)CPUString) = CPUInfo[1];

*((int*)(CPUString+4)) = CPUInfo[3];

*((int*)(CPUString+8)) = CPUInfo[2];

printf(" CPU vendor: %sn",CPUString);

…

Первый параметр функции __cpuid
– 4-х элементный целочисленный массив, который соответствует регистрам eax, ebx, ecx, edx после выполнения инструкции. Второй параметр функции – номер функции инструкции. Подробная информация о номерах функций инструкции cpuid
и содержимом регистров приведена в документах [1,2] для процессоров Intel и AMD. Так например с помощью функций 0x80000002, 0x80000003, 0x80000004 можно узнать полное название процессора.

Задание.

1. В соответствии с вариантом задания записать представление целого числа в типе char
и вещественного числа в типе float
(Обязательное задание
– 5 баллов).

2. С помощью функций WinAPI определить информацию об оперативной памяти (Дополнительное задание
– 1 балл).

3. С помощью функций WinAPI определить информацию о памяти на одном из жёстких дисков (Дополнительное задание
– 2 балла).

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 = %lfn",

(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
-расширения архитектуры
x
86

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:

обычная арифметика: x=254; x+=3; // результат x=1

арифметика с насыщением: x=254; x+=3; // результат x=255

1.2. Расширение 3
DNow
!

Технология 3DNow! была введена фирмой AMD в процессорах K6-2. Это была первая технология, выполняющая потоковую обработку вещественных данных. Расширение работает с регистрами 64-битными MMX, которые представляются как два 32-битных вещественных числа с одинарной точностью. Система команд расширена 21 новой инструкцией, среди которых есть команда выборки данных в кэш L1. В процессорах Athlon и Duron набор инструкций 3DNow! был несколько дополнен новыми инструкциями для работы с вещественными числами, а также инструкциями MMX и управления кэшированием.

1.3. Расширение
SSE

С процессором Intel Pentium III впервые появилось расширение SSE (Streaming SIMD Extension). Это расширение работает с независимым блоком из восьми 128-битных регистров XMM0-XMM7. Каждый регистр XMM представляет собой четыре упакованных 32-битных вещественных числа с одинарной точностью. Команды блока XMM позволяют выполнять как векторные (над всеми четырьмя значениями регистра), так и скалярные операции (только над одним самым младшим значением). Кроме инструкций с блоком XMM в расширение SSE входят и дополнительные целочисленные инструкции с регистрами MMX, а также инструкции управления кэшированием.

1.4. Расширение
SSE
2

В процессоре Intel Pentium 4 набор инструкций получил очередное расширение – SSE2. Оно позволяет работать с 128-битными регистрами XMM как с парой упакованных 64-битных вещественных чисел двойной точности, а также с упакованными целыми числами: 16 байт, 8 слов, 4 двойных слова или 2 учетверенных (64-битных) слова. Введены новые инструкции вещественной арифметики двойной точности, инструкции целочисленной арифметики, 128-разрядные для регистров XMM и 64-разрядные для регистров MMX. Ряд старых инструкций MMX распространили и на XMM (в 128-битном варианте). Кроме того, расширена поддержка управления кэшированием и порядком исполнения операций с памятью.

1.5. Расширение
SSE
3

Дальнейшее расширение системы команд – SSE3 – вводится в процессоре Intel Pentium 4 с ядром Prescott. Это набор из 13 новых инструкций, работающих с блоками XMM, FPU, в том числе двух инструкций, повышающих эффективность синхронизации потоков, в частности, при использовании технологии Hyper-Threading.

1.6. Поддержка
SIMD
-расширений архитектурой
x
86-64

Процессоры AMD Athlon64 и AMD Opteron с архитектурой x86-64 поддерживают все выше перечисленные SIMD-расширения, кроме SSE3. Кроме того, число XMM регистров у этих процессоров увеличилось до 16 (XMM0-XMM15). Подробное описание типов и команд SSE приведено в приложении.

2.
Встроенные функции потокового SIMD расширения

Типы данных

Для работы с векторными данными, содержащими несколько упакованных значений, используются следующие типы:

__m64 – 64-бит (регистр MMX)

1 * 64-битное целое

2 * 32-битных целых

4 * 16-битных целых

8 * 8-битных целых.

__m128 – 128-бит (регистр XMM):

4 * 32-битных вещественных (SSE),

2 * 64-битных вещественных (SSE2),

2 * 64-битное целых (SSE2),

4 * 32-битных целых (SSE2),

8 * 16-битных целых (SSE2),

16 * 8-битных целых (SSE2).

Для наибольшей эффективности элементы таких типов данных должны быть выровнены в памяти по соответствующей границе. Например, начало массива элементов типа __m64 выравнивается по 8 байтам, а массив элементов __m128 – по 16 байтам. Статические переменные и массивы компилятор выравнивает автоматически. Динамические данные компилятор обычно выравнивает по только величине 4 байта. Если данные векторных типов оказались невыровненными, то для работы с ними следует применять специальные команды невыровненного чтения и записи (они работают медленнее обычных – выровненных). Для выделения памяти с выравниванием используется функция:

void *_mm_malloc(int size, int align)

size – объем выделяемой памяти в байтах (как в malloc),

align – выравнивание в байтах.

Для освобождения памяти, выделенной таким образом, используется функция:

void _mm_free(void *p);

Например:

float *x; // массив для обработки с помощью инструкций SSE

x=(float)_mm_malloc(N*sizeof(float),16);

// … здесь обработка …

_mm_free(x);

Встроенные функции
SSE
для работы с вещественными числами

Заголовочный файл xmmintrin.h содержит объявления встроенных функций (intrinnsics) SSE.

Арифметические функции

Функция	Инструкция	Операция	R0	R1	R2	R3
_mm_add_ss	ADDSS	сложение	a0 [op] b0	a1	a2	a3
_mm_add_ps	ADDPS	сложение	a0 [op] b0	a1 [op] b1	a2 [op] b2	a3 [op] b3
_mm_sub_ss	SUBSS	вычитание	a0 [op] b0	a1	a2	a3
_mm_sub_ps	SUBPS	вычитание	a0 [op] b0	a1 [op] b1	a2 [op] b2	a3 [op] b3
_mm_mul_ss	MULSS	умножение	a0 [op] b0	a1	a2	a3
_mm_mul_ps	MULPS	умножение	a0 [op] b0	a1 [op] b1	a2 [op] b2	a3 [op] b3
_mm_div_ss	DIVSS	деление	a0 [op] b0	a1	a2	a3
_mm_div_ps	DIVPS	деление	a0 [op] b0	a1 [op] b1	a2 [op] b2	a3 [op] b3
_mm_sqrt_ss	SQRTSS	квадратный корень	[op] a0	a1	a2	a3
_mm_sqrt_ps	SQRTPS	квадратный корень	[op] a0	[op] b1	[op] b2	[op] b3
_mm_rcp_ss	RCPSS	обратное значение	[op] a0	a1	a2	a3
_mm_rcp_ps	RCPPS	обратное значение	[op] a0	[op] b1	[op] b2	[op] b3
_mm_rsqrt_ss	RSQRTSS	обратное значение квадратного корня	[op] a0	a1	a2	a3
_mm_rsqrt_ps	RSQRTPS	обратное значение квадратного корня	[op] a0	[op] b1	[op] b2	[op] b3
_mm_min_ss	MINSS	минимум	[op](a0,b0)	a1	a2	a3
_mm_min_ps	MINPS	минимум	[op](a0,b0)	[op](a1,b1)	[op](a2,b2)	[op](a3,b3)
_mm_max_ss	MAXSS	максимум	[op](a0,b0)	a1	a2	a3
_mm_max_ps	MAXPS	максимум	[op](a0,b0)	[op](a1,b1)	[op](a2,b2)	[op](a3,b3)

Функции сравнения

Каждая встроенная функция сравнения выполняет сравнение операндов a и b. В векторной форме сравниваются четыре вещественных значения параметра a с четырьмя вещественными значениями параметра b, и возвращается 128-битная маска. В скалярной форме сравниваются младшие значения параметров, возвращается 32-битная маска, остальные три старших значения копируются из параметра a. Маска устанавливается в значение 0xffffffff для тех элементов, результат сравнения которых истина, и 0x0, где результат сравнения ложь.

Имя	Сравнение	Инструкция
_mm_cmpeq_ss	равно	CMPEQSS
_mm_cmpeq_ps	равно	CMPEQPS
_mm_cmplt_ss	меньше	CMPLTSS
_mm_cmplt_ps	меньше	CMPLTPS
_mm_cmple_ss	меньше или равно	CMPLESS
_mm_cmple_ps	меньше или равно	CMPLEPS
_mm_cmpgt_ss	больше	CMPLTSS
_mm_cmpgt_ps	больше	CMPLTPS
_mm_cmpge_ss	больше или равно	CMPLESS
_mm_cmpge_ps	больше или равно	CMPLEPS
_mm_cmpneq_ss	не равно	CMPNEQSS
_mm_cmpneq_ps	не равно	CMPNEQPS
_mm_cmpnlt_ss	не меньше	CMPNLTSS
_mm_cmpnlt_ps	не меньше	CMPNLTPS
_mm_cmpnle_ss	не меньше или равно	CMPNLESS
_mm_cmpnle_ps	не меньше или равно	CMPNLEPS
_mm_cmpngt_ss	не больше	CMPNLTSS
_mm_cmpngt_ps	не больше	CMPNLTPS
_mm_cmpnge_ss	не больше или равно	CMPNLESS
_mm_cmpnge_ps	не больше или равно	CMPNLEPS
_mm_cmpord_ss	упорядочены	CMPORDSS
_mm_cmpord_ps	упорядочены	CMPORDPS
_mm_cmpunord_ss	неупорядочены	CMPUNORDSS
_mm_cmpunord_ps	неупорядочены	CMPUNORDPS
_mm_comieq_ss	равно	COMISS
_mm_comilt_ss	меньше	COMISS
_mm_comile_ss	меньше или равно	COMISS
_mm_comigt_ss	больше	COMISS
_mm_comige_ss	большеили равно	COMISS
_mm_comineq_ss	не равно	COMISS
_mm_ucomieq_ss	равно	UCOMISS
_mm_ucomilt_ss	меньше	UCOMISS
_mm_ucomile_ss	меньше или равно	UCOMISS
_mm_ucomigt_ss	больше	UCOMISS
_mm_ucomige_ss	больше или равно	UCOMISS
_mm_ucomineq_ss	не равно	UCOMISS

Операции преобразования
типов

Имя функции	Операция	Инструкция
_mm_cvtss_si32	Преобразует младший float в 32-битное целое	CVTSS2SI
_mm_cvtps_pi32	Преобразует два младших float в два упакованных 32-битных целых	CVTPS2PI
_mm_cvttss_si32	Преобразует младший float в 32-битное целое, отбрасывая дробную часть	CVTTSS2SI
_mm_cvttps_pi32	Преобразует два младших float в два упакованных 32-битных целых, отбрасывая дробную часть	CVTTPS2PI
_mm_cvtsi32_ss	Преобразует 32-битное целое в float	CVTSI2SS
_mm_cvtpi32_ps	Преобразует два упакованных 32-битных целых в два младших float	CVTTPS2PI
_mm_cvtpi16_ps	Преобразует четыре упакованных 16-битных целых в упакованные float	составная
_mm_cvtpu16_ps	Преобразует четыре упакованных беззнаковых 16-битных целых в упакованные float	составная
_mm_cvtpi8_ps	Преобразует четыре младших упакованных 8-битных целых в четыре упакованных float	составная
_mm_cvtpu8_ps	Преобразует четыре младших упакованных беззнаковых 8-битных целых в четыре упакованных float	составная
_mm_cvtpi32x2_ps	Преобразует две пары упакованных 32-битных целых в четыре упакованных float	составная
_mm_cvtps_pi16	Преобразует четыре упакованных float в четыре 16-битных целых	составная
_mm_cvtps_pi8	Преобразует четыре упакованных float в четыре младших 8-битных целых	составная

Другие функции

Имя функции	Операция	Инструкция
_mm_shuffle_ps	перестановка упакованных значений	SHUFPS
_mm_shuffle_pi16	перестановка упакованных значений	PSHUFW
_mm_unpackhi_ps	выборка старших значений	UNPCKHPS
_mm_unpacklo_ps	выборка младших значений	UNPCKLPS
_mm_loadh_pi	загрузка старших значений	MOVHPS reg, mem
_mm_storeh_pi	сохранение старших значений	MOVHPS mem, reg
_mm_movehl_ps	копирование старшей половины в младшую	MOVHLPS
_mm_movelh_ps	копирование младшей половины в старшую	MOVLHPS
_mm_loadl_pi	загрузка младших значений	MOVLPS reg, mem
_mm_storel_pi	сохранение младших значений	MOVLPS mem, reg
_mm_movemask_ps	создание знаковой маски	MOVMSKPS
_mm_getcsr	сохранить регистр состояния	STMXCSR
_mm_setcsr	установить регистр состояния	LDMXCSR

Команды для инициализации и работы с памятью

Инициализация
памяти

Имя функции	Операция	Инструкция
_mm_load_ss	загрузить младшее значение и очистить остальные три значения	MOVSS
_mm_load1_ps	загрузить одно значение во все четыре позиции	MOVSS + Shuffling
_mm_load_ps	Загрузить четыре значения по выровненному адресу	MOVAPS
_mm_loadu_ps	Загрузить четыре значения по невыровненному адресу	MOVUPS
_mm_loadr_ps	Загрузить четыре значения в обратном порядке	MOVAPS + Shuffling

Инициализация значений

Имя функции	Операция	Инструкция
_mm_set_ss	устанавливает самое младшее значение и обнуляет три остальных	составная
_mm_set1_ps	устанавливает четыре позиции в одно значение	составная
_mm_set_ps	устанавливает четыре значения, выровненные по адресу	составная
_mm_setr_ps	устанавливает четыре значения в обратном порядке	составная
_mm_setzero_ps	Обнуляет все четыре значения	составная

Операции записи

Имя функции	Операция	Инструкция
_mm_store_ss	записать младшее значение	MOVSS
_mm_store1_ps	записать младшее значение во все четыре позиции	MOVSS + Shuffling
_mm_store_ps	записать четыре значения по выровненному адресу	MOVAPS
_mm_storeu_ps	записать четыре значения по невыровненному адресу	MOVUPS
_mm_storer_ps	записать четыре значения в обратном порядке	MOVAPS + Shuffling
_mm_move_ss	записать младшее значение и оставить без изменения три остальных значения	MOVSS

Поддержка кэш-памяти в
SSE

Имя функции	Операция	Инструкция
_mm_prefetch	Загружает одну кэш-строку по указанному адресу в кэш-память	PREFETCH
_mm_stream_pi	Записывает данные в память без записи в кэш	MOVNTQ
_mm_stream_ps	Записывает данные в память без записи в кэш по адресу, выровненному по 16 байт	MOVNTPS
_mm_sfence	Гарантирует, что все предшествующие записи в память завершатся до следующей записи.	SFENCE

3. Использование встроенных функций
SSE
в программе на языке Си

// скалярное произведение векторов

#include <stdio.h>

#include <xmmintrin.h>

#define N 10000000

// «обычная» функция

float inner1(float *x,float *y,int n)

{

float s;

int i;

s=0;

for(i=0;i<n;i++)

s+=x[i]*y[i];

return s;

}

// функция с использованием SSE intrinsics

float inner2(float *x,float *y,int n)

{

float sum;

int i;

__m128 *xx,*yy;

__m128 p,s;

xx=(__m128 *)x;

yy=(__m128 *)y;

s=_mm_set_ps1(0);

for (i=0;i<n/4;i++)

{

p=_mm_mul_ps(xx[i], yy[i]); // векторное умножение четырех чисел

s=_mm_add_ps(s,p); // векторное сложение четырех чисел

}

p=_mm_movehl_ps(p,s); // перемещение двух старших значений s в младшие p

s=_mm_add_ps(s,p); // векторное сложение

p=_mm_shuffle_ps(s,s,1);//перемещение второго значения в s в младшую позицию в p

s=_mm_add_ss(s,p); // скалярное сложение

_mm_store_ss(&sum,s); // запись младшего значения в память

return sum;

}

int main()

{

float *x,*y, s;

long t;

int i;

// выделение памяти с выравниванием

x=(float *)_mm_malloc(N*sizeof(float),16);

y=(float *)_mm_malloc(N*sizeof(float),16);

for (i=0;i<N;i++)

{

x[i]=10*i/N;

y[i]=10*(N-i-1)/N;

}

// Using x87

s=inner1(x,y,N);

printf("Result: %fn",s);

// Using SSE

s=inner2(x,y,N);

printf("Result: %fn",s);

_mm_free(x);

_mm_free(y);

return 0;

}

Задание.

1. Реализовать процедуру умножения квадратных матриц (размером кратным четырём) без использования специальных расширений и с использованием расширений SSE, сравнить время выполнения этих реализаций (Обязательное задание
– 10 баллов).

2. В соответствии с вариантом задания реализовать матрично-векторную (с одинаковым размером матриц и векторов кратным четырём) процедуру с использованием расширений SSE (Дополнительное задание
– 7 баллов).

3. С использованием инструкции cpuid
определить наличие расширения SSE (Дополнительное задание
– 3 балла).

4. Крайний срок сдачи – 7 мая 2011 года
.

Варианты.

В предложенных вариантах предполагается, что – скаляры, – векторы, – матрицы:

1. Операция .

2. Операция .

3. Операция .

4. Операция .

5. Операция .

6. Операция .

7. Операция .

8. Операция .

9. Операция .

10. Операция .

Лабораторная работа № 4

Программирование многоядерных архитектур

Цель работы.

Использование интерфейса OpenMP для программирования простых многопоточных приложений.

Методические указания.

1. Интерфейс
OpenMP

OpenMP – интерфейс прикладного программирования (API) для масштабируемых SMP-систем (симметричные мультипроцессорные системы) в модели общей памяти.

Исполняемый процесс в памяти может состоять из множественных нитей, которые имеют общее адресное пространство, но разные потоки команд и раздельные стэки. В простейшем случае, процесс состоит из одной нити, выполняющую функцию main. Нити иногда называют также потоками, легковесными процессами, LWP (light-weight processes). OpenMP основан на существовании множественных потоков в общедоступной памяти [3]. Схема процесса представлена на рисунке.

Рисунок 8.

Все программы OpenMP начинаются как единственный процесс с главным потоком. Главный поток выполняется последовательно, пока не сталкиваются с первой областью параллельной конструкции. Создание нескольких потоков (FORK) и объединение (JOIN) проиллюстрировано на рисунке.

Рисунок 9.

2. Примеры программ с использованием
OpenMP

2.1. Определение и печать номера потока

#include <omp.h>

#include <stdio.h>

void main ()

{

int nthreads, tid;

/* Fork a team of threads giving them their own copies of variables */

#pragma omp parallel private(tid)

{

/* Obtain and print thread id */

tid = omp_get_thread_num();

printf("Hello World from thread = %dn", tid);

/* Only master thread does this */

if (tid == 0)

{

nthreads = omp_get_num_threads();

printf("Number of threads = %dn", nthreads);

}

} /* All threads join master thread and terminate */

}

2.2. Распределение работы

#include <stdio.h>

#include <omp.h>

#define CHUNKSIZE 100

#define N 1000

void main ()

{

int i, chunk;

float a[N], b[N], c[N];

/* Some initializations */

for (i=0; i < N; i++)

a[i] = b[i] = i * 1.0;

chunk = CHUNKSIZE;

#pragma omp parallel shared(a,b,c,chunk) private(i)

{

#pragma omp for schedule(dynamic,chunk) nowait

for (i=0; i < N; i++)

c[i] = a[i] + b[i];

} /* end of parallel section */

}

2.3.
Использование
секций

#include <stdio.h>

#include <omp.h>

#define N 1000

void main ()

{

int i;

float a[N], b[N], c[N], d[N];

/* Some initializations */

for (i=0; i < N; i++)

{

a[i] = i * 1.5;

b[i] = i + 22.35;

}

#pragma omp parallel shared(a,b,c,d) private(i)

{

#pragma omp sections nowait

{

#pragma omp section

for (i=0; i < N; i++)

c[i] = a[i] + b[i];

#pragma omp section

for (i=0; i < N; i++)

d[i] = a[i] * b[i];

} /* end of sections */

} /* end of parallel section */

}

2.4. Параллельная реализация одиночных циклов

#include <stdio.h>

#include <omp.h>

#define N 1000

#define CHUNKSIZE 100

void main ()

{

int i, chunk;

float a[N], b[N], c[N];

/* Some initializations */

for (i=0; i < N; i++)

a[i] = b[i] = i * 1.0;

chunk = CHUNKSIZE;

#pragma omp parallel for shared(a,b,c,chunk) private(i) schedule(static,chunk)

for (i=0; i < n; i++)

c[i] = a[i] + b[i];

}

2.5. Критические секции

#include <omp.h>

void main()

{

int x;

x = 0;

#pragma omp parallel shared(x)

{

#pragma omp critical

x = x + 1;

} /* end of parallel section */

}

2.6.
Редуцируемые
операции

#include <omp.h>

#include <stdio.h>

void main ()

{

int i, n, chunk;

float a[100], b[100], result;

/* Some initializations */

n = 100;

chunk = 10;

result = 0.0;

for (i=0; i < n; i++)

{

a[i] = i * 1.0;

b[i] = i * 2.0;

}

#pragma omp parallel for default(shared) private(i) schedule(static,chunk) reduction(+:result)

for (i=0; i < n; i++)

result = result + (a[i] * b[i]);

printf("Final result= %fn",result);

}

Задание.

1. В соответствии с вариантом задания реализовать алгоритм с использованием интерфейса OpenMP (Дополнительное задание:
варианты 1,2 и 3 – 20 баллов, вариант 4 – 30 баллов).

2. Защита лабораторной работы (Дополнительное задание
– 10 баллов).

3. Крайний срок сдачи – 20 мая 2011 года
.

4. Крайний срок защиты – 25 мая 2011 года
.

Варианты.

1. Скалярное произведение двух векторов.

2. Умножение матрицы на вектор.

3. Умножение матрицы на матрицу.

4. Решение системы линейных алгебраических уравнений методом Гаусса.

Литература

1. Спецификация инструкции cpuid для процессоров Intel http://www.intel.com/Assets/PDF/appnote/241618.pdf

2. Спецификация инструкции cpuid для процессоров AMD http://support.amd.com/us/Embedded_TechDocs/25481.pdf

3. Корнеев В.Д. Параллельное программирование кластеров // Новосибирск. НГТУ. 2008. – 312 с.