Sergey Golub

Министерство образования и науки Украины

Донецкий национальный технический университет

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

Тема: "Динамическая балансировка загрузки процессоров в многопроцессорных системах."

Руководитель: профессор, д.т.н. Фельдман Л.П.

Магистерская работа посвящена исследованию методов динамической балансировки загрузки процессоров в многопроцессорных системах. Научный руководитель - Фельдман Лев Петрович. На кафедре данное направление является новым, актуальным и интересным. Актуальность состоит в следующем: т.к. происходит стремительное увеличение числа многопроцессорных систем, которые применяются для решения широкого спектра задач, необходимы новые, эффективные методы управления этими системами.

АВТОРЕФЕРАТ

СОДЕРЖАНИЕ

Аннотация
Общая характеристика работы
Основной смысл работы
Выводы
Библиографические ссылки

АННОТАЦИЯ

Целью магистерской работы является исследование методов динамической балансировки загрузки процессоров в многопроцессорных системах и разработка собственного алгоритма, решаюшего данную задачу.
В магистерской работе присутствуют следующие этапы:
1. Обзор существующих многопроцессорных систем.
2. Обзор существующих алгоритмов решения задачи.
3. Сравнительный анализ существующих алгоритмов решения задачи.
Автор защищает следующие положения и результаты:
- Модель многопроцессорной системы.
- Реализацию алгоритма динамической балансировки.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Проблема динамической балансировки загрузки процессоров в вычислительных сетях является одной из наиболее актуальных проблем компьютерной науки с разнообразными постановками задачи.

Методы исследований. В работе используется теория алгоритмов, теория массового обслуживания.

Научная новизна работы состоит в разработке модели многопроцессорной системы для решения задачи динамической балансировки загрузки.

Практическая ценность работы состоит в разработке нового алгоритма динамической балансировки.

Реализация результатов работы. Практическим результатом данной работы является программный модуль, содержащий модель многопроцессорной системы.

Структура работы. Магистерская работа состоит из введения, трех глав, заключительной части, перечня ссылок и приложений.

Во введении формулируются тенденции развития многопроцессорных вычислительных систем и методов их эффективного использования.

В первой главе рассматриваются архитектурные особенности и топологические особенности вычислительных сетей, математическая постановка задачи, определяются задачи исследования.

Во второй главе рассматриваются основные алгоритмы решения данной задачи

В третьей главе представлена модель многопроцессорной системы, сравнительный анализ эффективности алгоритмов решения задачи.

В заключении анализируются результаты проделанной работы, ее возможности и практическая ценность.

В приложении приведен листинг программных модулей

ОСНОВНОЙ СМЫСЛ РАБОТЫ

Первая глава представляет собой обзор существующих топологий вычислительных систем.

Во второй главе рассмотрены наиболее известные алгоритмы решения задачи: алгоритм Грэхэма и алгоритм Бартала.

Алгоритм Грэхэма
Основан на назначении нового задания, поступающего в вычислительную сеть, на ту машину сети, которая в данный момент является наименее загруженной. Коэффициент эффективности этого алгоритма определяется соотношением 2 -1/m. Основным недостатком данного подхода является неспособность распознавать следующую ситуацию: при поступлении m небольших по трудоемкости заданий и следом одного задания, трудоемкость которого намного больше трудоемкости предыдущих, результат является неоптимальным.

Алгоритма Бартала - Фиата - Карлоффа - Вохры.
Идея этого подхода состоит в следующем: предпринимается попытка держать около 44,5% машин "слегка" загруженными. Это означает, что все машины делятся на две группы. В первую группу распределяются задания с небольшой трудоемкостью, а вторая группа предназначена для обработки "больших" заданий. Алгоритм определен для m > m0, m0 определяется позднее. Алгоритм имеет коэффициент эффективности (2 - e), где e = 1/ m0. Вводится дополнительный параметр d О (0,1) (зависящий от m), причем dm должно быть целым.
Основные определения
Высота машины - сумма трудоемкостей всех работ, которые будут выполняться на этой машине. Каждый раз алгоритм будет строить список машин, отсортированный в порядке неубывания по высоте. Пусть F_i - это последовательность первых dm машин и их высот; после того, как i заданий были распределены. L_i - последовательность оставшихся m - dm машин и их высот. A_i и M_i - обозначают среднюю и минимальную высоту (по всем m машинам), когда i заданий были распределены. P - последовательность высот машин. A(P) - средняя высота в P. M(P) - минимальная высота в P. Алгоритм: Когда приходит i + 1 задание с трудоемкостью a_i+1, оно распределяется на первую возможную машину из L_i, если: M(L_i) + a_i+1 Ј (2 - e) A(F0)

Третья глава
Дискретная модель многопроцессорной вычислительной системы для имитации работы алгоритмов балансировки.
Параметры модели: m - число машин в вычислительной сети. h_m - высота каждой машины. h_lim - предельная высота каждой машины.ы а - размер поступающего задания. t - величина такта времени, через которое поступают задания. Модель функционирует, используя онлайн версию задачи балансировки.
Схема модулей модели

Назначение модулей модели

Модуль задания - модель задания, поступающего в вычислительную сеть.
Модуль процессора - модель процессора (машины) для обработки задания.
Модуль управления - модель вычислительной системы в целом.
Модуль визуализации - модуль для наглядного отображения процессов поступления задания, его распределения и выполнения.

ВЫВОДЫ

В магистерской работе проведено исследование алгоритмов динамической балансировки в многопроцессорных системах. В процессе исследования были получены следующие основные результаты:

1. Разработана модель многопроцессорной системы для решения данной задачи.
2. Сравнительный анализ существующих алгоритмов балансировки.

БИБЛИОГРАФИЧЕСКИЕ ССЫЛКИ

На главную