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

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

Впервые адаптивное разбиение при конструировании приближенного алгоритма ввели Ду и коллеги [5], применившие его с помощью гильотинных разрезов при изучении задачи о прямоугольном разбиении с минимальной длиной ребра (MELRP). Авторы обнаружили, что если разбиение выполняется последовательностью гильотинных разрезов, то оптимальное решение может быть вычислено за полиномиальное время с помощью динамического программирования. Более того, это оптимальное решение можно использовать как достаточно хорошее приближенное решение для исходной задачи прямоугольного разбиения. И Арора [1], и Митчелл и др. [12, 13] выяснили, что разрез не обязательно должен быть полностью гильотинным. Другими словами, динамическое программирование по-прежнему может быть выполнено за полиномиальное время, если подзадачи сохраняют некоторые связи, но количество этих связей меньше исходного. При увеличении числа связей полученное приближенное решение становится ближе к оптимальному, а время выполнения, естественно, увеличивается. Также было установлено, что данный метод может быть применен ко многим задачам геометрической оптимизации для получения схем аппроксимации с полиномиальным временем выполнения.

Наивная идея построения алгоритма аппроксимации для общего случая заключается в использовании леса, соединяющего все отверстия с границей, и последующем решении полученной задачи без отверстий за время <math>O(n^4)</math>. На основе этой идеи Лингас [10] предложил первую аппроксимацию с константными границами, коэффициент эффективности которой равен 41.

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

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

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

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

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