Введение к работе
Актуальность темы. Стремительное развитие суперкомпьютеров и параллельных вычислительных систем позволило совершить радикальный прорыв в численном решении крупнейших прикладных проблем в таких областях как нефте- и газодобыча, автомобилестроение, сейсморазведка, прогноз погоды, моделирование биологических процессов, новых химических соединений и т.д. Реальность сегодняшнего дня такова, что с появлением массивно-параллельных компьютеров исчезли многие принципиальные проблемы на пути существенного увеличения пиковой производительности вычислительной техники. Уже сейчас готовится техническая база для создания сверхмощных вычислительных систем и разрабатываются проекты решения сверхсложных прикладных проблем. Именно поэтому США приняли общенациональную программу " Высокопроизг водительные вычисления и коммуникации" (ffigh Performance Computing and Communications). Аналогичная программа находится на рассмотрении Европейского Сообщества, активно стимулирующего применение параллельных компьютеров для решения сложных и важных задач. Соответствующая деятельность идет и в нашей стране.
Однако стремительное развитие вычислительной техники сопровождается не менее стремительным ростом трудностей ее использования. Недостаточное внимание к их преодолению приводит к снижению реальной производительности по сравнению с пиковой в десятки, сотни, а иногда и тысячи раз. Доступными для пользователей средствами повышения реальной производительности на конкретных задачах является лишь разработка новых методов решения задач и реструктурирование реализующих их программ. Поэтому для параллельных компьютеров проблема создания эффективного программного обеспечения становится актуальной. Председатель комитета по параллельным вычислениям, средствам связи и информационным технологиям при президенте США Кен Кеннеди (Ken Kennedy) в одном из своих интервью признал: "Мы подошли к осознанию того, что основная проблема параллельных вычислений— это, прежде всего, проблема создания эффективного программного обеспечения". Резюме третьего семинара по параллельным вычислениям в корпорации Fujitsu (г.Кавасаки,
Япония) сформулировано следующим образом: "Несмотря на то, что заголовки газет пестрят объявлениями о новых возможностях аппаратуры, именно разработка эффективного программного обеспечения и реальных приложений, в конечном счете, и определяют успех новых параллельных компьютеров".
Если фиксирован метод решения конкретной прикладной проблемы, то единственным средством достижения максимально возможной скорости его реализации на любом конкретном параллельном компьютере остается реструктуризация программы, описывающей данный метод. Целью реструктуризации является выбор такого порядка вычислений, который сохранял бы эквивалентность получаемых результатов, но был бы при этом наиболее согласован с требованиями архитектуры компьютера. Частично такую реструктуризацию осуществляет компилятор. В силу ограниченности используемых компилятором методов она редко бывает удовлетворительной. Поэтому основная работа по модернизации программы под требования целевого компьютера традиционно возлагается на пользователя.
Для облегчения выполнения этой работы уже давно создаются автономные программные системы (Rn, Parafrase, PIPS, FORGE, препроцессоры КАР, VAST и другие). Как правило, они реализуются на инструментальных ЭВМ и могут функционировать независимо от целевого компьютера. Несмотря на значительное число подобных систем, проблема поиска модификации программы, обеспечивающей достаточно высокую реальную производительность компьютера на конкретной программе, все еще остается далекой от решения. В конечном счете, ее решение определяется тем, насколько точно позволяют устанавливать информационные связи между отдельными операциями методы анализа структуры программ, включаемые в автономные системы.
Все разработанные до настоящего времени системы в качестве методов такого анализа используют тесты или критерии, определяющие достаточные условия информационной независимости множества операций (GCD тест, неравенство Банерджи, Л-тест, Delta-тест, метод Шостака, метод Фурье-Моцкина и т.п.). В создание подобных тестов вовлечено большое число специалистов (M.Wolfe, D.Kuck, K.Kennedy, R.Allen, J.Hennessy,
M.Lam, W.Pugh, U.Banerjee и другие) и эта деятельность продолжает развиваться. Однако использование достаточных критериев в системах анализа и преобразования программ имеет целый спектр серьезных недостатков. Все критерии с широкой областью применения очень грубы. Более или менее точные критерии всегда имеют очень узкую область применения. Для анализа многих достаточно простых ситуаций критерии просто отсутствуют. В этих условиях существующие системы анализа и преобразования программ не дают и принципиально не могут дать гарантий того, что ненахождение того или иного свойства или преобразования программы действительно означает их несуществование. Попав в подобную ситуацию, пользователь системы не получает никакой информации о том, что делать дальше: разрабатывать новый метод решения задачи, попытаться каким-то образом искать узкие места программы или воспользоваться другой системой для анализа структуры программы.
Таким образом, несмотря на наличие большого числа автономных программных систем для анализа структуры программ и их преобразования под требования архитектуры целевого параллельного компьютера разработка новых подходов к их созданию, свободных от недостатков, присущих использованию достаточных критериев, является актуальной задачей.
Целью диссертационной работы является создание принципиально новой методологии выявления по тексту программ многоступенчатой иерархической структуры больших программных комплексов, построенной на новых методах обнаружения информационных связей как на уровне отдельных операций, так и на уровне программ и их отдельных фрагментов, а также разработка на основе этой методологии общих принципов построения инструментальных систем для изучения и визуализации тонкой структуры программ.
Научная новизна. Представленные в диссертации результаты являются оригинальным вкладом в теорию анализа структуры программ, в теорию и практику создания инструментальных программных систем для исследования и преобразования структуры программ под требования архитектуры параллельных компьютеров с целью достижения максимальной реальной производительности.
Впервые в основу создания таких систем положена история реализации программ (исследования в данной области начаты А.П.Ершовым). Используя возможность компактного описания связей между операциями алгоритмов, разработаны и реализованы методы компактного параметрического описания историй. Все описания задаются для широкого класса программ кусочно-линейными функциями, зависящими от внешних переменных программы. Реализованы алгоритмы вычисления по тексту программ коэффициентов кусочно-линейных функций и областей их задания в пространстве итераций.
Возможность априорного (статического) построения для широкого класса программ историй их реализации, причем возможность построения в удобной аналитической форме, позволила решить две ключевые проблемы. Во-первых, на основе анализа историй построены новые критерии, в том числе, неулучшаемые, для установления самых различных фактов, связанных с параллелизмом вычислений, выполнением эквивалентных преобразований программ, выявлением различных нетрадиционных свойств программ, таких как избыточность вычислений, точное описание множества входных/выходных данных и т.п. Во-вторых, использование неулуч-шаемых или слабо улучшаемых критериев дало возможность разработать принципиально новую методологию выявления по тексту программ многоступенчатой иерархической структуры больших программных комплексов.
Разработка новой методологии исследования программ позволила предложить новые принципы построения инструментальных систем для изучения и визуализации тонкой структуры программ. Одна из таких систем, получившая название V-Ray System, работает на платформах Microsoft Windows и X Window. Эта система апробирована на большом числе реальных программ. Программы, на основе полученных сведений об их структуре, модифицировались под требования архитектуры различных современных параллельных компьютеров и супер-ЭВМ (CRAY EL, CRAY Y-MP C90, IBM SP2, CRAY T3D и других). Дополнительное ускорение, получаемое только за счет использования данной информации, достигало на разных программах 2-10 раз и более. Отметим, что вся модификация программ осуществлялась только на уровне языка высокого уровня без
использования ассемблерных вставок и обращений к высокоэффективным библиотечным программам.
Практическая значимость. Описанные в диссертации новая методология выявления многоступенчатой иерархической структуры больших программных комплексов и новые принципы построения инструментальных систем для изучения и визуализации тонкой структуры программ могут быть применены для достижения различных практических целей. Многоцелевое применение объясняется их независимостью от архитектуры целевого компьютера.
Основное применение связано с созданием автономных систем для изучения информационной структуры программ, в особенности тонкой структуры на уровне связей между отдельными операциями. Такие системы могут быть использованы для обнаружения узких мест программ по параллелизму вычислений, использованию памяти, точности вычислений, их избыточности и т.п. Знание узких мест программ дает возможность их устранить и построить новые, более эффективные параллельные методы. Привлечение сведений об архитектуре конкретных параллельных компьютеров позволяет автоматизировать процесс преобразования программ под требования этих компьютеров.
Предложенные в диссертации критерии параллелизма и других характеристик информационной структуры программ значительно эффективнее аналогичных критериев, используемых в современных компиляторах для параллельных компьютеров. Поэтому отдельные компоненты новой тех-' пологий анализа и преобразования программ можно включить во вновь разрабатываемые или модифицируемые оптимизирующие компиляторы.
Одной из серьезных существующих проблем является создание порта-бельного численного программного обеспечения для параллельных компьютеров и супер-ЭВМ. Возможность исследования информационной структуры программ до их реализации открывает перспективы решения задачи портабельности, по крайней мере, для конкретных классов компьютеров, например, для SMP компьютеров, имеющих несколько скалярных п/или векторных процессоров, работающих над общей памятью, массивно-параллельных компьютеров, кластеров и сетей рабочих станций.
Возможность детального изучения структуры программ оказывается полезной при выборе архитектуры параллельного компьютера, наиболее подходящей для решения класса задач. Результаты данной работы открывают хорошие перспективы для создания эффективных технологий проектирования программного обеспечения, являются основой для разработки нового поколения методов согласованного анализа структуры программ и особенностей архитектуры компьютеров, открывают возможность для исследований в области экстраполяции свойств программ на основе анализа их структуры при малых значениях внешних переменных, в получении аналитических оценок для "параллельных" характеристик программ и других областях.
Методика исследований. В работе используются результаты изучения историй реализации программ и структуры алгоритмов, общие принципы построения конвертеров и компиляторов, методы визуализации сложных объектов и графовых структур. Критерием достоверности методики исследований является создание на ее основе действующей системы анализа структуры программ и ее широкое апробирование на конкретных задачах и для конкретных параллельных компьютеров.
Апробация работы. Основные положения работы обсуждались на научно-исследовательских семинарах кафедры АСВК факультета ВМиК МГУ, НИВЦ МГУ, ИВМ РАН, на объединенном научно-исследовательском семинаре кафедр автоматизации систем вычислительных комплексов, алгоритмических языков и системного программирования факультета ВМиК МГУ, на российско-французском семинаре "Теоретическое и численное исследование атмосферной и океанической циркуляции" (Москва, 1996), на совместном семинаре Государственного комитета по науке и технологиям Российской Федерации и IBM (USA).
Результаты диссертации докладывались на П-й Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники (Ереван, 1987), на международной конференции "High Performance Computing in the Geosciences" (Франция, 1993), на 1-ой и 2-ой международных конференциях "Программное обеспечение для многопроцессорных систем: теория, практика, опыт" (Москва, 1993,1994), на международном симпози-
уме "High Performance Computing" (Phoenix, Arizona, USA, 1995), на Ломоносовских чтениях в МГУ (1995, 1996), на семинарах в компаниях Thinking Machines (USA), CRAY Research Inc. (USA), Intel Corp. (USA), опубликованы в трудах международного семинара "Workshop on Numerical Analysis and Applications" (Russe, Bulgary, 1996) и 22-й международной конференции "Euromicro Conference" (Prague, 1996).
Публикации. По теме диссертации опубликовано 27 работ, в том числе одна монография.
Структура и объем диссертации. Диссертация состоит из введения, четырех частей, заключения и списка литературы (175 наименований); изложена на 207 страницах, включает 33 рисунка и 14 таблиц.
