Введение к работе
Актуальность проблемы. В последние годы
многопроцессорные вычислительные системы стали доступны широкому кругу исследователей именно благодаря развитию кластерных технологий. Кластерные системы занимают более 75% в списке ТОР500 высокопроизводительных вычислительных систем. Ключевыми особенностями кластеров можно считать отсутствие общей памяти и межузловое взаимодействие через сеть. Эффективность параллельных программ, разработанных для кластеров, во многом зависит от того, как будет распределена нагрузка между узлами вычислительной системы. Одной из наиболее актуальных задач в этой области является разработка эффективных, масштабируемых сбалансированных параллельных алгоритмов для широкого круга приложений.
Кроме того, моделирование во многих отраслях стало повседневным инструментом, и для обеспечения необходимой точности расчетов, размерность моделей постоянно растет, что также стимулирует потребность в высокопроизводительных вычислениях.
Если прогресс в области аппаратных средств очевиден, то создание программных средств, эффективно использующих новые возможности параллельных платформ, сопряжено с целым рядом трудностей. Процесс осложняется еще и тем, что наибольшее распространение получила кластерная архитектура параллельных вычислителей.
Достоинством кластерных систем является хорошая масштабируемость, а недостатком слабая связь вычислительных узлов. Масштабируемость, позволяет относительно легко увеличивать число узлов в системе, но при этом растет топологический периметр сети и увеличиваются задержки при передаче сообщений. Это следствие слабой связи узлов, которая накладывает существенные ограничения на алгоритмы и методы распределения нагрузки.
Классические подходы к распределению нагрузки предполагают разделение кода или данных между узлами системы.
Кластеры, построенные из унифицированных узлов, а сегодня это компьютеры с многоядерными процессорами, и использующие стандартное программное обеспечение, наиболее доступны широкому кругу пользователей и могут вполне составить конкуренцию промышленным системам. Архитектурно, кластеры такого типа можно отнести к СоРС, CoWS или Беовульф системам.
Они обеспечивают высокую производительность для распределенных приложений, однако слабость коммуникаций, основанных на Gigabit Ethernet или даже Myrinet, не позволяет реализовывать параллельные процессы, требующие интенсивных обменов между узлами. Для повышения производительности таких параллельных систем необходимо разрабатывать алгоритмы, обеспечивающие:
минимизацию межпроцессорных обменов;
балансировку нагрузки узлов.
Поскольку основной проблемой, влияющей на производительность кластерных параллельных систем, является временная стоимость коммуникаций, то именно сокращение коммуникационных накладных расходов приводит к повышению эффективности вычислений.
Цель работы и задачи исследования. Повышение эффективности кластерных вычислительных систем при решении задачи построения кратчайших связывающих деревьев.
Для достижения поставленной цели в работе решаются следующие основные задачи:
Анализ особенностей аппаратных средств систем автоматизированного проектирования.
Анализ переносимости алгоритмов обработки графов на параллельную платформу.
Разработка параллельного алгоритма построения кратчайших связывающих деревьев из локально оптимальных фрагментов.
Разработка способа распределения нагрузки для решения задачи построения кратчайших деревьев на дискретном рабочем поле.
Разработка параллельной программы построения кратчайших связывающих деревьев, адаптированной для кластерных систем.
Экспериментальное исследование эффективности предложенного алгоритма.
Методы исследования. При решении поставленных задач были использованы положения теории графов, теории параллельного программирования, языки программирования.
Научная новизна. Разработка и исследование новых параллельных алгоритмов решения задач системного анализа на графовых моделях. Алгоритмы позволяют повысить эффективность использования узлов и общую производительность
вычислительных кластерных систем при решении оптимизационных задач системного анализа на графовых моделях.
Практическая значимость. Разработанный способ повышения эффективности кластерных вычислительных систем реализован в программном модуле автоматического построения кратчайших связывающих деревьев. Найденные решения позволят расширить класс решаемых задач системного анализа за счет увеличения размерности графовых моделей.
Способ распределения нагрузки вычислительных узлов кластеров, основанный на разбиении задачи на связанные фрагменты, может быть применен и для других классов задач системного анализа.
Положения, выносимые на защиту. ,
Анализ переносимости алгоритмов построения кратчайших связывающих деревьев на кластерные вычислительные системы.
Метод повышения эффективности кластерных вычислительных систем при решении задачи построения кратчайших связывающих деревьев.
Параллельный алгоритм построения кратчайших связывающих деревьев из локально-оптимальных фрагментов.
Параллельная программа автоматического построения кратчайших связывающих деревьев.
Анализ результатов исследований эффективности кластерных вычислителей при использовании предложенного алгоритма.
Внедрение результатов. Результаты диссертационной работы
используются на кафедре вычислительной техники МИЭТ при
проведении лабораторных работ по курсу
«Высокопроизводительные вычислительные системы».
Апробация работы. Основные положения диссертационной
работы докладывались и обсуждались на Всероссийских
межвузовских научно-технических конференциях студентов и
аспирантов "Микроэлектроника и информатика - 2005",
"Микроэлектроника и информатика - 2006", "Микроэлектроника и
информатика - 2007", Международной школы-конференции
"Информационно-телекоммуникационные системы - 2005"
Всероссийской межвузовской научно-практической конференции
"Актуальные проблемы информатизации. Развитие
информационной инфраструктуры, технологий и систем - 2007", научной сессии МИФИ "Компьютерные системы и технологии" -2007.
Публикации. По материалам диссертации опубликовано шесть тезисов докладов и три статьи. Получено свидетельство РФ на программу для ЭВМ.
Структура и объём диссертационной работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и приложения.
