Методы и средства распараллеливания комбинаторных алгоритмов в кластерных системах

• Автор: Еманов, Алексей Николаевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Пенза
• Количество страниц: 248 с. : ил.

1.1 Использование комбинаторных алгоритмов

1.2 Способы реализации алгоритмов.

1.3 Существующие архитектуры параллельных компьютеров.

1.3.1 i ii.

1.3.2 МРР iv i.

1.3.3 неоднородный доступ к памяти.

1.3.4 неоднородный доступ к памяти с поддержкой когерентности кэшей.

1.3.5 V параллельновекторные системы.

1.3.6 Кластеры

1.3.7 I вычислительная сеть

1.3.8 Выводы

1.4 Способы организации взаимодействия процессов
1.4.1 Стандарты.
1.4.2 Технологии
1.4.3 Высокоуровневые средства разработки.
1.4.4 Выводы
Выводы по главе 1.
Глава 2. Создание высокоэффективных реализаций параллельных
комбинаторных алгоритмов генерации комбинаторных объектов.
2.1 Эффективная реализация параллельной генерации перестановок элементного множества.
2.2 Эффективная реализация параллельной генерации всех подмножеств Лгэлементного множества
2.3 Эффективная реализация параллельной генерации элементных подмножеств.
2.4 Генерация комбинаторных объектов в гетерогенной кластерной среде.
2.4.1 Учет производительности узлов кластера при распараллеливании алгоритма.
2.4.2 Использование средств администрирования I для балансировки вычислительной нагрузки
2.5 Вычислительный эксперимент. Генерация комбинаторных объектов в гетерогенной среде
2.6 Метаалгоритм генерации комбинаторных объектов.
2.6.1 Фаза сбора данных.
2.6.2 Эффективное распределение задач.
2.6.3 Конструирование метаалгоритма управления распараллеливанием генерации комбинаторных объектов.
Выводы по главе 2.
Глава 3. Эффективные реализации параллельных алгоритмов на графах и матроидах.
3.1 Эффективная реализация параллельного алгоритма Флойда.
3.1.1 Метод распараллеливания.
3.1.2 Вычисление оптимального колва узлов для параллельного выполнения алгоритма Флойда
3.1.3 Вычислительный эксперимент.
3.2 Эффективная реализация параллельного жадного алгоритма на матроидах
3.2.1 Метод распараллеливания
3.2.2 Вычисление оптимального количества узлов для параллельного выполнения жадного алгоритма на матричном матроиде.
3.2.3 Вычислительный эксперимент.
3.3 Выполнение параллельных алгоритмов Флойда и жадного алгоритма на матричном матроиде в гетерогенной кластерной среде
Выводы по главе
Глава 4. Библиотека параллельных реализаций комбинаторных алгоритмов.
4.1 Общее назначение библиотеки.
4.2 Требования, предъявляемые к библиотеке
4.3 Выбор языка реализации
4.4 Особенности проектирования и реализации программ в среде стандарта I и I
4.4.1 Программа конфигурирования гетерогенной кластерной среды с использованием средств I.
4.4.2 Реализация метаалгоритма генерации комбинаторных объектов .
4.4.3 Реализация распараллеливания алгоритма Флойда в среде МРТ .
4.4.4 Реализация распараллеливания жадного алгоритма на матричных матроидах в среде I
4.4.5 Тестирование реализаций параллельных алгоритмов
4.5 Общая структура библиотеки эффективных параллельных реализаций комбинаторных алгоритмов
Выводы по главе 4.
Заключение
Литература


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