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

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

Основной задачей теории синтеза управляющих систем (см., например, [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 — сБ < Яв (п) 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).

Кроме того, для функций Шеннона, связанных с вложением BDD и СФЭ в базисе Б в &—значные кубы, получены следующие оценки: n-loglogwlog3-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 nlog 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].

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. 132 138.

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.