Two-sided Thomas, locality
Основные авторы описания: Вад.В.Воеводин (раздел 2), А.М.Теплов (раздел 3).
Содержание
1 Ссылки
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция Kernel).
2 Локальность данных и вычислений
Как видно по графу алгоритма, локальность данных по пространству хорошая - все аргументы, что нужны операциям, вычисляются "рядом". Однако по времени локальность вычислений не столь хороша. Если данные задачи не помещаются в кэш, то вычисления в "верхнем левом" и "нижнем правом" "углах" СЛАУ будут выполняться с постоянными промахами кэша. Отсюда может следовать одна из рекомендаций прикладникам, использующим прогонку, - нужно организовать все вычисления так, что бы прогонки были "достаточно коротки" для помещения данных в кэш.
При этом, однако, прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней, если две основные ветви реализуются по отдельности на разных ядрах или же последовательно друг за другом [1]. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что резко ухудшает эффективность исполнения прогонки даже на современных однопроцессорных и одноядерных системах. Именно поэтому в примере п.2.1 обе ветви (как прямого, так и обратного хода) сведены в общий цикл. Это, однако, даёт выигрыш только по сравнению с чересчур локальной монотонной прогонкой, ибо эффективность остаётся малой.
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 1 представлен профиль обращений в память для реализации точечного варианта встречной прогонки. Данный профиль состоит из двух этапов (разделены желтой линией), на каждом из которых выполняются обращения к 4-м массивам. Обращения к разным массивам разделены зелеными горизонтальными линиями. Исходя из общего профиля, можно предположить, что на первом этапе ко всем массивам выполняются примерно одни и те же обращения, которые в каждом случае формируют два параллельно выполняемых последовательных перебора, один по возрастанию элементов массива, другой – по убыванию.
На втором этапе профили для разных массивов отличаются, однако они также напоминают обычные последовательные переборы. Если это верно, то в целом данный профиль обладает высокой пространственной локальностью (обращения к соседним элементам следуют близко друг от друга) и достаточно низкой временной (повторное использование данных практически отсутствует). Рассмотрим профиль более детально и проверим, так ли это.
На рис. 2 представлен выделенный зеленым фрагмент общего профиля. Здесь видно, что обращения к 4-м массивам обладают регулярной структурой, при этом действительно соседние элементы задействованы рядом. Однако сложно определить с точностью до отдельных обращений, как они устроены.
На рис. 3 отдельно рассмотрены профили из рис. 2. При таком рассмотрении видно, что в целом все профили действительно состоят из последовательных переборов, только на каждом шаге перебора выполняется разное число обращений. В профиле на рис. 3а на каждом шаге задействован текущий и предыдущий элементы; в профиле на рис. 3б, видимо, задействован еще и следующий элемент. Профили 3в и 3г устроены чуть проще – только в одном переборе на каждом шаге выполняются два обращения.
Исходя из полученной информации, можно сделать вывод, что локальность обращений даже лучше, чем мы предположили при рассмотрении общего профиля. Это связано с тем, что во многих случаях одни и те же данные используются подряд несколько раз, что повышает как пространственную, так и временную локальность.
2.1.2 Количественная оценка локальности
Условия запуска описаны здесь.
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 4 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). В целом значение daps для данной программы показывает достаточно высокую производительность работы с памятью, что соответствует нашим ожиданиям согласно приведенному выше описанию локальности.
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
На рисунке 5 значения приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Для этой программы оценка cvg очень высока, даже лучше, чем в случае теста Linpack. Здесь можно отметить довольно заметную разницу между двумя оценками, daps и cvg. Возможные причины такой разницы здесь могут быть те же, что и в случае обычной прогонки, которые описаны здесь.
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
О масштабируемости самой встречной прогонки, как почти непараллельного алгоритма, говорить нельзя в принципе, за исключением разве что двухпроцессорных систем. Понятие масштабируемости неприменимо, поскольку описываемый алгоритм не предполагает параллельной реализации.
3.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости реализации алгоритма согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов"[2] Суперкомпьютерного комплекса Московского университета.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров 1;
- размер области [10240 : 1024000] с шагом 10240.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 0.0634%;
- максимальная эффективность реализации 0.0651%.
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
Мизерная эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о локальности данных и вычислений.
4 Динамические характеристики и эффективность реализации алгоритма
В силу существенно последовательной природы алгоритма и его избыточной локальности, исследование его динамических характеристик представляется малоценным.
Для проведения экспериментов использовалась реализация алгоритма прогонки, в реализации, доступной здесь. Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7. На рисунках показана эффективность реализации алгоритма встречной прогонки.
На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 8% в среднем. Это указывает на достаточно высокую нагрузку выполнения последовательного алгоритма на 8-ми ядерном процессоре.
На Рисунке 10 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений, достигающая в пике 2,7 млн операций в секунду.
На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое даже для одного ядра и находится на уровне 550 тыс/сек. Это указывает на достаточно хорошую локальность данных.
На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно низкое для небольшого числа процессов и находится на уровне 110 тыс/сек. Отношение промахов L1/L3 около 5, что выше средних показателей по типичным задачам. Это также указывает на хорошую локальность вычислений.
На графике чтений из памяти на наблюдается достаточно высокая активность чтения из памяти процессами. Так как активно работает только один процесс, то и активность чтения соответствует максимальным значениям. Активность достаточно типична для приложений такого класса.
Активность записи в память достаточно низкая, это вполне ожидаемо для такого алгоритма, и так же указывает на достаточно высокую локальность вычислений.
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 1. Это свидетельствует о стабильной работе программы с работающим только одним процессом. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала не очень эффективно, но с высокой локальностью вычислений. Интенсивность использования памяти низкая, при этом локальность вычислений обеспечивает достаточно эффективное использование кэш-памяти.
5 Результаты прогонов
6 Литература
- ↑ Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.
