ASA в 13:25, 20 июля 2022

2022-07-20T13:25:26Z

← Предыдущая версия		Версия от 13:25, 20 июля 2022
Строка 4:		Строка 4:

	= Ссылки =		= Ссылки =

	~~http://www.graph500.org~~

	= Локальность данных и вычислений =		= Локальность данных и вычислений =

ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:BagnikitaН.Ю.Багров]. = Ссылк...»

2022-07-20T13:24:56Z

Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:Bagnikita<b>Н.Ю.Багров</b>]. = Ссылк...»

Новая страница

{{level-i}}

Основные авторы описания: [https://algowiki-project.org/ru/Участник:Bagnikita<b>Н.Ю.Багров</b>].

= Ссылки =

http://www.graph500.org

= Локальность данных и вычислений =

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

Сортировка результатов также обладает свойством локальности, поскольку массив хранится непрерывно в памяти. При небольшом размере базы (1-10M изображений) он может полностью поместиться в кэш памяти.

== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===
=== Количественная оценка локальности ===
= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==

В дальнейшем во всех тестах будет использоваться сервер с 2x E5-2683v3 128GB RAM. MOPS - миллионы операций (для map -скалярное произведение, reduce - сортировка) в секунду.

Каждый тест проводится 20 раз, результаты усредняются.

[[Файл:Facerecognition-matcher.png|thumb|center|700px|Рисунок 1. Результаты работы map функции в зависимости от размера базы и числа потоков в openmp]]

Т.к. скорость чтения из DDR4 памяти 17GB/s (на практике немного меньше), то с 4 каналов памяти (по 2 на каждый процессор) нельзя считывать быстрее, чем 68GB/s. База 200M дескрипторов занимает 98GB ram, поэтому время 2300ms для вычисления всех скалярных произведений близко к нижней границе. Дальнейшее увеличение числа потоков на одном сервере не будет приводить к существенному ускорению работы программы.

Результаты работы reduce функции в зависимости от размера базы и числа потоков в openmp:
[[Файл:Facerecognition_reduce.png|thumb|center|700px|Рисунок 2. Результаты работы reduce функции в зависимости от размера базы и числа потоков в openmp]]

Reduce этап лучше распараллеливается, поскольку в нем намного меньше число обращений к памяти. Его также можно ускорять, например подбирая оптимальный размер блока (chunk size). Для базы в 200M лиц лучшая скорость 1400ms (достигается на 20 потоках, дальше ускорения нет).

Значительное ускорение при размере базы в 100M (значение близко к 64GB) возникает предположительно из-за использование памяти второго процессора (суммарно 4 канала памяти, а не 2).

[[Файл:Facerecognition_overall.png|thumb|center|700px|Рисунок 3. Суммарная скорость работы системы в зависимости от размера базы и числа потоков в openmp]]

==== Исследование влияния HyperThreading на работу алгоритма ====

Поскольку могут возникать проблемы из-за низкой пропускной способности памяти, можно предположить, что HyperThreading позволит ускорить работу программы. Во время ожидания данных из памяти может быть задействован второй вычислитель в ядре.

Синяя точка на графике - лучший результат c HyperThreading, красная - HyperThreading выключен.

[[Файл:Facerecognition-ht-matcher.png|thumb|center|700px|Рисунок 4. Результаты работы map функции в зависимости от размера базы и числа потоков в openmp (10-56 потоков)]]

[[Файл:Facerecognition-ht-reduce.png|thumb|center|700px|Рисунок 5. Результаты работы reduce функции в зависимости от размера базы и числа потоков в openmp (10-56 потоков)]]

[[Файл:Facerecognition-ht-overall.png|thumb|center|700px|Рисунок 6. Суммарная скорость работы системы в зависимости от размера базы и числа потоков в openmp (10-56 потоков)]]

Видно, что включение HyperThreading повышает производительность системы. Для reduce шага это ускорение значительно.

= Динамические характеристики и эффективность реализации алгоритма =

Эксперименты проводились на сервере с 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%)

= Результаты прогонов =

[[Категория:Статьи в работе]]

[[En:Face recognition, scalability]]

Face recognition, scalability - История изменений

ASA в 13:25, 20 июля 2022

ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:BagnikitaН.Ю.Багров]. = Ссылк...»