Реферат - Белой Олег Игоревич. Разработка и исследование итерационных алгоритмов компоновки на базе гиперграфовой модели электрической схемы.
ДонНТУ   Портал магистров

Реферат по теме магистерской работы.

Содержание

Введение

Компоновка – одна из обязательных процедур, которые выполняются при конструкторском проектировании. В процессе компоновки электрическая схема разбивается на модули, модули на ячейки, и т.д. Что в результате приводит к получению представления электрической схемы таким образом, который пригоден к непосредственной реализации на реальных компонентах [20].

Для построения формальной математической модели компоновочных задач удобно использовать теорию графов. При этом электрическую схему интерпретируют ненаправленным мультиграфом, в котором каждому конструктивному элементу (модулю) ставят в соответствие вершину мультиграфа, а электрическим связям схемы – его ребра. Тогда задача компоновки формулируется следующим образом: задан мультиграф. Требуется «разрезать» его на отдельные куски так, чтобы число ребер, соединяющих эти куски, было минимальным. Главными критериями для такого разбиения являются: минимум числа образующихся узлов, минимум числа межузловых соединений или внешних выводов на узлах.

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

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

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

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

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

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

1. Актуальность темы.

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

Развитие микроэлектронных компонентов постоянно идет в направлении увеличения интеграции, производительности и функциональности. Этот процесс характеризуется увеличением плотности активных элементов на кристалле примерно на 75% в год, а это, в свою очередь, вызывает необходимость в увеличении количества их выводов на корпусе на 40% в год. Этим обуславливается, во-первых, постоянно растущий спрос на новые методы компоновки, а во-вторых, увеличение плотности соединений на печатной плате.

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

2. Цели и задачи исследования, планируемые результаты

Во время исследования итерационных алгоритмов планируется выполнить следующие задачи:

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

Во время разработки планируется:

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

3. Обзор тематических источников.

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

3.1. Обзор международных источников

Для итерационных алгоритмов компоновки, исследуемых в магистерской работе, необходимо подавать исходные данные в виде матрицы, которая, в свою очередь, базируется на представлении электрической схемы в виде гиперграфа. Теория построения гиперграфа рассматривается, в частности, в публикации Даубера [1]. Математик формулирует теорему разбиения гиперграфа на подграфы и преставлении его в виде матрицы.

От проблемы построения гиперграфа в общем к проблеме его оптимизации для компьютерной обработки, его представления и отрисовки, позволяют перейти научная публикации Хенриксона и Кольда, Catalyurek'a и Aykanat'a [2,3], книга Хендриксона [4].

Непосредственно вопроса итерационной модели проведения компоновки, исследования различных алгоритмов компоновки касаются в книгах Eduardo R Miranda, Sen Su, Bregman, G.Karypis [5-8], публикациях K.Mohan, A.Feldstein, E.Carrillo, Bergmann, Alex Townsend и Lloyd N. Trefethen [9-12]

Также одной из перспективных современных ветвей исследования алгоритмов компоновки являются так называемые генетические алгоритмы. Эти алгоритмы используют механизм случайного подбора, комбинирования исходных параметров (в случаях с компоновкой проводников на микросхеме — перестановки проводников) и отсеивания непригодных с помощью способов, напоминающих биологическую эволюцию. С данной отраслью знаний возможно ознакомиться в работах Goldberg'a, Muehlenbein H., Schwarz, Rodriguez, Byung Ro Moon, Croix V, S.Raman [13-19].

3.2. Обзор русскоязычных источников.

Аналогичную информацию также можно найти в русскоязычных источниках, с которыми легче работать, т.к. они созданы на родном мне языке. Описание математической модели построения графов, разбиения на подграфы и построения матриц смежности и инцидентности можно найти в книге Курейчика [20]. В своей монографии [21] Лебедев описывает возможности оптимизации начального графа, для представления его в виде, наиболее пригодном для дальнейших автоматизированных вычислений и проектирования, представленных в учебных пособиях Алексеева [22] и Мироненко [23] для ВУЗов.

Непосредственно прямое пересечение с темой моей магистерской работы имеет научный труд моего руководителя Струнилина В.Н. в соавторстве с Саломатиным В.А. [24], где рассматривается алгоритм итерационного распределения элементов электрической схемы.

4. Разработка и исследование итерационных алгоритмов компоновки.

4.1. Постановка проблемы

Компоновка — одна из основных процедур, которые выполняются при конструкторском проектировании РЕА [20]. Это процесс перехода от электрической схемы к конструктивному распределению (разбиению) всех элементов на группы, в соответствии с конструкцией разных уровней, то есть процесс превращения функционального описания аппаратуры в конструктивное.

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

В последовательных алгоритмах сначала выбирается первая вершина графа и последовательным присоединением к ней других вершин из числа нераспределенных (при условии удовлетворения заданным критериям) формируется первый кусок графа. Потом набирается второй кусок графа и так далее к полному разрезанию.

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

В данном алгоритме необходимо найти пару вершин x і ∈ X 1 , x j ∈E\ X 1 , для которых прирост числа внешних связей (цепочек) буде больше чем 0 и максимальное.

maxΔ S ij = S ij − S ji >0  ;

 

S ij =|Γ X 1 ∩ΓE\ X 1 | , S ji =|Γ X 1 \ X i ∪ X j ∩ΓE\ X 1 \ X j ∪ X i | , где:

 

  • X 1  — кусок матрицы Q,
  • E\ X 1  — матрица Q без куска X 1 ,
  • S ij   –  число внешних связей между двумя кусками после перестановки вершин i и j
  • S ji   –  число внешних связей между кусками после перестановки вершин i и j.

 

Δ S ij =|Г X 1 ∩ГE\ X 1 |−|Γ X 1 \ X i ∪ X j ∩ΓE\ X 1 \ X j ∪ X i | . [25]

Таким образом, матрица Q разбивается на 2 подматрицы X 1  и E\ X 1 , для каждой пары вершин X ij рассчитывается Δ S ij . Потом среди всех Δ S ij  ищем самое большое дополнительное число и меняем местами i-тую и j-тую строки матрицы.  Потом снова рассчитываем Δ S ij  для всех возможных пар вершин подматриц. Если самое большое Δ S ij  равно 0, либо отрицательное — тогда заканчиваем компоновку.

Этот алгоритм достаточно легко запрограммировать, но он имеет существенный недостаток — в каждом цикле необходимо заново рассчитывать Δ S ij  для всех пар вершин подматриц, потому что после того, как мы меняем местами строки матрицы, изменяется число внешних и внутренних связей каждого узла схемы.

4.2. Исследование достоинств и недостатков итерационных алгоритмов на примере двух: итерационного алгоритма 4х правил и модифицированного алгоритма.

Итерационный алгоритм 4х правил намного сложнее запрограммировать, чем предыдущий, он требует большую память в процессе работы, но имеет существенный плюс — в каждом цикле необходимо рассчитывать Δ S ij  только для тех пар вершин которые связаны ребрами с переставленными на предыдущем шаге.

В случае модифицированного алгоритма матрица Q сначала разбивается на подматрицы Q 0 , Q 1 ,⋯, Q k , что соответствует разбитию гиперграфа на части G 0 , G 1 ,⋯, G k . В подматрицу Q 0 включаем элемент e 0 , который соответствует разъему.

Отметим, что при перестановке вершин e i , e j  прирост Δ S ij  находится только для частей G n  и G m  , и соответственно, для подматрицы   Q n  и Q m .[25]

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

Тестирование алгоритмов проводилось случайно сгенерированным гиперграфом с количеством ребер и вершин от 10 до 100. При этом гиперграфы «разбивались» на 2 - 10, 15, 20, 30, 40 и 50 частей с ровным количеством вершин в каждой. Результаты исследований зависимости времени вычисления нескольких из алгоритмов от размера матрицы приведены в таблице 1.

Таблица 1 – Зависимость времени вычисления алгоритмов от размера матрицы Q

№

Мощность вершин X

Мощность ребер Е

Число узлов

Время вычисления, сек.

Алгоритм 1

Алгоритм 2

1

20

20

2

0,165

0,055

2

40

40

2

0,934

0,22

3

80

80

2

4,286

0,495

4

100

100

2

10,165

0,989

5

100

100

3

48,297

5,275

6

100

100

4

51,978

5,934

7

100

100

5

91,319

12,365

8

100

100

10

110,275

20,275

9

100

100

20

39,725

8,846

10

100

100

50

16,648

4,066

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

Рисунок 1 — Гистограмма скорости вычислений алгоритмов, которые исследуются

График зависимости времени вычисления графу от количества узлов в схеме при разбитии на 7 подсхем приведен на рис.2.

Рисунок 2 — График зависимости времени рассчета от количества узлов входного графа для двух рассматриваемых алгоритмов

Количество кадров анимации: 7

Время задержки:2сек на каждый кадр, последний — 4 сек. За 2 сек возможно оценить шкалу графика и её изменение. Последний кадр с текстом, поэтому задержка выше

Выводы

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

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

Список источников

  1. Dauber E., in Graph theory, ed. Harary ,Wesley A., 1969. — 172 p.
  2. Hendrickson B., Kolda T.G., "Graph partitioning models for parallel computing", Parallel Computing, 2000. — 16 p.
  3. Catalyurek, U.V.; Aykanat C., "Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication", 1999. — 673 p.
  4. Hendrickson. "A multilevel algorithm for partitioning graphs", 1995. — 14 p.
  5. Miranda E.,"Composing with Computers,Algorithmic composition, Iterative systems", — 34 p.
  6. Sen Su, "Iterative selection algorithm for service composition in distributed environments", 2008. — 1841 p.
  7. Yin E., Osher S., "Iterative algorithms for minimization with applications to compressed sensing", — 26 p.
  8. Karypis G., "Multilevel hypergraph partitioning: applications in VLSI domain", 1999. — 69 p.
  9. Mohan K., "Iterative Reweighted Algorithms for Matrix Rank Minimization", — 34 p.
  10. Feldstein A., "A study of Ostrowski efficiency for composite iteration algorithms", 1969. — 147 p.
  11. Carrillo E., "Iterative algorithms for compressed sensing with partially known support", 2010. — 4 p.
  12. Bergmann S., "Iterative signature algorithm for the analysis of large-scale gene expression data", 2003. — 18 p.
  13. Goldberg, "Genetic Algorithms", 1989. — 412 p.
  14. Muehlenbein H., "Marginal Distributions in Evolutionary Algorithms", 1999. — 6 p.
  15. Rodriguez, "Schemata, Distributions and Graphical Models in Evolutionary Optimization, submitted for publication", 1999. — 34 p.
  16. Schwarz, "Genetic algorithm for partitioning circuits", 1998. — 126 p.
  17. Moon B.B., "Genetic Algorithm and Graph Partitioning", 1996. — 841 p.
  18. Croix V, "Graph partitioning using learning automata", 1996 — 195 p.
  19. Schwarz, "Hypergraph Partitioning Based on the Simple and Advanced Genetic Algorithm BMDA", 1999. — 130 p.
  20. Курейчик В.М., Математическое обеспечение конструкторского и технологического проектирования с применением САПР [Текст] / В. М. Курейчик. – М.: Радио и связь, 1990. – 352 c.
  21. Лебедев Б.К., Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография / Б. К. Лебедев. – Таганрог: изд-во ТРТУ, 2000. – 192 с.
  22. Алексеев О.В., Автоматизация проектирования радиоэлектронных средств: Учеб. пособие для радиотехн. спец. вузов [Текст] / Под ред. О.В. Алексеева. — М., 2000. — 479 с.
  23. Мироненко И.Г., Автоматизированное проектирование узлов и блоков РЭС средствами современных САПР: Учеб. пособие вузов / Под ред. И.Г. Мироненко. — М., 2002. — 391 с.
  24. Саломатин В.А., Итерационный алгоритм распределения конструктивных элементов при задании электрической схемы в виде гиперграфа [Текст] / В.А.Саломатин, В.Н.Струнилин // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика і обчислювальна техніка» (ІКОТ-2008). Випуск 9 (132). — Донецьк: ДоНТУ. — 2008. — 316 с.
  25. Белой О.И., Струнилин В.Н. Модифікація ітераційного алгоритму компонування на базі гіперграфової моделі електричної схеми. Матерiали мiжнародної науково-технiчної конференцiї студентiв, аспiрантiв та молодих вчених. — Донецьк, ДонНТУ — 2012