В настоящее время понятия «Многопроцессорные вычислительные системы» и «Многомашинные вычислительные системы» (МВС)[1] широко применяются при рассмотрении вопросов, связанных с параллельными вычислениями. В развитии вычислительной техники многое определяется стремлением повысить производительность существующих систем[1]. Мощность первых компьютеров была очень мала, поэтому решение многих прикладных задач (ПЗ) на них было невозможным или уходило немыслимое количество времени, для их решения. Сразу после появления первых компьютеров, стали придумывать различные методы для объединения нескольких компьютеров в одну единую систему, чтобы повысить производительность и минимизировать время решения задачи. Идея была проста — если мощности одного компьютера не хватает для решения ПЗ, то надо разделить задачу на две или более части и решать каждую часть на своем компьютере. Это и предопределило появление МВС, основным представителем которых являются кластерные вычислительные системы (КВС). КВС — это совокупность вычислительных узлов (ВУ), объединенных в рамках некоторой коммуникационной среды и нацеленных для решения одной сложной или множества независимых задач[1]. В качестве ВУ для кластеров некоторое время назад использовались доступные на рынке однопроцессорные компьютеры, в настоящее время используются 2-х или 4-х процессорные платформы, которые имеют различные архитектурные решения. В последнее время КВС становятся общедоступными аппаратными платформами для высокопроизводительных вычислений, обладающими неплохим соотношением стоимости и производительности.
Тем не менее, эффективное применение КВС на практике оказалось не такой простой задачей. Выяснилось, что реализации «больших задач"[1] на КВС сопутствует множество проблем, связанных со спецификой программирования, использованием вычислительных ресурсов системы, представлением результатов в нужной форме и т. д. Основной проблемой, с которой столкнулись абсолютно все пользователи таких систем, стало то, как добиться эффективного решения задач на КВС.
Для того чтобы выполнить прикладную задачу на КВС, пользователь, как правило, должен разработать параллельную программу (ПП), в том числе с учетом зернистости параллелизма в программе, при этом учитывать такие характеристики КВС, как количество узлов, процессоров, ядер (вычислителей), и статически назначить фрагменты ПП на вычислители КВС так, чтобы достичь желаемого эффекта[2]. При этом пользователь ожидает ускорение её решения пропорционально числу задействованных вычислителей. Однако чаще всего эти ожидания оказываются не оправданными, особенно это относится к кластерным вычислительным системам. Одной из причин такого положения является то, что КВС относятся к уникальным системам обработки данных как по организации памяти, сопряжению аппаратных средств и коммуникационного оборудования, так и настройки программного обеспечения и, следовательно, со своими особенностями реализации параллельных вычислений, которые чаще всего не учитываются пользователями при подготовке прикладной задачи к выполнению.
В работе приводится подход, основанный на предварительном исследовании конкретных КВС (кластер МЭИ (ТУ) и кластер Ханойского Технологического Университета (ХТУ)) с целью получения значений их характеристик, которые дополнительно необходимо учитывать при решении задачи назначения фрагментов программы на вычислители КВС так, чтобы минимизировать время её выполнения.
Таким образом, решаемая задача в диссертации — исследование влияния характеристик современных КВС и варианта назначения фрагментов параллельной программы (Ф1111) на вычислители КВС на время выполнения ПП с последующим учетом этого влияния при минимизации времени решения и, следовательно, повышении эффективности применения КВС. Само время выполнения задач в сильной степени определяется механизмом назначения 8 фрагментов программы на вычислители KB С. Под назначением понимается процесс распределения ФПП (сегмент задачи) по вычислителям КВС, определяющее на каком вычислителе будет выполняться тот или иной фрагмент ПП. Обычно при выполнении 1111 на КВС выделяется определенное количество свободных ресурсов (вычислителей, емкость памяти и т. д.) на момент запроса обработки, поэтому вычислители могут находиться в разных местах КВС (в одном или разных процессорах, в одном или разных ВУ), связанных коммутационными сетями разных уровней и иметь различную свободную емкость памяти. Поэтому время передачи данных между вычислителями, а так же время обращения к памяти в зависимости от свободной емкости памяти на разных уровнях могут различаться, из-за этого время выполнения ПП на одном и том же количестве вычислителей может различаться в зависимости от того, какие именно вычислители используются. Поэтому при неудачном назначении, время выполнения задачи намного возрастает за счет появления накладных расходов. Под накладными расходами в работе понимаются те временные затраты, которые определяются факторами замедляющими время выполнения задачи. Следовательно, это непроизводительное время, связанное с обменом блоками данных между оперативной и дисковой памятью, время на разрешение конфликтов, которые возникают при учете приоритетов на обращения к памяти, передачи данных между КС с более низкой пропускной способности, латентность коммутационной сети (КС) при загруженном состоянии.
Актуальность работы. Существующие методы [3,4] решения задачи назначения ФПП на вычислители КВС комплексно не учитывают вышеперечисленные факторы. В ряде работ предлагаются эвристические алгоритмы, учитывающие только номинальную производительность вычислителей, а иногда и время передачи данных по коммутационным сетям разных уровней. В настоящей работе предлагается в качестве дополнительных характеристик в процессе статического назначения ФПП учитывать приведенные выше факторы, представленные коэффициентами накладных расходов, что позволит повысить эффективность выполнения параллельных программ (ПП) на КВС. Поэтому разработка методики назначения ФПП на вычислители КВС, обеспечивающей учет таких важных характеристик конкретных КВС, как состояние памяти вычислительного узла в момент обработки задачи и неоднородность коммуникационной среды, выраженных в виде коэффициентов накладных расходов, является актуальной задачей.
Цель работы и задачи исследования.
Цель диссертационной работы заключается в исследовании КВС для получения численных значений коэффициентов накладных расходов, разработка математической модели и методики статического назначения ФПП, учитывающих как характеристики задач, КВС, так и значения данных коэффициентов. Основная задача исследования — определить степень влияния характеристик конкретной КВС и механизмов организации параллельных вычислений на время решения прикладных задач заданного класса.
В качестве критериев эффективности обычно рассматривают время выполнения параллельной программы, степень полноты использования ресурсов ВС, отображенной в виде коэффициентов ускорения и их загрузке и др. На эти критерии существенное влияние оказывают различные факторы, среди которых наиболее значимыми являются:
— архитектура ВС;
— вид организации памяти ВС;
— тип коммутационной сети;
— способ организации параллельных вычислений;
— качество параллельной программы, которое существенно зависит от языка программирования, метода решения и распараллеливания задачи, степени распараллеливания (зернистости).
Объектом исследования в работе являются кластерные вычислительные системы на примере кластеров МЭИ и Ханойского Технологического Университета (ХТУ), предметом исследования — особенности организации памяти и КС КВС, учет которых позволит сократить время выполнения параллельных программ на КВС за счет эффективного назначения ФПП на выделенные вычислительные ресурсы.
Научная новизна результатов, полученных в диссертации.
1. Определенны особенности иерархически-неоднородной организации памяти и коммуникационной среды КВС, а также виды накладных расходов, возникающих на разных уровнях иерархии, влияющих на время выполнения параллельных программ.
2. Разработана математическая модель задачи оптимизации обобщенного вида, выраженная в аналитической форме, которая отражает зависимость времени выполнения 1111 от варианта назначения ФПП на выделенные вычислители КВС.
3. Проведена адаптация генетического алгоритма для задачи эффективного назначения ФПП на вычислители КВС, построена имитационная модель процесса выполнения 1111 на КВС и разработана методика статического назначения ФПП на выделенные вычислители КВС.
Основные задачи диссертации. В диссертации ставятся и решаются следующие задачи.
1. Анализ современных КВС с точки зрения оценки влияния особенностей иерархически-неоднородной организации памяти и КС КВС на время выполнения прикладных задач, а также анализ различных методов и моделей распределения фрагментов параллельных программ по узлам КВС.
2. Разработка математической модели оптимизации назначения ФПП на выделенные ресурсы КВС с учетом характеристик КВС, задач и накладных расходов, возникающих при параллельных вычислениях.
3. Проведение тестирования указанных выше реальных КВС с целью получения экспериментальных данных, представленных в виде коэффициентов накладных расходов.
4. Разработка имитационной модели процесса выполнения задач на КВС и алгоритма статического назначения ФПП на вычислители КВС, основанного на аппарате теории генетических алгоритмов, учитывающего особенности.
11 организация памяти и КС, для КВС МЭИ и ХТУ.
5. Оценка эффективности предложенной методики статического назначения ФПП по вычислителям КВС на примере выполнения заданных прикладных задач.
Практическая значимость работы заключается в создании программных средств, реализующих предложенную автором методику, которые могут быть использованы при разработке параллельных программ и планировании их выполнения на выделенных ресурсах КВС для повышения эффективности использования конкретных систем. Получены реальные значения времени обращения к памяти на разных уровнях ее иерархии и пропускной способности КС КВС МЭИ и ХТУ. Определены особенности конфликтов, возникающих при одновременном обращении к памяти на разных уровнях КС, которые приводят к увеличению времени решения задачи.
Достоверность результатов работы подтверждена экспериментальным исследованием решения различных задач на кластерах МЭИ, МГУ и ХТУ.
Область применения разработанной методики. Предложенная методика предполагает предварительное тестирование вводимой вновь КВС, с целью получения коэффициентов накладных расходов с последующим их использованием при подготовке прикладных задач к выполнению на выделенных ресурсах КВС. Необходимо отметить ряд ограничений применения разработанной методики:
• В работе не рассматриваются вопросы, связанные с управлением процессами и не учитываются факторы, связанные с порождением процессов ОС и другими службами управления, которые тоже вносят большие задержки.
• Методика применима для класса задач, алгоритмы которых представимы ациклическими графами с одной начальной и одной конечной вершинами.
Реализация результатов работы.
Результаты диссертационной работы Во Минь Тунга применяются в учебном процессе на кафедре ВМСиС МЭИ (ТУ) при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы».
Результаты диссертационной работы Во Минь Тунга применяются в учебном процессе в Ханойском Технологическом Университете при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы».
Результаты диссертационной работы Во Минь Тунга применяются в учебном процессе в Институте Информационных Технологий при ВАНТ (Вьетнамском Академии Наук и Технологий) при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы».
Публикации. Всего по теме диссертации было опубликовано три печатные работы.
Во Минь Тунг. Исследование методов распределения данных по процессорам кластерной системы для заданного класса прикладных задач // Труды междун. науч.-техн. конф. «Информационные средства и технологии».2008 г. С. 118—123.
Во Минь Тунг. Генетические алгоритмы в задаче о назначении // «Шестнадцатая международная научно-техническая конференция студентов и аспирантов» .2010 г. С. 401 -402.
Во Минь Тунг. Оценка характеристик кластерных вычислительных систем // Вестник МЭИ. — М.: Издательский дом МЭИ, 2010. — № 2. — С. 133−140.
Основные выводы и результаты.
1. Приведены критерии для анализа эффективности разработанного ГА назначения ФПП на вычислители КВС, так же проведен анализ для сравнения разработанного алгоритма назначения с полным перебором на модельных задачах.
2. Разработаны ПП для оценки эффективности выполнения ГА назначения в частности параллельная MPI программа расчета освещенности виртуальных экранов (ЗЕ)-рефрактограмм) и визуализации освещенности экрана в интерференционной схеме для модели сферически неоднородной среды.
3. Проведены экспериментальные исследования эффективности выполнения параллельных программ при использовании ГА назначения ФПП по сравнению с принципом назначения в планировщике или в существующих эвристических методах назначения указным в данной главе. По данным результатам было получено положительный результат характеризующий повышение эффективности выполнения ПП от 6−12%.
4. Разработана методика назначения ФПП на вычислители КВС с иерархической организацией КС и памяти. В основу методики легла разработанная автором оптимизационная модель задачи назначения с помощью ГА.
Заключение
.
Перечислим основные результаты, полученные в работе:
1. Проведен анализ и рассмотрены принципы построения современных КВС на разных аппаратных платформах, выявлено, что КВС являются мультиархитектурными, так как на разных уровнях детализации КВС применяются различные способы их организации. Написаны тестовые программы для исследования особенности иерархической организация КС и памяти КВС. Экспериментально получены следующие результаты: а) реальное время обращения к памяти на разных уровнях иерархии для КВС МЭИ и ХТУ. Полученный результат показал, на сколько может повыситься время выполнения ПП при обращения за данными находящимися в памяти высокого уровняб) реальное время передачи данных на разных уровнях иерархии КС для КВС МЭИ, ХТУ. Реальная скорость обмена оказалось, намного меньше, чем заявленная производителем, связано это с латентностью и временем, затрачиваемым на организацию функций обменав) определены накладные расходы, возникающие в процессе обращения к памяти и при передаче данных на разных уровнях иерархии для КВС МЭИ и ХТУ. Полученный результат показал что эффективность выполнения ПП может существенно снизиться от 5% до десятков %.
Из проведенных экспериментов и исследования выявлены особенности иерархической — неоднородной организации КС и памяти, а также накладные расходы возникающие в процессе выполнения ПП, учет которых существенно влияет на общее время выполнения 1111.
2. Определено что с помощью поиска варианта эффективного назначения ФПП на КВС, возможно минимизировать время выполнения за счет минимизации накладных расходов и учёта особенности организации иерархической структуры КС и памяти.
В работе был предложен механизм преобразования графа ПА при учете накладных расходов и разных уровней иерархии КС и памяти, который наглядно демонстрирует, как изменится время выполнения ПП при учете данных факторов.
3. В работе был проведен анализ существующих методов и алгоритмов назначения фрагментов ПП на КВС, описаны их положительные и отрицательные стороны. Недостаток существующих методов заключается в том, что данные методы не учитывают иерархическую структуру организации КС и памяти, а так же накладные расходы, возникающие при выполнении ПП на современных КВС. В существующих методах предлагаются эвристические алгоритмы, учитывающие только номинальную производительность вычислителей, а иногда и время передачи данных по коммутационным сетям разных уровней. Такой подход не всегда позволяет получить минимальное время выполнения ПП, так как комплексно не учитывается вышеперечисленные факторы, которые влияют на время выполнения ПП. На основания проведенных исследований в диссертации были предложены следующие варианты решения: а) поярусная модель оптимизации, основанная на разработанной в диссертации аналитической зависимости времени выполнения задачи от вариантов назначения ФПП, учитывающая особенности иерархической организации памяти, КС и накладных расходов. Представленная поярусная модель оптимизации имеет следующие недостатки — узкий диапазон решаемых задач, а так же сложность в реализации. б) определено что для более точного учета всех перечисленных факторов необходимо перейти к разработке имитационной модели, моделирующий процесс выполнения ПП на разных КВС учитывающие иерархические организация КС и памяти, а также накладные расходы на разных уровнях иерархии для современных КВС.
4. Разработан алгоритм назначения ФПП на вычислители КВС основанный на эволюционных алгоритмов[24].
5. Написана параллельная MPI программа расчета освещенности виртуальных экранов (ЗО-рефрактограмм) и визуализации освещенности экрана в интерференционной схеме для модели сферически неоднородной среды.
6. На основе оптимизационной модели задачи назначения разработанной имитационной модели и ГА назначения, который реализован в программный продукт. Использования данной программы позволяет автоматизировать процесс выбора эффективного варианта назначения для заданных исследуемых классов задач. Применения предложенной оптимизационной модели задачи назначения позволило решить задачу назначения для множества задач, такие как, перемножения матриц, решения задачи надежности [3], расчета изображения светового излучения в трехмерном пространстве для оптически сферической неоднородной среды.
7. Предложенный ГА назначение имеет достаточно простое программное реализация. Затраты времени на поиск варианта эффективного назначения на порядки меньше чем при полном переборе. а) рассчитан доверительный интервал для разработанного ГА поиска варианта эффективного назначения, который показал узкий диапазон сходимости результатов для выбранных тип задач. Так же было доказана адекватность разработанной модели на примере перемножения матриц. б) отметим, что разработанный ГА назначения может быть использован для улучшения разработанных алгоритмов назначения. Так же разработанная имитационная модель выполнения ПП на КВС может быть использована для других алгоритмов назначения.
8. Приведены критерии для анализа эффективности разработанного ГА назначения по сравнению с другими алгоритмами или полным переборам.
9. Проведены экспериментальные исследования эффективности разработанного ГА назначения на КВС МЭИ, МГУ, ХТУ. Полученный результат продемонстрировал повышение эффективности выполнения ПП на 612% по сравнению с алгоритмом назначения, заложенным в планировщике КВС, или другими эвристическими методами.
Разработанная программная реализация оптимизационной модели поиска варианта назначение имеет возможность для внедрения в планировщики на КВС.
10. На основания проведенных в диссертации исследований и разработанного алгоритма назначения, была разработана методика назначения ФПП на вычислители КВС.
