Please download to get full document.

View again

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

V.V. Kureichik, N.E. Kurnosova, E.E. Polupanova PROGRAM REALIZATION OF CONFIGURATION INTEGRATED ALGORITHM

Category:

Sheet Music

Publish on:

Views: 5 | Pages: 7

Extension: PDF | Download: 0

Share
Related documents
Description
Информатика, вычислительная техника и инженерное образование 20, (3) ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ УДК 68.3 В.В. Курейчик, Н.Е. Курносова, Е.Е. Полупанова ПРОГРАММНАЯ
Transcript
Информатика, вычислительная техника и инженерное образование 20, (3) ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ УДК 68.3 В.В. Курейчик, Н.Е. Курносова, Е.Е. Полупанова ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕГРИРОВАННОГО АЛГОРИТМА КОМПОНОВКИ * Решение оптимизационной задачи компоновки зависит от выбираемой формальной математической модели коммутационной схемы. В работе рассматривается интегрированный эволюционно-генетический алгоритм для задачи компоновки блоков СБИС на основе гиперграфовой модели. Приводится его программная реализация. Интегрированный алгоритм, математическая модель, гиперграф. V.V. Kureichik, N.E. Kurnosova, E.E. Polupanova PROGRAM REALIZATION OF CONFIGURATION INTEGRATED ALGORITHM Solution of configuration optimization problem depends on mathematical model of connections diagram. Integrated algorithm for a problem of configuration VLSI elements based on hyper-graph models are resulted in this work. Also the program realization of this problem are represented. The integrated algorithm, mathematical model, hyper-graph. Введение Задачи конструкторского проектирования принадлежат к классу комбинаторных оптимизационных задач, реализация которых на ЭВМ зависят от выбираемой формальной математической модели коммутационной схемы. Различные математические модели в различной степени описывают одни и те же параметры устройства при решении каждой конкретной задачи конструкторского проектирования. В этой связи на различных этапах конструкторского проектирования используются различные коммутационные модели. Одним из важнейших вопросов этапа конструкторского проектирования ЭВА, РЭА, объектов машиностроения и др. является компоновка коммутационной схемы рассматриваемого устройства в конструктивно законченные части. Данная задача решается посредством разбиения схемы, с последующим группированием компонентов в блоки. В результате разбиения формируется множество блоков и межсоединений между блоками [,2]. * Работа выполнена при поддержке РФФИ (грант ) 3 Информатика, вычислительная техника и инженерное образование 20, (3) В данной работе рассмотрена гиперграфовая математическая модель задачи компоновки, а также приводится программная реализация интегрированного эволюционно-генетического алгоритма, рассмотренного в [3-5]. Построение математической модели для задачи компоновки Математическая модель это совокупность математических объектов (чисел, переменных, векторов, множеств и т.п.) и отношений между ними, которая адекватно отображает некоторые свойства проектируемого технического объекта [2]. Различные математические модели с различной степенью точности описывают одни и те же параметры устройства. В этой связи, к математическим моделям предъявляются следующие требования: адекватность и простота представления исходного объекта; информационная сложность, т.е. возможность перехода от одной математической модели к другой, от объекта к модели и обратно; разумный объём памяти ЭВМ, отводимый для хранения информации о модели; степень разработанности математического аппарата для оперирования с математическими моделями; простота обработки. Любая функциональная или принципиальная электрическая схема СБИС состоит из некоторого набора базовых элементов, определенным образом связанных между собой. Тогда схему можно рассматривать как некоторое множество элементов x, х 2,..., x п, соединенных между собой цепями из множества E. На рис. показана условная коммутационная схема блоков ЭВА. Здесь x - x 5 блоки; е -е 5 цепи (внешние связи); k, k 2 внешние контакты цепей схемы. Рис.. Условная коммутационная схема блоков ЭВА Графотеоретические модели объектов сохраняют всю наглядность и содержательность описываемых объектов и позволяет строить формальные алгоритмы конструирования, которые легко обрабатываются на ЭВМ. В этой связи, рассмотрим задачу компоновки блоков в конструктивно-законченные части на примере гиперграфовой математической модели [6]. Считают, что гиперграф Н = (X, E) задан, если задано множество вершин X = X X 2 и множество ребер E = {e, e 2,, e m }, Х = n, E = m. Причём, каждое ребро гиперграфа представляет собой некоторое подмножество вершин, т.е., j {,2,...,m} e j X где множество X подмножество вершин гиперграфа, соответствующие множеству блоков коммутационной схемы, а X 2 подмножество входных и выходных контактов коммутационной схемы. 4 Информатика, вычислительная техника и инженерное образование 20, (3) Причем, каждое ребро е Е соответствует соединённым одной электрической цепью элементам схемы. В данной математической модели каждому ребру E гиперграфа H взаимно однозначно соответствует некоторая цепь схемы. При этом заранее не обуславливается, в каком порядке будут соединяться вершины, инцидентные данному ребру. Задачу разбиения гиперграфа Н=(Х, Е) с взвешенными вершинами и рёбрами сведём к задаче о назначении множества гиперрёбер Е в К узлов при выполнении следующих условий: каждое гиперребро может быть назначено только в один узел, а стоимость вершин, назначенных в соответствующий узел, не должна превышать максимально допустимый суммарный вес вершин. Будем считать, что гиперребро назначено в узел, если всё множество составляющих его вершин назначено в этот узел. Таким образом, задача разбиения гиперграфа с взвешенными вершинами и рёбрами по критерию минимальной стоимости связей между узлами, или, что одно и то же, максимальной стоимости гиперрёбер, полностью размещённых в узлах, формулируется следующим k m образом: максимизировать F = h jv ψ j, при ограничениях: v = j = n yiv ϕ i p v ; v =, 2,, k; i = k yiv = ; i =, 2,, n; () v= yiv h jv Θ(е j ); j =, 2,, m; v =, 2,, k, i I j где y iv, hjv заданные условия; ϕ i вес i-й вершины; ψ j вес j-го гиперрёбер; p v максимально допустимый суммарный вес вершин, назначенных в v-й узел. Реализация этого критерия очень важна, т.к. очевидно, что внешние соединения между частями схемы являются одним из важнейших факторов, определяющих надёжность электронных устройств, а реализация этого критерия обеспечивает минимизацию взаимных индуктивных наводок, упрощение конструкции и, как следствие, повышение надёжности работы. На рис. 2 показан гиперграф, соответствующий коммутационной схеме (см. рис. ). Рис. 2. Неориентированный гиперграф H = (X, E) Для упрощения в нём не показаны входные и выходные контакты. Здесь каждое ребро гиперграфа представлено в виде замкнутой кривой, охватывающей инцидентные ребру вершины. 5 Информатика, вычислительная техника и инженерное образование 20, (3) Описание гиперграфа рассматриваемой схемы имеет вид: e = { x, x 2, x 5 }, e 2 ={ x 2, x 3 }, e 3 = { x, x 4, x 5 }, e 4 = { x 2, x 4, x 5 }, e 5 = { x 3, x 4, x 5 }. Гиперграф Н может быть описан и в матричном виде с помощью матрицы инцидентности: I(Н)= π ij, где i =, 2,..., n + N; j =, 2,..., D; (2) e e 2 e 3 e 4 e 5 I(H) = 2 3 (3) 4 5 Указанный способ представления схемы гиперграфом приводит к адекватной математической модели в тех случаях, когда элементы схемы (блоки) допускают стягивание в точку. Это возможно либо в случае безразличного расположения контактов (выводов на блоке), либо в случае использования гиперграфов для задач, в которых не существен порядок выводов. Програмная реализация интегрированного алгоритма Эффективность интегрированных алгоритмов определяется тщательной настройкой их параметров. При произвольном выборе параметров эффективность алгоритма может быть как очень высокой, так и очень низкой, а его надёжность может лежать в приделах от нуля до ста процентов для одной и той же задачи. Поэтому в результате тщательной настройки параметров данного алгоритма удаётся повысить его эффективность и снизить при этом время работы [5]. На рис. 3 показано окно настройки параметров разработанного интегрированного алгоритма компоновки. Рис. 3. Задание параметров интегрированного алгоритма компоновки Так как алгоритм является стохастическим, то для каждой настройки алгоритма эксперименты проводились по десять прогонов с ограничением по числу итераций, равным ста. В качестве параметра эффективности использовался процент нахождения оптимума целевой функции относительно ПГА. 6 Информатика, вычислительная техника и инженерное образование 20, (3) На рис. 4 показано окно для задания исходных данных задачи компоновки. Вес всех вершин принимался равным нулю, т.е. фактически не учитывался, а вес всех гиперрёбер единице. Число вершин генерируемого гиперграфа X = 40, а число гиперрёбер Е = 60. Рис. 4. Задание исходных данных задачи компоновки Далее осуществлялась генерация коммутационной схемы ЭВА на основе гиперграфовой модели, по заданным параметрам, что показано на рис. 5. Рис. 5. Генерация коммутационной схемы ЭВА После запуска интегрированного алгоритма компоновки получили разбиение на 2 подгиперграфа с равным количеством вершин в каждом разбиении, что показано на рис. 6. 7 Информатика, вычислительная техника и инженерное образование 20, (3) Рис. 6. Результат работы интегрированного алгоритма компоновки на основе роевого интеллекта (ИАКРИ) Заключение Проанализировав вышеизложенные факты, можно утверждать, что гиперграфовая модель является оптимальным вариантом для решения задачи компоновки элементов ЭВА в сильносвязные блоки при проектировании СБИС. Разработанный интегрированный алгоритм получает оптимальные результаты за меньшее число итераций за счёт направленности эволюционно-генетического поиска. Таким образом, использование предложенного интегрированного алгоритма компоновки на основе роевого интеллекта позволяет повысить эффективность решения задач конструкторского проектирования САПР СБИС, экономит процессорное время и память ЭВМ. Библиографический список. Норенков И.П. Основы автоматизированного проектирования. М.: Изд-во МГТУ им. Н.Э. Баумана, с. 2. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем: учеб. пособие для вузов. М.: Высш. школа, с. 3. Курейчик В.В., Курносова Е.Е. Эвристический эволюционно-генетический алгоритм // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, Курносова Е.Е. Интегрированный алгоритм поиска оптимальных решений в задачах оптимизации // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS 08) и «Интеллектуальные САПР» (CAD-2008). Научное издание в 4-х томах. М.: Физматлит, 2008, Т.. С Курейчик В.В., Полупанова Е.Е. Экспериментальные исследования интегрированнго алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, Курейчик, В.В., Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур: монография. Таганрог: Изд-во ТТИ ЮФУ, с. 8 Информатика, вычислительная техника и инженерное образование 20, (3) Курейчик Владимир Викторович Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге , г. Таганрог, пер. Некрасовский, 44. Тел.: 8(8634) Кафедра систем автоматизированного проектирования. Заведующий кафедрой, д.т.н., профессор. Курносова Наталья Евгеньевна Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге , г. Таганрог, пер. Комсомольский, 5, кв. 8. Тел.: 8(928) Кафедра систем автоматизированного проектирования. Полупанова Елена Евгеньевна Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге , г. Новороссийск, ул. Дзержинского, 95, кв. 47. Тел.: 8(928) Кафедра систем автоматизированного проектирования; аспирант. Kureichik Vladimir Viktorovich Taganrog Institute of Technology Federal State-Owned Educational Establishment of Higher Vocational Education Southern Federal University. 44, Nekrasovskiy, Taganrog, , Russia. Phone: 8(8634) The Department of Computer Aided Design. Head the Department of Computer Aided Design, professor. Kurnosova Natalia Evgenievna Taganrog Institute of Technology Federal State-Owned Educational Establishment of Higher Vocational Education Southern Federal University. 5, ap. 8, Komsomolskiy, Taganrog, , Russia. Phone: 8(928) Department of Computer Aided Design. Polupanova Elena Evgenievna Taganrog Institute of Technology Federal State-Owned Educational Establishment of Higher Vocational Education «Southern Federal University» 95, ap. 47, Dzerzhinskogo Street, Novorossiysk, , Russia. Phone: 8(928) Department of Computer Aided Design; post-graduate student. 9
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks