Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах

Структурно-функціональна таксономія розподілених обчислювальних систем.

Термин распределенная система [2] обозначает набор независимых компьютеров, представляющийся пользователям единой объединенной системой. В этом определении подчеркиваются два момента. Во-первых, все машины автономны. Во-вторых, распределенная система скрывает сложность и гетерогенную природу аппаратного обеспечения, на базе которого она построена. Организация распределенных систем включает в себя дополнительный уровень ПО, находящийся между верхним уровнем, на котором находятся пользователи и приложения, и нижним уровнем, состоящим из ОС. Такое ПО называется промежуточным.

На сегодняшний день можно выделить три типа распределенных систем [3]:

• Кластер -простая вычислительная система, ресурсы которой используются одной рабочей группой. Это несколько десятков компьютеров, на которых производятся вычисления, объединенных с помощью локальной сети. В отличие от кластера, определенного в параллельных системах, в распределенных системах кластеризация осуществляется только на уровне программного обеспечения.

• Вычислительная система корпоративного уровня -это вычислительная система, которая обслуживает несколько групп, работающих над разными проектами. В такой сети уже необходимо устанавливать правила совместного использования ресурсов, а в некоторых случаях и взаиморасчетов. Масштаб таких систем, как правило, небольшой, и можно обходиться «ручным» администрированием для организации работы ресурсов и пользователей.

• Глобальная система (грид-система) -это система, в которой участвуют несколько отдельных организаций, географически удаленных друг от друга, которые предоставляют друг другу свои ресурсы по определенным правилам и с определенными протоколами взаимодействия. Здесь прямые административные методы неэффективны, часто практически не применимы, и организационные проблемы и проблемы управления надо решать на уровне ПО.

Таким образом, при использовании термина «параллельные вычислительные системы» делается акцент на архитектурные особенности, такие как MPP, SMP, NUMA и т.д. Если необходимо описать систему, состоящую из независимых компьютерных архитектур, работающих как единое целое, и сделать акцент на программное обеспечение, благодаря которому эта работа возможна, то следует употреблять термин «распределенная вычислительная система».

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

Структура линий коммутации между процессорами вычислительной системы (топология сети передачи данных) определяется, как правило, с учетом возможностей эффективной технической реализации; немаловажную роль при выборе структуры сети играет и анализ интенсивности информационных потоков при параллельном решении наиболее распространенных вычислительных задач. К числу типовых топологий обычно относят следующие схемы коммуникации процессоров (см. рис. 1.1):

• полный граф (completely-connected graph or clique)- система, в которой между любой парой процессоров существует прямая линия связи; как результат, данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров;
• линейка (linear array or farm) - система, в которой каждый процессор имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, а с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);
• кольцо (ring) - данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки;
• звезда (star) - система, в которой все процессоры имеют линии связи с некоторым управляющим процессором; данная топология является эффективной, например, при организации централизованных схем параллельных вычислений;
• решетка (mesh) - система, в которой граф линий связи образует прямоугольную сетку (обычно двух- или трех- мерную); подобная топология может быть достаточно просто реализована и, кроме того, может быть эффективно используема при параллельном выполнении многих численных алгоритмов (например, при реализации методов анализа математических моделей, описываемых дифференциальными уравнениями в частных производных);
• гиперкуб (hypercube) - данная топология представляет частный случай структуры решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2 ^N процессоров при размерности N); данный вариант организации сети передачи данных достаточно широко распространен в практике и характеризуется следующим рядом отличительных признаков:

Рис. 1.2. Примеры топологий многопроцессорных вычислительных систем

• два процессора имеют соединение, если двоичное представление их номеров имеет только одну различающуюся позицию;
• в N -мерном гиперкубе каждый процессор связан ровно с N соседями;
• N -мерный гиперкуб может быть разделен на два (N – 1)-мерных гиперкуба (всего возможно N различных таких разбиений);
• кратчайший путь между двумя любыми процессорами имеет длину, совпадающую с количеством различающихся битовых значений в номерах процессоров (данная величина известна как расстояние Хэмминга).

Дополнительная информация по топологиям МВС может быть получена, например, в [2, 7]; при рассмотрении вопроса следует учесть, что схема линий передачи данных может реализовываться на аппаратном уровне, а может быть обеспечена на основе имеющейся физической топологии при помощи соответствующего программного обеспечения. Введение виртуальных (программно-реализуемых) топологий способствует мобильности разрабатываемых параллельных программ и снижает затраты на программирование.

Литература:

1. Основные классы современных параллельных компьютеров, Лаборатория НИВЦ МГУ http://www.parallel.ru/computers/classes.html

2. Э. Таненбаум Распределенные системы: принципы и парадигмы. – СПб: Питер, 2003. – 877 с.

3. Информационный Интернет-канал НАУКА и ИННОВАЦИИ http://www.rsci.ru/rt/

4. Ульянов М.В. Архитектуры процессоров. Учебное пособие.- М.: МГАПИ, 2002. - 68 с.

5. http://www.parallel.ru/computers/taxonomy/

6. Hockney R. W., Jesshope C.R. Parallel Computers 2. Architecture, Programming and Algorithms. - Adam Hilger, Bristol and Philadelphia, 1988. (русский перевод 1 издания: Р.Xокни, К.Джессхоуп. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986)

7. Гергель В.П., Стронгин, Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие – Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 с.

Дата добавления: 2014-01-14