Введение к работе
Актуальность темы. Тема исследований является актуальной. Решение поставленных в соответствии с ней задач позволяет на практике оптимально реализовать принцип распределённых вычислений с учётом высоких требований к структуре обмена, обусловленных алгоритмом решения задач. Это тем более важно, что идеи СЛЯ)-вычислений, рассматриваются как ждущие воплощения в ближайшее будущее, как выполнение распределённой обработки данных на основе сетевых технологий.
Цель данной диссертации. Целью настоящей диссертации является
разработка рекомендаций и средств, для организации распределённого
вычислительного процесса включающего этап распределения работ между
ресурсными процессорами, этап решения и этап сборки результатов
вычислений на головном процессоре, для минимизации времени решения
задачи. В качестве вычислительных средств рассматриваются
вычислительные сети и суперкомпьютер кластерного типа.
Объект исследований. Объектом исследования являются
распределенные вычислительные процессы на основе сетевых технологий и на суперкомпьютере кластерной архитектуры, время выполнения которых существенно зависит от плана и структуры внутрисистемного обмена данными. Частной исследуемой иллюстраций такого процесса является решение «больших» систем линейных уравнений методом Крамера.
Методы исследований. Методы кластеризации сетевого ресурса, методы маршрутизации в вычислительной сети, параллельное программирование, имитационное моделирование.
Научная новизна.
1. Предложена модель задачи на основе метода Крамера для решения
системы линейных уравнений с регулируемыми параметрами на основе
многопоточных вычислений, модель успешно минимизирует время
вычисления и позволяет решать задачи большой размерности.
2. Разработан новый параллельный алгоритм кластеризации ресурсных
процессоров вычислительной сети. Применение этого алгоритма
кластеризации позволило получить дальнейшее снижение времени
распределённых вычислений с количества процессоров порядка 15 до
привлечения гораздо большего количества процессоров (порядка 90).
При этом время решения тестовой задачи сокращается в 2000 раз.
3. Предложена модель реализации метода Крамера решения системы
линейных уравнений с применением разработанного нового
параллельного алгоритма кластеризации в вычислительной сети. Такая
модель увеличивает границу эффективности распределённых
вычислении. Например, система уравнений порядка п = 10 при
распределённых вычислениях становится эквивалентной (по времени решения) порядка 24. 4. Разработаны рекомендации по структуре организации распределенных вычислений, включающие структуру обмена, для задач, предполагающих схему вычислений типа «распределенные работы - счёт - сборка результатов», позволившие значительно удалить «точку насыщения» благодаря параллельному алгоритму кластеризации. Ключевая идея алгоритма заключается в том, что вычисляется минимальное покрывающее дерево для каждого подграфа и каждых вспомогательных двудольных графов, которые формируется параллельно на каждой паре подграфов. Тогда основной граф создаётся путем слияния построенных минимальных покрывающих деревьев. Математически доказано, что для получения оптимальной (максимальной) скорости обмена, нужно, чтобы число процессоров во всех подграфах было одинаковым (если число подграфов больше двух).
Достоверность основных научных положений. Выводов и рекомендаций, сформулированных в диссертации, обусловлена корректностью постановок задач, обоснованностью принятых допущений, удовлетворительной сходимостью результатов тестирования с данными, полученными в реальных условиях эксплуатации.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на ежегодных научных конференциях МИИТа (Неделя науки «Наука МИИТа - транспорту» в 2009, 2011 гг.); на IV международной научно-студенческой конференции в неделю науки Ирана, в 2010 г.; на VII международной научно-практической конференции студентов и молодых ученых «Trans-Mech-Art-Chem», МИИТ в 2010 г.; на 26th IEEE International Parallel & Distributed Processing Symposium, Shanghai, China, в 2011 г.; на IX международной конференции «Mathematical and Informational Technologies, MIT-2011» , Vrnjacka Banja, Serbia, в 2011 г.
Практическая значимость и реализация результатов работы:
-
Предложен новый параллельный алгоритм кластеризации вычислительных ресурсов для оптимизации обмена при распределённых вычислениях на этапе сборки результатов вычислений..
-
Показана возможность значительного увеличения числа процессоров, с вводом в использование которых время решения задачи убывает. Так, для размерности задачи п это количество используемых процессоров возросло с 15 (кластеризация не производилось) до порядка 90. Общее время решения задачи сокращается в 2000 раз.
3. Получены зависимости времени решения задачи от числа процессоров с
учётом их кластеризации. Они позволяют в будущем создать методику
оптимального назначения вычислительных ресурсов.
Публикации. По теме диссертации опубликовано 10 работ, из них 2 работы в ведущих изданиях из перечня, определенного ВАК России для опубликования основных результатов диссертаций.
Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (34 источников) и приложения. Работа изложена на 117 страницах машинописного текста, включая 22 рисунков, 7 таблиц, 1 приложение на 2 страницах.
