График - изображение переходного смыкания для планировки общих перекрытий

Министерство  образования РФ

Уфимский  государственный  авиационный технический  университет 
 

                                                                     
 
 
 
 

Кафедра ВМиК

                                                          

                                                              
 

 

Реферат

на тему: ГРАФИК-ИЗОБРАЖЕНИЕ ПЕРЕХОДНОГО  СМЫКАНИЯ ДЛЯ ПЛАНИРОВКИ ОБЩИХ ПЕРЕКРЫТИЙ. 
 
 
 

Выполнил

Студент гр. МИЭ-320

Стрельцов М.А.

Проверил:

Д.Т.Н. кафедры ВМиК

Мухачева  Э.А. 
 
 
 
 
 

Уфа 2004 
 

ГРАФИК-ИЗОБРАЖЕНИЕ ПЕРЕХОДНОГО СМЫКАНИЯ ДЛЯ ПЛАНИРОВКИ ОБЩИХ ПЕРЕКРЫТИЙ.

. 
 

Введение. 

  В  данном тексте мы представляем  идею Р*- допустимого изображения  и предлагаем Р*-допустимый график  переходного смыкания- базовое изображение  для общей планировки перекрытий, названный ГПС (TSG), а также показываем его превосходные характеристики. ГПС сочетает преимущества известных изображений, таких как чередование пар, ОСС (BSG)  и В*- ось (древо). Подобно чередованию пар и ОСС, но в отличии от О-оси, В*-оси и ПУБ (CBL), ГПС не требует создания дополнительных  графиков сдерживания для определения стоимости в процессе упаковки, предполагая более быстрое время эксплуатации. ГПС способствует возрастающему модернизированию в процессе работы и содержит информацию о пограничных модулях, а также формы и относительные местонахождения модулей в изображении. Наиболее важно то, что геометрическое соотношение между модулями понятно не только в изображении ГПС, то также в его практическом применении, что облегчает схождение к желаемому решению. Все эти свойства придают изображению ГПС эффективность и гибкость для решения проблем с различными реакциями связи в процессе общего конструирования и размещения перекрытий. Результаты экспериментов показывают ГПС многообещающим. 

ГПС. 
 

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

   В этом тексте мы предлагаем изображение  переходного смыкания, основанное на графике для общих неслоёных  конструкций перекрытий, именуемое ГПС, и показываем его превосходные характеристики. В ГПС используются диаграммы горизонтального и вертикального смыкания, Ch  и Cv, для описания горизонтальных и вертикальных соотношений каждой пары модулей. В Ch (Cv)  на рисунке 1 (b), например, край от модуля x  к модулю y показывает, что x – левее (ниже) по отношению к y. ГПС- первое изображение, которое может искажаться точно на графиках (без оси) и гарантировать выполнимое решение на каждое искажение. 
 

     

Рис.1 (а) – Некомпактное размещение, которое не может быть изображено с помощью любой О-оси. (b)- Изображение графика переходного смыкания (ГПС) для размещения, показанного в (а). 

Чтобы отличать характеристики ГПС от других существующих изображений мы расширяем в этом тексте концепцию Р-допустимого изображения до варианта Р*-допустимого путём добавления условия (5):

.

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

(5)  геометрическое соотношение между каждой парой модулей определяется в изображении. 

Среди существующих известных изображений  ЧП, ОСС и ГПС являются Р*-допустимыми, в то время как слоёные оси, СПВ, О-оси, В*-оси и ПУБ таковыми не являются. Слоёные оси, СПВ и ПУБ не являются Р-допустимыми и, соответственно, Р*-допустимыми. Изображения, основанные на оси, нарушают оба пятые условия Р*-допустимости. Недостаточность (в результате чрезмерного упрощения изображений) влечёт за собой следующие препятствия:

- Некоторые  геометрические соотношения между  модулями не могут выполняться  непосредственно из О-оси и  В*-оси , что усложняет использование  О-оси и В*-оси для решения  конструкторских проблем , связанных с вышеупомянутыми дополнительными требованиями. На Рисунке 2 (а) показано компактное размещение с пятью модулями a,b,c,d и e, широта и высота которых составляет (6,4), (4,6), (7,4), (6,3) и (3,2) соответственно. Как показано на рисунках, мы не можем получить какого-либо геометрического соотношения между двумя модулями из О-оси и В*-оси до тех пор, пока две соответствующие точки пересечения- родственные или находятся на одном пути. Например, даже хотя модуль b примыкает к модулю d, мы не можем достичь какого-либо геометрического соотношения непосредственно из изображений до тех пор, пока не выполнена упаковка. Далее, геометрическое соотношение между двумя модулями для одинаковой О-оси и В*-оси может изменяться, если изменяются размеры модулей. Например, если размер модуля b изменяется до (1,6), модуль d остаётся справа от модуля  b после упаковки, как показано на Рисунке 2 (d), вместо того чтобы быть над b как в Рисунке 2 (а) (для той же О-оси, показанной на Рисунке 2(в)). Несовпадение неизбежно усложнит процесс конструирования перекрытия. 

 

Рисунок 2. (а)- Размещение. (b)- Соответствующая О-ось. (c)- Соответствующая В*-ось. (d)-Размещение после упаковки, если размеры модуля b изменяются до (1,6). (e)- О-ось- производная от размещения (d). 

Кроме того, для калибровки модуля лучше сохранять геометрическое соотношение между каждой парой модулей в изображении для предотвращения перекрывания неизмеренного модуля другими модулями. Кроме того, управлять пограничными и симметричными модулями с помощью осевого изображения сложнее. Кажется, что  nb означает правый пограничный модуль  для О-оси, показанной на Рисунке 2 (b), поскольку на правой стороне нет точек пересечения. Однако, модуль b может и не быть правым пограничном модулем в конечном размещении, как показано на Рисунке 2(d). Что касается симметричных ограничений,то несколько пар модулей следует размещать симметрично относительно общей оси, а координаты x  или y модулей должны бытии одинаковыми. Предпочтительно соблюдать геометрическое соотношение между модулями в изображении чтобы упростить проектирование и размещение перекрытий с симметричными модулями.

-  В результате уплотнения О-ось  (древо) и В*-ось (древо) после  упаковки могут не соответствовать  оригиналу, что может повредить  структуру решения (соседнюю), а также приведение к оптимальному решению. После упаковки, к примеру, изначальная О-ось на Рисунке 2 (b) станет результатом размещения, показанного на Рисунке 2 (d), что соответствует уже другой О-оси на Рисунке 2 (е).

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

Напротив, ГПС сочетает преимущества ЧП, ОСС  и В*-оси. Подобно ЧП и ОСС, но в  отличии от О-оси, В*-оси и ПУБ, ГПС удовлетворяет пяти условиям Р*-допустимости:

1. его разрешающая поверхность – (m)2 и поэтому – конечна, где m-число модулей,
2. каждое разрешение выполнимо (заметьте, что ПУБ не гарантирует такой характеристики),
3. упаковка и расчёт стоимости могут выполняться в течение О (m2) времени,
4. упаковка на разрешающей поверхности, оцененная наилучшим образом, соответствует оптимальному расположению,
5. геометрическое соотношение между каждой парой модулей обозначено в изображении ГПС.

 

Разрешающая поверхность та же, что и ЧП, но объём памяти меньше, поскольку нам  нужно установить последовательность пар. Подобно В*-оси, но в отличии  от ЧП, ОСС, О-оси и ПУБ, ГПС не нуждается в создании дополнительных ограничительных графиков для определения стоимости в процессе упаковки, предполагая ускоренный темп выполнения работы. Далее, ГПС способствует непрерывной модернизации в процессе эксплуатации и сохраняет информацию о пограничных модулях, а также форму и относительные расположения модулей на схеме. Более важно то, что геометрическое соотношение между модулями очевидно не только в изображении ГПС, но также в процессе его эксплуатации (т.е. эффект от изменения геометрического соотношения известен до упаковывания), что облегчает стремительное схождение к желаемому решению и размещению вместе с ограничителями. Например, как показано на Рисунке 1, точка с нулевой отметкой  в градусе (из градуса) в горизонтальном фазово-импульсном векторе Сh соответствует левым (правым) пограничным модулям, а точка с нулевой в градусе (из градуса) отметкой на вертикальном фазово-импульсном векторе Сv соответствует нижним (верхним) пограничным модулям. Очевидность геометрического соответствия между модулями выделяет ГПС из числа других изображений для управления размещением с позиционными ограничителями. Все эти характеристики делают изображение ГПС гибким и эффективным для решения проблем, возникающих с выполнением различных требований в процессе конструирования и размещения перекрытий. Эксперименты с ГПС оправдали все ожидания. Для оптимизации площади ГПС достиг улучшений в среднем на 2.22%, 2.04%, 1.18% и 3.54%,  в сравнении с О-осью, повышенной О-осью, В*-осью и  ПУБ соответственно. Найдя наиболее выгодную длину провода, ГПС достигает значительных улучшений в среднем на 3.56% и 3.18% в сравнении с О-осью и повышенной О-осью. (Примечание. В*-ось и ПУБ- единственные, кто не доложил о результатах  определения наиболее выгодной длины провода.) Требования по эксплуатации у ГПС значительно ниже, чем у О-оси и В*-оси и они совместимы с повышенной О-осью. 
 
 
 

ХАРАКТЕРИСТИКИ  ГПС.

Свойство1.( Условия выполнимости ГПС). Выполнимый ГПС обладает тремя следующими

характеристиками:

1. Сh и Cv – ацикличны.
2. Каждая пара точек должна соединяться точно одним краем, или  в Сh, или в Сv.
3. Переходное смыкание Сh (Cv) равно самому  Ch (Cv).

 

Основываясь на характеристиках ГПС, мы получаем следующие теоремы.

Теорема 1: Существует уникальное местоположение, соответствующее ГПС.

Теорема 2: Размер разрешающей поверхности для ГПС равен (m!)2, где m- число модулей.

Теорема 3: ГПС является Р*-допустимым.

В Таблице 1 мы подвели объединили характеристики, собранные из недавно опубликованных изображений неслоёных перекрытий. 

РЕЗУЛЬТАТЫ  ЭКСПЕРИМЕНТОВ.

Основываясь на методе искусственного обжига, мы создали изображение ГПС на программном языке  С++ на установке SUN Sparc Ultra-60 при частоте 433 MHz и объёмом памяти 1 GB.

 Мы  сравнили ГПС с О-осью, В*-осью, увеличенной О-осью  и ПУБ, основываясь на исходных данных пяти цепей MCNC, перечисленных в Таблице II. В колонках 2,3,4 и 5 Таблицы перечислены числа модулей, номера изолированных монтажных поверхностей I/O, сеток и шифтов пяти цепей.

Экспериментальное исследование состоит из трёх частей: оптимизация площади, оптимизация длины провода, а также одновременная оптимизация площади и длины провода. Площадь размещения измеряется минимальностью ограничивающей коробки, закрывающей размещение. Площадь и время эксплуатации сравниваются в О-оси,  В*-оси, увеличенной О-оси, ПУБ, и ГПС и перечисляются в Таблице III. Как показано в Таблице III, ГПС достигает среднего улучшения в использовании площади на 2.22%, 1.18%, 2.04% и 3.54%  в сравнении с О-осью, В*-осью, увеличенной О-осью и ПУБ соответственно. Время эксплуатации значительно меньше, чем в О-оси и В*-оси и сравнимо с увеличенной О-осью.        

Для оптимизации длины провода мы вычислили длину провода одной  сетки по половине периметра минимальной  ограничивающей коробки, закрывающей сетку. Сравнение с предыдущими работами даётся в Таблице IV. (Заметьте, что только В*-ось и ПУБ не доложили результаты по оптимизации длины провода.) Как показано В таблице IV, ГПС достигает средних уменьшений длины провода на 3.56% и 3.18% в сравнении с О-осью и увеличенной О-осью соответственно. На Рисунке 7 (справа) показаны результаты размещения ami49 с оптимизированной длиной провода. Для одновременной оптимизации площади и длины провода мы назначаем для площади и длины провода одинаковую массу в ценовой категории.