лабы архитект. Методические указания к лабораторным работам для студентов 1го курса фпми
 Скачать 417 Kb.
|
|
Министерство образования и науки Российской Федерации Новосибирский государственный технический университет АРХИТЕКТУРА ЭВМ И ВС Методические указания к лабораторным работам для студентов 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. Представление беззнаковых целых чисел Для представления беззнаковых целых чисел необходимо перевести из десятичной системы исчисления в двоичную. Например, число  можно представить в виде суперпозиции по степеням двойки: ,где единицы в двоичном представлении числа стоят на позиции соответствующих степеней двоек. Для простоты рассмотрим беззнаковый однобайтовый тип данных (тип unsignedchar в языках С/С++). Для записи числа  в такой тип данных необходимо дополнить двоичное представление до 8 знаков  и записать полученные значения в соответствующие биты: Рисунок 1. 2. Представление знаковых целых чисел В случае знаковых типов данных старший бит отвечает за знак числа (1 – отрицательное число, 0 – положительное число). Основной проблемой является представление отрицательных чисел. Для такого представления существует следующий алгоритм: нахождение двоичного представления модуля числа, нахождение двоичного дополнения числа, прибавление единицы. Рассмотрим алгоритм на примере. Представим число  в знаковом однобайтном типе данных (тип char в языках С/С++):Двоичное представление  ,Для нахождения двоичного представления инвертируем все биты числа  ,Прибавляем единицу  .После этого записываем полученные значения в соответствующие биты:  Рисунок 2. 3. Представление вещественных чисел Основной интерес в вычислениях представляют вещественные типы данных и погрешности округления, связанные с ними. По стандарту IEEE 754 вещественное число  представляется в виде: Рисунок 3. Где  – однобитовый знак числа,  – нормализованная мантисса,  – показатель степени двойки. В случае типа float под мантиссу выделяется 23 бита, экспоненту 8 бит, в случае типа double 52 бита, экспоненту 11 бит.Приведём пример представления вещественного числа  в типе float. Основной задачей является запись числа в виде  . Число можно записать в виде  , в данном случае мантисса имеет вид  нормализация мантиссы позволяет отбросить единицу и записывать только дробную часть. Таким образом  . Далее записываем показатель степени двойки. При этом нужно учитывать, что эта степень может быть как отрицательной так и положительной. Для этого показатель степени имеет вид: ,где  – количество бит на показатель степени двойки. В результате число представимо в виде: Рисунок 4. В завершении описания представления вещественных чисел нужно отметить, что для стандартных типов данных (float и double) имеют место следующие значения: Таблица 1.
(*) Стоит отметить, что мантисса может быть ненормализованной, что и приводит к таким значениям минимального порядка. 4. Идентификация оборудования и программного окружения Средствами операционной системы Windows можно узнать достаточно много информации об оборудовании, памяти (функция GlobalMemoryStatus), жёстких дисках (функция GetDiskFreeSpace), сети и мониторе (функция GetSystemMetrics при различных параметрах), программном окружении (функции GetComputerName и GetUserName) и о многом другом. Подробное описание функций и примеры их использования можно найти в справочной системе MSDN. Для определения таких параметров процессора, как фирма производитель, наличие расширений, количества и параметров кэшей команд и данных, TLB и других параметров в случае архитектур x86 используется инструкция процессора cpuid, которая имеет интерфейс на языке С/С++ __cpuid. Так для определения идентификатора процессора имеет место следующий код: #include … 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 можно узнать полное название процессора. Задание. В соответствии с вариантом задания записать представление целого числа в типе char и вещественного числа в типе float (Обязательное задание – 5 баллов). С помощью функций WinAPI определить информацию об оперативной памяти (Дополнительное задание – 1 балл). С помощью функций WinAPI определить информацию о памяти на одном из жёстких дисков (Дополнительное задание – 2 балла). С помощью инструкции cpuid определить название процессора (Дополнительное задание – 2 балла). Крайний срок сдачи – 1 апреля 2011 года. Варианты. Целое число –12, вещественное число 12.5. Целое число –23, вещественное число 12.125. Целое число –56, вещественное число 12.25. Целое число –78, вещественное число 12.75. Целое число –89, вещественное число 12.625. Целое число –90, вещественное число 24.5. Целое число –21, вещественное число 24.125. Целое число –45, вещественное число 24.25. Целое число –78, вещественное число 24.75. Целое число –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 #include 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]; Известно, что в языке Си массивы располагаются в памяти по строкам (сначала идут элементы первой строки, затем элементы второй строки и т.д.). Значит, в памяти он разместится следующим образом:
|