автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Теоретические основы построения однородных вычислительных систем на неразрезных процессорных матрицах

у / о чУ «г / V (%- У

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ВОРОБЬЁВ Владимир Анатольевич

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ОДНОРОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА НЕРАЗРЕЗНЫХ ПРОЦЕССОРНЫХ МАТРИЦАХ

( 05.13.13 - Вычислительные машины, комплексы, системы и сети. )

ДИССЕРТАЦИЯ

на соискание учёной степени доктора технических наук

У

Содержание

Система шрифтов, обозначений и сокращений............................................. 8

Введение.........................................................................................................9

Глава 1. Алгоритмические модели ОВС......................................................40

1.1. Концепция ОВС...................................................................................41

1.1.1. Пути повышения быстродействия ЭВМ.....................................41

1.1.2. Однородные вычислительные системы (ОВС)...........................41

1.1.3. Экспансия параллельных систем и ОВС....................................52

1.1.4. Резюме..........................................................................................57

1.2. Функционально-алгоритмическая модель ОВС..................................58

1.2.1. Конфигуратор ОВС........................................................,............58

1.2.2. Структура алгоритмических описаний ОВС..............................62

1.2.3. Временные и схемные описания ОВС.........................................67

1.2.4. Алгоритмическое имитационное моделирование......................71

1.2.5. Резюме..........................................................................................73

1.3. Системная модель ОВС......................................................................74

1.3.1. Задача системного моделирования ОВС....................................74

1.3.2. Система параллельных процессов............................................74

1.3.3. Квазипараллельное исполнение параллельных процессов........77

1.3.4. Язык квазипараллельного программирования..........................78

1.3.5. Автоматное представление процесса..........................................80

1.3.6. Резюме..........................................................................................81

1.4. Клеточная модель ОВС.......................................................................82

1.4.1. Постановка задачи......................................................................82

1.4.2. Предшествующие модели коллективов вычислителей..............82

1.4.4. Однородная стохастическая клеточная (ОСК-) система.........84

1.4.5. Функциональные свойства ОСК-систем....................................87

1.4.6. Проблематика теории ОСК-систем............................................94

1.4.7. Резюме..........................................................................................95

1.5. Структурные характеристики ОВС................................................96

1.5.1. О теории идеального коллектива..............................................,.96

1.5.2. Структурные характеристики ОВС ............................................96

1.5.3. Теоретическое моделирование ОВС...........................................99

1.6. Основные результаты главы 1..........................................................101

Глава 2. Пределы производительности ОВС.............................................102

2.1. Технологические пределы производительности ОВС.......................103

2.1.1. Технологический прогресс ЭВМ...............................................103

2.2.2. Тепловой барьер........................................................................106

2.1.3. Резюме........................................................................................106

2.2. Исследование эффективности ОВС с общими шинами...................107

2.2.1. Постановка задачи....................................................................107

2.2.2. Предварительный анализ задачи..............................................109

2.2.3. Результаты моделирования.......................................................110

2.2.4. Обсуждение результатов...........................................................115

2.3. Исследование эффективности ОВС с трансляционным обменом.... 117

2.3.1. Операционная система ОВС......................................................117

2.3.2. Структура ОВС СУММА..........................................................120

2.3.3. Передача данных в ОВС СУММА...........................................121

2.3.4. Постановка задачи анализа распределённого управления.....123

2.3.5. Анализ управления трансляционными обменами в ОВС........124

2.3.6. Эффективность распределённого управления ОВС СУММА 126

2.3.7. Системный барьер производительности ОВС.........................129

2.4. Световой барьер и его преодоление...................................................131

2.4.1. Постановка проблемы...............................................................131

2.4.2. Световой барьер........................................................................132

2.4.3. Теория вычислений с физической точки зрения.......................132

2.4.4. Вычислительные события..........................................................133

2.4.5. Природа светового барьера......................................................134

2.4.6. Синхронные и асинхронные ЭВМ............................................136

2.4.7. Классический параллелизм.......................................................137

2.4.8. Принцип близкодействия..........................................................138

2.4.9. Релятивистские ЭВМ.................................................................142

2.4.10. О релятивистской теории вычислений....................................143

2.4.11. Проекты релятивистских ЭВМ...............................................145

2.4.12. Резюме......................................................................................146

2.5. Эффективность параллельных вычислений......................................147

2.5.1. Постановка проблемы..............................................................147

2.5.2. Алгоритмические пределы производительности....................147

2.5.3. Архитектурные пределы производительности.......................154

2.5.4. Резюме........................................................................................158

2.6. Основные результаты главы 2.........................................................159

Глава 3. Теория структур ОВС...................................................................160

3.1. Локальные однородные структуры..................................................162

3.1.1. Коммутаторы в вычислительных системах..............................162

3.1.2. Структура системы....................................................................169

3.1.3. Локальность...............................................................................171

3.1.4. Однородность............................................................................173

3.1.5. Периодичность..........................................................................174

3.2. КАИС-структуры............................................................................177

3.2.1. Определение КАИС-структур...................................................177

3.2.2. Эвклидовы и диофантовы структуры.......................................178

3.2.3. Локальные КАИС-структуры...................................................181

3.2.4. Типы КАИС-структур...............................................................181

3.2.5. Оптимальные КАИС-структуры...............................................182

3.2.6. Строение и эквивалентность КАИС-структур.........................185

3.2.7. Абсолютная и относительная адресация..................................190

3.2.8. Размеченная решётка относительных адресов.........................195

3.3. Вложение структур в структуры...................................................198

3.3.1. Задача вложения матриц в КАИС-структуры..........................198

3.3.2. Однозначные идеалы в Z+.......................................................199

3.3.3. Поиск и-мерных матриц, вложимых в /)„-граф.......................202

3.3.4. Клеточное и циклическое вложение матриц в структуру........204

3.3.5. Вложение структуры в физическое пространство....................205

3.4. Синтез и перебор Оп-графов............................................................. 209

3.4.1. Постановка задач синтеза и перебора......................................209

3.4.2. Предельные КАИС-структуры.................................................210

3.4.3. Таблица изоморфизмов............................................................212

3.4.4. Алгоритм синтеза 2)и-графов...................................................215

3.4.5. Каталог оптимальных /)„-графов.............................................217

3.5. Развитие теории структур ОВС.....................................................218

3.5.1. Исследования КАИС-структур.................................................218

3.5.2. Комбинированные структуры...................................................219

3.5.3. Функциональные проблемы теории структур ОВС.................221

3.4.4. Резюме........................................................................................223

3.6. Основные результаты главы 3.......................................................224

Глава 4. Отказоустойчивость ОВС............................................................225

4.1. Проблема отказоустойчивости ОВС..............................................226

4.1.1. Отказоустойчивые системы.......................................................226

4.1.2. Отказоустойчивые централизованные коммутаторы..............227

4.1.3. Отказоустойчивые распределённые коммутаторы..................227

4.1.4. Отказоустойчивые процедуры маршрутизации.......................229

4.1.5. О диагностике ОВС...................................................................230

4.1.6. Необходимость новой парадигмы структурной живучести....235

4.2. Пределы живучести ОВС.................................................................236

4.2.1. Проблема живучести ОВС........................................................236

4.2.3. Живучесть ОВС с точки зрения теории просачивания............241

4.2.4. Динамические модели живучести ОВС.....................................243

4.2.5. Исследование порогов просачивания.......................................246

Метод моделирующей решётки......................................................248

Метод второй производной............................................................250

4.2.6. Обсуждение результатов...........................................................253

4.2.7. Реальная парадигма живучести ОВС........................................255

4.3. Отказоустойчивые неразрезные процессорные матрицы (НПМ).... 257

4.3.1. Источники отказов СБИС........................................................258

4.3.2. Обеспечение отказоустойчивости НПМ .................................261

4.3.3. НПМ с программируемым резервом........................................264

4.3.4. Реконфигурация НПМ с программируемым резервом...........268

Алгоритм непосредственной перестройки.....................................268

Алгоритм вертикальной перестройки............................................270

Алгоритм ограниченного захвата.................................................270

Алгоритм свободного захвата........................................................272

4.3.5. Эффективность алгоритмов реконфигурации.........................274

4.3.6. Архитектура ОВС на НПМ с программируемым резервом 278

4.3.7. Резюме........................................................................................281

4.4. Программная реализация алгоритмов реконфигурации НПМ.........282

4.4.1. Недостатки схемной реализации..............................................282

4.4.2. Архитектура ОВС с программной реконфигурацией НПМ ...285

4.4.3. Локальная самодиагностика НПМ..........................................286

4.4.4. Язык ЛОГИКА для описания клеточных автоматов..............288

4.4.5. Резюме........................................................................................290

4.5. Реконфигурация отказоустойчивой НПМ методом консенсуса......291

4.5.1. Новая парадигма реконфигурации НПМ................................291

4.5.2. ОВС с реконфигурацией НПМ методом консенсуса...............292

4.5.3. Волновой алгоритм поиска консенсуса....................................293

4.5.4. Организация взаимодействий между ПЭ.................................297

4.5.5. Пример реконфигурации...........................................................298

4.5.6. Эффективность метода консенсуса...........................................300

4.6. Основные результаты главы 4..........................................................301

Заключение.................................................................................................303

Литература..................................................................................................306

Приложение.................................................................................................334

П. 1. Каталог оптимальных Т)п -графов..................................................335

П. 1.1. Оптимальные />2-графы............................................................335

П. 1.2. Оптимальные Дз-графы............................................................336

П. 1.3. Оптимальные 1>4-графы............................................................336

П. 1.4. Оптимальные />5-графы............................................................336

П. 2. Формальное описание языка ЛОГИКА............................................337

П. 3. Реализация языка ЛОГИКА.............................................................339

П. 4. Алгоритмы реконфигурации на языке ЛОГИКА.............................344

П.4.1. Алгоритм непосредственной перестройки..............................344

П.4.2. Алгоритм ограниченного захвата...........................................346

П.4.3. Алгоритм свободного захвата.................................................348

Система шрифтов, обозначений и сокращений

А, а ... Я, я - обычный текст

А,а... Я,я - определяемые термины

а,б...я; А,а...Я,я - выделенные: слова; фразы, заголовки, теоремы

a,b,...,z; 0,1, ... - элементы множеств, индексы, числа, параметры

п - число образующих (размерность) системы

a,...,y,z -векторы

s — {^о 1,... I} - вектор образующих /)п-графа

хч ,yiQ=j- 0 ~ относительные адреса в КАИС-структурах

0 - наибольший общий делитель (НОД)

[хо ,Х 1,... ,Хт_ 1 ] - наименьшее общее кратное (НОК)

[х]у - остаток от деления целого х на целое у

a\b -а делитель b (b делится на а без остатка)

ПСВ, ПрСВ - полная и приведённая системы вычетов

a,b,... ,z; 0,1,2,... - классы по модулю и номера теорем

A,B,C,...,Z - множества или важнейшие параметры

N - число элементов (мощность) системы

А,В,С,..., Z - алгебры, решётки, графы и другие системы

G(X, V) - граф: Х - множество вершин, Ve X2

Aut{G) - группа автоморфизмов графа G

Equ - группа эквивалентных преобразований адреса

Z - «-мерная целочисленная решётка

Z + - положительный квадрант решётки Z п

К, К*, Т, Ш - решётки: квадратная, треугольная и шестиугольная

ОВС - однородная вычислительная система

ЭМ - элементарная машина (СУ + ПЭ)

СУ - системное устройство (включая коммутатор)

ПЭ - процессорный элемент с памятью

НПМ - неразрезная процессорная матрица

ОСК-система - однородная стохастическая клеточная система

МПКА - микропрограммный клеточный автомат

(i.J.k) - ссылка на формулу (глава i. пункт j. формула к)

Введение

Актуальность проблемы. Одним из фундаментальных направлений развития современной науки и техники является достижение сверхвысокой производительности ЭВМ 1012-ь1014Р1орз и более. От решения этой проблемы зависит дальнейшее продвижение во многих стратегически важных отраслях науки, техники, экономики: численное моделирование сцен (синтез изображений), исследования по управляемому термоядерному синтезу, молекулярная динамика и статистическое моделирование в физике твёрдого тела и элементарных частиц, численный прогноз погоды, вычислительная аэродинамика и аэродинамика плазмы, разведка и моделирование нефтяных месторождений, численное решение трёхмерных волновых уравнений, проектирование интегральных схем, моделируются и декодируются структуры биомакромолекул. Для моделирование ядерных взрывов, вместо натурных испытаний, требуются ЭВМ с быстродействием в сотни раз большим, чем самые мощные суперкомпьютеры 90-х годов.

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

Концепция ОВС развивалась в СО РАН и в других научных организациях России при участии автора этой работы [1-9,13]. Исследования ОВС в России, связанные с развитием параллельных систем, основанных на однородности [ 1074], привели к созданию целого ряда экспериментальных и промышленных систем: МИНСК-222 [2], МИНИМАКС [3], СУММА [5] - в Институте матема-

тики СО РАН; МИКРОС[8] и МИКРОС-Т - в Институте физики полупроводников СО РАН; ПС-300, ПС-2000 [6], ПС-3000, ПС-4000- в Институте проблем управления РАН; МВС-100 [9] и МВС-хООО - в НПО «Квант».

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

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

Основные задачи диссертационной работы, определяемые поставленной целью, состоят в следующем.

1. Разработка математических моделей ОВС, пригодных для имитационного и аналитического исследования эффективности и корректности различных архитектур и алгоритмов функционирования ОВС.

2. Исследование фундаментальных пределов производительности различных архитектур ОВС и организации параллельных вычислений.

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

4. Разработка теории структур и алгоритмов функционирования структур ОВС, удовлетворяющих принципу близко действия.

5. Исследование пределов надёжности ОВС и новых парадигм живучести и самодиагностики НПМ.

6. Разработка близкодействующих алгоритмов реконфигурации избыточных НПМ СБИС с целью сохранения заданной стру