Книга: Черемисинов Д. И. «Проектирование и анализ параллелизма в процессах и программах»

В монографии обсуждается широкий круг вопросов, связанных с проектированием микроэлектронных устройств с программным управлением. Рассматриваются задачи и методы разработки программ и аппаратуры с использованием языка ПРАЛУ, область применения которого расширена задачами верификации. Описывается разработка программы для кластерного компьютера, решающей комбинаторно-сложные задачи.
Книга адресована спецталистам в области проектирования дискретных устройств и может быть полезна для студентов и аспирантов, специализирующихся в данном направлении.

Содержание:

Предисловие...... 6 Введение...... 11 ГЛАВА 1. Параллельные алгоритмы...... 33 1. 1. Определение...... 33 1. 2. Классическая модель вычисления...... 35 1. 3. Модели параллелизма...... 38 1. 3. 1. Формализация параллелизма в программировании...... 38 1. 3. 2. Формализация параллелизма при проектировании аппаратуры...... 49 1. 4. Концепция времени в моделях распределенных систем...... 60 1. 4. 1. Обобщенный конечный автомат...... 61 1. 4. 2. Сети Петри...... 64 1. 4. 3. Временная логика...... 70 1. 4. 4. Интерпретация временной логики на модели Kripke...... 72 1. 5. О системе классификации формализмов...... 76 ГЛАВА 2. Язык ПРАЛУ как логика для описания взаимодействия...... 78 2. 1. Физическая трактовка временной логики...... 81 2. 2. Логика взаимодействия параллельных процессов...... 84 2. 2. 1. Структура события взаимодействия...... 85 2. 2. 2. Альтернативные предположения о связи событий...... 90 2. 2. 3. Понятие окружающей среды...... 91 2. 3. Интерпретация ПРАЛУ как временной логики...... 93 2. 3. 1. Минимальная семантика ПРАЛУ...... 94 2. 3. 2. Эквивалентность минимальной семантики ПРАЛУ и CCS...... 102 2. 3. 3. Необходимость измеряемого времени...... 105 2. 3. 4. Уточнения минимальной семантики, обеспечивающие реализуемость...... 107 2. 3. 5. Однопроцессорная реализация ПРАЛУ...... 109 ГЛАВА 3. Проектирование распределенных систем...... 116 3. 1. Моделирование локальной шины PCI...... 117 3. 1. 1. Функционирование шины PCI...... 119 3. 1. 2. Стандарт шины PCI...... 124 3. 1. 3. Пример устройства PCI...... 124 3. 1. 4. Оценка работоспособности алгоритма методом симуляции...... 126 3. 1. 5. Логическая структура устройства PCI...... 128 3. 2. Самосинхронные схемы...... 132 3. 3. ПРАЛУ и высокоуровневые языки описания аппаратуры...... 134 3. 3. 1. Компиляция конструкций языков программирования в комбинационную схему...... 136 3. 3. 2. Схемная семантика подмножества языка Verilog...... 138 3. 3. 3. Сравнение ПРАЛУ и Verilog...... 144 3. 4. Верификация поведенческих моделей...... 148 3. 4. 1. Построение генератора и монитора...... 152 3. 4. 2. Задача верификации...... 154 3. 4. 3. Инструменты для символической верификации...... 156 3. 4. 4. ПРАЛУ-верификатор...... 163 ГЛАВА 4. Мультиагентные системы...... 168 4. 1. Задача оптимизации программы агента...... 172 4. 1. 1. Представление протоколов конечными автоматами...... 172 4. 1. 2. Представление протоколов логическими формулами...... 173 4. 1. 3. Синтез программ, реализующих конечные автоматы...... 176 4. 1. 4. Модели программы...... 179 4. 1. 5. Синтез программ по структуре описания автомата...... 184 4. 1. 6. Управление синтезом программ...... 193 4. 2. Системы с произвольным числом агентов...... 195 4. 2. 1. BDI-архитектура мультиагентных систем...... 196 4. 2. 2. Формализмы задания протоколов взаимодействия агентов...... 197 4. 3. Спецификация протоколов взаимодействия агентов на ПРАЛУ...... 200 4. 3. 1. Протокол английского аукциона...... 201 4. 3. 3. Онтология архитектуры BDI для ПРАЛУ...... 204 4. 3. 4. Методология программирования агентов на ПРАЛУ...... 207 4. 3. 5. Программная реализация алгоритмов на ПРАЛУ...... 210 ГЛАВА 5. Программирование кластерного компьютера...... 214 5. 1. Среда программирования кластера через удаленный терминал...... 215 5. 2. Управление вычислениями на кластерном компьютере...... 217 5. 2. 1. MPI-программа...... 218 5. 2. 2. Интерфейс для управления MPI-программой...... 224 5. 3. Параллельные вычисления в задачах проектирования СБИС...... 228 5. 3. 1. Задачи, решаемые программным комплексом...... 229 5. 3. 2. Сложность комбинаторно-логических задач...... 234 5. 3. 3. Закон Амдала...... 236 5. 3. 4. Классы параллельных алгоритмов...... 238 5. 4. Методика программирования MPI-программ...... 243 5. 4. 1. Специфика отладки параллельных программ...... 243 5. 4. 2. Предотвращение ошибок в параллельных вычислениях...... 246 5. 4. 3. Верификация на модели в MPI-программе...... 249 ГЛАВА 6. Защита программ...... 252 6. 1. Модели угроз нападения на защищаемую программу...... 253 6. 1. 1. Враждебная программа в легальной среде исполнения...... 255 6. 1. 2. Легальная программа во враждебной среде исполнения...... 256 6. 1. 3. Защита распределенных программ...... 258 6. 2. Сохранение доверенности среды и обнаружение угроз...... 260 6. 3. Формальные модели, используемые при защите программ...... 263 6. 3. 1. Защита автоматизированным преобразованием кода...... 263 6. 3. 2. Предотвращение изменения кода программы...... 265 6. 3. 3. Защита, обоснованная результатами, связанными со сложностью задачи...... 267 6. 3. 4. Использование аппаратных средств...... 268 6. 4. Анализ стойкости защиты программы с помощью электронного ключа...... 270 6. 4. 1. Защита программ посредством электронного ключа...... 271 6. 4. 2. Виды атак на защищенную программу...... 272 6. 4. 3. Противодействие атаке методом удаления блокировки...... 274 6. 4. 4. Атака злоумышленника, имеющего ключ...... 276 6. 5. Защита программы для кластерного компьютера...... 278 6. 5. 1. Протоколы для защищенной передачи данных...... 280 6. 5. 2. Анализ защищенности интерфейса для управления MPI-программой...... 283 Приложение...... 286

Издательство: "Белорусская наука" (2011)

ISBN: 9789850812858