Математические модели в проектировании аппаратно-программных реализаций алгоритмов, заданных текстами программ

• Автор: Лялин, Александр Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 98 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ

1.1. Возможные реализации алгоритма

1.2. Традиционные методы проектирования

1.3. Перспективные методы проектирования.

1.4. Автоматизация проектирования

1.5. Неформальное изложение технологии проектирования

1.6. Основные результаты теории схем программ

1.7. Современные системы компилляции.

1.8. Основные выводы главы 1.

ГЛАВА 2. МОДЕЛЬ ПРОГРАММЫ
2.1. Логическая структура алгоритма
2.2. Совершенное регулярное выражение
2.3. Информационная структура алгоритма
2.4. Примитивнорекурсивная информационная структура алгоритма алгоритма.
2.5. Информационные связи и функциональная эквивалентность
2.6. Регулярное выражение логической структуры алгоритма и примитивнорекурсивная информационная структура алгортима
2.7. Яруснопараллельная форма.
2.8. Конвейерные разложения
2.9. Особенности преобразования некоторых структур данных
2 Интерпретация действий элементарными функциями.
2 Фрагменты яруснопараллельной формы . Синхронизация
2 Основные выводы главы 2
ГЛАВА 3. АППАРАТНОПРОГРАММНАЯ РЕАЛИЗАЦИЯ .
3.1. Анализ возможных связей логической структуры алгоритма
3.2. Восстановление информационной структуры алгоритма.
3.3. Правильные разбиения и аппаратнопрограммная реализация
3.4. Необходимое условие правильного разбиения.
3.5. Конструирование управляющей схемы.
3.6. Дополнительные условия правильного разбиения
3.7. Раскрутка циклов и переименование элементов массива переменными .
3.8. Основные выводы главы 3.
ГЛАВА 4. НЕКОТОРЫЕ ПРАКТИЧЕСКИЕ ПРИМЕРЫ ПРИМЕНЕНИЯ
ТЕХНОЛОГИИ
4.1. Различные варианты реализации Ы1Ф8.
4.2. Различные варианты реализации .
4.3. Проектировании аппаратнопро1раммной реализации . .
4.4. Сравнения процесса декодирования и традиционной
архитектуры х
4.5. Основные выводы главы 4.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Формулировка основной задачи. Переход от описания алгоритмов к АПР определяется выбранной методологией, то есть совокупностью моделей и методов, используемых в технологическом маршруте перехода от описания содержательной задачи до корректно функционирующего аппаратного и программного обеспечения (рис. Рис. От содержательной задачи к аппаратно-программному комплексу. Содержательная задача описывает функции алгоритмов, вычислимые проектируемой АПР, и набор рекомендаций по выходным характеристикам будущей системы (энергопотребление, площадь схемной реализации, производительность). Содержательную задачу ещё называют техническим заданием. Методология структурно состоит из моделей описания содержательной задачи и некоторого количества этапов, на каждом из которых осуществляется преобразование над моделями. Время проектирования зависит от временных издержек методологических переходов. Поэтому в настоящее время особое внимание уделяется изучению формальных моделей и методов автоматизации, которые позволяют сократить эти временные издержки. Объект исследования. Объектом исследования являются математические модели, которые могут использоваться для описания этапов проектирования аппаратно-программных реализаций (АПР) и которые могут быть поддержены системами автоматизации проектирования. При этом под аппаратной реализацией (АР) понимается набор схем в виде соединённых между собой функциональных элементов, таких как мультиплексоры, триггеры, элементы «И», «ИЛИ» и т. ПР) понимается вычисление части функции алгоритма нрраммой специального или универсального процессора (рис. З). Рис. Общие проблемы современных методов проектирования. Основой традиционной методологии является функциональная спецификация (ФС). В ФС на основании заданного технического задания и своего опыта эксперты описывают модели. Рис. Переход от описания алгоритма к математической модели. Первая проблема заключается в том, что в традиционной методологии спецификация является полу-формальиым документом, который составляется экспертами на основании их опыта и интуиции. Спецификация определяет функциональность аппаратного и программного обеспечения устройства с учётом технического задания. В действительности, соответствие техническому заданию можно проверить только на поздних этапах разработки АПР. Поэтому правильно составленная экспертами спецификация не гарантирует, что система будет работать корректно. Данная проблема традиционно решается использованием нескольких моделей устройства (математическая модель устройства в виде программы, модель аппаратного и программного обеспечения), имитационное моделирование которых служит для доказательства непротиворечивости АПР техническому заданию. Из-за того, что описание в функциональной спецификация является неформальным, в каждую модель (рис. Исправление таких ошибок и тестирование исправлений существенно увеличивает время разработки. Вторая проблема. Алгоритмы, описанные в содержательной задаче, могут иметь различные способы их разделения на аппаратную (АР) и программную реализацию (ПР). В традиционных технологических маршрутах проектирования принято фиксировать в ФС (рис. САПР) построены на принципе заранее придуманной проектировщиком аппаратной и программной реализации (АЛР), описанных на специальных формальных языках (например, на языках Си, Уегік^ или УІ-ШЬ). Отсутствие механизмов САПР для поддержки исследования различных АПР алгоритма не позволяет вести поиск лучшей из них. Решаемые проблемы в диссертации. Решению перечисленных проблем посвящена данная работа. В качестве формального описания алгоритма принимается схема моделирующей алгоритм программы. Решается проблема преобразования схемы программы в виде логической структуры алгоритма (ЛСА) в примитивно-рекурсивную информационную структуру алгоритма (ИСА) для тех алгоритмов, которые это допускают. Рассматривается модель алгоритма в виде ИСА. Задача разделения алгоритма, заданного программой, сводится к поиску разбиения ИСА, отвечающему набору правил. Совокупность правил формулируется в виде лемм.