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

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

Пышкин Евгений Валерьевич Р Г 5 ОД

Автоматизация синтеза многоуровневых ' * 2И схем дискретных преобразователей информации на задаваемом избыточном элементном базисе

Специальность 05.13.13 - Вычислительные машины,

комплексы, системы и сети Специальность 05.13.05-Элементы и устройства вычислительной техники и систем управления

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

Санкт-Петербург 2000

Работа выполнена в Санкт-Петербургском государственном техническом университете

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

профессор Мелехин Виктор Федорович

Официальные оппоненты:

доктор технических наук, профессор Лыпарь Юрий Иванович

кандидат технических наук, старшин научный сотрудник

Евланпиков Дмитрий Леонидович

Ведущая организация - научно-производственное объединение «Импульс»

Защита состоится " М¡Z/r fó 2000 г. в часов на заседании диссертационного совета Д 063.38.04 С116ГТУ по адресу:

195251, Санкт-Петербург, ул. Политехническая, 29, ауд. 325 (9-й корпус). С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан и la2000 г.

Ученый секретарь диссертационного совета i í.——Дурандин К.П.

/

d

Общая характеристика работы

Актуальность темы. По статистическим данным, в настоящее врем» до 30% сверхбольших интегральных схем (СБИС) создаются на основе базовых матричных кристаллов (БМК, Gate Arrays). На крупных отечественных предприятиях, связанных с разработкой и производством радиоэлектронной аппаратуры, существуют системы автоматизированного проектирования и изготовления полузаказных БИС на основе БМК. В большинстве' случаев такие БИС удовлетворяют жестким требованиям по условиям использования, характерным для аппаратуры специального назначения. При этом САПР не поддерживают синтез, а только анализ (моделирование и отработка тестов), конструкторское и технологическое проектирование.

В цикле создания БИС на БМК время синтеза составляет до 20%. Синтез всегда неоднозначен, связан с творчеством проектировщика, поэтому трудно формализуем. Учитывая сложность формализации синтеза, не определяющую его долю по трудозатратам и времени, задача автоматизации синтеза не считалась насущно необходимой. Интерес к этой проблеме возник при разработке проекта «Интегрированная проектно-производственная система полупроводниковых структур» (ИППС ПС), выполняемого ЦНИ СПбГТУ и НПО «Светлана» по государственному заказу. В основу создания этой системы был положен подход проф. И. Берга к «одночиповому» производству СБИС, позволяющему исключить потребность в больших «чистых» специализированных помещениях и организовать производство СБИС с высоким уровнем интеграции. В рамках этого проекта необходима сквозная автоматизация, включая автоматизацию синтеза. Эта задача решалась группой разработчиков СПбГТУ, в которую входил и автор диссертационной работы, г!од руководством проф. В.Ф. Мелехина. Для теоретического обоснования проектйьк решений при разработке ИППС ПС. были в значительной мере использованы положения теории проектирования цифровых устройств, которая была в наиболее общем (абстрактном) виде'разработана В.М. Глушковым и развита его последователями: Ю.В. Капитоновой, А.Т. Мищенко; П.М. Ивановым (Иуаном).

Развитие субмикронной технологии в разработке и проектировании БИС и СБИС для компонентов электронно-цифровой аппаратуры повлекло за собой возникновение нового быстро развивающегося наукоемкого направления в проектировании - специализированных СБИС программируемой и гибкой логики (CPLD, FLEX FPGA). При этом реализованы новые уникальные возможности для проектировщиков устройств и систем. Однако их ориентация как правило только на коммерческий а для части - на промышленный стандарт не всегда позволяют их использовать в системах специального назначения. При этом, однако, остается возможность и целесообразность их использования для ускорения создания и отладки опытных образцов. Применение существующих технологий позволяет использовать имеющиеся средства анализа и тестирования прототипа, уменьшая тем самым средства, которые необходимо было бы затратить на реализацию аналогичных этапов при использовании БМК.

При таком подходе к проектированию далее при проектировании систем требуется перепроектировать устройства, реализованные в прототипе на CPLD, на основе БМК. Автоматизация синтеза при этом обеспечит снижение трудоемкости и затрат времени и, что наиболее существенно, позволит уменьшить число вносимых ошибок.' Существенно отметить, что задача автоматизации синтеза при проектировании на интегральных схемах общего назначения и на основе БМК в отечественных промышленных системах автоматизации проектирования (САПР) остается нерешенной. Это связано с тем, что задача синтеза многоуровневых схем на избыточном и изменяемом базисе много сложнее, чем синтез двухуровневых схем в СБИС программируемой логики.

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

анализируемого подхода к проектированию ПО положено использование визуального формализма проектирования ПО (¿-сеть), предложенного и обоснованного проф. М.Ф.Лекаревым.

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

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

Научная новизна и практические результаты

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

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

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

4. Разработано программное обеспечение для системы автоматизации синтеза с использованием визуального формализма на основе /--сети. Внедрен законченный образе! системы, сформулированы конкретные предложения по развитию системы. Проведена оцени использованных средств проектирования ПО на основе существующих подходов к оценк( трудоемкости и качества программных средств.

Апробация работы. Основные результаты работы представлялись на Российски" научной конференции "Инновационные наукоемкие технологии для России" 25-27 апреля 1995г. на Третьей Санкт-Петербургской Ассамблее молодых ученых и специалистов (СПбГТУ, 1998г.). на Десятой научно-технической конференции 'Экстремальная робототехника" (СПб, ЦНИИ РТК 1999г.), приводились в отчетах по научно-исследовательской работе "Система автоматизации синтеза при структурно-логическом проектировании" (Санкт-Петербург, АЦИА, 1992 и 1993гг.), г также были использованы в ходе научной работы по программе DAAD «Стипендия именр Леонарда Эйлера» в техническом университете Hamburg-Harburg (Гамбург, Германия, 1999г.).

В конкурсе 1997г. участниками проекта, в котором используются результата диссертационной работы, был выигран грант на 1998-1999г. по теме «Разработка теории ъ средств создания среды для автоматизированного проектирования управляющих систем».

Публикации. По теме диссертации опубликовано 5 печатных работ.

Структура и объем работы. Введение, четыре главы и заключение изложены нг 145 страницах. Работа содержит 43 рисунка, 5 таблиц, список литературы из 83 наименований и i приложений. Общий объем работы - 223 страницы.

Содержание работы

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

В главе 1 рассматриваются задачи, возникающие при автоматизации синтеза

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

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

2. Функциональная декомпозиция синтезируемых функций для нестандартных блоков с ориентацией на типы функций, реализуемых на базе элементов из задаваемого избыточного набора (реализация стратегии покрытия).

3. Функциональная декомпозиция при проектировании ПО и представлении сложных структур данных; выделение повторяющихся классов задач, для которых могут быть предложены типовые проектные решения (образцы).

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

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

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

В главе 2 рассматриваются ..задачи, сформулированные на уровне формальных представлений. , .

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

Целесообразность декомпозиции при синтезе последовательностных цепей основывается на соображении о том, что при построении иерархической сети автоматов может достигаться уменьшение суммарной сложности по сравнению со сложностью исходного представления. Например, конечный автомат на 16-128 состояний может быть реализован в виде комбинации автоматов соответственно на 8-16 и 2-8 состояний, причем реализация второго автомата может оказаться очень простой. Поэтому актуальна постановка частной задачи декомпозиции, связанной с особенностями выделяемого параметризуемого ядра.

Введем обозначение. Пусть из множества вершин & в множество вершин ^ графа <7 выходят дуги, помеченные символом 1"0) Тогда будем обозначать этот факт:

& = ТгатШоп (&,1п®)( в)

Сформулируем задачу декомпозиции с использованием формализма определения автомата в виде графа переходов. Задан граф переходов <7 некоторого автомата М, требуегся построить графы переходов С/ и б1; автоматов М/ и Мг, образующих пару декомпозиции исходного автомата на более простые. Например, автомат М, граф переходов которого С представлен на рис. 1,а, может быть представлен в виде композиции двух автоматов, графы переходов которых <?/ и Ог изображены на рис. 1,6. В каждом из результирующих графов появляется по одной дополнительной вершине для организации их взаимодействия. В соответствии с принципом разбиения исходного графа на два результирующих, нужно заметить, что чем больше взаимных связей между двумя подграфами, формирующими вариант декомпозиции, тем больше дополнительных переходов появится в каждом из результирующих графов, а значит - сложность возможной реализации каждого из таких автоматов по крайней мере не уменьшится, какой бы способ конечной организации логической схемы не использовался. Таким образом, минимизация числа взаимных связей между выделяемыми подграфами представляется оправданным критерием декомпозиции. Приведенный пример представляет вариант декомпозиции с минимальным числом взаимных связей:

Тгат 'Шоп{ 7,12 ) = 5 ТгатМоп{ 8,12) = 3,

где 12 - входная переменная.

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

б

Рис. I. Вариант декомпозиции конечного автомата

На основании сведений из теории разбиений устанавливается, что в том случае, когда в одном из сформированных графов <7„ ге{1,2}, выделенных из графа С и дополненных вершинами для организации передачи управления одним автоматом другому, существует такое подмножество вершин ^ = &2,..., а в графе С,, ^е {1,2}, можно выделить соответствующее ему подмножество = gS2,..., 1</<=к, что для графа 6' справедливо:

8,® с С, и 3]: ё'<> - Тгап*Шоп( Щ) )(0, то декомпозиция с получением двух детерминированных автоматов невозможна.

Вариант декомпозиции с возникновением неопределенности для того же исходного автомата (рис. 1,а) иллюстрирует рис. 2:

Ггаияй'сж(8, Ь ) = { 2, 5 = то есть = { 2,5 }, §1®= {1,4 } и ^ = Тгап!Шоп(ё,(к), Ь)(О)

Рис 2. Вариант декомпозиции с возникновением неопределенности

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

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

В подходе к оценкам сложности реализации автомата использованы фундаментальное определение сложности А.Н. Колмогорова и известные оценки функциональной сложности, предложенные К.Э. Шенноном и развитые О.Б. Лупановым, дополненные моделью сложности реализации, построенной с учетом статистических закономерностей развития технологий производства интегральных схем. Наиболее общей и удобной мерой сложности вычислительных устройств считается оценка сложности реализуемых функций в виде минимизированных формул

где | F | - число символов в формуле Г.

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

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

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

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

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

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

-Л

1п

КС]

Функции разрешения

кс2

Функции разрешения записи

МБ1

мб2

СТ

фф А С НУ т.

Е)С

КС3

Функции перехода

И2Г

.....->

2!°/'

кс4

Функции выхода

От

Рис. 3. Структура композиционного ядра конечного автомата

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

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

1. Количество входных переменных, влияющих ка переход из отдельного состояния Statefl): ssutl(]y

2. Количество входных переменных, влияющих на формирование отдельного выходного сигнала Out(k). s0„(t).

3. Количество состояний, в которые существует переход из некоторого отдельного состояния State®: ns,altW.

4. Количество состояний, в которые существует переход из некоторого отдельного состояния State(j), за исключением переходов в состояния из линейного участка: п^^^ (переходы по счету).

5. Количество состояний, связанных с формированием некоторой отдельной выходной переменной Out(k): /iow(1|.

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

1. Память конечного автомата на статическом регистре.

Сложность памяти L„:

Ln =18 т.

С использованием введенных параметров конечного автомата оценка для сложности схемы функций перехода KCl L^. 1(J), связанной с отдельным состоянием State(j), может быть записана следующим образом:

■Д'ЬйИ,) +т) / =_£_

'082 (SSl0UU)+m)

Для того, чтобы получить интегральную оценку по всем п состояниям, используем числовые характеристики, предоставляемые теорией вероятностей. Поскольку целью исследования является получение оценок сложности реализаций не для конкретного задания конечного автомата, а для различных структур реализаций при неизвестных заранее параметрах конечного автомата, то эти параметры можно считать случайными величинами, и использование характеристик случайных величин представляется оправданным. Усредняя LKC4j) по множеству состояний, в качестве интегральной оценки сложности реализации отдельной функции блока KCl LKci получим:

Lxa =MLKCUsu,,)m=: \ ~ I ;—?-ч рт>

где МЬ1:С1(!!!аи) - математическое ожидание сложности реализации функции из блока КС].

Оценки для блока функций выхода КСг £к:2 для разных типов конечных автоматов:

^КС2(Миш) MLKC2(Мили)* ~

2к„,0, + «)

"j=ll°g2(sOMW + «) J '

logjM

2. Память конечного автомата на регистре сдвига.

¿Я =13", vy = l»og2(

State\Lme(j)

) ^

Lf!C2Wimu) ~ MLKC2Wum)(Oiin'

1 =

2 (5o«»)

t

Ä = lfog2(.

/

2И0«Г(Ц

Л = 11о82"о

Тогда суммарная оценка сложности реализации структуры:

где - технологический коэффициент, отражающий неодинаковость стоимости внешних (нестандартных) и внутренних связей на плате (обычно кт = 0,1 -5- 0,2). 3. Память конечного автомата на счетчике.

Сложность памяти Ln определяется сложностью реализации счетчика ZCT :

Ln = LCT = 24 m.

Оценки сложности стандартных блоков - дешифратора LrK. н мультиплексора Lus известны:

¿к- = (2W + l)]log2 2W[= m(2m +1),

Lus = 2m + {2m + l)]log2 2m[- 2m(m+\)+m. В соответствии со структурой композиционного ядра (рис. 3), максимальное количество функций в нестандартных блоках КС] и КС2 - 2". Однако при этом часть из них, связанных с переходами типа «всегда по счету» («всегда по записи») или «никогда по счету» («никогда по записи») - константы (их сложность равна 1), поэтому, например, для KCl получим:

'l »

~LLKCHj)

V 7=1

где Ь!:СЦ]) = 1 для функций-констант при = 0 («всегда по счету» или «никогда по счету»), или при = 1. Для остальных функций применяется оценка

2 SSlals(i)

Аналогично могут быть записаны оценки для КС2,

Кроме того, учитывая факт, что если из некоторого состояния осуществляется переход типа «всегда по счету», то это означает, что по записи переход невозможен и vice versa, удобно записать суммарную оценку для блоков KCl и КСг следующим образом:

-5с,

2JS4KU>

log2 Наш*,)

'> Ssmtt(j) — '

>sSuu{j) > ^

ксиг ~ •

у = 1

При определении функции блока КСз, обеспечивающей формировании сигналов на информационных входах счетчика, возможны два варианта: из некоторого состояния имеется только один переход по записи или вообще нет переходов по записи; из некоторого состояния имеется более одного перехода по записи. В первом случае зависимость функций перехода от входных сигналов уже учтена в функциях блока КСг при формировании сигнала разрешения записи. Для них £дгзи); < 1. Во втором случае функции формирования сигналов на информационных входах счетчика зависят также и от входных переменных, поэтому:

С Л,

L/;C3(J) ~ nstale\L,m(j)

2 1

- + 1 в случае >1,

/ «

где слагаемое «единица» учитывает соединение с выходом дешифратора.

¿ксзо) = О В случае = 0.

1ксмп = 1 в случае = 1.

Счетчик имеет т информационных входов, соответствующих т функциям. Поэтому:

(\_ п \

)

Наконец, в общем случае оценка сверху для Г выходных функций будет иметь вид:

( (а ЛЛ

I

^КСЦШ.п) ~ ^^КСММишХОч/ ~

2 - + 1

log

г JOuк»)

V * К ■ /У

Для автомата Мура асимптотическая оценка не нужна.

( <

и = 1

Тогда сложность всей структуры с учетом технологического коэффициента:

^Ыщ = + фЬщ + -^ОС + ¿СГ ) + ^КСЪ + ^КС* •

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

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

<

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

гае к^ - полное число входов элемента, Р. - число типов бесповторных функций от / аргументов, реализуемых элементом, полное число типов бесповторных логических функций от i аргументов.

Коэффициент функциональных возможностей называют также коэффициентом логической эффективности или эквивалентным числом входов элемента. В случаях Р. = Б. элемент

универсален, в случаях

Р. <£. I г

элемент многофункционален. Многофункциональность

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

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

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

Табл.

Правила порождения настроек

1

Уровень представления данных

Схемотехнический уровень

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

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

Понижение рангов некорневых вершин с получением одной настройки, у которой ранги некорневых вершин уменьшены на единицу.

объединение пар входов каждой из п вершин некорневого уровня, то есть добавление п внешних связей

Установка управляющего входа с получением настройки, у которой одна из вершин некорневого уровня заменена фактическим повторителем (ранг устанавливается в единицу)._

объединение т входов той вершины некорневого уровня, которая замещается повторителем, то есть добавление т-1 внешних связей

2

3

При анализе целесообразности автоматического порождения новой настройки сравниваются сложности реализаций двух альтернатив:

• Порождение настройки на основе применения правила ( к настройке Например, настройка йо = 2+2+1 является результатом применения к настройке ^ = 2+2+2 правила 3. При

этом образуется одна внешняя связь. В этом случае можно вычислить сложность такой реализации как сумму сложности настройки ^ (она равняется 6) и сложности, обусловленной одной внешней связью (1 кт).

• Реализация функции, эквивалентной 4;, путем использования множества Ее некоторых существующих настроек. Например, функция, арифметический полином которой имеет вид 2+2+1, может быть получена последовательным соединением двух настроек, арифметические полиномы которых имеют вид 2+1. При этом также образуется одна внешняя связь. В этом случае можно вычислить сложность такой реализации как сумму сложностей двух использованных настроек с арифметическими полиномами 2+1 (она равняется 3+3=6) и сложности, обусловленной одной внешней связью (1 кт).

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

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

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

Логическая сложность программы включает характеристики, обусловливающие трудность, длину ■ или невозможность доказательства корректности программы (Б. Шнейдерман). Рассматриваемые программы автоматизации синтеза характеризуются существенной логической сложностью, связанной с большим числом условий, учитываемых при синтезе, и связанной с этим многовариантностью и запутанностью структуры программ. Преодоление логической сложности, присущей ПО - главная цель различных способов визуализации проектируемого ПО, являющихся в настоящее время одним из развивающихся направлений теории проектирования ПО. В работе рассматриваются две группы задач: первая связана с представлением данных и программной реализацией процесса синтеза, вторая представляет предложения по решению типовых задач проектирования, часто встречающихся при построении сложных программных систем и поэтому требующих унификации, и их решения в форме визуального формализма М.Ф. Лекарева на базе ¿-сети.

Далее анализируются формы записи логических выражений, определяется формальная грамматика системы логических функций, рассматривается задача синтаксического анализе входного набора групп логических функций и формирование бесскобочной формы записи логических выражений с переходом к организации данных с использованием древовидное структуры. Общая структура решения наглядно представлена на рис. 4. Далее излагаете* стратегия покрытия с использованием древовидных структур. Описание основных проектные решений иллюстрируется сетевыми программами, выполненными с использованием ¿-сете (рис. 5). Упомянутые алгоритмы синтеза опубликованы и поэтому в автореферате подробно ш рассматриваются [2].

В главе 4 рассматриваются особенности организации управления данными в ¿-сети состав программ в системе автоматизации синтеза и управление их взаимодействием; методик тестирования системы; анализ эффективности использованных средств проектирования.

формирование древовидного представления логического выражения

и настроечной функции (основная итерация при синтезе)

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

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

Среди известных подходов к оценке затрат на разработку программного обеспечения анализируются метрики программных средств, разработанные Б.У. Боэмом, В.В. Липаевым, Р. Нельсоном. Результаты, получаемые при использовании перечисленных методик, весьма противоречивы, поэтому они были объектом критики.

Непригодность использования оценок человеко-месяцев, требуемых для разработки программной системы, связаны с тем, что стоимость проекта действительно зависит от числа людей и от числа месяцев, потраченных на проектирование, но его успешность нет (Ф.П. Брукс). Подобные метрики не учитывают также индивидуальные качества работы программистов (Р. Дистасо).

По Б.У. Боэму, анализируемый проект системы автоматизации синтеза, разработанный за 48 человеко-месяцев, относится к полунезависимому типу, характеризуемому неоднородностью состава исполнителей, их средним опытом работы. Объем проекта составляет около 130.000 строк исходного текста. Трудоемкость разработки по Боэму, определяется по формуле;

ЧМ = 3,0 (ЧИК/1000)1'12 [человеко-месяцев], где ЧИК - число исходных команд (строк исходного текста).

Для системы автоматизации затраты по Б.У. Боэму должны были составить около 700 человеко-месяцев. Производительность труда разработчиков, таким образом, должна составить 186 строк/человеко-месяц. Для анализируемого проекта имеем 2.700 строк/человеко-месяц. Производительность превышена примерно в 14 раз.

Для оценки затрат по В В. Липаеву имеем:

ЧМ = 12 (0,007 ЧИК0'81), то есть затраты на разработку должны были составить 1164 человеко-месяца, что в 24 раза больше реальной трудоемкости разработки.

Используя оценку Р. Нельсона (ЧИК =175 ЧМ1,03) получаем для проекта с трудоемкостью 48 человеко-месяцев достижимый объем разработки около 10.000 строк исходного текста. Производительность превышена а 13 раз.

Альтернативой оценки используемых средств проектирования программ могут служить методики, основанные на оценке качественных характеристик получаемого ПО. Для оценки таких характеристик также предпринимались попытки их количественного выражения (М. Холстед, Т.Дж.Маккейб), однако для больших проектов со сложной логической структурой применение подобных количественных оценок обычно затруднено. Другой практический подход к оценке качества программ основывается на принципе: хорошие программы производятся по хорошей технологии. При этом качество программного продукта обеспечивается различными этапами жизненного цикла программной системы, а не только этапом программирования.

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

метода проектирования создает основу для подготовки и взаимодействия специалистов, приводит к уменьшению проектных и конструктивных ошибок. Все это определяет концептуальное единство проекта: «лучше иметь систему, не имеющую некоторых не слишком существенных свойств, но воплощающую в единое целое множество концепций проектирования, чем систему, содержащую много хороших, но независимых и нескоординированных идей» (Ф.П. Брукс). Применяя к этому случаю определение, данное Д.С. Лихачевым в статье «Контрапункт стилей как особенность искусств» (стиль - всегда некоторое единство), можно говорить о принципах хорошего стиля проектирования качественной программной системы.

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

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

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

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

4. Разработана программа синтеза схем дискретных преобразователей на задаваемом избыточном элементном базисе.

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

1. Мелехин В.Ф., Душутина Е.В., Пышкин ЕВ. Автоматизация синтеза при логическои» проектировании цифровых устройств на основе базовых матричных кристаллов Л Вычислительные, измерительные и управляющие системы: Сб. научных трудов СПбГТУ. ■ Спб,1994.

2. Лекарев М.Ф., Мелехин В.Ф., Пышкин Е.В. Автоматизированный синтез комбинационные схем на задаваемом наборе логических элементов // Вычислительные, измерительные I управляющие системы: Сб. научных трудов СПбГТУ. - Спб, 1995.

3. Мелехин В.Ф., Лекарев М.Ф., Давыдов В.Г., Пышкин Е.В. Системы автоматизации синтез* цифровых устройств. Кафедра автоматики и вычислительной техники.// Российская научно-техническая конференция "Инновационные наукоемкие технологии для России." 25-27 апрел5 1995г. Тезисы докладов. Часть 8,-Спб: СПбГТУ, 1995.

4. Пышкин Е.В. Автоматизация синтеза многоуровневых схем на задаваемом избыточнок элементном базисе // Третья Санкт-Петербургская Ассамблея молодых ученых и специалистов Тезисы докладов. СПб., 1998,- с.4б.

5. Лекарев М.Ф., Мелехин В.Ф., Пышкин Е.В. Автоматизация синтеза цифровых устройств н; основе базовых матричных кристаллов // Десятая научно-техническая конференции 'Экстремальная робототехника". Сборник докладов. СПб., ЦНИИ РТК, 1999.

Публикации по теме диссертации

Введение

1. Проблема автоматизации синтеза на задаваемом избыточном наборе элементов

1.1. Развитие систем автоматизации проектирования

1.2. Анализ возможности интеграции существующих систем синтеза и моделирования. Актуальность и оценка сложности задачи синтеза многоуровневых схем на избыточном и изменяемом базисе

1.3. Иерархия проблем проектирования системы ("дерево проблем ")

2. Модели дискретных преобразователей, оценки сложности реализаций, организация процесса синтеза схем преобразователей на задаваемом наборе элементов

2.1. Система алгоритмических алгебр и модель дискретного преобразователя

2.2. Декомпозиция конечных автоматов при синтезе последователъностных цепей

2.3. Формальная декомпозиция автомата, заданного в виде графа переходов

2.3.1. Общая постановка задачи

2.3.2. Критерии декомпозиции

2.3.3. Возможность декомпозиции в заданных условиях и правила «уступок»

2.3.4. Оптимизация результатов

2.4. Функциональная декомпозиция схемных решений

2.4.1. Параметризуемое композиционное ядро как основа функциональной декомпозиции

2.4.2. Разработка системы параметров абстрактного автомата

2.4.3. Оценки сложности вариантов параметризуемого ядра

2.4.4. Примеры использования методики оценки сложности структурной организации синтезируемого устройства для различных конечных автоматов

2.5. Функциональная декомпозиция при синтезе

2.5.1. Использование формализма арифметических полиномов при функциональной декомпозиции

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

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

3. Анализ организации данных, вычислительного процесса и управления процессом при автоматизации синтеза

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

3.2. Проблемы разработки программных систем

3.2.1. Логическая природа сложности задач и преодоление сложности

3.2.2. Иерархическая декомпозиция и иерархическая организация. Визуализация ПО. Визуальный формализм разработки ПО на базе сетевой модели (Z-сеть)

3.2.3. Элементы методики проектирования сложного ПО

3.3. Формы представления данных в процессе синтеза и связанные с этим частные задачи проектирования ПО

3.3.1. Формы записи логических выражений. Задача синтаксического анализа и формальные грамматики

3.3.2. Функциональная декомпозиция с использованием формализмов теории графов

3.3.3. Представление и использование элементного базиса

3.4. Решение типовых проблем проектирования ПО в форме визуального формализма на базе L-cemu

3.4.1. Обработка параметров управления программой

3.4.2. Обработка ошибок

3.4.3. Организация работы с файлами в кодовых форматах

4. Система автоматизации синтеза и анализ эффективности средств ее проектирования

4.1. Проблемы построения интерфейса

4.1.1. Интерфейсы данных в концепции визуального формализма разработки программного обеспечения (Ь-сеть)

4.1.2. Организация взаимодействия между подсистемами. Связь с другими системами

4.1.3. Взаимодействие с проектировщиком. Участие человека в процессе проектирования

4.2. Методика, использованная при тестировании системы

4.3. Оценка эффективности использованных средств проектирования

Актуальность темы

В настоящее время при разработке компонентов электронно-цифровой аппаратуры используют технологию больших (БИС) и сверхбольших интегральных схем (СБИС).

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

В последнее время по проблеме автоматизации проектирования цифровых устройств и, в частности, автоматизации синтеза ведутся интенсивные исследования [1 - 3, 11, 29, 34, 35, 37, 44, 57]. Возрастание значения систем автоматизации синтеза связано, в частности, с отчетливо выраженной тенденцией к быстрому расширению рынка специализированных заказных интегральных схем [11, 29]. Создание полузаказных СБИС стало компромиссным подходом, позволяющим снизить стоимость и сложность проектирования СБИС. При этом возникли и параллельно развиваются два направления полузаказных СБИС: на основе базовых матричных кристаллов (БМК) и на основе программируемой логики.

Основанием для данной работы стало рассмотрение проблем и проектных решений по разработке и развитию системы автоматизации синтеза цифровых устройств на задаваемом избыточном элементном базисе применительно к использованию базовых матричных кристаллов (БМК).

По статистическим данным, в настоящее время до 30% СБИС создаются на основе БМК (Gate Arrays). На большинстве крупных отечественных предприятий, связанных с разработкой и производством радиоэлектронной аппаратуры, существуют системы автоматизированного проектирования и изготовления полузаказных БИС на основе БМК. В большинстве случаев такие БИС удовлетворяют жестким требованиям по климатике и другим условиям эксплуатации, характерным для аппаратуры специального назначения. При этом САПР не поддерживают синтез, а поддерживают только анализ (моделирование и отработка тестов), а также этап конструкторского проектирования.

Развитие технологии проектирования матричных СБИС на основе БМК было обусловлено следующими факторами: сокращение трудоемкости изготовления БИС и СБИС на БМК, которые служат в качестве полуфабрикатов, как на стадиях опытного производства, так и при промышленном выпуске; возможность эффективной автоматизации благодаря регулярности структуры БМК с выделенными трассами для соединения макроэлементов в требуемую функциональную схему; возможность широкого применения готовых проектных решений, оформленных в виде библиотек, на этапах функционально-логического, схемотехнического и топологического проектирования, что обеспечивает существенное сокращение сроков и повышения качества разработки широкой номенклатуры специализированных БИС и СБИС, делает экономически выгодным их выпуск малыми партиями [13, 41, 58, 63].

В цикле создания БИС на БМК время синтеза составляет до 20%. Учитывая сложность формализации синтеза и актуальность наиболее полного использования ресурсов БМК, выполненных по микронной, а не субмикронной технологии, задача автоматизации синтеза не считалась насущно необходимой. Интерес к этой проблеме возник при разработке проекта «Интегрированная проектно-производственная система полупроводниковых структур» (ИППС ПС), выполняемого ЦНИ СПбГТУ и НПО «Светлана» по государственному заказу. В основу создания этой системы был положен подход проф. Й. Берга к «одночиповому» производству СБИС, позволяющему исключить потребность в больших «чистых» специализированных помещениях и организовать производство СБИС с высоким уровнем интеграции. В рамках этого проекта необходима сквозная автоматизация, включая автоматизацию синтеза. Эта задача решалась группой разработчиков СПбГТУ под руководством проф. В.Ф. Мелехина [37, 46, 54, 55]. Для теоретического обоснования проектных решений при разработке ИППС ПС были в значительной мере использованы положения теории проектирования цифровых устройств, которая была в наиболее общем (абстрактном) виде разработана В.М. Глушковым и развита его последователями: Ю.В. Капитоновой и А.Т. Мищенко в части логического проектирования дискретных устройств, П.М. Ивановым (Иуаном) в части построения теории дискретных преобразователей информации [16 - 18, 28].

В настоящее время интенсивно развивается подход, связанный с построением систем автоматизации проектирования БИС на базе устройств программируемой логики (ПЛ). Приоритетность данного направления обусловлена, главным образом, предоставляемыми возможностями сокращения цикла «проектирование-изготовление», обеспечения стопроцентной тестируемости проектируемой системы, внесения изменений в систему, что обеспечивает экономическую эффективность создания новых систем [4, 27]. Следует заметить также, что при синтезе ПЛ пространство решений значительно меньше, чем при синтезе многоуровневых структур, что определяет меньшую трудоемкость поиска логического решения задачи.

Однако направление синтеза многоуровневой логики на основе БМК также нельзя считать исчерпанным. В связи с появлением и развитием средств программируемой логики актуальность автоматизации синтеза для БМК связана со следующим. Фирмы, производящие СБИС ПЛ, ориентируются, главным образом, на коммерческий и отчасти на промышленный стандарт, что затрудняет использование средств программируемой логики в производстве систем специального назначения (например, системах, требующих военной приемки, робототехнических системах). При этом, однако, остается возможность и целесообразность их использования для ускорения создания и отладки опытных образцов. Применение существующих технологий позволяет использовать имеющиеся средства анализа и тестирования прототипа, уменьшая тем самым средства, которые необходимо было бы затратить на реализацию аналогичных этапов при использовании БМК.

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

Актуальность работы определяется также сформулированными и прошедшими практическую апробацию предложениями по методологии проектирования программного обеспечения (ПО), отличающегося существенной логической сложностью. В основу анализируемого подхода к проектированию ПО положено использование визуального формализма проектирования ПО (¿-сеть), предложенного и развитого проф. М.Ф.Пекаревым [19, 33, 76].

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

Цель работы

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

Предмет исследования

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

Процедура функциональной декомпозиции при синтезе с учетом заданного элементного базиса.

Сравнительные оценки сложности реализации структурных решений.

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

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

Методы исследования

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

Научная новизна и практические результаты

1. Разработана система параметров, характеризующая особенности реализуемого алгоритма, существенные для сложности вариантов структур с различными типами ядер и разработана система оценок сложности, использующих выделенные параметры и учитывающих особенности реализации типовых (библиотечных) узлов и нестандартных блоков структуры, для выбора варианта структурной организации проектируемого устройства. [34, 35, 54]

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

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

4. Разработано программное обеспечение для системы автоматизации синтеза на задаваемом избыточном элементном базисе, реализующее процедуру функциональной декомпозиции преобразователя и покрытия выделенных фрагментов элементами из заданного набора (синтез схемы в виде многоуровневой сети) и вошедшее в состав системы автоматизации синтеза цифровых устройств. [34, 36, 37, 52, 53, 55]

5. Обоснована организация данных, организация процесса обработки информации и организация управления вычислительным процессом в программной системе автоматизации синтеза с использованием визуального формализма на базе L-сети. [33, 36, 53, 55]

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

Апробация работы

Основные результаты работы докладывались на Российской научной конференции "Инновационные наукоемкие технологии для России" 25-27апреля 1995г., , на Третьей Санкт-Петербургской Ассамблее молодых ученых и специалистов (СПбГТУ, 1998г.), на Десятой научно-технической конференции "Экстремальная робототехника" (СПб, ЦНИИ РТК, 1999г.), приводились в отчетах по научно-исследовательской работе "Система автоматизации синтеза при структурно-логическом проектировании" (Санкт-Петербург, АЦИА, 1992 и 1993гг.), а также были использованы в ходе научной работы по программе DAAD «Стипендия имени Леонарда Эйлера» в техническом университете Hamburg-Harburg (Санкт-Петербург, Россия - Гамбург, Германия, 1998-99г.) [8].

В конкурсе 1997г. участниками проекта, в котором используются результаты диссертационной работы, был выигран грант на 1998-1999г. по теме «Разработка теории и средств создания среды для автоматизированного проектирования управляющих систем».

По рассмотренным темам имеются публикации, подготовленные при участии автора. [36, 37, 46, 47, 52]

Основные результаты проделанной работы заключаются в следующем:

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

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

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

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

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

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

Заключение

1. Автоматизация проектирования БИС: Практ. пособие: В 6 кн. / Под. ред. Г.Г.Казенкова.- М.: Высшая школа, 1990.- Кн.2: Функционально-логическое проектирование БИС / П.В.Савельев, В.В.Коняхин,- 1990,- 165с.

2. Автоматизированное проектирование СБИС на базовых кристаллах. / А.И.Петренко, В.Н.Лешаков, А.Я.Тетельбаум, В.А.Бердышев и др.; Под ред. С.С.Бадулина.- М.: Радио и связь, 1988,- 160с.

3. Аллен Дж. Параметрический синтез СБИС-систем // ТИИЭР, том 78, № 2, 1990.- с.124-143.

4. Антонов А.П., Мелехин В.Ф., Филиппов A.C. Проектирование электронных систем. Современные средства и технологии. Проблемы освоения и развития (в печати).

5. Артюхов В.Л. Логические методы синтеза дискретных систем. Конспект лекций.- Л.: Институт повышения квалификации работников судостроительной промышленности, 1974,- 98с.

6. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1 / Пер. с англ.- М.: Мир, 1978.- 612с.

7. Бар Р. Язык Ада в проектировании систем / Пер. с англ.- М.: Мир, 1988.-320с.

8. Воронин В.Н., Кораблев В.В., Селезнев К.В. Опыт совместной работы с вузами и фирмами Германии // Научно-технические ведомости СПбГТУ, № 1 (11).- СПб.: 1998,- с.109-114.

9. Боэм Б., Браун Дж., Каспар X. и др. Характеристики качества программного обеспечения / Пер. с англ.- М.: Мир, 1981.-206с.

10. Боэм Б.У. Инженерное проектирование программного обеспечения / Пер. с англ.- М.: Радио и связь, 1985.- 511с.

11. Брейтон Р.К., Хэтчел Г.Д., Санджованни-Винцетелли А.Л. Синтез многоуровневых комбинационных логических схем // ТИИЭР, том 78, № 2, 1990,-с.38-83.

12. Брукс Ф.П. Как проектируются и создаются программные комплексы: Мифический человеко-месяц. Очерки по системному программированию / Пер. с англ.- М.: Наука, 1979,- 151с.

13. Быстродействующие матричные БИС и СБИС. Теория и проектирование / Файзулаев Б.Н. и др.- М.: Радио и связь, 1989.- 304 с.

14. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные применения. М.: Наука, Гл. ред физ-мат. лит., 1988,- 480с.

15. Вирт Н. Долой «жирные» программы: Пер. с англ. // Открытые системы, № 6 (20).-М.: 1996.- с.27-31.

16. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Автоматизация проектирования вычислительных машин. Киев: Наукова думка, 1975.- 232с.

17. Глушков В.М., Капитонова Ю.В., Мищенко А.Т. Логическое проектирование дискретных устройств,- Киев: Наукова думка, 1987.- 262с.

18. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование.- Киев: Наукова думка, 1989.- 376 с.

19. Горячев Е.В., Лекарев М.Ф., Петренко А.А Организация аппаратного и программного обеспечения ЭВМ на базе сетевой модели. // Вычислительные, измерительные и управляющие системы: Сб.научных трудов,- Л.: ЛГТУ, 1990.-с.31-34.

20. Грис Д. Проектирование компиляторов для цифровых вычислительных машин / Пер. с англ.- М.:Мир,1975,- 544с.

21. Грушин С.И., Душутин И.Д., Мелехин В.Ф. Проектирования аппаратных средств микропроцессорных систем.- Л.: ЛПИ, 1990.- 84с.

22. Гуденаф Дж.Б., Макгоуэн К.Л. Обеспечение качества программных средств: Испытания и оценка// ТИИЭР,- Пер.с англ.- т.68, № 9, 1980.- с.66-73.

23. Джонстон Г. Учитесь программировать / Пер. с англ.- М.: Финансы и статистика, 1989,- 368с.

24. Дистасо Дж.Р. Обзор методов управления разработкой программного обеспечения (по состоянию на 1980 г.) // ТИИЭР.- Пер.с англ.- т.68, № 9, 1980.-с.80-99.

25. Дубова Н. Знак качества программному продукту // Открытые системы, № 6(20).- М.: 1996.- с.55-59.

26. Дьяков Ю.Н., Попов A.A., Яковлев А.Т. Основные направления и проблемы развития микроэлектроники в России // Информационные технологии и вычислительные системы, №1.- М.: 1995.- с.64-73.

27. Ефремов В.Д., Колесников Д.Н., Мелехин В.Ф. Информационные технологии создания сложных радиоэлектронных комплексов // Научно-технические ведомости СПбГТУ, №1,- СПб.: 1996.- с.49-53.

28. Иванов (Иуан) П.М. Алгебраическое моделирование сложных систем,- М.: Наука, Физматлит, 1996,- 272 с.

29. Кейвин III P.K. Проектирование интегральных схем: Направления и проблемы // ТИИЭР, том 78, № 2, 1990,- с.213-235.

30. Кертис Б. Измерения и эксперименты в проектировании программных средств // ТИИЭР,- Пер.с англ.- т.68, № 9, 1980,- с.129-145.

31. Колмогоров А.Н. Теория информации и теория алгоритмов.- М.:Наука, 1987,- 304с.

32. Колосов В.Г., Мелехин В.Ф. Проектирование узлов и систем автоматики и вычислительной техники,- Л.: Энергоатомиздат, 1983.- 255с.

33. Лекарев М.Ф. Визуальный формализм для разработки программного обеспечения.- СПб.: Санкт-Петербургский гос. техн. ун-т., 1997.- 95с.

34. Лекарев М.Ф., Мелехин В.Ф. Автоматизация проектирования дискретных устройств,- Л.: ЛПИ, 1978,- 80с.

35. Лекарев М.Ф., Мелехин В.Ф. Автоматизированное проектирование структур цифровых устройств,- Л.: ЛПИ, 1984,- 76с.

36. Лекарев М.Ф., Мелехин В.Ф., Пышкин Е.В. Автоматизация синтеза цифровых устройств на основе базовых матричных кристаллов // Научно-техническая конференция "Экстремальная робототехника". Сборник докладов.-СПб: ЦНИИ РТК, 1999 (в печати).

37. Лекарев М.Ф., Мелехин В.Ф., Пышкин Е.В. Автоматизированный синтез комбинационных схем на задаваемом наборе логических элементов //

38. Вычислительные, измерительные и управляющие системы: Сб. научных трудов (Труды СПбГТУ №452).- СПб.: 1995,- с.93-206.

39. Липаев В.В. Тестирование программ,- М.: Радио и связь, 1986,- 296с.

40. Липаев В.В., Потапов А.И. Оценка затрат на разработку программных средств,- М.: Финансы и статистика, 1988.- 224с.

41. Лихачев Д.С. О филологии,- М.: Высшая школа, 1989,- 208с.

42. Логическое проектирование БИС / Под ред. В.А.Мищенко.- М.: Радио и связь, 1984,- 352 с.

43. Майерс Г. Искусство тестирования программ / Пер. с англ.- М.: Финансы и статистика, 1982,- 182с.

44. Майерс Г. Надежность программного обеспечения / Пер. с англ.- М.: Мир, 1980,- 360с.

45. Макфарланд М.С., Паркер Э.С., Кампосано Р. Высокоуровневый синтез цифровых систем // ТИИЭР, том 78, № 2, 1990.- с.84-103.

46. Мелехин В.Ф. Микро-ЭВМ с преобразованием информации отображением множеств на основе структур данных, размещаемых в едином запоминающем устройстве. Диссертация на соискание степени доктора технических наук.- Л.: ЛПИ, 1984,-421с.

47. Мелехин В.Ф., Лекарев М.Ф., Давыдов В.Г., Пышкин Е.В. Системы автоматизации синтеза цифровых устройств // Российская научно-техническая конференция "Инновационные наукоемкие технологии для России",- Тез. докл., ч.8.- СПб: СПбГТУ, 1995,- с.23.

48. Мелехин В.Ф., Сидоров С.В. Задача функционально-структурной организации систем управления // Вычислительные, измерительные и управляющие системы. Труды СПбГТУ №449,- СПб.: 1994, с.3-15.

49. Новый Большой англо-русский словарь: в 3-х т. Т.2 / Апресян Ю.Д., Медникова Э.М., Петрова А.В. и др.; Под общ. рук. Ю.Д.Апресяна.- М.: Рус. яз., 1993 832с.

50. Поттосин И.В. Добротность программ и информационных потоков // Открытые системы, №6 (32).- М.: 1998,- с.41-45.

51. Программирование, отладка и решение задач на ЭВМ единой серии. Язык ПЛ/1: Учебное пособие для вузов / И.А.Кудряшов, В.Д.Жилеев, Н.Х.Кушнер и др.; Под ред. И.А.Кудряшова.- Л.: Энергоатомиздат. Ленингр. отд-ние, 1989.-280с.

52. Пышкин Е.В. Автоматизация синтеза многоуровневых схем на задаваемом избыточном элементном базисе // Третья Санкт-Петербургская Ассамблея молодых ученых и специалистов. Тезисы докладов. СПб.: 1998.- с.46.

53. Пышкин Е.В. Программа автоматического синтеза логических схем по бесповторным функциям. Дипломный проект. СПб.: ЛГТУ, 1992 - 163с.

54. Система автоматизации синтеза при структурно-логическом проектировании. Отчет по научно-исследовательской работе / Мелехин В.Ф. и др.- СПб.: АЦИА, 1992,- 356 с.

55. Система автоматизации синтеза при структурно-логическом проектировании. Отчет по научно-исследовательской работе / Мелехин В.Ф. и др.- СПб.: АЦИА, 1993,- 140 с.

56. Степанов В.А. Метод минимизации логических функций в избыточных базисах с операцией сложения по модулю два // Вычислительные, измерительные и управляющие системы: Сб. научных трудов (Труды СПбГТУ №449).- СПб.: 1994,- с.90-95.

57. Степанов В.А. Синтез информационных систем алгебраическими методами //Научно-технические ведомости СПбГТУ, № 1 (11).- СПб.: 1998,- с.103-105.

58. Томас Д.Э. Автоматизированный синтез цифровых систем.//ТИИЭР.- 1981.-Т.69, N 10,- с.20-35.

59. Фридман А.Д., Менон П.Р. Теория и проектирование переключательных схем / Пер. с англ.; Под ред. В.А.Тафта.- М.: Мир, 1978.- 580с.

60. Харрисон Д.С., Ньютон А.Р., Спикелмайер P.J1., Варне Т.Дж. Среда САПР для проектирования интегральных схем и электронных систем // ТИИЭР, том 78, №2, 1990,- с.185-212.

61. Холстед М.Х. Начала науки о программах / Пер. с англ.- М.: Финансы и статистика, 1981.- 128с.

62. Черноножкин С. Меры сложности программ (обзор) // Системная информатика, №5.- Новосиборск: Наука, 1996, Вып.5.- с.88-227.

63. Шива С.Г. Автоматизированный синтез аппаратных средств // ТИИЭР.-1983.-Т.71, N 1.- с.95-100.

64. Шило B.JI. Популярные цифровые микросхемы: Справочник. 2-е изд., испр.- Челябинск: Металлургия, Челябинское отд.,1989.- 352с.

65. Altera Application Handbook. Altera Corp., April 1992.

66. Altera. MAX + PLUS II. Programmable Logic Development System. Getting started. Altera Corporation. Version 6.0. November 1995.

67. Boolean Function Complexity ./Edited by M.S.Peterson. London Mathematical Society Lecture Note Series. 169. Cambridge University Press, 1992.

68. Chow T.S. Testing software design modeled by finite-state machines // IEEE Trans. Software Eng., vol.4, pp.278-286, May, 1978.

69. FPGA Data Book and Design Guide. Actel Corp., 1996.

70. Glass, Robert L. Software Conflict. Essays on the Art and Science of Software Engineering. Yourdon Press. Prentice-Hall Inc., 1991.

71. Harel D. On visual formalisms // Communication of the ACM. May 1988. Vol.31. N5, pp.514-530.

72. Hoare, Charles A. Unifying Theories of Programming. Prentice-Hall Inc., 1998.

73. Intel 82288 Bus Controller for iAPX 286 Processor // Intel 286 Microprocessors. Intel Corp., June 1982.

74. International Standard ISO 9000-3. Quality management and quality assurance standards. Part 3: Guidelines for the application of ISO 9001:1994 to the development, supply, installation and maintenance of computer software.

75. Le Petit Larousse. Dictionnaire encyclopédique. Larousse, 1993, Paris.152

76. Lekarev M.F. Das graphische Verfahren der Software-Entwicklung für logisch komplizierte Anwendungen // Technische Berichte der Fachhochschule Hamburg, N25 (Aug. 1993), s.36-38.

77. Mesarovic M.D., Takahara Y. Abstract Systems Theory. Springer Verlag, 1989.

78. Ming Li., Paul Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, 1993.

79. Pottosin I.V. A "Good Program": An Attempt at an Exact Definition of the Term // Programming and Computer Software. Vol.23, №2, 1997,- p.59-69.

80. Sommerville I. Software Engineering. Addison Wesley Publishers Co., 1996.

81. Straker, David. C-style: standards and guidelines. Prentice Hall, International (UK) Ltd., 1992,- 23 lp.

82. Weinberg, Gerald M. Quality Software Management: Volume 1. Systems Thinking. Dorset House Publishing, New York, 1992.