Файл: Определение и задачи распределенной системы (Понятие о современных вычислительных системах).pdf

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

В последние годы многопроцессорные системы стали входить и в жизнь массового пользователя: современные программы (например, трёхмерные игры) предъявляют высокие требования к скорости обработки данных (видеоданных), для чего целесообразно использовать несколько процессоров или процессорных ядер, работающих параллельно. Итак, современный персональный компьютер представляет собой простейшую разновидность многопроцессорной системы.

Для эффективного использования многопроцессорных систем необходимо:

преобразовывать последовательные алгоритмы обработки данных в параллельные;
использовать специальные алгоритмы (планировщики), которые позволят распределить операторы параллельных алгоритмов по процессорам ВС наиболее оптимальным образом.

Планировщик - часть основного алгоритма, служащая для обеспечения эффективного выполнения основного алгоритма на конкретной ВС.

При этом алгоритмы-планировщики могут использовать различные критерии оптимизации:

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

Сложность разработки планировщика связана с некоторыми сложностями:

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

Разработка и совершенствование алгоритмов-планировщиков увеличит быстродействие обработки данных на многопроцессорных системах.

В настоящей работе рассматриваются способы представления граф-схемы для случайного алгоритма с заданными параметрами и методы отображения их на структуре ВС (циркулянт).

ГЛАВА 1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1.Понятие о современных вычислительных системах

Параллельные вычислительные системы (ВС) являются одними из самых перспективных направлений увеличения производительности вычислительных средств. При решении задач распараллеливания существует два подхода:^[1]

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

При создании параллельных вычислительных систем учитываются различные аспекты их эксплуатации, такие как множественность решаемых задач, частоту их решения, требования к времени решения и т.д., что приводит к различным структурным схемам построения таких систем. Перечислим их в порядке возрастания сложности:^[2]

однородные многомашинные вычислительные комплексы (ОМВК), которые представляют собой сеть однотипных ЭВМ;
неоднородные многомашинные вычислительные комплексы (НМВК), которые представляют собой сеть разнотипных ЭВМ;
однородные многопроцессорные вычислительные системы (ОМВС), которые представляют собой ЭВМ с однотипными процессорами и общим полем оперативной памяти или без него;
неоднородные многопроцессорные вычислительные системы (НМВС), которые представляют собой системы с разнотипными процессорами и общим полем оперативной памяти или без него.

Система, представленная множеством описаний W={K,A}, где K – описание конструкций ВС, А – описание алгоритма работы множества вычислительных модулей, называется вычислительной. Описание К составляет множества значений {M,S}, где М – множество базовых вычислительных устройств {mi}, i=0, ... , N-1, где под базовыми вычислительными устройствами понимаются ЭВМ, процессоры, блоки памяти, внешние устройства. S – сеть связей между множествами элементов базиса.

В конструкцию К должны быть заложены следующие принципы:^[3]

а) параллелизм при обработке информации, т.е. организация вычислений одновременно на множестве вычислительных модулей М с организацией в случае необходимости обмена данными через сеть S;

б) адаптация конфигурации сети S к решаемой задаче. Алгоритм А обеспечивает наряду с требуемой обработкой управление одновременной работой определённым множеством ВМ и необходимым обменом данными между ними.

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

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

минимизация времени выполнения межмодульных обменов;
максимизация числа одновременно выполняемых обменов;
максимальная сохранность связности при выходах из строя ВМ и линий.

1.2 Структура ВС типа «Циркулянт»

В настоящее время в индустрии ВС получили широкое распространение коммутационные структуры (КС) типа циркулянтных. Эти структуры традиционно представляются D_n-графами.^[4]

Циркулянтой называется D_n-граф, представляемый в виде множества , где N – число вершин в графе, вершины нумеруются от 0 до N-1, – множество образующих чисел таких, что , а для чисел наибольший общий делитель, равен 1, n – число образующих чисел. Вершина i соединяется ребрами с вершинами .

Если граф коммутационной структуры имеет равные степени вершин, то КС называется симметричной, и несимметричной – в противном случае.

Циркулянта относится к классу симметричных КС. Пример циркулянты, представленной в виде двумерной матрицы или хордового кольца показан на рисунке 1 для {7,1,3}.

Рисунок 1 - Пример циркулянты {7,1,3}, изображенной в виде двумерной матрицы (а) и хордового кольца (б)

Для выполнения работы задана циркулянта {49, 1, 3, 4, 5, 7}.

ГЛАВА 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, НЕОБХОДИМЫЕ ДЛЯ РАЗРАБОТКИ АЛГОРИТМА РАСПРЕДЕЛЕНИЯ ПРОГРАММНЫХ МОДУЛЕЙ ПО ВЫЧИСЛИТЕЛЬНЫМ МОДУЛЯМ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ

Вершина – оператор ИЛГ заданной задачи.^[5]

Вес вершины (P) – время расчета вершины на i-ом процессоре.

Степень вершины (Vi) – количество узлов, находящиеся от i-ой вершины на минимальном расстоянии.

Коэффициент передачи (pA) – время передачи между узлами ВС.

Комплексный узел – транзитный узел ВС.

Время старта вершины (sT) – время старта расчета вершины в существующем разбиении вершин между процессорами.

Время финиша вершины (fT) – время финиша расчета вершины в существующем разбиении вершин между процессорами.

Нить – набор из одной или нескольких вершин, которые последовательно рассчитываются на одном процессоре.

Множество нитей (Т) – совокупность всех нитей заданного ИЛГ.

Пучок нитей ({Pz}) – множество связанных между собой нитей.

Таблица связей к-ой нити (TSk) – совокупность нитей, связанных с k-ой нитью (имеет Sk элементов).

Массив связей (MS) – упорядоченное множество связей всех нитей одного пучка.

ГЛАВА 3. РАСПРЕДЕЛЕНИЕ ОПЕРАТОРОВ ПО ВМ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ ДЛЯ ИНФОРМАЦИОННО-ЛОГИЧЕСКОЙ ГРАФ-СХЕМЫ

При построении плана распределения операторов по ВМ вычислительной системы с распределённой памятью для информационной граф-схемы возникают определённые трудности, связанные с передачей информации через транзитные ВМ. Сущность метода заключается в том, что на первом этапе создаются нити без учёта обмена информацией между ВМ. Затем при построении нитей в моменты обмена данными длины нитей корректируются на время обмена информацией в данной точке. Вначале получаем модифицированные веса вершин в виде pm,j=pj+qj,i ,где pj – вес j-й вершины, qj,i – вес дуги, исходящей из j-й вершины. При использовании транзитных ВМ модифицированный вес возрастает на qj,i(n-1), где n – количество используемых транзитных процессоров.

Структура ВС с общей памятью. Применяется в многопроцессорных системах и не используется в многомашинных системах.

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

Системы с общей оперативной памятью образуют современный класс ВС — многопроцессорных супер-ЭВМ. Одинаковый доступ всех процессоров к программам и данным представляет широкие возможности организации параллельного вычислительного процесса (параллельных вычислений). Отсутствуют потери реальной производительности на межпроцессорный (между задачами, процессами и т.д.) обмен данными (рис.2)

Рисунок 2 - Вычислительная система с общей памятью

Рисунок 3 - Граф-схема параллельного алгоритма (чёрным - веса вершин, синим - веса дуг)

3.1 Построение матрицы следования ИЛГ

Основным инструментом анализа граф-схем алгоритмов служит матрица следования, а также различные её модификации. Матрица следования – это транспонированная матрица смежности. Использование матрицы следования вместо матриц смежности объясняется удобством размещения и анализа граф-схем.^[6]