Исследование методов организации и выполнения параллельных вычислений в сети Смирнов Александр Николаевич

Содержание к диссертации

Содержание 2

Сокращении и условные обозначения 6

Введение 10

Глава 1, Анализ типовых технологий решения задач в сети 14

1. Введение

2. Parallel Virtual Machine (PVM) 17

3. Dynamite 19

4. Application Data Movement (ADM) 20

L5 Condor 23

1.6 Piranha 25

1.7NetSolve 27

8. Sun Grid Engine Enterprise Edilion 29

9. Pipelined Network Computing 34

10. Distributed Shell Tools System 36

11. Выводы по главе 38

Глава 2 Технология решения переборных задач в сети 40

2Л Введение

2.2 Обобщенная структура программы 43

2.2.1 Процесс решения переборной задачи в сети ...

3. Специфика сетевых вычислений 46

4. Метод декларативного описания задачи 48

1. Определение списка имен доступных компьютеров 49

2. Описание метода и параметров решения

3. Описание способа получения переборных последовательностей 52

4. Описание формата решающей функции

ті способа получения результата 55

5. Решающая функция 58

6. Декомпозиция задач переборного класса.

Формальная постановка задачи 59

1. Генерация переборных последовательностей, получаемых сочетанием без повторяющихся элементов с длиной получаемых последовательностей от 1 до п 60

2. Генерация переборных последовательностей, получаемых сочетанием без повторяющихся элементов

с определенной длиной получаемых последовательностей,.. 62
2.63 Генерация переборных последовательностей,
получаемых перестановками без повторяющихся элементов
с определенной длиной получаемых последовательностей.„ 64
2.6.4 Особенности генерации переборных
последовательностей, получаемых размещением и
переборных последовательностей с повторяющимися
элементами 65

7. Подготовка вычислений. Административный этап реализации... 67

8. Выводы по главе 70

Глава 3 Разработка динамических методов распределения нагрузки--- 71

ЗЛ Введение.

2. Статический метод 72

3. Динамический адаптивный метод 73

3.3Л Алгоритм работы адаптивного метода 76

3.3.2 Определения размера подзадачи

для адаптивного метода 79

3.4 Динамический директивный метод 81

1. Алгоритм работы директивного метода 82

2. Описание коэффициентов и параметров

директивного метода 84

3.4.3 Решение проблемы рассогласования нагрузки

для директивного метода , , 86

3.4.4 Определение базового размера подзадачи

для директивного метода 87

3.4.5 Расчет длительности импульса нагрузки достаточного

для изменения производительности компьютера 89

5. Отказоустойчивость координатора и рабочего процесса 90

6. Экспериментальная проверка динамических методов

и технологии решения переборных задач в сети 92

1. Условия постановки экспериментов и методика оценки эффективности вычислений

2. Сравнение времени решения задачи на нескольких компьютерах по сравнению с одним для различных

методов распределения нагрузки 94

3.6.3 Сравнение работы различных методов

распределения нагрузки при появлении фоновых процессов 97

4. Определение размера подзадачи для адаптивного метода, обеспечивающего минимальное время решения задачи 100

5. Влияние коэффициента мощности на работу директивного метода распределения нагрузки,, 102

6. Влияние коэффициента приращения на работу директивного метода распределения нагрузки 105

7. Определение влияния коэффициента инертности на работу директивного метода распределения нагрузки.... 107

3.7 Выводы по главе 110

Глава 4. Конвейер сетевых вычислений 111

1. Введение

2. Обобщенная структура программы 114

3. Особенности декларативного метода описания задачи

для сетевого конвейера 116

4. Решающая функция 117

5. Условия целесообразности использования конвейера в сети-,. 121

6. Конфигурирование сетевого конвейера 123

4.6Л Алгоритм конфигурирования конвейера 125

4.6,2 Некоторые особенности реконфигурирования

сетевого конвейера 129

7. Особенности тактирования сетевого конвейера

8. Особенности диспетчеризации сетевого конвейера 130

4.9 Алгоритм работы координатора , - 133

4.10 Формальная постановка задачи

с использованием сетей Петри 135

4.11 Реализация работы конвейера для задачи

фильтрации изображений 136

4.11Л Сравнение времени решения задачи на одном компьютере и конвейере в зависимости от количества ступеней конвейера 137 4Л1.2 Зависимость времени решения задачи на конвейере от

трудоемкости операций, выполняемых конвейером 138

4,11.3 Реконфигурирование конвейера путем замены

компьютера на ступени с низкой производительностью... 139

4.12 Выводы по главе 140

Заключение 142

Список литературы 143

Приложение 1 Пользовательский интерфейс генерации

файла о писаниц задачи 151

Приложение 2 Генерация переборной последовательности

определенной длинны, получаемая сочетанием 154

Приложение 3 Генерация переборной последовательности

определенной длинны, получаемая перестановками 156

Сокращения и условные обозначения

API Application Program Interface (Интерфейс прикладного программирования)

PVM Parallel Virtual Machine (Параллельная виртуальная машина)

VM Virtual Machine (Виртуальная машина)

TID Task Identifier (Идентификатор задачи)

MPI Message Passing Interface (Интерфейс передачи сообщений)

RMI Remote Method Invocation (Вызов удаленных методов)

CORBA Common Object Request Broker Architecture (Обобщенная архитектура

брокеров объектных запросов)

ADM Application Data Movement (Приложения перемещения данных)

NOW Network Of Workstation (Сеть рабочих станций)

DSHTS Distributed Shell Tools System (Инструменты системы распределенной

оболочки)

TID Task Identifier (Идентификатор задачи)

IPC Interprocess Communication (Взаимодействие процессов)

TCP Transmission Control Protocol (Протокол управления передачей)

IP Internet Protocol (Протокол Интернет)

NS Name Service (Сервис имен)

DNS Domain Name Service (Сервис доменных имен )

RSH Remolc Shell (Удаленная оболочка)

VHSI Very High Speed Internetwork (Высокоскоростное сетевое взаимодействие)

А множество допустимых символов (алфавит)

п мощность множества А т.е. количество допустимых символов

а кортеж над множеством А. Представляет некоторое слово, т.е. набор

упорядоченных символов из алфавита^.

к длина кортежа а т.е. количество символов в одном слове

М множество всевозможных слов

т мощность множества Мт.с. количество всевозможных слов

f} кортеж над множеством М Представляет набор упорядоченных в

лексикографическом порядке слов из множества М

С* сочетание из п по к

А * размещение из п по к

Р_п перестановка (размещение из п по п)

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

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

компьютера
tj Время решения задачи

pi Производительность і-го компьютера, измеряемая в количестве

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

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

времени
і] Обозначение коэффициента пропорциональности для І-го компьютера

sizen, размер подзадачи, измеряемой в количестве переборных

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

(определяющее величину рассогласования нагрузки)
N_b[art номер переборной последовательности, определяющий начало подзадачи

N_s[op номер переборной последовательности, определяющий конец подзадачи

t_lip время, затраченное на накладные расходы всеми компьютерами

t_lip j время, затраченное на накладные расходы і-м компьютером

Ііф_і среднее время накладных расходов, которое затрачивается на

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

когда первый компьютер завершает вычисления
t_nL«u время, затраченное непосредственно на вычисления.

size_reil| текущий размер подзадачи для директивного метода распределения

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

нагрузки

size_olher размер оставшейся части задачи

Хгещ размер оставшейся не решенной части задачи

Pncw текущая производительность компьютера

size_max Ограничение максимального размера подзадачи для директивного метода

распределения нагрузки
kpower коэффициент, отражающий текущую производительность компьютера
kj_nc коэффициент приращения

kineri коэффициент инертности

tj_Dad определяет величину рассогласования нагрузки для директивного метода

распределения нагрузки
tj время работы 1-го компьютера над своей подзадачей

size_[CUn реальный размер подзадачи для і-го компьютера в директивном методе

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

задачи
р_ср среднее значение производительности компьютеров

tsiow время работы самого медленного компьютера над подзадачей базового

размера
inew время решения подзадачи при воздействии импульса нагрузки

t_t время решения одной подзадачи без воздействия импульса нагрузки

т_ин время воздействия импульса нагрузки

р_пе№ значение реальной производительности компьютера при воздействии

импульса нагрузки
FI параметр, определяющий допустимое изменение производительности

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

постоянной
^скоив время работы конвейера

^посл времени последовательной обработки

Передачи время, затрачиваемое на передачу информации по сети
Обработан время, затрачиваемое на обработку объектов
tnepi время передачи одного объекта по сети

t₀6pi время обработки одного объекта

ti время работы і-й ступени конвейера

t_Py_[hl разность во времени работы всех ступеней

Won время работы самой медленной ступени на данном шаге вычислений

^ыор время работы самой быстрой ступени на данном шаге вычислений

tmyrepb совокупные потери от простоев компьютеров

fi трудоемкость функции і-й ступени конвейера

Vj Обозначение производительности j-ro компьютера при расчете конвейера

V_rccdj значение производительности ї-го компьютера, при достижении которой

W,=o

V_itjm совокупная общая производительность всех доступных компьютеров

f_min наименьшая трудоемкость из всех операций

V_reaij Производительность і-й ступени конвейера

Введение к работе

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

Быстрое развитие вычислительной техники и сетевых средств в последнее время привело к увеличению потенциальной вычислительной мощности сосредоточенной в компьютерных сетях. Следовательно, все большее количество вычислителыюемких задач можно решать за приемлемое время с использованием компьютерной сети. А с точки зрения стоимости вычислений, а так же возможностям масштабирования, бесспорно предпочтительнее использование сетей.

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

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

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

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

Поставленная цель достигается решением следующих задач: исследовать способы снижения трудоемкости написания параллельных программ для сети и определить критерии рационального использования ресурсов сети; - для переборного класса задач разработать метод декомпозиции этих задач, который позволит делить решаемую задачу на любое количество независимых частей, размеры которых могут соотноситься в любой пропорции; разработать динамические методы распределения нагрузки, которые смогут распределять нагрузку на вычислительные узлы в сети таким образом, чтобы обеспечить рациональное использование вычислительных ресурсов с учетом непредсказуемых изменений в сети во время вычисления;

разработать декларативный метод описания задачи, предназначенный для постановки задачи, выбора метода ее решения и способа формирования результата;

на основе предложенных методов описания и декомпозиции задачи, а так же методов распределения нагрузки разработать технологию для решения задач в сети на примере переборных задач;

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

разработать пакет программ, реализующий предложенную технологию для решения переборных задач в локальной сети и экспериментально проверить полученные результаты;

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

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

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

Научная новизна результатов, полученных автором, заключается в следующем:

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

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

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

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

1. Предложенная технология позволяет уменьшить трудоемкость написания параллельных программ при решении задач в сетевой среде.

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

3. Разработан пакет программ, реализующий разработанную технологию

решения задач в среде PVM на примере решения переборных задач. А. Разработан и программно реализован конвейер вычислений в среде PVM

для задачи фильтрации изображений. Апробация работы. Основные положения работы докладывались на следующих конференциях:

Научно-технические конференции профессорско-преподавательского состава СПбГЭТУ, 2001-2002Г.

Международной научно-технической конференции по мягким вычислениям SCM, 2002г., Санкт-Петербург.

Публикации. По теме диссертации опубликовано 4 печатные работы, из них 2 статьи, 1 депонированная рукопись и тезисы к одному докладу на международной научно-технической конференции.

Похожие диссертации на Исследование методов организации и выполнения параллельных вычислений в сети

Исследование и разработка методов организации выполнения и физической оптимизации запросов к XML-даннымФомичев Андрей Владимирович

Разработка и исследование методов преобразования прикладных семантических сетей в базы правилСамсонов, Владимир Викторович

Методы и средства исследования производительности сетей, использующих технологию передачи Wormhole Веселов Николай Александрович

Разработка и исследование методов оптимизации передачи информации в вычислительных сетях путемдинамического регулирования загрузкиКосых, Валерий Семенович

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

Разработка и исследование методов синтеза параллельных алгоритмов для многопроцессорных систем со структурно-процедурной организацией вычислений Пономарев Игорь Михайлович

Математическое и программное обеспечение массивно-параллельных вычислений в распределенных системах на базе аппарата нейронных сетей Калинин Александр Викторович

Разработка и исследование модели функционирования глобальной сети для анализа динамики распространения вредоносного программного обеспеченияАнтоненко Виталий Александрович

Исследование математических моделей и разработка сети связи, управляемой адаптивным протоколом случайного множественного доступаКузнецов Дмитрий Юрьевич

Разработка и исследование математических моделей агрегирования и расщепления трафика звездообразного фрагмента сетиМихеев, Павел Андреевич