Методы анализа и предсказания эффективности DVM-программ В.Н.Ильяков, Н.В.Ковалева, В.А.Крюков Институт прикладной математики им. М.В. Келдыша РАН, г. Москва

Факторы, определяющие эффективность выполнения параллельных программ степень распараллеливания программы - доля параллельных вычислений в общем объеме вычислений равномерность загрузки процессоров во время выполнения параллельных вычислений время, необходимое для выполнения межпроцессорных обменов степень совмещения межпроцессорных обменов с вычислениями

Характеристики эффективности DVM-программ Пользователь может получить следующие характеристики эффективности программы и отдельных ее частей: execution time - астрономическое время выполнения productive time - прогнозируемое время выполнения на одном процессоре parallelization efficiency – прогнозируемая эффективность параллельного выполнения = productive time / (N * execution time) lost time – потерянное время = N * execution time - productive time где N - число процессоров

Характеристики эффективности DVM-программ Компоненты lost time: insufficient parallelism - потери из-за выполнения последовательных частей программы на всех процессорах communication - потери из-за межпроцессорных обменов Idle time - простои процессоров из-за отсутствия работы и важный компонент времени коммуникаций – real synchronization - реальныепотери из-за рассинхронизации

Характеристики эффективности DVM-программ Кроме того, выдаются характеристики: load imbalance - возможные потери из-за разной загрузки процессоров synchronization - возможные потери на синхронизацию time_variation - возможные потери из-за разброса времен overlap - возможное сокращение коммуникационных расходов за счет совмещения межпроцессорных обменов с вычислениями

Processor system=16 Statistics has been accumulated on DVM-system version 348, platform MVS1000m Analyzer is executing on DVM-system version 348, platform MVS1000m INTERVAL ( NLINE=6 SOURCE=sorb.fdv ) LEVEL=0 EXE_COUNT=1 --- The main characteristics --- Parallelization efficiency Execution time Processors 16 Total time Productive time ( CPU= Sys= I/O= ) Lost time Insufficient parallelism ( User= Sys= ) Communication ( Real_sync= Starts= ) Idle time Load imbalance Nop Communic Real_sync I/O Reduction Shadow

Проблема – нестабильность характеристик Нестабильность коммуникаций Изменение состава процессоров при неоднородности коммуникационной среды Загрузка коммуникационной среды другими работами Можно выдавать стабильные характеристики коммуникаций (вычислять их по формулам, зависящим от длин сообщений, латентности и пропускной способности коммуникационной среды) Нестабильный разброс времен => рассинхронизация

Нестабильность производительности процессоров Попадание на медленные процессоры (появляется разбалансировка, можно запрашивать лишние процессоры и отключать медленные) Частая активизация системных процессов (возрастает время коммуникаций за счет времени реальной рассинхронизации) Можно моделировать не только коммуникации, но и загрузку процессоров => предсказание эффективности

Предсказатель эффективности получает характеристики выполнения DVM- программы на рабочей станции и использует их для предсказания эффективности ее выполнения на кластере с заданными параметрами (конфигурация, производительность процессоров, количество и характеристики каналов связи) Для реализации такой схемы предсказания необходимо тщательное проектирование интерфейса с run-time системой

Параметры целевого компьютера // System type = network | transputer | myrinet type = myrinet ( 8 ); // Communication characteristics (mks) start time = 10; send byte time = 0.01; // Comparative processors performance power = 1.00;

Принципиальные трудности предсказания эффективности Для современных процессоров трудно прогнозировать время выполнения разных фрагментов программы (кэш-память и динамическое планирование выполнения) Трудно моделировать работу программных компонентов коммуникационной системы => очень сложно получить точные характеристики выполнения программы

Предсказатель – инструмент отладки эффективности Он может довольно точно оценить влияние основных факторов: степень распараллеливания программы - доля параллельных вычислений в общем объеме вычислений равномерность загрузки процессоров во время выполнения параллельных вычислений время, необходимое для выполнения межпроцессорных обменов степень совмещения межпроцессорных обменов с вычислениями =>есть еще важный фактор – эффективное выполнение вычислений на процессорах

Предсказатель – инструмент отладки эффективности На современных процессорах эффективность вычислений может отличаться в 3-7 раз в зависимости от их согласованности с организацией кэш-памяти Поэтому важно предоставить программисту инструмент, помогающий ему обеспечить такую согласованность. Согласованность же с особенностями коммуникационных сетей (группировка или разбиение сообщений, их планирование) должны обеспечивать системы программирования с языков высокого уровня

Выводы Отладка эффективность параллельных программ для кластеров – процесс очень сложный и трудоемкий Развитые средства анализа эффективности могут существенно ускорить этот процесс Из-за нестабильности характеристик эффективности при коллективном использовании кластеров важную роль могут сыграть средства предсказания этих характеристик посредством моделирования выполнения параллельных программ Для достижения эффективности параллельной программы приходится многократно изменять программу, иногда кардинально меняя схему ее распараллеливания. Поэтому важно использовать высокоуровневые средства разработки параллельных программ