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

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

Содержание
Содержание

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

Введение

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

1.1 Введение

1.2 Vi i V.
1.3 i.
1.4 ii v
1.5
1.6 i
1.7v
1.8 i i i ii.
1.9 ii i
1. ii
1. Выводы по главе.
Глава 2 Технология решения переборных задач в сети
2.1 Введение
2.2 Обобщенная структура программы.
2.2.1 Процесс решения переборной задачи в сети.
2.3 Специфика сетевых вычислений.
2.4 Метод декларативного описания задачи.
2.4.1 Определение списка имен доступных компьютеров
2.4.2 Описание метода и параметров решения
2.4.3 Описание способа получения переборных последовательностей
2.4.4 Описание формата решающей функции
и способа получения результата.
2.5 Решающая функция.
2.6 Декомпозиция задач переборного класса.
Формальная постановка задачи.
2.6.1 Генерация переборных последовательностей, получаемых сочетанием без повторяющихся элементов с длиной получаемых последовательностей от 1 до п.
2.6.2 Генерация переборных последовательностей, получаемых сочетанием без повторяющихся элементов
с определенной длиной получаемых последовательностей.
2.6.3 Генерация переборных последовательностей, получаемых перестановками без повторяющихся элементов
с определенной длиной получаемых последовательностей.
2.6.4 Особенности генерации переборных последовательностей, получаемых размещением и переборных последовательностей с повторяющимися элементами.
2.7 Подготовка вычислений. Административный этап реализации.
2.8 Выводы по главе
Глава 3 Разработка динамических методов распределении нагрузки.
3.1 Введение.
3.2 Статический метод
3.3 Динамический адаптивный метод
3.3.1 Алгоритм работы адаптивного метода.
3.3.2 Определения размера подзадачи
для адаптивного метода.
3.4 Динамический директивный метод.
3.4.1 Алгоритм работы директивного метода
3.4.2 Описание коэффициентов и параметров
директивного метода
3.4.3 Решение проблемы рассогласования нагрузки
для директивного метода
3.4.4 Определение базового размера подзадачи
для директивного метода
3.4.5 Расчет длительности импульса нагрузки достаточного
для изменения производительности компьютера
3.5 Отказоустойчивость координатора и рабочего процесса
3.6 Экспериментальная проверка динамических методов
и технологии решения переборных задач в сети.
3.6.1 Условия постановки экспериментов и методика оценки эффективности вычислений.
3.6.2 Сравнение времени решения задачи на нескольких компьютерах по сравнению с одним для различных
методов распределения нагрузки
3.6.3 Сравнение работы различных методов
распределения нагрузки при появлении фоновых процессов
3.6.4 Определение размера подзадачи для адаптивного метода, обеспечивающего минимальное время решения задачи
3.6.5 Влияние коэффициента мощности на работу директивного метода распределения нагрузки
3.6.6 Влияние коэффициента приращения на работу директивного метода распределения нагрузки
3.6.7 Определение влияния коэффициента инертности на работу директивного метода распределения нагрузки
3.7 Выводы по главе.
Глава 4. Конвейер сетевых вычислений
4.1 Введение
4.2 Обобщенная структура программы
4.3 Особенности декларативного метода описания задачи
для сетевого конвейера
4.4 Решающая функция
4.5 Условия целесообразности использования конвейера в сети.
4.6 Конфигурирование сетевого конвейера.
4.6.1 Алгоритм конфигурирования конвейера.
4.6.2 Некоторые особенности реконфигурирования
сетевого конвейера
4.7 Особенности тактирования сетевого конвейера.
4.8 Особенности диспетчеризации сетевого конвейера
4.9 Алгоритм работы координатора
4. Формальная постановка задачи
с использованием сегей Петри
4. Реализация работы конвейера для задачи
фильтрации изображений
Сравнение времени решения задачи на одном компьютере
и конвейере в зависимости от количества ступеней конвейера
Зависимость времени решения задачи на конвейере от трудоемкости операций, выполняемых конвейером
Реконфигурирование конвейера путем замены компьютера на ступени с низкой производительностью.
4. Выводы по главе
Заключение
Список литературы


Для решения вычислительноемких задач традиционно используются специализированные многопроцессорные системы. Данные системы обладают четко определенным составом и структурой, что с одной стороны обеспечивает простоту их использования, но с другой стороны они достаточно дороги. Быстрое развитие вычислительной техники и сетевых средств в последнее время привело к увеличению потенциальной вычислительной мощности сосредоточенной в компьютерных сетях. Следовательно, все большее количество вычиелнтельноемких задач можно решать за приемлемое время с использованием компьютерной сети. А с точки зрения стоимости вычислений, а так же возможностям масштабирования, бесспорно предпочтительнее использование сетей. В современном мире все больше возрастает потребность в решении таких актуальных и трудоемких задач, как предсказание прогноза погоды, моделирование физических процессов, аэродинамических свойств объектов и др. Многие из них относятся к задачам, решение которых возможно путем применения методов параллельной обработки данных. В данной диссертационной работе исследуются методы и программные средства предназначенные для решения задач параллелизма данных в компьютерной сети. Решение задач в компьютерной сети возможно путем применения методов параллельного программирования. Причем разработка приложений является достаточно сложной задачей. Трудоемкость разработки прикладных программ для многопроцессорных систем с распределенной памятью является главным препятствием для их широкого внедрения. Следовательно, разработка методов позволяющих упростить процедуру написания сетевых приложений, а так же методов, позволяющих эффективно использовать вычислительные ресурсы является актуальной задачей. Целью работы является исследование и разработка методов организации и выполнения параллельных вычислений в сети, которые существенно снижают трудоемкость разработки приложений и обеспечивают рациональное использование ресурсов сети. Предметом исследования являются методы и программные средства разработки распределенных приложений. Методы исследования базируются на теории множеств, сетей Петри и методах проектирования программного обеспечения. Разработаны два динамических метода распределения нагрузки адаптивный и директивный. В отличие от известных методов распределения, данные методы распределяют нагрузку, учитывая текущую реальную производительность компьютеров во время вычисления, не требуя при этом специального мониторинга ресурсов, что позволяет использовать эти ресурсы рационально. Предложена технология для решения задач в сети, которая, в отличие от существующих, предполагает использование методов декомпозиции задачи и распределения нагрузки, а так же средств организации вычислений в сети, что обеспечивает снижение трудоемкости написания приложений в сетевой среде. Предложен метод организации программного конвейера вычислений в сети, который, в отличие от существующих методов организации потоковых вычислений в сети, включает вопросы диспетчеризации и конфигурирования конвейера с целью повышения производительности. Достоверность результатов подтверждена экспериментальными исследованиями и результатами практической апробации. Предложенная технология позволяет уменьшить трудоемкость написания параллельных программ при решении задач в сетевой среде. Предложенные критерии рационального использования ресурсов сети позволяют определять способность методов максимально выгодно использовать доступные ресурсы. Разработан пакет программ, реализующий разработанную технологию решения задач в среде РУМ на примере решения переборных задач. Разработан и программно реализован конвейер вычислений в среде РУМ для задачи фильтрации изображений. Апробация работы. Научнотехнические конференции профессорскопреподавательского состава СПбГЭТУ, г. Международной научнотехнической конференции по мягким вычислениям БСМ, г. СанктПетербург. Публикации. По теме диссертации опубликовано 4 печатные работы, из них 2 статьи, 1 депонированная рукопись и тезисы к одному докладу на международной научнотехнической конференции.