Задание к практической работе №5 «Векторизация вычислений»

Задание к практической работе №5 «Векторизация вычислений»

1. Написать три варианта программы, реализующей алгоритм из задания:

· вариант без векторизации,

· вариант с ручной векторизацией (выбрать любой вариант из возможных трех: ассемблерная вставка, встроенные функции компилятора, расширение GCC),

· вариант с матричными операциями, выполненными с использованием оптимизированной библиотеки BLAS. Для элементов матриц использовать тип данных float.

2. Проверить правильность работы программ на нескольких небольших тестовых наборах входных данных.

3. Каждый вариант программы оптимизировать по скорости, насколько это возможно.

4. Сравнить время работы трех вариантов программы для N=2048, M=10.

5. Составить отчет по лабораторной работе. Отчет должен содержать все обязательные элементы из шаблона и к тому же следующее:

· Результаты измерения времени работы трех программ.

· Полный компилируемый листинг реализованных программ и команды для их компиляции.

· Вывод по результатам лабораторной работы

Вычислительный алгоритм к заданию:

Комментарий

Данная практика основана на pdf для лабораторной №7 и посвящена использованию векторных расширений архитектуры x86 и векторных регистров. Основная идея в том, что в векторном регистре мы храним не одно, а целый набор значений одного типа и за одну ассемблерную команду выполняем действие не с одним числом, а сразу с несколькими. Естественно, в первую очередь, это применяется для операций над массивами. То есть, если мы работаем с двумя 128-битными xmm-регистрами, то в них мы можем положить по 16 чисел типа float и за одну команду получить, например, сумму сразу 16 элементов векторов. Также в один регистр можно положить 16 int-ов или 8 double-ов.

В pdf с описанием приводится 3 варианта использования векторных расширений. Если сделаете с использованием расширений AVX или AVX-512 – честь вам и хвала! А если примените ассемблерные вставки – то я сразу захочу поставить вам «отлично» за практический курс (но к сожалению не смогу L ). В прошлом году, по-моему, только 1 или 2 человека сделали в моих группах с использованием AVX, а с ассемблерными вставками - никто.

Пару слов по самой задаче. На каждом шаге Вы должны умножать очередную матрицу справа на R. То есть строку очередной матрицы Rn (назовем ее так) Вы должны умножать на столбец матрицы R. Распишем этот цикл. Пусть Q – итоговая матрица произведения (Q = Rn*R). Пусть все матрицы квадратные размерности P. Тогда:
for (i = 0; i < P; i++) {
for (j = 0; j < P; j ++) {
for (k = 0; k < P; k++) {
Q[i][j] += Rn[i][k]*R[k][j];
}
}
}

Это стандартный алгоритм умножения матриц. Но задайтесь вопросом – что в нем плохо с точки зрения производительности? Не читайте сразу текст дальше. Остановитесь на этом моменте и подумайте 5 минут над вопросом… Подумали? Тогда сверьте свой ответ с дальнейшими рассуждениями. Когда мы считываем элементы матрицы, то наиболее выгодно считывать построчно. Вы ведь знаете, что в C/C++ элементы матрицы хранятся в памяти построчно? Когда процессор считывает один элемент, то на самом деле он подгружает из памяти в свой кэш (не будем здесь вдаваться в то, что кэш многоуровневый – это тема следующей практики) целую последовательность из десятков байт (например, 64 байта), лежащих ПОДРЯД. То есть за одно обращение в оперативную память он может подгрузить, например, 16 вещественных чисел одинарной точности (помните, что вам следует работать с типом float). Если же процессор вынужден брать из памяти элементы матрицы постолбцово, то есть не подряд, то за каждым следующим элементом он должен лезть отдельно. Следовательно, количество обращений в медленную память увеличивается на порядок. Какой выход? Еще раз пересмотрите фрагмент кода с умножением. Подумайте – что будет, если циклы по i, j, k переставлять местами. Надеюсь вы пришли к правильному выводу – результат умножения матриц будет тем же. А теперь определите ту комбинацию этих перестановок, при которой ни одна из матриц не будет читаться постолбцово.

Во втором варианте (собственная векторизация) обязательно векторизуйте умножение матриц, поскольку на это требуется больше всего времени. При этом крайне нежелательно использовать фрагмент из примера с intrinsic-функциями из pdf-ки с описанием лабы. Там используется противоестественный и неочевидный прием с перемешиванием элементов вектора (shuffle). Лучше сделайте проще и нагляднее. Причем самостоятельно.

В третьем варианте (с библиотекой BLAS) используйте хотя бы 2 BLAS-функции (для умножения одной матрицы на другую и сложения матриц).

ПРО ПРЕЗЕНТАЦИЮ:

Много слайдов взято из презентаций компании Intel про векторизацию в их процессорах. Причем местами там уже устаревшая информация (например на слайде 4 говорится про то, что AVX512 – дело будущего, а в современных процессорах он уже используется). И из этих слайдов сочится нескрываемая реклама. Однако я старался выбирать слайды, содержащие полезную информацию. На слайдах 3, 5 идет речь о параллелизме в смысле распределения какой-то большой вычислительной работы по процессорным ядрам при помощи многопоточной программы, порождающей несколько нитей (thread). Об этом мы не говорим в рамках данного курса. Эта тема дисциплины «Основы параллельного программирования», которая будет у вас в следующем семестре. В данной теме нас интересует только векторизация в рамках одной нити.

Еще серия слайдов – про ассемблерные вставки и ассемблерные команды, относящиеся к векторизации. Это на случай, если всё-таки захотите сделать на ассемблерных вставках.

Обратить внимание на доп. ссылки к лабе 7 на странице курса. Особенно справочник на Intel® Developer Zone, где вы можете искать по имени функции. А также на пример с blas-функцией.

Успехов!

С уважением,

Власенко А. Ю.