Введение
1 Обзор задач, требующих классификации бинарных отношений, и подходов к их практическому решению 12
1.1 Формализованное описание граф-схем алгоритмов управления 12
1.2 Постановка задачи поиска разбиения и ограничения базиса логических мультиконтроллеров 15
1.3 Классификация методов построения разбиений 18
1.4 Обзор задач на графах, требующих классификации бинарных отношений 21
1.5 Обзор классов современного аппаратного обеспечения для программной и аппаратной реализации преобразований матриц отношений 23
1.6 Обзор программных и аппаратных подходов к реализации классификации бинарных отношений с использованием матричных преобразований 26
2 Математическая модель и свойства бинарных отношений вершин граф-схем параллельных алгоритмов 30
2.1 Свойства бинарных отношений 30
2.2 Понятие и свойства бинарных отношений вершин граф-схем параллельных алгоритмов 31
2.3 Понятие матрицы отношений и ее свойства 37
3 Алгоритмы классификации бинарных отношений, ориентированные на программную и аппаратную реализацию 43
3.1 Понятие транзитивного замыкание бинарного отношения и алгоритмы его построения 43
3.2 Анализ эффективности и оптимизация программной реализации алгоритма транзитивного замыкания отношения, основанного на умножении матриц 46
3.3 Аппаратно-ориентированный алгоритм умножения битовых векторов 67
3.4 Стратегия аппаратно-программной классификации бинарных отношений. Аппаратно-ориентированный алгоритм построения матрицы отношений 70
4 Аппратно-программная реализация классификации бинарных отношений вершин 74
4.1 Структурно-функциональная организация устройства-акселератора для аппаратно-ориентированной классификации бинарных отношений 74
4.2 Матричное запоминающее устройство для хранения битовых признаков отношения следования 75
4.3 Схема загрузки данных в запоминающее устройство 78
4.4 Схема булева умножения битовых векторов 78
4.5 Схемотехническая реализация операции транзитивного замыкания отношения следования 82
4.6 Ячейка однородной среды для хранения битовых признаков отношения связи 85
4.7 Ячейки однородной среды для хранения битовых признаков отношений параллельности и альтернативы 87
4.8 Оценка выигрыша во времени при аппаратно-ориентированной классификации бинарных отношений 4.8.1 Оценка времени выполнения преобразований при программной реализации 92
4.8.2 Оценка быстродействия матричного запоминающего устройства для хранения отношения следования 93
4.8.3 Оценка быстродействия схемы умножения битовых векторов 93
4.8.4 Оценка быстродействия схемы транзитивного замыкания отношения следования 94
4.9. Оценка аппаратной сложности акселератора 97
4.9.1. Оценка аппаратной сложности ячейки и запоминающего устройства для хранения битовых признаков 97
4.9.2. Оценка аппаратной сложности операционной части устройства 99
4.10. Сравнительная оценка аппаратной сложности и быстродействия систолических матричных устройств для умножения матриц 102
Заключение 106
Список использованных источников 108
