Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Инструкция'
наиболее рациональные способы проверки, ремонта, сборки, установки и обслуживания электродвигателей и электроаппаратуры, способы защиты их от перенап...полностью>>
'Статья'
Желая стимулировать и ускорить экономический прогресс развивающихся стран путем принятия мер, предназначенных повысить эффективность их правовых сист...полностью>>
'Лекция'
Важно отметить, что общий (конституционный) статус является единым и одинаковым для всех граждан государства, не зависящим от конкретных обстоятельст...полностью>>
'Семинар'
2. Особенности налогообложения курсовых разниц в условиях применения ПБУ 3/2006 «Учет активов и обязательств, стоимость которых выражена в иностранно...полностью>>

Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное моделирование, генетические и бионические алгоритмы

Главная > Решение
Сохрани ссылку в одной из сетей:

Информатика, вычислительная техника и инженерное образование 2011, № 1(3)

ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ

УДК 681.3

В.В. Курейчик, Н.Е. Курносова, Е.Е. Полупанова

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ИНТЕГРИРОВАННОГО

АЛГОРИТМА КОМПОНОВКИ1

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

Интегрированный алгоритм, математическая модель, гиперграф.

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.

Введение

Задачи конструкторского проектирования принадлежат к классу комбинаторных оптимизационных задач, реализация которых на ЭВМ зависят от выбираемой формальной математической модели коммутационной схемы. Различные математические модели в различной степени описывают одни и те же параметры устройства при решении каждой конкретной задачи конструкторского проектирования. В этой связи на различных этапах конструкторского проектирования используются различные коммутационные модели. Одним из важнейших вопросов этапа конструкторского проектирования ЭВА, РЭА, объектов машиностроения и др. является компоновка коммутационной схемы рассматриваемого устройства в конструктивно законченные части. Данная задача решается посредством разбиения схемы, с последующим группированием компонентов в блоки. В результате разбиения формируется множество блоков и межсоединений между блоками [1,2].

В данной работе рассмотрена гиперграфовая математическая модель задачи компоновки, а также приводится программная реализация интегрированного эволюционно-генетического алгоритма, рассмотренного в [3-5].

Построение математической модели для задачи компоновки

Математическая модель – это совокупность математических объектов (чисел, переменных, векторов, множеств и т.п.) и отношений между ними, которая адекватно отображает некоторые свойства проектируемого технического объекта [2]. Различные математические модели с различной степенью точности описывают одни и те же параметры устройства. В этой связи, к математическим моделям предъявляются следующие требования:

  • адекватность и простота представления исходного объекта;

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

  • разумный объём памяти ЭВМ, отводимый для хранения информации о модели;

  • степень разработанности математического аппарата для оперирования с математическими моделями;

  • простота обработки.

Любая функциональная или принципиальная электрическая схема СБИС состоит из некоторого набора базовых элементов, определенным образом связанных между собой. Тогда схему можно рассматривать как некоторое множество элементов x1, х2, ..., xп, соединенных между собой цепями из множества E. На рис. 1 показана условная коммутационная схема блоков ЭВА. Здесь x1- x5 блоки; е15 цепи (внешние связи); k1, k2  внешние контакты цепей схемы.

Рис. 1. Условная коммутационная схема блоков ЭВА

Графотеоретические модели объектов сохраняют всю наглядность и содержательность описываемых объектов и позволяет строить формальные алгоритмы конструирования, которые легко обрабатываются на ЭВМ. В этой связи, рассмотрим задачу компоновки блоков в конструктивно-законченные части на примере гиперграфовой математической модели [6].

Считают, что гиперграф Н = (X, E) задан, если задано множество вершин и множество ребер E = {e1, e2, …, em}, |Х|= n, |E| = m. Причём, каждое ребро гиперграфа представляет собой некоторое подмножество вершин, т.е.,

где множество X1 – подмножество вершин гиперграфа, соответствующие множеству блоков коммутационной схемы, а X2 – подмножество входных и выходных контактов коммутационной схемы.

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

Задачу разбиения гиперграфа Н=(Х, Е) с взвешенными вершинами и рёбрами сведём к задаче о назначении множества гиперрёбер Е в К узлов при выполнении следующих условий: каждое гиперребро может быть назначено только в один узел, а стоимость вершин, назначенных в соответствующий узел, не должна превышать максимально допустимый суммарный вес вершин. Будем считать, что гиперребро назначено в узел, если всё множество составляющих его вершин назначено в этот узел. Таким образом, задача разбиения гиперграфа с взвешенными вершинами и рёбрами по критерию минимальной стоимости связей между узлами, или, что одно и то же, максимальной стоимости гиперрёбер, полностью размещённых в узлах, формулируется следующим образом:

k m

максимизировать F = h jv j , при ограничениях:

v 1 j 1

n

yivi pv ; v = 1, 2, …, k;

i 1

k

yiv 1; i = 1, 2, …, n; (1)

v1

yiv hjv (еj); j = 1, 2, …, m; v = 1, 2, …, k,

iI j

где yiv, hjv – заданные условия; i – вес i-й вершины; j – вес j-го гиперрёбер; pv – максимально допустимый суммарный вес вершин, назначенных в v-й узел.

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

На рис. 2 показан гиперграф, соответствующий коммутационной схеме (см. рис. 1).

Рис. 2. Неориентированный гиперграф H = (X, E)

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

Описание гиперграфа рассматриваемой схемы имеет вид: e1 = { x1, x2, x5}, e2={ x2, x3}, e3= { x1, x4, x5}, e4= { x2, x4, x5}, e5= { x3, x4, x5}. Гиперграф Н может быть описан и в матричном виде – с помощью матрицы инцидентности:

I(Н)=||πij||, где i = 1, 2,..., n + N; j = 1, 2,..., D; (2)

(3)

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

Програмная реализация интегрированного алгоритма

Эффективность интегрированных алгоритмов определяется тщательной настройкой их параметров. При произвольном выборе параметров эффективность алгоритма может быть как очень высокой, так и очень низкой, а его надёжность может лежать в приделах от нуля до ста процентов для одной и той же задачи. Поэтому в результате тщательной настройки параметров данного алгоритма удаётся повысить его эффективность и снизить при этом время работы [5]. На рис. 3 показано окно настройки параметров разработанного интегрированного алгоритма компоновки.

Рис. 3. Задание параметров интегрированного алгоритма компоновки

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

На рис. 4 показано окно для задания исходных данных задачи компоновки. Вес всех вершин принимался равным нулю, т.е. фактически не учитывался, а вес всех гиперрёбер − единице. Число вершин генерируемого гиперграфа X = 40, а число гиперрёбер Е = 60.

Рис. 4. Задание исходных данных задачи компоновки

Далее осуществлялась генерация коммутационной схемы ЭВА на основе гиперграфовой модели, по заданным параметрам, что показано на рис. 5.



Рис. 5. Генерация коммутационной схемы ЭВА

После запуска интегрированного алгоритма компоновки получили разбиение на 2 подгиперграфа с равным количеством вершин в каждом разбиении, что показано на рис. 6.



Рис. 6. Результат работы интегрированного алгоритма компоновки на основе роевого интеллекта (ИАКРИ)

Заключение

Проанализировав вышеизложенные факты, можно утверждать, что гиперграфовая модель является оптимальным вариантом для решения задачи компоновки элементов ЭВА в сильносвязные блоки при проектировании СБИС. Разработанный интегрированный алгоритм получает оптимальные результаты за меньшее число итераций за счёт направленности эволюционно-генетического поиска. Таким образом, использование предложенного интегрированного алгоритма компоновки на основе роевого интеллекта позволяет повысить эффективность решения задач конструкторского проектирования САПР СБИС, экономит процессорное время и память ЭВМ.

Библиографический список

  1. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. – ­360 с.

  2. Норенков И. П. Введение в автоматизированное проектирование технических устройств и систем: учеб. пособие для вузов. – М.: Высш. школа, 1980. – 311с.

  3. Курейчик В.В., Курносова Е.Е. Эвристический эволюционно-генетический алгоритм // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2009.

  4. Курносова Е.Е. Интегрированный алгоритм поиска оптимальных решений в задачах оптимизации // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS’08) и «Интеллектуальные САПР» (CAD-2008). Научное издание в 4-х томах. – М.: Физматлит, 2008, Т. 1. − С. 193-197.

  5. Курейчик В.В., Полупанова Е.Е. Экспериментальные исследования интегрированнго алгоритма компоновки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2010.

  6. Курейчик, В.В., Полупанов А.А. Эволюционные методы разбиения схем на основе адаптивных генетических процедур: монография. – Таганрог: Изд-во ТТИ ЮФУ, 2007. – 160 с.

Курейчик Владимир Викторович

Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге.

E-mail: vkur@

347928, г. Таганрог, пер. Некрасовский, 44.

Тел.: 8(8634) 38-34-51.

Кафедра систем автоматизированного проектирования.

Заведующий кафедрой, д.т.н., профессор.

Курносова Наталья Евгеньевна

Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге.

E-mail: kurnosova_88@

347928, г. Таганрог, пер. Комсомольский, 5, кв. 18.

Тел.: 8(928) 171-75-10.

Кафедра систем автоматизированного проектирования.

Полупанова Елена Евгеньевна

Технологический институт федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге

E-mail: jienka@

353900, г. Новороссийск, ул. Дзержинского, 195, кв. 47.

Тел.: 8(928) 401-33-01.

Кафедра систем автоматизированного проектирования; аспирант.

Kureichik Vladimir Viktorovich

Taganrog Institute of Technology – Federal State-Owned Educational Establishment of Higher Vocational Education “Southern Federal University”.

E-mail: vkur@

44, Nekrasovskiy, Taganrog, 347928, Russia.

Phone: 8(8634) 38-34-51.

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”.

E-mail: kurnosova_88@

5, ap. 18, Komsomolskiy, Taganrog, 347928, Russia.

Phone: 8(928) 171-75-10.

Department of Computer Aided Design.

Polupanova Elena Evgenievna

Taganrog Institute of Technology – Federal State-Owned Educational Establishment of Higher Vocational Education «Southern Federal University»

E-mail: jienka@

195, ap. 47, Dzerzhinskogo Street, Novorossiysk, 353900, Russia.

Phone: 8(928) 401-33-01.

Department of Computer Aided Design; post-graduate student.

УДК 681.3

В.В. Гудилов

ЭВОЛЮЦИОННОЕ ПРОЕКТИРОВАНИЕ СЛОЖНЫХ СИСТЕМ

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

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

V.V. Gudilov

EVOLUTIONARY DESIGNING OF DIFFICULT SYSTEMS

This work considers one of the modern CAD’s basic problems – a designing of a difficult systems. The problem’s decision is considered as the set of positions and principles defining intellectual systems of an automated designing building technique. The basis of the intellectual methods is the evolutionary algorithms by the instrumentality of the tasks solution of the structural and parametrical synthesis for problems with the incomplete information is shown on. The issues of the hardware support of resource-intensive evolutionary algorithms by means of the hybrid multiprocessing computing structures’ construction are touched upon and the necessity of the dynamically changeable evolutionary algorithms’ development for their designing is shown. In conclusion of the application issues of evolutionary methods for the hardware-software co-design task solution are considered. The effective solution of this task is necessary for working with the heterogeneous multiprocessing architectures.

The evolutionary designing of complex systems; the evolutionary algorithms of parametrical and structural synthesis with incomplete information; the dynamically changeable evolutionary algorithms; the support of evolutionary algorithms’ computing load; the evolutionary methods of hardware-software co-design.

Проектирование сложных систем

Определение “Сложная система” в современном толковании имеет множество значений и представление, обусловленных предметной областью, в рамках которой рассматривается система. Различные предметные области оговаривают не только сущность сложных систем, но и степени иерархических взаимодействий подсистем, их взаимосвязи и формы сложности. Например, для сложных технических систем Н.Г. Ярушкина [1] вводит следующее определение: сложная техническая система – это система с разнообразными частями и связями, развивающаяся во времени и объективно содержащая неопределенность в описании поведения. Большой энциклопедический словарь определяет сложную систему как составной объект, части которого можно рассматривать в виде отдельных систем, объединенных в единое целое в соответствии с определенными принципами или связанных между собой заданными отношениями. Не смотря на различия множества определений сложных систем, общим для них является то, что сложность современных систем зачастую превышает возможности человеческого интеллекта, т.е. человек уже неспособен учитывать все множество параметров и состояний проектируемых систем без помощи дополнительных средств автоматизированной разработки и имитационного моделирования. Таким образом, дальнейший рост сложности систем определяется возможностями систем имитационного моделирования и их способностью соответствовать и опережать требования проектируемых систем.

Р. Шагалиев с своей работе [2] указывает, что сегодня 95% высокотехнологической продукции производится с использованием полномасштабного имитационного моделирования. В подавляющем большинстве случаев применяется моделирование на стадии проектирования компонентов и фрагментов сложных систем. В основе моделирования лежит идея использования имитационного моделирования мелкомасштабных аналогов на этапах изучения и оценки параметров моделируемых систем. Как показано в [3], целью имитационного моделирования при проектировании сложных систем является воспроизведение поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между ее элементами. Но применение имитационного моделирования для реальных систем осложняется влиянием случайных факторов, содержанием большого числа параметров, множеством связей между элементами и разнообразными нелинейными ограничениями, учет которых аналитическим путем представляет весьма большие трудности, зачастую непреодолимые при большом их числе. В работе [1] Н.Г. Ярушкина утверждает, что: попытки применения традиционных математических моделей на ранних стадиях проектирования малоэффективны, поскольку основаны на обработке точных и полных численных данных и не соответствуют высокому уровню неопределенности задачи.

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

В настоящий момент подавляющая часть рынка разработки систем автоматизированного проектирования принадлежит западноевропейским компаниям, данные компании имеют внушительный опыт разработки и внедрения систем проектирования и кажется, что нет смысла разрабатывать что-то новое в данном направлении. Но имеющиеся на рынке средства САПР довольно дороги. Несмотря на многообразие полнофункциональных САПР западноевропейских разработчиков, их использование в Российской Федерации зачастую ограничено учебными версиями, для наиболее наукоемких и стратегически важных направлений средства проектирования на рынок не выставляются, продажа современных САПР и высокотехнологичного оборудования для предприятий военно-промышленного комплекса РФ запрещена законодательством многих западноевропейских стран. Подобная ситуация просматривается и с конкурентно-способными предприятиями в космической, авиастроительной, энергетической и других отраслях РФ. Поэтому соответствующие зарубежные средства для российских предприятий оказываются недоступными. В то же время, без автоматизации проектирования не удастся достичь успеха в создании сверхсложных технических систем, в том числе в многокристальном, гибридном или "система-на-кристалле" (System-on-Chip) исполнении. Новые направления разработок, в основе которых лежат идеи объединения электрических, оптических, механических и, возможно, биологических элементов в единые микросистемные проекты, требуют разработки новых методов системного проектирования.

Увеличение сложности систем проектирования ведет к неизбежному росту требований к вычислительным ресурсам, необходимым для поддержания функционирования более сложных и ресурсоемких систем, ориентированных на заданную предметную область. Количество процессоров в современных многопроцессорных системах исчисляется тысячами, но несложно видеть, что существует некий предел, за которым попытки увеличения быстродействия за счет увеличения количества вычислительных процессоров не будет приводить к желаемому результату. С другой стороны, уже сейчас разработчики столкнулись с проблемами по решению вопросов энергопотребления и охлаждения разрабатываемых суперкомпьютерных систем. Лидеры рейтинга Top500 самых быстрых суперкомпьютеров мира подошли к некоторому естественному пределу по энергопотреблению: в одном из докладов японские специалисты объявили, что готовы создать суперкомпьютер с энергопотреблением в 20 Мегаватт. Несложно видеть, что рост производительности посредством наращивания архитектурной составляющей будет отходить на второй план. На передний план встают вопросы разработки новых технологий повышения производительности при снижении энергопотребления, а также алгоритмов и методов эффективного использования имеющихся ресурсов, т.е. эффективного распределения вычислительной нагрузки между компонентами системы, т.к. известно, что реальная производительность многопроцессорных систем не является линейно-зависимой от количества процессоров в системе. Производительность многопроцессорных систем для различного класса задач может различаться на несколько порядков. Поэтому дальнейшее развитие суперкомпьютерных технологий может пойти по пути создания объектно-ориентированных суперкомпьютерных вычислительных систем, т.е. систем, универсальных в рамках ограниченного класса задач, но при этом максимально эффективных и производительных в своей предметной области. Данное направление активно развивается для небольших систем, в которых разработчики пытаются добиться хороших результатов при ограниченном бюджете посредством разработки гетерогенных систем с использованием специализированных узлов и акселераторов. Параллельно развивается новое направление в проектировании вычислительной техники, в основе которого лежит создание все более и более неоднородных систем, способных реконфигурировать собственную архитектуру в соответствии со спецификой решаемой задачи, и содержащих наборы разного рода параллельно функционирующих ускорителей. Аппаратные ускорители специально проектируются для программного кода, создающего высокую вычислительную нагрузку. В зависимости от степени детализации, аппаратное ускорение может варьироваться от небольшой функциональной единицы до крупного функционального блока, как например, видеообработка в MPEG2 и т.п.



Скачать документ

Похожие документы:

  1. В. В. Гудилов эволюционное проектирование аппаратных средств

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

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

    Книга
    Сибирской государственной геодезической академии); д-р геогр. наук, проф. В. 3. Макаров (зав. кафедрой физической географии и ландшафтной экологии Саратовского государственного университета)
  4. Технологические пакеты

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

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

Другие похожие документы..