Преобразование циклических конструкций для многопроцессорных систем кластерного типа с учетом количества вычислительных устройств

Актуальность темы

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

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

Преобразованием наразных уровнях представления алгоритмов занимаются как зарубежные, так и российские специалисты. Среди достижений наших ученых самыми значимыми являются труды Воеводина В. В. и Воеводина Вл.В. [12] по оптимизирующим преобразованиям программного кода для однопроцессорных систем. Кроме того ими разработана система V-Ray [97] для оптимизации выполнения циклических конструкций на многопроцессорных системах. Широко известны статьи и патенты сотрудников ЗАО «Московский Центр SPARC-технологий» (МЦСТ) [68], сотрудничающих с корпорацией Sun MicroSystems в области высокоуровневой оптимизации циклов в перспективных компиляторах. Среди зарубежных ученых выдающиеся работы в области оптимизации программ для многопроцессорных систем опубликовали Lamport L. [94] и Ramamoorthy С. Такие крупнейшие корпорации, как Intel, IBM, Sun MicroSystems, разрабатывают оптимизаторы кода, проводят исследования в области построения многопроцессорных систем и патентуют новые решения в области анализа и оптимизации алгоритмов и программ для различных типов вычислительных систем, в том числе параллельных.

Постоянная нехватка должной аналитической поддержки со стороны языков программирования, компиляторов и операционных системв обеспечении эффективности процессов решения задач привела к созданию специализированных программных комплексов по анализу пользовательских программ и их преобразованию в^ соответствии с требованиями конкретных вычислительных систем. Указанные комплексы (некоторого* рода препроцессоры языков программирования высокого уровня), представляясобой автономные программные системы, оказались удобным инструментом для выполненияразличных работ, когда программы одного вида нужно перевести в эквивалентные программы другого вида [12].

Одним из важнейших преобразований современных компиляторов* является автопараллелизация. Автопараллелизация. — это семейство оптимизирующих преобразований, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управленияНаиболее распространена-автоматическая параллели-зация циклов, в которых нет зависимости данных. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур [68].

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

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

Применение кластерных вычислительных систем связано с рядом проблем. Известно, что на время решения задачи в кластере влияет количество используемых процессоров [16]. При проектировании вычислительного кластера для конкретной прикладной задачи требуется предварительный анализ ресурсной базы и реализации алгоритма: необходимо оценить объем вычислительной работы и определить количество вычислительных устройств, при котором время решения будет наименьшим, что позволит максимально эффективно использовать имеющиеся ресурсы.

Определение оптимального количества вычислительных устройств нетривиально, так как время решения задачи зависит от множества факторов: количества оперативной памяти на узлах кластера, производительности дисков и коммуникационной среды и, наконец, программной реализации алгоритма решения задачи.

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

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

— анализ и исследование существующих преобразований программ для многопроцессорных систем кластерного типа;

— разработка способа преобразования циклических конструкций вычисления рекуррентных последовательностей, так что операторы циклов могут выполняться одновременно и независимо на разных вычислительных устройствах;

— разработка способа преобразования циклических конструкций с использованием индексных множеств для многопроцессорных вычислительных систем;

— определение влияния количества используемых устройств кластерной вычислительной системы на время решения прикладной задачи.

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

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

На защиту выносятся:

— способ преобразования циклических конструкций вычисления рекуррентных последовательностей;

— способ преобразования циклических конструкций с использованием индексных множеств;

— дополненная формула Амдала с учетом обмена сообщениями между узлами многопроцессорной системы кластерного типа;

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

Методологическая основа работы.

В работе использованы графовые модели программ [12]:

— графы передач управления и информационные графы программ;

— графы зависимостей.

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

Научная новизна работы состоит в следующем:

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

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

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

Практическая ценность работы. Разработанные способы преобразования циклических конструкций при интегрировании их в системы оптимизирующей компиляции или специализированные программные комплексы по анализу и преобразованию пользовательских программ в соответствии с требованиями конкретных вычислительных систем позволят сократить время выполнения ряда программ. Разработанные способы не зависят от аппаратных платформ и языков реализации алгоритмов, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

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

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

Степень достоверности и обоснованности результатов.

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

Реализация и внедрение результатов работы.

При проведении исследования было разработано и реализовано программное обеспечение, содержащее алгоритм прикладной задачи преобразования информации, который заключаетсяв решении систем линейных уравнений и реализован с использованием вложенных циклических конструкций. Результаты работы были внедрены в изделия, разработанные в рамках ОКР на ФГУП «Пензенский научно-исследовательский электротехнический институт», о чем свидетельствует акт о внедрении, приведенный в приложении В. ю.

Апробация результатов исследования.

Результаты работы докладывались на:

— VI Международной научно-технической конференции «Новые информационные технологии и системы» («НИТиС-2004»), которая проводится Международной академией информатизации, Академией информатизации образования и Пензенским государственным университетом совместно с ОАО «ВолгаТелеком» (июнь 2004 г.);

— 5-й Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки», которая проводится по инициативе Самарского государственного технического университета и Поволжской молодежной академии наук (сентябрь 2004 г.);

— X Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (НИТ-2005), которая проводится Рязанской государственной радиотехнической академией-(апрель 2005 г.);

— Всероссийской научной конференции студентов, аспирантов и молодых ученых «Наука. Технологии. Инновации» (НТИ-2005), которая проводится Новосибирским государственным техническим университетом (декабрь 2005 г.);

— XI Международной открытой научной конференции «Современные проблемы информатизации в моделировании и программировании» (ноябрь 2005 г. — январь 2006 г.);

— XII Международной открытой научной конференции «Современные проблемы информатизации в проектировании и телекоммуникациях» (ноябрь 2006 г. — январь 2007 г.);

— V всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии», которая проводилась на базе «Кибернетического центра» Томского политехнического университета (февраль — март 2007 г.);

— Седьмой Международной конференции-семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», которая проводится Нижегородским государственным университетом (ноябрь 2007 г.).

Публикации.

По теме диссертации опубликовано 11 печатных работ, в том числе одна статья в издании, рекомендованном ВАК России.

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

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 101 наименования и трех приложений. Работа содержит 131 страницу основного машинописного текста, 55 рисунков, 10 таблиц, 28 страниц приложений.

4.6 Выводы по главе.

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

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

3. Спрогнозировано время выполнения алгоритма задачи решения систем уравнений при разных объемах обрабатываемой информации для вычислительных систем кластерного типа и оценены доля последовательных вычислений и доля операций передачи сообщений по коммуникационной среде, что позволило определить количество вычислительных устройств, при котором время решения задачи наименьшее. Время решения системы линейных уравнений из 1024 уравнений методом Га-усса-Жордана на пятнадцати вычислительных устройствах сокращается более чем в 10 раз относительно времени решения той же задачи на одном вычислительном устройстве.

4. Подтвеждена эффективность применения предложенной методики для стандартных и нестандартных программ, а также для специфических задач.

Заключение

.

В диссертационной работе были получены следующие результаты:

1. Проанализированы существующие преобразования программ, в частности преобразования циклических конструкций, в которых присутствуют зависимости данных, для многопроцессорных систем кластерного типа.

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

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

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

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

6. Получены экспериментальные значения времени решения прикладной задачи, заключавшейся в решении систем уравнений, на вычис1 лительных системах кластерного типа, которые подтвердили сокращение времени решения задач пропорционально количеству вычислительных устройств, задействованных в многопроцессорных комплексах. Определена зависимость времени выполнения задачи, заключающейся в решении систем уравнений, от ее размера при различном количестве используемых процессорных элементов.

7. Получены экспериментальные результаты, подтверждающие существование такого количества процессорных элементов, при котором время решения задачи наименьшее. Для задачи решения систем уравнений спрогнозировано время выполнения алгоритма при разных объемах обрабатываемой информации для вычислительных систем кластерного типа и оценены доля последовательных вычислений и доля операций передачи сообщений по коммуникационной среде, что позволило определить количество вычислительных устройств, при котором время решения задачи наименьшее. Время решения системы линейных уравнений из 1024 уравнений методом Гаусса-Жордана на пятнадцати вычислительных устройствах сокращается более чем в 10 раз относительно времени решения той же задачи на одном вычислительном устройстве.