книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники

матричной БИС, полученное после размещения компонентов на ЭВМ Е С -1052 в течение 85 мин. Фрагмент содержит 65 электрических цепей и 27 БТ51* Видно, что дискреты с мак­ симальными значениями функции загрузки, f - 5 и / = 6, со­ ставляют менее одного процента площади МКП.

Рис. Распределение загрузки фрагмента матричной Б И С .^ - функция загрузки; А/ - число дис­

кретов МКП

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

в монтажном пространстве. На* множестве Z определено би­ нарное отношение близости, отражаемое графом близости [4 ]. Данный граф является нечетким, причем значение функции при­

надлежности ребра	^/„характеризует меру взаимного то­
пологического влияния	и l j [5 ]. Кластерами являются не­
вложенные подмножества множества Lj покрывающие L*
Кластеры соединений ранжируются в порядке убывания их
связности. Трассировка	начинается с наиболее связных* класте­

71

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

Ли т е р а т у р а

1.РЯБОВ Г.Г., ПРЕОБРАЖЕНСКИЙ Н.Б., МИКРЮКОВ Ю Г, Метод оценки результатов размещения компонентов. - В кн.:

Математическое, программное, информационное и техническое обеспечение САПР, - Изд-во Саратовского ун-та, 1982, с, 1 4 -1 3 .

2. БЕРШАДСКИЙ А.М., КАРПОВ Е.В,, ТУЖИЛОВ И.В. Размещение ячеек МАБИС по критерию минимальной загруз­ ли монтажного поля. - В кн,: Автоматизация технического про­ ектирования цифровой аппаратуры: Тез. докл, Республ. конф. - Каунас: Каунасский политехи, ин-т, 1964, с. 5 9 -6 0 .

3. БЕРШАДСКИЙ А.М., КАРПОВ Е.В., ТУЖИЛОВ И.В. Структура программного обеспечения подсистемы размещения САПР МАЕТС, - В кн.: Автоматизация конструкторского про­ ектирования РЭА и ЭВА: Тез. докл. научиэ-техн. конф. - Пен­ за: ЦДНТГ1, 1983, с. 3 4 -3 5 .

4. МАТУЛА Д.В. Методы теории графов в алгоритмах кла­ стер-анализа. - В кн.: Классификация и кластер. - М.: Мир, 1980, с. 83-1,11.

5. ТУЖИЛОВ И.В, Декомпозиция задачи трассировки с помощью методов кластерного анализа - В кн.: Автоматиза­ ция конструкторского проектирования РЭА и ЭВА: Тез. докл. научи э-техн, конф. - Пенза: ПДИТГ1, 1984, с. 7 7 -7 8 .

УДК 6 8 1 .3 .8 2

МОДЕЛИ СИСТЕМНЫХ БИБЛИОТЕК ЭЛЕМЕНТОВ ДЛЯ ИНТЕРАКТИВНЫХ САПР ПЕЧАТНЫХ ПЛАТ

Е.Г. Ойхман,

При разработке информационного обеспечения интерактив­ ных САПР печатных плат (ПП) наряду с вопросами проекти­ рования структур данных в оперативной памяти [1, 2] важ­ ную роль играет задача организации данных во внешней ламя-

7 2

ти, САПР ПП является специализированной системой, для ко­ торой, как указано в [3 ], не требуется разработки сложных СУБД, а достаточно обычных средств управления файлами, име­ ющихся в составе операционной системы. Тем не менее даже в этом случае логическая структура данных во внешней памя­ ти в значительной мере определяет возможности системы,удоб­ ство ее для пользователя,.

С расширением круга задач, решаемых в САПР ПП, увели­ чивается количество атрибутов у электрорадиээлементов (ЭРЭ); причем новые атрибуты обычно не являются индивидуальными характеристиками ЭРЭ, то есть их значения совпадают для многих ЭРЭ, Примерами таких атрибутов являются номинал ЭРЭ, геометрическое представление ЭРЭ на принципиальной электрической схеме (ПЭС), цена, геометрическое представ­ ление ЭРЭ на сборочном чертеже Г1П и т.д. Для хранения та-' ких атрибутов используется системная библиотека элементов, размещаемая во внешней памяти ЭВМ. Системная библиотека обычно создается для множества всех ЭРЭ, используемых в системе проектирования. Организация системной библиотеки должна предусматривать возможность расширения библиотеки как путем включения в нее новых элементов, так и путем вклю­ чения в ее состав новых атрибутов элементов (образов).

	Пусть /?		- множество ЭРЭ, используемых в системе про­
ектирования ПГ1. Рассмотрим множество задач, решаемых в
системе, F=			.^которые используют данные					об элементах te R .
Не	детализируя			характер использования				этих данных, бу­
дем предполагать, что каждая задача FJ определяет на множе­
стве		некоторое отображение					A jt ставящее в соот­
ветствие		элементу £ f			совокупность	характеристик соответ­
ствующего ЭРЭ,				используемых задачей			F j . Очевидно,		что
разбивает множество F на классы элементов, эквивалентных
с точки зрения задачи					Fj. Множество задач
назовем		подсистемой,			если
	Таким образом, множество задач /"представляется								в вице
совокупности			подсистем //^ ц л н каждой из которых определе­
но	отображение				«Множество Л}		будем называть < -м
библиотечным			оорпзэм		множества ^	о элементы множества
	-библиотечными образами элементов 4							Рассмотрим мно­
жество 4 s*At				*Ап>и	отображение^			.-*£V*rae	чис­
ло подсистем. Тогда отображение								‘будем Называть
							г-7

73

-библиотечным. Отображение у	представляет собой инъекцию,
поскольку не у всех элементов а £ А есть прообраз в		R *Си­
стемной библиотекой назовем	множество 3 » { фС{){Ь£	Я / СА .

Разработка принципов организации системной библиотеки должна быть связана с обеспечением возможности ее расшире­

ния как путем включения новых элементов в R j так	и путем
увеличения числа хранимых в ней образов элементов	& . При

оценке метода организации библиотеки по объему занимаемой памяти применим аппарат реализации бинарных отношений, опи­ санный в [2 ].

Рассмотрим некоторые модели системных библиотек. В си­ стеме ГРИФ [4 ] имеется библиотека групповых элементов. Множество образов каждого элемента описывается .в одном файле, хранящемся на системном диске. Библиотечный элемент указывается с помощью имени файла, а выбор нужного образа осуществляет прикладная программа.. Для пополнения библиоте­ ки используется специальная программа формирования новых элементов. Однако, добавление новых образов к уже имеющим­ ся в библиотеке элементов в этом случае затруднено.

Таким образом, библиотека групповых элементов в систе­ ме ГРИФ представляет собой структурно независимое множе­

ство в .	Пусть		I	- множество ЭРЭ		на ПЭС или ПП. Исполь­
зование	библиотеки 3				возможно путем вычисления			отображе­
ния ^ставящ его				в соответствие некоторому ЭРЭ				/^мно­
жество его библиотечных образов, то есть							в.	Вычисле­
ние отношения J				д	в системе ГРИФ выполняет сам чело­
век. Для	этой	цели у			представляется в виде композиции
					ставит в соо^етствие		ЭРЭ его номи­
нал, а	- ^ * 2 позволяет по номиналу найти						имя соответст­
вующего файла, содержащего описание библиотечных» образов
для ЭРЭ	этогр		номинала. Отношение			задается перечнем эле­
ментов,	a	-	распечаткой каталога			файлов.
Объем памяти, требуемой для хранения такой библиотеки,
оценивается по формуле:
				/в **т п C a rd 8				га©
				О
/77 - среднее число байтов, требуемое для описания одного
образа;
^ - число		образов.
Основным		недостатком таким образом организованной биб-

7 4

лиотеки, затрудняющим ее использование в интегрированной си­ стеме „проектирования, является трудность редактирования биб­ лиотеки и в частности добавления новых образов в описания библиотечных элементов. Кроме того, для описания исходных данных для проектирования ПП необходимо иметь распечатку дополнительного документа - каталога файлов. Заметим также, что множество В содержит избыточные данные, так как раз­ ные библиотечные элементы могут иметь совпадающие образы.

Рассмотрим модель системной библиотеки, в которой по­

мимо множества	В задано биективное отображение	» в
Это отображение	будем называть каталэговым. Тогда пара

будет называться каталогом библиотеки В . Наличие каталога позволяет для определения библиотечных образов эле­ ментов с С I задавать только отображение Пусть произвольный библиотечный образ. Применим к нему следую­ щее преобразование: если несколько элементов

= 1, ... С) имеют совпадающие образы fyC4jK) j заменим все описания этих образов, кроме одного, ссылками на этот образ.

Среди всех	Aj имеется	по крайней мере одно множество
= $,(Ю,апя	кэтэрогэ	при i f f ^.Таким А„ яв-

ляется множество номиналов. Естественно в таком случае сде­ лать номинал ЭРЭ ключом для поиска образов ЭРЭ в библио­

теке В . Для этой цели будем		считать номинал элементом мно­
жества я , исключив	множество Ам из библиотеки^?,		Тогда
отображение/-*^5»	ставящее	в соответствие заданному	на

Г1ЭС или ПП ЭРЭ его номинал, задается перечнем элементов Г1ЭС и может быть введено в соответствующие модели ПЭС

или ПП.				Care/Aj
Обозначим		через			число		описаний различных биб­
лиотечных образов			элементов			С	4 ) ). Тогда число ссы­
лок в Aj	будет равно			CaretR — CarcfAj. Предполагая, что для
каждого	номинала		определены все			библиотечные		образы, имеем:
	.. гг				*
У£?Я (T,CardA. ) *Яя CardЯ+Г ЯА.(Card В- Card А;)
*	£с/	6	*		fa	f f	'	*
Положим,		что		Const			(f$C	тогда, учиты­
вая, что	Caret 8 -		Carets,получим			оценку:
У £ С/?+лЯА)Саг##+(т							CaretА ,	где
*____;		f	п

CarcfA т л (Л CardА^)

i*1

Таким образом, библиотека & с каталогом позво­ ляет избавиться от пополнительного документа (каталога фай­ лов) при описании исходных данных. Недостатком такой орга­ низации является необходимость создания специальных прог­ раммных средств, обеспечивающих увеличение числа хранимых в библиотеке образов. Это объясняется тем, что в библио*оке

должны храниться элементы	j	поэтому соз­
дание нового образа Ап+/ связано	не только с	описанием его
элементов, но и с коррекцией всего	множества	3 и катало-
га

В значительной степени свободной от подобного недостат­ ка является предлагаемая ниже модель системной библиотеки. Представим библиотеку & в виде дизъюнктного объединения

библиотечных образов:

л

В* V А:

>/ J

Заметим, что в множествах Aj присутствуют только описания

образов	f i j	{£ € ./? ),№ совпадающих между собой.				Вместо
отображения уо		будем хранить его проекции				щ
Тогда каталогом			библиотеки	3	будет совокупность
,	Объем занимаемой			памяти при такой организации биб­
лиотеки	оценивается следующим				образом;
	К « Z	т	CaretА; + J2 *А; CaretR
	9		H		6 ~
или с учетом введенных выше обозначений
	/Q ^ /h n		Саг&А + г>ЯА		C a re ts

Сравнивая „эту оценку с оценкой для предыдущей модели, легко видеть, о они одного порядка и отличаются на вели­ чину

г! .e Я3 C a rd /? -К 'n C ardА ,

где	Card/? - общее число элементов, используемых в систе­
ме	проектирования, а /? C ard А ^ 2	CardA^	- общее число
различных библиотечных образов* элементов			4 6 Я.
	«Достоинством предлагаемого метода является независи­
мость библиотечных образов A j ,		обеспечивающая простоту

7 6

пополнения библиотеки. Для включения в библиотеку нового элемента достаточно описать его новые образы

и включить их в множества Ajf,*- jAjK, а также скорректиро­ вать каталог библиотеки. Введение нового образа множества

Att+f не затрагивает множества			Ал	и требует поми­
мо описания элементов А к+f		лишь расширения каталога,				за­
ключающегося в создании нового массива ссылок.
О тображ ение/^1* -^ ставящее			в соответствие ЭРЭ на
ПЭС или ПП его номинал, позволяет по номеру					образа J	най­
ти описание этого	образа для любого элемента				<*‘<5/, При этом
поиск описания J	-го образа	элемента ^ е		в	библиотеке
сводится к вычислению ссылки			Тем самым время пэибка

библиотечного образа меньше, чем в предыдущей модели, где помимо вычисления ссылки необходимо выделить нужный образ' из описания Y c i).

Таким образом, системная библиотека, хранимая во внеш­ ней памяти, позволяет вычислить для любой задачи множество необходимых библиотечных образов элементов множества./ Для этой цели в модель ПЭС или ПП необходимо ввести мно­

жество	номиналов & и отображение/ - ^ ^ / f . При этом множе­
ство /р	и отображение уЮ не должны постоянно храниться в

оперативной памяти. Для каждой задачи известен номер исполь­

зуемого библиотечного образа J л поэтому	доступ к этому об­
разу осуществляется путем отображения	= у7	-> ^

Поскольку для интерактивной работы необходимо хранить тре­ буемы* образы JTjCi) ( £ € / ) в оперативной naMsmi,наибо­ лее целесообразно сформировать из них временную библиотеку

L	и библиотечное	отображение [	Введение библиотеки
L	и отображения	Л позволяет	избежато обращений к систем­

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

для всех 4 ,	ЧТО A j ( 6 * , ) * . . .	L
включается только одно описание	образа.

Заметим» что обобщенный библиотечный принцип, основан­ ный на создании временных библиотек, остается справедливым и в случае, когда для решения задачи требуется хранить в оперативной памяти одновременно несколько образов. В этом случае в описание библиотечного элемента / с L включаются ссылки на соответствующие образы. Этот принцип эбеспечиьа-

7 7

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

Л и т е р а т у р а

1, ОЙХМАН Е.Г., ЗЮЗИН Ю.В., НОВОЖЕНОВ Ю.В. Мо­ дель представления данных в БД интерактивной графической системы, - Электронная техника. Серия 9. Экономика и си­ стемы управления. 1984, N? 1 (5 0 ), с. 4 2 -4 5 .

2. ОЙХМАН Е.Г., ЗЮЗИН Ю.В., НОВОЖЕНОВ Ю.В. Мето­ ды оценки структуры данных в интерактивных графических си­ стемах на СМ ЭВМ. - Автоматизация технического проекти- у звания цифровой аппаратуры. Тезисы докладов Республикан­

ской научно-технической конференции. Каунас, 198 4 , с. 49 -50 .

■3 N A S'H		D. T o p ic s in		D e sig n	A utom ation	D a ­
ta B a s e s .	-	P r o s , of	1 5 - th	D e sig n	A u tom ation	Conf.
L a s V eg as,	N e v a d a ,		J u n e 1 9 7 8 , p.		4 6 3 - 4 7 4 .
4. ЁЛШМН Ю.М, Проектирование печатных плат с исполь­
зованием АРМ-Р. - Обмен опытом в радиопромышленности,
1979, вып.	10.

УДК 5 1 9 .8 :6 8 1 .5 1

ГЕНЕРИРОВАНИЕ ТЕСТ-ЗАДАЧ РАЗРЕЗАНИЯ ГРАФА С ЗАДАННЫМ ОПТИМАЛЬНЫМ РЕШЕНИЕМ

Й.-К.Л. М а т и д к а с , Г.С. П а л у б е ц к и с

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

78

следовании последних очень важной является проблема оценки точности решений! даваемых этими алгоритмами. Такая оцен­ ка возможна! если известно оптимальное значение целевой функции задачи. Для произвольных -задач ето значение может быть определено с помощью точных алгоритмов разрезания. В работе [6] в целях исследования точности двух приближенных алгоритмов был использован алгоритм типа ветвей и границ [3]. Однако подобный подход применим лишь для задач неболь­ шой размерности. Альтернативная схема оценки точности алго­ ритмов решения комбинаторных экстремальных задач опирает­ ся на генерировании специальных тестовых задач с априорно заданным оптимальным решением {и значением) и сопоставле­ нии этого решения с решением, выдаваемым исследуемым при­ ближенным алгоритмом. Реализация такой схемы применитель­ но к задаче-размещения описана в [7], Графы, генерируемые алгоритмом из [7], можно использовать и для оценки точно­ сти алгоритмов разрезания графа на две части. Если множест­ во вершин разбивается на три или более частей, то подобное утверждение уже не имеет места.

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

Пусть G			V -	неориентированный
граф с весами	js a р	е б	р а х f j	разрезаемый на под­
графы ” 6i*(\%9£g9!%/mm		к f t		* порождаемые под­
множествами вершин		Р	(предполагается, что 6* л/т
целое число). Пусть				множество все­

возможных таких разрезаний. Рассматриваемая задача разре­ зания графа заключается в минимизации целевой функции

не	Щ к ,т ) .	ft* .	' £	и
		'	t-irt'K S S X tW se V j
	Обозначим через		оптимальное значение функции ft$6)
на	Тс*ь,к,т) для графа <?. *
	Введем в	рассмотрение также совокупность Tfn^k) произ­

вольных, (т.е. без требования_одинаковой мощности) разбие­

ний множества I/ на		(допускается,
что	для некоторых £ ё { 1 ^ k j j -	Минимальное значение
функции	/чг^йлга rCfitjk) обозначим	через

79

	Следующий результат указывает на достаточно общий ме­
тод отыскания			оценки снизу для		CG).
	Предложение. Пусть G ^ (^ £ )^				полный граф с весами Су
н а М у/)б£		(возможно		для некоторых (i,J))j 6 s- СК Л
S =•		-	подграфы графа Q		с приписанными		ребрами
<V;e ^ BecaM"			<$• Пусть	d j = Oj если (i,j)t£ \ £ s .			Тэга а ес-
ли	£ s*t cij *Cijj			, го j £	ГЛС& Sr ZC6J.
	Доказательство. Элементарно."
^	В частности, мож! о выбрать G?j					такими, что
f\>(G*)= £(GV=Oj S~ fj C l - Тогда £CG eJ & F?(6)* На						основании дач­

ного предложения построены конкретные алгоритмы нахожде­ ния нижней оценки значения оптимума в задаче разрезания графа. Они опираются на операции выделения полных подгра­ фов (в качестве (5^ множество вершин каждого из которых разбито на два подмножества. При этом ребра, со­ единяющие вершины из разных подмножеств, имеют положи­ тельный вес, а остальные ребра - отрицательный.

На базе сформулированного предложения разработана так­ же достаточно общая схема формирования тест-задач разреза­ ния графа с априорно заданным оптимальным решением. Ее можно представить в следующем виде.

1°. Фиксировать допустимое разбиение С ^(^jC^^k)€T(nfkp)

множества вершии К			Положить f i =0;Cy:=o,	К i+ j '
(для	простоты здесь и в дальнейшем принимается,			что Су и
Cjtjtejjобозначают			одну и ту же величину - вес	ребра
	6>	Используя некоторую процедуру выбрать полный под­
граф		с весами с у на ребрах, удовлетворяющий следу­

ют л требованиям:

а)

б) Ч	;& )	где	t s fq /? 7 , t = r,*jeroP /, к)}
		где
		г* О.	то с у $ О)если для
			П олОЖИТЬ С	у : ~ С у + C i j П ОЛ 0-
жить / ;= /+ / ?	CGJ.
4°. Вернуться к 2 °		либо перейти к 5° в		зависимости от
некоторого правила.

	5 Э Определить Лш/min d j /. Положить Ci/:=Cty+h,V(i.jJ( £■
Ее	6°. Генерировать случайную перестановку р = (?<?/,..>,рел)),
	элементы обозначают вершины полного графа	Вес реб­
ра	этого графа равен Су.

8 0