Journal influence
Bookmark
Next issue
The distributed subsystem of the electronic circuits design
The article was published in issue no. № 3, 2013 [ pp. 263-272 ]Abstract:The chronological express analysis of the approaches to constructing high-speed CAD electronic schemes is given. The attention is directed to the fact that the systems of automated designing should satisfy the interactivity require-ment. This requirement can be realized when the system gives replies to the user inquiries with a delay not exceeding2-3 se-conds. In the conditions of constant increasing of projected objects complexity the maintenance of automated designing sys-tems interactivity is impossible without constant escalating of their high-speed properties. The article considersthree essen-tial directions of CAD interactivity maintenance. Taking into account general expansion of network technologies, using the potential of various kinds of networks for creation of distributed CAD is a perspective and promising direction of researches. There is the structure developed by authors and the results of imitating modeling of distributed CAD that substantiated the expediency of constructing a real subsystem of designer projecting of electronic schemes. The basic modules of the subsys-tem, their functioning and results of experimental researches are described. Experimental researches have shown that the de-veloped subsystem is referred to the type of GRID-systems and allows reducing time of projecting to 3 times.
Аннотация:Дается хронологический экспресс-анализ подходов к построению быстродействующих САПР электронных схем. Заостряется внимание на том, что САПР должны удовлетворять требованию интерактивности. Реализация этого требования возможна, если ответы на запросы пользователя система будет выдавать с задержкой не более 2–3 секунд. В условиях постоянного повышения сложности проектируемых объектов поддержание интерактивности САПР невозможно без постоянного наращивания их скоростных свойств. В статье рассматриваются три основных направления обеспечения интерактивности САПР. В связи со всеобщим расширением сетевых технологий перспективным и многообещающим направлением исследований является использование возможностей различных видов сетей для создания распределенных САПР. Приводятся разработанные авторами структура и результаты имитационного моделирования распределенной САПР, ставших обоснованием целесообразности построения реальной подсистемы конструкторского проектирования электронных схем. Описаны основные модули подсистемы, их функционирование и результаты экспериментальных исследований. Экспериментальные исследования показали, что разработанная подсистема относится к типу GRID-систем и позволяет уменьшить время проектирования до трех раз.
Authors: Glushan V.M. (gluval07@rambler.ru) - Academy of Engineering and Technology Southern Federal University, Taganrog, Russia, Ph.D, (levarto@mail.ru) - , Russia | |
Keywords: client-server architecture, simulation, distributed cad, Grid-system |
|
Page views: 11071 |
Print version Full issue in PDF (13.63Mb) Download the cover in PDF (1.39Мб) |
Проектирование с помощью САПР предполагает ведение интерактивного диалога человека с ЭВМ. Поэтому такое проектирование является автоматизированным, а не автоматическим. Оно сочетает скоростные возможности средств вычислительной техники в переборах вариантов решений и творческие способности человека при оценке и принятии решений. Интерактивный диалог эффективен, если он происходит в режиме реального времени (РРВ). В САПР под РРВ понимается такое взаимодействие пользователя и ЭВМ, когда ответы на запросы пользователя поступают из ЭВМ со скоростью, комфортной для пользователя. Известно [1], что для реализации РРВ необходимо, чтобы ЭВМ выдавала ответы не более чем через 2–3 секунды после поступления запроса пользователя. В противном случае человек становится самым ненадежным звеном в цепи «человек–ЭВМ», внося существенную долю ошибок, вызванных длительным ожиданием ответа. При этом теряется всякий смысл в использовании режима диалога. В [2] выделены три основных направления в обеспечении интерактивности САПР: многопроцессорные вычислительные системы (МВС), пакеты прикладных программ (ППП) пользователя, распределенные системы [3, 4].
В настоящей статье приводятся некоторые результаты исследований по созданию программной подсистемы автоматизированного конструкторского проектирования электронных схем. С точки зрения системной архитектуры и организации вычислительного процесса разработанная подсистема наиболее близка интенсивно развивающейся GRID. Имитационное моделирование распределенной подсистемы Первый шаг в создании подсистемы состоит в анализе и обосновании ее эффективности. В качестве критерия эффективности выбрано время проектирования. Исследование эффективности было проведено путем имитационного моделирования по специально разработанной структурной схеме, приведенной на рисунке 1. Очевидно, что время проектирования зависит от числа частей (подсхем), на которые будет разбита исходная принципиальная схема при условии, что все части обрабатываются одновременно. По окончании процесса обработки каждой части должна осуществляться «сборка» всех частей. При такой организации процесса проектирования необходимо оптимальное сочетание двух противоречивых процедур. Первая – обработка каждой из подсхем. Чем подсхем больше, тем меньше их сложность (в каждой подсхеме будет меньше элементов и, соответственно, связей между ними), а поэтому и время обработки каждой из них будет меньше. Вторая процедура – сборка всех частей в единую схему. Она протекает тем дольше, чем на большее число частей разбита исходная схема, так как тогда при сборке приходится обрабатывать большее число связей между подсхемами. Таким образом, ясно, что должно существовать оптимальное число подсхем, на которое целесообразно разбивать проектируемую схему. Для проведения экспериментальных иссле- дований по схеме (рис. 1) была разработана программа имитационного моделирования. Она состоит из трех основных модулей: модуля формирования случайных схем с заданными топологическими свойствами, проектирующего модуля и модуля статистической обработки. Назначение первого модуля – генерация множества случайных схем. Второй модуль осуществляет непосредственное конструкторское проектирование, а третий реализует удобный исследовательский интерфейс для задания необходимых схем, а также выводит на экран компьютера нужные графические зависимости и спроектированную схему (Глушань В.М., Лаврик П.В. Свид. о госрегистр. прогр. для ЭВМ № 2010612909 28.04.2010).
Структура реальной распределенной подсистемы Имитационное моделирование вместе с ранее полученными теоретическими результатами, изложенными в [6], стимулировало разработку реальной распределенной подсистемы конструкторского проектирования электронных схем. Для построения распределенной подсистемы была выбрана клиент-серверная архитектура, поскольку она является относительно простой в реализации и не требует специальных настроек операционных систем используемых машин. Особенность реализации подсистемы в том, что сервер является активной управляющей компонентой, а клиенты – пассивными поставщиками вычислительных ресурсов. Общая схема распределенной подсистемы конструкторского проектирования представлена на рисунке 2. На серверную часть подсистемы возложены следующие функции: управление процессом проектирования, синхронизация потоков данных, удаленное управление клиентами, генерация моделей схем по заданным параметрам, ввод-вывод информации из файлов, прием/передача данных по сети, проведение серий экспериментов по заданным параметрам, последовательный запуск различных процедур проектирования, взаимодействие с пользователем, отображение информации о результатах экспериментов. В связи с этим серверную часть можно условно разделить на блоки интерфейса, проектирования и управления. Блок проектирования, в свою очередь, подразделяется на платформу, в которую входят структуры данных и генераторы этих структур, и надстройку, включающую внутренние реализации алгоритмов проектирования, блок взаимодействия с подключаемыми библиотеками и блок набора и обработки статистических данных.
Блок проектирования (рис. 4) содержит: – базу встроенных реализаций алгоритмов конструкторского проектирования; – интерфейс для подключения сторонних реализаций различных процедур проектирования; – реализацию процесса проектирования с возможностью циклического повтора и автоматической работы по набору статистических данных; – генераторы графовых моделей схем, ДРП, схем с заданными топологическими свойствами; – структуры данных, представляющие схему. Под сторонними реализациями проектных процедур понимаются генераторы схем, средства ручного ввода схем, средства конвертации схем из других форматов, реализации алгоритмов конструкторского проектирования, отличающихся от встроенных принципами решения задач. Сторонние реализации должны быть оформлены в виде dll-библиотек и поддерживать внутренние структуры данных подсистемы. В блоке проектирования применяются следующие встроенные алгоритмы: конструктивный алгоритм компоновки, итерационный алгоритм парных перестановок, двухэтапный итерационно-последовательный алгоритм размещения пограничных элементов в подсхемах с использованием принципов факторизации и силовой релаксации, размещение элементов алгоритмом групповых перестановок, трассировка соединений волновым алгоритмом.
Двухэтапный итерационно-последовательный алгоритм размещения пограничных элементов в подсхемах с использованием принципов факторизации и силовой релаксации заключается в следующем. На первом этапе по результатам ком- поновки формируется взвешенный граф (рис. 5), каждая вершина которого соответствует одной подсхеме разбиения, ребра между вершинами показывают наличие внешних связей между конкретными подсхемами, а вес ребра соответствует числу внешних связей, то есть производится процедура факторизации графа, представляющего схему. Далее осуществляется размещение подсхем на основе взвешенного графа с использованием парных перестановок.
Второй этап начинается с извлечения клиентом информации из полученного файла. Создается начальное размещение элементов, при этом используется сила растяжения, модуль которой равен весу вершины, а направление задается векторами, поставленными в соответствие каждой вершине на первом этапе. Блок-схема второго этапа применяемого алгоритма приведена на рисунке 6. Реализация структур данных В подсистеме используются структуры данных, представляющие ДРП, цепи, целостное описание схемы, а также входные и выходные файлы. При реализации целостного описания схемы предъявлялись следующие требования к структуре данных. 1. Для генерации исходной схемы минимальными входными данными являются число элементов, число контактов элемента, число цепей, разветвленность цепи (под ней понимается число контактов, инцидентных данной цепи), дисперсия разветвленности. Могут быть также заданы размеры ДРП и расстояние между элементами. В результате должны быть получены графовое представление схемы и список цепей. 2. Для решения задачи компоновки необходимы данные о связях между элементами и количестве элементов. На выходе получаем информацию о принадлежности элементов к подсхемам. 3. При решении задачи размещения элементов подсхемы необходимы информация о позициях элементов на ДРП, размеры самого ДРП, число элементов в подсхеме, размеры элементов, список цепей. Результатом работы является информация о новых позициях элементов в подсхеме. 4. Входной информацией для трассировки соединений являются список цепей, координаты контактов элементов, подключенных к этой цепи, информация об уже проложенных трассах и положениях элементов. После выполнения процедуры трассировки должно быть получено описание каждой трассы в виде последовательности единичных векторов. Таким образом, разрабатываемая структура данных должна давать возможность извлечь такие данные, как число входящих в схему элементов, элементная база, список цепей, число подсхем компоновки, принадлежность элемента к подсхеме компоновки, параметры ДРП, координаты элементов на ДРП, координаты контактов элементов, информация о проложенных и прокладываемых трассах. Структура данных реализована с ориентацией на концепцию CALS-технологий с целью организации единого рабочего пространства на всех этапах проектирования. Она представляет класс DRP, который содержит следующие данные: размер поля в ячейках, размер элементной базы, количество цепей, подсхемы разбиения и их количество, представление ДРП в виде массива ячеек, массив элементов, список цепей, цепи в виде минимальных связывающих деревьев (МСД). Ячейка ДРП представляет собой квадрат 3´3 позиции и выполнена в виде класса faset. В классе содержатся физические координаты центра ячейки, номер проходящей в ней трассы, ссылки на располагающиеся рядом ячейки, вес ячейки, флаги состояния ячейки (контакт элемента, трасса, пусто). Элемент представлен прямоугольным посадочным местом, размеры которого определяются количеством контактов. Он оформлен в виде класса Element, в котором хранится информация о координатах точки привязки элемента (левый верхний угол), количестве контактов, принадлежности к подсхеме компоновки. Сами контакты являются ссылками на ячейки ДРП. Имеется также флаг заполненности элемента (элемент считается заполненным, когда ко всем его контактам подходят цепи). Для представления цепей используется минимальное связывающее дерево. С его помощью можно обеспечить близкую к реальной оценку длин цепей до этапа трассировки, адекватный перерасчет длин цепей при решении задачи размещения, значительное уменьшение времени и ресурсов, требующихся для трассировки. В качестве вершин для МСД используются ячейки ДРП, соответствующие выводам элементов. Данная структура применяется на всех этапах проектирования внутри системы. Для сохранения результатов трассировки в файл была разработана векторная структура трасс в связи с тем, что по завершении этапа трассировки трассы представляют собой совокупность ячеек ДРП, занимающих большой объем памяти и содержащих много избыточной информации. Преобразование трасс в векторную форму производится для их более компактного представления. При этом каждая трасса представляется в виде совокупности векторов, несущих в себе информацию о прямых участках. У всех векторов есть координаты начала, направление и длина. В работе подсистемы используются файлы с двумя представлениями информации. Первые используются при передаче информации о результатах компоновки на клиентские части, вторые – для передачи результатов работы клиентов на сервер. Файлы имеют текстовый формат. В случае сохранения результатов компоновки и взаимного расположения подсхем структура информации имеет следующий вид: Число элементов в блоке # число контактов элементов # число цепей в схеме # разветвленность цепей # номер элемента # вес элемента # х-составляющая силы растяжения # у-составляющая силы растяжения # № цепи, подключенной к 1-му контакту # № цепи, подключенной ко 2-му контакту # ... # номер элемента # ... Такая структура позволяет извлечь всю необходимую информацию для создания начального размещения с учетом взаимного расположения подсхем, а также для трассировки внутренних соединений. При сохранении результатов работы клиентов структура информации имеет следующий вид: № элемента в схеме # х-координата в блоке # у-координата в блоке # ... # № цепи # х-координата начала вектора # у-координата начала вектора # направление вектора # длина вектора # ... # end (окончание структуры) # процент проложенных трасс Координаты элементов даются в локальной системе координат подсхем и впоследствии пересчитываются в координаты схемы. Векторы являются представлением проложенных трасс. Таким образом, информация, сохраненная в файле, дает возможность полностью воссоздать результат работы клиента, содержащий размещение элементов и топологию проложенных трасс. Генерация исходной схемы осуществляется по таким входным параметрам, как количество элементов, количество выводов элемента, количество цепей, разветвленность цепей (математическое ожидание количества контактов, подсоединенных к цепи), отклонение разветвленности (дисперсия), коэффициент площади (отношение ширины каналов к размерам элемента). Расстояние между элементами принимается равным числу контактов элемента, умноженному на коэффициент пло- щади. В результате проведенных исследований был выявлен следующий недостаток случайной генерации цепей: происходит практически однородное заполнение цепей элементами так, что становится сложно разбить схему на сильно связанные подсхемы. При этом вся схема представляет собой один сильно связанный блок. В этом случае невозможно определить влияние решения задачи компоновки и размещения на качество последующей трассировки, так как решение первых двух задач неэффективно. Поэтому была принята следующая стратегия создания цепей: в схеме случайным образом формируется некоторое (от 3 до n/3, где n – количество элементов схемы) количество подсхем элементов. Далее при формировании очередной цепи с вероятностью 0,7 в нее включаются элементы только из одной подсхемы. С вероятностью 0,3 данная цепь не будет зависеть от количества подсхем, а цепи при этом равномерно распределятся между подсхемами. Данная стратегия выбрана из соображения, что в любой реальной схеме уже неявно присутствуют сильно связанные блоки элементов. Это обусловлено степенью их функциональной законченности. Выбранная вероятность зависимости принадлежности цепи нескольким подсхемам введена эвристически для исключения случая формирования схемы из нескольких изолированных подсхем. Пример сгенерированной схемы при принятой стратегии приведен на рисунке 7. Клиентская часть подсистемы
Результаты экспериментальных исследований Естественной и главной целью проведения экспериментов было выявление оптимального числа подсхем (и, соответственно, компьютеров-клиентов), на которые целесообразно разбивать исходную схему, чтобы обеспечить минимальное абсолютное время проектирования. При этом в качестве оценки использовалось усредненное по множеству случайных схем с одинаковыми параметрами сложности абсолютное время проектирования. В каждом опыте случайно генерировалось по 10 схем. В качестве примера на рисунке 9 приведен график, построенный на основе серии экспериментов по проектированию моделей схем, состоящих из 100 элементов с 10 контактами у каждого элемента, 50 цепями и разветвленностью
Поэтому в дальнейшем оценивалось не абсолютное время проектирования на распределенной подсистеме, а относительно сосредоточенной подсистемы. При этом по завершении каждого отдельного эксперимента вычислялась относительная величина времени работы, а по завершении серии экспериментов находилась средняя величина относительного времени в процентах. Ввиду того, что сложность схемы определяется в основном числом элементов и загруженностью цепей, были проведены серии экспериментов для исследования поведения относительного времени проектирования при изменении загруженности схемы цепями и числа блоков разбиения при фиксированных значениях размерности схемы. При этом загруженность схемы цепями определялась процентом используемости контактов элементов и последовательно увеличивалась и изменялась с шагом в 10 %. Из приведенных соображений по экспериментальным данным для случая с 400 элементами была построена трехмерная поверхность (рис. 10), представляющая относительную зависимость временного выигрыша от числа подсхем и загруженности схемы цепями (в процентах). Анализируя полученную поверхность, можно заметить, что величина выигрыша и положение оптимального числа подсхем, а следовательно и компьютеров-клиентов, в большей степени определяются размерностью схемы. Загруженность схемы цепями также влияет на размер выигрыша, но практически не влияет на положение оптимума. Кроме приведенной поверхности, интерес представляет поверхность, отражающая динамику выигрыша в зависимости от числа подсхем, но при фиксированной загруженности исходной схемы цепями. Для этого были проведены соответствующие серии экспериментов, результаты которых представлены на рисунке 11. В заключение сделаем следующие выводы: – на схемах с малым количеством элементов время проектирования достигает 3-кратного уменьшения; – на схемах с малым количеством элементов оптимальное число компьютеров-клиентов смещается в сторону больших значений по сравнению с более сложными схемами; – выигрыш по времени обратно пропорционален загруженности схемы цепями, однако с ростом размерности схемы влияние загруженности на выигрыш ослабевает; – при увеличении размерности схемы оптимальное число компьютеров-клиентов смещается в сторону меньших значений и составляет три клиента; – выигрыш при увеличении размерности схемы уменьшается достаточно резко, затем стабилизируется в районе 1,3 раза. В результате проведенных экспериментов был выяснен характер зависимости выигрыша от размерности схемы с точки зрения сложности применяемого алгоритма трассировки. В программе применяется волновой алгоритм, время работы которого растет прямо пропорционально площади ДРП, причем зависимость квадратичная. Соответственно, чем большего размера схема разбивается на подсхемы, тем больше в общем случае доля работы дотрассировки на сервере относительно клиентов в силу разности площадей ДРП у клиентов и сервера. И, следовательно, уменьшается доля работы, которую можно распараллелить. Именно по этой причине уменьшается выигрыш. На малых же схемах разница в площадях, с которыми работают компьютеры-клиенты и сервер, невелика, и поэтому растет выигрыш и смещается оптимум разбиения в сторону увеличения числа подсхем. Одним из путей решения этой проблемы, по мнению авторов, является применение алгоритмов трассировки, слабо зависящих от площади ДРП. Литература 1. Нестеров Ю.Г., Папшев Ю.С. Разработка САПР: В 10 кн. Выбор программно-технического комплекса САПР: Практ. пособие; [под ред. А.В. Петрова]. М.: Высш. школа, 1990. Кн. 6. 159 с. 2. Глушань В.М. Использование GRID-технологий для построения подсистемы автоматизированного проектирования СБИС // AIS&IT’11: тр. конгр. М.: Физматлит, 2011. 3. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с. 4. Глушань В.М., Лаврик П.В Концептуальный анализ и построение распределенной подсистемы автоматизированного конструирования электронных схем: В кн. Интеллектуальные системы: коллектив. моногр. М.: Физматлит, 2011. Вып. 5. 262 с. 5. Лаврик П.В. Концептуальные подходы параллельной обработки информации в контексте реализации распределенной САПР // AIS-IT’10: тр. конгр. М.: Физматлит, 2010. Т. 3. С. 112–118. 6. Глушань В.М., Иванько Р.В., Лаврик П.В., Орлов Н.Н. Обобщение некоторых результатов исследования когнитивной модели распределенной САПР. Изв. Волгоградского гос. технич. ун-та. 2008. № 5. References 1. Nesterov Yu.G., Papshev Yu.S., Razrabotka SAPR: v 10 kn., Kn. 6, Vybor programmno-tekhnicheskogo kompleksa SAPR: Prakt. posobie [CAD design: in 10 books, Book 6. The choice of CAD hardware and software suite: practical guide], Moscow, Vyssh. shkola, 1990. 2. Glushan V.M., Trudy kongressa po intellektualnym sistemam i informatsionnym tekhnologiyam “AIS&IT’11” [Proc. cong. on intelligent systems and IT “AIS&IT’11”], Moscow, Fizmatlit, 2011, Vol. 2. 3. Kureychik V.M., Glushan V.M., Shcherbakov L.I., Kombinatornye apparatnye modeli i algoritmy v SAPR [Combinatorial hardware simulators and algorithms in CAD], Moscow, Radio i svjaz, 1990. 4. Glushan V.M., Lavrik P.V., Intellektualnye sistemy. Kollektivnaya monografiya [Intelligent systems. Multi-author book], iss. 5, Moscow, Fizmatlit, 2011. 5. Lavrik P.V., Trudy kongressa po intellektualnym sistemam i informatsionnym tekhnologiyam “AIS&IT’11” [Proc. cong. on intelligent systems and IT “AIS&IT’11”], Moscow, Fizmatlit, 2011, Vol. 3, pp. 112–118. 6. Glushan V.M., Ivanko R.V., Lavrik P.V., Orlov N.N., Izvestiya VSTU [The Bulletin of VSTU], Volgograd, 2008, iss. 5, no. 8(46), pp. 130–134. |
Permanent link: http://swsys.ru/index.php?id=3601&lang=en&like=1&page=article |
Print version Full issue in PDF (13.63Mb) Download the cover in PDF (1.39Мб) |
The article was published in issue no. № 3, 2013 [ pp. 263-272 ] |
Perhaps, you might be interested in the following articles of similar topics:
- Система моделирования поведения групп робототехнических агентов с элементами социальной организации Кворум
- О программе расчета потерь электроэнергии в радиальных электрических сетях
- Некоторые результаты имитационного моделирования мультисервисных бортовых цифровых платформ стандарта DVB-RCS
- Программный комплекс поддержки принятия решений при оптимизации производственно-сбытового процесса
- Разработка специального программного обеспечения для ввода исходных данных при имитационном моделировании
Back to the list of articles