Многопроцессорные вычислительные системы. Теоретический анализ, математические модем и применение

УДК 004.272.43:51.7(075.8) 
ББК 32.973.202 
А65 

Р е ц е н з е н т ы: 
 
кафедра «Управляющие ЭВМ»  
Московского государственного института радиотехники, электроники и автоматики  
(Технического университета)  
 (зав. кафедрой д-р техн. наук, проф., засл. деятель науки и техники РФ Н.Л. Прохоров);  
директор ООО «Радиокомпьютерные системы»,  
д-р техн. наук, проф. А.В. Горячев 
 
           Андреев А. М. 
    Многопроцессорные вычислительные системы: теоретический анализ, 
математические модели и применение : учеб. пособие / А. М. Андреев, 
Г. П. Можаров, В. В. Сюзев. — М. : Изд-во МГТУ им. Н. Э. Баумана,  
2011. —  332, [4] с. : ил.  —  (Информатика в техническом университете) 

ISBN 978-5-7038-3439-8 

Рассмотрены вопросы выбора структуры, методы расчета и оптимизации 
структур многопроцессорных вычислительных систем (ВС). С единых позиций 
исследовано влияние структурных характеристик ВС на пропускную способность, 
производительность, стоимость и ряд других системных характеристик. 
Изложена спектральная теория графов: зависимости между спектральными и 
структурными свойствами графов, спектрами и группами автоморфизмов, ха-
рактеризация графов посредством их спектров и др. 
Описаны алгоритмы выбора конкретных структур ВС, приведены примеры 
применения этих алгоритмов, даны практические рекомендации для проектирования 
ВС. Основное внимание уделено выбору надежной и отказоустойчивой 
структуры многопроцессорных ВС. 
Содержание учебного пособия соответствует курсам лекций, читаемых в 
МГТУ им. Н.Э. Баумана. 
Для студентов старших курсов высших технических учебных заведений и 
аспирантов, обучающихся по направлениям системотехники, автоматизации 
технологических процессов и производств, а также для системных аналитиков 
и научных работников. 
 
УДК 004.272.43:51.7 (075.8) 
                                                                                        ББК 32.973.202 

  
 
 
 
 
 
 Андреев А.М., Можаров Г.П., Сюзев В.В., 2011 
 
                                                               Оформление. Издательство  
ISBN 978-5-7038-3439-8  
          МГТУ им. Н.Э. Баумана, 2011 

А65 

ОГЛАВЛЕНИЕ 

ПРЕДИСЛОВИЕ ...........................................................................................................  
7 
СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ ...................................................................  10 
СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ ..................................................................  11 
ВВЕДЕНИЕ.....................................................................................................................  12 
1. ПОНЯТИЕ «МНОГОПРОЦЕССОРНАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА»....  14 
1.1. Вычислительные системы на базе сверхбольшой интегральной схемы ........  14 
1.2. Современные задачи и требования к основным характеристикам ВС ..........  21 
1.3. Классификация ВС .............................................................................................  24 
1.4. Проблемы создания многопроцессорных ВС ...................................................  34 
1.5. Математическая модель, используемая для описания структур ВС............... 37 
1.6. Элементы теории графов ....................................................................................  39 
1.7. Числовые инварианты графов структур ВС .....................................................  47 
2. ОСНОВНЫЕ СВОЙСТВА СПЕКТРА ГРАФА ......................................................  54 
2.1. Спектр графа ВС..................................................................................................  54 
2.2. Матрица смежности и обыкновенный спектр графа........................................  62 
2.3. Характеристики спектров графов ......................................................................  66 
2.4. Определение спектров графов ВС .....................................................................  76 
2.5. Определение характеристических многочленов и спектров графов  
       некоторых специальных типов...........................................................................  80 

3. СВЯЗЬ МЕЖДУ СПЕКТРОМ И СТРУКТУРОЙ ГРАФОВ ВЫЧИСЛИТЕЛЬ- 
    НЫХ СИСТЕМ...........................................................................................................  85 
3.1. Основные соотношения между спектром и структурой графов ВС ............... 85 
3.2. Связи спектральных и структурных характеристик однородных ВС............. 94 
3.3. Группа автоморфизмов графов ВС ....................................................................  103 
3.4. Пример использования теории групп при расчете характеристик ВС ........... 108 

4. ВЛИЯНИЕ СТРУКТУРЫ НА ТЕХНИЧЕСКИЕ ХАРАКТЕРИСТИКИ ВЫЧИС- 
    ЛИТЕЛЬНЫХ СИСТЕМ ..........................................................................................  113 
4.1. Сложность сети ВС..............................................................................................  113 
4.2. Адаптация ВС к алгоритмам .............................................................................  116 
4.3. Проблемы адаптации структуры ВС к алгоритмам решаемых задач в тер- 
       минах теории графов ..........................................................................................  118 
4.4. Пример решения задач ВС..................................................................................  124 
4.5. Пропускная способность, диаметр и средний диаметр ВС .............................  127 
4.6. Надежность и живучесть топологической структуры ВС .............................. 132

Оглавление 

 6 

4.7. Примеры оценки влияния структурных характеристик на технические 
       характеристики сложных ВС.............................................................................. 138  
4.8. Связь стоимостных и структурных характеристик ВС.................................... 162  
5. ТЕХНОЛОГИЯ МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ  
    И ПРОЦЕССОВ..........................................................................................................  170 
5.1. Основные понятия теории моделирования ВС.................................................  170 
5.2. Методы моделирования ВС................................................................................  177 
5.3. Применение сетевых моделей для описания параллельных процессов ........  180 
5.4. Примеры построения математических моделей ВС.........................................  206 
5.5. Задачи моделирования ВС.................................................................................. 215 
5.6. Пример схемы проектирования ВС....................................................................  217 
5.7. Использование гиперсетей в качестве математических моделей для иссле-   
       дования структур ВС........................................................................................... 218  
5.8. Гиперсети с заданной связностью ..................................................................... 227  
6. МЕТОДЫ ОРГАНИЗАЦИИ ОДНОРОДНЫХ СТРУКТУР ВЫЧИСЛИТЕЛЬ- 
    НЫХ СИСТЕМ........................................................................................................... 235  
6.1. Операции над графами структур ВС и результирующие спектры.................. 235 
6.2. Структура динамически реструктурируемых отказоустойчивых ВС.............  243 
6.3. Пример организации структуры ВС, базирующейся на бинарной матрице   
       микропроцессоров............................................................................................... 250 
7. РАЗРЕШЕНИЕ ТУПИКОВЫХ СИТУАЦИЙ В ВЫЧИСЛИТЕЛЬНЫХ  
     СИСТЕМАХ .............................................................................................................. 261 
7.1. Основные проблемы информационного обмена в ВС ..................................... 261 
7.2. Определение числа маршрутов в ВС................................................................. 264 
7.3. Методы преодоления тупиковых ситуаций в ВС ............................................. 270 
7.4. Навигация и трансляция в ВС ............................................................................ 277 
8. МНОГОПРОЦЕССОРНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ С МАГИСТ- 
    РАЛЬНЫМИ СВЯЗЯМИ........................................................................................... 288 
8.1. Магистральные ВС.............................................................................................. 288 
8.2. Алгоритм выбора структуры магистрально-модульной ВС............................ 298 
8.3. Примеры расчета магистральных ВС ................................................................ 305 
ЗАКЛЮЧЕНИЕ.............................................................................................................. 324 
ТЕМЫ КУРСОВЫХ И САМОСТОЯТЕЛЬНЫХ РАБОТ........................................... 326 
ЛИТЕРАТУРА................................................................................................................ 328 
ПРИЛОЖЕНИЕ ............................................................................................................. 331 
 
 

 

Предисловие 

 
7 

ПРЕДИСЛОВИЕ 

В последнее время резко возросло количество научно-технической лите-
ратуры, посвященной вопросам теории, моделирования и оптимизации раз-
работок многопроцессорных вычислительных систем (ВС). 
Многопроцессорные ВС призваны удовлетворять возрастающие запросы 
пользователей в быстродействии, надежности, отказоустойчивости, точности 
и других характеристиках вычислительных средств. Проводимые исследова-
ния многопроцессорных ВС, однако, показывают, что их возможности могут 
быть полностью раскрыты и использованы только после тщательного анализа 
всех аспектов создания подобных вычислительных средств. 
Трудность в подготовке настоящего издания заключалась в обширности 
материалов, подлежащих систематизации, в необычайно быстром росте зна-
ний по данному направлению, а также в отсутствии единых взглядов на раз-
витие вычислительной техники. 
В настоящее время произошли значительные изменения в теории много-
процессорных ВС (выразившиеся в накоплении новых математических поня-
тий и, главное, в значительном изменении представлений о достигнутых ре-
зультатах), что обусловливает необходимость продолжения математических 
исследований в каждом из многочисленных направлений теории многопро-
цессорных ВС. 
Учебное пособие написано на основе многолетнего опыта чтения лекций 
по теории элементов многомодульных вычислительных систем в МГТУ  
им. Н.Э. Баумана на кафедре «Компьютерные системы и сети» с учетом ре-
зультатов научных работ авторов, современных публикаций в России и за 
рубежом. В нем доступно представлена фундаментальная теория спектров 
графов применительно к решению проблем топологического анализа и синте-
за многопроцессорных ВС. Ограниченный объем книги обусловил исключе-
ние некоторых математических положений, которые могут нарушить началь-
ное представление об основах спектральной теории графов. 
Авторы с единых позиций рассмотрели широкий круг вопросов струк-
турного проектирования многопроцессорных ВС. Особую актуальность име-
ет проблема создания формальных моделей структур ВС, с помощью кото-
рых можно было бы, абстрагируясь от определенных конкретных понятий, 
исследовать общие свойства многопроцессорных ВС: типы структур и состав 
блоков, исключение тупиковых ситуаций и однозначность управляющих воз-
действий, зависимость свойств от числа процессоров и т. п. 
Теории и практике применения многопроцессорных ВС посвящен целый 
ряд известных работ. Однако большинство из них носит монографический 
характер. В отечественной и зарубежной литературе есть монографии по 

 

Предисловие 

 8 

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

Авторы стремились к объективному изложению современных тенденций 
применения достаточно сложного математического аппарата, на фундаменте 
которого и создается топология перспективных ВС. От математического аппарата 
можно ожидать, кроме помощи и детализации конкретных частных 
задач, нетрадиционных решений неотложных проблем, а также хорошего видения 
того, что именно достижимо при воплощении желательной топологии 
многопроцессорной ВС. 
Для облегчения чтения в пособии приведены необходимые сведения из 
теории графов, матриц и групп. Авторы полагают, что при заведомо математически 
сложном материале, есть два пути его изложения. Можно все проделать 
за читателя, а можно оставить читателю преодоление многих задач, как 
правило, кратко формулируемых, но в то же время требующих постоянной 
работы мысли. Именно этот путь привлекает авторов. 
В пособии многие утверждения даны без доказательств: простые и естественные 
этапы доказательств или построения примеров нередко предоставляются 
читателю, для некоторых — намечен путь доказательства, для других — доказательство 
можно найти в источнике, приведенном в литературе. 
Пособие состоит из восьми глав. Глава 1 посвящена краткой истории, 
перспективам развития специализированных ВС. Здесь даны основные понятия 
и определения из теории многопроцессорных ВС, приведены необходимые 
для дальнейшего изложения теоретико-графовые понятия и обозначения. 
В главе 2 приведены необходимые сведения из теории матриц, некоторые 
основные результаты о спектрах графов: описаны способы определения спектров 
графов ВС, определены характеристический многочлен матрицы смежности 
и спектры графов некоторых специальных типов. 
В главе 3 даны соотношения между спектром и структурой графов ВС, 
приведены примеры решения задач синтеза ВС с использованием результатов 
теории групп. 
В главах 4 и 5 рассмотрено влияние структурных характеристик графов 
ВС и алгоритмов на технико-эксплуатационные характеристики многопроцессорных 
ВС; описаны методы моделирования структур ВС. 
Главы 6, 7 и 8 посвящены частным методам создания сложных ВС, алгоритмам 
выбора структуры многопроцессорных ВС с магистральными связями, 
построению алгоритмов, предотвращающих тупиковые ситуации в ВС. 
Теоретические положения иллюстрируются примерами. 

Предисловие 

 
9 

В конце каждого раздела приведены вопросы и примеры для самопроверки 
различной трудности, предназначенные для закрепления введенных 
понятий и рассмотренных алгоритмов. Решение примеров для самопроверки 
в большинстве случаев можно найти в содержании раздела и указанных источниках, 
что, по мнению авторов, будет стимулировать дальнейшие исследования. 
В приложении I приведены числовые данные, относящиеся к спектрам 
графов и соответствующим характеристическим многочленам. 
Изучение материала пособия целесообразно завершить курсовыми работами 
и перечнем тем для самостоятельного изучения и размышления (примерный 
перечень тем, которые могут быть использованы для курсовых и дипломных 
работ, приведен в приложении II). 
Пособие представляет собой единый методически взаимоувязанный курс, 
который будет полезен студентам-бакалаврам, магистрам, инженерам-исследователям, 
проходящим постдипломную подготовку, аспирантам, проходящим 
подготовку в МГТУ им. Н.Э. Баумана по специальности «Вычислительные 
машины, комплексы, системы и сети», а также студентам, обучающимся по 
другим специальностям направления «Информационные системы». 
Содержание пособия может дать определенный толчок для учебно-
исследовательской работы студентов, а также служить для самостоятельного 
изучения курса «Многопроцессорные вычислительные системы». 
Учебное пособие подготовлено в соответствии с программами дисциплин «
Многопроцессорные вычислительные системы». 
Авторы выражают глубокую благодарность доктору технических наук, 
профессору А.В. Горячеву, коллективу кафедры «Управляющие ЭВМ» (зав. 
кафедрой доктор технических наук, профессор, заслуженный деятель науки и 
техники Н.Л. Прохоров) за ценные предложения, замечания и помощь при 
создании настоящего пособия. 

 

Предисловие 

 10

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ 

ВК 
ВМ 
ВС 
ИИ 
КВВ 
КС 
МКМД 
МКОД 
 
МП 
ОВС 
ОКМД 
 
ОКОД 
ОС 
ПЗУ 
ПК 
ПМ 
ПМО 
ПО 
ПРО 
РВС 
РКТ 
СБИС 
СКМ 
СМО 
СП 
СУ 
СУБД 
СЦВМ 
СЦВС 
УВВ 
ЦВМ 
ЦОС 
ЦОСИ 
ЦП 
ЭП 
ЭРИ 

— вычислительный кластер 
— вычислительный модуль 
— вычислительная система 
— искусственный интеллект 
— канал ввода-вывода 
— космическая система 
— система с множественными потоками команд и данных 
— система с множественным потоком команд и одиночным     
     потоком данных 
— микропроцессор 
— однородные вычислительные системы 
— система с одиночным потоком команд и множественным  
     потоком данных 
— система с одиночными потоками команд и данных 
— операционная система 
— постоянное запоминающее устройство 
— персональный компьютер 
— программный модуль 
— программно-математическое обеспечение 
— программное обеспечение 
— противоракетная оборона 
— распределенная вычислительная система 
— ракетно-космическая техника 
— сверхбольшая интегральная схема 
— системы компьютерной математики 
— система массового обслуживания 
— специальный процессор 
— система управления 
— системы управления базами данных 
— специализированная цифровая вычислительная машина 
— специализированная цифровая вычислительная система 
— устройство ввода-вывода 
— цифровая вычислительная машина 
— цифровая обработка сигналов 
— цифровая обработка сигналов и изображений 
— центральный процессор 
— элементарный процессор 
— электронные радиотехнические изделия 

 

Предисловие 

 
11

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ 

|A|, Сard(A) 
A – B 
А  В 
]A[ 
a(G) 
BIB-схема 
Г 
Г(G) 
Cn
m 
det ||a||, |a| 
g(G) 
G1 + G2 
G1  G2 
G1  G2 
G1  G2 

1
2
G
G
+
 

1
2
G
G

 
J 
I 
ING-пара 
NEP-сумма 
cof X 
rmin(A) 
rmax(A) 
HG(t) 
L(G) 
per A 
р-сумма 
графов 
PG() 
S(G) 
sum M 
t(G) 
T(G) 
(G) 
ij 
 

— число элементов конечного множества А 
— разность 
— кронекерово произведение матриц 
— целая часть числа А 
— алгебраическая связность графа 
— уравновешенная неполная блок-схема 
— группа автоморфизмов 
— группа автоморфизмов мультиорграфа 
— число сочетаний без повторения из m элементов по n 
— определитель матрицы ||a|| 
— обхват орграфа G 
— сумма графов 
— полное произведение графов 
— объединение графов 
— произведение графов 
— прямая сумма графов 
— графы G1 и G2 изоморфны 
— квадратная матрица, все элементы которой равны 1 
— единичная матрица 
— пара изоспектральных неизоморфных графов 
— неполная расширенная p-сумма 
— сумма алгебраических дополнений квадратной матрицы X 
— наименьшая степень вершины A 
— наибольшая степень вершины A 
— производящая функция числа маршрутов 
— реберный граф 
— перманент матрицы А 
 — граф, множество вершин которого является прямым произведе- 
      нием вершин графов G1,…,Gn 
— характеристический многочлен графа G 
— граф подразбиений графа G 
— число остовных деревьев, содержащихся в графе G 
— сумма всех элементов невырожденной квадратной матрицы M 
— тотальный граф 
— хроматическое число графа G 
— символ Кронекера 
— сложение по модулю 2 
 

 

Предисловие 

 12

ВВЕДЕНИЕ 

Проблема выбора высокопроизводительных структур вычислительных сис-
тем (ВС), которые могли бы составить основу аппаратной поддержки процессов 
обработки интеллектуальной информации, неизбежно приводит к анализу воз-
можностей многопроцессорной (в том числе распределенной) обработки инфор-
мации. Дальнейший рост производительности цифровых вычислительных ма-
шин (ЦВМ) связан с необходимостью изменения их структурного построения в 
основном в направлении организации многопроцессорных ВС с широким ис-
пользованием параллелизма при обработке информации. Успехи микропроцес-
сорной технологии создают все предпосылки для реализации многопроцессор-
ных систем. 
Создание многопроцессорных ВС — задача комплексная и весьма слож-
ная. Она требует учета не только возможностей элементной базы, но и мно-
жества других факторов, особое место среди которых занимают выбор струк-
туры ВС и организация ее подсистем (кластеров) с учетом свойств алгорит-
мов решаемых задач. 
Новые возможности в повышении эффективности обработки информа-
ции сопровождаются и новыми проблемами, преодолеть которые можно 
только на основе сочетания достижений, присущих всему спектру исследова-
ний: от математических методов и алгоритмов до моделей ВС и принципов 
построения процессоров. 
Примером такой проблемы является значительное усложнение задачи эф-
фективного отображения алгоритмов на архитектуру многомодульных парал-
лельных систем. Комбинаторная сущность задачи отображения такова, что  
значение критерия эффективности может резко падать при, казалось бы, несу-
щественном изменении структуры алгоритма или структуры ВС. Стремление к 
наиболее тесному увязыванию решаемых задач и структур ВС ведет к необхо-
димости определенной специализации устройств по обработке данных. 
Проектирование ВС начинается с разработки алгоритма ее поведения, 
верификации этого алгоритма, его оптимизации и, возможно, декомпозиции 
на блоки (модули). Эти задачи существенно усложняются при разработке па-
раллельных ВС и алгоритмов. 
В предлагаемом пособии сформулированы задачи анализа и синтеза 
структур многопроцессорных ВС и сетей ЦВМ; даны их решения в виде 
классов графов, имеющих экстремальные топологические параметры, кото-
рые соответствуют характеристикам производительности и надежности при 
ограничениях на затраты. При определении классов графов структур ВС ис-
пользуется математический аппарат спектральной теории графов — научное 
направление, находящееся на стыке теории графов и теории матриц. 

 

Введение 

 
13

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

 

Предисловие 

 14

1. ПОНЯТИЕ «МНОГОПРОЦЕССОРНАЯ  
ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА» 

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

1.1. Вычислительные системы на базе  
сверхбольшой интегральной схемы 

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