Двухслойные контактные схемы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский Государственный Университет имени М.В.Ломоносова

Факультет вычислительной математики и кибернетики

^ р -л На правах рукописи

' : '"'' УДК 519.7

Задорожнюк Олег Анатольевич ДВУХСЛОЙНЫЕ КОНТАКТНЫЕ СХЕМЫ

специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

г.Москва 1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского Государственного Университета им. М.В.Ломоносова.

Научный руководитель:

кандидат физико-математических наук, доцент А.И.Рыбко

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

доктор физико-математических наук, профессор А.Б.Угольников; кандидат физико-математических наук, научный сотрудник Н.А.Карпова

Оппонирующая организация: вычислительный центр РАН

Защита диссертации состоится « ^ » ^^/иЬ/М 1998г. в И час. мин, на заседании диссертационного совета Д.053.05.38 в Московском Государственном Университете им. М.В.Ломоносова по адресу: 119899, Москва, Воробьевы горы, МГУ, 2-й учебный корпус^ факультет вычислительной математики и кибернетики, аудитория ¿>§£~.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан «_

4

1997г.

>

Ученый секретарь диссертационного совета

кандидат физико-мэтематических наук, и, ,, „ _ .

профессор ^ Н.П.Трифонов

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

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

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

В 1967 году А.Н.Колмогоровым и Я.М.Барздинем было показано, что если учесть объемные характеристики элементов и соединений схемы, то вполне может оказаться, что активные элементы схемы будут занимать ничтожно малый объем по сравнению с объемом всей схемы. Поскольку при производстве реальных схем на такие важные характеристики как быстродействие, надежность и даже стоимость влияет не только количество активных элементов, но и размеры схемы (причем весьма существенно), то вопрос о линейных размерах схемы представляется довольно важным.

Первые существенные результаты в построении и исследовании математических моделей, учитывающих размеры схемы были получены тогда же, в 1967 году, когда в работах А.Д.Коршунова и С.С.Кравцова были описаны клеточные и объемные схемы из функциональных элементов, и было показано, что функция Шеннона (необходимая и

достаточная сложность схемы, реализующей «самую плохую» булеву функцию, зависящую от п переменных) имеет порядок 2" (напомним, для обычных схем из функциональных элементов функция Шеннона

асимптотически равна 2"/п). В дальнейшем клеточные схемы из функциональных элементов и близкие к ним модели исследовались в работах А.Альбрехта, Ю.Громковича и Б.Шустера, Н.А.Шкаликовой, Х.Пападимитриу и М.Сипсера, а также других авторов.

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

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

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

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

Цель работы.

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

2) Оценка функции Шеннона.

3) Исследование сложности реализации схемами данной модели конкретных булевых функций.

4) Количественная оценка стоимости учета объемных характеристик элементов схемы и необходимости подачи на контакты управляющего воздействия.

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

Научная погиппа. Все основные результаты работы являются новыми:

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

2) Получен порядок функции Шеннона для двухслойных контактных схем.

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

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

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

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

Апробация работы. Результаты работы докладывались на IV Межгосударственном семинаре по дискретной математике (МГУ, февраль 1993г.), X международной конференции по проблемам теоретической кибернетики (Саратов, июнь 1993г.), VI школе-семинаре «Синтез и сложность управляющих систем» (Минск, ноябрь 1993г.), семинаре «Математические вопросы кибернетики» под руководством член-корр. РАН С.В.Яблонского (МГУ, ноябрь 1996г.), семинаре «Математическая теория синтеза управляющих систем» под руководством член-корр. РАН О.Б.Лупанова (МГУ, май 1997г.).

Публикации. Основные результаты диссертации опубликованы в работах автора [1—6].

Структура и объем диссертации. Диссертация состоит из введения и семи глав, некоторые из которых разбиты на параграфы. Полный объем диссертации составляет 77 страниц машинописного текста. В работе содержится 26 рисунков, список литературы содержит 31 наименование.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Глава 1 посвящена строгому описанию модели двухслойных контактных схем.

Пусть (К,, £,) - плоская целочисленная решетка, ^ - множество всех точек евклидовой плоскости с целочисленными координатами, а £, - множество всех отрезков единичной длины с концами в И,. Элементы из К, и £, будем называть, соответственно, вершинами и ребрами. Будем далее рассматривать прямоугольные сети, являющиеся конечными подграфами (К,,£|), назовем их л-сетями. Пусть задан конечный алфавитХ= {х,,...,*,,,*,,...,хн,0,1}.

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

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

Рассмотрим цепи, соединяющие пары полюсов схемы нижнего слоя. Каждой цепи 2 поставим в соответствие конъюнкцию К2 = а1&...&ар, где аи...,ар - символы, приписанные ребрам цепи.

Каждой паре полюсов, например, А и В, схемы нижнего слоя ставится в соответствие булева функция //(Л(х1,...,х)|) = У Кг, где дизъюнкция берется по всем цепям, соединяющим полюса А и В. Если полюса А к В совпадают, будем полагать //ц)(х\.....х») 3 ' •

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

Длиной (высотой) однослойной схемы 51 будем считать число вершин в одном ряду (столбце) и обозначать через /,(5") (//,(5')). Сложностью однослойной схемы 51 будем считать число вершин г-сети и обозначать через £,(£'). Очевидно, ¿,(5') = /,(£')• А, (51).

Обозначим через £|(./) сложность минимальной однослойной схемы, реализующей функцию а через £,(«) - функцию Шеннона для

однослойных схем.

Однослойные схемы практически ничем не отличаются от модели схем, предложенной Ю.Г.Таразевичем, для которых функция Шеннона имеет порядок 2" ¡\о& п.

Пусть дана некоторая окружность и некоторое множество К={у,,...,уА} принадлежащих ей точек, упорядоченное в порядке обхода окружности по часовой стрелке, начиная с любой точки.

Определение 1.3. Я-компонентой будем называть подмножество Уя с V, > 1, точек окружности и все соединяющие их попарно хорды.

Определение 1.4. Разводкой будем называть разбиение множества V на Л-компоненты такое, что хорды, принадлежащие различным Я-компонентам, не пересекаются.

Пусть й - планарный граф, уложенный на плоскости, а у -вершина степени т графа (7. Пометим инцидентные V ребра символами е|,...,ет в порядке обхода вершины по часовой стрелке, начиная с любого ребра. Сопоставим вершине V некоторую /я-вершинную разводку Я, причем ребру, помеченному символом е, (/ = 1 ,...,т), сопоставляется вершина V, разводки Я. Будем говорить, что разводка /? покрывает вершину V.

Пусть К(С7) - множество вершин графа С?, и каждая вершина V, е покрыта некоторой разводкой Л,.

Определение 1.5. Множество разводок,

покрывающих все вершины графа С, будем называть трассировкой графа С7.

Пусть Т - трассировка графа С, V - вершина графа О, покрытая разводкой Л, е, и е2 -два ребра, инцидентных V.

Определение 1.6. Т-цепью будем называть упорядоченное

множество ребер 2 = {е1,е2,...,еЛ} = {(у0.г|),(у1,у2).....К.,,^,)), то есть

такое, что для всех / (/ = 1.....5-1) конец ребра е, является началом

ребра ем, и кроме того, для всех / (/'= 1,...,л-1) в разводке /?,, покрывающей вершину V,, соответствующие ребрам е, и е/+) вершины принадлежат одной ^-компоненте.

Определение 1.7. Множество ребер {е,, е2.....е%} графа О будем

называть Т-компонентой, если любые два ребра из этого множества принадлежат какой-либо одной Г-цепи графа О.

Определение 1.8. Множество ребер [е^,е2.....ел) графа С будем

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

В дальнейшем для краткости максимальные Г-компоненты будем называть просто Г-компонентами.

Пусть {л:,.....х,,} - некоторый набор переменных. Будем

рассматривать только такие трассировки, которые разбивают все множество ребер графа С ровно на п Г-компонент. Перенумеруем Г-компоненты числами от 1 до п и будем говорить, что /-я Г-компонента соответствует переменной х,.

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

Рассмотрим плоскую решетку (К2,£2), полученную из (И|,£|) следующим сдвигом: каждая вершина V, V е К,, имеющая координаты (х,у), отображается в вершину V', V' еУ2< с координатами (* +1/2, у+ 1/2).

Будем говорить, что ребро е решетки (И,,£|) покрывается ребром е' решетки £2), если е' пересекаете?.

Определение 1.9.

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

б) Открытой трассировкой будем называть трассировку, такую что каждая из Г-компонент содержит ребро, принадлежащее периметру /•-сети.

в) Сквозной трассировкой будем называть трассировку, для которой выполняется следующее условие: существует перестановка / = (/',,...,/„) такая, что на периметре г-сети можно выбрать 2п ребер и

пометить их символами Ь/.....в порядке обхода периметра

по часовой стрелке, начиная с некоторого ребра так, что для любого у, (у — I.....и), ребра и Ь] принадлежат Г-компоненте с номерому.

Определение 1.10. Схемой верхнего слоя будем называть /--сеть, принадлежащую решетке (И2,£2), с выбранной для нее трассировкой.

Длиной (высотой) схемы верхнего слоя 52 будем считать длину (высоту) прямоугольника, в котором она построена и обозначать через 12(Б2) ЩБ2)).

Определение 1.11. Двухслойной схемой будем называть всякую пару (5',52), где 51 и Б2 - схемы соответственно нижнего и верхнего слоя, для которой выполнены следующие условия:

1) /.(Я'Ь/^1); МЯ^МЯ1).

2) Каждое ребро схемы 51 покрывается каким-либо ребром схемы 52, причем для каждого / (/ = 1,...,«) все контакты х, и Зс,

покрываются ребрами 1-й Г-компоненты схемы Б2.

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

Пусть задана двухслойная схема 5 = (5',52). Длиной (высотой) схемы 5 будем считать длину (высоту) схемы верхнего слоя и обозначать тем же символом. Сложность двухслойной схемы 5 обозначим через ^(5) и определим следующим образом: ¿2(5) = /2(5) /12(5). Заметим, что из определения 10 следует, что на единицу площади двухслойной схемы приходится ровно одна вершина схемы нижнего слоя.

Обозначим через (соответсвенно, и ££(/))

сложность минимальной двухслойной схемы, реализующей функцию/ трассировка верхнего слоя которой является простой (соответственно, открытой и сквозной), а через С'2(«) (соответсвенно, И'2(п) и Л'2 (п))

обозначим соответствующую функцию Шеннона.

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

соотношения ДЛЯ ¿2 ВЫПОЛНЯЮТСЯ ДЛЯ ¿2 , ¿2 И ¿2 .

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

***(/). (О

Ц{п)<щп)<ф). (2)

Глава 2 посвящена получению оценок функции Шеннона для двухслойных схем.

Доказана следующая теорема:

Теорема 2.1, Справедливы оценки

-2— < ип) < 2".

1о8224 ~ ^ ' ~

Методы доказательства довольно традиционные.

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

В силу соотношения (2) нижняя оценка доказывается для схем с простой трассировкой, а верхняя - для схем со сквозной трассировкой.

В Главе 3 производится адаптация метода Нечипорука для получения нижних оценок сложности к модели двухслойных схем.

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

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

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

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

сложности вида ¿-

тогда как в классе обычных

контактных схем этим же методом можно получить лишь оценку вида

4/)*-.. 2

Ч^ п)

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

Пусть /(д-,,...,*,,) - булева функция, У = (/,,...,/„) - некоторая перестановка, а к - некоторое число (1 < А ^ я-1). Пусть А* -разбиение множества переменных {*,,...,*„} на два подмножества:

Лп = {*;.....хи Л*г = {х,к .....}. Обозначим через Г*, количество

попарно различных подфункций функции /, получаемых при всевозможных подстановках констант на места всех переменных из Л*, (/=1,2). Основным результатом главы 4 является доказательство следующей теоремы:

Теорема 4.1. Справедлива оценка

и-1

где минимум берется по всем возможным перестановкам /.

Заметим сразу, что теорема 1 позволяет получать нижние оценки по порядку не выше п2. Действительно, для любой функции / величина тах(£*|,£*2) не превосходит тах(2*,2"~*), и нетрудно убедиться в

том, что |>в(тах(2*,2''"*))<С>(л2).

Для эффективного применения теоремы 4.1 необходимо уметь довольно точно оценивать число различных подфункций исследуемой функции. Глава содержит три примера применения теоремы 4.1. В примере 4.1 для симметрической функции доказывается оценка вида 0{п\о%п). В примере 4.2 для функции выборки из памяти

получена оценка вида Наиболее близкая к

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

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

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

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

ориентированными двухслойными контактными схемами. Доказана следующая теорема:

Теорема 5.1. Для любой булевой функции / имеет место соотношение

LK{f)iO(L2{f)),

где Z2(/) и LK (f) сложности минимальных, соответственно,

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

Теорема 5.1 позволяет перенести на ориентированные двухслойные схемы все известные методы и результаты по нижним оценкам для клеточных схем из функциональных элементов, в частности, метод рассеченных схем и нижние оценки вида 0{п2).

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

Как уже отмечалось ранее, функция Шеннона для однослойных схем имеет порядок 2"/logп, а в главе 2 было показано, что функция

Шеннона для двухслойных схем имеет порядок 2". Таким образом, почти все булевы функции реализуются двухслойными схемами по порядку в log я сложнее, чем однослойными.

Существуют и примеры конкретных функций, реализуемых двухслойными схемами существенно сложнее, чем однослойными. Так, например, функция выборки из памяти (пример 4.2) требует сложности 0(п-/п) при реализации двухслойными схемами со сквозной трассировкой, тогда как в классе однослойных схем ее сложность линейна. Сложность функции двухступенчатой выборки из памяти (пример 4.3) в классе двухслойных схем со сквозной трассировкой не

меньше, чем в то время как ее сложность в классе

однослойных схем, как несложно доказать, не превосходит .

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

Пусть и /^(А7,,) - сложности минимальных однослойной

и двухслойной схем, реализующих многополюсник /•"„. Исследуем

/ / С }

функционал А.,.(л) = шах———, где максимум берется по всем

многополюсникам , функции которых зависят от п переменных. Теорема 6.1. Справедливо соотношение

\,.<п) = О(п).

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

эквивалентную ей двухслойную схему, имеющую сложность не более, чем 12/1-£,(5|).

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

Таким образом, отношение сложностей минимальных эквивалентных двухслойной и однослойной схем может достигать О(п), но не более того.

Глава 7 носит вспомогательный характер и содержит доказательства некоторых лемм, использованных в главах 3 и 4 при получении нижних оценок.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Задорожнюк O.A. Нижняя оценка сложности реализации одной булевской функции двухслойными контактными схемами на плоской целочисленной решетке. Межвузовский сборник научных трудов «Методы и системы технической диагностики». Тезисы докладов X международной конференции по проблемам теоретической кибернетики, г.Саратов, 1993г. Изд-во Саратовского университета, 1993, вып. 18, с.65-66.

2. Задорожнюк O.A. Нижняя оценка сложности реализации одной булевской функции двухслойными контактными схемами на плоской целочисленной решетке. Дискретная математика. 1997, т.9(2), с.40-52.

3. Задорожнюк O.A. О контактных схемах из клеточных элементов. Математические вопросы кибернетики. 1997, т.6, с.257-280.

4. Задорожнюк O.A. О сложности реализации булевых функций двухслойными контактными схемами. Препринт №4 за 1997г. Изд-во «Диалог-МГУ», Москва, 1997.

5. Задорожнюк O.A., Рыбко А.И. Об одной модели плоских контактных схем. Дискретная математика. 1995, т.7(4), с.40-50.

6. Задорожнюк O.A., Рыбко А.И. О сложности двух типов плоских контактных схем. Сибирский журнал исследования операций. Тезисы докладов VI школы-семинара «Синтез и сложность управляющих систем», г.Минск, 22-26 ноября 1993г. Новосибирск, 1994, т. 1(1), с.78.