Содержание к диссертации
Введение
1 Оптимизация и распараллеливание программного кода 13
1.1 Анализ и преобразование алгоритмов решения задач 14
1.2 Оптимизация и оптимизирующие преобразования программ 17
1.3 Оптимизация и параллельная обработка данных 23
1.4 Параллельная оптимизация циклов 30
1.5 Рекуррентные программные циклы 34
1.6 Выводы по главе 37
2 Способы преобразования циклических конструкций 38
2.1 Циклические конструкции 39
2.2 Способ преобразования циклов вычисления рекуррентных последовательностей 40
2.3 Способ преобразования циклов с использованием индексных множеств 56
2.4 Выводы по главе 62
3 Решение задач на кластерных вычислительных системах 63
3.1 Объем информации и количество вычислителей 63
3.2 Методика определения количества вычислительных устройств, необходимых для решения задачи за минимальное время 72
3.3 Оценка эффективности параллельных вычислений для задач обработки информации 77
3.4 Выводы по главе 85
4 Эффективность методики определения количества вычислительных устройств 86
4.1 Использование методики для оценки стандартных пакетов 86
4.2 Использование методики для оценки алгоритмов программ 95
4.3 Применение методики для экспериментальных данных, полученных на разных кластерных установках и для различных задач 101
4.4 Применение методики для разрабатываемых программ 106
4.5 Применение методики в практических задачах 116
4.6 Выводы по главе 119
Заключение 120
Список использованных источников
- Оптимизация и оптимизирующие преобразования программ
- Способ преобразования циклов вычисления рекуррентных последовательностей
- Методика определения количества вычислительных устройств, необходимых для решения задачи за минимальное время
- Использование методики для оценки алгоритмов программ
Введение к работе
Актуальность темы. Сокращение времени решения сложных научно-технических задач является стимулом совершенствования вычислительной техники. Оно достигается! применением оптимизирующих преобразований к выявленным "недоброкачественным" участкам про-граммного кода, начиная с оптимизации на уровне исходного языка, заканчивая машинно-зависимой оптимизации.
Наибольшее внимание при преобразовании алгоритмов программ исследователи уделяют оптимизации циклов, так как основное время исполнения большинства программ приходится именно на циклические конструкции.
Преобразованием на- разных уровнях представления алгоритмов занимаются как зарубежные, так и российские специалисты. Среди достижений наших ученых самыми значимыми являются труды ВоеводинаїВ.В. и Воеводина Вл.В. [12] по оптимизирующим преобразованиям программного кода для однопроцессорных систем. Кроме того ими разработана система V-Ray [97] для оптимизации выполнения циклических конструкций на многопроцессорных системах. Широко известны статьи и патенты сотрудников ЗАО "Московский Центр SPARC-технологий" (МЦСТ) [68], сотрудничающих с корпорацией Sun MicroSystems в области высокоуровневой оптимизации циклов в перспективных компиляторах. Среди зарубежных ученых выдающиеся работы в области оптимизации программ для многопроцессорных систем опубликовали Lamport L. [94] и Ramamoorthy С. Такие крупнейшие корпорации, как Intel, IBM, Sun MicroSystems, разрабатывают оптимизаторы кода, проводят исследования в области построения многопроцессорных систем и патентуют новые решения в области анализа и оптимизации алгоритмов и программ для различных типов вычислительных систем, в том числе параллельных.
Постоянная нехватка должной аналитической поддержки со стороны языков программирования, компиляторов и операционных систем; в обеспечении эффективности процессов решения задач привела к созданию специализированных программных комплексов по анализу пользовательских программ и их преобразованию в^ соответствии с требованиями конкретных вычислительных систем. Указанные комплексы (некоторого- рода препроцессоры языков программирования высокого уровня), представляя^ собой автономные программные системы, оказались удобным инструментом для выполнения; различных работ, когда программы одного вида нужно перевести в эквивалентные программы другого вида [ 12].
Одним из важнейших преобразований современных компиляторов* является автопараллелизация. Автопараллелизация. — это семейство оптимизирующих преобразований, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления; Наиболее распространена, автоматическая параллели-зация циклов, в которых нет зависимости данных. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур [68].
Сложности при распараллеливании возникают с циклами, в которых присутствуют различные зависимости данных. Преобразование циклических конструкций с неявной зависимостью данных, например вычисление рекуррентных последовательностей, существующими средствами либо невозможно, либо малоэффективно даже при использовании специальной аппаратной поддержки.
Применение специализированных вычислительных комплексов позволяет ускорить решение некоторых классов задач за счет аппаратной реализации операций. Однако специализация резко ограничивает область применения таких систем. Напротив, простая в организации архитектура вычислительной системы кластерного типа оказывает влияние
на время решения задач. Накладные расходы, связанные с пересылкой сообщений, могут перекрыть эффект от использования множества вычислительных устройств.
Применение кластерных вычислительных систем связано с рядом проблем. Известно, что на время решения задачи в кластере влияет количество используемых процессоров [16]. При проектировании вычислительного кластера для конкретной прикладной задачи требуется предварительный анализ ресурсной базы и реализации алгоритма: необходимо оценить объем вычислительной работы и определить количество вычислительных устройств, при котором время решения будет наименьшим, что позволит максимально эффективно использовать имеющиеся ресурсы.
Определение оптимального количества вычислительных устройств нетривиально, так как время решения задачи зависит от множества факторов: количества оперативной памяти на узлах кластера, производительности дисков и коммуникационной среды и, наконец, программной реализации алгоритма решения задачи.
Таким образом, актуальными являются исследования, связанные с разработкой способов преобразования циклических конструкций вычисления рекуррентных последовательностей и циклов с использованием индексных множеств для многопроцессорных систем кластерного типа с учетом количества задействованных вычислительных устройств.
Целью диссертационной работы является повышение эффективности использования ресурсов многопроцессорных систем кластерного типа посредством преобразования программного кода, в частности преобразования циклических конструкций, используемых при реализации алгоритмов прикладных задач.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
анализ и исследование существующих преобразований программ для многопроцессорных систем кластерного типа;
разработка способа преобразования циклических конструкций вычисления рекуррентных последовательностей, так что операторы циклов могут выполняться одновременно и независимо на разных вычислительных устройствах;
разработка способа преобразования циклических конструкций с использованием индексных множеств для многопроцессорных вычислительных систем;
определение влияния количества используемых устройств кластерной вычислительной системы на время решения прикладной задачи.
Объект исследования - вычислительные системы кластерного типа и циклические конструкции прикладных программ, представленные на языках программирования высокого уровня. К исследуемым конструкциям относятся циклы вычисления рекуррентных последовательностей и циклы с использованием индексных множеств.
Предмет исследования составляют способы и методики параллели-зации программного кода, в частности циклических конструкций, для вычислительных систем кластерного типа.
На защиту выносятся:
способ преобразования циклических конструкций вычисления рекуррентных последовательностей;
способ преобразования циклических конструкций с использованием индексных множеств;
дополненная формула Амдала с учетом обмена сообщениями между узлами многопроцессорной системы кластерного типа;
методика определения количества вычислительных устройств, необходимых для решения задачи за минимальное время с учетом обмена сообщениями между узлами многопроцессорной системы кластерного типа.
Методологическая основа работы.
В работе использованы графовые модели программ [12]:
графы передач управления и информационные графы программ;
графы зависимостей.
Методологическую и теоретическую базу работы составили научные труды отечественных и зарубежных авторов в области анализа и оптимизации алгоритмов программ, применения параллельных вычислений при решении широкого класса прикладных задач.
Научная новизна работы состоит в следующем:
предложен способ преобразования циклических конструкций вычисления рекуррентных последовательностей, отличающийся от известных способов тем, что исходную зависимость вычисления элементов последовательности заменяют на- совокупность зависимостей так, что циклические конструкции выполняются параллельно как последовательные независимые участки программы в нескольких потоках управления;
предложен способ преобразования циклических конструкций, с использованием индексных множеств, который позволяет трансформировать исходный алгоритм программы в более эффективный с точки зрения времени его выполнения на вычислительной системе с общей памятью и аппаратной синхронизацией вычислений;
предложена методика определения количества вычислительных устройств, необходимых для решения задачи на многопроцессорной системе кластерного типа за наименьшее время с учетом дополнения формулы.Амдала, что позволяет оценить влияние количества вычислительных устройств и коммуникационной среды, на время решения задачи.
Практическая ценность работы. Разработанные способы преобразования циклических конструкций при интегрировании их в системы оптимизирующей компиляции или специализированные программные комплексы по анализу и преобразованию пользовательских программ в
соответствии с требованиями конкретных вычислительных систем позволят сократить время выполнения ряда программ. Разработанные способы не зависят от аппаратных платформ и языков реализации алгоритмов, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.
На основании предложенной методики с точки зрения прикладных-, свойств задачи оценивается количество используемых вычислительных устройств, при которых достигается максимальное сокращение времени-, решения задачи, с целью выдвижения требований к архитектуре кластерной вычислительной системы.
Решение задачи преобразования циклических конструкций вычисления рекуррентных последовательностей и циклов с использованием индексных множеств, а также задачи определения оптимального с точки зрения» времени решения задачи количества вычислительных устройств имеет существенное значение для повышения, эффективности использования ресурсов многопроцессорных систем кластерного типа.
Степень достоверности и обоснованности результатов.
Достоверность и обоснованность теоретических и практических результатов, выводов и рекомендаций подтверждается использованием современных методов исследования, методов обработки и апробацией в лабораторных условиях.
Реализация и внедрение результатов работы.
При проведении исследования было разработано и реализовано программное обеспечение, содержащее алгоритм прикладной задачи преобразования информации, который заключается' в решении систем линейных уравнений и реализован с использованием вложенных циклических конструкций. Результаты работы были внедрены в изделия, разработанные в рамках ОКР на ФГУП "Пензенский научно-исследовательский электротехнический институт", о чем свидетельствует акт о внедрении, приведенный в приложении В.
10'
Апробация результатов исследования.
Результаты работы докладывались на:
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 страниц приложений.
Краткое содержание работы.
Во введении обоснована актуальность темы, сформулированы цель и задачи диссертационной работы, ее научная новизна, практическая значимость полученных результатов и положения, выносимые на защиту, приведены сведения об апробации и практическом внедрении результатов работы.
В первой главе рассмотрено использование параллельных вычислительных систем для решения прикладных задач, выполняющих обработку информации, применяемые методы и технологии анализа и оптимизации их алгоритмов на вычислительных системах кластерного типа с целью уменьшения времени решения задач. Рассмотрены распростра-
ненные оптимизирующие преобразования программ для однопроцессорных и многопроцессорных вычислительных систем.
Вторая глава посвящена описанию разработанных способов преобразования циклических конструкций прикладных программ. Рассматриваемые трансформации исходного кода программ относятся к оптимизирующим преобразованиям программ, а именно к способам реорганизации алгоритмических конструкций повторения, в теле которых имеется зависимость данных. Достоинством предложенных способов является то, что операторы преобразованных циклов могут выполняться одновременно и независимо без синхронизации вычислений на разных вычислительных устройствах.
В третьей главе рассматриваются теоретические аспекты параллельных вычислений на многопроцессорных системах кластерного типа. Дополняется формула Амдала с учетом накладных расходов, связанных с передачей сообщений по коммуникационной среде. Проводится теоретический анализ влияния коммуникационной среды на время решения задач.
В четвертой главе описывается проведение экспериментов, подтверждающих эффективность применения предложенной- методики для различных задач. Описано применение методики для оценки стандартных математических пакетов и нестандартных программ, а также для задачи преобразования информации, которая заключается в решении систем уравнений. Определяется количество процессорных элементов, необходимых для сокращения времени вычисления задач, для ряда вычислительных систем кластерного типа.
В заключении суммируются полученные практические и теоретические результаты. В приложениях приводятся материалы по проведению экспериментов, исходные коды используемых программ и документ, подтверждающий внедрение результатов диссертационной работы.
Оптимизация и оптимизирующие преобразования программ
Под оптимизацией понимают последовательность эквивалентных преобразований исходной программы, уменьшающих ее стоимость. Как набор, так и порядок выполнения этих преобразований зависят от того, что считается стоимостью программы. В качестве такой стоимости могут выступать, например, среднее время работы, объем кода и т.д. За счет оптимизации невозможно добиться существенного улучшения алгоритма программы, можно только говорить об улучшении реализации этого алгоритма. В удачных случаях оптимизация ускоряет программу в несколько раз.
Чтобы понимать, с чем борется оптимизация, необходимо понимание факторов, которые влияют на сложность программы. Проведем анализ критериев, используемых в метриках оценки сложности программ.
Чем больше объем программы (программный код), тем больше вероятность присутствия ошибки, некоторой непроверенной "ветви" алгоритма решения задачи. Кроме того, чем больше программа, тем она сложнее - необходимо понимание работы программы в целом.
Одно и то же действие можно запрограммировать разными способами, причем общее количество операторов и операндов может отличаться. В некоторых случаях, например, деление числа на 8 эквивалентно сдвигу вправо на 3, сложность одинакова (для понимания), но время выполнения операций значительно отличается.
В технической литературе по организации процессоров описано влияние условных переходов на время выполнения программ. Существует вероятность отсутствия нового фрагмента программного кода в кэш-памяти процессора, а дополнительная его загрузка занимает некоторое время. Кроме того, современные архитектуры процессоров используют конвейер команд (для ускорения работы линейных фрагментов программ). Чем длиннее конвейер, тем дольше выгрузка из него старого фрагмента программы.
Таким образом, наличие условных переходов, особенно длинных, увеличивает время выполнения алгоритмов программ. Сокращение количества переходов — раскрутка циклов широко используется в оптимизирующих компиляторах.
Аналогичная ситуация с данными: большое их количество не только усложняет понимание программы, но и требует постоянную догрузку данных, не умещающихся в кэш-данных.
Итак, факторы, влияющие на время выполнения программ: - сложность операций и объем кода; - количество переходов - циклические и условные конструкции; - количество операндов и сложность их использования-вызова в программе.
Существует много различных классификаций оптимизирующих преобразований. В зависимости от уровня представления программы различают следующие виды оптимизации: - оптимизацию на уровне исходного языка (в результате трансформации получается программа, записанная на том же самом языке); - машинно-независимую оптимизацию (преобразованию подвергается программа на уровне машинно-независимого промежуточного представления, общего для группы входных или машинных языков); - машинно-зависимую оптимизацию (на уровне машинного языка).
С точки зрения эффективности наиболее предпочтительной является машинно-зависимая оптимизация, поскольку именно с ее помощью можно учесть особенности конкретной вычислительной среды, однако машинно-зависимый оптимизатор непереносим. С другой стороны, преобразование программы на уровне исходного языка позволяет получить более эффективную программу, допускающую дальнейшее развитие и сопровождение. Наконец, машинно-независимая оптимизация на уровне промежуточного представления является компромиссом между этими двумя крайними случаями.
Наиболее эффективный код, ориентированный на конкретную вычислительную систему, увеличивает риск повторного переписывания программы при переходе на другую архитектуру. Зачастую ранее используемые методы не обеспечивают достижение требуемых критериев, например, погрешности вычислений, и тогда приходится создавать новые алгоритмы, адаптированные к специфике предоставляемых вычислительных ресурсов [38].
При использовании разнообразных архитектур нет никакой гарантии, что в ближайшем будущем не придется перерабатывать существующие вычислительные методы и алгоритмы. Возможный выход из данной ситуации состоит в использовании специализированных средств описания прикладных задач и систем программирования, переводящих описание задачи в высокоэффективную, даже машинно-зависимую, форму для конкретной вычислительной системы [47].
Способ преобразования циклов вычисления рекуррентных последовательностей
Признаками предлагаемого способа, общими с общеизвестным преобразованием (раскруткой цикла, рассмотренным выше) являются: - поиск в теле цикла операторов безусловного перехода, прерывания цикла, ввода-вывода или вызова подпрограмм, влияющих на формирование значений переменных; - прекращение преобразования в случае положительного результата поиска; - дублирование тела цикла с естественным увеличением количества вычислительных операций в теле конструкции повторения; - сокращение количества итераций выполнения циклическое конструкции (за счет изменения операторов в теле цикла); - замена всех вхождений переменных; цикла1 в. дублированном,теле на выражения, вычисляющие требуемые: значения; (учитывая изменения значений переменной;цикла, приведение содержимого циклической конструкции к виду эквивалентному исходному циклу).
Признаками данного способа отличными«от известного преобразования являются:. - поиск операторов; вычисления.; очередного элемента множествам (массива) из значений элементов; этого множества, полученных на предыдущих итерациях выполнения; циклической-конструкции; - прекращение преобразования в случае отрицательного результата поиска; - сокращение количества выполняемых операций за счет подстановки выражений из тела цикла одной итерации в операторы другой; дублированной итерации; - формирование нескольких циклических конструкций с учетом заданного количества вычислительных устройств (приведение к виду эквивалентному исходной циклической конструкции) так, что каждая циклическая конструкций может независимо выполняться на любом из вычислительных устройств; - приведение нескольких циклических конструкций к одной, где счетчик номера итерации вычисляется в зависимости: от номера используемого вычислительного устройства; - размещение до циклической конструкции операторов вычисления значений нескольких первых элементов множества (массива), которые будут использоваться для вычисления значений элементов множества в теле цикла.
Предлагаемый способ преобразования циклических конструкций предполагает некоторые ограничения на операторы, применяемые в теле цикла. Среди ограничений следует отметить необходимость отсутствия в теле цикла операторов: - ввода-вывода; - безусловных переходов или прерываний цикла, то есть передачи управления на выражение или оператор, находящийся за телом цикла; - вызова подпрограмм (функций), которые могут изменить значения используемых или порождаемых переменных.
Для описания предлагаемого способа преобразования циклических конструкций необходимо ввести и пояснить ряд обозначений.
Способ преобразования циклических конструкций вычисления рекуррентных последовательностей предполагает возможность изменения алгоритма вычисления элементов некоторого множества в теле цикла. Вычисление очередного элемента множества выражается зависимостью, общей вид которой следующий: Si+i Si+k[,Si+j[,[...,Si+i]..]] , где / к j ... 1, то есть (I — к) I; (к — j) 1; и так далее. Таким образом, элемент множества зависит (знак " ") от некоторой совокупности предыдущих элементов этого множества (или одного элемента). Выражение в квадратных скобках может в зависимости отсутствовать.
В работе Вальковского [25] рассматривается частный случай предлагаемого преобразования - рассмотрен цикл с зависимостью элемента только от одного предыдущего элемента. В работе [25] предлагается "разнесение" информационных связей путем "концентрации" вычислений для цикла:
Методика определения количества вычислительных устройств, необходимых для решения задачи за минимальное время
Для эффективного решения задачи ограниченного объема на вычис лительной системе кластерного типа, как было отмечено, существует та ! кое количество процессоров, при котором время выполнения алгоритма задачи будет наименьшим. Определение этого количества вычислительных устройств является нетривиальной задачей, так как время решения задачи зависит от множества факторов: количества оперативной памяти і t і на узлах кластера, производительности коммуникационной среды и, наконец, программной реализации алгоритма решения задачи.
Предлагается методика [44, 52, 54], в которой по результатам анализа реализации аппаратно-программного обеспечения и алгоритма решения задачи составляется зависимость времени выполнения задачи от величин, характеризующих решение задачи на многопроцессорной кластерной системе. Этими величинами считаются время выполнения последовательных участков алгоритма, время выполнения параллельных вычислений и время, необходимое для обмена сообщениями по коммуникаци-онной среде с учетом ее особенностей.
Исходными данными для расчета количества вычислительных устройств являются результаты проведенных экспериментов. Поскольку неизвестных величин — три, то необходимо провести, как минимум, три эксперимента при разном количестве процессоров.
Рассмотрим методику на примере задачи решения системы линейных уравнений с использованием вычислительного кластера. Пусть система уравнений решается методом Гаусса-Жордана и каждый вычислитель производит расчеты со своей частью (несколько строк) коэффициентов системы уравнений. После анализа алгоритма решения задачи, предполагающего передачу строк коэффициентов с ключевыми элементами (сообщений) от каждого вычислительного устройства к каждому, выявлена зависимость времени решения задачи Тт, которая упрощенно описывается так: Tm=Tc+-?- + (m-l)-m2s+ami (3.6) т где Т$ - время, затрачиваемое на передачу сообщений, не зависящее от m, что согласуется с формулой (3.5).
Сколь малой ни была бы величина 7Л? при использовании значительного количества устройств, на время решения задачи начнет влиять составляющая передачи сообщений (это неизбежно для систем кластерно го типа). Использование формулы (3.6) позволяет достаточно просто оценить время выполнения операций и долю последовательных операций в алгоритме прикладной задачи. При выполнении расчетов с использованием экспериментальных данных рассчитывается зависимость времени решения задач от компонент Тс,Тр,Т$, описанных в формуле (3.6).
Для решения данной задачи оптимальным количеством, вычислительных устройств будет такое к, при котором: 7 Т _\ и Тд. Т +\, что соответствует точке минимума на графике функции Tm, представленном на рисунке 3.4.
Методика определения количества вычислительных устройств кластерной системы, при котором время решения задач будет наименьшим, опирается на методы обработки эмпирических данных и позволяет последовательным приближением определить к по результатам проведен-ных экспериментов.
Как было отмечено, необходимо проведение нескольких экспериментов с разным количеством процессоров. Например, были проведены эксперименты на вычислительной системе с использованием одного, двух и трех процессоров (три - минимально необходимое количество конфигураций). На каждой конфигурации было проведено несколько экспериментов и получены следующие усредненные значения времени решения задачи, в миллисекундах:
Все описанные действия повторяются до тех пор, пока \kz - kz_i\ 1.
Для примера получено оптимальное количество процессоров, равное 5, что действительно подтверждено экспериментом-в главе 4. Следуя данной методике, точка минимума, определяющая оптимальное количество - процессоров, быстро находится, что доказывают полученные экспериментальные значения. Доля последовательных вычислений будет рассчитана по формуле: Полученное значение будет приблизительным.
Анализ различных экспериментальных данных выявил зависимость времени, выполнения задачи от количества используемых вычислительных устройств: увеличение количества процессорных элементов .приводит к сокращению времени решения задачи однако, приї значительном количестве вычислителей эффект от параллельных вычислений, становится отрицательным. Все это подтверждает правильность рассуждений о характере зависимости и ее представлении.
В практическом смысле важным- является экспериментальное подтверждение того, что существует оптимальное с точки зрения времени-решения задачи количество вычислительных устройств кластерной сисг темы. Полученное заключение относится к многопроцессорным системам кластерного типа, поскольку в них для полного решения задачи необходимо собирать фрагменты результирующих данных с вычислительных устройств.
Использование методики для оценки алгоритмов программ
Для подтверждения эффективности применения предложенной методики было разработано программное обеспечение, реализующее алгоритмы, (с использованием вложенных циклических конструкций) формирования и решения систем уравнений (СУ) с заполненной матрицей методом Гаусса-Жордана, а также все вспомогательные функции для обеспеченилэтих процессов на языке программирования Си с использованием библиотеки МРІ. Для удобства компиляции и переноса программного обеспечения на разные операционные системы (ПО работоспособно в Windows и Linux) исходный код находится в одном файле.
Программное обеспечение состоит из следующих фрагментов: - инициализация вспомогательных таблиц и переменных (в том числе циклическими конструкциями с рекуррентными зависимостями); - формирование (генерация) систем уравнений случайным образом, реализованное циклами с однократным вложением; - решение систем уравнений, реализованное циклическими конструкциями с двукратным вложением; - анализ времени выполнения соответствующих фрагментов. Размер системы уравнений и необходимых буферов рассчитывается автоматически1 от количества неизвестных системы. Все переменные и структуры данных выделяются в динамической памяти.
Программа реализована так, что решение прикладной задачи осуществляется на количестве процессоров, которое задается из командной строки при постановке задачи на исполнение.
Масштабируемость программного обеспечения была оценена на че-тырехпроцессорномь кластере Регионального Центра Суперкомпьютерных Вычислений ПГУ и сетевом многомашинном комплексе компьютерной лаборатории Института Информатики и Вычислительной Техники ПГУ, состоящем из восьми персональных компьютеров с процессо рами Intel Pentium Celeron (с тактовой частотой 1 ГГц) и коммуникационной средой Ethernet 100 Мбит/с на витой паре.
Экспериментальные значения времени решения систем из 512 и 1024 уравнений на кластере РЦСВ ПТУ представлены в таблице 4.7.
По графикам зависимостей можно определить размеры систем уравнений, при которых ощутим эффект от использования множества вычислительных устройств.
На основе полученных результатов решения систем уравнений в соответствии с предложенной методикой были рассчитаны кубические зависимости времени от количества неизвестных в системах по формуле (3.8) для разного количества вычислительных устройств средствами пакета Microsoft Excel: - для одного процессора: ti(x)=0.0002x3+0.0228x2-l.5654х+86.329; - для двух процессоров: t2(x)=0.0001x3+0.005x2 +0.544 Гх+207.35; - для трех процессоров: t3(x)=0.00008x3+0.0003x2+1.5865x+l 79.94; - для четырех процессоров: t4(x)=0.00007x3-0.015x2+7.3815x-104.4, где х - количество уравнений (неизвестных) в системах линейных уравнений.
Рассчитанные значения показывают, что зависимость времени решения систем уравнений при малом количестве неизвестных превращается в линейную функцию, что соответствует теоретическим прогнозам (восьмикратное увеличение времени при двукратном увеличении количества- неизвестных).
При увеличении количества неизвестных в системе на время решения систем уравнений начинают влиять факторы, напрямую не относящиеся к алгоритму задачи (например, влияние операционной системы). Кубическая аппроксимация позволяет сгладить влияние этих факторов.
Полученные зависимости позволяют спрогнозировать время решения задачи для систем из 2048 и 4096 уравнений на используемом кластере. Прогнозируемые значения представлены на рисунке 4.24.
Зависимости времени решения систем уравнений от количества неизвестных На основе полученных значений времени решения систем уравнений по предложенной методике были рассчитаны кубические зависимости времени от количества неизвестных по формуле (3.8) для разного количества вычислительных устройств средствами пакета Microsoft Excel: - для одного процессора: ti(x)=0.000155x3-0.12087x2+66.34x-10255; - для двух процессоров: t2(x)=0.00009 х3-0.0631 х2 +26.169 х-2312.1; - для трех процессоров: t3(x)=0.00005 х3-0.0238х2+8.8697 х-763.4; - для четырех npo4eccopoB:t4(x)=0.00004 х3-0.0167х2+5.7034х-395.98; - для пяти процессоров: t5(x)=0.00003 х3-0.02 х2+8.4264 х-921.62, где х — количество уравнений (неизвестных) в системах линейных уравнений.
Полученные зависимости позволяют спрогнозировать время решения задачи для систем из 4096 и 8192 уравнений на используемом кластере.
