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

УДК 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

ВВЕДЕНИЕ 

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