Содержание к диссертации
Введение
Глава 1. Анализ архитектур систем распределенных вычислений, способов оптимизации их построения и оптимизации процесса вычислений 16
1Л Обзор архитектур распределенных вычислительных систем 16
1.1.1 Классификация архитектур многопроцессорных вычислительных систем 17
1.1.2 Обзор вычислительных систем метакомпьютерного типа 22
1.2 Обзор методов компоновки и размещения 31
1.2.1 Простая задача назначения...! 32
1;2.2 Квадратичная задача назначения 33
1.2.3 Задачи, решаемые с помощью линейного и динамического программирования... 34
Г.2.4 Задачи компоновки, решаемые в теории автоматизации проектирования 36
1.215 Методы оптимизации размещения из теории графов 37
1.3 Обзор средств управления заданиями в распределенных вычислительных системах. 39
1.4 Выводы по главе '. 44
Глава 2. Стратегия размещения узлов и подзадач в системе распределенных вычислений кластерно-метакомпьютерного типа ... 47
2.1 Стратегия размещения узлов в РВСКМТ.. 47
2.2 Размещение подзадач в идеально надежной системе 62
2.3 Размещение подзадач в системе с отказами 74
2.4 Размещение подзадач с использованием равномерного деления 85
2.5 Выводы по главе 91
Глава 3. Система управления заданиями на основе адаптивной стратегии размещения подзадач 92
3.1 Классификация стратегий размещения подзадач и обоснование выбора адаптивной стратегии размещения подзадач 92
3.1.1 Метод равномерного размещения в идеальных системах (системах без отказов узлов) 93
3.1.2 Метод равномерного размещения в реальных системах (системах с отказами узлов) 95
3.1.3 Метод неравномерного размещения в идеальных системах (системах без отказов узлов) 96
3.1.4 Метод неравномерного размещения в реальных системах (системах с отказами узлов) 97
3.1.5 Обоснование выбора адаптивной стратегии размещения подзадач .99
3.1.6 Метод адаптивного размещения подзадач с барьерной адаптацией. 100
3.1.7 Метод адаптивного размещения подзадач с непрерывной адаптацией 102
3.2 Система управления заданиями на основе адаптивного метода размещения подзадач с непрерывной адаптацией 102
3.2.1 Размещение на основе известных статистических данных о надежности узлов. 102
3.2.2 Размещение на основе динамически рассчитываемых данных о надежности узлов '. 108
3.3 Выводы по главе 116
Глава 4. Программный комплекс для управления распределенной вычислительной системой кластерно-метакомпьютерного типа 118
4.1 Основные характеристики систем управления заданиями для кластерно- метакомпьютерных систем 118
4.2 Модуль сбора статистики для системы распределенных вычислений ... 120
4.2.1 Программа журналирования NS Logger 120
4.212 Программа анализа статистики NS Analyzer 123
4.3 Модуль планирования вычислений для распределенной вычислительной системы 129
4.4 Результаты работы РВСКМТ для расчетно-ориентированных задач. 135
4.4.1 Равномерное разбиение в системе без отказов 136
4.4.2 Статическая стратегия размещения подзадач в системе без отказов 138
4.4.3 Статическая стратегия размещения подзадач в системе с отказами. 141
4.5 Результаты работы РВСКМТ для обменно-ориентированных задач 146
4.5.1 Равномерное разбиение в системе без отказов 146
4.5.2 Статическая стратегия размещения подзадач в системе без отказов148
4.5.3 Статическая стратегия размещения подзадач в системе с отказами. 150
4.6 Результаты применения адаптивной стратегии размещения подзадач в системе с отказами. 153
4.6.1 Размещение на основе известных статистических данных о надежности узлов153
4.6.2 Размещение на основе динамически рассчитываемых данных о надежности узлов 154
4.7 Выводы по главе 157
Заключение... 159
Литература
- Классификация архитектур многопроцессорных вычислительных систем
- Размещение подзадач в идеально надежной системе
- Метод равномерного размещения в реальных системах (системах с отказами узлов)
- Модуль сбора статистики для системы распределенных вычислений
Введение к работе
В настоящее время фундаментальные и прикладные проблемы, эффективное решение которых возможно только с использованием высокопроизводительных вычислений, объединены понятием "Grand challenges", которое включает в себя, например, задачи предсказания климата и глобальных изменений в земной коре [1], задачи аэродинамики для самолетостроения и создания; реактивных двигателей [2], распознавание изображений при навигации движущихся объектов [3], и т.д.
При решении этих задач возникает потребность в значительно больших вычислительных ресурсах, чем может предоставить обычный компьютер. Таким задачам необходимо либо большее быстродействие, либо возможность обрабатывать и хранить большие объемы информации.
Большого быстродействия требуют сложные, многомерные задачи; которые необходимо решить в течение определенного, достаточно ограниченного времени. Один из наиболее характерных примеров - задачи прогноза погоды. Область решения (атмосфера) разбивается на отдельные пространственные; ячейки, причем для расчета временных изменений? вычисления в каждой ячейке повторяются много раз. Если объем ячейки равен 1 км3, то для моделирования слоя атмосферы высотой в 10 км потребуется 5x108 таких ячеек. Предположим, что вычисления в каждой ячейке потребуют 200 операций с плавающей точкой, тогда за один временной шаг потребуется выполнить 1011 операций с плавающей точкой. Для того, чтобы произвести расчет прогноза погоды с заблаговременностью 10 дней с 10-ти минутным шагом по времени, компьютеру производительностью 100 MFlops (10 операций с плавающей точкой в секунду) потребуется 10 секунд или свыше 100 дней. Для того, чтобы произвести расчёт за 10 мин, потребуется уже
* - ... * ' 10 * - * *
компьютер производительностью 1.7 TFlops (1.7 х 10 операций с плавающей точкой в секунду) [48].
Таким образом, поскольку для решения подобных задач существует спрос на вычислительные системы повышенной мощности, современный рынок
. 6 , .
предлагает суперкомпьютеры, отвечающие достаточно высоким требованиям. К ним относятся комплексы, собранные из специальных комплектующих, с использованием, как правило, векторных или матричных процессоров, позволяющих выполнять за 1 такт несколько операций^- а также специальные коммуникативные средства, дающие, в отличие от стандартных средств, гарантированную полосу пропускания для каждого подсоединенного к ним устройства. Такие специальные средства производят фирмы Cray research, IBM, Compaq, NEC и некоторые другие [5].
Логично сделать вывод, что основной задачей при создании суперкомпьютеров был девиз «производительность любой ценой». Специальные процессоры, дорогостоящая сверхбыстрая память, нестандартное периферийное оборудование - всё это приводит к увеличению стоимости таких систем в десятки и сотни раз.
Естественно, позволить себе купить суперкомпьютер может далеко не каждое предприятие,, которое занимается деятельностью, требующей * интенсивных расчетов.
Есть ли выход из этой ситуации?
Сейчас можно с уверенностью сказать: есть.
Из-за быстрого роста производительности персональных компьютеров и развития интрасетей, стало возможным создание высокопроизводительной вычислительной системы при помощи объединения ' в сеть существующих персональных компьютеров. Получаемая при этом вычислительная система -кластер - обладает многими преимуществами, главными из которых являются дешевизна, доступность, возможность постепенного расширения и модернизации.
Однако, при создании кластерной системы нужно сделать выбор: либо система обеспечивает повышенную надежность вычислений, любо дает увеличение производительности. Эти термины обычно исключают друг друга, т.е. повышение надежности всегда сопровождается увеличением кода программы, большими требованиями к памяти, вследствие дублирования
информации или хранения параметров для проверки корректности данных, дополнительными проверками и т.п. Все это, естественно, снижает быстродействие системы. Наоборот, если считать оборудование абсолютно надежным, то можно не учитывать возможность его отказа и работать без дополнительных проверок, кодирования и дублирования информации. Таким образом, некую абстрактную кластерную систему можно настроить либо на большее быстродействие, либо на большую надежность.
Многие существующие системы распределенных вычислений изначально настроены либо на одно, либо на другое.
Так, узким местом Beowulf-кластеров (Beowulf-технология организации параллельных вычислений на Linux-кластерах) [53,54] является головная машина-сервер. На ней хранится информация о структуре кластера и с нее осуществляется запуск параллельных программ, поэтому кластер не сможет работать в случае ее отказа.
Популярная' в настоящее время технология параллельного; программирования MPI (Message Passing Interface - Интерфейс передачи* сообщений) позволяет организовать распределенные вычисления в многомашинном комплексе на основе передачи сообщений. Данная технология: (в частности ее свободно-распространяемая версия MPICH (MPI CHameleon)) настроена на оптимальное быстродействие - в ней нет низкоуровневых средств слежения за отказами узлов, и неполадки с одним из них приводят к краху системы в целом и необходимости начинать вычисления с начала [49,50].
Кроме того, в вышеупомянутых системах практически не имеется средств смены конфигурации кластера во время вычислительного процесса, и они слабо ориентированы на гетерогенную сеть, состоящую из множества вычислительных узлов самых разных конфигураций - от персонального компьютера с процессором i486 до многопроцессорной стойки с процессорами Alpha. При написании MPI-программ для таких систем приходится прибегать к разного рода ухищрениям, учитывая разброс скоростных и архитектурных характеристик вычислительных узлов.
8 Этих "недостатков не имеют системы другого класса - метакомпьютеры
[51,52]. Это распределенные вычислительные системы, в которых нет
постоянного соединения между вычислительными узлами, и которые могут
динамически менять свою конфигурацию. Обычно в таких системах
вычислительному узлу передаются данные для расчета, и он «отключается» от
системы и решает свою задачу. После того, как данные готовы, он
подключается к головной машине, возвращает результат и берет следующую
порцию данных.
Налицо преимущества такой системы: возможность оптимального размещения задачи по вычислительным узлам разной архитектуры и различной мощности, возможность динамического подключения и отключения произвольного количества вычислительных узлов.
Недостаток метакомпьютерной системы - ориентированность на задачи, переборного и поискового типа, где вычислительные узлы не взаимодействуют друг с другом.
В настоящее время во всем мире идет активная работа по? совершенствованию теоретических и практических основ функционирования кластерных и метакомпьютерных систем, созданию оптимальных методов размещения задач в распределенной вычислительной системе и механизмов планирования вычислений и оптимизации вычислительного процесса. Это отражено в работах В.Воеводина, В л. Воеводина [4,33,55], В.Коваленко [34,42], А. Орлова, Л. Соколинского; Д. Смирного [44] в России, Г. Эндрюса [57], И. Фостера [51,52]; Ф. Хоффмана, Р. Вильямса [38,39] за пределами нашей страны.
Разработано множество средств планирования вычислительного процесса и управления заданиями в распределенных вычислительных системах, но ни одно из них, естественно, не является универсальным. Кроме того, основная масса исследований проводится в области глобальных метакомпьютерных систем с гигантским множеством пользователей и огромным количеством вычислительных узлов. При этом упор делается на эффективное обслуживание
9 потока заданий от множества, пользователей. И очень мало разработано
методик анализа вычислительного процесса в кластерно-метакомпьютерных
системах, которые не являются столь глобальными, как метакомпьютеры и
столь простыми, как кластеры, и соответственно, требуют к себе особого
подхода.
Например, в работах В.Коваленко, А. Орлова, Е. Хухлаева [34,42] (Институт прикладной математики имени М.В.Келдыша РАН, г. Москва) для управления заданиями в распределенной вычислительной среде предлагается идея метадиспетчера (или грид-диспетчера), который планирует размещение заданий в группах вычислительных узлов метакомпьютера в соответствии с требованиями каждого задания к ресурсам и с имеющимися ресурсами в узлах, при этом используется распределенная база данных, имеющая информацию о ресурсах. При этом, так как предполагается, что метадиспетчер имеет дело с большим количеством разнородных заданий, приходящих с разных направлений, большее внимание уделено определению очередности запуска и предсказанию моментов старта заданий в узлах, когда выполнение будет наиболее эффективно.
Такой подход не совсем обоснован для кластерно-метакомпьютерных^ систем, в которых множественный гетерогенный поток заявок как таковой отсутствует из-за централизованной структуры управления системой, но присутствует задача, которую необходимо распределить между вычислительными узлами таким образом, чтобы обеспечить минимальное время расчета. При этом должна учитываться разная производительность узлов и каналов связи между узлами и сервером (т.е. гетерогенность системы).
В работах Д. Смирного [44] (Институт математики и механики УрО РАН, г.Екатеринбург) предлагается решение задачи эффективного распределения процессов в многомашинном вычислительном комплексе путем решения оптимизационной задачи методом ветвей и границ. При этом учитываются пропускные способности каналов связи. Полученное улучшение за счет перераспределения процессов достигает 12%. Однако, недостатком такого
10 ' подхода является необходимость иметь историю вычислений программы для
каждого из процессов. Кроме того, в этих исследованиях не учитываются
характеристики надежности узлов и каналов связи.
В работах Н.П. Вашкевича, Б.Д. Шашкова и А.В.Антонова [58] (Пензенский государственный университет, г.Пенза) рассматриваются способы повышения эффективности параллельных и распределенных вычислений за счет переработки алгоритма параллельной программы с использованием моделей недетерминированных цифровых автоматов и теории марковских процессов. При этом рассматривается возможность анализа различных вариантов реализации алгоритма задачи по трудоемкости и выбора наиболее эффективного из них. Также предложен способ организации вычислительной системы, позволяющий осуществлять динамическую балансировку загрузки отдельных ее узлов за счет разделения программы на заведомо большое число? ветвей и асинхронного запуска параллельных процессов.
Однако, данный подход не учитывает пропускные способности каналов *
СВЯЗИ, ЧТО МОЖЄТ СНИЗИТЬ эффеКТИВНОСТЬ ПреДЛОЖеННЫХ МеТОДОВ. КрОМе TOrOjf-
не учитываются надёжностные характеристики элементов системы.
Целью данной диссертационной работы является разработка и совершенствование методов и алгоритмов повышения эффективности распределенных вычислений в'системах кластерно-метакомпьютерного типа.
Поставленная цель достигается решением следующих задач:
1. Анализ вариантов организации и особенностей кластерных и
метакомпьютерных вычислительных систем, исследование существующих
методов оптимизации размещения элементов.
Исследование скоростных и надежностных характеристик узлов и каналов связи распределенной вычислительной системы (РВС) и' разработка стратегии размещения узлов в РВС с учетом этих характеристик.
Создание' классификации стратегий размещения подзадач в РВС с обоснованиями применимостей каждой стратегии.
11 *
Разработка статической стратегии размещения подзадач в РВС с учетом скоростных и надежностных характеристик узлов и каналов связи.
Разработка динамической адаптивной стратегии размещения подзадач в системе для учета изменений состава системы в процессе решения задачи.
6. Создание программного обеспечения для реализации разработанной
стратегии размещения подзадач в реальных РВС.
Объектом исследования диссертационной работы является распределенная вычислительная система кластерно-метакомпьютерного типа.
Предметом исследования является структурная организация РВС, стратегии размещения узлов и подзадач для планирования и' управления вычислительным процессом в РВС.
Методы исследования основаны на положениях теории графов, теории вероятности, теории надежности и теории марковских процессов.
Научная новизна состоит в развитии научных основ и теоретическом анализе способов и методов организации и функционирования распределенных вычислительных систем.
В результате проведенных исследований достигнуто следующее:
Разработана стратегия размещения узлов РВС, реализуемаяша основе л поиска потокового центра графа и позволяющая повысить эффективность РВС за счет учета характеристик производительности и надежности узлов, входящих в систему.'
Предложена классификация стратегий размещения подзадач в РВС, которая позволяет выделить основные параметры, достоинства и недостатки каждой стратегии и области ее применимости.
3; Предложена расчетно-обменная характеристика задач, применение которой позволяет учесть соотношения объемов передаваемых на узлы данных и таким образом настроить РВС на определенный тип задач.
4. Разработана статическая стратегия размещения подзадач в РВС, отличающаяся тем, что она учитывает характеристики производительности и надежности узлов и каналов связи.
- 12 5. Разработана динамическая адаптивная стратегия размещения подзадач
в РВС, которая учитывает изменения характеристик системы, что позволяет
увеличить эффективность вычислений для РВС с ненадежными узлами.
Практическая ценность заключается в разработке новых способов эффективной организации структуры вычислительных систем и способов усовершенствования распределения подзадач в таких системах. Полученные результаты позволяют повысить эффективность распределенных вычислений.
Создано программное обеспечение для реализации вышеуказанных стратегий на реальной вычислительной системе.
Достоверность полученных результатов подтверждается
экспериментальными исследованиями и математическими расчетами.
Реализация и внедрение результатов работы. Диссертация является
теоретическим обобщением научно-исследовательских работ, выполненных
автором в Пензенском государственном университете: Данная диссертационная
работа проводилась по гранту для поддержки научно-исследовательской
работы аспирантов высших учебных заведений Министерства образования
России по теме «Высокопроизводительная вычислительная система
повышенной надежности с динамическим распределением ресурсов» шифр
АОЗ-3.16-349. Также результаты диссертации использовались для проведения
работ по гранту Министерства образования России по теме «Теория и методы
организации управления распределенными вычислительными процессами в
многопроцессорных вычислительных системах и метакомпьютерных сетях»
шифр Т02-03;3-2476. Результаты работы были использованы в рамках создания
«Регионального центра суперкомпьютерных вычислений и
телекоммуникационных баз данных коллективного пользования». Результаты диссертационной работы применялись при организации учебного процесса на кафедре Вычислительной техники Пензенского государственного университета. Также результаты диссертационной работы применялись в рамках проведения расчетов характеристик моделей сигналов радиоволновых
13 средств обнаружения в распределенной вычислительной системе для ФГУП
«НИКИРЭТ».
Апробация работы. Основные результаты работы докладывались и
обсуждались на международных и всероссийских научно-технических
конференциях и семинарах, в том числе:
на XII и XIII международных школах-семинарах «Синтез и сложность управляющих систем» (Пенза, октябрь 2000 и 2001гг)
на XIII научно-технической конференции студентов и профессорско-преподавательского состава Пензенского Государственного университета. (Пенза, 2002г.)
на V и VI Международных научно-технических конференциях «Новые информационные технологии и системы» (Пенза, 2002 и 2004гг).
на Международном юбилейном симпозиуме «Актуальные: проблемы науки и образования» (Пенза, 2003г).
на V и VI Всероссийских научно-практических молодежных конференциях «Антикризисное управление в России в современных условиях» (Москва, МГТУ им. Н.Э. Баумана, 2004г).
на 5-й Международной конференции и 1-м Международном форуме молодых ученых «Актуальные проблемы современной науки» (Самара, СамГТУ, 2004 и 2005гг.).
Работа автора по теме «Разработка оптимальной стратегии размещения узлов в распределенной вычислительной системе метакомпьютерного типа» получила Диплом в номинации лучшей научно-исследовательской работы на 5-й Международной конференции молодых ученых «Актуальные проблемы современной науки» (г. Самара, 2004 г).
Публикации. По теме диссертации опубликовано 16 печатных работ, в том числе 7 статей и 9 тезисов докладов.
Структура и объем работы. Данная диссертационная работа состоит из четырех глав, заключения и приложения.
. 14 В первой главе проводится обзор существующих классификаций
вычислительных систем, в частности распределенных вычислительных систем.
Анализируются варианты построения высокопроизводительных систем с
параллельной обработкой данных, производится анализ особенностей
кластерно-метакомпьютерных систем. Анализируются методы компоновки и
размещения, потенциально применимые для решения задачи эффективного
размещения узлов распределенной вычислительной системы в имеющейся сети.
Проводится анализ исследований эффективности планирования вычислений в
распределенных системах. На основании проведенного анализа формулируются
задачи дальнейшего исследования.
Во второй главе предлагаются модели, основанные на теории графов, теории вероятности и теории надежности, позволяющие повысить эффективность систем распределенных вычислений как на этапе проектирования структуры системы, так и на этапе деления задачи на параллельные подзадачи. Предлагаются возможные способы организации статического распределения подзадач для вычислительных узлов системы.
Третья глава посвящена разработке классификации стратегий и методов размещения подзадач в вычислительных узлах системы распределенных вычислений, исходя из которой осуществляется выбор того или иного метода для систем с определенными параметрами. На основе результатов, полученных в главе 2, и с учетом выработанной классификации разрабатывается динамическая адаптивная стратегия размещения узлов, учитывающая изменение структуры вычислительной системы во время процесса вычисления задачи. Для этого используются положения теории надежности и теории марковских процессов.
Четвертая глава посвящена разработке программного обеспечения для реализации предложенных во второй и третьей главах стратегий размещения подзадач, а также проверке полученных теоретических результатов на практике. В ней предложено описание разработанного программного комплекса системы управления заданиями, который позволяет осуществлять получение и
15 накопление статистических характеристик узлов системы распределенных
вычислений, рассчитывать характеристики надежности узлов, осуществлять
разбиение задачи на подзадачи в соответствии с полученными
характеристиками и на основе выработанных в главах 2 и 3 стратегий
размещения подзадач. Приводятся результаты замеров временных
характеристик работы системы.
Основные положения, выносимые на защиту:
1. Стратегия размещения узлов в РВС для поиска местоположения и
количества серверных узлов системы.
Расчетно-обменные характеристики задачи, решаемой в PBG.
Классификация стратегий размещения подзадач в РВС.
Статическая стратегия размещения подзадач на основе данных о производительности и надежности узлов и каналов связи.
Динамическая адаптивная стратегия размещения подзадач на основе имеющихся заранее или рассчитываемых динамически данных о надежности узлов.
Классификация архитектур многопроцессорных вычислительных систем
Понятие архитектуры высокопроизводительной системы является достаточно широким, поскольку под архитектурой можно понимать и способ параллельной обработки данных, используемый в системе, и организацию памяти, и топологию связи между процессорами, и способ исполнения системой вычислительных операций: Кроме того, при введении классификации ( можно преследовать самые разные цели. Классификация М. Флинна.
Самой ранней и наиболее известной является классификация, предложенная в 1966 г. М. Флинном [4,5]: В ее основу было положено понятие потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. Соответствующая; система классификации основана на рассмотрении числа потоков инструкций и потоков данных и описывает четыре архитектурных класса: - SISD - Single Instruction Single Data; - MISD - Multiple Instruction Single Data; - SIMD-Single Instruction Multiple Data; - MIMD = Multiple Instruction Multiple Data. SISD (single instruction stream /single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся последовательные компьютерные системы, которые имеют один центральный процессор, способный обрабатывать только один поток последовательно исполняемых инструкций. Для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка. Примерами компьютеров с архитектурой SISD является большинство обычных однопроцессорных рабочих станций.
MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Теоретически в этом типе машин множество инструкций должно выполняться над единственным потоком данных. До сих пор ни одной реальной машины, попадающей в данный класс, не было создано.
SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В системах подобного рода сохраняется один поток команд, включающий векторные команды, в которых единственная инструкция параллельно выполняется над многими элементами данных. К данному классу относят, например, компьютеры ILLIAC IV (обработка элементов вектора производится матрицей процессоров) и CRAY-1 (обработка элементов вектора производится с помощью конвейера).
MIMD (multiple instruction stream / multiple data stream) -множественный поток команд и множественный поток данных. Эти машины параллельно выполняют несколько потоков инструкций над различными потоками данных. В отличие от многопроцессорных SISD-машин команды и. данные связаны, потому что они представляют различные части одной и той же выполняемой задачи. Класс MIMD включает в себя очень широкий спектр многопроцессорных систем, примерами которых являются C.mmp, BBN Butterfly, CRAY T3D и многие другие.
Описанная классификация является самой широко распространенной и универсальной, однако, она не лишена недостатков, к которым относится, например, чрезмерная заполненность класса MIMD и то, что некоторые архитектуры, например, векторно-конвейерные компьютеры, четко не вписываются ни в один из классов. Классификация Флинна неоднократно дополнялась и расширялась для возможности описать нестандартные или сложные архитектуры. Некоторые из перечисленных ниже классификаций были предложены именно как дополнения классификации Флинна, некоторые являются самостоятельными исследованиями.
Классификация Р. Хокни
Пытаясь решить задачу более детальной классификации вычислительных машин класса MIMD, Р. Хокни предложил иерархическую структуру, показанную на рисунке 1.1.
Множественный поток данных может быть обработан либо одним конвейерным устройством, работающим в режиме разделения времени для разных потоков, либо каждый поток обрабатывается своим собственным устройством. Архитектуры, реализующие первую схему работы, входят в класс конвейерных. Архитектуры, работающие по второй схеме, в свою очередь делятся на два класса: переключаемые системы, в которых возможна прямая связь каждого компьютера с каждым, реализуемая с помощью переключателя, и сети, взаимодействие в которых возможно только с соседями, а с остальными узлами это взаимодействие осуществляется с помощью специальной системы маршрутизации [4];
Существует множество других классификаций, например, классификация Д.Скилликорна, Т.Фенга и т.д. Они уточняют в той или иной мере более ранние классификации или предлагают описать нетрадиционные архитектуры [4].
Часто основным признаком "классификации многопроцессорных вычислительных систем является наличие общей или распределенной оперативной памяти. В соответствии с данным признаком различают следующие классы аппаратных архитектур многопроцессорных вычислительных систем: SMP-архитектура, МРР-архитектура и NUMA архитектура [5]. SMP-архитектура (Symmetric Multiprocessing) предполагает, что система состоит из нескольких однородных процессоров и массива общей памяти (рисунок 1.2). Обычно процессоры подключаются к памяти с помощью общей шины. Каждый процессор имеет собственную кэш-память, когерентность кэшей процессоров поддерживается аппаратно. Обмен сообщениями в SMP системах организован через общую память, что существенно упрощает взаимодействие процессоров между собой. Примерами систем с SMP архитектурой являются SMP-серверы на базе процессоров Intel (IBM, Compaq, Dell).
Размещение подзадач в идеально надежной системе
Пытаясь аналитически описать работу системы, мы должны принять ряд допущений, касающихся характеристик узлов и линий связи (а, значит, весов вершин и дуг графа G).
Сначала найдем оптимальный способ размещения подзадач для системы, исходя из того, что РХі=ІиРаі=\, т.е. система является идеально надежной, и отказы оборудования отсутствуют. Также будем считать, что в общем случае производительность всех узлов разная, так же, как и пропускная способность линий связи: , х1 " хк ІаіФІа2Ф... Іат.
Мы будем рассматривать преимущественно вычислительные узлы, и, чтобы избежать излишнего загромождения формул, договоримся называть 7-м узлом некоторый і-и. вычислительный узел из общего количества п вычислительных узлов. На рисунке 2.2 узлы пронумерованы числами, изображенными внутри вершин. Также /-й путь представляет собой путь до /-го вычислительного узла от серверного узла, осуществляющего выдачу ему подзадачи. На графе G этот путь будет являться дугой или цепью из дуг, соединяющих узел из множества Xs и узел из множества Хс и, возможно, проходящих через промежуточные узлы. Следует помнить, что в соответствии со стратегией размещения узлов каждому серверному узлу может быть приписана группа вычислительных узлов, которые работают только с ним (до тех пор, пока он существует), и соответственно, рассматривается путь от этого серверного узла до вычислительного, узла из его группы. Например, для графа на рисунке 2.2 путь, соответствующий 10-му узлу, будет включать следующие дуги (при условии, что этот узел включен в группу серверного узла х3):
Введем некоторые обозначения. Пусть ta = —— время обработки некоторой единицы информации в узле х, (приведенное время расчета, зависящее только от производительности узла), tTj= время передачи единицы информации по 7-му каналу (также приведенное время, зависящее от производительности канала связи).
Очевидно, данные времена являются приведенными временами, которые никак не характеризуют конкретную задачу, а характеризуют узлы и каналы.
Производительность коммуникационных сетей в любых кластерных системах характеризуется множеством параметров, основными из которых являются два: пропускная способность и латентность [4].
Пропускная способность - это количество информации, передаваемой между узлами сети в единицу времени. Как мы договорились, пропускные способности линий связи между узлами могут быть различными, соответственно, общая пропускная способность і-го канала между парой узлов (Xj, ху) будет равна: I„=I(x„Xj)= mm[I(xmxk)], (2.16) т.е. будет определяться линией связи с минимальной пропускной способностью на пути (/, j) от узла хг до узла х}.
Латентность - это время начальной задержки при посылке сообщения (время, затрачиваемое программным обеспечением и устройствами сети на: подготовку к передаче информации по данному каналу). Иногда считается, что это просто время передачи сообщения нулевой длины.
Если учитывать возможность деления задачи на подзадачи небольшого объема, при этом возникает необходимость учета латентности из-за того, что она гораздо сильнее влияет на процесс передачи именно небольших сообщений. Поэтому введем в рассмотрение параметр tLi - латентность, или время передачи нулевого пакета данных (с учетом передачи служебной информации) по каналу связи. Итак, будем считать, что задача для решения представляет собой некоторый объем данных S0, который необходимо разделить между вычислительными узлами: S0 = Sl+S2+S3+... + Su.. (2.17) В соответствии с приведенной ранее классификацией каждая /-я подзадача представляет собой следующую совокупность объемов данных: 5, = (..}.. (2.18) где: SCJ - объем данных для расчета на вычислительном узле. Этот параметр определяет сложность (время) расчета; SSj - объем данных для передачи на вычислительный узел. Этот параметр определяет время передачи исходных данных j -й подзадачи узлу; SRJ - объем данных для передачи от вычислительного узла (результат).
Этот параметр определяет время передачи результата решения j-к подзадачи от вычислительного узла. В общем случае т.е. объем передаваемых данных не всегда определяет сложность подзадачи, и, соответственно, время ее решения на вычислительном узле. Так же, объем возвращаемых данных может не зависеть от объема исходных данных. Для каждой решаемой задачи соотношение этих трех параметров может быть различным. Введем термин «обобщенный объем подзадачи»: Sj=SCJ+SSj+SRJ, (2.19) и выразим значения каждого из трех вышерассмотренных объемов через этот обобщенный объем: Sq =kc Sj SSJ=ks-Sj, (2.20) Соотношения коэффициентов будут характеризовать тип задачи, решаемой в системе. Условимся, что в сумме эти значения будут равны единице: kc + ks+kR=l. (2.21)
Конкретные числовые значения коэффициентов задаются для каждой задачи эмпирически, исходя из анализа алгоритма и анализа объемов массивов, передаваемых в расчетную функцию, выполняющуюся на вычислительных узлах, и возвращаемых из нее. При этом следует помнить, что больший объем данных не всегда определяет большее время на обработку. Для корректировки этих параметров возможен замер времен передачи, расчета и приема данных в конкретной РВСКМТ и последующий расчет соотношений этих трех времен.
Метод равномерного размещения в реальных системах (системах с отказами узлов)
Данный метод предполагает разбиение всей задачи делением на равные по объему подзадачи. Однако, в отличие от вышерассмотренного метода, объем подзадач определяется не только с точки зрения уменьшения времени, затраченного на передачу блоков данных по сети, но и с учетом характеристик надежности узлов (времени наработки на отказ и времени восстановления). щ, Основная задача при выработке данного метода, как было сказано в главе 2, заключается в том, чтобы с учетом характеристик надежности каждого узла определить, насколько можно увеличить размер блока данных, чтобы обеспечить минимальную совокупную латентность при сохранении высокой отказоустойчивости.
Этот метод является усовершенствованием предыдущего, и также является достаточно простым для реализации.
Данный метод целесообразно применять в следующих случаях. 1. Если сервер нецелесообразно нагружать сложными алгоритмами планирования вычислений. 2. Если узлы, входящие в РВСКМТ, достаточно разнородны по своей надежности, и имеется статистически полученная характеристика надежности этих узлов. 3. Если задача решается достаточно длительное время.
Ф Достоинствами этого метода размещения подзадач, по сравнению с предыдущим, является учет характеристик надежности узлов, а значит, выдача узлам такого количества данных, которое они способны обработать за время своей безотказной работы.
Недостаток также очевиден - так как учет ведется по самому отказонеустоичивому узлу, а деление является равномерным, то размер каждой подзадачи будет в общем случае меньше, чем при простом равномерном делении, а значит, потери на служебную информацию при обмене данными по сети будут выше.
Этот метод предполагает разбиение всей задачи на подзадачи разного размера (в общем случае) с привязкой к вычислительным узлам. Для применения данного метода необходимо знать некоторые характеристики узлов и каналов связи до них от сервера. При этом деление осуществляется исходя из производительностей узлов и каналов связи. Мощные узлы (Pentium 4, AMD Athlon) с быстрыми каналами связи (Fast Ethernet, Gigabit Ethernet); получают большие блоки; слабые узлы, либо подключенные 10-мегабитным Ethernet или даже модемными линиями, получают меньшие блоки.
Очевидно, что данный метод предполагает на этапе распределения задачи некоторый усложненный процесс принятия решений. Например, предложенная в главе 2 стратегия размещения данного класса нуждается в решении системы линейных уравнений порядка N, где N - число вычислительных узлов РВСКМТ (которое может достигать нескольких сотен и даже тысяч!).
Поэтому данный метод целесообразно применять в следующих случаях. 1. Если имеется возможность некоторое время перед началом расчета затратить на работу алгоритма разбиения. 2. Если узлы, входящие в РВСКМТ, сильно разнородны по своей производительности, а каналы связи от этих узлов до серверов - по своей пропускной способности и латентности. 3. Если отсутствуют статистические данные о надежности узлов, или эта надежность достаточно высока. Достоинства такого метода размещения подзадач вытекают из учета производительности узлов и каналов связи. При размещении подзадач каждый узел получает ровно столько данных для расчета, сколько он может обработать с учетом того, чтобы закончить расчет одновременно со всеми остальными узлами и избавить РВСКМТ от простоев. Недостаток метода - отсутствие учета отказов, а также необходимость применения некоторых усложненных методик разбиения, что увеличивает нагрузку на серверные узлы и усложняет алгоритм функционирования серверов.
Модуль сбора статистики для системы распределенных вычислений
Поэтому помимо рассмотренных методов динамического адаптивного размещения подзадач с учетом статистики существует необходимость разработки такого метода, который не была бы жестко привязан к наличию статистической информации о надежности узлов.
Анализ процесса функционирования узлов в РВСКМТ показал, что такой метод может быть получен с использованием теории марковских случайных процессов.
Одним из определений марковского процесса является следующее утверждение: при фиксированном состоянии процесса в настоящий момент времени будущее и прошлое состояния марковского процесса независимы [14]..
Или, можно сказать, что случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятность любого состояния системы при t t0 зависит только от ее состояния при t = t0 и не зависит от того, как и когда система пришла в это состояние.
В нашем случае, как показано на рисунке 2.8, процесс функционирования каждого вычислительного узла представляет собой чередование двух состояний (работы и восстановления), причем состояние, в которое узел перейдет в определенный момент, зависит только от того, в каком состоянии он находился до перехода (состояния чередуются), и не зависит от более ранних состояний узла.
Таким образом, мы можем рассматривать процесс функционирования каждого вычислительного узла системы как дискретный марковский процесс с двумя состояниями. Воспользуемся положениями теории марковских процессов для того, чтобы из выражений определения вероятностей перехода процесса в состояния работы и восстановления определить время работы узла в каждом состоянии и, в конечном итоге, вычислить объемы подзадач для каждого узла.
В [14] приведена последовательность действий для определения вероятностей переходов для дискретного марковского процесса с двумя состояниями. Воспользуемся некоторыми положениями этой последовательности и разработаем свой способ определения необходимых нам значений времени в условиях особенностей нашей РВСКМТ.
Процесс (/) в любой момент времени может иметь лишь одно из значений = 1 (работа) и v2 = 0 (восстановление), причем вероятность перехода у, - v2 (отказ узла) за малое время At равна AAt, а вероятность перехода v2- v1 (возврат узла к работе) равна /Лі. Известны вероятности начального состояния р, = 1, р2 = 0.
В соответствии с [14], имея эти исходные данные, можно определить вероятность перехода 7riJ(t0,t) = P{@(t) = vJ\(tQ)-vi}, где vr=l, v2=0, /,./ = 1,2.
В общем случае имеет место система линейных дифференциальных уравнений, полученных из уравнения Колмогорова-Чепмена: ; Д ) = Е« (0 і( о»0. ,7 = 1,2, (3.2) 01 к=\ где ац- крутизна изменения вероятности на небольшом отрезке времени [14].
Для того чтобы применительно к реальным условиям иметь возможность решить эту систему уравнений, необходимо некоторое упрощение, в качестве которого и приняты ранее указанные соотношения а12 = Л, a2l-/j, (3.3) и из условий нормировки [14]: ап=-Л,а22 = -/г. (3.4)
Это значит, что на достаточно небольшом отрезке времени график функции надежности узла можно аппроксимировать линейной функцией. Если рассмотреть графики, построенные по статистически полученным данным (глава 4), то можно высказать следующее предположение. Так как нас интересует время безотказной работы каждого узла, мы рассматриваем только вероятности безотказной работы каждого узла, близкие к единице, и, соответственно, можно рассматривать только участки графика надежности, находящиеся выше определенного порога вероятности. Действительно, при выборе приемлемого уровня надежности вряд ли будет выбрано значение вероятности безотказной работы, скажем, Pw = 0.4. Можно предположить, что при развертывании РВСКМТ мы ожидаем, что задача будет решена с вероятностью как минимум 7 = 0.8. А на этих участках график функции надежности, как показывает практика, хорошо аппроксимируется линейной функцией (график на рисунке 3.6 построен по статистическим данным, полученным программами NS Logger и NS Analyzer, рассматриваемым в главе 4).
