Составители:
Рубрика:
Глава 3. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ
В СВЯЗИ С РАСПАРАЛЛЕЛИВАНИЕМ . . . . . . . 41
§ 1. О понятии графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41
§ 2. Ориентированный граф . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
§ 3. Топологическая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
§ 4. Примеры графов параллельных форм . . . . . . . . . . . . . . . . . . 45
§ 5. Изоморфизм графов. Операции гомоморфизма . . . . . . . . 47
§ 6. Построение графов параллельных форм . . . . . . . . . . . . . . . .49
§ 7. Направленные графы и параллельные формы . . . . . . . . . .51
Глава 4. ФУНКЦИОНАЛЬНЫЕ УСТРОЙСТВА . . . . . . . . . 55
§ 1. Некоторые определения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
§ 2. Свойства простых и конвейерных функциональных
устройств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
§ 3. О времени реализации алгоритма . . . . . . . . . . . . . . . . . . . . . . . 60
§ 4. Ускорение при распараллеливании . . . . . . . . . . . . . . . . . . . . . . 62
Глава 5. АЛГОРИТМЫ И ВЫЧИСЛИТЕЛЬНЫЕ
СИСТЕМЫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
§ 1. О соотношении графов алгоритма
и вычислительной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
§ 2. Базовая вычислительная система. . . . . . . . . . . . . . . . . . . . . . . .68
§ 3. К построению графа вычислительной системы. . . . . . . . . .70
Глава 6. ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ
АЛГОРИТМОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
§ 1. Программы реализации алгоритмов . . . . . . . . . . . . . . . . . . . . 75
1.1. Условия реализуемости алгоритмов . . . . . . . . . . . . . . . . 75
1.2. О времени выполнения алгоритмов . . . . . . . . . . . . . . . . 78
1.3. Уравновешенность базовой системы.
Режим максимального быстродействия . . . . . . . . . . . 79
§ 2. Матричные представления графов алгоритмов . . . . . . . . . 82
2.1. Матрицы инциденций и смежности . . . . . . . . . . . . . . . . 82
2.2. О реализации алгоритма с данной
матрицей инциденций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.3. Об использовании памяти для хранения
промежуточных результатов . . . . . . . . . . . . . . . . . . . . . . 85
2.4. Задача отображения алгоритмов
на вычислительные системы как задача
минимизации функционала . . . . . . . . . . . . . . . . . . . . . . . 86
205
