Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Глава 1. Определение предметной области и постановка задачи . . . . 17
1.1 Анализ опыта применения вычислительных систем для
обработки больших объемов данных . . . . . . . . . . . . . . . . . 17
1.2 Проблемы развития вычислительной техники . . . . . . . . . . . . 27
1.3 Влияние архитектуры ЭВМ на эффективность обработки данных . 33
1.4 Критический анализ исследований и разработок в области
аппаратного ускорения обработки данных . . . . . . . . . . . . . . 42
1.5 Обоснование выбора темы исследования . . . . . . . . . . . . . . . 63
Глава 2. Анализ методов и средств аппаратной поддержки обработки
множеств и структур данных . . . . . . . . . . . . . . . . . . . . 73
2.1 Вычислительные аспекты реализации операций дискретной
математики в ЭВМ . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.2 Анализ элементной базы для реализации аппаратной обработки
множеств и структур данных . . . . . . . . . . . . . . . . . . . . . . 86
2.3 Варианты организации аппаратной обработки множеств
и структур данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
2.4 Исследование принципов организации памяти и доступа
к структурам данных . . . . . . . . . . . . . . . . . . . . . . . . . . 103
2.5 Цикл выполнения команд Процессора обработки структур . . . . . 108
2.6 Выводы по главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Глава 3. Архитектура вычислительной системы с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . . . 116
3.1 Принципы функционирования вычислительной системы
с аппаратной поддержкой операций над структурами данных . . . . 116
3.2 Выбор вариантов взаимодействия устройств в вычислительной
системе с набором команд дискретной математики . . . . . . . . . 126
3.2.1 Топология общей шины . . . . . . . . . . . . . . . . . . . . 129
3
Стр.
3.2.2 Топология независимых шин . . . . . . . . . . . . . . . . . . 130
3.2.3 Топология с иерархией шин . . . . . . . . . . . . . . . . . . 133
3.3 Принципы функционирования Процессора обработки структур . . 135
3.3.1 Функциональная декомпозиция Процессора
обработки структур . . . . . . . . . . . . . . . . . . . . . . . 135
3.3.2 Принципы хранения структур данных . . . . . . . . . . . . 141
3.4 Аппаратные средства реализации основных операций
в вычислительной системе со множественным потоком команд
и одиночным потоком данных . . . . . . . . . . . . . . . . . . . . . 144
3.4.1 Функциональная схема Процессора обработки структур . . 144
3.4.2 Принцип функционирования Каталога . . . . . . . . . . . . 150
3.4.3 Принцип функционирования Операционного буфера . . . . 154
3.4.4 Принцип функционирования Устройства выборки команд
и определение форматов . . . . . . . . . . . . . . . . . . . . 161
3.4.5 Набор машинных команд . . . . . . . . . . . . . . . . . . . . 174
3.4.6 Реализация команды Добавление . . . . . . . . . . . . . . . 180
3.4.7 Реализация команды Удаление . . . . . . . . . . . . . . . . . 186
3.5 Реализация центрального устройства управления Процессора
обработки структур . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
3.6 Принципы организации высокопроизводительных
вычислительных систем с набором команд дискретной математики 204
3.7 Выводы по главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Глава 4. Оптимизация алгоритмов в вычислительной системе
с набором команд дискретной математики . . . . . . . . . . . . 217
4.1 Цели и принципы оптимизации алгоритмов в вычислительной
системе с набором команд дискретной математики . . . . . . . . . 217
4.1.1 Особенности представления алгоритмов
в вычислительной системе с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . 217
4.1.2 Анализ существующих подходов к разработке
параллельных алгоритмов в вычислительных системах . . . 218
4.1.3 Общие вопросы ускорения вычислительного процесса
при организации параллельной обработки . . . . . . . . . . 221
4
Стр.
4.1.4 Методика модификации алгоритмов для вычислительной
системы со множественным потоком команд
и одиночным потоком данных . . . . . . . . . . . . . . . . . 222
4.2 Вопросы представления программы ЭВМ с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . . . . . 231
4.2.1 Представление алгоритмов со множественным потоком
команд и одиночным потоком данных в виде псевдокодов . 232
4.2.2 Формальная постановка задачи декомпозиции
информационного графа программы . . . . . . . . . . . . . 234
4.2.3 Преобразование декомпозиции информационного графа
программы и критерии получения оптимальной
декомпозиции информационного графа алгоритма. . . . . . 240
4.2.4 Преобразование декомпозиции информационного графа
программы для вычислительной системы со
множественным потоком команд
и одиночным потоком данных. . . . . . . . . . . . . . . . . . 241
4.3 Реализация алгоритмов оптимизации на сетях и графах . . . . . . . 246
4.3.1 Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . 246
4.3.2 Алгоритмы обхода графа . . . . . . . . . . . . . . . . . . . . 251
4.3.3 Алгоритм Форда-Фалкерсона . . . . . . . . . . . . . . . . . 260
4.3.4 Алгоритмы поиска минимального остовного дерева . . . . . 267
4.4 Вопросы применения вычислительной системы с набором
команд дискретной математики . . . . . . . . . . . . . . . . . . . . 281
4.4.1 Применение Процессора обработки структур для
аппаратного ускорения баз данных . . . . . . . . . . . . . . 281
4.4.2 Защита данных в системах обработки информации . . . . . 292
4.4.3 Применение вычислительной системы с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . 303
4.5 Выводы по главе 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Глава 5. Реализация и экспериментальные исследования
эффективности вычислительной системы с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . . . 317
5
Стр.
5.1 Реализации вычислительной системы с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . . . . . 317
5.1.1 Этапы проектирования системы с набором команд
дискретной математики . . . . . . . . . . . . . . . . . . . . . 317
5.1.2 Основные технические параметры реализации
Процессора обработки структур . . . . . . . . . . . . . . . . 322
5.1.3 Язык ассемблера и машинные коды команд Процессора
обработки структур . . . . . . . . . . . . . . . . . . . . . . . 324
5.2 Верификация Процессора обработки структур и вычислительной
системы с набором команд дискретной математики . . . . . . . . . 337
5.2.1 Верификация модели системы . . . . . . . . . . . . . . . . . 337
5.2.2 Отладка прототипа на макете . . . . . . . . . . . . . . . . . 342
5.3 Экспериментальные исследования эффективности
вычислительной системы с набором команд дискретной математики345
5.3.1 Экспериментальное исследование временной сложности
основных операций . . . . . . . . . . . . . . . . . . . . . . . 345
5.3.2 Исследование производительности Процессора обработки
структур на алгоритмах поиска
минимального остовного дерева . . . . . . . . . . . . . . . . 349
5.3.3 Исследование производительности Процессора обработки
структур на алгоритмах обхода графа . . . . . . . . . . . . . 352
5.4 Архитектура высокопроизводительного вычислительного
комплекса Тераграф . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
5.5 Выводы по главе 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
Список сокращений и условных обозначений . . . . . . . . . . . . . . . . 382
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
