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

Название: Методические указания к лабораторным работам для студентов 1-го курса фпми составители
Раздел: Остальные рефераты
Тип: учебное пособие Скачать документ бесплатно, без SMS в архиве

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

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

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

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

для студентов 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: %s\n",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 = %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 -расширения архитектуры 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: %f\n",s);

// Using SSE

s=inner2(x,y,N);

printf("Result: %f\n",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 = %d\n", tid);

/* Only master thread does this */

if (tid == 0)

{

nthreads = omp_get_num_threads();

printf("Number of threads = %d\n", 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= %f\n",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 с.