автореферат диссертации по , 05.00.00, диссертация на тему:Методика формирования структурных моделей цифровых устройств по их алгоритмическим моделям

На правах рукописи

Басаргин Александр Сергеевич

МЕТОДИКА ФОРМИРОВАНИЯ СТРУКТУРНЫХ МОДЕЛЕЙ ЦИФРОВЫХ УСТРОЙСТВ ПО ИХ АЛГОРИТМИЧЕСКИМ МОДЕЛЯМ

Специальность 05.12.12 - Системы автоматизации проектирования (промышленность)

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Владимир - 2005

Работа выполнена на кафедре «Вычислигельная техника» Владимирского государственного университета.

Научный руководитель: доктор технических наук, профессор

Дубов Илья Ройдович

Научный консультант: доктор технических наук, профессор

Ланцов Владимир Николаевич

Официальные оппоненты: докюр технических наук, профессор

Жигалов Илья Ев1еиьевич

кандидат технических наук Долинин Александр Геннадьевич

Ведущая организация: Конструкторское бюро радиосвязи,

г. Владимир

Защита состоится "_"_ 2005 I. в__на

заседании диссертационного совета Д.212.025.01 в ауд. 211 корп. 1 Владимирского государственного университета по адресу: 600000, Россия, г. Владимир, ул. Горького, д. 87.

С диссертацией можно ознакомиться в библиотеке Владимирского государственного университета.

Автореферат диссертации разослан "_" _ 2005 г.

Отзывы на авюреферат в двух экземплярах, заверенные печатью, просьба направлять по адресу совета университета: 600000, Россия, г. Владимир, ул. Горького, д. 87, учёному секретарю диссертационного совета Д.212.025.01.

Учёный секретарь

диссертационного совета Д.212.025.01 доктор технических наук, профессор

Р.И. Макаров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В настоящее время рынок изделий цифровой микроэлектроники является одним из наиболее динамично развивающихся. На современном уровне развития изделий цифровой микроэлектроники их проскти-рование невозможно без применения средств САПР. В связи с быстрым моральным старением изделий цифровой микроэлектроники предъявляются высокие требования к скорости, дешевизне и удобству не только процесса их производства, но и процесса их проектирования. г>ю понятие особенно важно в связи с широким внедрением САПР, затраты на создание которых весьма велики. Например, может оказаться, чго затраты на проектирование какою-либо устройства на апробированной элементной базе с помощью ютовой САПР будут значительно меньше затрат на проектирование модификации того же устройава, улучшенной благодаря использованию новой элемениюй базы. Причинами мо-iyr послужить:

- необходимость модификации самой САПР;

- необходимость обучения для повышения квалификации проект иров-щиков.

Сюимость такою улучшения может оказался слишком высокой из-за роста заграг на упомяпуше нововведения. Поэтому методики проектирования изделий микроэлектроники постоянно эволюционируют, находясь на передовом iiane развшия изделий вычислительной техники. Можно выделить основные подходы к методам проектирования:

- проектирование на уровне регистровых передач {RTL);

- повшрнос использование {IP Cores);

- совместное проектирование {HW/SW coclesign);

- системное проекхирование {SLDL).

Диссертационная paöoia посвящена исследованию и развитию методов системного проектирования изделий цифровой микроэлектроники. Пид:-"£[емы САПР системного проектирования поддерживают трансляцию программ на языках высокого уровня, например С++, в описания цифровых устройств (ЦУ) на языках аппаратурного описания, полому применение этих средств существенно ускоряет и упрощает процесс проектирования изделий микроэлектроники. В работе рассмотрены вопросы формирования структурной модели ЦУ по его алгоритмической модели. В настоящее время не существует средств САПР, поддерживающих автоматический метод формирования структурной модели ЦУ по его функциональным моделям. Причина в том, что до сих пор не развиты меюды перехода от теоретических моделей ЦУ к их практической реализации.

Несовершенство средств системною проецирования приводи! к увеличению требований к квалификации специалистов, занимающихся проектированием изделий микроэлектроники. Вследствие роста сложности проектов разработчики вынуждены осваивать новые методики проектирования, численные методы, новые научные теории, например юорию параллельных вычислений. Таким образом, основным недостатком coiipeivMmioro ,працесса-нрос1сгнрования изде-

*ОС НАЦИОНАЛЬНАЯ 1

МЫШНЛ I

ygbffl 1

лий микроэлектроники является высокая трудоёмкость проектирования и получение проектного решения более низкого качества. Например, отсутствие автоматизации на сложных этапах проектирования ЦУ приводит к неэффективному планированию структуры ЦУ, к неэффективному реконфигурнрованию и распараллеливанию блоков ЦУ, к усложнению исследования алгоритма на выявление скрытых взаимосвязей, к неэффективному планированию хода вычислительного процесса при различных критериях оптимизации

Таким образом, исследования по созданию новой методики формирования структурной модели ЦУ по его алгоритмической модели, должны включать в себя две связанные задачи:

- поиск методов и маршрутов проектирования изделий микроэлектроники (математическое обеспечение САПР), коюрые позволят автоматизировать процесс формирования структурной модели ЦУ;

- совершенствование, на основе разработанных методов, информационною и программного обеспечений (ПО) CAI IP цифровой микроэлектроники.

Обе задачи одинаково важны и актуальны, более того сильно взаимосвязаны, поэтому эффективность методики проекшровапия закиси i как от её математического аппарата, 1ак и от поддерживаемого ею маршрута проектирования.

Целью работы является разработка методов, позволяющих автоматизировать процесс формирования структурных моделей цифровых устройств по их алгоритмическим моделям.

Основные задачи исследований.

1 Исследование методологий, математических моделей цифровых устройств, используемых на этапах структурного и функционально-логического проектирования.

2. Разработка методики преобразования ал! оритмических моделей цифровых устройств в их структурные модели.

3. Разработка методов планирования п организации параллельных процессов вычислительных систем для проекшроваипя цифровых устройств.

4. Разработка алгоритмов и программ, реализующих формирование структурной модели цифровою устройства по ею алюршмической модели. Исследование алгоритмов формирования структурной модели цифрового устройства по его алгоритмической модели.

Методы исследования. В работе применялись теоретические и экспериментальные методы исследований. Теоретические методы основаны на положениях вычислительной математики, системного анализа, численных методах параллельных вычислений, теории САПР, теории графов, leopini множеств, ieopim цифровой обработки сигналов, теории параллельных вычислений. Математическое моделирование проводилось как с применением стандартных языков программирования, так и в специализированных пакетах прикладных npoi рамм Эксперимешалъные исследо! .шня были проведены на специально разработанной подсистеме САПР, позволяющей автомашзировать формирование структурных моделей цифровых устройств по их алгоритмически моделям.

* > .•»»: - ч.' щ} •*

Научная новизна работы.

1. Разработан функционально полный базис схемных реализаций алго-ригмических конструкций и методика преобразования шноригмической модели I [У в структурную модель, реализующую последовательное выполнение операций апгоригма.

2. Модифицированы существующие алгоритмы реконфшурирования ин-формационно-логичсских графов алгоритмов для повышения детализации представления параллельных алгоритмов.

3. Разработаны новые и модифицированы существующие алгоритмы планирования вычислительных процессов цифрового устройства, алгоритмы планирования обмена информацией между блоками цифрового устройства.

4. Впервые предложена методика, позволяющая автоматизировать процесс перехода от алгоритмической модели цифровою устройства к его структурной модели, реализующая параллельное выполнение операций am оритма.

Практическая ценность и реализация результатов работы.

Практическая ценность работы состоит

1. В уменьшении времени и упрощении процесса проектирования ЦУ, по сравнению с проектированием па уровне регистровых передач, за счёт использования методов формирования структурных моделей ЦУ.

2. В разработке специального ПО, позволяющего сокрагшь временные и материальные затраты при проектировании ЦУ.

Работа по теме диссертации проводилась на кафедре ВТ ВлГУ, в Центре Микроэлектронного Проектирования и Обучения, в рамках юсзаказа по контрактам ПИОКР № 2875/03, 2876/03. Полученные резулмаш исследований в виде методик и ПО внедрены в виде материалов отчетов по НИР и ОКР, выполненных в рамках госзаказа, и в учебный процесс кафедры ВТ Вл1~У.

Апробация результатов работы.

Основные положения и результаты работы докладывались на следующих совещаниях, семинарах и конференциях'

1. Международная научно-техническая конференция «Новые методологии проектирования изделий микроэлектроники» «New Design Methodologies» (Владимир, 2002 и 2004);

2. Международная научно-техническая конференция «XI Туполевские чтения студентов» (Казань, 2003);

3. 12th International Conference «Mixdcs Design of Integrated Circuits and Systems» (Poland, 2005);

4. НТК нрофессорско-пренодава1ельского состава ВлГУ (2002-2004 г);

5. Научно-практические семинары Центра Микроэлектронного Проектирования и Обучения ВлГУ (2002-2004 г).

Публикации. По материалам диссертационной pa6oibi опубликовано 9 печатных работ, из них одна - в материалах Европейской конференции. Одна стагья напечатана в сборнике научных фудов и 8 тезисов докладов в трудах Международных и Российских научно-технических конференций.

Структура н объём диссертации. Диссертация состоит из введения, четырёх глав и заключения, списка лшературы (108 наименований) и приложений. Общий объём диссертации 191 страница машинописного текста (167 страниц основного текста), в том числе 72 рисунка

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы pañol ы, сформулированы цели и задачи исследования.

В первой главе проведён анализ состояния в области проектирования цифровых устройств (ЦУ). Проанализированы маршруты проектирования в современных коммерческих САПР ЦУ Исследованы преимущества и недостатки существующих методик проектирования ЦУ. Исследованы и проанализированы публикации, посвященные состоянию в области проектирования изделий цифровой микроэлектроники. Было выявлено, что в настоящий момент наиболее слабо развита методика формирования структурных моделей ЦУ по их функциональным моделям (системное проектирование). Было рассмотрено несколько реализаций этой методики. Показано, что проектирование на системном уровне является наиболее перспективным направлением в проектировании изделий цифровой микроэлектроники.

В разделе, посвящённом анализу проблем технологий разработки изделий микроэлектроники, были проанализированы: технология разработки систем на кристалле (CI1K) и технология проектирования современных микропроцессоров. В результате было показано, что при проекшровании СНК наиболее трудоёмкими и ответственными этапами разработки выступают эганы структурного проектирования и верификации соответствия вычислительного устройства (ВУ) заданным алгоритмам функционирования Из всех методов проектирования в настоящее время наиболее распространённым является метод проектирования на уровне регистровых передач. Однако использование этого метода не позволяет справиться с проектированием усложняющихся СНК. В связи с этим внедряются новые эффективные методики проектирования ЦУ, такие как: ускорение разработки с применением крупных библиотечных модулей (IP Cores)-, ускорение с помощью применения совместного проектирования аппаратно-программного обеспечения (Hardware-Software Codesign); ускорение разработки с помощью применения подсистем САПР системного проектирования. В настоящее время направление системного проектирования является наиболее перспективным, но вместе с тем недостаточно развитым. При анализе проблем проектирования современных микропроцессоров были выявлены схожие проблемы: повышение требований к функциональности, усложнение элементной базы, выбор эффективных архитектур вычислительных устройств. Были выявлены и описаны архитектурные ограничения, bjii /пощпе на сложность проектирования и производительность как суперскалярных так и процессоров с длинным командным словом Бып сделан вывод что для решения большинства архитектурных проблем в ос-

новном необходимо решить задачи эффективного распараллеливания вычислений.

В разделе, посвящённому исследованию маршрутов проектирования современных САПР были проанализированы:

- Маршруты проектирования на уровне peí истровых передач на примере Xilinx 1SE 6.2i (и дополнительного математического, информационного и программного обеспечений).

- Маршруты проектирования с использованием языков и средств структурного описания ЦУ на примере SysíemC и Mentor CatapultC. Был сделан вывод, что средство Mentor CatapultC предоставляет наиболее развитый маршрут проектирования, позволяющий осуществить переход от описания алгоритмической модели ЦУ к ei о аппаратурной реализации. Один из основных недостатков упомянутого средства является неполная автоматизация процесса проектирования, при этом накладываются высокие требования к квалификации проектировщика; отсутствуют средства выявления в профаммах скрытого параллелизма и свойств, необходимых для эффективного планирования вычислений в ЦУ.

В результате была поставлена задача работы, сформулирована цель и задачи исследования, направленные на разработку методики, позволяющей автоматизировать формирование структурной модели ЦУ но ею алгоритмической модели.

Во второй главе диссертации предлагается методика формирования сфуктурной модели цифрового устройства но его функциональной модели. Глава включает в себя три раздела: определение свойств и характеристик математических моделей объекта исследования; разработка метода фансляции «как есть» описания алгоритмической модели ЦУ в его структурную модель; разработка метода получения структурной модели ЦУ с помощью планирования и организации параллельных вычислительных процессов.

В главе обоснован выбор описания функциональной модели цифрового устройства. Под функциональной моделью в диссертационной работе понималась модель, отражающая информационные процессы, протекающие в моделируемом объекте, в общем виде устанавливающая зависимость выходных параметров объекта, от его внутренних и входных параметров. Под алгоритмической моделью понимался частный случай функциональной модели, в которой соотношения задаются в виде ашоритма. На способ описания алгоритмической модели был наложен ряд ограничений (класс линейных программ) для автоматизации её исследования, в частности:

1. В профамме может использоваться любое число простых переменных и неременных с индексами.

2. Единственным тииом исполнительною оператора може! бьпь оператор присваивания, правая часть которого есть арифмсшчсскос выражение; допускается любое число таких операюров.

3. Все повторяющиеся операции описываются только с помощью цикла с указанием ipamm изменения параметра цикла; струшура вложенности циклов

может быть произвольной; шаги изменения параметров циклоп всегда равны +1; если у цикла нижняя 1раница больше верхней, то цикл не выполняется

4. Допускается использование любого числа условных и безусловных операторов перехода, передающих управление «вниз» по тексту; не допускается использование побочных выходов из циклов.

5. Все индексные выражения переменных, границы изменения параметров циклов и условия передачи управления задаются, в общем случае, неоднородными формами, линейными как по параметрам циклов, гак и по внешним переменным программы; все коэффициенты линейных форм являются целыми числами.

6. Внешние переменные программы всегда целочисленные, и вектора их значений принадлежат некоторым целочисленным многогранникам; конкретные значения внешних переменных известны только перед началом работы программы и неизвестны в момент её исследования.

Обычно под переменными с индексами понимается весь массив лросшх переменных, объединённых общим идентификатором. При изучении тонкой структуры профаммы такая «групповая» переменная очень неудобна. Поэтому в диссертационной работе массивы рассматривались как группы простых переменных, идентификаторы которых составлены из идентификатора массива и индексов, то есть под переменной с индексами понимался отдельный элемент массива, а не весь массив.

м

В соответствии с наложенными ограничениями на способ описания алгоритмических моделей был разработан функционально полный набор моделей элементов программ и метод- ка трансляции «как есгь» описания алюришиче-ской модели ЦУ в его структурную модель. Был выявлен набор классов элементов программ, которые транслировались в структурную модель ЦУ. целые числа; простые переменные; переменные с индексами; индексы; опера юры при-

сваивания; арифметические выражения; безусловные операюры перехода; условные операторы перехода; циклы; внешние переменные программы.

Для каждою элемента были разработаны схемная реализация и правила формирования управляющих сш налов. Например, для циклической конструкции правила формирования управляющих сигналов приведены на рис. 1, а схемная реализация на рис. 2.

Гнс 2 Схемная реализация машины состояний с управляемым циклом

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

Рассматривались две задачи планирования.

Задана 1. Для заданного комплекса информационно и по управлению вмшмосвязанных задач, заданной структуры ЦУ, а шкже заданного ограничения на допустимое время вычислительного процесса выбран, комплектацию ЦУ минимальной стоимости.

Задача 2. Иайт план решения за минимальное время заданного комплекса информационно и по управлению взаимосвязанных задач на данной комплектации блоков ЦУ.

В работе были использованы методы и алгоритмы анализа и рекоифигу-рирования алюршмов, относящиеся к теории параллельных вычислений. Ряд методов был модифицирован, н частости, для более эффективною распараллеливания задач в ЦУ были введены два дополнительных условия на способ описания информационно-ло! ического I рафа ал гори I ма (ИЛГ'А):

1. У оператора вет вления для каждого значения логической переменной может существовать более одной связи по управлению.

2. Каждому оператору ветвления ставятся в соответствие одна или более информационных связей на блоки, следующие после ветвления в схеме алгоритма.

Ниже приведены отличительные особенности модифицированного мею-да. Оператор Ь\ является входящим оиюснтепьно оператора , если резулыат

ОиКР,) работы, связанной с оператором Р], используется в качестве ар|умен I а /п(Р]). При этом операюры !■] и образуют цепочку информационно связанных операторов. При этом если Ош(Ь])п /"(/у) = 0, то объединение операторов Я) и не приводит к нарушению эквивалентности схемы исходной пр01 раммы.

11оиск каждого из Я) и Я'у операторов можно осуществить с помощью исследования путей на графе алгоритма. Пусть путь на графе:

Т = (Х1,Х2,...Х„),

где Xк - операторы, к = 1,2 п, тогда Хк = , Л',,, = Я'у, то есть рассматриваем каждая пара операторов в пути на графе. Поиск путей на графе должен производиться неоднократно в случае изменения связей на графе.

Для формирования входа и выхода операторов Е необходимо ввести дополнительные правила. Если Р - оператор ветвления, то его результатом необходимо считать объединение множеств Ош(Р1г), где /у, - операторы на всех возможных путях от начала конструкции ветвления до её завершения. Входом оператора ветвления необходимо считать объединение множеств /н(Я'4л), где Я, 1( - операторы на всех возможных путях от начала конструкции ветвления до её завершения.

В результате был разработан алюритм реконфшурирования ИЛГД, основной отличительной особенностью которого является то, что каждый блок ветвления (в 2-значной логике) может иметь множество связей в случае удовлетворения условною выражения и множество связей в случае не удовлетворения условия. Такой метод имеет преимущество но сравнению с базовым методом при реализации специализированных схем управления ЦУ уменьшается число линий (сигналов) управления в аппаратной реализации ЦУ.

Ниже приведены диаграммы, демонстрирующие результат применения описанных выше правил. Тонкие сплошные линии изображают информационные связи, толстые сплошные линии - связи по управлению. Линии, зачёркнутые крестиком, удаляются в результате реконфигурации графа алгоритма. Линии, показанные пунктиром, добавляются. Первая группа диафамм (см. рис. 3) относится к ситуации, когда каждый следующий алгоритмический блок информационно или по управлению не зависит от предыдущего.

Диаграмма на рис. 4 демонстрирует пример реконфигурнровапия последовательности оператор -> условный оператор. Изменение такой последователь-

ноети возможно, если в вычислении логического выражения не используются выходные параметры предшествующего оператора.

Рис 3 Реконфигурировапие ИЛГА (каждый следующий алгоритмический блок информационно или по управлению не зависит от предыдущего)

Рис 4 Реконфигурировапие ИЛГА (в вычислении логического выражения не используются выходные параметры предшествующего оператора) Разработанный метод реконфигурироваиия не поддерживает вариант, когда связи но управлению первой операции ветвления используются в операциях второй операции ветвления (но не в вычислении логического выражения). Ука-

Рш 5 Реконфигурировапие ИЛГА (связи по управлению первой операции ветвления используются в операциях второй операции ветвления)

В работе были также модифицированы следующие алгоритмы:

- Получения транзитивной матрицы следования.

- Получения матрицы логической несовместимости.

- Получения транзитивной матрицы логической несовместимости.

- Поиска полных множеств взаимно независимых операторов (ВНО).

— -- —

ш1 I' 1"

и I4

I1 —

** 1* -- —-

— — I

г

— 1

1 I

- - 1' г 1' 1"

г 1'

I ** 1' I7

Рис. 6 Матрица следования .9 , матрица I. чо?ической несовместимости и транзитивная матрица логической несовместимости !.'

Матрица следования в соо1ветствии с модифицированным алгоршмом анализа ИЛГА, была дополнена признаками групп связей по управлению. В гаком случае информационные связи разных групп указывают на ю, чю образующие их операторы не могут ни при каких условиях выполняться одновременно (параллельно). Таким образом, в шиоритмах получения матрицы логической несовместимости I и матрицы логической несовместимости с транзитивными связями V также учитывается группировка связей по управлению.

Основная характеристика модифицированных алгоритмов состоит в том, что в результате анализа ИЛГА матрица независимое!и операторов М Л"и V. заполнена более плотно по сравнению с магрицей, полученной базовым методом, таким образом, степень параллелизма модифицированных алторитмов повышайся. Это проявляется тем больше, чем больше количество связен по управлению в исходном алторитме. В этом случае на выходе модифициропанно-

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

а) Граф в для неоднородной ВС

Процессор 1

Процессор 2

Процессор 3

6) Один из вариантов диаграммы выполнения операторов

Рис. 7 Распределение работ дли ИЛГ4 с векторными весами вершин

Для составления плана вычислений в ЦУ были использованы методы теории параллельных вычислений. Разработанные методы планирования вычислительных процессов в ЦУ были ориентированы на методы статического распараллеливания по ИЛГА с векторными весами вершин. Поиск точных планов параллельной реализации операторов и оценка этих планов решались для неоднородной ВС. Исходными данными планирования параллельного выполнения алгоритмов являлись результаты, поручаемые при реконфигурировании и анализе ИЛГА. На рис. 7 показан пример планирования выполнения задач в неоднородной ВС для трёх вычислительных блоков ЦУ (Показан ИЛГА и график плотности загрузки трёх блоков ЦУ).

Составляя все возможные варианты реализации алгоритма на построенном таким образом графе можно решить следующие задачи:

- найти план выполнения операторов за минимальное время;

- наши все планы реализации данного частично упорядоченного множества работ, как перебор планов выполнения операторов. Я = Пр,

- привести любой план выполнения операторов к информационному графу для однородной ВС, так что на него будут распространяться все положения, касающиеся планирования работ для однородной ВС (что упрощает процесс составления плана выполнения вычислений в ЦУ);

- найти ранние и поздние сроки выполнения онера юров (peuiHib Задачу 1 и Задачу 2); т

- найти плотности загрузки, загрузки на временных oi резках и минимальные загрузки для блоков ЦУ;

- найги наименьшее время выполнения алгоритма для множества {ni} блоков ЦУ;

- найти достаточный набор {ni} блоков ЦУ для выполнения алгоритма за заданной время;

- выполнить перечисленные выше пункты, когда каждый из операторов может быть выполнен блоком одного и только одного типа из множества к типов;

- оценить минимальное количество ш, г=/..... к блоков ЦУ, необходимых для выполнения данного алгоритма за время Т;

- оценить минимальное время выполнения алгоршма Т набором {ni} блоков ЦУ к типов.

Для решения задачи планирования обмена данными в ЦУ между его блоками были использованы методы теории параллельных вычислений. Задача планирования обмена данными была сведена к упомяну!ой ранее задаче распределения работ и поиска плошос[ей загрузки по графу G . Для этого 1раф G дополнялся вершинами «обмена информацией» для каждой из информационных связей ИЛГА. Базовый меюд планирования обмена данными был модифицирован с тем, чтобы учес!ь ¡руппнровки операций обмена между блоками ввода/вывода (в простейшем случае отличить мультиплексор А от мультиплексора Б). Такие группировки в базовом методе отсутствовали, тк. в методе рассматривалась единственная шина (магистраль) ввода/вывода параллельной ВС. В результат удалось уменьшитъ число сигналов (линий) управления блоками ЦУ (для каждой операции обмена данными) за счёт усложнения базовою метода. Для всех вновь предложенных модификаций были разрабо1аны модели на языках С и Prolog, которые были использованы для проверки теоретических положений, изложенных во второй главе диссертационной работы.

В третьей главе описывается ПО подсистемы САПР ЦУ, реализующее предложенные методы. Разработанное специальное Г10 также использовалось в ходе тестирования и отладки алгоритмов методики. Приведена структурная схема разработанной подсистемы САПР ЦУ.

Четвёртая глава посвящена вопросам практического использования и экспериментального исследования подсистемы САПР формирования струк!урной модели ЦУ и включает следующие разделы:

I. Пример практического использования разработанного информационного. методического и программного обеспечений подсистемы САПР в рамках

задачи выбора комплектации ЦУ минимальной стопмосш по заданному алгоритму.

2. Пример практического использования разработанного информационного, методического и программного обеспечений подсистемы САПР в рамках задачи поиска плана выполнения заданного алгоритма за минимальное время.

3. Пример практического использования разработанного информационного, методического и программного обеспечений подсистемы САПР в рамках задачи получения структурной модели рекурсивного цифрового фильтра переменного порядка.

В главе были показаны примеры решения тестовых задач. Была продемонстрирована сложность применения методики в ручном режиме, заключающаяся в переборе большого количества вариантов решения задачи. Были даны оценки трудоёмкости решения задач при заданных критериях минимизации параметров (характеристик) ЦУ. Было проведено сравнение времени проектирования ЦУ с использованием методики проектирования на уровне регистровых передач и разработанной методики системного проектирования. В резулыате чего были сделаны выводы по эффективности использования разработанной меюдики.

В качестве объекта исследования был вьтбра.ч линейный дискретный фильтр, который описывается разностным уравнением:

Д/-1 N I

п, =-£«л,-,„ „, (1)

1-х I'о

где хи1, ун! -отсчёты входного {хи1} и выходного {ynl J сигналов фильтра соответственно; Ь1 - константы или отсчёты решётчатых функций.

В процессе решения задачи 2 планирования для М^З, N=3 было выполнено:

1. описана модель формулы (1) на языке Pascal (выполнялось вручную);

2 упрощение программной модели и приведение её к классу линейных программ (выполнялось вручную, результат на рис. 8-а);

3. анализ алгоритмической модели (выполнялось автоматизировано с помощью разработанного ПО подсистемы САПР ЦУ), в результате чего были получены отчёты о характеристиках алгоритмической модели, граф-схема алгоритма, рекоифигурированная граф-схема алгоритма, ИЛГА (см рис. 8-6), матрица следования, матрица независимости, множество ВНО.

4. анализ ИЛГА и типов использованных операций алгоритма: умножение, сложение, вычитание, назначение, а также оценка их разрядности (выполнялось вручную).

5. опенка веса каждого типа операций и стоимости блоков ЦУ при реализации их в базисе ПЛИС (выполнялось автоматизировано с помощью средства CORE Generator);

6 планирование обмена информацией при решении задачи построения ЦУ на базе полученных блоков (выполнялось вручную и с помощью рафабо-танного ПО подсистемы САПР ЦУ), создание графика плотности загрузки вычислительных блоков ЦУ (см. рис. 9-а) и модификация ИЛГА (см. рис. 9-6);

7. получение структурной модели ЦУ на основе графика плошости загрузки вычислительных блоков и модифицированного ИЛГА (выполнялось вручную).

а) схема алгоритма

б) модифицированный ИЛГА с операциями обмена данными

Рис. 9 Решение задачи 2 на информационном графе алгоритма

Перечисленные выше шаги были выполнены в течение 2 часов проектировщиком низкой квалификации. При этом было найдена структурная модель фильтра минимальной стоимости (для ограниченного набора блоков ЦУ), выполняющего вычислительную задачу за минимальное время. Во время эксперимента было выполнено 9 итераций по поиску минимальной стоимости структурной модели, при этом 6 из них были отвергнуты по критерию минимизации стоимости ЦУ.

Следует заметить, что в практике проектирования ЦУ на уровне peí петровых передач перед проектировщиками не стаи шея задача поиска минимальной стоимости проектного решения. Проектировщик высокой квалификации на проектирование и верификацию фильтра (М=3 и JV=J?) тратит около 6 часов на одну итерацию. Таким образом, разработанная методика справляется с поставленной ранее задачей проектирования цифрового фильтра минимальной стоимости в = Ра'! быстрее. При увеличении сложности фильтра на один порядок

формирование структурной модели устройства с помощью разработанной методики будет выполнено в течение 3-4 часов (за счёт автоматизации большинства рутинных задач), в то время как сложность и время проектирования фильтра вручную возрастёт более чем на порядок.

В заключении приведены основные результаты работы.

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

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие результаты:

1. Проведено исследование состояния в области современных САПР 1 цифровых устройств, в ходе которою была установлена недостаточная проработанность методов формирования функциональной модели цифрового устройства по его структурной модели.

2. Реализована подсистема САПР, позволяющая автоматизировать переход от представления устройства в виде алгоритмической модели к его структурной модели. Данная подсистема представляет собой совокупность про-траммных модулей, написанных на языке С и SWI-Prolog, что позволяет достичь легкой переносимости данной подсистемы между различными платформами.

3. Предложена и реализована методика перехода от описания устройства в виде алгоритмической модели к его структурной модели Разработано информационное обеспечение подсистемы САПР, предназначенное для применения данной методики.

4. Модифицированы существующие и предложены новые методы планирования и организации параллельных процессов вычислительных систем для проектирования цифровых устройств.

5. Разработаны алгоритмы, реализующие переход от шпоритмической модели устройства к его структурной модели. Алгоритмы решают задачу построения структуры цифрового устройства по двум критериями - минимизация размера ЦУ и минимизация времени решения задачи в ЦУ.

6 Разработано информационное обеспечение и программное обеспечение для формирования структурных моделей цифровых устройств, позволяющие сократить количество ошибок, возникающих в процессе проект ирования цифровых устройств, что в целом уменьшает время разработки.

7. Показана применимость разрабо!энной методики на ряде тестовых примеров.

8. Даны оценки трудоёмкости решения задач при заданных критериях минимизации параметров (характеристик) ЦУ, проведено сравнение времени проектирования ЦУ с использованием методики проектирования на уровне ре- 4 гистровых передач и разработанной методики системного проектирования в результате чего были сделаны выводы об эффективности использования разработанной методики.

Основное содержание диссертации опубликовано следующих работах:

1. Басаргин А. С., Коломиец И. А., Программные модели прямого канала CDMA // Новые методологии проектирования изделий микроэлектроники. Материалы 3-й международной научно-технической конференции г. Владимир. 1011 декабря 2004. / ВлГУ - Владимир, 2004. 86-88 с.

2. Басаргин А. С., Коломиец И. А., Учебная подсистема САПР функционально-логического проектирования // Новые методологии проектирования изделий микроэлектроники. Ма1ериалы 3-й международной научно-технической конференции г Владимир 10-1! декабря 2004 / ВлГУ - Владимир, 2004. 26-28, 232 е.,

3. Басаргин А. С., Преобразование недетерминированно! о фафа информационной зависимости параллельного алгоритма // Новые методологии проектирования изделий микроэлектроники: Материалы международной научно-технической конференции. - Владимир: ВлГУ, 2002. *

4. Басаргин А. С., Разработка подсистемы САПР для перехода от поведенческих моделей описания аппаратуры к представлению, ориентированному на аппарашую реализацию // Перспективные 1ехноло1ИИ в средствах передачи информации. Ма1ериалы 5-ой международной научно-технической конферен- ' ции. - Владимир: Связьоценка, 2003. - 270-271 с.

5. Басаргин А. С., Синтез amiaparypnoi о описания устройств в базисе ПЛИС по поведенческим моделям на высокоуровневых языках // Новые методологии проектирования изделий микроэлеюроники. Материалы 3-й международной научно-технической конференции г. Владимир. 10-11 декабря 2004. / ВлГУ -Владимир, 2004. 29-30, 232 е.

6. Калыгина Л. А., Басаргин А С., Мстодоло! ия перехода oi поведенческих моделей описания аппаратуры к представлению, ориентированному на аппаратную реализацию // Информационные технологии проектирования элек-

тронных средств: Материалы научно-технической конференции «Туиолевские чтения студенюв». - Казань, 2003.

7. Коблов Е. Б., Коломиец И. А., Заболотько М.А., Басаргин А. С., Оценка эффективности алгоритмов линейного предсказания в кодеках сетей 3G II Новые методологии проектирования изделий микроэлектроники. Материалы 3-й международной научно-технической конференции г. Владимир. 10-11 декабря 2004. / ВлГУ - Владимир, 2004. 177-179,245 с.

8. Коломиец И. А., Басаргин А. С., Состав библиотеки моделей алгоритмов для построения систем кодирования речи И Новые методологии проектирования изделий микроэлектроники. Материалы 3-й международной научно-технической конференции г. Владимир. 10-11 декабря 2004. / ВлГУ - Владимир, 2004. 173-176, 244 с.

9. Basargin Alexander, Methodology of transition functional model of the digital device to its hardware description in basis of integrated schemes // 12th International Conference. Mixed Design of Integrated Circuits and Systems. Poland. Krakow, 22-25 June, 2005.

ЛР № 020275. Подписано в печать 30.06.05. Формат 60x84/16. Бумага для множит, техники. Гарнитура Тайме. Печать офсетная. Усл. печ. л.0,93. Уч.-изд. л. 0,97. Тираж 100 экз. Заказ /46-¿005п Издательство Владимирского т осударет венного университета 600000, Владимир, ул. I орькото, 87

ИИ 4 7 2 6

РНБ Русский фонд

2006-4 15682

» *

I

ПЕРЕЧЕНЬ ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ И ТЕРМИНОВ.

ВВЕДЕНИЕ.

1. АНАЛИЗ СОСТОЯНИЯ В ОБЛАСТИ ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ.

1.1. Анализ проблем технологии разработки систем на кристалле.

1.2. Анализ проблем проектирования современных микропроцессоров.

1.3. Исследование структуры САПР, обеспечений САПР.

1.4. Место методики в процессе проектирования ЦУ.

1.4.1. Исследование уровней и задач проектирования ЭВМ и ЦУ.

1.4.2. Исследование маршрута проектирования, используемого в современной САПР ПЛИС.

1.4.3. Исследование маршрута проектирования на RTL уровне.

1.4.4. Исследование маршрута проектирования с использованием языков структурного описания ЦУ.

1.4.5. Исследование математических моделей процесса проектирования.

1.5. Постановка задачи исследования.

1.6. Выводы по главе.

2. РАЗРАБОТКА МЕТОДИКИ, РЕАЛИЗУЮЩЕЙ ПЕРЕХОД ОТ АЛГОРИТМИЧЕСКОЙ МОДЕЛИ ЦУ, К ЕГО СТРУКТУРНОЙ МОДЕЛИ.

2.1. Определение свойств и характеристик математических моделей.

2.2. Алгоритмическая модель ЦУ.

2.2.1. Применение машинно-ориентированных языков программирования в качестве алгоритмической модели.

2.2.2. Информационная структура программы.

2.2.3. Ограничения алгоритмической модели ЦУ.

2.2.4. Выбор способа представления алгоритмических моделей ЦУ.

2.3. Структурная модель устройства.

2.3.1. Исследование языков структурного описания ЦУ.

2.4. Планирование вычислительных процессов в ЦУ.

2.5. Неэффективный способ. Трансляция «как есть».

2.5.1. Структурная организация ЦУ.

2.5.2. Набор моделей элементов класса линейных программ.

2.5.3. Методика преобразования алгоритмической модели.

2.5.4. Трансляция тестовой задачи.

2.6. Планирование и организация параллельных процессов ВС.

2.6.1. Условия планирования и организации вычислительных процессов в ЦУ.

2.7. Информационная структура алгоритмической модели ЦУ класса линейных программ.

2.7.1. Модифицированный метод реконфигурирования графов алгоритмов.

2.7.2. Модифицированные алгоритмы исследования связей.

2.8. Распределение работ в вычислительных системах по информационно-логическим графам алгоритмов.

2.8.1. Решение задач 1 и 2 на информационно-логическом графе.

2.9. Планирование обмена информацией по реконфигурированным информационно-логическим графам алгоритмов.

2.10. Правила формирования структурной модели ЦУ.

2.10.1. Алгоритм построения структурной модели ЦУ.

2.11. Выводы по главе.

3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ФОРМИРОВАНИЯ СТРУКТУРНОЙ МОДЕЛИ ЦУ ПО ЕГО АЛГОРИТМИЧЕСКОЙ МОДЕЛИ.

3.1. Структурная схема разработанной подсистемы САПР ЦУ.

3.2. Выводы по главе.

4. ИССЛЕДОВАНИЕ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ.

4.1. Решение задач 1 и 2 на информационно-логическом графе.

4.2. Получение структурной модели линейного дискретного рекурсивного фильтра.

4.2.1. Аналитическая формула.

4.2.2. Программа на языке Pascal с циклами.

4.2.3. Программа на языке Pascal без циклов.

4.2.4. Анализ программы.

4.2.5. Исследование реконфигурированного графа алгоритма.

4.2.6. Планирование обмена информацией при решении задач построения ЦУ.

4.2.7. Построение структурной модели ЦУ.

4.3. Выводы по эффективности использования разработанной методики

4.4. Выводы по главе.

Актуальность работы.

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

- необходимость модификации самой САПР;

- необходимость обучения для повышения квалификации проектировщиков.

Стоимость такого улучшения может оказаться слишком высокой из-за роста затрат на упомянутые нововведения. Поэтому методики проектирования изделий микроэлектроники постоянно эволюционируют, находясь на передовом этапе развития изделий вычислительной техники. Можно выделить основные подходы к методам проектирования:

- проектирование на уровне регистровых передач (RTL);

- повторное использование (IP Cores);

- совместное проектирование (HW/SW codesign);

- системное проектирование (SLDL).

Диссертационная работа посвящена исследованию и развитию методов системного проектирования изделий цифровой микроэлектроники. Подсистемы САПР системного проектирования поддерживают трансляцию программ на языках высокого уровня, например С++, в описания цифровых устройств (ЦУ) на языках аппаратурного описания, поэтому применение этих средств существенно ускоряет и упрощает процесс проектирования изделий микроэлектроники. В работе рассмотрены вопросы формирования структурной модели ЦУ по его алгоритмической модели. В настоящее время не существует средств САПР, поддерживающих автоматический метод формирования структурной модели ЦУ по его функциональным моделям. Сложность такого перехода заключается в различии подходов, используемых на этапах теоретической проработки и практической реализации ЦУ. Использование теоретического алгоритма подразумевает последовательное выполнение описанных в алгоритме операций. Самым нижним уровнем при этом представляется код программы с набором последовательных инструкций одному процессору. В то время как использование языка проектирования аппаратуры подразумевает описание многопроцессной (многопроцессорной) архитектуры ЦУ с одновременным переключением (функционированием) блоков ЦУ.

Несовершенство средств системного проектирования приводит к увеличению требований к квалификации специалистов, занимающихся проектированием изделий микроэлектроники. Проектировщикам необходимо повышать квалификацию не только в области проектирования ЦУ, но и в других областях, например, в области параллельных вычислений. Таким образом, основным недостатком современного процесса проектирования изделий микроэлектроники является высокая трудоёмкость проектирования и получение проектного решения более низкого качества. Например, отсутствие автоматизации на сложных этапах проектирования ЦУ приводит к неэффективному планированию структуры ЦУ, к неэффективному реконфигурированию и распараллеливанию циклов, к усложнению 7 исследования алгоритма на выявление скрытых взаимосвязей, к неэффективному планированию хода вычислительного процесса при различных критериях оптимизации.

Таким образом, исследования по созданию новой методики формирования структурной модели ЦУ по его алгоритмической модели, должны включать в себя две связанные задачи:

- поиск методов и маршрутов проектирования изделий микроэлектроники (математическое обеспечение САПР), которые позволят автоматизировать процесс формирования структурной модели ЦУ;

- совершенствование, на основе разработанных методов, информационного и программного обеспечений (ПО) САПР цифровой микроэлектроники.

Обе задачи одинаково важны и актуальны, более того сильно взаимосвязаны, поэтому эффективность методики проектирования зависит как от её математического аппарата, так и от поддерживаемого ею маршрута проектирования.

Целью работы является исследование и развитие методов автоматизации проектирования цифровых устройств по их алгоритмическим моделям, разработка новых методов, позволяющих автоматизировать процесс формирования структурных моделей цифровых устройств по их алгоритмическим моделям. Для достижения поставленной цели в диссертационной работе решались следующие основные задачи:

1. Исследование методологий, математических моделей цифровых устройств, используемых на этапах структурного и функционально-логического проектирования.

2. Разработка моделей элементов программ и методики преобразования алгоритмической модели в структурную модель.

3. Разработка методов планирования и организации параллельных процессов вычислительных систем для проектирования цифровых устройств.

4. Разработка алгоритмов и программ, реализующих формирование структурной модели цифрового устройства по его алгоритмической модели. Исследование алгоритмов формирования структурной модели цифрового устройства по его алгоритмической модели.

Методы исследования. В работе применялись теоретические и экспериментальные методы исследований. Теоретические методы основаны на положениях вычислительной математики, системного анализа, численных методах параллельных вычислений, теории САПР, теории графов, теории множеств, теории цифровой обработки сигналов, теории параллельных вычислений. Математическое моделирование проводилось как с применением стандартных языков программирования, так и в специализированных пакетах прикладных программ. Экспериментальные исследования были проведены на специально разработанной подсистеме САПР, позволяющей автоматизировать формирование структурных моделей цифровых устройств по их алгоритмически моделям.

Научная новизна работы. Новые научные результаты, полученные в работе, состоят в следующем.

1. Разработан функционально полный базис схемных реализаций алгоритмических конструкций и методика преобразования алгоритмической модели цифрового устройства в его структурную модель, реализующую последовательное выполнение операций алгоритма.

2. Модифицированы существующие алгоритмы реконфигурирования информационно-логических графов алгоритмов для повышения детализации представления параллельных алгоритмов.

3. Разработаны новые и модифицированы существующие алгоритмы. планирования вычислительных процессов цифрового устройства, 9 алгоритмы планирования обмена информацией между блоками цифрового устройства.

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 тезисов докладов в трудах Международных и Российских научно-технических конференций.

Структура работы. Диссертация состоит из введения, четырёх глав и заключения, списка литературы и приложений. Общий объём диссертации

4.4. Выводы по главе

1. Описан процесс тестирования, проведённый для подтверждения работоспособности разработанной методики и реализующей её подсистемы САПР ЦУ.

2. Рассмотрен пример реального ЦУ, на котором апробировалась разработанная методика. Применение разработанной подсистемы САПР позволяет в десятки раз сократить время, затрачиваемое на проектирование ЦУ (по сравнению с ручным проектированием). Данный пример показал работоспособность разработанной методики, алгоритмов, информационного и программного обеспечения подсистемы САПР.

3. В ходе тестирования была рассмотрена задача поиска плана решения за минимальное время заданного комплекса информационно и по управлению взаимосвязанных задач на данной комплектации блоков

ЦУ.

4. В ходе тестирования также была рассмотрена задача поиска для заданного комплекса информационно и по управлению взаимосвязанных задач, заданной структуры ЦУ, а также заданного ограничения на допустимое время вычислительного процесса с выбором комплектации ЦУ минимальной стоимости.

5. Была продемонстрирована сложность применения методики в ручном режиме, заключающаяся в переборе большого количества вариантов решения задачи. Были даны оценки трудоёмкости решения задач при заданных критериях минимизации параметров (характеристик) ЦУ. Было проведено сравнение времени проектирования ЦУ с использованием методики проектирования на уровне регистровых передач и разработанной методики системного проектирования. В результате чего были сделаны выводы по эффективности использования разработанной методики.

ЗАКЛЮЧЕНИЕ

Проведенное исследование в области методов и средств проектирования цифровых устройств показало необходимость развития средств САПР высокоуровневого проектирования цифровых устройств. Это связано с высокими темпами развития современной цифровой аппаратуры, появлением новых подходов к проектированию цифровых устройств: реконфигурируемые устройства, системы на кристалле и так далее. Необходимость упора именно на высокоуровневое проектирование объясняется повышенной сложностью современных цифровых устройств (исчисляется миллионами логических вентилей), что делает практически невозможным моделирование поведения всего устройства даже на уровне регистровых передач.

На данный момент в современных системах САПР имеется достаточное количество хорошо отработанных методов проектирования и верификации цифровых устройств на системном уровне. Также хорошо развиты методы формирования конфигурации устройства по его модели на уровне регистровых передач. Однако очень плохо развиты методы формирования СМ ЦУ по его AM. Основными задачами, решенными в процессе выполнения работы, были: разработка методики формирования СМ ЦУ по его AM, а также разработка пакета прикладных программ, являющегося подсистемой САПР, предназначенной для реализации данного подхода.

В диссертационной работе были получены следующие основные результаты:

1. Проведено исследование состояния в области современных САПР цифровых устройств, в ходе которого была установлена недостаточная проработанность методов формирования функциональной модели цифрового устройства по его структурной модели.

2. Реализована подсистема САПР, позволяющая автоматизировать переход от представления ЦУ в виде AM к его СМ. Данная подсистема представляет собой совокупность программных модулей, написанных на языке С++ и SWI-Prolog, что позволяет достичь легкой переносимости данной подсистемы между различными платформами.

3. Предложена и реализована методика перехода от описания ЦУ в виде AM к его СМ. Разработано информационное обеспечение подсистемы САПР, предназначенное для применения данной методики.

4. Модифицированы существующие и предложены новые методы планирования и организации параллельных процессов вычислительных систем для проектирования цифровых устройств.

5. Разработаны алгоритмы, реализующие формирование СМ ЦУ по его AM. Алгоритмы решают задачу построения СМ ЦУ по двум критериями - минимизация размера ЦУ и минимизация времени решения задачи в ЦУ.

6. Разработано информационное обеспечение и программное обеспечение для формирования структурных моделей цифровых устройств, позволяющие сократить количество ошибок, возникающих в процессе проектирования цифровых устройств, что в целом уменьшает время разработки.

7. Показана применимость разработанной методики на ряде тестовых примеров.

8. Даны оценки трудоёмкости решения задач при заданных критериях минимизации параметров (характеристик) ЦУ, проведено сравнение времени проектирования ЦУ с использованием методики проектирования на уровне регистровых передач и разработанной

149 методики системного проектирования, в результате чего были сделаны выводы об эффективности использования разработанной методики.

Проведено исследование предложенных методик и программного обеспечения на примерах, в ходе решения которых рассматривалось получение структурных моделей с использованием двух критериев оптимизации — минимизация размера ЦУ и минимизация времени решения задачй в ЦУ. Использование методики существенно уменьшает время, затрачиваемое на разработку эффективных цифровых устройств.

СПИСОК ИСПОЛЬЗОВАННЫХ ИЛЛЮСТРАЦИЙ

Рисунок 1.1 Рост производительности труда при разработке СНК.18

Рисунок 1.2 Маршрут проектирования на уровне регистровых передач.30

Рисунок 1.3 «Идеальный» маршрут системного проектирования.31

Рисунок 1.4 Маршрут проектирования с использованием SystemC.32

Рисунок 1.5 Маршрут проектирования с использованием CatapultC.34

Рисунок 1.6 Этап составления плана выполнения алгоритма в ЦУ.35

Рисунок 1.7 Этап выбора наиболее эффективной реализации из протестированных.36

Рисунок 2.1 Примеры представления структурной модели ЦУ.50

Рисунок 2.2 Управление блоками ЦУ, полученными в результате трансляции.57

Рисунок 2.3 Пример схемного представления целого числа (константы).59

Рисунок 2.4 Схемное представление простой переменной.60

Рисунок 2.5 Схемное представление группы переменных.62

Рисунок 2.6 Пример асинхронного блока вычисления арифметического выражения.64

Рисунок 2.7 Пример синхронного блока вычисления арифметического выражения.65

Рисунок 2.8 Разбиение несимметричного арифметического выражения.66

Рисунок 2.9 Пример реализации логики управления оператором присваивания.68

Рисунок 2.10 Пример формирования управляющих сигналов для оператора присваивания.69

Рисунок 2.11 Машина состояний с безусловными переходами.69

Рисунок 2.12 Схемная реализация машины состояний с безусловными переходами.70

Рисунок 2.13 Машина состояний с управляемым циклом.72

Рисунок 2.14 Схемная реализация машины состояний с управляемым циклом.73

Рисунок 2.15 Пример схемной реализации внешней переменной.74

Рисунок 2.16 Автомат управления последовательным поиском.80

Рисунок 2.17 Взаимосвязь УУ и блоков ЦУ последовательного поиска.80

Рисунок 2.18 Место диспетчера в ходе выполнения параллельного процесса.83

Рисунок 2.19 Реконфигурирование ИЛГА по правилам 4,6,8 (каждый следующий алгоритмический блок информационно или по управлению не зависит от предыдущего).95

Рисунок 2.20 Реконфигурирование ИЛГА по правилам 5,7,8 (в вычислении логического выражения не используются выходные параметры предшествующего оператора).96

Рисунок 2.21 Реконфигурирование ИЛГА (связи по управлению первой операции ветвления используются в операциях второй операции ветвления).97

Рисунок 2.22 Применение методики распараллеливания информационной структуры алгоритма.98

Рисунок 2.23 Матрица следования & .100

Рисунок 2.24 & : множество задающих и транзитивных связей в матрице следования.101

Рисунок 2.25 Матрица L логической несовместимости операторов (указаны задающие связи).103

Рисунок 2.26 Матрица Е логической несовместимости операторов с транзитивными связями.105

Рисунок 2.27 Формирование матрицы независимости М.107

Рисунок 2.28 Распределение работ для информационного графа с векторными весами вершин.110

Рисунок 2.29 Граф G*.111

Рисунок 2.30 Построение графа G*.119

Рисунок 3.1 Структурная схема разработанной подсистемы САПР ЦУ.125

Рисунок 4.1 Граф G (а) и i-e подграфы (б, в, г).114

Рисунок 4.2 Решение задачи 1 на информационно-логическом графе.127

Рисунок 4.3 Решение задачи 1 при закреплении операторов за типами блоков ЦУ.128

Рисунок 4.4 Решение задачи 2 при закреплении операторов за типами блоков ЦУ.130

Рисунок 4.5 Результат реконфигурирования графа алгоритма.138

Рисунок 4.6 Алгоритм и его реконфигурированный граф G для FIR-фильтра.139

Рисунок 4.7 Решение задачи 1 на информационном графе.140

Рисунок 4.8 Решение задачи 2 на информационном графе.142

Рисунок 4.9 Структурная модель линейного дискретного рекурсивного фильтра.143

1. Алексеев О. В., Головков А. А. Автоматизация проектирования радиоэлектронных средств. М.: «Высшая школа», 2000. - 479 с.

2. Баранов С. И., Майоров С. А., Сахаров Ю. П. Селютин В. А.

3. Автоматизация проектирования цифровых устройств — JL: Судостроение, 1979, 261с.

4. Барский А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь. 1990. - 256 с.

5. Барский А. Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. - 192.

6. Басаргин А. С., Преобразование недетерминированного графа информационной зависимости параллельного алгоритма // Новые методологии проектирования изделий микроэлектроники: Материалы международной научно-технической конференции. Владимир: ВлГУ, 2002.

7. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989.

8. Воеводин В. В. Информационная структура алгоритмов. М.: МГУ, 1997.-139 с.

9. Воеводин В. В. Массивный параллелизм и декомпозиция алгоритмов // ЖВМ и MB. 1995. - Т. 35. №6. - с. 988-996.

10. Воеводин В. В. Математические основы параллельных вычислений. — М.: МГУ, 1991.-345 с.

11. Воеводин В. В. Параллельные структуры алгоритмов и программ. — М.: ОВМ АН СССР. 1987. 148 с.

12. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 с.

13. Воеводин Вл. В. Суперкомпьютеры: вчера, сегодня, завтра // Наука и жизнь. 2000. - №3. - с. 38-53.

14. Воеводин Вл. В. Теория и практика исследования параллелизма последовательных программ // Программирование. 1992. - №3. с. 38-53.

15. Гольденберг JI. М. и др. Цифровая обработка сигналов: Справочник/ Л.М.Гольденберг, Б.Д.Матюшкин, М.Н.Поляк. М.: Радио и связь, 1985.-312 с.

16. Гук М. Процессоры Pentium II, Pentium Pro и просто Pentium СПб: ЗАО «Издательство «Питер», 1999.-288 с.

17. Данчул А. Н., Полуян JI. Я. Разработка САПР. В 10 кн. Кн. 2.

18. Системотехнические задачи создания САПР: Практ. пособие; Под ред. А.В. Петрова М.: Высш. шк., 1990 - 144 с.

19. Дж. Ф. Уэйкерли. Проектирование цифровых устройств. М.: Постмаркет, 2002. 544 с.

20. Джеффи Берт. Новые компьютеры для масштабируемых архитектур. // PC WEEK / RE №48, 28 декабря, 2004.

21. Долинин А. Г. Развитие программного и математического обеспечения САПР нелинейных аналоговых устройств. — Канд. диссертация. Владимир, ВлГТУ, 1996, - 200 с.

22. Ильин В. Н., Фролкин В. Т. Автоматизация схемотехнического проектирования. М.: Радио и связь, 1987. - 368 с.

23. Ильин В. Н., Фролкин В. Т., Бутко А. И. Автоматизация схемотехнического проектирования: Учеб. пособие для вузов: Под ред. В. Н. Ильина. М.: Радио и связь, 1987. - 368с.: ил.

24. Калыгина JI. А., Лобачев Г. А. Реализация цифрового демодулятора k FM сигналов в базисе ПЛИС фирмы Xilinx, Сборник научных статей

25. Ташкент: НПО «Кибернетика» АН РУз, 2002 г.

26. Калыгина JI. А., Лобачев Г. А. Реализация цифрового демодулятора FM сигналов в базисе ПЛИС фирмы Xilinx, Данные информация и ихобработка: Сборник научных статей/Под ред. С.С. Садыкова, Д.Е. Андрианова М.: Горячая линия - Телеком, 2002. - С. 219 - 224.

27. Коблов Е. Б., Коломиец И. А., Заболотько М.А., Басаргин А. С.,

28. Корнеев В. В., Киселёв А. В. Современные микропроцессоры. — 3-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2003. - 448 с.

29. Корячко, Курейчик В. М., Норенков И. П. Теоретические основы САПР: Учебник для вузов. — М.: Энергоатоимздат, 1987. 400 с.

30. Куликов К. В. Выбор многократно используемых ядер при проектировании систем на одном кристалле // Новые методологии проектирования изделий микроэлектроники материалы международной научно-технической конференции. Владимир: Владим. гос. ун-т, 2003.

31. Куликов К. В. Создание многократно используемых блоков для проектирования систем на одном кристалле // Новые методологиипроектирования изделий микроэлектроники материалы международной научно-технической конференции. Владимир: Владим. гос. ун-т, 2002.

32. Ланцов В. Н. Проектирование ПЛИС на VHDL. Владимир, ВлГУ, 2000, 121с.

33. Легалов А. И. Параллельное программирование. Стратегии управления в вычислительных системах и языках программирования. http://www.softcraft.ru/parallel/strat/strat.shtml

34. Лобачев Г. А. Методика формирования моделей цифровых устройств в САПР ПЛИС. Канд. Диссертация. - Владимир, ВлГУ, 2004, - 165 с.

35. Лобачев Г. А. Сравнение характеристик ПЛИС Xilinx и ALTERA, Международная научно-техническая Конференция «Новые методологии проектирования изделий микроэлектроники» «New design methodologies». Владимир, 2003 г.

36. Лобачев Г. А., Плотников П. В. Подсистема САПР устройств обработки сигналов, Обработка информации: методы и системы /Под ред. С.С. Садыкова, 2003 188 -194с.

37. Лобачев Г. А., Плотников П. В. Архитектура подсистемы САПР устройств обработки сигналов, Международная научно-техническая Конференция «Новые методологии проектирования изделий микроэлектроники» «New design methodologies». Владимир, 2003.

38. Лоусон С. Микросхемы FPGA с ядром PowerPC // Computerworld, №32 2000.

39. Михайлов А. П., Самарский А. А. Компьютеры и жизнь. — М.: Педагогика, 1987. — 128 с.

40. Мищенко В. А., Городецкий Л. М., Гурский Л. И.

41. Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных микросхем. М.: Радио и связь, 1988.-272 с.

42. Мур Г. Ничто не бесконечно, но предел можно отодвинуть! // Chip News. 2003. №2.

43. Новиков Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2002. 304 с.

44. Норенков И. П., Маничев В. Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры: Учеб. Пособие для вузов. М.: Высш. Школа, 1983. - 272 с.158

45. Поляков А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры. М.: COJIOH-Пресс, 2003. - 320 с.

46. Пратт Т., Зелковиц М. Языки программирования. 4-е издание. -СПб.: Питер, 2002. 688 с.

47. Садыхов P. X. Татур М. М. Технический сервис однородных вычислительных устройств. — Мн.: Университетское, 2001. 279 с.

48. Самофалов К. Г., Луцкий Г. М. Основы теории многоуровневых конвейерных систем. — Москва: Радио и связь, 1989. 272 с.

49. Седжвик Роберт. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер с англ./Роберт Седжвик. СПб: ООО «ДиаСофтЮП», 2002.-496 с.

50. Седжвик Роберт. Фундаментальные алгоритмы на С++.

51. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. СПб.: ООО «ДиаСофтЮП», 2002. - 688 с.

52. Сергиенко А. М. VHDL для проектирования вычислительных устройств. К ЧП «Корнейчук», ООО «ТИД «ДС», 2003 208с.

53. Стешенко В. Шипулин С. Храпов В. Тенденции и перспективы развития ПЛИС и их применение при проектировании аппаратуры

54. ЦОС // Компоненты и технологии, №8, 2000

55. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 1. Алгоритмы, элементная база, способы реализации // Компоненты и технологии, №3, 2000

56. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 2. Некоторые полезные мелочи, о• которых почти никто никогда не пишет, опасаясь прослыть любителем банальных фактов // Компоненты и технологии, №4, 2000

57. Стешенко В. Школа схемотехнического проектирования устройствобработки сигналов. Занятие 3. Интерфейсы передачи данных исопряжение устройств // Компоненты и технологии, №5, 2000159

58. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 4. Уровни, логика и быстродействие // Компоненты и технологии, №6, 2000.

59. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 5. Стандарты, уровни, сопряжение// Компоненты и технологии, №7, 2000.

60. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 6. Реализация вычислительных устройств на ПЛИС // Компоненты и технологии, №8, 2000.

61. Стешенко В. Школа схемотехнического проектирования устройств обработки сигналов. Занятие 8. Средства визуальной разработки цифровых автоматов // Компоненты и технологии, №2, 2001.

62. Танненбаум Э. Архитектура компьютера. 4-е издание. — СПб.: Питер, 2002.-704 с.

63. Угрюмов Е. П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2000. - 528 с

64. Abramov S. М., Adamowitch A. I., Nesterov I. A., Pimenov S. Р., Shevchuck Yu. V. Autotransformation of evaluation network as basis for automatic dynamic parallelizing // NATUG'1993 Spring Meeting "Transputer: Research and Application", May 10-11, 1993.

65. Barrie Mullins. Xilinx Teams with Optos // Xcell journal. 2004. V. 48. -pp. 85-87.

66. Chris Sullivan. Codesign Comes to Virtex-II Pro and MicroBlaze Systems // Xcell journal. 2002. V. 44. - pp. 36-39.

67. Clare, Computing In Reconfigurable Logic // New Design Methods for Reconfigurable Hardware, Celoxica. Aug., 2002

68. Clare, Handel-C for Hardware Design // New Design Methods for Reconfigurable Hardware, Celoxica. Aug., 2002

69. David Maliniak, Design Languages Vie For System-Level Dominance // New Design Methods for Reconfigurable Hardware, Celoxica. Oct., 2001

70. Dino Caporossi. Use ASIC Design Methodology for Your Next FPGA Design // Xcell journal. 2004. V. 48. - pp. 48-51.

71. Don Davis. Architectural Synthesis. Unleasing the Power of FPGA System-Level Design // Xcell journal. 2002. V. 44. - pp. 30-34.

72. Evgeny Galichev Universal Compact Low-Power Protoboard with Reconfigurable Architecture for Digital Signal Processing, Microelectronic and Microsystems Design REASON Student Contest 4th Electronic Circuits and Systems Conference 2003

73. Hitesh Patel. Better. Stronger. Faster. Virtex-II Pro FPGAs offer marked performance advantages over a completing device // Xcell journal. 2004. V. 49. - pp. 53-56.

74. Kai Hwang, Faye A. Briggs. Computer Architecture and Parallel Processing, McGRAW-HILL International editions, Computer Science Series, 1989.-846.

75. Kent Shaw. Wind River Delivers Embedded System Performance // Xcell journal. 2004. V. 48. - pp. 32-34.

76. Konovalov N. A., Krukov V. A., Mihailov S. N. and Pogrebtsov A. A.

77. Fortran DVM — a language for portable parallel program development //161

78. Proceedings of Software For Multiprocessors & Supercomputers: Theory, Practice, Experience. Institute for System Programming, RAS, Moscow, 1994.

79. Lamport L. The coordinate method for parallel execution of DO loops // Proc. 1973 Samagore Comput. Conf. Parallel Process., N. Y., IEEE. -1973. -P. 1-12.

80. Lewis T. G. Foundation of parallel programming: machine-independent approach. IEEE Computer Society Press, 1994. — 282 p.

81. Lobachev G. A., Plotnikiv P. V. Computer-Aided Design Subsystem of Multi-channel Quadrature Delimiters on XILINX FPGA, Microelectronic and Microsystems Design REASON Student Contest 4th Electronic Circuits and Systems Conference 2003

82. Рак К. Chan, Digital System Design Using Field Programmable Gate Arrays : Prentice Hall, 1994

83. Plotnikov P., Lobachev G., Comparison XILINX and ALTERA FPGAs // in Proceedings of International Scientific Conference Informatics, Mathematical Modelling and Design in the Technics, Controlling and Education (IMMD'2004), Vladimir, 2004. p. 137 139

84. Robert Kaye. Mentor Graphics Offers Seamless Integration for Virtex-II Pro Developers // Xcell journal. 2002. V. 44. - pp. 40-41.

85. Ross Nelson. Seamless HW/SW Co-Verification for Xilinx Virtex-II Pro FPGAs // Xcell journal. 2004. V. 48. - pp 56-58.

86. Shawn McCloud. Algorithmic С Synthesis Optimizes ESL Design Flows // Xcell journal. 2004. V. 50. - pp. 46-51.

87. Tom Durkin. SETI Researchers Sift Interstelar Static fo Signs of Life // Xcell journal. -2004. V. 48. pp. 9-13.

88. Voevodin V. V. Information structure of sequential programs // Russ. J. of Num. An. and Math. Modelling. — 1995. — V. 10. № 3. — P. 279—286.

89. Информационно-аналитический центр по параллельным вычислениям в сети Интернет // http://www.parallel.ru

90. Многоядерные процессоры — уже норма. (iXBT Hardware News, 2005.02.09) // http://ixbt.com/news/hard/

91. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф. Г. Энслоу. — М.: Мир, 1976. — 384 с.

92. Разработка трансляторов. Общие принципы организации синтаксического разбора // http://www.softcraft.ru/translat/lect/t06-Ol.shtml

93. Разработка трансляторов. Организация лексического анализа // http://www.softcrafl.ru/translat/lect/t04-01 .shtml

94. Разработка трансляторов. Основы теории языков и формальных грамматик // http://www.softcrafl.ru/translat/lect/t02-02.shtml

95. Самая большая ПЛИС // http://www.osp.ni/cw/2002/31/00019.htm

96. Сервер информационных технологий // http://www.citforura.ru

97. Тема 2. Основы теории языков и формальных грамматик. Способы записи синтаксиса языка // http://www.softcraft.ru/translat/lect/t02-04.shtml

98. Agilent EEsof EDA. Advanced Design System overview. Online. // http://www.tmo.hp.com/tmo/hpeesof/prod-ucts/ ads/adsoview.html

99. CoCentric SystemC Compiler. // http://www.synopsys.com/products/cocentricsystemC/cocentricsystemCds.html

100. CoCentric™ System Studio ARM Processor Developer Kits. II http://www.synopsys.am/products/cocentricstudio/cocentricstudiopdkA 4.pdf

101. IEEE Std 1076-1993 "IEEE Standard VHDL Language Reference Manual"

102. Method of might reliability system synthesis using VHDL // 1st IEEE International conference on circuits and systems for communications. Saint-Petersburg 2002. Page(s):134 137