Содержание к диссертации
Введение
1 Анализ систем и средств автоматизации проектирования и верификации устройств быстрого преобразования фурье высокой разрядности 16
1.1 Основные направления повышения эффективности обработки цифровых сигналов при помощи быстрых алгоритмов 16
1.2 Особенности алгоритмов, моделей построения и функционирования устройств быстрого преобразования Фурье высокой разрядности 18
1.2.1 Алгоритмы БПФ с основанием 2 - как наиболее оптимальные для реализации модуля БПФ высокой разрядности 18
1.2.2 Сопоставление объема вычислений при использовании оснований 2,4 и 8, для нахождения оптимального 23
1.3 Разработка оптимальной математической модели функционирования модуля быстрого преобразования Фурье 26
1.3.1 Особенности аппаратной реализации быстрого преобразования Фурье с основанием 2 26
1.3.2 Оптимальная аппаратурная реализация алгоритма с основанием 2 30
1.3.3 Параллельные структуры для алгоритмов быстрого преобразования Фурье с основанием 2 и 4 31
1.3.4 Построение поточных схем быстрого преобразования Фурье 35
1.4 Средства моделирования при проектировании БПФ высокой разрядности. Анализ направлений и методов верификации RTL моделей микроэлектронных устройств высокой разрядности 36
1.5 Цель и задачи исследования 53
2 Разработка математического обеспечения процесса проектирования и верификации устройств быстрого преобразования фурье высокой разрядности 56
2.1 Анализ процесса функционально-логического проектирования 56
2.1.1 Технология восходящего и нисходящего проектирования 57
2.2 Иерархия моделей СБИС на этапе функционально-логического проектирования 61
2.3 Математические модели создания тестовых последовательностей, для верификации устройств быстрого преобразования Фурье высокой разрядности 63
2.4 Основные выводы второй главы 68
3 Алгоритмизация функционального тестирования устройства быстрого преобразования фурье высокой разрядности 69
3.1 Особенности алгоритмов для арифметики с плавающей точкой 69
3.2 Алгоритм работы функции умножения над операндами с плавающей точкой в формате IEEE-754 70
3.3 Алгоритм работы функции сложения над операндами с плавающей точкой в формате IEEE-754 73
3.4 Алгоритм работы генератора тестовых последовательностей 75
3.5 Алгоритм работы генератора front-end модели ПЗУ 77
3.6 Алгоритм работы тестбенча модели умножителя и сумматора 79
3.7 Алгоритм работы тестбенча модели ОЗУ 79
3.8 Алгоритм работы тестбенча front-end модели ПЗУ 82
3.9 Основные выводы третьей главы 83
4 Разработка средств программного обеспечения функционального тестирования модуля быстрого преобразования фурье высокой разрядности 85
4.1 Используемые технические средства и обоснование их применения 85
4.1.1 Платформа тестового окружения 85
4.1.2 Выбор среды моделирования 86
4.1.3 Средства автоматизации тестов 8 8
4.1.4 Язык и среда программирования 89
4.2 Функциональное описание программного комплекса 96
4.2.1 Функциональная схема тестового окружения модели ОЗУ и ПЗУ 96
4.2.2 Функциональная схема тестового окружения модулей умножения и суммирования 98
4.2.3 Функциональная схема тестового окружения модуля БПФ 99
4.3 Описание физической структуры программного комплекса 101
4.4 Использование разработанного программного обеспечения для
верификации БПФ на 256К точек и анализ его эффективности по
результатам внедрения 104
4.5 Основные выводы четвертой главы 109
Заключение
Список использованных источников
- Особенности алгоритмов, моделей построения и функционирования устройств быстрого преобразования Фурье высокой разрядности
- Технология восходящего и нисходящего проектирования
- Алгоритм работы функции сложения над операндами с плавающей точкой в формате IEEE-754
- Функциональное описание программного комплекса
Введение к работе
Актуальность темы:
Наступление эры глубоко-субмикронных СБИС размерностью в миллионы условных вентилей, делает неизбежными большие перемены в среде средств автоматизированного проектирования. Многие передовые промышленные предприятия присматриваются к проблемам нанометровых проектов и к тому, как удовлетворить возрастающие в связи с этим нужды разработчиков в новых программных инструментах и методологиях проектирования.
Разрыв между технологическими возможностями, которые могут быть реализованы в кремнии, и современными средствами СЛПР продолжает возрастать. Требуется новое поколение САПР, способное удовлетворить требованиям более быстрого и, одновременно, более точного анализа в нанометровых (глубоко-субмикронных) проектах. Одна из точек, на которой фокусируются проблемы - физическая верификация нанометровых проектов.
В системах ближайшего будущего потребуется дополнительно и одновременно с этим решать проблемы питания, целостности сигналов, электромагнитной интерференции, миграции металла, надежности и термического анализа.
Программные средства должны обладать способностью оперировать с огромными объемами данных и различными типами этих данных. Разными методами решения этой проблемы являются новые эффективные рабочие алгоритмы, способы минимизации и сжатия данных, разработка такой структуры базы данных, которая позволяет разным средствам работать с одними и теми же данными, а не генерировать новые. И опять же -использование иерархических методов, позволяющих разбивать задачу на подзадачи меньшей размерности.
Разработка модуля быстрого преобразования Фурье высокой разрядности с применением современных САПР является наиважнейшей задачей. Эффективность работы пассивной радиолокации можно повысить за
счет применения более совершенных систем антенных приемников всевозможных излучений, а также за счет более совершенных систем обработки принятого сигнала. Наиболее перспективным и актуальным, на данный момент, выглядит возможность повышения эффективности пассивной радиолокации за счет улучшения обработки цифрового сигнала, посредством разложения сигнала в спектр при помощи быстрого преобразования Фурье.
Несмотря на тот факт, что пассивная радиолокация обладает меньшей эффективностью, по сравнению с активной, так как нет облучения изучаемого пространства, и лишь прием и обработка излучений летящих объектов, а также огромного множества атмосферных помех, пассивная радиолокация является наиболее перспективной, так как обладает сто процентной неуязвимостью для средств подавления противника.
Для качественного определения происхождения сигнала, необходимы надежные и эффективные средства его обработки.
Набор алгоритмов, называемых алгоритмами быстрого преобразования Фурье (БПФ), включает разнообразные методы уменьшения времени вычисления дискретного преобразования Фурье (ДПФ). Поскольку вычисление ДПФ является основной операцией в большинстве задач спектрального анализа, то использование БПФ в некоторых встречающихся на практике случаях, позволяющее ускорить вычисление ДПФ в 100 и более раз по сравнению с методом прямого вычисления ДПФ, имеет чрезвычайно важное значение и должно рассматриваться как неотъемлемая часть применения методов цифровой обработки сигналов для спектрального анализа.
Степень интеграции современных СБИС, как и постулировал Мур, растет экспоненциально. На первый план выходит другой сдерживающий фактор - проблема функциональной верификации СБИС. Особую остроту она приобретает при разработке систем на кристалле, включающих не только
цифровые, но и аналоговые, смешанные и даже СВЧ блоки, а также процессорные ядра со встроенным программным обеспечением.
Актуальность задачи проистекает из того факта, что возможности средств верификации сегодня заметно отстают от возможностей систем проектирования. Это привело к необходимости принципиально нового подхода к методам верификации СБИС.
В связи с этим актуальна задача разработки программного комплекса функциональной верификации сложно-функционального (СФ) модуля быстрого преобразования Фурье (БПФ) на 256К точек предназначенного для систем пассивной радиолокации, а также проектирование тестов, тестовых векторов и последовательностей для проведения верификации модуля в ведущих промышленных САПР таких компаний как Cadence Design Systems, Inc. и Mentor Graphics Inc.
Цель и задачи исследования:
Разработка средств основывается на следующих положениях:
достижение высокой производительности;
совместимость со всеми средствами проектирования, работающими в стандарте ШЕЕ - 754;
отсутствие жестких ограничений на размерность проекта (количество приборов, плотность и размеры топологии);
настройка на любые технологии изготовления;
простота и удобство языка описания технологических файлов;
верификация параметров приборов;
быстрый и удобный доступ к информации о сравниваемых схемах и к результатам сравнения;
высокая степень локализации ошибок;
возможность экстракции схемы на уровне логических моделей;
усовершенствованная система управления генерацией тестов;
генерация тестов должна обеспечивать возможность их повторного использования в других проектах, сокращая затраты на написание тестов;
Целью диссертационного исследования является разработка моделей, алгоритмов и программного комплекса функциональной верификации устройства быстрого преобразования Фурье высокой разрядности, позволяющего повысить качество проектируемых устройств, а также сократить затраты времени на выполнение полноценной верификации. Для достижения поставленной цели, необходимо решить ряд задач:
провести анализ возможных типов функциональной реализации и построения модуля быстрого преобразования Фурье высокой разрядности;
провести анализ систем и средств проведения функциональной верификации на различных этапах создания проекта;
разработать математические модели функциональной верификации и создания тестовых последовательностей (векторов), для отдельных блоков и всего БПФ в целом;
осуществить разработку алгоритмов функционального тестирования устройства быстрого преобразования Фурье высокой разрядности;
- разработать верификационное окружение модуля быстрого
преобразования Фурье на 256К точек, с обоснованием технических решений
выбранных для реализации программного комплекса.
Методы исследования. При выполнении работы использованы методы алгоритмического моделирования интегральных микросхем, элементы теории оптимизации обработки и математического моделирования цифрового сигнала, элементы теории чисел с плавающей арифметикой, автоматизированного проектирования, элементы теории верификации сложных систем на кристалле. При разработке программных средств применялись методы системного программирования.
Научная новизна: В работе получены следующие результаты, характеризующиеся научной новизной:
1. Сформированы математические модели тестирования всего БПФ высокой разрядности и входящих в его состав отдельных модулей, позволяющие на их основе сгенерировать тестовые векторы, обеспечивающие наиболее полное покрытие верификационными тестами VHDL модели БПФ и ее субмодули, что позволяет свести к минимуму возможные ошибки и несоответствия RTL кода спецификации системного уровня, перед переходом на следующие этапы проектирования - синтез, реализацию и трассировку.
Разработаны алгоритмы функционального тестирования устройства быстрого преобразования Фурье высокой разрядности, которые позволяют осуществить наиболее полное покрытие верификационными тестами VHDL модели БПФ и ее субмодули, и свести к минимуму возможные ошибки и несоответствия RTL кода спецификации системного уровня, перед переходом на следующие этапы проектирования - синтез, реализацию и трассировку.
Разработанные алгоритмы тестирования отдельных блоков и всего БПФ в целом, используют сочетание формализованной методики с применением технологий моделирования. Данный подход позволяет добиться следующих критериев оптимальности:
производительность;
применение механизма assertions;
совместимость со всеми средствами проектирования, работающими в стандарте ШЕЕ - 754;
отсутствие жестких ограничений на размерность проекта (количество приборов, плотность и размеры топологии);
настройка на любые технологии изготовления;
простота и удобство языка описания технологических файлов;
верификация параметров приборов;
быстрый и удобный доступ к информации о сравниваемых схемах и к результатам сравнения;
высокая степень локализации ошибок;
возможность экстракции схемы на уровне логических моделей;
усовершенствованная система управления генерацией тестов;
генерация тестов должна обеспечивать возможность их повторного использования в других проектах, сокращая затраты на написание тестов;
4. Предложена методика применения нетрадиционного показателя полноты верификации проекта. Применен механизм так называемых "утверждений" (assertions). Который подразумевает расстановку внутри моделируемого кода "закладок", проверяющих работу тех или иных функций по мере их срабатывания, не дожидаясь распространения следствия данного срабатывания на выход схемы. Данный подход обеспечивает высокую степень локализации ошибок.
Практическая ценность. На основе предложенных моделей и алгоритмов разработан программный комплекс, позволяющий производить структурную, поэлементную или всеобщую верификацию БПФ высокой разрядности, посредством автоматизированного создания тестовых векторов (тестбенчей) и сравнения отклика на них с эталонными данными, с ведением протокола в реальном времени, что исключает участие человека. Использование этого программного комплекса позволяет заметно ускорить процесс верификации высокоразрядных, сложных сверхбольших интегральных схем, систем на кристалле, программируемых логических интегральных схем и других проектов нанотехнологии, а также выявлять ошибки на ранних стадиях проектирования, быстро и безошибочно, по протоколу, определять точное местоположение дефектного модуля любого уровня разукрупнения, а также проводить верификацию без постоянного участие человека.
Внедрение результатов работы. Результаты проведенных исследований использовались при выполнении хоздоговорных работ № 1/05 от 01 апреля 2005 года, заключенном со специализированным конструкторско-технологическим бюро электронных систем «НПО СКТБ
ЭЛЕКТРОНИКА», а также в ГБ НИР 2000.17 «Проектирование и технология электронных средств» выполненной на кафедре КИПРА ВГТУ. Основные положения диссертации в виде автоматизированного программного комплекса внедрены в ОАО «Видеофон» г. Воронеж.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах:
Международной конференции «Системные проблемы надежности, качества, информационных и электронных технологий» (Сочи 2004, 2005, 2006);
Всероссийской научно-технической конференции молодых ученых «Современные проблемы радиоэлектроники» (Красноярск, КГТУ, 2004,2005, 2006);
Научно-технических конференциях Воронежского государственного технического университета в 2004,2005 и 2006 годах.
Публикации.
По теме диссертационной работы опубликовано 13 печатных работ, из них 11 в соавторстве и 2 лично соискателем. Работа /103/ опубликована в издании, рекомендованном ВАК РФ. Основной ход работы изложен в 3 отчетах о НИР.
В работах опубликованных в соавторстве, лично соискателю принадлежит: /25/ - выбор методов бездефектного производства РЭС; в /26, 76, 99, 101, 102/ - математические модели модулей входящих в состав БПФ; /27, 100/ - оценка эффективности БПФ при вычислении дискретного преобразования Фурье в системах пассивной радиолокации; /78, 79/ -математические модели виртуальных прототипов и анализ эффективности применения общего языка описания аппаратуры; в /103/ - алгоритмы верификации БПФ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников,
включающего 103 наименования, 11 приложений. Основная часть работы изложена на 136 страницах, содержит 46 рисунков и 10 таблиц.
В ПЕРВОЙ ГЛАВЕ работы рассмотрены быстрые алгоритмы, позволяющие увеличить скорость и производительность вычисления дискретного преобразования Фурье. Дастся сравнение характеристик наиболее оптимальных алгоритмов преобразования Фурье.
Проанализированы современные средства оптимального
моделирования и синтеза при проектировании СБИС. Рассмотрены методологии автоматизированного проектирования больших и сверхбольших интегральных схем при бездефектном производстве.
Произведен анализ и выбор лингвистического обеспечения, характеризующегося достаточно гибкими описательными способностями для реализации преимуществ нисходящего проектирования, включающего в себя языки описания аппаратуры (ЯОА), позволяющие создавать адекватные модели проектируемых устройств и эффективно выполнять соответствующее имитационное моделирование, обладая при необходимости независимостью от конкретных аппаратных структур.
Выбранные алгоритмы и математические модели для разрабатываемого программного комплекса соответствуют следующим требованиям:
алгоритмы обеспечивают высокое покрытие верифицируемого кода, поскольку это один из главных показателей качества верификации;
модели обладают достаточной адекватностью и универсальностью;
алгоритмы и модели экономически оправданы с точки зрения затрат времени и средств на их реализацию.
высокое быстродействие, так как для полной верификации устройств на плавающей арифметике стандарта IEEE-754, необходим прогон порядка 10 млн. тестовых векторов;
независимость от среды моделирования, поддержка верификационных платформ основных производителей.
ВО ВТОРОЙ ГЛАВЕ
1. Сформирована структура процесса нисходящего функционально-
логического проектировании устройства быстрого преобразования Фурье
высокой разрядности. Поэтапное моделирование и аппаратурная реализация
с описание принципа работы и RTL кодом представлено в приложении.
2. Предложены математические модели создания тестовых
последовательностей для верификации входящих в состав модуля быстрого
преобразования Фурье высокой разрядности.
3. Предложена модель создания тестбенча умножителя и сумматора,
создания тестбенча проверки адекватности функционирования модели ОЗУ и
ПЗУ. Разработанные модели создания системных тестов позволяют
проводить моделирование на уровне транзакций, верификацию интерфейсов
различных подсистем одновременно с их проектированием, т.е. возможность
верификации системы, отдельные блоки которой представлены на разных
уровнях абстракции. Чаще всего оптимальное решение заключается в
комбинации обоих названных подходов.
В ТРЕТЬЕЙ ГЛАВЕ
1. Разработано алгоритмическое обеспечение функционального
тестирования. За основу взят стандарт IEEE-754 для вычислительных
устройств на арифметике с плавающей точкой, который в настоящее время
является общепринятой нормой. Умножители и сумматоры, разработанного
ранее (в рамках хоздоговорных работ № 1/05 от 01 апреля 2005 года,
заключенном со специализированным конструкторско-технологическим
бюро электронных систем «НПО СКТБ ЭЛЕКТРОНИКА») модуля БПФ
высокой разрядности, построены на принципах совместимости с IEEE-754;
2. Разработанные алгоритмы тестирования отдельных блоков и всего
БПФ в целом, позволяют в процессе тестирования достичь оптимальных
результатов, благодаря сочетанию формализованной методики с
применением технологий моделирования.
При этом учитывались следующие критерии оптимальности:
производительность;
применение механизма assertions;
совместимость со всеми средствами проектирования, работающими в стандарте IEEE - 754;
отсутствие жестких ограничений на размерность проекта (количество приборов, плотность и размеры топологии);
настройка на любые технологии изготовления;
простота и удобство языка описания технологических файлов;
верификация параметров приборов;
быстрый и удобный доступ к информации о сравниваемых схемах и к результатам сравнения;
высокая степень локализации ошибок;
возможность экстракции схемы на уровне логических моделей;
усовершенствованная система управления генерацией тестов;
генерация тестов должна обеспечивать возможность их повторного использования в других проектах, сокращая затраты на написание тестов;
В ЧЕТВЕРТОЙ ГЛАВЕ
1. На основе ранее предложенных математических моделей и
алгоритмов разработан программный комплекс, обеспечивающий
верификацию и создание тестового окружения, которое осуществляет
наиболее полное покрытие верификационными тестами VHDL модели БПФ
и ее субмодули, и позволяет свести к минимуму возможные ошибки и
несоответствия RTL кода спецификации системного уровня, перед
переходом на следующие этапы проектирования - синтез, реализацию и
трассировку. Также комплекс позволяет произвести верификацию проекта на
логическом уровне и оценить разницу в поведении проекта с оным на RTL
уровне при моделировании.
2. Разработанное программное средство в автоматическом режиме
производит генерацию тестовых последовательностей для модуля БПФ, для
умножителей и сумматоров на плавающей арифметике. Затем
сгенерированные тестовые последовательности подаются в качестве стимулов на входные интерфейсы модуля на тестировании, а результаты на выходе сравниваются с эталонными вычисленными программным средством, все расхождения протоколируются в специальный файл-лог. Запуск симуляции осуществляется путем исполнения скриптов автоматизации BASH (наиболее распространенная в настоящее время версия Unix shell). Это обеспечивает многократный прогон тестов без непосредственного участия человека.
3. Разработанные средства верификации поддерживают все стандартные языки проектирования и верификации - VHDL, Verilog, VHDL-AMS, Verilog-A, Spice, С, C++, SystemC, System Verilog, MATLAB, PSL assertions и др.
В ЗАКЛЮЧЕНИИ представлены основные результаты диссертационной работы.
1 АНАЛИЗ СИСТЕМ И СРЕДСТВ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ И ВЕРИФИКАЦИИ УСТРОЙСТВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ВЫСОКОЙ РАЗРЯДНОСТИ
Особенности алгоритмов, моделей построения и функционирования устройств быстрого преобразования Фурье высокой разрядности
Любой алгоритм, подобно большинству инженерных устройств, можно описывать либо через соотношение между входом и выходом, либо детально объясняя его внутреннюю структуру. Применяя к некоторой новой задаче методы цифровой обработки сигналов, мы сталкиваемся с заданием алгоритмов через соотношение вход-выход/1,2,3,5,6,11,12,52/. При заданном сигнале или записанных некоторым образом данных основное внимание сосредотачивается на том, что с этими данными сделать, т. е. каков должен быть выход алгоритма, если на его вход подаются те или иные данные. Примерами такого выхода служат профильтрованная версия входа или его преобразование Фурье. Такая связь входа с выходом в алгоритме математически может быть записана без детального выписывания всех шагов, необходимых для выполнения вычислений.
Под быстрыми алгоритмами понимают/1,6,7,18,20/детальное описание вычислительной процедуры, которая не является очевидным способом вычисления выхода по данному входу. Как правило, быстрый алгоритм жертвует концептуальной ясностью вычислений в пользу их эффективности.
Существует ограниченное число алгоритмов вычисления цифрового сигнала, обладающих высокой эффективностью. К таким задачам относятся: задача вычисления линейной свертки, циклической свертки, многомерные линейные и циклические свертки, дискретное преобразование Фурье, многомерное дискретное преобразование Фурье, решение теплицевых систем уравнений и нахождение пути на решетке.
Как видно из таблицы 1.1, при приближении к концу списка повышение эффективности алгоритмов замедляется. Уменьшение числа умножений на одну точку вычислительной сетки на выходе от шести до четырех может существенно снизить затраты времени на обработку сигнала, при построении больших схем.
Современные сверхбольшие интегральные схемы (СБИС) завоевали мировой рынок бытовой аппаратуры и аппаратуры специального назначения-СБИС может содержать до 8 миллионов логических элементов. Улучшить характеристики СБИС возможно двумя путями - увеличивая его быстродействия или размер и выбором оптимального алгоритма обработки сигнала. На первый взгляд эти два направления - быстродействующие интегральные схемы и быстрые алгоритмы - конкурируют между собой. Если можно простроить достаточно большие и быстродействующие чипы, то на первый взгляд можно мериться с тем, что используются неэффективные алгоритмы. Однако большие цифровые процессоры сами создают потребность в разработке быстрых алгоритмов, так как размерность решаемых на них задач растет. Будет ли процессорное время алгоритма, предназначенного для решения некоторой задачи, пропорционально п2 или п , несущественно при п, равном 3 или 4, но при п равном 1000, это становится критичным.
Несмотря на то, что алгоритмы БПФ хорошо известны и широко используются, при первом ознакомлении с ними они по ряду причин достаточно трудны для понимания. К тому же в литературе встречается несколько различных подходов к описанию алгоритмов БПФ, которых появилось очень много. Наконец, ввиду сложности операции перестановки данных ее проще всего понять на конкретных примерах /28,29,31,32,33,34/.
Ниже будет показано, что периодичность W" является одним из ключевых моментов БПФ. Часто периодичность W подчеркивают тем, что вместо ( записывают W .
Из соотношения (1.1) следует, что в случае, когда последовательность х(п) является комплексной, при прямом вычислении N -точечного ДПФ нужно выполнить (N- if комплексных умножений uN (N- 1) комплексных сложений. Таким образом, для достаточно больших N (порядка 1000) прямое вычисление ДПФ требует выполнения чрезмерного количества вычислительных операций. Основная идея БПФ состоит в том, чтобы разбить исходную JV-точечнуіо последовательность на две более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы получилось ДПФ исходной -точечной последовательности. Так, например, если N четное, а исходная //-точечная последовательность разбита на две (N/2)-точечные последовательности, то для вычисления искомого JV-точечного ДПФ потребуется порядка (N/2) 2 =N /2 комплексных умножений, т. е. вдвое меньше по сравнению с прямым вычислением. Здесь множитель (N/2) дает число умножений, необходимое для прямого вычисления (/// -точечного ДПФ, а множитель 2 соответствует двум ДПФ, которые должны быть вычислены. Эту операцию можно повторить, вычисляя вместо (W/2j04e4iioro ДПФ два (N/4) -точечных ДПФ (предполагая, что N/2 четное) и сокращая тем самым объем вычислений еще в два раза. Выигрыш в два раза является приближенным, поскольку не учитывается, каким образом из ДПФ меньшего размера образуется искомое -точечное ДПФ.
На рисунке 1.1 с помощью направленного графа представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных преобразований. Входная последовательность х(п) сначала разбивается на две последовательности х\(п) и Х2(п) из четных и нечетных членов х(п), после чего рассчитываются их преобразования Хф) и Xi(k). Затем в соответствии с формулой (1.10) получают Х(к).
Кружки в правой части рисунка 1.1 обозначают операцию сложения/вычитания, причем верхний выход соответствует сумме, а нижний разности. Стрелка обозначает операцию умножения на значение множителя а, указанного над стрелкой. В общем случае переменные являются комплексными числами. Заметим, что кружок можно интерпретировать как двухточечное ДПФ. Узлы обозначают регистры, содержащие входные и выходные массивы отдельных ДПФ. Все эти обозначения согласуются с правилами изображения направленных графов в теории линейных систем.
Рассмотренная схема вычислений может быть использована для расчета Л 2-точечных ДПФ в соответствии с формулами (1.9) и (1.10). Каждая из последовательностей х\(п) и х2(п) разбивается на две последовательности, состоящие из четных и нечетных членов. Аналогично iV/2-точечные ДПФ могут быть записаны как комбинации двух iV/4-точечных ДПФ, т. е.
Технология восходящего и нисходящего проектирования
При функционально-логическом проектировании (ФЛП) СБИС могут быть реализованы две стратегии: восходящая (снизу вверх) и нисходящая (сверху вниз). Выбор той или иной стратегии в основном определяется постановкой задачи на проектирование, объемом исходной информации и технологическими требованиями к СБИС.
При восходящей стратегии проектирования задана некоторая логическая схема ЭЗ, элементами которой являются корпусные ИС, и на ее основе необходимо разработать логический проект СБИС.
Стратегия создания логического проекта "сверху вниз" более сложна и трудоемка в реализации, чем разработка логического проекта по стратегии "снизу вверх" в силу большой неопределенности исходной информации. Применение нисходящего проектирования целесообразно в случае, когда известен только алгоритм функционирования БИС и ее желаемые технические характеристики, а информация о структуре логической схемы СБИС отсутствует. Поэтому для разработки логической схемы необходимо предварительно провести работы на этапах архитектурного и функционального проектирования, т.е. разработать сначала схемы Э1 и Э2. Таким образом, нисходящее проектирование БИС сведем к такой последовательности действий, которой и будем придерживаться при проектировании модуля быстрого преобразования Фурье:
1. разрабатывается архитектура БИС (схема Э1) как совокупность функциональных блоков (ФБ);
2. каждый блок описывается алгоритмической моделью и проводится моделирование схемы Э1 на регистровом уровне. По результатам моделирования уточняются и конкретизируются технические требования на СБИС, формируются требования к блокам, уточняется алгоритм функционирования СБИС в целом;
3. на основе библиотеки ячеек проводится разработка функциональной схемы (Э2), а затем логической схемы СБИС (ЭЗ). Стратегия нисходящего проектирования предполагает иерархию не только алгоритмических и структурных моделей БИС, используемых па уровнях архитектурного, функционального и логического проектирования СБИС, но и иерархию тестов для проверки работоспособности ячеек и СБИС в целом.
При разработке логического проекта СБИС большой объем работ падает на его верификацию, которая выполняется с помощью программ функционально-логического моделирования на регистровом и логическом уровнях.
Для разработки логического проекта СБИС должен быть задан тип БМК. В качестве исходных данных может также выступать логическая схема цифрового устройства в базисе элементов различных серий ИС или логическая схема СБИС в базисе библиотечных элементов другого БМК. Кроме того, для реализации восходящего проектирования необходимо, чтобы САПР была настроена на библиотечные элементы БМК, на которых требуется проектировать логическую схему СБИС. В результате настройки САПР на заданный тип БМК в соответствующей библиотеке БД-системы должны храниться алгоритмические и структурные модели всех ячеек БМК, а в библиотеке типовых ФУ БД могут храниться логические схемы узлов и блоков, которые могут применяться во вновь проектируемых СБИС, и поэтому являются типовыми. На основе такой исчерпывающей информации выполняется комплекс работ восходящего проектирования по непосредственной разработке логического проекта СБИС, включающий следующие этапы.
Этап 1 - декомпозиция исходной логической схемы цифрового устройства на отдельные функциональные блоки и узлы. Из библиотеки типовых узлов и блоков банка данных САПР выбираются элементы, которые могут быть использованы в проектируемой СБИС. Затем определяется совокупность функциональных блоков и узлов, подлежащих разработке.
Этап 2 - логическое проектирование на ячейках БМК ФУ, входящих в установленную на первом этапе совокупность: 1. исходная логическая схема узла покрывается соответствующими ячейками БМК; 2. разрабатываются функциональные тесты на каждый узел; 3. составляются структурные модели каждого узла; 4. проводится логическое моделирование функциональных узлов на САПР с целью отладки его логической схемы и тестов для проверки работоспособности, определения технических характеристик и принятия решения о возможности использования какого-либо разработанного узла в качестве типового;
Алгоритм работы функции сложения над операндами с плавающей точкой в формате IEEE-754
Алгоритм функции сложения над операндами с плавающей точкой в формате IEEE-754 представлена на рисунке 3.2. При вычислении суммы может возникнуть три различных ситуации: когда разность экспонент операндов положительна (пункты 6, 3, 7, 8, 10, 11,12, 15, 17, 18), когда разность экспонент операндов отрицательна (пункты 1, 5, 9, 13, 14, 16, 19, 20, 21, 23) и когда равна нулю (пункты 22, 24, 25,27, 28, 31). Для каждого из вариантов производится проверка на NaN (пункты 8, 5 , 22 соответственно) в случае успешности которой операнды передаются для вычисления специальной функции.
Функция propagateFloat32NaN (пункты 12, 14, 27) производит вычисление результата сложения, в случае если один или оба операнда NaN. Для случаев, когда разность экспонент больше или меньше нуля производится также проверка является ли второй (первый для положительной разности экспонент) операнд бесконечностью (пункты 9 и 8), в этом случае результат бесконечность, которую в виде float32 возвращает функция pack32Float (пункт-13 или 18).
Рассмотрим подробно вариант с положительной разностью, исключая объясненные выше случаи. В этом случае если экспонента второго операнда равна нулю (пункт 7) производится инкремент разности экспонент, иначе мантисса второго операнда подвергается побитовому сложению с числом 0x20000000. Затем производится вызов функции shift32Right Jamming (пункт 15), а также значение экспоненты первого операнда присваивается экспоненте результата (пункт 17). После чего вычисляют мантиссу результата (пункты 26, 29, 30) сложением мантисс операндов, в случае переполнения увеличивают его экспоненту (пункты 29,30) и наоборот (пункт 17).
После данных преобразований результат округляется и преобразовывается в формат float32, для чего мантисса, экспонента и знак передаются функции roundAndPackFloat32.
В случае отрицательной разности экспонент операндов производятся аналогичные действия с той лишь разницей, что операнды меняются местами первый становится вторым, второй первым.
Когда экспоненты обоих операндов равны, определяется равны ли они и нулю (пункт 24), поскольку в этом случае сумма будет равна простой сумме мантисс сдвинутой на 6 разрядов вправо и упакованной с помощью packFloat32 (пункт 28). Если экспоненты операндов отличны от нуля, к сумме мантисс операндов прибавляется число 0x20000000, а экспонента результата принимается равной экспоненте операндов (пункты 31), после чего результат округляется и приводится в форму f!oat32 функцией roundAndPackFloat32 (пункт 32).
Алгоритм работы генератора тестовых последовательностей представлен на рисунке 3.3. Программа генератор тестовых последовательностей представляет собой консольное приложение, поэтому все входные данные передаются ей как аргументы командной строки (пункт 1). Которые перед использованием необходимо соответствующим образом обработать, что в случае UNIX-систем обеспечивается предоставляемыми операционной системой вспомогательными функциями.
Затем производится генерация тестовых последовательностей на основе работы о тестировании вычислительных модулей совместимых с IEEE-754 на основе теории чисел /20,21,23/, после чего генерируются случайные тестовые векторы, и завершается генерация вставкой предопределенных тестовых последовательностей тестирующих крайние режимы работы вычислительных модулей на плавающей арифметике одинарной точности (пункты 3, 6, 7). После чего в зависимости для какой операции (сложение или умножение) производится генерация векторов (пункт 2) с помощью функций библиотеки ieee754float программно вычисляются эталонные результаты для тестовых пар (пункты 4 и 5 соответственно для умножения и сложения). Следующим действием является проверка эталонных результатов на модуле арифметики с плавающей точкой ЭВМ в цикле (пункты 8, 9, 10, 11, 12), и только в случае совпадения с эталонными, тестовые триады сохраняются в файл тестовых векторов.
Алгоритм работы генератора front-end модели ПЗУ представлен на рисунке 3.4. Назначением генератора является создание текстового файла представляющего собой VHDL модель ПЗУ с необходимыми коэффициентами. Генератор является консольными приложением и сразу после старта производит проверку правильности аргументов переданных ему в командной строке (пункты 2, 4, 6) и в случае ошибочного синтаксиса показывает справку (пункт 9). Собственно сама модель создается добавлением в файла заголовков библиотек (пункт 1), которые всегда одинаковы для моделей с разной разрядностью шин, разными выходами и т.д. Далее формируется и записывается entity или интерфейс модели на основе данных о разрядности шин переданных аргументами командной строки. После чего формируется заголовок архитектуры (пункт 7) или реализации модели, и открывается оператор CASE (пункт 10). Путем последовательного чтения из файла дампа памяти формируется каждая ячейка модели ПЗУ в формате адрес-значение, действие это производится в цикле (пункты 8, 11).
Функциональное описание программного комплекса
В течение многих лет единственным определением языка Си было первое издание книги "Язык программирования Си". В 1983 г. Институтом американских национальных стандартов (ANSI) учреждается комитет для выработки современного исчерпывающего определения языка Си. Результатом его работы явился стандарт для Си ("ANSI-C"), выпущенный в 1988 г. Большинство положений этого стандарта уже учтено в современных компиляторах.
Стандарт базируется на первоначальном справочном руководстве. По сравнению с последним язык изменился относительно мало. Одной из целей стандарта было обеспечить, чтобы в большинстве случаев существующие программы оставались правильными или вызывали предупреждающие сообщения компиляторов об изменении поведения.
Для большинства программистов самое важное изменение - это новый синтаксис объявления и определения функций. Объявление функции может теперь включать и описание ее аргументов. В соответствии с этим изменился и синтаксис определения функции. Дополнительная информация значительно облегчает компилятору выявление ошибок, связанных с несогласованностью аргументов, это очень полезное добавление к языку.
Следует также отметить ряд небольших изменений. В языке узаконены присваивание структур и перечисления, которые уже некоторое время широко используются. Вычисления с плавающей точкой теперь допускаются и с одинарной точностью. Уточнены свойства арифметики, особенно для беззнаковых типов. Усовершенствован препроцессор. Большинство программистов эти изменения затронут очень слабо.
Второй значительный вклад стандарта - это определение библиотеки, поставляемой вместе с Си-компилятором, в которой специфицируются функции доступа к возможностям операционной системы (например чтения-записи файлов), форматного ввода-вывода, динамического выделения памяти, манипуляций со строками символов и т. д. Набор стандартных заголовочных файлов обеспечивает единообразный доступ к объявлениям функций и типов данных. Гарантируется, что программы, использующие эту библиотеку при взаимодействии с операционной системой, будут работать также и на других машинах. Большинство программ, составляющих библиотеку, созданы по образу и подобию "стандартной библиотеки ввода-вывода" системы UNIX. И здесь программисты не заметят существенных различий. Так как типы данных и управляющих структур языка Си поддерживаются командами большинства существующих машин, исполнительная система (runime library), обеспечивающая независимый запуск и выполнение программ, очень мала. Обращения к библиотечным функциям пишет сам программист (не компилятор), поэтому при желании их можно легко заменить на другие. Почти все программы, написанные на Си, если они не касаются каких-либо скрытых в операционной системе деталей, переносимы на другие машины.
Си соответствует аппаратным возможностям многих машин, однако он не привязан к архитектуре какой-либо конкретной машины. Проявляя некоторую дисциплину, можно легко писать переносимые программы, т. е. программы, которые без каких-либо изменений могут работать на разных машинах. Стандарт предоставляет возможность для явного описания переносимости с помощью набора констант, отражающих характеристики машины, на которой программа будет работать.
Си не является "строго типизированным" языком, но в процессе его развития контроль за типами был усилен. В первой версии Си хоть не одобрялся, но разрешался бесконтрольный обмен указателей и целых, что вызывало большие нарекания, но это уже давным-давно запрещено. Согласно стандарту теперь требуется явное объявление или явное указание преобразования, что уже и реализовано в хороших компиляторах. Новый вид объявления функций - еще один шаг в этом направлении. Компилятор теперь предупреждает о большей части ошибок в типах и автоматически не выполняет преобразования данных несовместимых типов. Однако основной философией Си остается то, что программисты сами знают, что делают; язык лишь требует явного указания об их намерениях.
Си, как и любой другой язык программирования, не свободен от недостатков. Уровень старшинства некоторых операторов не является общепринятым, некоторые синтаксические конструкции могли бы быть лучше. Тем не менее, как оказалось, Си - чрезвычайно эффективный и выразительный язык, пригодный для широкого класса задач.
Коллекция компиляторов (GNU Compiler Collection, также известная как GCC) это комплект компилятора и утилит, необходимых для разработки программного обеспечения, позволяющая получить из высокоуровнего исходного кода исполняемый бинарный. GCC это продукт проекта GNU, который был основан в 1984 году с целью создания полностью UNIX-совместимой операционной системой как свободного программного обеспечения. Как и любой другой проект такого масштаба GNU имел некоторое количество неудач, но основная цель была достигнута. Сегодня существует полнофункциональная UNIX-подобная операционная система названная Linux. Повсеместно в мире она используется с большим успехом компаниями, правительствами и частными лицами. И эта система, со всеми своими приложениями и утилитами основана на коллекции компиляторов GNU. GCC поддерживает широкий спектр целевых платформ таких как х86, RS6000, Arm, PowerPC и других, а также большое количество хост систем: Linux, Solaris, Windows и других.
Похожие диссертации на Разработка моделей и алгоритмов верификации в САПР высокоразрядных СБИС спектрального анализа
