авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |

«Конспект лекций 3 А. И. Власов, Л. А. Зинченко, В. В. Макарчук, И. А. Родионов АВТОМАТИЗИРОВАННОЕ ...»

-- [ Страница 2 ] --

7. Выступ топологического элемента B по отношению к элементу A – расстояние от внутренней стороны фигуры В, не принадле жащей области пересечения указанных элементов, до ближай шей внешней стороны фигуры А, ограничивающей область их взаимного пересечения (рис. 1.19). Аналогично определяется вы ступ топологического элемента A по отношению к элементу В.

Область Выступ В перекрытия Выступ А А В Рис. 1.19. Ограничение «Выступ»

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

Таблица 1. Пр и м ер о пр е де л е ни я т и по в то по ло г иче с ки х с тр ук т ур Обозначение топологи Описание топологической структуры ческих структур Топологический элемент из слоя CNT, COMPCNT охваченный элементом из слоя COMP Область топологического элемента из слоя N-COMP COMP, перекрытая элементом из слоя NP Топологический элемент из слоя CNT, N-COMPCNT охваченный элементом из структуры N-COMP Область топологического элемента из слоя P-COMP COMP, перекрытая элементом из слоя PP Топологический элемент из слоя CNT, P-COMPCNT охваченный элементом из структуры P-COMP Область перекрытия топологического элемента GATE из слоя POLY элементом из слоя COMP Переходной контакт – топологический элемент PDV из слоя V1, охваченный элементом из слоя PD Переходной контакт – топологический элемент PDV из слоя V2, охваченный элементом из слоя PD Переходной контакт – топологический элемент PDV из слоя V3, охваченный элементом из слоя PD Топологический элемент из слоя CNT, POLYCNT охваченный элементом из слоя POLY Топологический элемент M1, ширина и длина WIDE_M которого больше 10 мкм Топологический элемент M2, ширина и длина WIDE_M которого больше 10 мкм Топологический элемент M3, ширина и длина WIDE_M которого больше 10 мкм Топологический элемент M4, ширина и длина WIDE_M которого больше 10 мкм 52 Автоматизированное проектирование наносистем На последующих этапах эти топологические структуры исполь зуются для определения конструктивно-технологических ограни чений. Количество типов топологических структур определяется требуемым набором правил проектирования.

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

Активными элементами являются:

n-канальный МДП-транзистор;

p-канальный МДП-транзистор.

К пассивным элементам можно отнести:

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

диоды на различных структурах («P-COMP»–NW, NW–PW и т. п.).

К вспомогательным конструктивным элементам можно отнести:

контакты к n-карманам – конструкции «N-COMP»– «N-COMPCNT»–«M1», расположенные внутри топологиче ского элемента NW (рис. 1.2.8).

N-COMP POLY P-COMP M1 NW Vdd p-МДП- Контакт транзистор к n-карману Сток Исток N-COMP P-COMP P-COMP NW Рис. 1.20. Формирование контактов к n-карманам контакты к p-карманам – конструкции «P-COMP»– «P-COMPCNT»–«M1», расположенные внутри топологиче ского элемента PW (рис. 1.21);

фигуры заполнения – дополнительные топологические эле менты, предназначенные для обеспечения необходимой плот ности заполнения (рис. 1.22);

вырезы в шинах металлизации для предотвращения их разрыва при тепловых напряжениях.

Конспект лекций N-COMP POLY P-COMP M1 NW Vss n-МДП Контакт транзистор к p-карману Исток Сток N-COMP N-COMP P-COMP PW Рис. 1.21. Формирование контактов к p-карманам Рис. 1.22. Фигуры заполнения Помимо приведенных выше в данном разделе устанавливается шаг координатной сетки проектирования, разрешенные углы топо логических фигур (обычно 90 и 135), шаг сетки оценки плотно сти заполнения и т. п.

Плотность заполнения топологического слоя обычно рассчиты вается по следующему алгоритму: сначала вся топология разбива ется на прямоугольники заданного размера, далее оценивается ло кальная плотность заполнения внутри каждого прямоугольника и рассчитывается средняя (интегральная) плотность заполнения все го слоя. Шаги сетки оценки плотности заполнения по осям X и Y равны соответствующим сторонам прямоугольников, на которые разбивается вся топология.

3. Правила выполнения топологических слоев и приборов ядра кристалла В данном разделе на примере масштабируемых правил проек тирования изложены правила выполнения топологических слоев и приборов ядра кристалла для технологического процесса с про 54 Автоматизированное проектирование наносистем ектными нормами 0,35 мкм одним уровнем поликремния и че тырьмя уровнями металлизации, используемыми компанией TSMC.

Данные правила проектирования являются открытыми и доступны на сайте www.mosis.com.

Для них определены следующие основные проектные тополо гические слои (табл. 1.9).

Таблица 1. Ос но в н ые пр о е к т ны е т о по ло г и чес к ие с ло и Название № слоя Обозначение Комментарий слоя в GDS-файле в CIF-файле 1 2 3 N_WELL 42 CWN Области n-карманов Области формирования ACTIVE 43 CAA приборов THICK_ 60 CTA Не обязательный слой ACTIVE Области поликремниевых POLY 46 CPG затворов и поликремниевой разводки SILICIDE_ 29 CSB Области салицидирования BLOCK N_PLUS_ Области n+-имплантации 45 CSN SELECT P_PLUS_ Области p+-имплантации 44 CSP SELECT Области контактов CONTACT 25 CCC к карманам Области контактов к поли POLY_ кремнию, слой не может быть 47 CCP CONTACT заменен объединенным слоем контактов Области контактов к стокам/ ACTIVE_ истокам, слой не может быть 48 CCA заменен объединенным слоем CONTACT контактов Области металлизации METAL1 49 CM 1-го уровня Области переходных межсое VIA 50 CV1 динений между 1-м и 2-м уровнями металлизации Области металлизации METAL2 51 CM 2-го уровня Области переходных межсое VIA2 61 CV2 динений между 2-м и 3-м уровнями металлизации Конспект лекций Окончание табл. 1. 1 2 3 Области металлизации METAL3 62 CM 3-го уровня Области переходных межсое VIA3 30 CV3 динений между 3-м и 4-м уровнями металлизации Области металлизации METAL4 31 CM 4-го уровня Области вскрытия окон GLASS 52 COG к контактным площадкам Слой, который используется для выделения контактных PADS 26 XP площадок (не используется при производстве ИС) Comments – CX Cлой для комментариев Слой «THICK_ACTIVE» используется только для процессов, в которых требуется применение транзисторов с различной тол щиной подзатворного диэлектрика. Обычно он используется для создания транзисторов, работающих на разных уровнях напряже ния. Для таких процессов слой «ACTIVE» используется для обо значения активных областей всех транзисторов, независимо от толщины подзатворного окисла. А слой «THICK_ACTIVE» исполь зуется только для того, чтобы выделить области формирования транзисторов с более толстым подзатворным окислом.

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

Правила проектирования областей формирования приборов (активных областей) Не допускается применение топологических элементов ACTIVE, не охваченных топологическими элементами NPLUS или PPLUS.

Типовое описание правил проектирования для данного топологи ческого слоя представлено в табл. 1.10.

56 Автоматизированное проектирование наносистем Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля то по ло г ичес ко го с ло я № пра- Значение Описание вила (в единицах ) 1.1 Минимальная ширина элемента 1.2 Минимальный зазор между элементами Минимальное расстояние от стока/истока 1.3 до границы кармана Минимальное расстояние от контакта 1.4 к стоку/истоку до границы кармана Минимальный зазор между не граничащими активными областями с различным типом 1.5 имплантации. Граничащие активные области будут рассмотрены в правилах проектирования областей имплантации 1. Active Active 1. 1.2 Active n-plus-select p-plus-select 1. 1. p-region n-region 1. 1. 1.5 Active 1.1 Active Active 1. n-plus-select p-plus-select Рис. 1.23. Расчетная схема правил проектирования для топологического слоя Ограничения на правила 1.1 и 1.2 связаны с возможностями процессов литографии и травления, а также качеством изолирую щего окисла между активными областями, который должен обес печивать минимизацию различного рода влияния и паразитных связей между различными активными элементами.

Конспект лекций Ограничения на правила 1.3–1.5 связаны с процессами диффу зии легирующей примеси в близлежащие области во время раз личных термообработок в течение технологического процесса из готовления ИС.

Правила проектирования областей n-карманов Типовое описание правил проектирования для данного тополо гического слоя представлено в табл. 1.11.

Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля то по ло г ичес ко го с ло я № пра- Значение Описание вила (в единицах ) 2.1 Минимальная ширина элемента Минимальный зазор между карманами 2.2 под разными потенциалами Минимальный зазор между карманами 2.3 под одним потенциалом Минимальный зазор между карманами 2.4 различных типов 2.2 2. N_well N_well N_well 2. 2. P_well Рис. 1.24. Расчетная схема правил проектирования для топологического слоя Ограничение на правило 2.2 обусловлено необходимостью обеспечения заданного для данной технологии уровня пробивного напряжения между карманами. Между карманами под разными потенциалами возникает существенная разность потенциалов, ко 58 Автоматизированное проектирование наносистем торая может стать причиной пробоя, поэтому между ними увели чивают слой изолирующего диэлектрика.

Ограничение на правило 2.4 вызвано тем, что для различных технологий слой «P_well» часто получают прямой инверсией слоя «N_well», соответственно зазор между ними отсутствует.

Правила проектирования областей затворов МДП-транзисторов и поликремниевой разводки Типовое описание правил проектирования для данного тополо гического слоя представлено в табл. 1.12.

Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля то по ло г ичес ко го с ло я № пра- Значение Описание вила (в единицах ) 3.1 Минимальная ширина элемента Минимальный зазор над областями изолирующего 3.2 диэлектрика Минимальный зазор над активными областями 3.2a (между затворами) 3.3 Минимальный вылет затвора за активную область 3.4 Минимальный вылет активной области от затвора Минимальное расстояние от поликремниевой 3.5 шины, лежащей на изолирующем диэлектрике, до активной области 3. Active Poly 3. 3. 3. Poly 3. Active Рис. 1.25. Расчетная схема правил проектирования для топологического слоя Конспект лекций Ограничения на правила 3.1, 3.2 и 3.2а являются определяю щими для любой КМОП-технологии, так как задают минимально допустимые размеры элементов ИМС, и всегда определяются воз можностями литографического процесса.

Ограничение на правило 3.4 вызвано сокращением длины затво ра со стороны свободного края при операции литографии. Это со кращение приводит к уменьшению длины канала МДП-транзистора «на вылете» затвора за активную область, что вызывает резкое изме нение электрических характеристик МДП-транзисторов от заданных.

Dпол Dном Рис. 1.26. Оценка минимального вылета затвора за активную область и активной области от затвора Существует два метода борьбы с данным эффектом:

1. Введение фигур коррекции.

2. Увеличение вылета затвора за активную область транзистора на величину, учитывающую сокращение длины.

Второй метод приводит к увеличению габаритных размеров элемента и тем самым к снижению степени интеграции СБИС.

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

Правила проектирования высоколегированных n+- и p+-областей Типовое описание правил проектирования для данного тополо гического слоя представлено в табл. 1.13.

60 Автоматизированное проектирование наносистем Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля то по ло г ичес ко го с ло я № пра- Значение Описание вила (в единицах ) Минимальный зазор между областями 4.1 n+- (p+)-имплантации и каналами транзисторов Минимальное перекрытие активной области 4.2 областью n+- (p+)-имплантации Минимальное перекрытие области контакта 4.3 к стоку/истоку областью n+- (p+)-имплантации Минимальные ширина элемента и зазор между ними (области n+- и p+-имплантации могут 4.4 соприкасаться, но не должны перекрываться) p+_Select* 4. t ac nt Co 4. 4. Poly 4. Active + n _Select* Рис. 1.27. Расчетная схема правил проектирования для топологического слоя Ограничение по правилу 4.1 необходимо для обеспечения тре буемой минимальной ширины стока/истока.

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

Правила проектирования контактных окон к активным областям и затворам МДП-транзисторов Для технологических процессов с проектными нормами 0,5 мкм и ниже необходимо выполнять контактные окна в виде стандартных Конспект лекций фигур одного размера. Большие области контактов должны разби ваться на массивы стандартных фигур. Контактные окна должны быть нарисованы ортогонально сетке проектирования топологии.

Типовое описание правил проектирования для слоя контактных окон к области поликремния представлено в табл. 1.14.

Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля с ло я ко н та к т ны х о ко н к о б лас т и по л и кр е м н и я № пра- Значение Описание вила (в единицах ) 5.1 Точный (разрешенный) размер контактного окна 5.2 Минимальное перекрытие слоем поликремния 1, 5.3 Минимальный зазор между контактными окнами 5.4 Минимальное расстояние до затвора транзистора Active 5. 5. 5. ct nta Co Poly 5. Рис. 1.28. Расчетная схема правил проектирования для слоя контактных окон к области поликремния Типовое описание правил проектирования для слоя контактных окон к активной области представлено в табл. 1.15. Контактные окна должны быть нарисованы ортогонально сетке проектирова ния топологии.

Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля с ло я ко н та к т ны х о ко н к а к т ив но й о б ла с ти № пра- Значение Описание вила (в единицах ) 6.1 Точный (разрешенный) размер контактного окна Минимальное перекрытие слоем ACTIVE 6.2 1, 6.3 Минимальный зазор между контактными окнами 6.4 Минимальное расстояние до затвора транзистора 62 Автоматизированное проектирование наносистем 6. 6. 6. ct ta n Co Active 6. Poly Рис. 1.29. Расчетная схема правил проектирования для слоя контактных окон к активной области Контактные окна разделены на два отдельных топологических слоя, так как в общем случае режимы литографии и травления для них отличаются (они обеспечивают контакт к топографически раз ным уровням).

Правила проектирования топологии слоев металлической разводки и межсоединений Типовые правила проектирования топологии слоев металлизи рованной разводки и межсоединений всех уровней аналогичны. Пра вила проектирования первого слоя металлизации (наиболее кри тичного из всех слоев межсоединений) представлены в табл. 1.16.

Ограничения по правилу 7.3 связаны с возможностями лито графического оборудования в отношении точности совмещения двух топологических слоев.

Переходные окна должны быть нарисованы ортогонально сетке проектирования топологии. Типовое описание правил проектиро вания для первого слоя переходных окон к области поликремния представлено в табл. 1.17.

Таблица 1. Пр а ви л а пр о е к т ир о в а н и я пер во го с ло я м е та л л из ац и и № пра- Значение Описание вила (в единицах ) 7.1 Минимальная ширина элемента 7.2 Минимальный зазор между элементами Минимальное перекрытие области любого 7.3 контакта Минимальное расстояние между шинами метал 7.4 лизации, если ширина шины составляет более Конспект лекций Active 7. 7.1 Metall 7. Poly t ac Metall nt Co Рис. 1.30. Расчетная схема по правилам проектирования первого слоя металлизации Таблица 1. Т ипо во е о п ис а н ие пр а в и л пр о е к т ир о в а н ия д ля п е р во го с ло я пер е х о д ны х о ко н к о б лас т и по л и кр е м н и я № пра- Значение Описание вила (в единицах ) 8.1 Точный (разрешенный) размер 8.2 Минимальный зазор между переходными окнами Минимальное перекрытие слоем MET 8.3 8.4 Минимальное расстояние до контактного окна Минимальное расстояние до шины поликремния 8.5 или активной области Poly Active 8.5 8. 8.4 ct 8. nta Via Via Via Co Metall 8. 8.5 8. Active Рис. 1.31. Расчетная схема по правилам проектирования для первого слоя переходных окон к области поликремния Правила по плотности заполнения слоев ИМС Фигуры заполнения обычно используются только для слоев ACTIVE, POLY и всех слоев металлизации, т. е. тех слоев, после соз дания которых необходимо проведения процесса ХМП.

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

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

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

Заполнение осуществляется прямоугольными фигурами с задан ными размерами и заданным расстоянием между соседними фигу рами. Помимо этого в правилах проектирования задается мини мальное расстояние между рабочими топологическими элемента ми и фигурами заполнения.

4. Правила проектирования периферийных областей кристалла, контактных площадок и широких шин металлизации В данной части правил проектирования изложены правила вы полнения контактных площадок, периферийного контура и широ ких шин в слоях MET1, MET2, МЕТ3 и MET4 (выполнение этих правил предотвращает от разрывов в шинах металла при тепловых напряжениях), а также правила выполнения широких шин в углах кристалла.

1.3. МЕТОДОЛОГИЯ ТОПОЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ОБЪЕКТОВ НАНОИНЖЕНЕРИИ 1.3.1. ОБЩИЕ СВЕДЕНИЯ О МЕТОДОЛОГИИ ТОПОЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ ОБЪЕКТОВ НАНОИНЖЕНЕРИИ Как уже было сформулировано выше, задача топологического проектирования объектов наноинженерии представляет собой одну из комбинаторных задач. Эту проблему будем рассматривать применительно к проектированию топологии СБИС, составляю щих в настоящее время бльшую часть объектов наноинженерии.

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

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

1.3.2. УПРОЩЕННОЕ ПРОЕКТИРОВАНИЕ ТОПОЛОГИИ Поскольку в настоящее время согласно действующему закону Мура происходит непрерывное увеличение степени интеграции СБИС (в два раза за каждые 18 месяцев), то эта тенденция вполне согласуется с тенденциями к повышению эффективности элек тронной аппаратуры и снижению ее стоимости. Сейчас можно по лагать, что она будет продолжаться до тех пор, пока будет наблю даться прогресс в тех направлениях, которые поддерживают раз витие микроэлектронных технологий.

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

В области топологического проектирования – этапа, который, как уже было сказано выше, представляет собой узкое место про цесса создания СБИС, – производятся исследования, направлен ные на создание новых методов топологического проектирования, которые будут рассмотрены ниже в связи с общими методами по строения и проектирования СБИС.

Использование структуры ЗУ. Если допустить, что ПЗУ представляет собой «черный ящик», входами которого: являются линии выборки слов, а выходами – разрядные линии, то ПЗУ, очевидно, можно будет рассматривать как своеобразную комби национную логическую схему. Подав на один из входов ПЗУ возбуждающий сигнал, на его выходах можно получить сигналы, соответствующие содержимому слова, выбранного в ПЗУ. Дру гими словами, логические значения сигналов на каждом из выхо дов представляют собой логические величины, хранимые в раз рядах, соответствующих выбранному слову. Следовательно, ус тановив посредством дешифратора соответствие между линиями выборки слов и комбинацией переменных на входах и воспользо вавшись одним ПЗУ ( 2m n бит), логическую функцию с m вхо дами и n выходами можно реализовать в виде схемы. Так, на пример, логические функции:

f1 = x1 x2 x3 + x1 x2 x3 ;

f 2 = x1 x2 x3 + x2 x3 ;

f3 = x1 x3, – можно реализовать схемой со стандартной структурой, представ ленной на рис. 1.32. Для того чтобы получить относительно слож Конспект лекций ный выходной сигнал путем комбинирования состояний на срав нительно небольшом количестве входов, и с физической точки зрения и с точки зрения проектирования зачастую целесообраз нее использовать не вентильные структуры, а ПЗУ.

x1 x2 x3 f1 f2 f 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 a x x Дешифратор x VDD f VDD f f б Рис. 1.32. Представление логических функций в ПЗУ:

а – таблица истинности;

б – структура базисной схемы Если возбуждающие сигналы одновременно подаются на две или более линии выборки слов ПЗУ, не имеющего дешифратора, 68 Автоматизированное проектирование наносистем то на разрядных линиях появляются суммы битов, хранимых в раз рядах, соответствующих двум или более выбранным словам. Сле довательно, установив однозначное соответствие между несколь кими логическими переменными, с одной стороны, и шинами вы борки слов – с другой, можно, записывая в ПЗУ «1» или «0», реализовать произвольные суммы указанных переменных. ПЗУ, используемое в структуре такого типа, называется матрицей «ИЛИ». Если каждый вход и выход этой структуры соединить с инвертором, то можно получить логическое произведение:

x1 + x2 + … + xn = x1 x2 … xn.

В этом случае ПЗУ называется матрицей «И». Поскольку все логические функции могут быть, представлены в форме сумм, произведений, то, объединив матрицы «И» и «ИЛИ», любую логи ческую функцию можно реализовать посредством такой схемы.

Устройство, которое позволяет реализовать заданные матрицы в виде одной СБИС, а затем зафиксировать их содержание в процессе ее изготовления (или по его окончании), называется программируе мой логической матрицей (ПЛМ). Так, например, логические функции:

f1 = x1 ;

f 2 = x1 + x1 x2 x3 ;

f3 = x2 x3 ;

f 4 = x1 x2 x3 + x1 x2 x3, – могут быть реализованы посредством схемы (рис. 1.33).

Схемы, представленные на рис. 1.32 и 1.33, в сущности пред ставляют собой схемы памяти и соответственно имеют регуляр но повторяющуюся структуру. На практике при реализации ло гической схемы с помощью ПЗУ или ПЛМ процедуры разработ ки топологии в части определения местонахождения блоков и соединений между ними не требуется. Такая ситуация вполне отвечает целям снижения стоимости проектирования СБИС.

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

ПЛМ и ПЗУ могут быть эффективно использованы при реали зации комбинационных схем. Вместе с тем известны методы про Конспект лекций ектирования последовательностных схем, также предусматриваю щие использование матричных структур. Такие схемы называются программируемыми логическими матрицами с памятью. По существу, это схемы, объединяющие матрицу «И» и матрицу «ИЛИ». Элементы матриц содержат триггеры. Эффективные ме тоды автоматического формирования структуры в настоящее вре мя не разработаны, однако в будущем можно ожидать отказ от применения произвольной логики с вентилями и триггерами и пе реход к стандартным СБИС.

Матрица «И» Матрица «ИЛИ»

VDD VDD x x2 x x1 x2 x x1 x2 x f1 f2 f3 f x x1 x Рис. 1.33. Представление логических функций в ПЛМ При реализации функций всего кристалла СБИС посредством ПЛМ эффективность использования вентилей оказывается недос таточно высокой. Однако тот факт, что многие области, которые должны быть заняты элементами произвольной логики, можно ис пользовать с помощью ПЛМ, возможно, следует рассматривать как основу проектирования с ориентацией на память. В 32-раз рядном однокристальном микропроцессоре фирмы Hewlett-Packard (США), основная часть площади кристалла занята ПЗУ и ПЛМ.

Глубокого внимания заслуживает и то обстоятельство, что разрыв по степени интеграции между микропроцессорами, с одной сторо ны, и ЗУ, с другой стороны, сокращается с каждым годом. Это обусловлено тем, что год от года удельный вес ЗУ в микропроцес сорах растет.

70 Автоматизированное проектирование наносистем Стандартизация методов проектирования топологии. По методам проектирования и изготовления существующие СБИС могут быть разделены на две группы: заказные и полузаказные.

В случае полузаказных СБИС заранее проектируют те фрагмен ты топологии, которые являются общими для ряда схем такого класса, и заново проектируют только те фрагменты, которые спе цифичны для изделий данной группы. Благодаря этому достигает ся сокращение сроков проектирования и, как следствие, снижение его стоимости. Однако при этом площадь кристалла, как правило, возрастает. Но при мелкосерийном производстве такой подход имеет свои преимущества.

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

Типичными представителями полузаказных схем являются СБИС типа вентильных матриц, описанные далее, и СБИС, со ставляемые из компоновочных блоков. Первый из названных ти пов СБИС относится к полузаказным и по своей структуре и по методу проектирования, а второй – только по методу проектиро вания. В обоих типах СБИС задачи топологического проектирова ния до определенной степени стандартизованы. Поэтому при раз мещении их элементов и трассировке соединительных проводни ков могут быть использованы специальные алгоритмы, описанные ниже. Вместе с тем площадь кристалла у них больше, чем у заказ ных СБИС. Однако по сравнению с кристаллами, всю площадь ко торых занимает ЗУ, размеры таких кристаллов и их быстродейст вие оказываются весьма удовлетворительными.

Новые методы проектирования. В настоящее время почти все микропроцессоры и ЗУ проектируются интерактивным способом, при котором на каждой итерации результаты работы САПР оцени ваются и контролируются разработчиком.

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

Конспект лекций Говоря о САПР СБИС, которые являются средством повыше ния эффективности ручного проектирования топологии тех схем, которые производятся крупными сериями в условиях малой но менклатуры производства, можно назвать системы проектирова ния топологии диалогового типа, которые кратко будут обсуж даться в следующих лекциях, а также существующие системы ве рификации топологии. Оба типа САПР в настоящее время находят широкое применение на практике. Вместе с тем для того чтобы справиться с многообразием ошибок при проектировании тополо гии и успешно противостоять росту объема самих задач топологи ческого проектирования, сопровождающего резкое повышение степени интеграции СБИС, требуется создание новых методов, в том числе таких, которые опрокидывали бы прежние представ ления о топологическом проектировании. Одним из средств реше ния указанной задачи, появившихся на фоне этих требований, яв ляется способ проектирования символьной топологии (п. 1.5.4). Он позволяет при ручном проектировании топологии сократить число операций по переходу от электрической схемы к рисунку тополо гического слоя.

Еще одним способом проектирования является иерархическое проектирование топологии. Этот способ предполагает разделение логической структуры СБИС по принципу «сверху вниз». В этом случае представление логической схемы устройства осуществля ется в виде отдельных блоков с приемлемыми размерами, которые затем размещаются на кристалле и осуществляется трассировка межсоединений между ними в последовательности от нижнего уровня к верхнему. При проектировании топологии на всех уров нях в этом случае находят применение традиционные методы, на пример метод стандартных блоков, ручное проектирование и т. п.

Иерархический принцип проектирования топологии иллюстриру ется на рис. 1.34. Управление базой данных (для СБИС в целом) и взаимодействие между уровнями определяются иерархическим деревом, показанным на рис. 1.34, б.

На рис. 1.35 приведено фотографическое изображение кристалла СБИС, созданного с использованием системы иерархического про ектирования, разработанной одной из японских фирм. Для того что бы иерархическое проектирование топологии воплотить в виде пол ностью автоматизированной системы и обеспечить ей самое широ кое применение, необходимо решить много проблем. Вместе с тем схему, которую можно в будущем реализовать на одном кристалле 72 Автоматизированное проектирование наносистем СБИС, в настоящее время можно реализовать разбиением ее на не сколько кристаллов. Если встать на такую точку зрения, то можно ожидать, что иерархическое проектирование топологии станет важ ным средством поддержки проектирования СБИС больших размеров.

1 Кристалл В 1 2 3 А 3 С B A а a b c C c b б а Рис. 1.34. Топология СБИС иерархической структуры:

а – топология;

б – иерархическое дерево Рис. 1.35. Кристалл СБИС на КМОП-транзисторах (32-разрядный микропроцессор) Конспект лекций 1.3.3. МЕТОД ВЕНТИЛЬНЫХ МАТРИЦ Метод вентильных матриц (или метод базовых кристаллов) пред полагает изготовление кристалла, в котором в заранее предусмот ренном порядке размещены базовые логические схемы или базовые ячейки, и создание СБИС с заданной структурой осуществляется исключительно путем выбора рисунка межсоединений (рис. 1.36).

Базовая ячейка Контактная площадка ввода-вывода данных б а Рис. 1.36. Пример вентильной матрицы (по данным фирмы Toshiba):

а – структура кристалла;

б – структура базовой ячейки Базовая ячейка с геометрией, показанной на рис. 1.37, б, имеет эквивалентную схему рис. 1.37, а.

Реализовав между базовыми ячейками надлежащие межсоедине ния (рис. 1.37, б, в), можно получить простые логические вентили.

Объединив две базовые ячейки, можно получить логический блок (рис. 1.37, г), а объединив несколько таких ячеек, можно реализо вать триггер или счетчик. Логический блок, выполненный на основе нескольких базовых ячеек, называется макроячейкой. Рисунок меж соединений внутри логического блока, выполненного из базовых или макроячеек, определяется заранее и обычно хранится в библио теке. Следовательно, объектом автоматического проектирования топологии блоков и трассировки межсоединений являются привязка 74 Автоматизированное проектирование наносистем (в каждом изделии) логических блоков к базовым или макроячейкам и определение рисунка соединений между ними. Базовая ячейка, не привязанная к определенному логическому блоку, называется пус той. Хотя в состав такой ячейки, естественно, входят транзисторы, на практике она не выполняет активных функций и играет роль пространства для прокладки межъячеечных соединений.

VDD 1 2 4 6 VDD 2 1 8 45 3 9 3 7 6 5 Вход А Выход Вход В 8 Вход А Выход Вход В а б в г Рис. 1.37. Базовые ячейки и макроячейки:

а – эквивалентная схема базовой ячейки;

б – двухвходовый вентиль «И–НЕ»;

в – двухвходовый вентиль «ИЛИ–НЕ»;

г – макроячейки Так как размеры кристалла и площадь пространства, через ко торое могут проходить межсоединения, ограничены, то с точки зрения топологии основной целью проектирования при использо вании данного метода является обеспечение 100%-й трассируемо сти межсоединений. Метод вентильных матриц имеет ряд досто инств, связанных с изготовлением пластин. Вместе с тем он имеет и недостатки: например, при ненадлежащем выборе базового кри сталла для группы изделий снижается эффективность использова ния площади кристалла.

1.3.4. МЕТОД СТАНДАРТНЫХ БЛОКОВ Метод стандартных блоков наиболее широко распространен при автоматизированном проектировании топологии МОП БИС. В этом Конспект лекций случае, как и при использовании метода вентильных матриц, зара нее проектируется рисунок внутренних межсоединений и данные поблочно направляются в библиотеку. Блоки располагаются в виде столбцов, а соединительные проводники – в длинных узких облас тях между столбцами, именуемых каналами. Соединения между соседними каналами осуществляются через так называемые про ходные блоки или через внешнюю область монтажа. Основное от личие данного метода от метода вентильных матриц состоит в том, что, хотя шаблоны для каждого изделия стандартизованы, в рассматриваемом случае структуру конкретных изделий необхо димо проектировать отдельно. Следовательно, места расположе ния блоков и области, через которые проходят межсоединения, не фиксированы, и поэтому одной из целей при проектировании то пологии является максимальное уменьшение размеров кристалла.

Другими словами, следует стремиться к тому, чтобы обеспечить оптимальные размеры кристалла и соответственно 100%-ю трас сировку межсоединений.

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

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

Методы второй группы можно назвать методами стандартных блоков в узком смысле. Хотя они допускают использование раз личных по величине блоков, например ПЗУ, ЗУВП, регистров сдвига, и в этом отношении область применения довольно обшир на, для кристаллов больших размеров результаты автоматического проектирования с их применением существенно уступают резуль татам ручного проектирования. Пример топологии кристалла, спроектированного по методу стандартных блоков и содержащего блоки различных размеров, показан на рис. 1.38.

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

76 Автоматизированное проектирование наносистем Рис. 1.38. Пример СБИС с топологией, использующей стандартные блоки с нерегулярным расположением Хотя автоматическое проектирование топологии этим методом и предусматривает использование блоков различной величины, но, ограничив число их типоразмеров, можно добиться вполне удов летворительных результатов, так что в будущем следует ожидать довольно широкого распространения этого метода на практике.

1.3.5. КРИТЕРИИ ОЦЕНКИ ЭФФЕКТИВНОГО РАЗМЕЩЕНИЯ БЛОКОВ И ТРАССИРОВКИ МЕЖСОЕДИНЕНИЙ Проблемы размещения блоков и трассировки межсоединений взаимосвязаны, поэтому рассматривать их по отдельности весьма затруднительно. В общем случае желательно реализовать высокую плотность монтажа, при которой соединительные проводники за нимали бы около 80% площади кристалла. Однако решить эту за дачу чрезвычайно сложно, и поэтому при автоматизированном проектировании топологии задача делится на два этапа: размеще ние блоков и трассировка межсоединений.

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

1. Геометрические ограничения. Межсоединения, как правило, выполняются в виде двухслойной структуры. Если же количество слоев три и более, то обычно их объединяют попарно. К двум пер вым слоям привязывают цепи с наибольшими ограничениями, а за тем производят привязку оставшихся слоев. Проводники межсоеди нений имеют определенную толщину. Проводники, относящиеся к одному и тому же слою, не должны пересекаться, и, кроме того, расстояние между ними не должно быть менее некоторого мини мального. Цепи, относящиеся к двум или более слоям, соединяются посредством сквозных переходов. Эти переходы также имеют опре деленные размеры, и расстояния между ними не должны быть ме нее некоторого минимального. Кроме того, существуют ограниче ния и на их расположение. В частности, они не могут располагать ся внутри блоков.

2. Ограничения, связанные с паразитными параметрами сиг нальных шин. Если длина соединительных проводников оказыва ется излишне большой, их сопротивление возрастает и электри ческие характеристики соответственно ухудшаются. При этом возрастает также роль временной задержки, так что при проекти ровании сигнальных шин рисунок монтажа должен быть таким, чтобы соединительные проводники были по возможности корот кими. В случае МОП ИС, в которых используется двухслойная структура межсоединений (металл и поликристаллический крем ний), особенно важно сокращать участки проводников, проходя щих через слой поликристаллического кремния. Отметим также, что при увеличении количества межсоединений, осуществляемых посредством сквозных отверстий, сопротивление межсоединений также возрастает. Кроме того, в быстродействующих ИС для 78 Автоматизированное проектирование наносистем снижения паразитных ёмкостей накладываются ограничения на длину горизонтальных соединительных проводников.

VSS VDD б К выводу модуля а в Рис. 1.39. Проектирование шин питания:

а – напряжение одного номинала;

б – напряжение двух и более номиналов;

в – разводка шин питания 3. Ограничения, связанные с допустимой силой тока в шинах питания. Для того чтобы минимизировать отклонение потенциа ла в шинах питания и «земляных» шинах, в качестве таковых обычно используют однослойную металлическую структуру.

Трассировка логических схем, работающих от однополярного питания и «земляной» шины, производится так, как показано на рис. 1.39, а. В тех же случаях, когда необходимы два или более источников напряжения – так, как показано на рис. 1.39, б. При этом размещение указанных шин должно совпадать с размещени ем выводов питания каждого блока. При проектировании шин питания весьма важно учитывать, что если плотность тока в них становится слишком большой, то под действием выделяющегося тепла может произойти их расплавление. В общем случае пита ние на блоки подают не от одной, а от нескольких шин (рис. 1.39, в).

Чем ближе к источнику расположена шина питания, тем выше Конспект лекций в ней плотность тока, поэтому такие шины должны иметь доста точно большую толщину.

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

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

В общем случае рисунок межсоединений определяется деревом Штейнера, имеющим несколько точек ветвления (рис. 1.40, а).

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

а б в Рис. 1.40. Способы трассировки проводников между несколькими точками:

а – дерево Штейнера;

б – соединения типа «вход–выход»;

в – последовательное соединение точек: – вход, – выход, – точка ветвления Следует учитывать, что выводы, расположенные по краям бло ков, размещенных на кристалле, характеризуются как определен ными ограничениями, так и степенями свободы. На рис. 1.41 показа на функциональная схема блока, содержащего вентиль «ИЛИ–НЕ»

и проводники из поликристаллического кремния. Выводы (2, 4) этого блока можно рассматривать как эквивалентные точки. Цепи, которые должны быть подключены к блоку, могут подключаться 80 Автоматизированное проектирование наносистем или к точке 2, или к точке 4. Выводы (5, 6) также представляют собой эквипотенциальные точки. Соединяющий их проводник ана логичен перемычкам в печатных платах. Его назначение состоит в том, чтобы внешние цепи могли быть проведены через блок.

По отношению к выводам других блоков, соединяемых с данным, выводы 1 и (2, 4) можно считать «логически эквивалентными», т. е. взаимозаменяемыми. Учитывая наличие подобных степеней свободы, в схеме можно обеспечивать более высокое быстродей ствие. Вместе с тем ограничения, накладываемые на характер межсоединений, отличаются строгостью, и вводить их в програм му автоматической трассировки достаточно сложно.

1 и (2, 4): логически эквивалентны 4 (2, 4): эквипотенциальны (5, 6): проходной проводник 5 Рис. 1.41. Степени свободы при подключении к выводам 5. Ограничения, связанные со стандартизацией методов обра ботки. Решение задачи автоматизированной трассировки предпо лагает стандартизацию некоторых ее параметров, при которой, в частности, задается (в расчете на самый худший случай) ширина всех сигнальных шин и расстояния между ними, что влечет за со бой, однако, снижение плотности монтажа. При двухслойной структуре межсоединений во многих случаях целесообразно вести трассировку так, чтобы отрезки проводников, идущих в продоль ном направлении, относились к одному слою структуры, а идущих в поперечном направлении – к другому. Таким образом, задача трассировки представляет собой задачу нахождения совокупности не пересекающихся между собой маршрутов в решетчатой струк туре, типа показанной на рис. 1.42. Такой подход дает возмож ность упростить алгоритм трассировки. При этом одно из требова ний стандартизации гласит, что сквозные отверстия и выводы (точнее, их центры) должны находиться в узлах решетки.

Если при условии стандартизации трассировки 100%-я трасси ровка не обеспечивается, то от принципа ортогональной структуры следует отказаться. В этом случае следует производить трассиров Конспект лекций ку оставшейся части цепей, допуская в зависимости от конкретной ситуации расположение проводников под углом (чаще всего 45° или 135°), причем трассировка оставшейся части цепей в основном производится не автоматически, а вручную.

a б Рис. 1.42. Графы типа «решетки»:

а – с ортогональной структурой;

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

Самой распространенной топологической задачей является за дача размещения на кристалле блоков одинаковых размеров в пра вильном порядке. Эта задача подобна задаче о топологии печатной платы, на которой в правильном порядке размещены БИС типа вентильных матриц или аналогичные им.

y1 y xi c xi, x j : количество проводников d yk, y j : расстояние между ними ym Рис. 1.43. Двухмерная регулярная структура 82 Автоматизированное проектирование наносистем Если через X = { x1, x2,…, xn } обозначить n блоков, а через Y = { y1, y2,…, ym } – m областей, в которых блоки могут быть раз мещены на кристалле и которые в совокупности имеют вид двух мерной решетки ( m n ), то задача размещения может быть пред ставлена в виде отображения ( X Y ) (рис. 1.43).

Решение задачи о топологическом проектировании вентильной матрицы связано со следующими ограничениями:

а) блоки (базовые ячейки), из которых состоят макроячейки, должны быть расположены поблизости друг от друга;

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

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

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

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

() c xi, x j d ( xi ), x j.

f () = xi, x j X Считается, что чем меньше величина f ( ), тем лучше вы бранный вариант топологии. Через c xi, x j здесь обозначено ко личество проводников, соединяющих блоки xi и x j, а через () d ( xi ), x j – расстояние между ячейками (местами располо жения блоков).

При определении гипотетической длины проводников в случае соединений между множеством точек предполагается, что способы соединения соответствуют показанным на рис. 1.44 или же оценка дается на основании их приближенной гипотетической длины, как показано на рис. 1.45.

Конспект лекций Умножение суммы длин полного графа на 2 / n, а где n число выводов а Сумма двух сторон "минимального прямо б b угольника", содержа щего выводы ( a + b ) Рис. 1.44. Предполагаемая длина маршрута между точками Линия раздела Блок Линия раздела Трасса Рис. 1.45. Оценка топологии с помощью линий раздела Эти методы оценки топологии позволяют просто производить расчет оценочной функции, что является их несомненным преиму ществом.


2. Количество проводников, пересекающих линии раздела.

Эффективность выбранного варианта топологии тем выше, чем меньше количество проводников, пересекающих вертикальные или горизонтальные линии раздела на кристалле (см. рис. 1.45).

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

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

3. Использование пустых ячеек (минимизация плотности монтажа). Важным критерием оценки качества топологии СБИС типа вентильных матриц является возможность эффективного ис пользования их пустых ячеек (в СБИС со стандартными блоками в качестве пространства для прокладки соединительных провод ников можно использовать базовые ячейки, не подключенные к ло гическим блокам). Согласно критерию (1), топология рис. 1.46, б эффективнее топологии рис. 1.46, а. В данном случае необходима некоторая предварительная обработка, предусматривающая окон чательное определение топологии, после того как произведено распределение пустых ячеек (на рис. 1.46 заштрихованы). Вместе с тем одного введения горизонтальных и вертикальных линий раз дела в соответствии с критерием (2) недостаточно. Дело в том, что количество проводников, пересекающих линии раздела и, одинаково и в случае рис. 1.46, а, и в случае рис. 1.46, б. Однако если провести еще линию раздела и оценить топологию по от ношению числа пересекающих ее проводников к их длине, то бо лее эффективной окажется топология рис. 1.46, а. Иными словами, так введено представление о минимизации плотности соедини тельного монтажа.

y1 y2 y3 y4 y1 y2 y3 y y5 y6 y7 y8 y5 y6 y7 y y9 y10 y11 y12 y9 y10 y11 y y13 y14 y15 y16 y13 y14 y15 y а б Рис. 1.46. Использование «пустых» ячеек Для оценки качества топологии с учетом плотности соедини тельного монтажа предложен метод, предусматривающий анализ гипотетических возможностей разветвления одного соединитель ного проводника (рис. 1.47) на проводники с весовыми коэффици ентами менее 1 (1/2, 1/4, 1/8 и т. д.). Так, например, для маршрута проводника между оконечными точками A и B на рис. 1.47 (даже Конспект лекций для случая соединения по кратчайшему пути) существует целый ряд возможностей, и на этапе размещения блоков невозможно предста вить, какие маршруты будут выбраны для соединяющих эти блоки проводников на этапе трассировки. Как показано на рис. 1.47, в данном случае производится вероятностная оценка величин, на которые в ветвях структуры делится единичный поток (физическая величина, удовлетворяющая второму закону Кирхгофа) по мере его продвижения от точки A к точке B. Цифры, указанные на рис. 1.47, характеризуют ожидаемое значение потока, проходящего по про водникам, соединяющим оконечные точки A и B. Просуммировав количество проводников с учетом соответствующих ожидаемых значений (меньших единицы) по всей структуре, можно оценить плотность соединительного монтажа в этой области кристалла.

1/ 8 1/ 4 1/ 2 Вывод А 1/ 8 1/ 1/ 8 1/ 1/ 8 1/ 1/ 1/ 4 1/ 1/ 4 1/ 1/ 1/ 4 1/ 1/ 2 1/ 4 1/ 8 1/ Вывод В 1/ 1/ 1/ Рис. 1.47. Распределение вероятностей для маршрутов проводников Метод оценки по сложности монтажа требует для получения оценочной функции большее время, чем методы (1) и (2). Однако он позволяет получить более точную оценку топологии для данной зоны.

4. Площадь кристалла. Говоря о критериях оценки по методам (1), (2), (3), следует иметь в виду, что объектом исследования в данном случае являются кристаллы с постоянной площадью, что характерно, например, для СБИС типа вентильных матриц. В слу чае СБИС на стандартных блоках площадь кристалла определяется как результат проектирования топологии. Поэтому качество топо логии в этом случае, т. е. когда в отличие от случая вентильных матриц интерес представляет взаимное расположение блоков, оце 86 Автоматизированное проектирование наносистем нивается по величине площади кристалла, занимаемой соедини тельными проводниками. Чтобы оценить эту площадь, необходимо предварительно произвести некоторые операции по упорядочению топологии соединительных проводников, позволяющие усреднить их распределения по каналам (области, используемые для про кладки соединительных проводников между блоками).

1.3.6. РАЗДЕЛЕНИЕ И ГРУППИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ 1. Задача разделения. Задача «разделения логики», как показы вает ее название, представляет собой задачу разделения комплекса логических схем на функциональные блоки («модули») в виде СБИС. После того как логическая схема, выполняемая на одном кристалле, окончательно определена, ее разделяют на группы из нескольких вентилей или ячеек. Так, например, кристалл СБИС типа вентильной матрицы, показанный на рис. 1.48, а, разделяется на пять групп по 18 базовых ячеек в каждой. СБИС с «полиячееч ной» топологией аналогичным образом разделена на несколько вертикальных групп (столбцов) вентилей.

В общем случае ограничивающие условия или критерии оцен ки, которыми следует руководствоваться при решении задачи раз деления, сводятся к следующим:

а) площадь, занимаемая каждым отдельным модулем;

б) количество внешних выводов в каждом модуле;

в) размеры модулей и однородность их структуры;

г) электрические характеристики: время задержки распростра нения сигнала, уровень тепловыделения и т. п.;

д) легкость проведения измерений и профилактических работ.

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

Поэтому все известные до настоящего времени способы разделе ния СБИС формализуются в виде задачи математического про граммирования, в которой учитываются только физические огра ничения, отмеченные в пп. а и б.

Исходя из конкретного примера, задачу разделения можно оп ределить следующим образом. Если B – множество логических вентилей, подлежащих размещению на одном кристалле;

X – множество внешних выводов (входные и выходные контактные площадки), то все цепи Wi, i = 1, n, содержащие соединительные Конспект лекций проводники, можно рассматривать как подмножество B X.

( ) Кроме того, если распределить B по p модулям B1, B2,…, B p ( j = 1, p ) и потребовать, чтобы площадь каждого B j -го модуля была меньше A j, то легко сформулировать следующее ограничи вающее условие:

( r ) Aj, j = 1, p, rB j где ( r ) – площадь логического вентиля r B.

Вместе с тем, обозначив через c (Wi ) величину, полученную путем вычитания 1 из количества модулей (внешние выводы X рассматриваются как модуль B p +1 ), присоединенных к каждой из цепей Wi, выражение для целевой функции можно представить в следующем виде:

n C = c (Wi ) min, i = где C – сумма пар выводов цепей, соединяющих модули между собой.

Так, например, сопоставив логическую схему на рис. 1.48, а с приведенными выше формальными соотношениями, можно по лучить множество логических вентилей B = {1,…,15}, множество внешних выводов X =, а множество цепей, содержащих про водники, W = {a,…, n}. Приняв, что площадь каждого вентиля равна 1, и разделив множество вентилей по трем модулям с пло щадью не более 5, приходим к некоторому ограничению, согласно которому «каждый модуль содержит в точности 5 вентилей».

Отметим, что в соответствии со способом разделения, принятым на рис. 1.48, б, оптимальным решением для целевой функции бу дет C = 6.

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

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

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

h i 3 k c g d 4 f e o 9 n b i m a 6 12 j а i g 2, 4, 10, 13, 15 1, 3, 5, 7, e n a b 6, 8, 9, 11, б Рис. 1.48. Распределение логических схем:

а – логическая схема;

б – результаты разделения схем на три группы 2. Задача группирования. Задача группирования логических схем в принципе является задачей представления частных схем (модулей), полученных в результате решения задачи разделения, в виде функциональных блоков.

Конспект лекций При проектировании СБИС задача группирования состоит в раз делении размещаемой на кристалле схемы на соответствующие ча стные схемы, причем каждая из этих схем может быть реализована посредством промышленной ИМС. Например, если логическая схе ма, состоящая из 22 вентилей «И–НЕ» и 17 вентилей «ИЛИ–НЕ», должна быть реализована посредством ИМС типа A, содержащей 4 вентиля «И–НЕ», и ИМС типа B, содержащей 4 вентиля «ИЛИ– НЕ», то потребуется 6 ИМС типа A и 5 ИМС типа B. Однако за дача разделения заданной группы вентилей на блоки ИМС харак теризуется значительным количеством степеней свободы, поэтому она должна решаться оптимальным образом в отношении монта жа, расположения внешних выводов и т. п.


При проектировании гибридных СБИС, содержащих печатные резисторы и блочные ИМС, существуют различные варианты реа лизации резисторов. В этом случае задача группирования сводится к выбору их оптимальных типов. При этом на первом этапе из группы резистивных паст (с удельным сопротивлением 1 кОм, 10 кОм, 100 кОм и т. д.) выбирают наиболее подходящую пасту с учетом площади и стоимости печати. На втором этапе из множе ства стандартных типоразмеров, данные о которых хранятся в биб лиотеке, выбирают наиболее подходящие с точки зрения возмож ности их размещения на подложке.

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

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

При проектировании топологии СБИС на вентильных матрицах задача группирования решается как задача представления требуе мой логической схемы в виде комбинации ячеек (или макроячеек), данные о которых хранятся в библиотеке. На рис. 1.49 приведен пример группирования базовых ячеек логических схем в макро ячейки.

Как правило, количество типоразмеров ячеек, данные о кото рых зарегистрированы в библиотеке, ограничено, поэтому во мно гих случаях, прежде чем приступать к группированию, производят 90 Автоматизированное проектирование наносистем переход от логической схемы к ее эквиваленту, вводя инверторы (показаны пунктиром) и преобразуя многовходовые вентили в вен тили с числом входов менее трех. Такой подход к задаче группи рования позволяет увеличить число возможных вариантов. Однако при этом необходимо выбирать оптимальный метод группирова ния, предполагающий минимизацию количества ячеек, минимиза цию времени задержки, минимизацию количества соединений ме жду ячейками и т. п.

А B C D E F Рис. 1.49. Группирование логических схем по базовым и макроячейкам Выше в общих чертах была рассмотрена задача группирования для некоторых аспектов ее реализации. Вместе с тем, в принципе, задача группирования состоит из задачи выбора, предусматри вающей выбор блоков (ячеек), посредством которых должны быть реализованы частные схемы, из каталогизированной библиотеки, и собственно задачи группирования (объединения), предусматри вающей определение частных схем, подлежащих объединению в блоки (ячейки). Успешность решения первой из этих задач не редко зависит от особенностей ручного или диалогового проекти рования. Вторая задача представляет собой один из видов задач разделения, и, если алгоритм проектирования достаточно прост, удовлетворительное решение может быть получено также и с ис пользованием ЭВМ.

3. Алгоритмы разделения/группирования. Ниже приведены типичные алгоритмы, используемые при автоматизированном ре шении задач разделения/группирования.

Конспект лекций Алгоритм максимальной связности – минимальной несвязности.

Анализируя элементы (вентили, ячейки и т. п.), которые должны стать «ядром» модуля, т. е. единицей разделения, из них выделяют один, обладающий наибольшей связностью с остальными. Затем из оставшихся блоков выбирают те, которые удовлетворяют огра ничениям по занимаемой площади и количеству внешних выводов и обладают наиболее сильной связью с «ядрами», и присоединяют их последовательно к ранее выбранному модулю. Если указанные ограничения превышены, то формирование модуля завершается, из множества оставшихся элементов выбирается «ядро» нового модуля и процесс повторяется.

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

В дальнейшем, используя эти «зародыши» в качестве «ядер»

модулей, оставшиеся элементы последовательно присоединяют к модулям с самой сильной связью с данными элементами.

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

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

1.3.7. АЛГОРИТМЫ РАЗМЕЩЕНИЯ Критерии оценки качества топологии были изложены в п. 1.3.2.

В данном разделе будут рассмотрены типичные алгоритмы разме щения элементов на БИС в свете этих критериев. В принципе эти методы можно разделить на две группы – конструктивные и ите рационные. Конструктивные методы дают приближенное решение 92 Автоматизированное проектирование наносистем путем многократного повторения одних и тех же действий, осно ванных на критериях качества, обеспечивающих локальную опти мальность. Итерационные методы предусматривают последова тельное совершенствование начальной топологии, полученной тем или иным способом, путем локальной замены элементов. Типовые алгоритмы для обеих групп методов рассмотрены далее в пп. 1, 2.

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

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

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

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

А B E C D Рис. 1.50. Размещение блоков, при котором длина соединительных проводников минимальна Вместе с тем задачу обработки можно упростить, построив мо дель, в которой длина соединительных проводников между блока ми соотнесена с силой притяжения. Так, например, если блоки A, B, C, D (рис. 1.50) уже размещены, а блок E не размещен, то оптимальная область, в которую с учетом указанных соображений он может быть помещен, представляет собой заштрихованный прямоугольник серого цвета. В терминах динамики группу соеди нительных проводников можно рассматривать как упругое тело, и задача, таким образом, становится эквивалентной задаче поме щения еще неразмещенных блоков в точки, в которых силы при тяжения уравновешивают друг друга (точки центров тяжести). Если число блоков равно n, то время, затрачиваемое на решение задачи размещения одного блока, пропорционально n. Следовательно, время, затрачиваемое на решение задачи размещения всех блоков () системы, равно O n 2.

Силонаправленный метод. Данный метод, основанный на ис пользовании динамической модели роста «пучков», имеет целью 94 Автоматизированное проектирование наносистем определение равновесных точек одновременно для всех блоков.

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

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

Метод дихотомического деления. Если в двух рассмотренных выше методах критерием оценки является минимизация общей длины проводников, то критерием оценки в данном методе является минимизация количества проводников, проходящих через область блока. Этот метод предусматривает такое разделение кристалла на две части, при котором общая площадь блоков будет в них при близительно одинаковой, а число групп проводников, соединяю щих эти части, – минимальным. Операции деления (рис. 1.51) про изводят до тех пор, пока не будет получен единственный блок или последовательность линейно расположенных блоков.

Метод использования потоков сигналов в логической схеме.

Данный метод отображает последовательность, в которой разра ботчик, анализируя логическую схему при ручном проектирова нии, определяет расположение отдельных блоков. Действительно, при вычерчивании логической схемы разработчик размещает ло гические вентили (блоки) по возможности в соответствии с на Конспект лекций правлениями потоков сигналов. Во многих случаях такой подход позволяет сократить длину сигнальных шин и количество их пере сечений. Включив этот принцип в ориентированный на ЭВМ алго ритм и, например, ранжировав вентили на логической схеме, мож но выработать некоторые правила, позволяющие отобразить эти вентили в виде ячеек, упорядоченно расположенных на поверхно сти кристалла. При этом, однако, следует принимать во внимание необходимость сокращения длины соединительных проводников по критическому пути, определяющему задержку на передачу сиг налов.

4-й этап 1-й этап Одномерная структура 3-й этап 2-й этап 2-й этап Рис. 1.51. Метод половинного деления Метод случайного размещения. Данный метод предполагает, что итерационным методом может быть получено удовлетворительное решение и позволяет использовать последовательность случайных чисел для определения первоначального варианта компоновки.

В этом отношении он существенно отличается от рассмотренных выше конструктивных методов.

Метод случайного размещения основан на использовании сле дующих допущений:

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

б) при использовании удовлетворительного приближенного ре шения, полученного конструктивным методом, во многих случаях останавливаются на локальных оптимальных реше 96 Автоматизированное проектирование наносистем ниях, которые не удается приблизить к оптимальному реше нию итерационным методом;

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

Отметим, что рассмотренные выше конструктивные методы по зволяют получить только одно первоначальное решение.

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

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

Они имеют цель улучшить топологию кристалла СБИС путем из менения положения блоков в пределах ограниченной области.

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

Метод парных перестановок. Если выбрав один блок A, мож но добиться улучшения топологии путем его перестановки с ка ким-либо другим блоком, то такая процедура называется переста новкой блоков A и B (если наибольшая эффективность достига ется при этой перестановке).

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

Типичные методы рассмотрены ниже. Время, требуемое на одну () перестановку, составляет O ( n ) O n 2.

1. Объектом перестановки являются все блоки, кроме A.

2. Объектом перестановки являются только блоки, расположен ные поблизости от A.

Конспект лекций 3. Зафиксировав положение блоков, кроме A, получают векторы, направленные к «центру тяжести» (п. 1), и выбирают ближай ший в этом направлении блок B.

4. Выбирают блок B, расположенный в центре тяжести.

Силонаправленный метод релаксации. Выбрав один блок ( A ), для него находят центр тяжести. Если в этом месте находится дру гой блок ( B ), его следует переместить в другое место. После это го находят центр тяжести для блока B, и если в этом месте нахо дится блок C, его также перемещают. Эту операцию повторяют до тех пор, пока центр тяжести не окажется в свободной области.

В качестве альтернативы после конечного числа перестановок блок, находящийся в центре тяжести, полученном в последний раз, перемещают в положение A, и если это приводит к улучшению оценочной функции, производят соответствующую перестановку (рис. 1.52). Данный метод допускает перемену мест только для двух блоков. Возможны методы, в которых объектом замены яв ляются три и более блоков;

от них, очевидно, можно ожидать только более эффективного улучшения топологии.

Время, затрачиваемое на расчет одной подстановки (при огра () ничении их числа), составляет O n 2.

До перемещения А D перемещения В А После В С D С Вектор центра тяжести Направление перемещения Рис. 1.52. Силонаправленный метод релаксации Метод Штейнберга. Обозначим множество несоединенных ме жду собой блоков (несвязное множество) через B = { B1, B2,…, Bm }, а множество областей, в которых расположены эти блоки, – через P = { P, P2,…, Pm }, и проведем перекомпоновку таким образом, чтобы максимально снизить общую длину соединительных про водников для отображения B P. Если ввести двудольный граф, 98 Автоматизированное проектирование наносистем вершины которого соответствуют элементам множеств B и P, обозначив весовые коэффициенты его ребер, соединяющих точки Bi B и Pj P через ij и задав минимальную длину соедини тельных проводников для того случая, когда Pi находится в пози ции Pj (при ее увеличении ij 0 ), то оптимальную перекомпоновку можно реализовать методом максимального весового согласования (рис. 1.53). Так, например, если при первоначальном размещении (рис. 1.53, а) несвязным множеством является { B1, B2, B3 }, а в ре зультате перестановок может быть достигнуто улучшение оценоч ной функции (рис. 1.53, б), то перестановка, обеспечивающая ее максимальное улучшение, соответствует процедуре согласования, показанной на рис. 1.53, в. Результаты перекомпоновки воспроиз ведены на рис. 1.53, г.

0P B1 P B1 4 B B1 5 3 0 B2 P B2 B2 P2 B 2 B3 P3 P B3 B3 B а б в г Рис. 1.53. Метод Штейнберга и задача максимального весового согласования:

а – начальное расположение;

б – двудольный граф;

в – максимальное весовое согласование;

г – результаты перемещений Задача максимального весового согласования двудольного гра фа эквивалентна задаче, именуемой в области исследования опе раций задачей распределения. При использовании метода потока в сетях ее решение может быть получено за время, пропорциональ ное третьей степени количества вершин графа. Таким образом, ес ли количество элементов несвязного множества равно m ( m n ), () то время обработки по методу Штейнберга составляет O m3.

3. Одномерная задача размещения. Если в ряду блоков, вхо дящих в состав группы, расположенной на кристалле или на его части, можно пренебречь их связями с блоками других групп, то локально-оптимальное расположение блоков можно приближенно оценить с помощью модели, показанной на рис. 1.54. Собственно Конспект лекций оценка сводится к задаче минимизации количества необходимых трасс при условии, что все блоки соединяются в горизонтальном направлении. Иными словами, эта задача является задачей мини мизации для каждого блока максимального значения суммы числа проходных проводников и числа внешних выводов. Отметим, что в примере рис. 1.54 расположение блоков в варианте б более целе сообразно, чем в варианте а. Как и при двухмерной топологии, за дача может решаться двумя методами: конструктивным методом, предусматривающим поочередное сближение блоков с наиболее сильной связью между ними, и итерационным методом, согласно которому значение оценочной функции улучшают путем много кратной замены и перестановки блоков.



Pages:     | 1 || 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.