Содержание к диссертации
ВВЕДЕНИЕ 4
1 глава. ОСОБЕННОСТИ ЛОГИЧЕСКОГО ПРОЕКТИРОВА
НИЯ НА ОДНОРОДНОЙ СРЕДЕ 13
1.1. Параметры однородных сред 13
1.2. ОВС - настраиваемая однородная среда 16
1.3. Использование настраиваемых логических модулей при логическом проектировании 21
1.4. Выводы 29
2 глава. ИСПОЛЬЗОВАНИЕ ДЕКОШОЗИЦИОННЫХ МЕТОДОВ ДНЯ СИНТЕЗА ЛОГИЧЕСКИХ ФУНКЦИЙ С ИСПОЛЬЗОВАНИЕМ НАСТРАИВАЕМЫХ ЛОГИЧЕСКИХ МОДУЛЕЙ 30
2.1. Простая неразделительная декомпозиция 31
2.2. Выделение функции V, 34
2.3. Выбор представления исходной логической функции 36
2.4. Выводы 41
3 глава. ПОСТРОЕНИЕ НАСТРАИВАЕМЫХ ЛОГИЧЕСКИХ МОДУЛЕЙ ИЗ ЭЛЕМЕНТОВ ОДНОРОДНОЙ ЗЫЧИСЛИТЕЛЬНОЙ СРЕДЫ 42
3.1. Организация совокупности модулей
в однородной среде 42
3.2. Определение настроечных операций
НЛМОВС 53
3.3. Оценка сложности реализации логической функции совокупностью НЛМОВС 60
3.4. Выводы - З
4 глава. РЕАЛИЗАЦИЯ СОВОКУПНОСТИ НАСТРАИВАЕМЫХ МОДУЛЕЙ В ОДНОРОДНОЙ СРЕДЕ 63
4.1. Размещение НЛМОВС в однородной среде 64
4.2. Организация инвариантных преобразований НЛМОВС 74
4.3. Настройка среды при размещении в ,ней НЛМОВС 77
4.4. Оценка длины транзитных участков среды 80
4.5. Организация каналов связи в однородной среде 88
4.6. Выводы 98
5 глава. ОПИСАНИЕ КОМПЛЕКТА ПРОГРАММ АВТОМА ТИЗИРОВАННОГО СИНТЕЗА ЛОГИЧЕСКИХ ФУНКЦИЙ 3
ОДНОРОДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ 100
5.1. Описание программного сегмента 3ADR0 100
5.2. Описание блок-схемы программного ,сегмента 103
5.3. Описание программного сегмента PROBLEM. 106
5.4. Описание блок-схемы программного сегмента 109
5.5. Характеристики программных сегментов 3
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА 115
Введение к работе
Требования, предъявляемые к устройствам вычислительной техники на современном этапе (малые габариты, высокая надежность, высокая производительность, малое потребление энергии), могут быть удовлетворены только при постоянном росте степени интеграции элементной базы устройств ЭВА. Это приводит к тому, что возрастает объем использования в устройствах вычислительной техники заказных и полузаказных БИС. В [72]приводится прогноз, согласно которому доля заказных и полузаказных схем в объеме продаж к концу текущего десятилетия увеличится примерно с 20 до 50$. Уровень интегральной технологии в настоящее время позволяет производить интегральные схемы, объединяющие на одном кристалле десятки и сотни тысяч транзисторов. В то же время затраты на разработку таких БИС еще достаточно велики, и их производство становится рентабельным лишь при относительно крупных объемах производства. Так производство заказных БИС в настоящее время становится рентабельным при объеме их выпуска свыше примерно 100 000 изделий. Использование матричных БИС несколько улучшает ситуацию: их разработка становится рентабельной при размере партии порядка 30 000 штук. Для многих видов аппаратуры, которая не выпускается массовыми тиражами и предназначена для специального применения, но к которой предъявляются высокие требования по скорости, единственным на сегодня способом усовершенствования технологии производства представляется использование специфических БИС - универсальных микроэлектронных однородных сред, настраиваемых на выполнение конкретных функций в устройствах ЭВА самим заказчиком или даже перестраиваемых в процессе эксплуатации. Они облада - 5 ют следующими свойствами: регулярность структуры, что наилучшим образом отвечает требованиям интегральной технологии; являются программируемыми, что позволяет при решении каждой конкретной задачи приспосабливать технологически одинаковую структуру устройства к структуре решаемой задачи. Областями применения такого рода схем являются ( И2-1 ):
- цифровая обработка изображений ;
- цифровая фильтрация ;
- управление роботами ;
- обработка сейсмической и метеорологической информации.
Требованиями к такого рода устройствам, в частности,являются .; высокая надежность и способность обрабатывать информацию в реальном масштабе времени. Требование обработки информации в реальном масштабе времени при существующем быстродействии логических элементов может быть удовлетворено лишь при организации конвейерной и параллельной обработки информации с пользованием подхода, называемого коллективом вычислителей
( [І0] ). В основе этого подхода лежит применение однородных вычислительных систем, структур и сред.
Использование однородной вычислительной среды в качестве элементной базы позволяет обеспечить высокую живучесть устройства за счет наличия резервных элементов в схеме, которые в процессе эксплуатации заменяют выбывшие. Кроме того, регулярность структуры схемы позволяет организовать достаточно простые методы контроля и диагностики схем в процессе производства, что так же способствует снижению их стоимости.
Одной из наиболее распространенных задач при проектировании ЭВА является реализация некоторой логической функции или системы функций на заданной элементной базе. При этом решение задачи не является однозначным и зависит от требований, предъявляемых к устройствам ЭВА. Чем больше число переменных, от которых зависит логическая функция, тем сложнее найти для нее оптимальную реализацию в соответствии с принятыми критериями. Поэтому усилия разработчиков ЭВА постоянно направлены на разработку средств автоматизации проектирования логических функций, которые позволяют по описанию функции находить ее реализацию в требуемой элементной базе близкую к оптимальной. Процесс проектирования можно условно разделить на несколько относительно самостоятельных этапов. При этом решения, принятые на каждом этапе, влияют на качество решения последующих этапов. Поэтому желательно на более ранних этапах проектирования учитывать требования, предъявляемые к последующим.
Использование однородной вычислительной среды в качестве элементной базы изменяет процесс проектирования, так как происходит совмещение этапов логического и конструкторского проектирования устройства: конструкторское проектирование сводится к созданию программы настройки участка среды. А это требует разработки средств автоматизации программирования среды с учетом особенностей всех этапов проектирования и самой среды.
Начиная с 60-х годов в нашей стране и за рубежом публикуются работы, в которых обосновываются подходы к выбору конкретных структур однородной среды, функциональных возможностей ячейки среды, способов реализации комбинационных автоматов и автоматов с памятью в таких средах ( [11 , 37 , E6J , J,
Выбор функциональных возможностей ячейки близким к базису широко используемому при логическом синтезе в настоящее время (функция Вебба, штрих Шеффера, сложение по модулю 2) позволяет использовать в процессе логического синтеза в однородной среде хорошо разработанный аппарат. Однако такие методы проектирования логических схем, как представление логических функций нормальными формами с последующей факторизацией оказываются не вполне подходящими для новой элементной базы из-за изменения критериев, налагаемых на проектируемые схемы. Например, для среды, организованной по принципу близкодействия (связь осуществляется только между соседними ячейками среды), передача информации по полю среды осуществляется с помощью таких же элементов среды, что и для операционной обработки. Это не позволяет использовать критерии, ориентированные на минимальное количество операционных элементов (минимальные формы), так как организация связей между операционными элементами требует количества ячеек среды сравнимого с используемым для непосредственной обработки информации.
Все изложенное выше позволило сформулировать следующую цель диссертационной работы: разработать автоматизированный метод синтеза логических функций в однородной вычислительной среде, позволяющий вести процесс проектирования с учетом особенностей среды и размеров участка, выделенного для реализации схемы.
Исходя из поставленной цели в данной работе решены следующие задачи:
- разработан способ представления заданной логической функции логической сетью в базисе используемой однородной среды и направленный на минимизацию площади участка среды, занимаемого схемой ;
- разработан способ реализации полученной логической сети в поле среды с учетом размеров участка, выделяемого для реализации, и задержек, вносимых элементами среды при передаче
- информации по полю среды ;
- предусмотрен интерактивный режим работы программ для возможности разработчика влиять на ход процесса проектирования ;
- осуществлена программная реализация разработанных методов синтеза на языке программирования ІШ/І.
Решив поставленные задачи, автор защищает:
1. Подход к синтезу в однородной среде, основанный на ис
пользовании настраиваемых логических модулей, реализованных
из элементов среды.
2. Способ выбора совокупности настраиваемых логических
модулей.
3. Методику представления заданной логической функции совокупностью настраиваемых логических модулей.
4. Способ определения настроечных операций модуля, основанный на анализе представления заданной логической функции и порождающей функции модуля в базисе функций Радемахера-Уолша.
5. Метод оценки расстояний между источниками и приемниками информационных сигналов в поле однородной среды.
6. Метод согласования задержек информационных сигналов в поле однородной среды, поступающих на входы настраиваемого модуля.
7. Комплект программ, осуществляющих реализацию указанных методов.
В качестве методов исследования использовался анализ содержательных аспектов проблемы и их интерпретация в терминах булевой алгебры. В качестве формальных методов использовался аппарат функций алгебры логики, методы теории графов, аппарат теории множеств, аппарат спектральных преобразований в базисе Радемахера-Уолша.
Научная новизна работы заключается в следующем:
- предложены шесть типов логических модулей, реализованных в однородной среде, которые за счет настроечных операций позволяют реализовать любую из 256 логических функций, зависящих от трех переменных ;
- предложен эффективный метод определения настроечных операций указанной совокупности модулей, основанный на анализе представлений в базисе Радемахера-Уолша порождающей функции модуля и реализуемой функции ;
- предложен метод представления заданной логической функции совокупностью указанных модулей, основанный на декомпозиционном подходе и направленный на минимизацию площади участка среды для реализации функции ;
- разработан способ оценки расстояний на среде, основанный на коррекции манхеттенового расстояния между узлами прямоугольной сетки координат, в которых расположены элементы среды ;
- разработан метод согласования задержек по входам модуля в зависимости от положения модуля в среде по отношению к координатам входа переменных в поле среды ;
- разработан алгоритм синтеза каналов связи в среде, основанный на предложенном способе оценки расстояний на среде.
Практическая ценность работы заключается в разработке эффективных алгоритмов реализации логических функций в однородной среде, ориентированных на модульный подход к синтезу и освобождающих разработчика от операций перевода полученного решения в настроечную информацию регистров команд ячеек однородной среды. Отдельные алгоритмы могут иметь самостоятельное применение. Так метод выбора совокупности настраиваемых логических модулей может быть использован для среды, имеющей параметры аналогичные используемой в данной работе. Метод определения настроечных операций модуля не зависит от используемой элементной базы и может быть использован для любых настраиваемых модулей с аналогичным набором настроечных операций. Алгоритмы размещения модулей в среде и прокладки каналов связи могут использоваться для любых однородных сред, организованных по принципу близкодействия.
Реализация и внедрение. Разработанные алгоритмы реализованы и представляют собой комплект программ на языке программирования ПЛ/І. Результаты работы внедрены в научно-производственном объединении "Астрофизика" и ИППММ АН УССР. Акты о внедрении прилагаются.
Апробация. Основные результаты работы докладывались:
- на всесоюзной школе-семинаре "Распараллеливание обработки информации", г. Львов, 1981 г. ;
- на X юбилейном совещании-семинаре "Автоматизация проектирования структурных элементов и математического обеспечения ЭВМ и вычислительных систем", г. Симферополь, 1982 г. ;
- на научной конференции Московского энергетического института, посвященной 60-летию образования СССР, г. Москва, 1982 г.
Публикации. По материалам диссертации опубликовано четыре печатные работы и тезисы к докладам (из них три написаны в соавторстве).
Структура и объем работы. Работа состоит из введения, пяти глав, заключения и списка литературы.
Во введении к работе определено место универсальных микроэлектронных однородных сред в структуре современной элементной базы ЭВА, обоснована актуальность разработки средств автоматизации логического синтеза в однородных средах, сформулирована цель работы и защищаемые положения, изложена структура работы.
В первой главе рассматриваются вопросы, связанные с классификацией существующих однородных сред, рассмотрены особенности среды, которая используется в данной работе для реализации логических функций. Рассмотрены существующие методы синтеза логических функций с помощью однородной среды. Излагается подход к логическому синтезу, основанный на использовании настраиваемых логических модулей.
Во второй главе обосновывается возможность использования функциональной декомпозиции для представления заданной логической функции суперпозицией порождающих функций настраиваемых логических модулей. Рассматривается способ простой неразделительной декомпозиции, предложенный в работе [Li2l, Излагается алгоритм использования указанного метода декомпозиции для получения требуемой совокупности модулей, представляющих заданную функцию.
В третьей главе излагается способ определения логических структур настраиваемых логических модулей и их реализация на основе ячеек однородной среды. Рассматривается метод определения настроечных операций с помощью анализа представлений логических функций в базисе Радемахера-Уолша, предложенный в данной работе.
В четвертой главе рассмотрены алгоритмы по оптимизации размещения совокупности модулей, представляющих исходную логическую функцию, в поле однородной среды, организация инвариантных преобразований модуля в поле среды. Обосновывается способ оценки расстояний на среде и алгоритм организации каналов связи в среде.
Пятая глава содержит описание программного обеспечения алгоритмов, реализованных на ЭВМ.
В заключении изложены основные результаты, полученные в данной работе.
