Документ взят из кэша поисковой машины. Адрес оригинального документа : http://asa.guru.ru/papers/pap8.doc Дата изменения: Mon Nov 6 19:22:20 2000 Дата индексирования: Mon Oct 1 19:57:37 2012 Кодировка: koi8-r

Комплексный подход к анализу эффективности программ
для параллельных вычислительных систем

Андреев А.Н., Антонов А.С., Воеводин В.В., Воеводин Вл.В., Жуматий С.А.
НИВЦ МГУ им.М.В.Ломоносова, ИВМ РАН



За последние годы нам приходилось работать в рамках многих проектов на
большом числе параллельных компьютеров и супер-ЭВМ и практически всегда
перед нами стояла основная задача - помощь в создании действительно
эффективных параллельных программ. Ясно, что помощь была нужна только
тогда, когда были какие-то проблемы - нет проблем, значит нет и вопросов.
Но интересно то, что сама проблема каждый раз формулировалась
пользователями практически одинаково: "Что-то не так с эффективностью моей
программы".

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

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

АНАЛИЗ КОНФИГУРАЦИИ КОМПЬЮТЕРА
(
АНАЛИЗ ЭФФЕКТИВНОСТИ СИСТЕМНОГО И ПРИКЛАДНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
(
АНАЛИЗ СТРУКТУРЫ ПРОГРАММЫ
(
АНАЛИЗ АЛГОРИТМИЧЕСКОГО ПОДХОДА

Начинать исследование, чаще всего, приходилось с анализа конфигурации
конкретного компьютера: тип и число процессоров, уровни и объем памяти,
параметры и топология коммуникационной среды, особенности ввода/вывода и
т.п. - даже эти, казалось бы простые и очевидные вещи, на практике могут
оказаться причиной вопросов пользователей. В свое время мы разрабатывали
программу для векторно-конвейерного компьютера CRAY Y-MP C90. Когда
программа была закончена и передана пользователю, он после нескольких
запусков на своем компьютере стал утверждать, что "с программой что-то не
так", так как время ее работы было где-то на 30% больше заявленного нами.
Детальный анализ показал, что истинная причина крылась вовсе не в
программе: процессор второго компьютера, в отличие от первого, имел лишь
два канала связи с памятью, а не три, как предписано стандартной
конфигурацией. С программой было "все так" и в рамках той конфигурации она
работала идеально.

Следующий большой срез - это анализ эффективности системного и
прикладного программного обеспечения. Наверняка у всех когда-либо были
нарекания на работу штатных компиляторов, потому проблемы этого пункта
хорошо знакомы всем. Однако далеко не всегда удается столь легко найти
виновника бед пользователей и тогда приходится проводить детальный анализ
характеристик программного окружения. В свое время, в частности, анализ
причин низкой эффективности некоторых MPI-программ, работающих на
параллельном компьютере RM600 (ИПХФ РАН, г.Черноголовка), привел к
неожиданному результату: в операционной системе Reliant Unix, установленной
на компьютере, отсутствовала поддержка работы с семафорами, потому об
эффективности обмена между параллельно работающими процессами говорить
особо не приходилось. Другой пример - это обнаруженная крайне низкая
эффективность ряда процедур в реализации PVM, включенной в состав штатного
программного обеспечения компьютера CRAY T3D. Проблема с программой
пользователя? Да нет, опять-таки дело далеко не в самой программе...

Для облегчения исследования эффективности программного окружения
конкретного компьютера нами была написана система тестов, ориентированная,
в основном, на исследование систем с передачей сообщений типа MPI или PVM.
Данные тесты позволяют определить реальную скорость передачи сообщений,
величину латентности, скорость срабатывания различных функций систем с
передачей сообщений, время задержки на барьерах, эффективность обменов
параллельных процессов в различных логических топологиях и многое другое.
Текущая версия системы тестов может быть найдена по адресу
http://parallel.ru/testmpi.

Основная задача в рамках анализа структуры программы состоит в поиске
ответа на вопрос: можно ли не изменяя алгоритма улучшить эффективность
программы? Занимаясь исследованиями в данном направлении в течении более
десяти лет, мы разработали и используем на практике комбинацию методов
статического и динамического анализа. На основе проведенных исследований
создана и успешно апробирована многоцелевая система - V-Ray,
предназначенная для изучения структуры больших программных комплексов и
адаптации этих комплексов к требованиям целевых компьютеров с параллельной
архитектурой. Система прошла успешную апробацию во время большого числа
экспериментов на современных суперкомпьютерах CRAY Y-MP C90, IBM SP2, CRAY
T3D, HP Exemplar, вычислительном кластере МГУ и других, а также во время
участия в целом ряде проектов по разработке высокоэффективного численного
программного обеспечения для супер-ЭВМ. Описание системы и другие материалы
можно найти в сети Интернет по адресу http://parallel.ru/V-Ray.

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

Понимая явную необходимость в создании основ инфраструктуры,
покрывающей широкий спектр вопросов из области параллельных вычислений и
помогающей осваивать данную область, мы организовали Информационно-
аналитический центр в сети Интернет, посвященный как раз этой теме:
http://parallel.ru . Уже сейчас здесь собрано очень много информации по
архитектурам современных параллельных компьютеров и супер-ЭВМ, технологиям
параллельного программирования, современным исследованиям в данной области,
истории развития параллельных вычислений, персоналиям. Организована
еженедельная рассылка новостей мира параллельных вычислений, поддерживается
дискуссионный Web-клуб и многое другое.

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

Работа выполнена при поддержке РФФИ, гранты N99-07-90414, 99-07-90230,
99-15-90001.