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

Требования, предъявляемые к устройствам вычислительной техники на современном этапе (малые габариты, высокая надежность, высокая производительность, малое потребление энергии), могут быть удовлетворены только при постоянном росте степени интеграции элементной базы устройств ЭВА. Это приводит к тому, что возрастает объем использования в устройствах вычислительной техники заказных и полузаказных БИС. В [72]приводится прогноз, согласно которому доля заказных и полузаказных схем в объеме продаж к концу текущего десятилетия увеличится примерно с 20 до 50%, Уровень интегральной технологии в настоящее время позволяет производить интегральные схемы, объединяющие на одном кристалле десятки и сотни тысяч транзисторов. В то же время затраты на разработку таких БИС еще достаточно велики, и их производство становится рентабельным лишь при относительно крупных объемах производства. Так производство заказных БИС в настоящее время становится рентабельным при объеме их выпуска свыше примерно 100 ООО изделий. Использование матричных БИС несколько улучшает ситуацию: их разработка становится рентабельной при размере партии порядка 30 ООО штук. Для многих видов аппаратуры, которая не выпускается массовыми тиражами и предназначена для специального применения, но к которой предъявляются высокие требования по скорости, единственным на сегодня способом усовершенствования технологии производства представляется использование специфических БИС — универсальных микроэлектронных однородных сред, настраиваемых на выполнение конкретных функций в устройствах ЭВА самим заказчиком или даже перестраиваемых в процессе эксплуатации. Они обяадают следующими свойствами: регулярность структуры, что наилучшим образом отвечает требованиям интегральной технологииявляются программируемыми, что позволяет при решении каждой конкретной задачи приспосабливать технологически одинаковую структуру устройства к структуре решаемой задачи. Областями применения такого рода схем являются ([{?1):

— цифровая обработка изображений ;

— цифровая фильтрация ;

— управление роботами ;

— обработка сейсмической и метеорологической информации.

Требованиями к такого рода устройствами частности, являются^{высокая} надежность и способность обрабатывать информацию в реальном масштабе времени. Требование обработки информации в реальном масштабе времени при существующем быстродействии логических элементов может быть удовлетворено лишь при организации конвейерной и параллельной обработки информации с истт:.: пользованием подхода, называемого коллективом вычислителей [10]). В основе этого подхода лежит применение однородных вычислительных систем, структур и сред.

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

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

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

Начиная с 60-х годов в нашей стране и за рубежом публикуются работы, в которых обосновываются подходы к выбору конкретных структур однородной среды, функциональных возможностей ячейки среды, способов реализации комбинационных автоматов и автоматов с памятью в таких средах ([ {1, ?37, [63 ГШ).

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

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

Исход®из поставленной цели в данной работе решены следующие задачи:

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

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

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

— осуществлена программная реализация разработанных методов синтеза на языке программирования ПЛ/1.

Решив поставленные задачи, автор защищает:

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

2. Способ выбора совокупности настраиваемых логических модулей.

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

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

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

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

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

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

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

Реализация и внедрение. Разработанные алгоритмы реализованы и представляют собой комплект программ на языке программирования ПЛ/1. Результаты работы внедрены в научно-производственном объединении «Астрофизика» и ИППММ АН УССР. Акты о внедрении прилагаются.

Апробация. Основные результаты работы докладывались:

— на всесоюзной школе-семинаре «Распараллеливание обработки информации», г. Львов, 1981 г. ;

— на X юбилейном совещании-семинаре «Автоматизация проектирования структурных элементов и математического обеспечения ЭВМ и вычислительных систем», г. Симферополь, 1982 г. ;

— на научной конференции Московского энергетического института, посвященной 60-летию образования СССР, г. Москва, 1982 г.

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

Структура и объем работы. Работа состоит из введения, пяти глав, заключения и списка литературы.

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

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

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

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

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

Пятая глава содержит описание программного обеспечения алгоритмов, реализованных на ЭВМ.

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

I. ОСОБЕННОСТИ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ НА ОДНОРОДНОЙ СРЕДЕ.

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

Результаты работы были представлены в виде докладов на всесоюзной школе-семинаре «Распараллеливание обработки информации», г. Львов, 1981 г.- на I юбилейном совещании-семинаре «Автоматизация проектирования структурных элементов и математического обеспечения ЭВМ и вычислительных систем», г. Симферополь, 1982 г.- на научной конференции Московского энергетического института, посвященной 60-летию образования СССР, г. Москва, 1982 г.- а так же в печатных работах ([58],[5д].

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

На основании разработанных методов реализации логической функции в однородной среде был подготовлен комплект программ на алгоритмическом языке ПЛ/1. Разработанные методы автоматизации проектирования логических функций с помощью однородной среды внедрены в НПО «Астрофизика» и ИППММ АН УССР.