Определить степень ассоциативности кэш-памяти.

Для выполнения задания требуется написать программу, выполняющую чтение элементов массива заданного размера в заданном порядке. Процедура обхода массива x[] должна выглядеть следующим образом:

for (i=0, j=0; j<N; j++) i = x[i];

где элементы массива x[] представляют собой связный список, заполненный специальным образом. Для определения степени ассоциативности кэш-памяти необходимо выполнять чтение данных в памяти с шагом, вызывающем кэш-буксование (для большинства процессоров подойдет шаг 1MB).

Необходимо построить график зависимости среднего времени обращения к одному элементу массива от числа блоков, отстоящих друг от друга на заданном расстоянии. По полученному графику следует сделать вывод о степени ассоциативности кэш-памяти.

3. Определить размер кэш-строки.

Для выполнения задания требуется написать программу, выполняющую чтение элементов массива заданного размера в заданном порядке. Процедура обхода массива x[] должна выглядеть следующим образом:

for (i=0, j=0; j<N; j++) i = x[i];

где элементы массива x[] представляют собой связный список, заполненный специальным образом. Чтобы определить размер кэш-строки, требуется выполнить чтение элементов данных в памяти с различными шагами, начиная от шага 4 байта и заканчивая шагом 512 байт (в предположении, что размер кэш-строки не превышает 512 байт). Размер массива, обход которого выполняется, должен быть не больше объема исследуемой кэш-памяти. Число обращений к элементам должно для всех тестов быть одинаковым.

Необходимо построить график зависимости среднего времени обращения к одному элементу от шага обхода. По полученному графику следует сделать вывод о размере кэш-строки.

4. Определить параметры tlb: объем, степень ассоциативности.

Принцип определения параметров TLB аналогичен принципу определения параметров кэш-памяти. Отличия заключаются только в размерах обходимого массива и шагах обхода.

Для определения объема TLB следует выполнить обход массива с шагом, равным размеру страницы виртуальной памяти (4 KB для архитектуры x86/x86-64). Необходимо построить график зависимости среднего времени обращения к одному элементу от размера массива. По полученному графику сделать вывод о размере TLB. Для определения ассоциативности TLB необходимо выполнять чтение данных в памяти с шагом, вызывающем буксование TLB.

Необходимо построить график зависимости среднего времени обращения к одному элементу массива от числа блоков, отстоящих друг от друга на заданном расстоянии. По полученному графику следует сделать вывод о степени ассоциативности TLB.

РГЗ 3. Функционирование процессора

1. Ознакомиться с программной архитектурой x86/x86-64.

Необходимо изучить набор регистров, основные арифметико-логические команды, способы адресации памяти, способы передачи управления, работу со стеком, вызов подпрограмм, передачу параметров в подпрограммы и возврат результатов, работу с арифметическим сопроцессором.

2. Изучить ассемблерный листинг программы для архитектуры x86/x86-64.

Необходимо познакомиться с программной архитектурой x86/x86-64 путем разбора сгенерированных компилятором ассемблерных листингов простой программы. Для заданной программы на языке Си сгенерировать ассемблерные листинги для архитектуры x86 (используя различные уровни оптимизации) и архитектуры x86-64 (используя различные уровни оптимизации).

Используя полученные листинги:

• сопоставить команды языка Си с машинными командами,

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

• описать и объяснить оптимизационные преобразования, выполненные компилятором,

• продемонстрировать использование ключевых особенностей архитектур x86 и x86-64 на конкретных участках ассемблерного кода,

• сравнить различия в программах для архитектуры x86 и архитектуры x86-64.

• кода.

РГЗ 4. Введение в параллельную обработку

1. Изучить векторные расширения архитектуры x86/x86-64.

2. Реализовать программу, используя векторные расширения архитектуры x86.

Для выполнения заданий необходимо написать программу обращения матрицы A размером N×N:

где , , , , I – единичная матрица N×N (на диагонали – единицы, остальные – нули).

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

• без использования специальных расширений (обычный вариант),

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

• с использованием библиотеки BLAS.

Использовать тип данных float. Размер N предполагать кратным четырем. Каждый вариант программы оптимизировать по скорости, насколько это возможно, и проверить на правильность на небольшом тесте (при N = 8). Сравнить время работы четырех вариантов программы для N=512, число шагов 10 (везде использовать уровень оптимизации –O3):

• обычный вариант без векторизации компилятором,

• обычный вариант с векторизацией компилятора,

• вариант с ручной векторизацией,

• вариант c использованием библиотеки BLAS.

Замер времени выполнить несколько раз, в качестве результата взять минимальное время. Для измерения времени использовать функцию измерения времени работы процесса. Результаты измерений проанализировать и сделать выводы.

3. Реализовать процедуру для быстрого выполнения векторной операции (копирование вектора, умножение вектора на скаляр, сложение векторов и т.п.). Использовать команды векторного расширения и команды управления кэшированием. Сравнить результаты с простым циклом, оптимизированным с помощью компилятора, и со стандартной библиотечной процедурой.

Список литературы для РГР

1. Касперски К. Техника оптимизации программ. Эффективное использование памяти. – СПб.: БХВ-Петербург, 2003. – 464 с.

2. Грушин В.В. Выполнение математических операций в ЭВМ. Погрешности компьютерной арифметики: Учебное пособие / СПбГЭТУ "ЛЭТИ". СПб., 1999. 56 с.

3. Г.Р. Эндрюс. Основы многопоточного параллельного и распределенного программирования. – М.: Изд. Дом Вильямс, 2003. – 330 с.

4. OpenMP Homepage, http://www.openmp.org

5. Гуров В.В. Архитектура микропроцессоров: Учебное пособие. – М..: Интернет-Университет Информационных Технологий: БИНОМ. Лаборатория знаний, 2010. – 272 с.

6. Калачев А.В. Многоядерные процессоры: Учебное пособие. – М..: Интернет-Университет Информационных Технологий: БИНОМ. Лаборатория знаний, 2011. – 247 с.

Интернет-ресурсы:

1. Информационно-аналитические материалы по параллельным вычислениям (http://parallel.ru).

2. Информационные материалы Центра компьютерного моделирования Нижегородского университета (http://www.software.unn.as.ru/ccam).

3. Информационные материалы рабочей группы IEEE по кластерным вычислениям (http://www.ieeetfcc.org).

4. Материалы по параллельным вычислениям (www.openmp.opg).

2