О реализации функций алгебры логики схемами из некоторых классов, вложенными в гиперкубы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Седелев, Олег Борисович

• Седелев, Олег Борисович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Седелев, Олег Борисович

Введение

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

§ 1.1. Единичные кубы, некоторые их подмножества и разбиения.

Вложение единичных кубов в fc-значные кубы.

§ 1.2. Гомеоморфные вложения деревьев и звезд в гиперкубы

§ 1.3. Специальная раскраска вершин гиперкуба на основе кодов

Хэмминга и ее свойства.

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

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

§ 2.1. Вложение некоторых логических схем в единичные кубы и верхние оценки функции Шеннона для размерности этих кубов. Нижние мощностные оценки.

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

§ 2.3. Улучшенная верхняя оценка функции Шеннона для BDD

§ 2.4. Верхняя оценка функции Шеннона для СФЭ

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

Постановка задачи и общая характеристика работы

Основной задачей теории синтеза управляющих систем (см., например, [11,23,36]) является изучение вопросов оптимальной структурной реализации дискретных функций и, в частности, функций алгебры логики (ФАЛ) или, иначе, булевских функций в различных классах схем. Важным направлением теории синтеза является асимптотический синтез, связанный с изучением поведения так называемой функции Шеннона, которая равна сложности оптимальной реализации с помощью схем из рассматриваемого класса самой сложной ФАЛ от заданного числа переменных, являющегося аргументом этой функции и стремящегося к бесконечности.

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

Основными классами схем, в которых обычно реализуются ФАЛ, являются контактные схемы и схемы из функциональных элементов (СФЭ) [11], а в последнее время — двоичные решающие диаграммы (BDD) [33]. В качестве структур, в которых происходит геометрическая реализация схем, выступают, как правило, 2-х и 3-х мерные прямоугольные решетки [9], и, в частности, клеточные схемы [1,22], а в последнее время - единичный булев куб или, иначе, гиперкуб. С геометрической точки зрения единичный куб представляет собой прямоугольную решетку, значность которой равна 2, а размерность может расти. Обобщением единичного куба являются Акзначные кубы (к = 3,4,.).

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

Имеется большое число работ посвященных вложениям различных графов в гиперкубы (см., например, [2,12,31]). Так, исследовано вложение одномерных (линейка, кольцо) [21] и двумерных (решетка, тор) [27] структур параллельных программ в регулярные структуры и в частности, в гиперкуб. Показано, что в гиперкуб размерности к могут быть эффективно вложены многие типы графов со степенями вершин, равными константе и количеством ребер порядка 0(2к) [32]. Одной из самых активно изучаемых задач в области вложения графов является задача вложения различи ных видов деревьев в единичные кубы. Так, было показано, что полное двоичное n-ярусное дерево можно гомеоморфно вложить в единичный куб размерности (п + 1) [26].

Рассматриваются и вложения гиперкубов в различные графы. В работах [25,29,30], например, получены оценки некоторых параметров прямоугольных решеток, допускающих вложение в них гиперкубов, и рассмотрена проблема вложения n-мерного куба в прямоугольные решетки с 2П вершинами.

Геометрическая реализация заданного графа (схемы) <7, то есть его вложение в ту или иную структуру (граф) S, происходит, как правило, в два этапа (см., например, [9]). На первом этапе — этапе "размещения — вершинам графа G сопоставляются "моделирующие" их вершины или группы вершин графа S. На втором этапе — этапе "проведения соединений - ребрам графа G сопоставляются моделирующие их цепи или другие специальные подграфы графа S. Заметим, что в ряде моделей геометрической реализации и, в частности, в модели клеточных схем эти этапы могут не разделяться. В то же время при решении задачи топологического синтеза СБИС, которая сводится к вложению графа схемы в плоские прямоугольные решетки, эти этапы — этап размещения и этап трассировки, — как правило, отделяются друг от друга.

Задачу проведения соединений в рассматриваемой структуре часто сводят к задаче построения в ней различных систем связывающих деревьев (см., например, [35]). В данной работе рассматривается один из возможных вариантов этой задачи — задача построения системы т. н. одноцветных свяt зывающих деревьев, состоящая в следующем. Для данного графа, часть вершин которого раскрашена в различные цвета, необходимо построить такую содержащую все раскрашенные вершины графа систему из непересекающихся подграфов-деревьев, что множество листьев каждого из них содержит все вершины" раскрашенные в один цвет. Эта "задача решается в диссертации для единичного куба, в котором вершины его подкуба размерности п раскрашены в п цветов.

Исследование вопросов сложности реализации ФАЛ схемами, вложенными в гиперкубы, а также вопросов вложения в них различных графов интересно не только с теоретической точки зрения. Архитектура единичного куба хорошо подходит для моделирования различных параллельных алгоритмов, а вложения различных графов в гиперкубы могут быть полезны в области синтеза схем, химии и нанотехнологиях [38]. Так, например, в [3] исследованы вложения некоторых реализованных на плоскости планарных графов, применяемых в химии, в многомерные кубы или кубические решетки с сохранением или же удвоением всех расстояний.

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

Целью данной работы является исследование вопросов синтеза схем из некоторых классов, вложенных в гиперкубы. В ней рассматривается задача вложения некоторых графов в гиперкубы и методы построения в гиперкубах систем одноцветных связывающих деревьев, а также задача реализации ФАЛ с помощью BDD и СФЭ, вложенных в единичный куб, которая является частным случаем задачи о геометрической (структурной) реализации дискретных функций. В качестве меры сложности такой реализации ФАЛ выбрана минимальная размерность единичного куба, допускающего гомеоморфное вложение некоторой BDD или СФЭ, реализующей эту ФАЛ. В работе вводятся функции Шеннона, которые равны сложности самой "сложной" ФАЛ от п переменных при их реализации указанным образом в классе BDD и классе СФЭ над заданным базисом. Доказано, что эти функции с точностью до аддитивной константы равны п — [loglognj.1

Аналогичные результаты получены и для /г-значных кубов. гВ работе через [aJ (через [а]) обозначается ближайшее снизу (соответственно сверху) к числу о целое число, а все логарифмы берутся по основанию 2.

Основные определения и формулировка полученных результатов

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

Напомним основные понятия2, связанные с реализацией ФАЛ с помощью BDD или СФЭ и вложениями BDD или СФЭ в единичные кубы.

Пусть В — {0,1} и Вп — 71-ая декартова степень множества В, — единичный n-мерный куб {гиперкуб), являющийся областью определения ФАЛ f:Bn —>В от булевских переменных (БП) х = (rri,., жп). Обобщением единичного n-мерного куба является /г-значный n-мерный куб Е^ — где Ek = {0,к — 1}.

Известно, что в ориентированном ациклическом графе [24] всегда есть хотя бы один исток, то есть вершина без входящих в нее ребер и хотя бы один сток, то есть вершина без исходящих из нее ребер, а путь не имеет продолжения тогда и только тогда, когда он заканчивается в стоке.

Двоичная решающая диаграмма от БП х = (х\,. ,хп) - это ориентированная ациклическая сеть (схема) £ = Е(ж) с одним истоком, являющимся ее входом, в которой каждый сток является выходом £ и ему приписывается либо 0, либо 1, а каждой вершине, отличной от стока, при

2Те понятия, которые не определены в данной работе, могут быть найдены в [8,11,24]. писывается БП Xi (г £ [1>гс]), причем предполагается, что из такой вершины выходят два ребра, одно из которых помечено символом 0, а другое символом 1 3. Сложность L(Е) BDD Е равна числу вершин Е, отличных от ее выходов. Те BDD, которые имеют единственный сток с пометкой 1 и единственный сток с пометкой 0, будем называть приведенными по выходам BDD.

Напомним, что любой набор a=(ai,., ап) из Вп задает в BDD Е(х) путь Се(ск), который начинается в истоке Е и, проходя через вершину с пометкой Xi, следует дальше по дуге с пометкой aj до тех пор, пока не достигнет одного из стоков Е. Считается что BDD Е(х) реализует ФАЛ f{x), которая принимает значение <т, о £В, на наборе а, а £ Вп, тогда и только тогда, когда путь Се (а) заканчивается в стоке с пометкой и. Под сложностью L(f) ФАЛ / при реализации ее в классе BDD будем понимать минимальную сложность тех BDD, которые реализуют ФАЛ /.

Заметим, что BDD, по существу, представляют собой специальный частный случай контактных схем ( [8,11]), как с точки зрения их структуры, так и с точки зрения их функционирования. Две BDD, реализующие равные ФАЛ, будем называть эквивалентными. Легко видеть, что любая BDD эквивалентна приведенной по выходам BDD той же сложности.

Двоичные решающие диаграммы были введены в рассмотрение в 1959 г. Lee C.Y. [33]. Им же были получены следующие оценки для функции Шеннона L(n), которая равна сложности самой "сложной" ФАЛ от п БП при их реализации в классе BDD:

2 п 2п < L(n) <4--1.

2 п~ к J ~ п

Позднее Кузьмин В.А. установил [4], что:

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

L(n) = -( 1±5(1)), а Ложкин С.A. [6,7] получил для функции Шеннона L(ri) асимптотические оценки высокой степени точности: т( \ 2"(л л. -vlogn^

Традиционной моделью, в рамках которой чаще всего происходит реализация ФАЛ, являются СФЭ над некоторым конечным полным базисом Б. Под сложностью 1>б(/) ФАЛ / при реализации ее в классе СФЭ в базисе Б будем понимать минимальную сложность СФЭ в базисе Б, которые реализуют ФАЛ /. Известно [8,11], что для функции Шеннона Ьв(п), которая равна сложности самой "сложной" ФАЛ от п БП при их реализации в классе СФЭ в базисе Б, имеет место асимптотическое равенство

2 п

Ьв(п) ~ рв—, п где рв — константа, зависящая от базиса. В работах [6, 7] для функции Шеннона Ьв(п) были получены асимптотические оценки высокой степени точности. Аналогичные оценки были установлены и для функции Шеннона, характеризующей глубину СФЭ (см., например, [5,8])

Рассмотрим теперь концепцию геометрической реализации как вложения графов на основе работы [9].

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

G в вершины и простые цепи графа G: которые называются основными вершинами и транзитными цепями данного отображения (подразбиения) соответственно.

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

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

1) начальная вершина каждого указанного пучка переходит в корень, а конечные вершины его дуг - в листья соответствующего транзитного поддерева;

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

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

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

Заметим, что гомеоморфные вложения являются частным случаем квазигомеоморфных и что любую СФЭ всегда можно вложить квазиго-меоморфным образом в единичный куб достаточно большой размерности.

Пусть задан граф G, часть вершин которого раскрашена в цвета {1, .,п}. Будем говорить, что в графе G существует система одноцветных связывающих деревьев, если в нем найдутся п непересекающихся деревьев Di,., Dn таких, что все вершины цвета г, i £ {1,.,п}, являются листьями Di. Частным случаем этой задачи является задача построения системы одноцветных связывающих деревьев в гиперкубе, подкуб которого раскрашен произвольным образом в различные цвета (см. § 1.4).

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

Обычным образом значение рассматриваемого функционала сложности определяется для произвольной ФАЛ /, а затем вводится функция Шеннона R(n) (соответственно Rb(ti)), которая равна минимальной размерности единичного куба, допускающего для любой ФАЛ f(x 1,., хп) го-меоморфное вложение реализующей её BDD (соответственно квазигомео-морфное вложение реализующей ее СФЭ в базисе Б). Аналогично определяется функция Шеннона R(k,n) (соответственно Rb(k,n)) - которая равна минимальной размерности /г-значного куба, допускающего для любой ФАЛ f(xi,., хп) гомеоморфное (соответственно квазигомеоморфное) вложение реализующей её BDD (соответственно СФЭ в базисе Б).

Основными результатами работы являются:

1) разработка техники вложения некоторых графов в гиперкубы, а также методов построения в единичных кубах систем одноцветных связывающих деревьев и, в частности, доказательство того, что если в подкубе размерности п единичного куба Вп+Ъ каждая вершина раскрашена в один из п цветов, то в этом кубе указанная система существует;

2) разработка оптимальных методов реализации произвольных ФАЛ вложенными в гиперкубы СФЭ и BDD и, в частности, получение оценок, устанавливающих поведение для введенных выше функций Шеннона R(n), Re(tl) с точностью до слагаемого 0( 1).

Полученные при этом оценки имеют вид: п — log log п - log 3 — о(1)1 < R{n) <п — [log log nj + 1 (1) и n - [log log nj - сБ < Яв(п) <n - [log log nj + 15, (2) причем верхняя оценка (2) справедлива при п > Cg, где сб и с'в — некоторые константы, зависящие от базиса.

Так, для мультиплексорного базиса Бм = {/i(x, уа, yi), 0,1}, где fi(x, г/О) У\) = %Уо и стандартного базиса Бд = { & , V, ->} справедливы оценки: п - log log п - log 3 - о(I)] < ЛБДп) <п - [log log тт.J + 8 (3) п - log log 71 - log3 - o( 1)1 < RB0(n) <n - [log log 72 J + 8. (4)

Кроме того, для функций Шеннона, связанных с вложением BDD и СФЭ в базисе Б в &-значные кубы, получены следующие оценки: n-loglogw- log3-o(l)-. < га - LloglogwJ + 1 log/с [log &J и, в случае п> с'Б, п - log log n-cBl .D/, ч ™ ~ [log log nj + 15 г-i^k-1 ^ n) *-[Wfcj-• (6)

При этом для мультиплексорного базиса Бм и стандартного базиса Бо оценки (5) и (6) имеют вид: п - log log n- log 3-о(1)-, n- [log log nj +8 Г-l^k-1 - НВ^П) ~-[b^]- (?) и rn — log log n — log3 — o(l)1 . , n- [log log nj +8 r-ъ£к-1 - КбЛК n) ~-[iZ^ki-• (8)

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

Основные результаты, полученные в диссертации, опубликованы в работах [10,14-20].

Список литературы диссертационного исследования кандидат физико-математических наук Седелев, Олег Борисович, 2008 год

1. Альбрехт А. О. О схемах из клеточных элементов // Проблемы кибернетики. - 1975. — Вып. 33. - С. 209-214.

2. Деза М., Штогрин М. Изометрические вложения полуправильных многогранников, разбиений и им дуальных в гиперкубы и кубические решетки // УМН. 1996. - Т. 51, № 6. - С. 199-200.

3. Деза М., Штогрин М. Вложение химических графов в гиперкубы. // Матем. заметки. — 2000. — Т. 68, № 3. — С. 339-352.

4. Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Сб. тр. ин-та математики СО АН СССР. 1976. - Вып. 29.- С. 11-39.

5. Ложкин С. А. О глубине функций алгебры логики в некоторых базисах // Ann. Univ. Sci. Budapest. Sec. Comput.— 1983. — V. IV.— Pp. 113-125.

6. Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. — 1996. — Вып. 6. — С. 189-214.

7. Ложкин С. А. Лекции по основам кибернетики. — ВМиК МГУ, 2004.

8. Ложкин С. А., Ли-Да-Мин. О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решетки // Вестн. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 1995. — № 4. С. 49-55.

9. Ложкин С. А., Седелев О. Б. О реализации функций алгебры логики bdd, вложенными в единичный куб // Вестн. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 2006. — № 4. — С. 29-35.

10. Лупанов О. Б. Асимптотические оценки сложности управляющих систем,- М.: Изд-во МГУ, 1984.

11. Никонов В. Г., Шевелев Д. С. Булевы графы и функции // Дискрет.матем. — 1991. — Т. 3, № 4. — С. 51-61.

12. Оре О. Теория графов. М.: Наука, 1982.

13. Седелев О. Б. Верхняя и нижняя оценки сложности реализации функций алгебры логики bdd, вложенными в n-мерный куб // Тезисы XIV Международной школы-семинара "Синтез и сложность управляющих систем". — Нижний Новгород, 2003. — С. 70-73.

14. Седелев О. Б. Сложность реализации функций алгебры логики схемами, вложенными в гиперкуб. // Сборник тезисов лучших дипломных работ 2004 года. — М.: Издательский отдел факультета ВМиК МГУ, 2004. С. 63-64.

15. Седелев О. Б. Реализация функций алгебры логики схемами из функциональных элементов, вложенными в единичный куб // Вести. Моск. ун-та, сер. 15. Вычисл. матем. и киберн. — 2008. — № 1. — С. 44-50.

16. Тарков М. С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. 2003. - Т. 39, № 3. - С. 84-96.

17. Шкаликова Н. А. О реализации булевых функций схемами из клеточных элементов j j Математические вопросы кибернетики, — 1989. — Вып. 2. С. 177-197.

18. Яблонский С. Основные понятия кибернетики // Проблемы кибернетики, вып. 2.— 1959.— С. 7-38.

19. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.

20. Bezrukov S. L. Embedding complete trees into the hypercube // Discrete Appl. Math. 2001. - Vol. 110, no. 2-3. - Pp. 101-119.

21. Bhatt S. N., Ipsen I. C. F. How to embed trees in hypercubes: Research Report 443: inst-yale, 1985.

22. Chan M. Y. Embedding of grids into optimal hypercubes // SI AM J. Comput. 1991. - Vol. 20, no. 5. - Pp. 834-864.

23. Chen W.-K., Stallmann M. F. M. On embedding binary trees into hyper-cubes /7 J. Parallel Distrib. Comput. 1995. - Vol. 24, no. 2. - Pp. 132138.

24. The congestion of n-cube layout on a rectangular grid / Bezrukov, Chavez, Harper et al. // DMATH: Discrete Mathematics. 2000.- Vol. 213. — Pp. 13 - 19.

25. Embedding of hypercubes into grids / S. L. Bezrukov, J. D. Chavez, L. H. Harper et al. // Lecture Notes in Computer Science. — 1998. — Vol. 1450.

26. Fu W. S., Huang H. C.} Sengupta A. On ring embedding in hypercubes with faulty nodes and links // Information Processing Letters. — 1998. — Vol. 68. Pp. 207-214.

27. Gupta А. К., Hambrusch S. E. Multiple network embeddings into hyper-cubes // Journal of Parallel and Distributed Computing. — 1993. — Vol. 19, no. 2. Pp. 73-82.

28. Lee C. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal— 1959.— July. — Vol. 38.— Pp. 985-999.

29. Ostergard P. R. J. On a hypercube coloring problem // J. Comb. Theory Ser. A. 2004. - Vol. 108, no. 2. - Pp. 199-204.

30. Parallel construction of optimal independent spanning trees on hyper-cubes / J.-S. Yang, S.-M. Tang, J.-M. Chang, Y.-L. Wang // Parallel Comput. 2007. - Vol. 33, no. 1. - Pp. 73-79.

31. Yanushkevich S., Shmerko V., Lyshevski S. Logic Design of NanoICs. — CRC Press, 2004.