Содержание к диссертации
Введение
Глава 1. Анализ кластерных вычислительных систем и методов распределения задач 14
Классификация параллельных компьютеров и систем 14
1.1.2. Обзор современных суперкомпьютерных систем СНГ 15
1.2. Особенности организация кластерных вычислительных систем 19
1.3. Классификация кластерных вычислительных систем 21
1.1. Структуры кластеров, построенных на разных аппаратных платформах на примере кластеров МЭИ И ХТУ 22
1.5. Принципы организации памяти кластерной вычислительной системы на примере кластера МЭИ И ХТУ 24
1.6. Коммутационные среды кластерной вычислительной системы 25
1.7. Анализ современных методов распределения задач...
1.7.1. Режимы функционирования кластерных вычислительных систем 27
1.7.2. Управление ресурсами в распределенных вычислительных системах 28
1.7.3. Планировщики кластерных вычислительных систем 29
1.8. Модели и алгоритмы назначения задач наКВС 30
1.8.1. Понятие назначения задач на КВС 30
1.8.2. Обзор моделей распределения ресурсов и алгоритмов назначения 32
1.9. Постановка задачи решаемой в диссертации 41
1.9.1. Формальное описание модели кластерной вычислительной системы 41
1.9.2. Формализованное описание класса задач 43
1.9.3. Задача эффективного назначения фрагментов параллельных программ на вычислители КВС 45
1.9.4. Постановка задачи 46
Основные результаты и выводы 47
Глава 2. Экспериментальное исследование характеристик кластерных вычислительных систем, построенных на разных аппаратных платформах 49
2.1. Предложенные тестовые программы для исследования факторов,
влияющих на время выполнения параллельных программ 52
2.2. Результаты выполнения тестовых программ 54
2.3. Разработка тестовых MPI-программ для исследования коммуникационной среды кластера 63
Основные результаты и выводы 69
Глава 3. Модель и алгоритм назначения фрагментов параллельных программ на вычислители КВС 71
3.1. Оценка ожидаемого результата времени выполнения параллельных программ на КВС 71
3.2. Оптимизационная модель назначения фрагментов параллельных программ на вычислители КВС 78
3.2.1. Словесное описание математической модели, используемой в диссертации для моделирования процесса выполнения параллельных программ на КВС в зависимости от варианта назначения 79
3.2.2. Аналитическая зависимость времени выполнения параллельных программ от характеристик КВС и варианта назначения фрагментов параллельных программ на вычислители КВС 81
3.2.3 Оптимизационная модель обобщенного вида задачи назначения 89
3.2.4 Имитационная модель по интервалам времени для задач назначения 90
3.3 Генетический алгоритм назначения вершин графа алгоритма на КВС 95
Основные результаты и выводы 107
Глава 4. Анализ эффективности разработанного алгоритма назначения 108
4.1 Критерии эффективности алгоритма назначения 108
4.2. Анализ критерии эффективности от количества вычислителей и алгоритма назначения 109
4.3. Экспериментальные исследования эффективности выполнения параллельных программ при разных вариантах назначения на КВС 112
4.4. Методика назначения фрагментов параллельных программ на вычислители КВС 121
4.4.1. Предварительная оценка эффективности выполнения параллельных программ 121
4.4.2. Формальное представление класс решаемой задачи и КВС 126
4.4.3. Тестирования КВС для получения характеристик
необходимых для имитационной модели 127
4.4.4. Назначения фрагментов 1111 на вычислители КВС 127
4.4.5. Оценка результатов выполнения 1111 на КВС 128
Основные выводы и результаты
- Принципы организации памяти кластерной вычислительной системы на примере кластера МЭИ И ХТУ
- Результаты выполнения тестовых программ
- Словесное описание математической модели, используемой в диссертации для моделирования процесса выполнения параллельных программ на КВС в зависимости от варианта назначения
- Методика назначения фрагментов параллельных программ на вычислители КВС
Введение к работе
В настоящее время кластерные вычислительные системы (КВС) являются самыми распространенными из широко используемых суперкомпьютерных вычислительных систем в мире. Тем не менее, эффективное применение КВС на практике представляет собой не простую задачу. Обусловлено это множеством причин. Одной из причин, которая влияет на эффективность применения КВС, является не достаточно обоснованное решение задачи назначения фрагментов параллельных программ (ФПП) на КВС. При неудачном назначении, время выполнения задачи намного возрастает за счет накладных расходов. Под накладными расходами в работе понимаются те временные затраты, которые определяются факторами, замедляющими выполнение задачи. Это непроизводительное время, связанное с обменом блоками данных между оперативной и дисковой памятью, время на разрешение хшіцілйкїйв, которые возникают при учете приоритетов на ооращекия к памяти и передаче данных между коммутационными сетями (КС).
Актуальность работы. Существующие методы решения задачи назначения ФПП на вычислители КВС комплексно не учитывают вышеперечисленные факторы. В ряде работ предлагаются эвристические алгоритмы, учитывающие только номинальную производительность вычислителей, а иногда и время передачи данных по коммутационным сетям разных уровней. В настоящей работе предлагается в качестве дополнительных характеристик в процессе статического назначения ФПП учитывать приведенные выше факторы, представленные коэффициентами накладных расходов, что позволит повысить эффективность выполнения параллельных программ (ПП) на КВС. Поэтому разработка методики назначения ФПП на вычислители КВС, обеспечивающей учет таких важных характеристик конкретных КВС, как состояние памяти вычислительного узла в момент обработки задачи и неоднородность коммуникационной среды, выраженных в виде коэффициентов накладных расходов, является актуальной задачей.
Объектом исследования в работе являются кластерные вычислительные системы на примере кластеров МЭИ и Ханойского Технологического Университета (ХТУ), предметом исследования — особенности организации памяти и КС КВС, учет которых позволит сократить время выполнения параллельных программ на КВС за счет эффективного назначения ФПП на выделенные вычислительные ресурсы.
Цель работы и задачи исследования.
Цель диссертационной работы заключается в исследовании КВС для получения численных значений коэффициентов накладных расходов, разработка математической модели и методики статического назначения ФПП, учитывающих как характеристики задач, КВС, так и значения данных коэффициентов.
Поставленная цель определяет следующие основные задачи исследования.
1. Анализ современных КВС с точки зрения оценки влияния особенностей
иерархически-неоднородной организации памяти и КС КВС на время выполнения прикладных задач, а также анализ различных методов и моделей распределения фрагментов параллельных программ по узлам КВС.
Разработка математической модели оптимизации назначения ФГШ на выделенные ресурсы КВС с учетом характеристик КВС, задач и накладных расходов, возникающих при параллельных вычислениях.
Проведение тестирования указанных выше реальных КВС с целью JкщчeIyIЯJЭкcпepимeнтaльныx_дaнньrx,лIpeдcтaвлeнньIX-в-BИдe-кoэффициeнтoв— накладных расходов.
Разработка имитационной модели процесса выполнения задач на КВС и алгоритма статического назначения ФГШ на вычислители КВС, основанного на аппарате теории генетических алгоритмов, учитывающего особенности организация памяти и КС, для КВС МЭИ и ХТУ.
Н^чияя новизна результатов полненных в диссертации.
Определенны особенности иерархически-неоднородной организации памяти и коммуникационной среды КВС, а также виды накладных расходов, возникающих на разных уровнях иерархии, влияющих на время выполнения параллельных программ.
Разработана математическая модель задачи оптимизации обобщенного вида, выраженная в аналитической форме, которая отражает зависимость времени выполнения ПП от варианта назначения ФПП на выделенные вычислители КВС.
3. Проведена адаптация генетического алгоритма для задачи
эффективного назначения ФПП на вычислители КВС, построена имитационная
модель процесса выполнения ПП на КВС и разработана методика статического
назначения ФПП на выделенные вычислители КВС.
Практическая значимость работы заключается в создании программных средств, реализующих предложенную автором методику, которые могут быть использованы при разработке параллельных программ и планировании их выполнения на выделенных ресурсах КВС для повышения эффективности использования конкретных систем. Получены реальные значения времени обращения к памяти на разных уровнях ее иерархии и пропускной способности КС КВС МЭИ и ХТУ. Определены особенности конфликтов, возникающих при одновременном обращении к памяти на разных уровнях КС, которые приводят к увеличению времени решения задачи.
Внедрение результатов работы.
Результаты диссертационной работы используются в учебном процессе кафедры ВМСиС МЭИ (ТУ) при проведении лекционных и лабораторных занятий по курсу «Вычислительные системы». Они также применяются в учебном процессе Ханойского Технологического Университета и Института Информационных Технологий при Вьетнамской Академии Наук и Технологий для проведения лекционных и лабораторных занятий по курсу «Вычислительные системы».
Достоверность результатов работы подтверждена экспериментальным исследованием решения различных задач на кластерах МЭИ, МГУ и ХТУ.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 15-й Международной научно-технической конференции «Информационные средства и технологии», г. Москва, 2008 г., а также на 16-й Международной научно-технической конференции студентов и аспирантов, г. Москва, 2010 г.
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 3 печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка используемых источников и 9 приложений. Диссертация содержит 218 страниц машинного текста, включая приложения.
Принципы организации памяти кластерной вычислительной системы на примере кластера МЭИ И ХТУ
По типу ВУ кластеры делятся на гомогенные (однородные), и гетерогенные (неоднородные)[1]. «Гомогенным» принято называть кластер, все ВУ которого имеют одинаковую конфигурацию, соответственно, производительности вычислителей в ВУ одинаковые, либо кластер, где все ВУ работают под управлением одной ОС. «Гетерогенным» называют кластер, узлы которого имеют разную конфигурацию и, соответственно, производительность, либо кластер, узлы которого работают под управлением разных типов ОС. Неоднородность вычислительного кластера вносит следующие существенные проблемы в организацию вычислительного процесса: - различие в производительности разных ВУ кластера требует соответствующего учёта при распределении работы между процессами, которые выполняются на разных ВУ (балансировка загрузки узлов); - различие в архитектуре процессоров требует подготовки разных выполняемых файлов для разных узлов, а в случае различий в представлении данных может потребоваться и преобразование информации при передаче сообщений между узлами. Похожие проблемы могут возникнуть и при использовании разных типов ОС.
По типу используемой памяти кластеры делятся на так называемые DSM- и DM-кластеры [1]. Если в вычислительном кластере аппаратно или аппаратно -программно реализована распределённая общая память (DSM - distributed shared memory), позволяющая выполняющимся на разных узлах программам взаимодействовать через общие переменные, то такой кластер является DSM -кластером. Если распределённая общая память отсутствует, и программы взаимодействуют посредством передачи сообщений, то кластер является DM -кластером (DM - distributed memory).
По типу используемой ОС кластеры делятся на два больших класса подобных систем: Unix-кластеры и Windows-кластеры.
Из таблицы 2 и [8] можно увидеть, что большинство ВУ современных КВС построены на основе двух платформ поэтому, исследуя принципы и механизмы этих платформ можно сделать выводы, которые будут справедливы и для других систем. Вычислительные узлы КВС МЭИ построены на основе двух двуядерных процессоров AMD Opteron 254[10]. Вычислительные узлы КВС ХТУ построены на двух двуядерных процессорах Хеоп Е5410[11].
Для простоты анализа сделаем следующее допущение: пусть КВС представлена в виде дерева, состоявшего из множества уровней. Каждый уровень системы образован из множества модулей (например: система, ВУ, процессор, вычислители), которые объединены КС своего уровня. В зависимости от типа выбранного ВУ определяется организация доступа к памяти и механизм обмена между ячейками памяти.
На рис.1.1 представлена четырехуровневая иерархическая структура КВС первого типа, в которой первый уровень это сама система, состоящая из п ВУ, объединенных коммуникационной средой InfiniBand (1В)[12], которые представляют второй уровень. Третий уровень показывает, что каждый ВУ состоит из двух процессоров, объединенных общей памятью через контроллер каждого процессора, четвертый уровень соответствует двум вычислителям каждого процессора, функционирующим с использованием технологии
HyperTransport (НТ)[13]. На рис. 1.2 представлена четырехуровневая иерархическая структура второго типа, отличающаяся от первой тем, что связь между вычислителями как внутри одного процессора, так и в разных процессорах ВУ осуществляется через общий контроллер памяти, объединенных через шину FSB[14].
Иерархическая структура КВС второго типа Анализируя рис. 1.1 и 1.2, можно заметить, что все вычислители ВУ КВС второго типа подключены к одному контролеру памяти, поэтому есть высокая вероятность появления конфликтов при одновременном запросе на доступе к памяти. Следовательно, производительность ВУ может существенно упасть из-за простоя вычислителей, простаивающих в ожидании своей очереди для доступа к памяти. Каждый процессор КВС первого типа имеет свой контролер памяти, следовательно, конфликтов при запросе на доступ к памяти будет меньше, чем у КВС второго типа. Однако для доступа вычислителя к оперативной памяти другого процессора, необходимо обращаться через линк НТ и использовать его встроенный контролер. Следовательно, доступ к ОЗУ является неоднородным, время доступа может быть разным. Во второй главе будут приведены результаты экспериментов, которые проводились для подтверждения всех данных предположений.
На общее время решения задачи влияет много факторов — это время выполнения арифметических операций, время взаимодействия с памятью, пропускная способность КС и механизмы назначения ФГШ на КВС.
Время выполнения арифметических и логических операций зависит от быстродействия вычислителя, которое в первую очередь определяется его тактовой частотой. Для доставки данных из памяти в вычислитель используются разные КС, что влияет на скорость доставки данных. Поэтому время выполнения программы на вычислителе определяется тем, с какой памятью он непосредственно работает и как организован механизм доставки данных[16].
Основное требование к памяти - это обеспечение малого время доступа. На рис. 1.1 и рис 1.2 представлены иерархические структуры, соответствующие двум кластерам с разными платформами ВУ Рис. 1 соответствует кластеру, у которого ВУ построен на основе ВУ многоядерных процессоров AMD Opteron. Архитектура AMD отличается от обычных платформ тем, что каждый процессор является независимой и самостоятельной единицей, включающей в себя всю функциональность северного моста[14,15]. Непосредственно каждый процессор ВУ имеет доступ только к своему блоку оперативной памяти. Доступ к другому блоку памяти возможен только через контроллер памяти другого процессора. Передача данных между процессорами одного ВУ осуществляется через шину НТ. На рис 2 представлена КВС, за основу ВУ, в которой взята совокупность многоядерных процессоров компании Intel. Архитектура компании Intel отличается от AMD тем, что это традиционная и привычная для пользователей SMP-система с общей шиной. Выглядит подобная система так: один чипсет, к которому подключается вся оперативная память, и процессорная шина с автономным контроллером, к которой подключены все процессоры [15].
Как уже отмечалось, выбор КС определяется, прежде всего, классом решаемых задач, поэтому кластерные системы, используют самые разнообразные сетевые технологии. В состав кластера могут входить несколько видов сетей, с разными технологиями передачи данных. Одна сеть может отвечать за передачу управляющей информации, другая за поддержку вычислительного процесса в ВУ кластера. Стоит отметить, что характеристики КС оказывают большое воздействие на общую производительность кластерных систем. Знание этих характеристик, а также ряда других параметров системы, позволяет оценить их влияние на эффективность решения рассматриваемых задач на кластере. Числовых характеристик коммуникационных сетей, по сути говоря, две: латентность и пропускная способность.
Результаты выполнения тестовых программ
Пятый тест предназначен, для определения реальной пропускной способность (скорость обмена на уровне MPI) КС при передаче данных между вычислителями в пределах одного ВУ и между вычислителями в разных ВУ для КВС МЭИ и ХТУ. Напомним, что КВС имеет трехуровневую иерархически - неоднородную коммуникационную среду, обеспечивающую передачу данных. Для КВС МЭИ: - между ядрами внутри процессора через общую память (первый уровень); - между ядрами разных процессоров одного узла через сеть HyperTransport (второй уровень); - между ядрами разных вычислительных узлов, через сеть InfiniBand (третий уровень).
Для замера времени передачи данных, первый вычислитель посылает пакет данных определенной размерности другому вычислителю. Пересылка данных осуществлялась с помощью функции MPISend [3,20,21,22]. Для повышения точности результатов данный тест повторялся многократно. Среднее арифметическое полученных значений определяется как время Т2, так как в данном случае КС используется в моно программном режиме. Проведя данный тест на КВС МЭИ было определено, что время передачи данных между вычислителями, находящимися в одном процессоре или в разных процессорах одного ВУ почти одинаково, отличие между ними составляет всего лишь 1-2%, поэтому считаем, что д2 — дг. При передаче данных между вычислителями, находящимися в разных ВУ, время передачи существенно возрастает, примерно в два раза по сравнению с передачей данных в пределах одного ВУ, если объемы данных более 1 Мб. Таким образом, при передаче данных между вычислителями находящимися в одном процессоре или в разных процессорах одного ВУ д 2 = д2 = 1, а при передаче данных между вычислителями находящихся в разных ВУ д 2 = 2.
Для определения коэффициентов накладных расходов г2 (передачи данных в загруженном состоянии) данный тест выполнялся сразу на нескольких вычислителях. Например, для замера времени передачи данных между вычислителями находящимися в разных ВУ, эксперимент проводился следующим образом. Все четыре вычислителя одного ВУ передавали четырем вычислителям другого ВУ. Таким образом, мы загружаем КС одновременной передачей данных между вычислителями. По полученным результатам, для случая передачи данных в пределах одного ВУ, г2 = 0,2, а при передаче данных между ВУ є2 = 3,8 для данных объемом около 1 Мб. Автор предполагает, что возникновение данных задержек связано с тем, что ВУ содержит только один адаптер InfiniBand, следовательно, одновременные заявки на передачу данных всех вычислителей ВУ, приводят к возникновению конфликтов.
Аналогично был проведен данный тест для КВС ХТУ. Отличием в КС является то, что все вычислители объедены одним контролером памяти. Обмен осуществляется: - между ядрами внутри процессора через общую память с помощью шины FSB (первый уровень); - между ядрами разных процессоров одного узла через общую память с помощью шины FSB (второй уровень); - между ядрами разных вычислительных узлов, через сеть GigabitEthernet (третий уровень). Время передачи данных между вычислителями, находящимися в одном процессоре или в разных процессорах одного ВУ почти одинаково. При передаче данных малых размерностей около 1Кб разница составляет 2%. При передаче данных большего объема, порядка нескольких Мб разница примерно в 2-3%. автор предполагает, что некоторое увеличение времени передачи данных вызвано латентностью КС. Таким образом, можно считать д2 = д"2. Это свидетельствуют о том, что время передачи зависит от объема передаваемых данных и от характеристик коммуникационной сети, используемой для передачи. При передаче данных (объем около 1Мб) между вычислителями, находящимися в разных ВУ, время передачи существенно возрастает, примерно в 21 раз по сравнению с передачей данных между вычислителями, находящимися в одном ВУ. Таким образом, при передаче данных между вычислителями, находящимися в одном процессоре или в разных процессорах одного ВУ д 2 = д 2 = 1, а при передаче данных между вычислителями, находящимися в разных ВУ д2 = 21. Расчет коэффициентов накладных расходов при загруженной КС показал, что для случая передачи данных в пределах одного ВУ г2 = 0,16, а при передаче данных между ВУ Е2"= 7,3. Результаты проведенных исследований представлены в таблицах 2.3 — 2.6 и на рис. 2.9 и 2.10.
Время передачи данных между КС для КВС МЭИ Таблица 2. Объем передаваемых данных, Кб 1,6 8 48 80 800 время передачи данных (мкс) между вычислителями в одном ВУ 2,68 10,5 54,1 79,6 590 время передачи данных (мкс) между вычислителями в разных ВУ 10,1 26,3 88,1 133,6 1180 Значение коэффициентов д2 для КВС МЭИ Таблица 2. КВС МЭИ Коэффициенты д 2 = д 2 междувычислителями водном ВУ ё2 междувычислителями вразных ВУ Время передачи данных между КС для КВС ХТУ
Анализируя проведенные исследования, можно сделать вывод, что время решения задачи в сильной степени зависит от накладных расходов и используемых уровней иерархии КС и памяти. В начале главы было отмечено, что время U ([ ]=с) выполнения і-го фрагмента 1111 на вычислителе, зависит от быстродействия вычислителя и структуры объединенных общей памятью фрагмента ПП. Проведением тестов доказано, что производительность вычислителя тесно связана с уровнем памяти, в который вычислитель обращается за данными. Так же производительность вычислителя будет падать, если возникнут накладные расходы при обращении к памяти. Введем коэффициент Кпр коэффициент уменьшения производительности вычислителя, который зависит от накладных расходов при обращения к памяти, данный коэффициент отражает, на сколько увеличивается время выполнения ФПП на вычислителе при возникновении накладных расходов s,, Кпр = 1 + є,. Так же производительность вычислителя будет падать если в ВУ где расположен вычислитель обрабатывается ПП другого пользователя. Введем коэффициент Upl который зависит от количества пользователей, использующие общие ресурсы в ВУ (в нашем случае это общая память), данный коэффициент отражает, на сколько увеличивается время выполнения ФПП на вычислителе при возникновении данного конфликта. Таким образом, время выполнения фрагмента 1111 можно вычислить как t, SW(V) Кпр Upl. При расчете времени передачи данных между вычислителями, кроме учета уровня иерархии КС, надо учитывать накладные расходы при передаче данных. Следовательно, время передачи данных между вычислителями можно h определить как ———Ккс, где коэффициент Ккс отражает, на сколько увеличивается время передачи фрагмента ПП при возникновении накладных расходов Е2. Рис. 2.11 иллюстрирует преобразование графа алгоритма представленный на рис. 1.4 при учете накладных расходов и используемых уровней иерархии КС и памяти.
Словесное описание математической модели, используемой в диссертации для моделирования процесса выполнения параллельных программ на КВС в зависимости от варианта назначения
Так как вычислитель может выполнять множество ФПП в процессе выполнения всей задачи, то пространство полного перебора возможных вариантов назначений вершин на вычислители составляет KN, где К количество вычислителей в КВС и N количество вершин в графе алгоритма. Так как для проверки каждого назначения производится процесс моделирования выполнения задачи на КВС, то время затрачиваемое на полный перебор возможных вариантов назначения может быть заведомо больше времени решения самой задачи при самом худшем распределении. В таблице 1 представлены результаты сравнения времени поиска эффективного варианта назначения при ГА и полным перебором на примере нескольких задач (представленных в графе алгоритма). Выигрыш во времени поиска эффективного варианта назначения достигнут из-за того, что для поиска минимального времени решения задачи количество переборов при ГА на порядок меньше, чем при полном переборе. Несмотря на это, минимальное время решения задачи при найденном варианте назначения с помощью ГА приближенно равно минимальному времени решения задачи при полном переборе всех вариантов назначения. Следовательно, полученный вариант назначения, найденный при ГА считается правильным. Было проведено варьирование параметров ГА для проверки достоверности полученных результатов при выбранном количестве вариантов перебора при моделировании. По проведенным экспериментам для типичных задач автор, рекомендует выбирать большое количество потомков кратное начальным популяциям или на порядок больше для моделирования.
Так как ГА является эвристическим алгоритмом, то необходимо рассчитать достоверный интервал (ДИ)[32] для доказательства достоверности полученных результатов. _ s _ s \ sin -Jn J где - х среднее арифметическое значение переменной[32], вычисленное по выборке; s - стандартное отклонение переменной[32], вычисленное по выборке; п - объем выборки; zl-a/2 - доверительный коэффициент, соответствующий доверительной вероятности (1 - а); для а = 0,1 доверительный коэффициент z0,95 = 1,64; для а = 0,05 z0,975 = 1,96; для а = 0,01 z0,995 = 2,58.
Для задачи № 2 13/19 (вершин/дуг), где все 3 вычислителя в одном ВУ при доверительной вероятности равной 0,95 и при выборке равной тридцати, доверительный интервал составил (208,212). Для задачи № 3 14/21 (вершин/дуг), где все 3 вычислителя расположены в одном ВУ, доверительный интервал составил (250,254). Такой узкий диапазон сходимости результатов, связан с выбранными типами задач.
Для доказательства адекватности разработанной модели было проведено сравнение реального времени решения ПП и время решения данной ПП на модели для разных вариантов назначения. Время решения ПП на модели показало одинаковый динамический характер изменения времени решения ПП от разных вариантов назначений. Для иллюстрации на рис. 3.17 и 3.18 представлены значение коэффициента ускорения[1] при решении задачи перемножения матриц от разных вариантов назначениях XI и Х2 на КВС и на модели.
Область применения разработанного алгоритма назначения. Разработанная оптимизационная модель с использованием ГА для задач назначения фрагментов ПП на вычислители КВС требует следующее: 1) Параллельная программа задачи должна быть представленная в виде графа алгоритма. Вершины графа взвешены временем выполнения ti соответствующего фрагмента программы на вычислителе с заданным быстродействием и объемом Vi обрабатываемых данных, дуги графа взвешены объемом ht] передаваемых данных. 2) Должны быть представлены все параметры модели КВС, а так же накладные расходы, которые могут повлиять на время выполнения задачи. 3) Представление данных в виде генов для ГА. Применения разработанного алгоритма назначения фрагментов ПП позволяет получить вариант эффективного назначения быстрее, чем при полном переборе. Основные результаты и выводы 1. Разработан алгоритм назначения ФПП на выделенные вычислители КВС. 2. Построена в обобщенном виде аналитическая зависимость времени выполнения задачи от варианта назначения ФПП. 3. На основе построенной аналитической зависимости разработана оптимизационная модель задачи назначения для ярусно параллельной формы. 4. Разработана имитационная модель, моделирующая процесс выполнения ПП на выделенные вычислители системы. 5. Разработана оптимизационная модель поиска эффективного варианта назначения на КВС на основе разработанного ГА. 6. Рассчитан доверительный интервал для разработанного оптимизационной модели поиска варианта эффективного назначения, который показал узкий диапазон сходимости результатов для выбранных тип задач. 7. Доказано адекватность разработанной модели на примере задачи перемножение матриц.
Для оценки эффективности алгоритма назначения была выбрана методика, представленная в работе[4]. В главе приведены критерии, по которым проводилась оценка эффективности разработанного алгоритма назначения. На основе результатов, полученных путем имитационного моделирования, проведен анализ эффективности представленного алгоритма назначения по сравнению с полным перебором или с назначением, полученным с помощью алгоритма случайного выбора при таком же количестве выборки как при ГА.
Методика назначения фрагментов параллельных программ на вычислители КВС
Существуют апостериорная и априорная оценки [1,27,28]. Попробуем дать определения для них. Априорная оценка позволяет оценивать возможную эффективность (до реализации задачи на параллельной ВС), что даёт возможность понять, стоит ли дальше пытаться реализовывать задачу на параллельной ВС. Апостериорная оценка позволяет оценить полученную эффективность после реализации задачи на параллельной ВС. С помощью данных показателей можно понять, что, нужно изменить для повышения уже достигнутой эффективности решения.
Для реализации этого метода определим показатели, характеризующие эффективность решения задачи на параллельных системах. Когда возникает потребность решать задачу быстрее, и чтобы понять насколько быстрее это удается сделать, нужно ввести понятие "Ускорение". Ускорение может вводиться различными способами, многообразие зависит от того, что с чем и как мы сравниваем [1]. Мы будем рассматривать - К , показывающий соотношение времени работы последовательной или параллельной реализации задачи на К вычислителях ко времени решения параллельной реализации задачи на К вычислителей: Т —- - если используется параллельная и последовательная К, реализация задачи (4.1) Т, —- - если используется только параллельная реализация задачи ,где То — время работы последовательной реализации задачи на одном вычислителе, Ті — время работы параллельной реализации задачи на одном вычислителе используемой КВС, Тк - время работы параллельной реализации задачи на К вычислителей используемой КВС.
Следует отметить, что в общем случае То Г/, т.е. последовательная реализация задачи работает быстрее, чем параллельная реализация задачи на одном вычислительном устройстве параллельной ВС. Так как в любой параллельной программе всегда присутствует дополнительная часть кода, обеспечивающая распараллеливание вычислений, а именно точки синхронизации параллельных фрагментов программы, передача данных от одного фрагмента другому и т.д.
Ускорение системы, никогда не превысит К вычислителей КВС, и может достигать К в том случае, когда все устройства системы имеют одинаковую пиковую производительность и полностью загружены. коэффициент относительного ускорения (эффективность)К., показывающий степень загрузки К вычислителей КВС и определяется следующим способом.
Вышеуказанные определения ускорения и эффективности применимы только к системам, состоящим из одинаковых вычислительных устройств (гомогенные ВС), и не распространяются на смешанные системы (гетерогенные ВС). Так как наша система рассматриваемая в диссертации является гомогенной, а также выше указанные характеристики используются для апостериорной оценки эффективности решения задачи на некоторой параллельной ВС, то выше указанные определения пригодны для реализации.
Теперь рассмотрим подробней априорную оценку. Введём следующие обозначения. Пусть параллельная программа, соответствующая решаемой на параллельной ВС задаче, состоит из N операций. Причём время выполнения каждой операции равно т. Пусть а {0 а Г) есть некоторая доля операций (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения) выполняемых последовательно, а {1-а) — доля операций, выполняемых параллельно [28]. При этом выполнение доли последовательных операций не совмещено во времени с выполнением доли параллельных операций [29]. Крайние случаи в значениях а соответствуют полностью параллельным (а = 0) и полностью последовательным (а = 7) программам.
Тогда при выполнении параллельной программы на одном вычислительном устройстве параллельной ВС последовательные операции (вычисления) занимают время a-N-т, а параллельные - время (l-a)-iV-r. При выполнении параллельной программы на р вычислительных устройствах параллельной ВС последовательные операции занимают то же самое время OL-N, а параллельные — время (l-a)-Nfp. Произведение N равно времени выполнения Ті параллельной программы на одном вычислительном устройстве параллельной ВС. Таким образом, общее время выполнения параллельной программы нар вычислительных устройствах параллельной ВС равно Тр = а-Т, + (1-а)- Ttlp. Тогда формулы (2) и (3) для коэффициентов абсолютного и относительного ускорения принимают следующий вид: К к Из формулы (4.2) выразим зависимость эффективности: к 1 эф [ахК + (1-а)] (4.3) При любом режиме работы ускорение не может превзойти обратной величины доли последовательных вычислений. Пусть К — од. Тогда на основании формулы (4.3) получаем: К-кя СС Формула (4.5) - известна как третий закон Амдала [1]. Согласно этому закону для параллельной программы, имеющей последовательные и параллельные операции, выполнение которых не совмещено во времени, границей ускорения её работы является величина, обратная доле последовательных операций. Иными словами, если, например, доля последовательных операций в параллельной программе составляет а — 0.1, а доля параллельных операций соответственно (1-а) = 0.9, то получить ускорение более чем в 10 раз в принципе невозможно вне зависимости от качества реализации параллельной части кода программы и числа используемых вычислительных устройств параллельной ВС. Закон Амдала используется для прогноза возможного ускорения в смысле определения верхней границы данного ускорения.
Для значительного повышения скорости вычислений необходимо уменьшать долю последовательных операций в программе. В программах с большим объёмом параллельных операций заметным является уменьшение количества последовательных операций даже на 1% от общего количества операций параллельной программы. Повышение скорости вычислений за счёт повышения скорости работы параллельных операций не даёт ощутимого эффекта в увеличении скорости работы параллельной программы, так как остающиеся последовательные вычисления всё в большей степени тормозят ускорение работы параллельной программы в целом.
Таким образом, участки не подлежащие распараллеливанию являются одним из факторов влияния на эффективность выполнения ПП. Кроме данного фактора есть еще важные факторы, которые нужно учитывать на стадии анализа эффективности выполнения ПП. Одним из них является степень связанности задач[3] и качество распараллеливания задач и ее программная реализация.