Адаптивные разбиения: различия между версиями

На важном субмикронном этапе технологической эволюции в электронике именно межсоединения стали доминирующим фактором, определяющим производительность и надежность СБИС. Исторически сложилось так, что задача проектирования межсоединений в СБИС была очень тесно переплетена с классической задачей вычислительной геометрии – построением минимального [[дерево Штейнера|дерева Штейнера]]. Некоторые важнейшие характеристики СБИС примерно пропорциональны длине межсоединений. К таким характеристикам относятся площадь кристалла, выход годных кристаллов, энергопотребление, надежность и синхронизация. Например, площадь, занимаемая межсоединениями, пропорциональна их суммарной длине и напрямую влияет на размер чипа. Увеличение размера микросхемы приводит к снижению процента выхода годных и росту стоимости производства. С увеличением длины проводов возрастает и стоимость других компонентов, необходимых для производства. С точки зрения производительности более длинные межсоединения способствуют увеличению рассеивания мощности, деградации синхронизации и другим нежелательным последствиям. Именно поэтому поиск минимальной длины межсоединений, согласующейся с другими целями и ограничениями, является настолько серьезной задачей на данном этапе развития технологии СБИС.

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

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