Моделирование и оценка эффективности планирования независимых заданий в распределенной вычислительной среде

• Автор: Паньшенсков, Михаил Алексеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 123 с. : ил.

Содержание

Глава 1. Введение

1.1. Задача планирования.

1.2. Распределенная вычислительная среда.

1.3. Планирование вычислений в распределенной среде

1.4. Модель

1.5. Описание диссертационной работы.

Глава 2. Методы оценки эффективности.

2.1. Оптимальный план в среде без задержек на соединение

2.2. Относительная эффективность плана в среде с задержками на коммуникацию.

2.3. Эффективность по ресурсам при вычислении на одном кластере

2.4. Относительное ускорение при удвоении вычислительной мощности
2.5. Относительное ускорение при горизонтальном масштабировании
Глава 3. Практическая иллюстрация методов.
3.1. Система АРСО
3.2. Эксперимент по проверке оптимальности плана для задачи поиска простых чисел в системе АРСО
3.3. Оценка эффективности некоторого плана по решению вычислительной задачи проверки простоты чисел.
3.4. Эффективность планов вычислений на одном кластере
3.5. Относительная эффективность масштабирования.
3.6. Сравнение методов оценивания пропускной способности каналов данных в распределенной вычислительной среде
Заключение.
Список используемых источников


Задача планирования вычислений в распределенной вычислительной среде [] является задачей теории расписаний, где в качестве целевой функции выбрана некоторая функция наиболее соответствующая целям задачи планирования, свойствам распределенной вычислительной среды и типам вычислительных заданий. Среди целевых функций задачи планирования называют: среднее время нахождения заданий в системе, величину эффективности системы, среднее время ожидания заданий в очереди, показатель равномерности распределения заданий по вычислителям. Множество планов X содержат все возможные планы выполнения заданий с учетом ограничений ресурсов среды (процессоров, памяти, каналов связи). Параметры ресурсов среды могут быть оценены специальными методами [6]. В классической формулировке задача планирования вычислений является трудноразрешимой, или NP-трудной [9], поэтому на данный момент уже придумано множество быстроработаюших эвристических алгоритмов [][1, 2] для се решения. В редких случаях, как в случае с СЛк++ [, ], авторы предлагают приближенные алгоритмы с гарантированной теоретической оценкой качества составляемого плана вычислений. В диссертационной работе рассматриваются приближенные алгоритмы, для которых делается теоретическая оценка качества плана и практическое сравнение с другими алгоритмами планирования. Задача планирования вычислений представляется в виде классической задачи дискретной оптимизации [5, 8]. Для параллельной среды [6] такой задачей является поиск экстремума некоторой целевой функции (например, времени исполнения) при условии соблюдения ограничений связанных с имеющимися ресурсами среды (процессорами, памятью, каналами связи) — их параметры могут быть оценены специальными методами [7]. Решение такой задачи позволяет использовать имеющиеся ресурсы наиболее эффективно, позволяя получить минимальное время исполнения заданий, максимальную загружен ность ресурсов, минимальный расход электроэнергии в час, и т. Впрочем, в общем случае, задачу оптимального планирования вычислений относят к классу трудноразрешимых, также известных как ЫР-трудных []. Поэтому придумано множество быстроработаюших эвристических алгоритмов [8, , ]. Такие алгоритмы зачастую решают задачу планирования неоптимально и не гарантируют качества результата. Поэтому, чтобы продемонстрировать эффективность эвристических алгоритмов, многие авторы реализуют их на реальных системах и показывают их эффективность на практических данных [, ][ 1, 3]. Другим классом алгоритмов решающих поставленную задачу являются приближенные алгоритмы [][2]. Последние работают за полиномиальное время, но также гарантируют результат качества предоставляемого плана. Опишем математическую модель распределенной вычислительной среды. В литературе встречается множество различных моделей. В данной диссертационной работе используется модель основанная на терминологии из публикаций Вл. В. Воеводина [], A. C. Хританкова [, , -], Charles Е. Leiscrson и Wen Jing Hsu [, ]. Распределенная вычислительная среда представляет собой набор вычислительных узлов, объединенных между собой в односвязную сеть с единой целью решения вычислительных задач. Такая сеть может иметь разнообразную структуру, называемую топологией сети. Наиболее известными физическими сетевыми топологиями являются [, ]: шина, звезда, кольцо, дерево и полносвязная топология. В данной работе рассматривается наиболее используемая в современной практике физическая топология «звезда» и соответственно ее производная топология «дерево». Кластер — группа вычислительных узлов с общим родительским узлом (в топологии «дерево») представляющих с точки зрения пользователя единый вычислительный ресурс. Для решения вычислительной задачи группа вычислительных узлов, принадлежащих одному кластеру, работает по одному расписанию. Кластеры могут объединяться в двухуровневую вычислительную сеть. Некоторые авторы [] также называют такую сеть двухуровневым Гри-дом. Двухуровневые вычислительные сети могут объединяться в трехуровневую вычислительную сеть, и т. В диссертационной работе рассматриваются одноуровневые и двухуровневые вычислительные сети.