Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Кустикова В.Д., Сиднев А.А., Сысоев А.В. кафедра математического обеспечения ЭВМ, факультет ВМК Лабораторная работа 1: Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители Параллельные численные методы

2 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Содержание Описание приложения Краткое описание инструментов пакета Intel Parallel Studio –Возможности Intel Parallel Composer –Возможности Intel Parallel Inspector –Возможности Intel Parallel Amplifier Подходы к распределению вычислительной нагрузки: –Подход #1: разделение множества чисел на одинаковые части по числу потоков –Подход #2: разделение множества чисел на четные и нечетные –Подход #3: разделение множества чисел на небольшие группы

3 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Тестовая инфраструктура Процессор2 четырехъядерных процессора Intel Xeon E5520 (2.27 GHz) Память16 Gb Операционная система Microsoft Windows 7 Среда разработкиMicrosoft Visual Studio 2008 Компилятор, профилировщик, отладчик Intel Parallel Studio SP1

4 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Разложение множества чисел на простые сомножители Задача: разложить на простые множители (факторизовать) числа из диапазона от 1 до N. Используется алгоритм, который основан на попытке деления факторизуемого числа на каждое из меньших его чисел: Если остаток от деления равен нулю, то очередной множитель запоминается, после чего производится повторная попытка деления на это же число. При нахождении каждого множителя, факторизуемое число делится на него, и алгоритм завершает работу, когда частное от очередного деления становится равным единице.

5 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Пример разложения на простые множители Пример: 12 = ?*?*...*? 12 / 2 = 6; // пробуем разделить на 2 раз 6 / 2 = 3; // пробуем разделить на 2 еще раз 3 / 2 = 1.5; // берем следующий делитель 3 / 3 = 1; // СТОП! – получили единицу

6 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Пример разложения на простые множители Пример: 12 = ?*?*...*? 12 / 2 = 6; // пробуем разделить на 2 раз 6 / 2 = 3; // пробуем разделить на 2 еще раз 3 / 2 = 1.5; // берем следующий делитель 3 / 3 = 1; // СТОП! – получили единицу Результат: 12 = 2 * 2 * 3 Замечание: данный алгоритм факторизации использован только для демонстрации возможностей пакета Intel Parallel Studio. На практике используют алгоритмы Полларда, Диксона и др.

7 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Intel Parallel Studio Intel Parallel Advisor помогает разработчику обнаружить участки кода, которые при параллельной обработке работают эффективнее. Intel Parallel Composer предназначен для быстрого подключения средств параллельной обработки к компилятору языка C/C++ с использованием обширного набора библиотек с функциями многопоточной обработки. Intel Parallel Inspector обеспечивает поиск ошибок в коде приложений для любых моделей параллельного программирования. Intel Parallel Amplifier представляет собой анализатор производительности последовательных и параллельных приложений для поиска узких мест в алгоритме.

8 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Подход #1: разделение множества чисел на одинаковые части по числу потоков Стратегия распределения нагрузки между потоками: // tid – идентификатор потока 1. start (NUM_NUMBERS / NUM_THREADS) * tid + 1; 2. end (NUM_NUMBERS / NUM_THREADS) * (tid + 1) + 1; 50K100K150K200K

9 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта c пустой реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_BV\01_EqualPartition.sln. Сделайте проект 01_EqualPartition рабочим. Измените количество создаваемых потоков по количеству ядер. Убедитесь, что проект компилируется. Реализуйте потоковую функцию в соответствии с подходом #1.

10 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта с реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_CV\01_EqualPartition.sln. Сделайте проект 01_EqualPartition рабочим. Измените количество создаваемых потоков по количеству ядер. Соберите Debug версию проекта. Запустите приложение и убедитесь, что оно упало.

11 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Intel Parallel Inspector (IPI) Инструмент поиска ошибок для приложений, разрабатываемых на C/C++, функционирующих на базе операционной системы Microsoft Windows, использующих преимущества многопоточности. Memory Errors: –поиск ошибок работы с памятью. Threading Errors: –поиск ошибок многопоточности.

12 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. IPI – поиск ошибок многопоточности Схема поиска ошибок многопоточности с использованием Intel Parallel Inspector: –собрать Debug версия программы; –выбрать в IPI режим работы Threading errors; –выбрать режим анализа Analysis level: Extreme; –нажать Run Analysis. Найдите ошибки многопоточности в проекте 01_EqualPartition

13 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Гонка данных (data race) (1) В программе найдена гонка данных:

14 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Гонка данных (data race) (2)

15 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Правильная реализация программы int *tNum = new int[NUM_THREADS]; // создание потоков for (int i = 0; i < NUM_THREADS; i++) { tNum[i] = i; tHandle[i] = CreateThread(NULL, 0, factorization, &tNum[i], 0, NULL); } Убедитесь, что программа отрабатывает корректно!

16 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. IPI – поиск ошибок работы с памятью Схема поиска ошибок работы с памятью с использованием Intel Parallel Inspector: –собрать Debug версия программы; –выбрать в IPI режим работы Memory errors; –выбрать режим анализа Analysis level: Extreme; –нажать Run Analysis. Найдите ошибки работы с памятью в проекте 01_EqualPartition

17 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Утечка памяти В программе найдена утечка памяти: Одна из типичных ошибок в программах: забыли освободить используемую память (сделать delete). Исправьте ошибку!

18 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Intel Parallel Amplifier (1) Hotspots. «На что программа тратит вычислительное время процессора?» Необходимо знать те места в программе, Hotspot-функции, где больше всего тратится вычислительных ресурсов при исполнении, а также тот путь, по которому программа в эти места попала, т.е. стэк вызовов. Concurrency. «Какова степень параллелизации кода?» Часто бывает, что ожидаемый прирост производительности, например, при переходе от 4- ядерной системы к 8-ядерной, так и не достигается. Поэтому необходима оценка эффективности параллельного кода, которая дала бы представление о том, насколько полно используются ресурсы микропроцессора.

19 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Intel Parallel Amplifier (2) Locks and Waits. «Где программа простаивает в ожидании синхронизации или операции ввода-вывода?» Поняв, что программа плохо масштабируется, можно найти, где именно и какие именно объекты синхронизации стали на пути к хорошей параллельности. Возможно необходимо пересмотреть реализацию алгоритмов, а может, и всю параллельную инфраструктуру приложения.

20 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Анализ эффективности («Горячие» точки) Увеличьте количество факторизуемых чисел. Соберите Release версию проекта. Запустите Intel Parallel Amplifier в режиме Hotspots и найдите самую медленную функцию. Время, потраченное на обработку: с

21 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. «Горячая» точка Основное время программа тратит на выполнение операции получения остатка от деления и сравнение: Необходимо минимизировать количество таких операций!

22 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Алгоритмическая оптимизация Используемый алгоритм основан на попытке деления факторизуемого числа на каждое из меньших его чисел. Это избыточный алгоритм! Достаточно выполнять деления до величины, равной половине факторизуемого числа. Внесите соответствующие изменения в потоковую функцию.

23 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Алгоритмическая оптимизация Запустите Intel Parallel Amplifier в режиме Hotspots и оцените полученное ускорение. Время, потраченное на обработку: с

24 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Анализ эффективности (Степень параллелизма) Запустите Intel Parallel Amplifier в режиме Concurrency и оцените степень параллелизма.

25 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Анализ эффективности Видно, что программа достаточно длительное время работает в 2 потока

26 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Подход #2: разделение множества чисел на четные и нечетные Стратегия распределения нагрузки между потоками (проект 02_EvenOdd): // tid – идентификатор потока // i – индекс числа в наборе чисел, факторизуемых потоком 1. number = i * NUM_THREADS + tid + 1; …

27 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта c пустой реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_BV\02_EvenOdd.sln. Сделайте проект 02_EvenOdd рабочим. Измените количество создаваемых потоков по количеству ядер. Убедитесь, что проект компилируется. Реализуйте потоковую функцию в соответствии с подходом #2.

28 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта с реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_CV\02_EvenOdd.sln. Сделайте проект 02_EvenOdd рабочим. Измените количество создаваемых потоков по количеству ядер. Соберите Release версию проекта. Убедитесь, что оно отработало корректно.

29 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Запустите Intel Parallel Amplifier в режиме Concurrency и оцените степень параллелизма. Подход #2. Анализ эффективности

30 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Подход #2. Оценка степени параллелизма Большую часть времени программа работает в 4 потока Но! Четные числа факторизуется проще, чем нечетные

31 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Подход #3: разделение множества чисел на небольшие группы Стратегия распределения нагрузки между потоками (проект 03_Blocks): // tid – идентификатор потока 1. numberOfGrains = NUM_NUMBERS / NUM_THREADS / GRAIN_SIZE; 2. for i = 0 to numberOfGrains 3. begin = (NUM_THREADS * i + tid) * GRAIN_SIZE + 1; 4. end = (NUM_THREADS * i + tid + 1) * GRAIN_SIZE + 1; …

32 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта c пустой реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_BV\03_Blocks.sln. Сделайте проект 03_Blocks рабочим. Измените количество создаваемых потоков по количеству ядер. Убедитесь, что проект компилируется. Реализуйте потоковую функцию в соответствии с подходом #3.

33 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Открытие проекта с реализацией потоковой функции Откройте решение.\SEPARATEDPROJECTS_CV\03_Blocks.sln. Сделайте проект 03_Blocks рабочим. Измените количество создаваемых потоков по количеству ядер. Соберите Release версию проекта. Убедитесь, что оно отработало корректно.

34 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Запустите Intel Parallel Amplifier в режиме Concurrency и оцените степень параллелизма. Подход #3. Анализ эффективности Но! Как определить оптимальный размер блоков?

35 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Подход #3. Оценка степени параллелизма Большую часть времени программа работает в 8 потоков

36 Н.Новгород, 2010 г. Распределение вычислительной нагрузки в параллельной программе на примере задачи разложения набора чисел на простые множители. Вопросы ???