Читайте также:
|
Вопросы к экзамену
1. Виды зависимостей по данным (причин гонок данных) в многопоточных программах. Чем опасны гонки данных?
Под данных (Data Race) понимают ситуацию, когда два или более потока соперничают за обладание некоторым общим ресурсом. Чаще всего соперничество возникает из-за такого ресурса как оперативная память. Но таковым ресурсом может быть и внешняя память (работа с одним и тем же файлом, например), или некоторое устройство, подключенное к компьютеру.
§ Read after read (RAR)
§ Read after write (RAW)
R2= R1 + R3(write to R2)
R4 = R2+ R3 (read R2)
§ Write after read (WAR)
R4 = R1 + R3 (read R3)
R3= R1 + R2 (write to R3)
§ Write after write (WAW)
R2= R4 + R7 (write to R2)
R2= R1 + R3 (write to R2)
Типы планировщика (scheduler), используемые в OpenMP, их достоинства и недостатки.
Schedule задаёт, каким образом распределяются итерации цикла. Задается вид алгоритма планирования и, если необходимо, числовой параметр алгоритма.
schedule(kind[, chunk_size])
§ static – итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно
§ dynamic – распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1)
§ guided – размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1)
§ runtime – правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен)
Динамическое и управляемое планирование хорошо подходят, если при каждой итерации выполняются разные объемы работы или если одни процессоры более производительны, чем другие. Как правило, при управляемом планировании код выполняется быстрее, чем при динамическом, вследствие меньших издержек на планирование.
При статическом планировании нет никакого способа, позволяющего сбалансировать нагрузку на разные потоки.
3. Классификация параллельных систем по Флинну с примерами.
По числу потоков команд и потоков данных выделяют четыре класса архитектур: SISD, MISD, SIMD, MIMD.
1. SISD (Single Instruction stream / Single Data stream) – Вычислительная система с одиночным потоком команд и одиночным потоком данных.
2. MISD (Multiple Instruction streams / Single Data stream) – Вычислительная система с одиночным потоком команд и множественным потоком данных. Пример: некоторые считают, что конвейерные ЭВМ, но реально – нет.
3. SIMD(Single Instruction stream / Multiple Data streams) – Вычислительная система со множественным потоком команд и одиночным потоком данных. Пример: векторная архитектура.
4. MIMD (Multiple Instruction streams / Multiple Data streams) – Вычислительная система со множественным потоком команд и множественным потоком данных. Пример: многопроцессорные системы, где процессоры обрабатывают множественные потоки данных.
SPMD(Single Program / Multiple Data streams) – Параллельное программирование:
§ На основе процессов
§ На основе потоков внутри одного процесса
§ Гибридный: использование параллельных потоков и процессов в одном приложении
4. Коэффициент ускорения параллельной программы и закон Амдала.
a – доля последовательного кода
p – число процессоров
Время работы параллельной программы:
Time = a + (1-a)/p
Ускорение параллельной программы:
Speedup = 1/Time = 1/(a + (1-a)/p)
→масштабируемость параллельных программ органичена
При 50% – ускорение в 2 раза.
При 75% – ускорение в 4 раза.
При 90% – ускорение в 10 раза.
При 95% – ускорение в 20 раза.
Причины низкой производительности последовательных и параллельных программ.
Причины низкой эффективности на уровне программы и микроархитектуры
•неоптимальный алгоритм
•отсутствие или неоптимальность параллельной версии для многоядерных систем
•размещение данных (мешающее конвейеру и параллельному исполнению)
•простои выполнения программы из-за ожидания ресурсов: потоков, сети, диска
•промахи в кэш-память
•ошибки предсказания ветвлений
6. Каким требованиям должны удовлетворять тесты для профилирования программы?
Подготовка программы
Для выполнения анализа приложения потребуются:
§ Исполняемый (бинарный) файл в сборке типа Release (со всеми оптимизациями)
§ Файлы исходного кода (желательно, поскольку в этом случае результаты сбора статистики можно «привязать» к исходному коду программы)
§ символьная информация
§ информация о номерах строк
Тестовый набор входных данных
Главные характеристики:
•Воспроизводимость сценария
•Репрезентативность
•Полнота охвата
7. Как устранять гонки данных для корректной работы программы? Плюсы и минусы разных приёмов.
1. Взаимоисключения (mutex, мьютекс) — это объект синхронизации, который устанавливается в особое сигнальное состояние, когда не занят каким-либо потоком. Только один поток владеет этим объектом в любой момент времени, отсюда и название таких объектов (от английского mutually exclusive access — взаимно исключающий доступ) — одновременный доступ к общему ресурсу исключается. После всех необходимых действий мьютекс освобождается, предоставляя другим потокам доступ к общему ресурсу. Могут привести к взаимной блокировке потока при попытке рекурсивного захвата.
2. Семафоры представляют собой доступные ресурсы, которые могут быть приобретены несколькими потоками в одно и то же время, пока пул ресурсов не опустеет. Тогда дополнительные потоки должны ждать, пока требуемое количество ресурсов не будет снова доступно. Семафоры очень эффективны, поскольку они позволяют одновременный доступ к ресурсам.
3. События. Объект, хранящий в себе 1 бит информации «просигнализирован или нет», над которым определены операции «просигнализировать», «сбросить в непросигнализированное состояние» и «ожидать». Ожидание на просигнализированном событии есть отсутствие операции с немедленным продолжением исполнения потока. Ожидание на непросигнализированном событии приводит к приостановке исполнения потока до тех пор, пока другой поток не просигнализирует событие. Возможно ожидание нескольких событий в режимах «любого» или «всех».
4. Критические секции обеспечивают синхронизацию подобно мьютексам за исключением того, что объекты, представляющие критические секции, доступны в пределах одного процесса.
8. Плюсы и минусы параллельного программирования на основе процессов и на основе потоков.
Использование нескольких процессов фактически означает использование нескольких программ, которые выполняются независимо друг от друга. Такой подход создает большие неудобства в управлении обмена данными между этими программами. В качестве альтернативы существует другой подход – создание многопоточных программ. Обмен данными между потоками существенно упрощается. Но управление такими программами усложняется, и вся ответственность ложится на программиста.
На основе процессов:
§ Обмен данных между процессами с помощью сообщений
§ Обмен сообщениями: блокирующий или асинхронный
§ Передача сообщений имеет значительные накладные расходы
На основе потоков внутри одного процесса:
§ Обмен данных между потоками через общую память
§ Нужна координация потоков (mutexes, semaphores,...), чтобы исключить порчу общей памяти
§ Проблема синхронности кешей
§ Проблема медленного обращения к оперативной памяти
Гибридный: использование параллельных потоков и процессов в одном приложении
9. Основные трудности при проектировании и реализации параллельного кода.
При проектировании:
§ Каков ожидаемый выигрыш от распараллеливания кода?
§ Оправданы ли усилия разработчика?
§ Будет ли параллельный код масштабироваться с увеличением числа ядер и процессоров?
В реализации:
§ Правильно распараллелить нужный код
§ Не сломать тесты
§ Добиться желаемого ускорения программы
§ Идентифицировать разделяемые ресурсы
§ Отладить параллельный код и исправить трудновоспроизводимые ошибки
10. Как ведут себя потоки программы до, внутри и после директивы #parallel в OpemMP?
Принцип организации параллелизма:
Директива parallel (основная директива OpenMP):
Формат директивы parallel
#pragma omp parallel [clause...] newline
{structured_block}
11. Зачем повышать производительность программного обеспечения?
Зачем профилировать? Почему скорость важна?
•Скорость работы – часть нефункциональных требований к программе
•Недостаточная скорость – ущерб качеству вплоть до провала проекта
•Рост вычислительных мощностей уже не даёт прямого роста производительности программ: the free lunch is over
•HPC (High-Performance Computing): от производительности программ зависит стоимость покупки и обслуживания суперкомпьютерной системы
•Более точные и быстрые решения сложных задач
•Разработка программ для устройств с меньшими ресурсами, например, для встраиваемых (embedded) систем
Цели оптимизации программного обеспечения
1.Минимизация времени выполнения
2.Минимизация объёма потребляемой памяти
3.Минимизация энергопотребления процессором
Актуальность вопроса объясняется постоянно возрастающей сложностью и значимостью программных средств. Особое внимание производительности уделяется:
§ в инженерных и научных разработках, где часто производятся сложные длительные вычисления, а процессорное время на кластерных системах дорого и ограничено;
§ в web-приложениях, в которых время генерации страницы критично для пользователя и напрямую зависит от объемов серверных мощностей;
§ в встраиваемых программных продуктах, и т.д.
Тщательный анализ производительности программного продукта может существенно сократить стоимость самого оборудования и затраты на поддержание работоспособности, увеличить лояльность пользователей ПО.
12. Какие данные собирают профилировщики?
Сбор статистики по производительности кода программы
•Профилировщик – отладчик особого рода, контролирует выполнение, собирает данные и формирует отчёт:
1. Общее время исполнения функций/методов
2. Удельное время исполнения
3. Количество вызовов
4. Структура вызовов функций (caller/callee)
5. Места возникновения конфликтов и ожиданий
6. Значения аппаратных счётчиков
Типы профилировщиков по способам сбора информации:
1. Event-based - считают события: вызовы, возвраты, исключения, аппаратные счётчики
2. Sampling - сбор статистики через заданные промежутки времени; возможна запись стека выполнения
3. Instrumentation - модификация кода приложения – вставка специальных вызовов; больше накладные расходы
13. Основные методы оптимизации производительности последовательных и параллельных программ.
Цикл оптимизации программы
1.Выявление «горячих пятен» (Hotspots)
2. Определение причин низкой эффективности:
•системный уровень (уровень ОС: использование процессора, ввод-вывод)
•уровень программы (эффективность алгоритма, параллельность)
•уровень микроархитектуры
3. Оптимизация
•более производительный алгоритм
•оптимизирующий распараллеливающий компилятор
•оптимизированные библиотеки
•переупорядочение данных
Основные подходы к оптимизации
1.Оптимизация алгоритма
2.Распараллеливание
3.Оптимизация доступа к памяти
-Кэш, ОЗУ, диск, сетевые хранилища
4. Векторизация
5. Оптимизация на уровне инструкций:
-загрузки конвейеров
-циклов
-ветвлений
Пошаговый подход к оптимизации кода
1. Осуществляется профилирование кода (проблемных участков) и выявляются “горячие точки” (hotspots) – участки программы выполняющиеся дольше всего
2. Горячие точки сортируются в порядке не убывания времени выполнения–формируется приоритетный список участков программы для последующей оптимизации
3. Каждая горячая точка оптимизируется
4. После оптимизации каждого “hotspot”
проводится тестирование программы –проверяется совпадение результатов её работы до модификации и после внесения изменений
Дата добавления: 2015-01-29; просмотров: 87 | Поможем написать вашу работу | Нарушение авторских прав |
| <== предыдущая лекция | | | следующая лекция ==> |
| Б) валютний курс відображає ціну одиниці іноземної валюти в національній валюті. | | | Строение и свойства атомов. |