Face recognition, scalability
Основные авторы описания: Н.Ю.Багров.
Содержание
1 Ссылки
2 Локальность данных и вычислений
Данный алгоритм производит вычисления скалярных произведений, поэтому на этом этапе все обращения к памяти обладают свойством локальности. Биометрический шаблон полностью помещается в кэш память любого современного процессора, данные под базу изображний выделяются в виде больших непрерывных блоков памяти.
Сортировка результатов также обладает свойством локальности, поскольку массив хранится непрерывно в памяти. При небольшом размере базы (1-10M изображений) он может полностью поместиться в кэш памяти.
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
В дальнейшем во всех тестах будет использоваться сервер с 2x E5-2683v3 128GB RAM. MOPS - миллионы операций (для map -скалярное произведение, reduce - сортировка) в секунду.
Каждый тест проводится 20 раз, результаты усредняются.
Т.к. скорость чтения из DDR4 памяти 17GB/s (на практике немного меньше), то с 4 каналов памяти (по 2 на каждый процессор) нельзя считывать быстрее, чем 68GB/s. База 200M дескрипторов занимает 98GB ram, поэтому время 2300ms для вычисления всех скалярных произведений близко к нижней границе. Дальнейшее увеличение числа потоков на одном сервере не будет приводить к существенному ускорению работы программы.
Результаты работы reduce функции в зависимости от размера базы и числа потоков в openmp:
Reduce этап лучше распараллеливается, поскольку в нем намного меньше число обращений к памяти. Его также можно ускорять, например подбирая оптимальный размер блока (chunk size). Для базы в 200M лиц лучшая скорость 1400ms (достигается на 20 потоках, дальше ускорения нет).
Значительное ускорение при размере базы в 100M (значение близко к 64GB) возникает предположительно из-за использование памяти второго процессора (суммарно 4 канала памяти, а не 2).
3.2.1 Исследование влияния HyperThreading на работу алгоритма
Поскольку могут возникать проблемы из-за низкой пропускной способности памяти, можно предположить, что HyperThreading позволит ускорить работу программы. Во время ожидания данных из памяти может быть задействован второй вычислитель в ядре.
Синяя точка на графике - лучший результат c HyperThreading, красная - HyperThreading выключен.
Видно, что включение HyperThreading повышает производительность системы. Для reduce шага это ускорение значительно.
4 Динамические характеристики и эффективность реализации алгоритма
Эксперименты проводились на сервере с 2x E5-2683v3 128GB RAM.
Для семейства процессоров на ядре haswell возможно выполнение 32 операций умножения+сложения за такт.
Поэтому пиковая производительность [math]R_{\rm peak}=2·14·32·2.0·10^9[/math], где
- 2 - число процессоров
- 14 - количество ядер на каждом из процессоров
- 32 - количество операций за один такт
- [math]2.0·10^9[/math] - частота ядра без turbo boost
FLOPS алгоритма [math]k=100·10^6·128·2[/math], где
- [math]100·10^6[/math] - число операций в секунду
- 128·2 - количество действий, необходимых для проведения одного сравнения
Эффективность для map = [math]k[/math] / peak = 0.014 (1.42%)
