Содержание к диссертации
Введение
1. Анализ состояния в области проектирования цифровых устройств 15
1.1. Анализ проблем технологии разработки систем на кристалле 17
1.2. Анализ проблем проектирования современных микропроцессоров 19
1.3. Исследование структуры САПР, обеспечений САПР 22
1.4. Место методики в процессе проектирования ЦУ 26
1.4.1. Исследование уровней и задач проектирования ЭВМ и ЦУ 26
1.4.2. Исследование маршрута проектирования, используемого в современной САПР ПЛИС 28
1.4.3. Исследование маршрута проектирования на RTL уровне 29
1.4.4. Исследование маршрута проектирования с использованием языков структурного описания ЦУ 30
1.4.5. Исследование математических моделей процесса проектирования 37
1.5. Постановка задачи исследования 39
1.6. Выводы по главе 42
2. Разработка методики, реализующей переход от алгоритмической модели цу, к его структурной модели 43
2.1. Определение свойств и характеристик математических моделей 43
2.2. Алгоритмическая модель ЦУ 43
2.2.1. Применение машинно-ориентированных языков программирования в качестве алгоритмической модели 44
2.2.2. Информационная структура программы 46
2.2.3. Ограничения алгоритмической модели ЦУ 47
2.2.4. Выбор способа представления алгоритмических моделей ЦУ 48
2.3. Структурная модель устройства 49
2.3.1. Исследование языков структурного описания ЦУ 50
2.4. Планирование вычислительных процессов вЦУ 51
2.5. Неэффективный способ. Трансляция «как есть» 53
2.5.1. Структурная организация ЦУ 54
2.5.2. Набор моделей элементов класса линейных программ 59
2.5.3. Методика преобразования алгоритмической модели 75
2.5.4. Трансляция тестовой задачи 77
2.6. Планирование и организация параллельных процессов ВС 81
2.6.1. Условия планирования и организации вычислительных процессов в ЦУ 86
2.7. Информационная структура алгоритмической модели ЦУ класса линейных программ 89
2.7.1. Модифицированный метод реконфигурирования графов алгоритмов 90
2.7.2. Модифицированные алгоритмы исследования связей 99
2.8. Распределение работ в вычислительных системах по информационно-логическим графам алгоритмов 109
2.8.1. Решение задач 1 и 2 на информационно-логическом графе 112
2.9. Планирование обмена информацией по реконфигурированным информационно-логическим графам алгоритмов 117
2.10. Правила формирования структурной модели ЦУ 120
2.10.1. Алгоритм построения структурной модели ЦУ 120
2.11. Выводы по главе 121
3. Реализация алгоритмов формирования структурной модели цу по его алгоритмической модели... 123
3-1. Структурная схема разработанной подсистемы САПР ЦУ 124
3.2, Выводы по главе...,. 126
4. Исследование и внедрение результатов работы 127
4.1. Решение задач 1 и 2 на информационно-логическом графе 127
4.2. Получение структурной модели линейного дискретного рекурсивного фильтра 131
4.2.1. Аналитическая формула 131
4.2.2. Программа на языке Pascal с циклами 132
4.2.3. Программа на языке Pascal без циклов 132
4.2.4. Анализ программы 134
4.2.5. Исследование реконфигурированного графа алгоритма 138
4.2.6. Планирование обмена информацией при решении задач построения ЦУ 140
4.2.7. Построение структурной модели ЦУ 141
4.3. Выводы по эффективности использования разработанной методики 144
4.4. Выводы по главе 147
Заключение 148
Список использованных иллюстраций 151
Библиографический список использованной литературы
- Анализ проблем проектирования современных микропроцессоров
- Применение машинно-ориентированных языков программирования в качестве алгоритмической модели
- Методика преобразования алгоритмической модели
- Получение структурной модели линейного дискретного рекурсивного фильтра
Введение к работе
Актуальность работы,
В настоящее время рынок изделий цифровой микроэлектроники является одним из наиболее динамично развивающихся. На современном уровне развития изделий цифровой микроэлектроники их проектирование невозможно без применения средств САПР. В связи с быстрым моральным старением изделий цифровой микроэлектроники предъявляются высокие требования к скорости, дешевизне и удобству не только процесса их производства, но и процесса их проектирования. Это понятие особенно важно в связи с широким внедрением САПР, затраты на создание которых весьма велики. Например, может оказаться, что затраты на проектирование какого-либо устройства на апробированной элементной базе с помощью готовой САПР будут значительно меньше затрат на проектирование модификации того же устройства, улучшенной благодаря использованию новой элементной базы. Причинами могут послужить:
- необходимость модификации самой САПР;
- необходимость обучения для повышения квалификации проектировщиков.
Стоимость такого улучшения может оказаться слишком высокой из-за роста затрат на упомянутые нововведения. Поэтому методики проектирования изделий микроэлектроники постоянно эволюционируют, находясь на передовом этапе развития изделий вычислительной техники. Можно выделить основные подходы к методам проектирования:
- проектирование на уровне регистровых передач (RTL);
- повторное использование (IP Cores);
- совместное проектирование (HW/SW codesign);
- системное проектирование (SLDL).
Диссертационная работа посвящена исследованию и развитию методов системного проектирования изделий цифровой микроэлектроники. Подсистемы САПР системного проектирования поддерживают трансляцию программ на языках высокого уровня, например C++, в описания цифровых устройств (ЦУ) на языках аппаратурного описания, поэтому применение этих средств существенно ускоряет и упрощает процесс проектирования изделий микроэлектроники. В работе рассмотрены вопросы формирования структурной модели ЦУ по его алгоритмической модели. В настоящее время не существует средств САПР, поддерживающих автоматический метод формирования структурной модели ЦУ по его функциональным моделям. Сложность такого перехода заключается в различии подходов, используемых на этапах теоретической проработки и практической реализации ЦУ. Использование теоретического алгоритма подразумевает последовательное выполнение описанных в алгоритме операций. Самым нижним уровнем при этом представляется код программы с набором последовательных инструкций одному процессору. В то время как использование языка проектирования аппаратуры подразумевает описание многопроцессной (многопроцессорной) архитектуры ЦУ с одновременным переключением (функционированием) блоков ЦУ.
Несовершенство средств системного проектирования приводит к увеличению требований к квалификации специалистов, занимающихся проектированием изделий микроэлектроники. Проектировщикам необходимо повышать квалификацию не только в области проектирования ЦУ, но и в других областях, например, в области параллельных вычислений. Таким образом, основным недостатком современного процесса проектирования изделий микроэлектроники является высокая трудоёмкость проектирования и получение проектного решения более низкого качества. Например, отсутствие автоматизации на сложных этапах проектирования ЦУ приводит к неэффективному планированию структуры ЦУ, к неэффективному реконфигурированию и распараллеливанию циклов, к усложнению
исследования алгоритма на выявление скрытых взаимосвязей, к неэффективному планированию хода вычислительного процесса при различных критериях оптимизации.
Таким образом, исследования по созданию новой методики формирования структурной модели ЦУ по его алгоритмической модели, должны включать в себя две связанные задачи:
- поиск методов и маршрутов проектирования изделий микроэлектроники (математическое обеспечение САПР), которые позволят автоматизировать процесс формирования структурной модели ЦУ;
- совершенствование, на основе разработанных методов, информационного и программного обеспечений (ПО) САПР цифровой микроэлектроники.
Обе задачи одинаково важны и актуальны, более того сильно взаимосвязаны, поэтому эффективность методики проектирования зависит как от ее математического аппарата, так и от поддерживаемого ею маршрута проектирования.
Целью работы является исследование и развитие методов автоматизации проектирования цифровых устройств по их алгоритмическим моделям, разработка новых методов, позволяющих автоматизировать процесс формирования структурных моделей цифровых устройств по их алгоритмическим моделям. Для достижения поставленной цели в диссертационной работе решались следующие основные задачи:
1. Исследование методологий, математических моделей цифровых устройств, используемых на этапах структурного и функционально-логического проектирования.
2. Разработка моделей элементов программ и методики преобразования алгоритмической модели в структурную модель.
3. Разработка методов планирования и организации параллельных процессов вычислительных систем для проектирования цифровых устройств.
4. Разработка алгоритмов и программ, реализующих форм ирование структурной модели цифрового устройства по его алгоритмической модели. Исследование алгоритмов формирования структурной модели цифрового устройства по его алгоритмической модели.
Методы исследования. В работе применялись теоретические и экспериментальные методы исследований. Теоретические методы основаны на положениях вычислительной математики, системного анализа, численных методах параллельных вычислений, теории САПР, теории графов, теории множеств, теории цифровой обработки сигналов, теории параллельных вычислений. Математическое моделирование проводилось как с применением стандартных языков программирования, так и в специализированных пакетах прикладных программ. Экспериментальные исследования были проведены на специально разработанной подсистеме САПР, позволяющей автоматизировать формирование структурных моделей цифровых устройств по их алгоритмически моделям.
Научная новизна работы. Новые научные результаты, полученные в работе, состоят в следующем.
1. Разработан функционально полный базис схемных реализаций алгоритмических конструкций и методика преобразования алгоритмической модели цифрового устройства в его структурную модель, реализующую последовательное выполнение операций алгоритма.
2. Модифицированы существующие алгоритмы реконфигурирования информационно-логических графов алгоритмов для повышения детализации представления параллельных алгоритмов.
3. Разработаны новые и модифицированы существующие алгоритмы.
планирования вычислительных процессов цифрового устройства,
алгоритмы планирования обмена информацией между блоками цифрового устройства. 4. Впервые предложена методика, позволяющая автоматизировать процесс перехода от алгоритмической модели цифрового устройства к его структурной модели, реализующая параллельное выполнение операций алгоритма.
Практическая ценность работы состоит:
1. В уменьшении времени и упрощении процесса проектирования цифровых устройств, по сравнению с проектированием на уровне регистровых передач, за счёт использования методов формирования структурных моделей цифровых устройств.
2. В разработке специального программного обеспечения, позволяющего сократить временные и материальные затраты при проектировании цифровых устройств.
Реализация и внедрение результатов работы.
Работа по теме диссертации проводилась на кафедре ВТ ВлГУ, в Центре Микроэлектронного Проектирования и Обучения, в рамках госзаказа по контрактам НИОКР № 2875/03, 2876/03. Полученные результаты исследований в виде методик и программного обеспечения внедрены в виде материалов отчётов по НИР и ОКР, выполненных в рамках госзаказа, и в учебный процесс кафедры ВТ ВлГУ.
Апробация работы.
Основные положения и результаты работы докладывались и обсуждались на следующих семинарах и конференциях:
Международная научно-техническая конференция «Новые методологии проектирования изделий микроэлектроники» (Владимир, 2002);
Международная научно-техническая конференция «XI Туполевские чтения студентов» (Казань, 2003);
Международная научно-техническая конференция
«Новые методологии проектирования изделий микроэлектроники»
«New Design Methodologies» (Владимир, 2004 г);
12th International Conference «Mixdes Design of Integrated Circuits and
Systems» (Poland, 2005);
НТК профессорско-преподавательского состава ВлГУ (2002-2004 г);
Научно-практические семинары Центра Микроэлектронного
Проектирования и Обучения ВлГУ (2002-2004 г).
На защиту выносятся.
1. Методика формирования структурной модели цифрового устройства по его алгоритмической модели.
2. Модифицированные алгоритмы реконфигурирования информационно-логических графов алгоритмов и алгоритмы исследования информационно-логических взаимосвязей графов алгоритмов.
3. Алгоритмы планирования вычислительных процессов цифрового устройства, алгоритмы планирования обмена информацией между блоками цифрового устройства.
4. Информационное, математическое и программное обеспечения разработанной подсистемы САПР ЦУ.
5. Результаты применения разработанной подсистемы САПР ЦУ для формирования структурных моделей цифровых устройств.
Публикации по работе. По теме диссертации опубликовано 9 печатных работ, из них одна - в материалах Европейской конференции. Одна статья напечатана в сборнике научных трудов и 8 тезисов докладов в трудах Международных и Российских научно-технических конференций.
Структура работы. Диссертация состоит из введения, четырёх глав и заключения, списка литературы и приложений. Общий объём диссертации
192 страница, в том числе - 167 страниц основного текста, 12 страниц списка литературы (108 наименований). Диссертация содержит 72 рисунка.
В первой главе диссертации проведён анализ состояния в области проектирования цифровых устройств. Проанализированы маршруты проектирования в современных коммерческих САПР цифровых устройств. Исследованы преимущества и недостатки существующих методик проектирования цифровых устройств. Исследованы и проанализированы публикации, посвященные состоянию в области проектирования изделий цифровой микроэлектроники. Было выявлено, что в настоящий момент наиболее слабо развита методика формирования структурных моделей цифровых устройств по их функциональным моделям (системное проектирование). Было рассмотрено несколько реализаций этой методики. Показано, что проектирование на системном уровне является наиболее перспективным направлением в проектировании изделий цифровой микроэлектроники.
Во второй главе диссертации предлагается методика формирования
структурной модели цифрового устройства по его функциональной модели.
В главе обоснован выбор описания функциональной модели цифрового
устройства. Была выбрана алгоритмическая модель, как частный случай
функциональной модели. На способ описания алгоритмической модели были
наложены ряд ограничений для автоматизации её исследования. В
соответствии с наложенными ограничениями на способ описания
алгоритмических моделей — был разработан функционально полный набор
моделей элементов программ и методика трансляции «как есть» описания
алгоритмической модели цифрового устройства в его структурную модель.
Был выявлен набор классов элементов, которые транслировались в
структурную модель цифрового устройства. Для каждого элемента были
разработаны схемная реализация и правила формирования управляющих
сигналов. В результате был сделан вывод, что задача формирования
структурной модели цифрового устройства по его алгоритмической модели
решаема, форма постановки задача корректна, а накладываемые ограничения приемлемы. Далее была поставлена задача нахождения наиболее эффективного способа формирования структурной модели цифрового устройства, используя методы оптимизации. В качестве наиболее эффективного способа планирования и организации вычислительных процессов цифрового устройства с учётом применения этого способа в разрабатываемой методике, было предложено применение
распараллеливания вычислений. Приведены алгоритмы реконфигурирования информационно-логических графов алгоритмов, приведены алгоритмы исследования информационно-логических связей графов алгоритмов. Приведено описание алгоритмов планирования вычислительных процессов в цифровом устройстве, как в параллельной вычислительной системе. Предложен алгоритм формирования структуры цифрового устройства. Задача формирования структурной модели цифрового устройства решалась с использованием двух критериев минимизации — стоимости устройства и времени выполнения поставленной на проектирование задачи.
В третьей главе описывается программное обеспечение подсистемы САПР цифровых устройств, реализующее предложенные методы. Приведена структурная схема разработанной подсистемы САПР цифровых устройств.
В четвёртой главе рассматриваются вопросы практического
использования и экспериментального исследования подсистемы САПР
формирования структурных моделей цифровых устройств. Эксперименты
проводились как на простейших задачах, состоящих из небольшого
количества операций и связей между ними, так и на получении сложного
рекурсивного цифрового фильтра переменного порядка. Задачи решались с
использованием двух критериев минимизации — стоимости цифрового
устройства и времени выполнения поставленных задач. Была
продемонстрирована сложность применения методики в ручном режиме,
заключающаяся в переборе большого количества вариантов решения задачи.
Были даны оценки трудоёмкости решения задач при заданных критериях
минимизации параметров (характеристик) цифровых устройств. Было проведено сравнение времени проектирования цифровых устройств с использованием методики проектирования на уровне регистровых передач и разработанной методики системного проектирования. В результате чего были сделаны выводы по эффективности использования разработанной методики.
В заключении приведены основные результаты работы.
В приложениях приведены дополнительные материалы, использованные для получения функционально полного набора моделей элементов линейных программ, а также материалы, использованные при тестировании алгоритмов и разработанной подсистемы САПР цифровых устройств.
Анализ проблем проектирования современных микропроцессоров
Рассмотрим подходы и способы организации современных микропроцессоров [31]. Повышение производительности микропроцессоров достигается за счёт увеличения тактовой частоты, совершенствования параллельной и конвейерной обработки данных, а также уменьшения доступа к памяти. В настоящее время возможно проектирование микропроцессоров с несколькими сотнями миллионов транзисторов на кристалле. Уверенно просматривается перспектива увеличения количества транзисторов до миллиарда [49, 96, 101]. Возросшее количество транзисторов может быть использовано: - для построения ФУ микропроцессора, таких как АЛУ, конвейеры, сопроцессоры и так далее; - для увеличения объёма внутрикристальной кэш-памяти; - или для того и другого.
Возможно также создание новых классов кристаллов однокристальных параллельных систем. Увеличение количества транзисторов можно использовать для построения кэш-памяти. Однако это не всегда приводит к приросту производительности, так как память представляет собой ресурс, не производящий непосредственно вычислений. Поэтому также привлекательным выглядит использование ресурса транзисторов кристалла для построения совокупности ФУ. Основное препятствие на пути повышения производительности за счёт увеличения количества ФУ - это загрузка устройств полезной работой. То есть для увеличения производительности микропроцессора недостаточно включить в него максимальное количество ФУ. Необходимо учесть конфликты по управлению, конфликты информационного обмена, равномерно распределить нагрузку на ФУ и так далее.
Можно отметить наличие архитектурных ограничений, влияющих на производительность как суперскалярных так и процессоров с длинным командным словом (в иностранной литературе эти процессоры упоминаются как VLIW-процессоры или Very Large Instruction Word).
В основном производительность суперскалярных архитектур ограничивается: - сложностью блоков предвыборки; - сложностью блоков предсказания ветвлений; - размерами окна исполнения команд; - сложностью синхронизации информации в кеш-памяти.
Производительность процессоров с длинным командным словом главным образом ограничивается: - командами ветвления, зависящими от данных, - отсутствием у компилятора зависимостей, формируемых в процессе вычислений; - невозможностью переупорядочивания операций во время исполнения программ.
Тем не менее, эффективность архитектурно-структурных решений повышается с каждым поколением микропроцессоров - повышается степень универсальности решаемых задач современными микропроцессорами, увеличивается функциональность и автономность блоков процессора. Если когда-либо будет создан микропроцессор, выполняющий программную реализацию вычислений наиболее эффективно (для разного класса задач), то существуют, по крайней мере, три задачи, которые необходимо будет решить при проектировании такого устройства: - устранение недостатков/ограничений существующих решений; - число активных команд, которые могут исполняться параллельно, не должны ограничивать присущий программам параллелизм; - необходимо эффективное исследование зависимостей между командами всего программного кода для возможной их реструктуризации/переупорядочивания;
Исходя из сказанного выше, архитектурно, и по количеству занятых в процессе вычислений ФУ процессора, такая система станет напоминать схемную реализацию заданного алгоритма - уникальная схема объединения регистров и ФУ, специализированность управляющих воздействий и других решений. Сейчас для решения подобных задач требуется построение уникальных вычислительных установок, которые по постановке задачи являются специализированными.
Современная система автоматизированного проектирования (САПР цифровых устройств) представляет собой сложную программно-информационно-аппаратурную человеко-машинную систему, построенную по иерархическому принципу, так что каждый уровень иерархии отражает определённый уровень проектирования - структурный, функциональный, логический и так далее. Разработка САПР занимает длительное время, поэтому САПР должна в максимальной степени удовлетворять требованию моральной долговечности, поэтому, обычно, САПР проектируется как открытая и развивающаяся система [1, 24, 51].
Участие человека в процессе проектирования формально носит характер диалога между ЭВМ и проектировщиком. Этот диалог эффективен при выполнении следующих трёх условий:
1. Человек работает эффективнее ЭВМ при решении трудно формализуемых или не формализуемых задач. Человек при решении трудных задач пользуется эвристическими методами, ЭВМ -перебором имеющихся в наборе правил/алгоритмов.
2. Время ожидания ответа на запрос в режиме диалога не должно быть слишком большим. Это условие ограничивает круг задач, решаемых в режиме диалога, задачами невысокой размерности.
3. Объем изменяемой в процессе диалога информации не должен быть слишком большим, иначе диалог теряет оперативность, к тому же возрастает вероятность ввода ошибочной информации.
Из перечисленных условий следует, что САПР тем удобнее для проектировщика, чем больше правил/алгоритмов положено в её основу. То есть чем меньше проектировщику приходится решать сложные задачи. Кроме того, ошибки и квалификация проектировщика при большом объёме ручного проектирования сказываются на качестве изделия.
Применение машинно-ориентированных языков программирования в качестве алгоритмической модели
Реализация алгоритмов в машинных кодах или с помощью коммуникационных автокодов PVM или MPI, или описание на машинно-ориентированных языках, например, ассемблер в целом выполняют поставленное требование установления зависимости выходных параметров от входных. Однако такой способ описания вносит дополнительные структурно-архитектурные ограничения на организацию ВС. Например, описание на ассемблере предполагает обязательное использование регистров центрального процессора; использование VLIW-инструкций предполагает параллельное управление фиксированным количеством ФУ ВС.
Все машинно-ориентированные языки аппаратно-зависимы, так как работают с архитектурно-структурной организацией процессора (регистры, стековая память, отдельные функциональные устройства). При этом набор регистров всегда ограничен, регистры связаны с функциональными устройствами, мультиплексорами, через которые возможны передачи данных [31 стр. 16]. В зависимости от исходной схемы объединения регистров и функциональных устройств, набор используемых команд может больше подходить для выполнения одних алгоритмов и препятствовать эффективной реализации других.
Таким образом, использование машинно-ориентированного языка как способа оформления AM ограничивает класс решаемых задач. Ниже перечислено несколько важных недостатков; — ограничивается естественный параллелизм алгоритмов; - вследствие использования буферов предвыборки, стека, регистров в общем случае исчезает прямая зависимость выходных параметров от входных, например, нельзя значения всех изменённых в процессе вычислений регистров считать выходными данными; - добавляются проблемы, связанные с реконфигурированием алгоритма для ВС другой архитектуры; - добавляются иные фрагменты кода, отсутствующие в исходном алгоритме, например, операция: a = b c + d на ассемблере может быть реализована следующим образом: mov eaxy[b] imul dword ріг [с] add еах, [d] mov [a],eax { однако операция умножения imul изменила пару регистров EDX:EAX, хотя значение для 32-х битного результата формулы использует только значение регистра еах. Значение регистра edx в данном случае может быть, как проигнорировано при реконфигурировании алгоритма, так и рассмотрено как выходной параметр (так как информация об исходной формуле потеряна).
Что касается программ в машинных кодах и на машинно-ориентированных языках - программный код может быть так реконфигурирован, что в него могут быть включены изменённые фрагменты с точки зрения оптимальной загрузки ФУ во времени [31]. Исходя из вышеперечисленного, необходимо избежать использования какого-либо машинно-ориентированного языка в качестве описания AM ЦУ. Сказанное выше также вносит ограничение на область применения разрабатываемой методики: исключается использование исполняемого кода откомпилированных программ (машинные коды, инструкции какому-либо процессору) в качестве AM ЦУ. 2.2.2- Информационная структура программы
При обсуждении вопроса использования машинно-ориентированных языков в качестве способа описания AM ЦУ было сформулировано несколько недостатков такого подхода. В целом, исключение упомянутых недостатков и поиск подходящего способа описания AM ЦУ — задача сложная. Вопрос, касающийся этой проблемы, до сих пор находится в стадии исследования [15 стр. 325]. Например, как провести такую реорганизацию программы, чтобы минимизировать число используемых переменных, число обменов с медленной памятью и другие преобразования. При выявлении в программах скрытого параллелизма и свойств, необходимых для эффективного его использования, вопросов возникает ещё больше.
Далее будут определены правила описания AM ЦУ. Для этого введём понятие такой структуры программы, которую можно исследовать. Упомянутые выше вопросы связаны со знанием явных и скрытых свойств программ, определяющих их строение, или информационную структуру. Будем использовать определение информационной структуры программы, приведённое в [15 стр. 324], где информационная структура программы есть совокупность сведений о том, как отдельные элементы программы связаны между собой. Понятие алгоритма является в математике первичным и его нельзя строго определить через другие понятия, мы будем использовать информационную структуру программы в качестве модели алгоритма.
В теории параллельных вычислений [15 стр. 327, 3 стр. 19] принято различать отношения отдельных элементов программы между собой описанным далее способом. Если какие-либо действия выполняются непосредственно друг за другом, то связь называется связью по управлению. Если одно действие в качестве аргумента использует результат выполнения
другого действия, то такая связь называется информационной связью. Операторам программы ставятся в соответствие вершины графа с установленными связями. В различных публикациях предлагаются разные способы представления информационных структур программ, различающиеся типом решаемых задач, их детализацией, а, соответственно, сложностью применения; различается также количество и тип используемых графов взаимосвязей. Далее модели алгоритмов будут исследованы в соответствии с методиками, изложенными в [3].
Методика преобразования алгоритмической модели
В качестве заключения и подведения итогов формирования СМ ЦУ по его AM способом трансляции — ниже сформулированы действия, которые необходимо выполнить проектировщику для осуществления такого перехода. Действия разбиты на отдельные группы по этапам, выполняя которые проектировщик может получить структурную модель ЦУ.
Предположим, что задача на проектирование сформулирована с помощью описания AM. Такое описание должно удовлетворять требованиям, и правилам оформления кода, сформулированным ранее в работе (см. раздел "2.2 Алгоритмическая модель "). Этап 1. Анализ описания алгоритмической модели.
На первом этапе необходимо проанализировать приведённое описание AM, выделив классы и количество объектов, соответствующих классов, которые были выявлены в ходе исследования класса программ (см. Приложение 1).
Этап 2. Анализ плана управления блоками ЦУ. На втором этапе выполняется анализ объектов, выявленных на первом этапе. Анализ выполняется с целью: — выяснения структуры автомата управления ЦУ; — выяснения структуры и взаимосвязи блоков ЦУ и его УУ. На этом этапе выясняются взаимосвязи операторов алгоритма по входу и выходу для построения взаимосвязей блоков ЦУ.
Этап 3. Формирование автомата управления.
Для получения автомата управления необходимо руководствоваться следующими правилами: — изначально предполагается, что состояния автомата управления нумеруются как аО, al, ... — в состоянии аО автомат выполняет ожидание сигнала СЕ устройства; — изначально предполагается также, что автомат управления не имеет контуров и имеет всего один простой путь; — последовательно, от одной операции алгоритма к следующей за ней операции внести изменения в автомат управления - в соответствии с правилами построения фрагментов автомата, сформулированных в ходе предыдущего анализа; - необходимо предусмотреть, что никакие две последовательные операции алгоритма не могут выполняться одновременно в одном состоянии автомата; - все пути в орграфе автомата должны быть аналогичны историям реализации программы, а также полный автомат управления не должен содержать никакого пути, отличного от какой-либо истории реализации программы; - граф автомата должен содержать одно состояние aN (точка выхода программы), в котором выставляется сигнал DRDY устройства; - если программа предусматривает несколько точек выхода, то все они должны быть сведены к состоянию aN.
Этап 4. Формирование структурной модели ЦУ.
Для формирования схемного представления ЦУ необходимо руководствоваться следующими правилами: - построить схему УУ по составленному на предыдущем этапе автомату управления, например методом Квайна — Мак-Класки [51 стр. 140] или методом, приведённом в [21 стр. 658], или с помощью объединения фрагментов УУ, разработанных и предложенных выше; - в соответствии с выявленными блоками и их взаимосвязями построить схему ЦУ в целом, соединив взаимосвязанные блоки с УУ;
Анализ описания алгоритмической модели.
При составлении автомата будем использовать правила реализации соответствующих профаммных конструкций (объектов, выявленных в ходе анализа предметной области - класса программ). В приведённом поведенческом описании используются: — одна циклическая конструкция; — один безусловный переход; — две операции присваивания; - одна операция сравнения; - три входных внешних переменных v, / и г; - одна выходная внешняя переменная Result; - одна простая переменная і; - одна группа переменных с индексами а[]. т Анализ плана управления блоками ЦУ.
Таким образом, получаем, что автомат управления и само ЦУ состоит из следующих конструкций: - в автомате управления имеется один контур; - в автомате управления имеется один безусловный переход из состояния с реализацией условного оператора; - также имеются два состояния в автомате управления, выполняющих операции присваивания; - в состав ЦУ входит асинхронный блок сравнения; - четыре блока внешних переменных, три из которых по входу соединены с шиной Din ЦУ, а один по выходу с шиной Dout ЦУ; - блок простой переменной / упрощается, так как переменная является счётчиком цикла; - один блок групповой переменной. Формирование автомата управления. Ниже приведён автомат управления, разработанный в соответствии с приведённым выше описанием AM ЦУ.
Получение структурной модели линейного дискретного рекурсивного фильтра
Как видно из примера, если оператор 2 логически несовместим с оператором 5, то операторы 3 и 4 также логически несовместимы с оператором 6, так как существуют связи 2= 39 2= 4 и 5= б. Эти операторы не могут выполняться при одной реализации алгоритма. То есть при формировании плана параллельного выполнения алгоритма они не должны рассматриваться совместно. Таким образом, появляется необходимость на основе заданных связей логической несовместимости операторов определить несовместимость для всех операторов схемы. То есть появляется необходимость добавления в матрицу L транзитивных связей несовместимости операторов.
Возможна следующая ситуация, представленная в примере: операторы 6 и 8 несовместимы, но существуют связи 6- 10 и 8- 10. Таким образом, оператор 10 нельзя считать логически несовместимым ни с одним из операторов 6 и 8. В то же время операторы 6 и 8 несовместимы с оператором 5, а так как существуют связи 6-+10 и 8- /0, но отсутствует связь 5 10, то оператор 10 несовместим с оператором 5. Таким образом, если оператор а логически несовместим с оператором J3 и существует связь а », то оператор Алогически несовместим с оператором ртолько в том случае, если отсутствует связь р 8. Если же существуют связи а р и /3 , то оператор 8 логически несовместим с оператором у в том случае, если с ним логически несовместимы операторы а и Д и если отсутствует связь у $ [3].
В общем случае при решении вопроса о наличии транзитивных связей логической несовместимости данного оператора 8 необходимо выделить множество Сё = {а19...,аг} всех операторов, которые образуют связи ам 8, //=7,..„г. Для этого необходимо ввести все транзитивные связи. Из данного множества должны быть исключены операторы-входы как не имеющие логически несовместимых операторов. Для каждого оператора а строится множество Вм операторов, логически несовместимых с ним. Тогда формируется множество А8 операторов, логически несовместимых с оператором 8: І В, 9 если г = 1, В1 пВ2 П...П Внесли г 1. При этом учитываются ещё и задающие связи логической несовместимости, которые образует оператор 8. 1. Организуем однократный просмотр строк матрицы 5". 2. В очередной 1-й строке матрицы S1 находим множество {(/,уд)} ненулевых её элементов, то есть множество номеров операторов {Уд}, А=7,...,/7, образующих связи вида jx i. Если і-я строка нулевая, то переходим к анализу (і+1)-й строки. 3. Из множества номеров операторов удэ А=7,...,р, исключаем номера операторов, образующих входы матрицы S , то есть её нулевые строки. В результате образуется множество номеров операторов Ц }9 /и=1,...,г Если {j/4} = 0, переходим к анализу (і+1)-й строки. Если г 7, формируем строку / , объединяя по операции конъюнкции строки матрицы L с номерами уи...,Л при этом элементов выполняются правила: 1 л1 =1 и I"1 Л I 2 Л ...Л Г = 1 ""/„7А д, Ф к! Ф ... Ф kN Если г=1, положим строку равной строке h. 5. Формируем новую строку / в матрице L на основе её старого значения и сформированной строки / с помощью операции дизъюнкции г = і v і по формулам: 1 v 1 = 1 и 6. Применяем шаги 4 и 5 для формирования і-го столбца матрицы L. Ниже (см. Рисунок 2.26) представлена матрица Л логической несовместимости операторов с транзитивными связями, сформированная по описанному выше алгоритму.
Рассматриваемый в текущем разделе пример непоказателен с точки зрения формирования матрицы логической несовместимости операторов с транзитивными связями. Возможны сложные информационно-логические схемы алгоритмов (в том числе и с k-значной логикой). В приложениях (см. Приложение 2) разобрано несколько ситуаций, которые могут встретиться при исследовании связей в информационно-логических схемах алгоритмов.
Матрица I! представляет информацию о том, могут или не могут конкретно взятые операторы выполняться при одной реализации алгоритма, то есть при некотором наборе значений логических переменных. Матрица S" отражает ограничения на порядок выполнения операторов.
Теперь поставим вопрос: можно ли для каждого оператора построить множество тех операторов, внутри которого имеет смысл решать задачу планирования одновременно независимого параллельного выполнения операторов? Для решения этого вопроса необходимо объединить информацию о логической несовместимости операторов и их информационно-логической связи.
Откажемся от свойства ориентированности графа G, считая, что если существует связь а р (задающая или транзитивная), то операторы аир никогда не могут быть выполнены одновременно, параллельно. Достаточно считать, что в графе G существует неориентированная дуга, связывающая вершины а и р. В матрице следования s (см. Рисунок 2.27), соответствующей исследуемому графу, положим (a,P) (Pa) L Матрица S получается из матрицы 5", симметричным отображением её элементов относительно главной диагонали.
