Презентация на тему «На эффективность выполнения различных видов деятельности»

Система программирования DVM

Н.А.Коновалов, В.А.Крюков Институт прикладной математики им. М.В. Келдыша РАН, г. Москва e-mail: konov@keldysh.ru, krukov@keldysh.ru

Отладка DVM-программ

Под отладкой DVM-программ подразумеваются два различных вида деятельности : функциональная отладка, целью которой является достижение правильности функционального выполнения программы; отладка эффективности, целью которой является достижение требуемого уровня эффективности параллельного выполнения программы.

Функциональная отладка DVM-программ

Используется следующая методика поэтапной отладки программ: На первом этапе программа отлаживается на рабочей станции как последовательная программа, используя обычные методы и средства отладки На втором этапе программа выполняется на той же рабочей станции в специальном режиме проверки распараллеливающих указаний На третьем этапе программа выполняется на рабочей станции или на параллельной машине в специальном режиме, когда промежуточные результаты параллельного выполнения сравниваются с эталонными результатами (например, результатами последовательного выполнения)

Типы ошибок

Синтаксические ошибки в DVM-указаниях и нарушение статической семантики Неправильная последовательность выполнения DVM-указаний или неправильные параметры указаний Неправильное выполнение вычислений из-за некорректности DVM-указаний и ошибок, не проявляющихся при последовательном выполнении программы Аварийное завершение параллельного выполнения программы (авосты, зацикливания, зависания) из-за ошибок, не проявляющихся при последовательном выполнении программы

Динамический контроль

Чтение неинициализированных переменных Выход за пределы массива Необъявленная зависимость по данным в параллельной конструкции Модификация в параллельной ветви размноженных переменных (не редукционных и не приватных) Необъявленный доступ к нелокальным элементам распределенного массива Чтение теневых граней распределенного массива до завершения операции их обновления Использование редукционных переменных до завершения операции асинхронной редукции

Ограничения метода динамического контроля

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

Способы уменьшения ресурсов времени и памяти

При конвертации посредством специальной опции задается уровень функциональной отладки – целое число от 0 до 4, определяющее события в программе, о которых сообщается отладчику: 0 - нет событий, 1 - модификация распределенных массивов, 2 - модификация и использование распределенных массивов, 3 - модификация всех переменных, 4 - модификация и использование всех переменных.

Сравнение результатов

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

# Trace size = 476385 bytes # String count = 11326 # Used memory =

1087632 bytes PL: 1() [2] {"jac.fdv", 13} = # , (0:1,8,1), (1:1,8,1) # Trace size = 11464 bytes # String count = 322 # Count of traced iterations = 64 # Used memory = 31168 bytes EL: 1 SL: 2() [1] {"jac.fdv", 22} = # # Trace size = 464846 bytes # String count = 11002 # Count of traced iterations = 20 # Used memory = 1056272 bytes PL: 3(2) [2] {"jac.fdv", 26} = # , (0:2,7,1), (1:2,7,1) # Trace size = 238227 bytes # String count = 5800 # Count of traced iterations = 720 # Used memory = 559680 bytes EL: 3 PL: 4(2) [2] {"jac.fdv", 34} = # , (0:2,7,1), (1:2,7,1) # Trace size = 222363 bytes # String count = 5080 # Count of traced iterations = 720 # Used memory = 490560 bytes EL: 4 EL: 2 END_HEADER

# Trace size = 476385 bytes # String count = 11326 # Used memory = 1087632 bytes PL: 1() [2] {"jac.fdv", 13} = # , (0:1,8,1), (1:1,8,1) # Trace size = 11464 bytes # String count = 322 # Count of traced iterations = 64 # Used memory = 31168 bytes EL: 1 SL: 2() [1] {"jac.fdv", 22} = # # Trace size = 464846 bytes # String count = 11002 # Count of traced iterations = 20 # Used memory = 1056272 bytes PL: 3(2) [2] {"jac.fdv", 26} = # , (0:2,7,1), (1:2,7,1) # Trace size = 238227 bytes # String count = 5800 # Count of traced iterations = 720 # Used memory = 559680 bytes EL: 3 PL: 4(2) [2] {"jac.fdv", 34} = # , (0:2,7,1), (1:2,7,1) # Trace size = 222363 bytes # String count = 5080 # Count of traced iterations = 720 # Used memory = 490560 bytes EL: 4 EL: 2 END_HEADER

Диагностика расхождений

Файл трассы BW: [3] "maxeps"; {"jac.fdv", 9} AW: [3] "maxeps" = 0.0000; {"jac.fdv", 9} PL: 1() [2]; {"jac.fdv", 13} IT: 9, (1,1) BW: [3] "a(i,j)"; {"jac.fdv", 15} AW: [3] "a(i,j)" = 0.0000; {"jac.fdv", 15} BW: [3] "b(i,j)"; {"jac.fdv", 17} AW: [3] "b(i,j)" = 0.0000; {"jac.fdv", 17} IT: 10, (1,2) Диагностика *** CMPTRACE *** : TraceRecord(36), Loop( No(1), Iter(1,3) ). File: jac.fdv, Line: 17 Different FLOAT values: 0.7000 != 0.0000. *** Total found errors: 1; Limit: 1000 *** CMPTRACE *** : TraceRecord(36), Loop( No(1), Iter(1,3) ). File: jac.fdv, Line: 17 Different FLOAT values: 0.7000 != 0.0000.

Факторы, определяющие эффективность выполнения параллельных программ

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

Интервалы выполнения программы

При конвертации посредством специальной опции задается, какие участки программы рассматриваются в качестве интервалов выполнения программы. 0 - нет интервалов, 1 - параллельные циклы и охватывающие их последовательные циклы, 2 - последовательности операторов, указанные в программе посредством директив INTERVAL и END INTERVAL, 3 - объединение подмножеств 1 и 2, 4 - все циклы и интервалы, заданные с помощью директив INTERVAL и END INTERVAL.

Интервалы выполнения программы

При запуске программы можно задать: Режим автоматического разбиения интервалов на подинтервалы – от одной коллективной операции до другой Количество уровней в иерархии интервалов, для которых собирать характеристики выполнения Режим выдачи для каждого интервала статистики вызовов функций системы поддержки и времен их работы

Характеристики эффективности 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 0.3831 Execution time 14.1855 Processors 16 Total time 226.9688 Productive time 86.9442 ( CPU= 86.1276 Sys= 0.8165 I/O= 0.0001 ) Lost time 140.0245 Insufficient parallelism 12.2911 ( User= 0.0421 Sys= 12.2490 ) Communication 121.1065 ( Real_sync= 38.7362 Starts= 0.0186 ) Idle time 6.6269 Load imbalance 4.0264 Nop Communic Real_sync I/O 21 0.0000 0.0000 Reduction 20 25.6738 16.9355 Shadow 22 64.4747 21.8809

Проблема – нестабильность характеристик

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

Нестабильность производительности процессоров

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

Предсказатель эффективности

получает характеристики выполнения 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 раз в зависимости от их согласованности с организацией кэш-памяти Поэтому важно предоставить программисту инструмент, помогающий ему обеспечить такую согласованность. Согласованность же с особенностями коммуникационных сетей (группировка или разбиение сообщений, их планирование) должны обеспечивать системы программирования с языков высокого уровня