Введение к работе
Актуальность темы. Постоянное увеличение требований к скорости обработки . информации и вычислений привело к необходимости применения многопроцессорных вычислительных систем (МВС), позволяющих ускорять вычисления за счет одновременного (параллельного) выполнения различных частей одной и той же задачи на разных вычислительных устройствах.
Однако практика использования МВС показывает, что для реальных задач увеличение скорости вычислений, как правило, не бывает пропорциональным увеличению количества процессоров вычислительной системы. Т.е. МВС, содержащая, например, 16 процессоров, обычно не .может выполнять программу в 16 раз быстрее, чем аналогичная однопроцессорная ЭВМ. Одной из фундаментальных причин этого является то, что при выполнении программы на нескольких процессорах требуются дополнительные затраты времени на пересылки данных во время выполнения программы. Поэтому для повышения эффективности параллельных вычислений необходимо сократить время, затрачиваемое на пересылки. Для этого надо решить, по крайней мере, две важные проблемы: обеспечить эффективную, и при этом экономичную, коммутацию и адаптировать программу к структуре МВС (эффективно распараллелить программу). Важной частью проблемы распараллеливания для МВС с параллельной памятью является проблема размещения данных в памяти для бесконфликтного и эффективного доступа к ним в процессе выполнения программы.
Этим проблемам посвящены многочисленные исследования и публикации. Среди работ по коммутации следует отметить работы В.Э. Бенеша, В.И.Неймана, А.В. Каляева, В.И. Кодачигова. Распараллеливанию
4 посвящены работы В.В. Воеводина, Д.Кука, М. Вольфа, К.Кеннеди,.и многие другие Связь между коммутацией и распараллеливанием обычно рассматривается в одном направлении — при разработке методов распараллеливания программ и размещения данных учитывается структура системы коммутации МВС. Некоторыми исследователями (см., например, работы Валяха, А.В. Каляева, В.И. Кодачигова) проводится также анализ систем коммутации с точки зрения их эффективности для параллельных вычислений. Однако большинством исследователей эти проблемы изучаются по отдельности, без учета их взаимной связи и влияния. <. .. Таким.образом, актуальной является задача комплексного изучения проблем коммутации и распараллеливания программ.
Цель и задачи диссертации. Цель работы — комплексное изучение возможностей снижения . затрат времени на межпроцессорные пересылки данных при параллельных вычислениях. Для достижения этой цели необходимо учитывать взаимосвязь между коммутацией и распараллеливанием. Одной фразой эту связь можно охарактеризовать следующим образом: чем универсальнее коммутация, тем проще и эффективнее выполняется распараллеливание программ и размещение данных для такой вычислительной системы. В работе изучены различные варианты соотношения «коммутация-распараллеливание». Основным ограничением для использования универсальных коммутационных систем является их достаточно высокая структурная сложность. Поэтому в диссертации основным критерием при анализе выбрана сложность коммутационной схемы, т.е. количество элементов, из которых построена схема.
Рассмотрим возможные варианты построения коммутационных схем для МВС с параллельной памятью, и их связь с размещением данных. В каждом из рассмотренных случаев выделим возникающие задачи.
Если система коммутации позволяет реализовать любой набор :оединений, то на размещение данных накладывается одно основное граничение — бесконфликтность. Бесконфликтное размещение данных в юдулях памяти является отдельной очень сложной проблемой, и в данной »аботе не рассматривается. Поэтому одной из основных проблем при іазработке полнодоступной системы коммутации является экономичность юммутационной схемы. Полнодоступная разовая коммутационная схема с
Существенно более экономичные схемы можно получить только в лассе неполнодоступных коммутационных схем. Идея состоит в том, что уія многих важных классов алгоритмов требуются регулярные соединения іежду процессорами. Поэтому можно использовать схему, эффективно еализующую лишь ограниченный, но достаточный для вычислений класс оединений (например, решетка, тор или гиперкуб). Однако при азмещении данных для таких схем надо уже обеспечивать не только есконфликтность, но и реализуемость соединений, необходимых для оступа к данным в процессе работы.
В предельном случае соединения между элементами ычислительной системы могут быть жестко фиксированы. В таком случае атраты на коммутацию минимальны, однако размещение данных в
сочетании с преобразованиями программ приобретают первостепенно* значение. Для такой модели МВС важно изучить вопрос о том, как надс размещать данные, чтобы программа могла быть реализована на МВС бе: лишних пересылок.
В диссертации для каждого из этих вариантов построена и изученг математическая модель. Кроме экономичности, важной характеристико? системы коммутации является наличие эффективного алгоритмі построения настройки коммутационной схемы на реализацию требуемогс набора соединений. Такие алгоритмы также разработаны в диссертации.
Помимо чисто теоретического анализа, важной являете* практическая сторона проблемы. Эффективность применения в МВС тої" или иной коммутационной схемы существенно зависит от способности распараллеливающего компилятора разместить данные и преобразовать текст программы оптимальным (для используемой системы коммутации; образом. Поэтому при разработке распараллеливающих компиляторов необходимо применять специальные преобразования, ориентированные на имеющуюся систему коммутации. Такие преобразования также представлены в работе.
Объект исследования — средства уменьшения пересылок данных при параллельных вычислениях. В диссертации изучаются графовые модели коммутаторов и эффективные размещения; , данных для автоматического распараллеливания.
Методы исследований. В работе использованы методы теории графов и теории чисел, а также теории автоматического распараллеливания и преобразования программ. Для программной реализации разработанных алгоритмов преобразований программ был использован язык программирования Arity Prolog для MS DOS. .
7 Научная новизна и практическая ценность работы. В
іиссертации получены новые классы экономичных коммутационных ;хем. Для полученных схем разработаны алгоритмы их настройки на )еализацию заданного соединения. Также проведен анализ множества программ, реализуемых на МВС с фиксированными соединениями, и іредложен ряд преобразований, необходимых для распараллеливания ірограмм для суперкомпьютера со структурной реализацией :ычислений.
Все приведенные в диссертации теоретические результаты юлучены лично автором. Программная реализация преобразований, іредставленньїх в четвертой главе, также выполнена автором как часть аспараллеливаюшего компилятора, разработанного группой сотрудников, спирантов и студентов мехмата РГУ.
Полученные в диссертации теоретические результаты могут быть спользованы при проектировании вычислительных систем, а также при азработке распараллеливающих компиляторов. Представленные в иссертации алгоритмы преобразования программ использованы при азработке (в составе коллектива разработчиков) распараллеливающего омпилятора с языка Фортран для суперпроцессора со структурной еализацией вычислений.
Апробация работы. Основные результаты диссертации
экладывались на Всероссийской научной конференции
Фундаментальные и прикладные, аспекты разработки больших определенных программных комплексов» (Абрау-Дюрсо, 1998 г.), на [еждународной научно-технической конференции «Интеллектуальные ногопроцессорные системы» (ИМС'99) (Таганрог, 1999), а также на гучных семинарах РГУ.
Публикации. Основные результаты диссертации опубликованы в іботах [1—7]. В совместной работе [2] автору диссертации принадлежит
описание алгоритма распределения переменных по страницам памяти и алгоритма разбиения программы на кадры.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, библиографического списка и приложения, имеются 2 таблицы и 29 рисунков. Полный объем диссертации — 143 страницы, библиографический список содержит 96 наименований работ отечественных и зарубежных авторов.
