Random Walk FS

Абстрактная математическая и алгоритмическая модель вероятностного 3D-солвера паразитных ёмкостей

Рисунок 1. Общий алгоритмический тракт вероятностного 3D-солвера.

1. Введение

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

Вероятностная основа такой постановки относится к классу floating random walk. В ранних работах по стохастической экстракции ёмкостей показано, что решение уравнения Лапласа и поток через окружающую проводник поверхность могут быть представлены математическими ожиданиями случайных величин [1, 2]. Современные FRW-солверы используют масштабируемые локальные переходные области, пространственные индексы и специальные процедуры для многодиэлектрической среды [3–5].

Настоящее описание не является обзором всех вариантов FRW. Оно фиксирует конкретную абстрактную композицию модели Random Walk FS: геометрические объёмы, сети и кластеры, прямоугольные поверхности запуска, стратифицированный выбор начальных точек, воспроизводимый случайный поток, локальный куб, ориентированный по координатным осям, раздельный поиск проводников и диэлектриков, специальный первый переход, повторяющиеся принятые переходы, терминальные состояния, статистические накопители и postprocessing ёмкостной матрицы.

2. Электростатическая постановка

Пусть D ⊂ ℝ³ — расчётная область, содержащая идеальные проводящие тела K₁,…,Kₘ и диэлектрические подобласти E₁,…,Eₚ. В области, свободной от проводников и объёмного свободного заряда, потенциал φ удовлетворяет уравнению:

На поверхности каждого проводника задаётся постоянный потенциал Vᵢ. На внешней границе ∂D действует выбранное граничное условие расчётной модели. Полный заряд проводника выражается потоком электрической индукции через его границу либо через любую замкнутую поверхность Γᵢ, охватывающую этот проводник и не пересекающую другие источники свободного заряда:

Линейность электростатической задачи приводит к соотношению между векторами полных зарядов и потенциалов проводников:

где C — матрица ёмкостных коэффициентов. В вероятностной модели отдельный элемент Cᵢⱼ получается не из решения глобальной системы, а из статистической оценки потока и вероятностей терминальных исходов для траекторий, связанных с исходной сетью i и конечной сетью j. Такой прямой переход от потока к матрице ёмкостей является характерным свойством FRW-экстракции [1, 3].

2.1. Физическая область и отдельная случайная траектория

Одна случайная траектория рассматривается внутри общей расчётной области D. Начальная точка x₀ выбирается на поверхности запуска Γᵢ, связанной с исходной сетью i. Далее формируется последовательность точек x₀, x₁, …, xτ. Каждый переход определяется локальным окружением текущей точки: расстояниями до ближайших проводящих тел и внешней границы, положением диэлектрических интерфейсов и состоянием траектории. Поэтому длина и направление шага изменяются по мере движения.

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

3. Геометрическая модель

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

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

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

3.1. Сети, кластеры и активный уровень

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

4. Поверхности запуска и стратифицированная выборка

Для каждой активной исходной сети i формируется конечное множество прямоугольных граней Fᵢ. Совокупность этих граней образует дискретное представление поверхности запуска Γᵢ. Грани не выбираются равновероятно: их вклад зависит от площади, ориентации, доступности и результатов геометрической проверки. Внутри граней формируются страты — непересекающиеся прямоугольные области, используемые для уменьшения дисперсии.

Здесь μᵢₛ — распределение точки внутри страты s, а αᵢₛ — её нормированный вес. Выбор выполняется в два этапа: сначала дискретно выбираются грань и страта по накопленному распределению, затем непрерывно выбираются координаты внутри прямоугольной области. После этого точка проходит геометрическую проверку. Непригодная точка не запускает траекторию и приводит к повторной выборке.

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

где A_f — геометрическая площадь, N_f^trial — число попыток, N_f^valid — число принятых точек. Эффективные площади участвуют в нормировке статистического вклада и позволяют корректно учитывать фильтрацию стартовых точек.

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

5. Воспроизводимое состояние случайного потока

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

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

6. Состояние одной траектории

После выбора начальной точки траектория описывается состоянием

где xₖ — текущая точка; wₖ — накопленный статистический вес; ξₖ — состояние генератора; hₖ — история посещений и локальные кэши; bₖ — служебное состояние границ, последнего препятствия и условий продолжения. До специального первого перехода принимается w₀ = 1. Первый переход формирует начальную физическую весовую нормировку, после чего общий рекуррентный цикл использует то же представление состояния.

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

7. Локальная допустимая кубическая область

В каждой текущей точке xₖ строится куб Qₖ с центром в xₖ, грани которого параллельны координатным плоскостям. Его линейный размер не фиксирован глобально и заново определяется на каждом шаге. Полусторона ρₖ является минимумом нескольких независимых ограничений, а полная длина ребра куба равна 2ρₖ:

• ρ_D — расстояние до внешней границы допустимой области;
• ρ_K — проводящий предел, полученный поиском ближайшей проводящей геометрии;
• ρ_E — ограничение, связанное с диэлектрическими интерфейсами;
• ρ_S — ограничение, зависящее от текущего состояния, защитного буфера и истории.

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

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

8. Локальное диэлектрическое окружение

Для выбранного куба Qₖ выполняется отдельный запрос к диэлектрической геометрии. Результат не сводится к единственному значению ε. Модель получает локальную последовательность всех диэлектрических областей, пересекающих запрос:

Lₖ рассматривается как упорядоченное мультимножество: повторное появление одной и той же области допустимо, а порядок поступления элементов сохраняется. Такая модель естественно отражает пространственный индекс, в котором один объект может быть обнаружен через несколько локальных ячеек. Перед вероятностной обработкой устранение повторов и глобальная сортировка не являются обязательными операциями.

Из Lₖ строится локальное диэлектрическое состояние

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

9. Специальный первый переход

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

Специальное ядро первого перехода выполняет дискретно-непрерывную выборку направления и локального смещения, преобразует выборку в глобальную ориентацию грани и при необходимости повторяет выборку до принятия. Начальный вес w₁ включает знак ориентации, геометрическую нормировку поверхности запуска, локальный диэлектрический отклик и нормировку переходного куба. Конкретная формула представляется оператором 𝒯₀:

Такое выделение первого перехода согласуется с классической FRW-идеей оценки электрического потока через окружающую поверхность [1, 3], но конкретная модель использует собственное таблично-аппроксимационное локальное ядро и ориентационные преобразования.

10. Общее переходное ядро

Для k ≥ 1 кандидат следующей точки генерируется условным распределением

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

10.1. Принятие и повторная выборка

После генерации кандидата вычисляется вероятность принятия

Если кандидат отклонён, координата xₖ и вес wₖ сохраняются, но случайное состояние ξₖ развивается. Затем генерируется новый кандидат. Если кандидат принят, новая точка фиксируется, обновляются вес и история. Один физический переход поэтому может потребовать нескольких внутренних случайных выборок.

10.2. Весовая коррекция

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

11. Повторяющийся цикл Random Walk

После специального первого перехода применяется единый рекуррентный цикл. В математической форме один шаг задаётся оператором перехода состояния:

где 𝒢_K и 𝒢_E — раздельные проводящий и диэлектрический пространственные запросы. Алгоритмическая последовательность шага имеет вид:

1. определить проводящий и внешний пределы локального куба;
2. получить локальное упорядоченное мультимножество диэлектрических областей;
3. построить состояние dₖ и при необходимости уточнить размер куба;
4. генерировать кандидаты до успешного принятия;
5. обновить точку, вес, случайное состояние и историю;
6. проверить попадание в проводник, escape/restart и ограничения траектории.

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

12. Терминальные состояния, escape и restart

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

• проводящий терминал — достигнута сеть j;
• внешняя граница — достигнута граница D либо состояние, эквивалентное уходу из области;
• escape — выполнено внутреннее условие прекращения, включая ограничение числа переходов;
• restart — текущая траектория признаётся непригодной и должна быть запущена повторно;
• защитное завершение — обнаружена вырожденная геометрическая или численная ситуация.

Условия escape и restart не объединяются с обычным попаданием в проводник, поскольку их статистическая интерпретация различается. Терминальный результат одной траектории представим как

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

13. Вклад одной траектории

Для связи исходной сети i с сетью j простейшая форма вклада определяется индикатором терминального проводника:

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

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

14. Стратифицированная статистическая оценка

Пусть для исходной сети i и страты s выполнено Mᵢₛ траекторий. Средний вклад в связь с сетью j равен

После учёта весов страт и физико-геометрической нормировки оценка имеет вид

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

14.1. Дисперсия и стандартная ошибка

Для каждой страты вычисляются выборочные первые и вторые моменты. При Mᵢₛ > 1 несмещённая оценка дисперсии среднего записывается в стандартной форме

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

Текстовое описание статистической агрегации. Терминальные результаты отдельных траекторий преобразуются во взвешенные вклады для пар исходных и конечных сетей. Вклады накапливаются по стратам, после чего вычисляются средние значения, вторые моменты и оценки статистической ошибки. Если требуемая точность не достигнута, запускается дополнительный пакет траекторий; после выполнения критериев сходимости результаты проецируются на активные сети и формируют матрицу ёмкостей.

15. Пакетный контроль сходимости

Траектории выполняются пакетами. После каждого пакета обновляются числа попыток и валидных стартовых точек, средние, вторые моменты, оценки стандартной ошибки, total-capacitance показатели и coupling-показатели. Контроллер сходимости проверяет не один общий скаляр, а набор целей:

• точность полного отклика выбранной исходной сети;
• точность значимых взаимных связей;
• достаточность числа экспериментов в активных стратах;
• корректность статистических переменных и отсутствие неограниченной дисперсии;
• выполнение минимальных и предельных ограничений объёма выборки.

Если хотя бы одна активная цель не выполнена, планировщик формирует дополнительный пакет для нужных исходных сетей или страт. Таким образом, объём расчёта адаптируется к сложности конкретной связи. Слабые coupling-термы могут требовать больше траекторий, чем доминирующие total-термы.

16. Формирование ёмкостной матрицы

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

1. проекцию геометрических терминалов на активный иерархический уровень;
2. канонизацию неупорядоченной пары сетей для взаимной связи;
3. суммирование повторных вкладов одной пары;
4. отделение total-оценок от pairwise coupling-оценок;
5. проверку конечности оценки и статистической достоверности;
6. физический postprocessing диагональных и взаимных элементов.

Оператор 𝒫_C обеспечивает соглашение знаков, иерархическую агрегацию и внутренние условия согласованности. Конкретное правило построения диагональных элементов не фиксируется отдельной формулой: они формируются совместно из total- и coupling-оценок на этапе postprocessing. Каждая выдаваемая связь может сопровождаться оценкой стандартной ошибки и эффективным числом траекторий.

Физически ожидаемая симметрия взаимных ёмкостей относится к точной электростатической задаче. Независимые статистические оценки противоположных направлений могут различаться в пределах погрешности; согласование таких оценок относится к оператору 𝒫_C, а не к локальному random-walk переходу.

17. Параллельная вычислительная организация

Траектории после раздачи исходных точек практически независимы. Поэтому вычисление естественно распараллеливается по рабочим потокам и пакетам. Каждый исполнитель получает локальный набор начальных состояний, продолжает сохранённые случайные последовательности и возвращает статистические записи. Совместно изменяемое состояние минимизируется и сосредоточено в выдаче заданий, объединении накопителей и контроле сходимости.

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

18. Сводный алгоритм

Цельный алгоритмический тракт модели можно представить следующей последовательностью:

1. построить проводящие и диэлектрические локальные объёмы, сети, кластеры и внешнюю границу D;
2. сформировать объёмы экстракции и прямоугольные грани поверхностей запуска Γᵢ;
3. построить страты, эффективные площади и накопленные распределения выбора граней;
4. сформировать план пакетов и воспроизводимые случайные состояния стартовых точек;
5. для каждой принятой точки выполнить специальный первый переход с ориентационной и диэлектрической весовой нормировкой;
6. повторять: построение куба, проводящий поиск, локальный диэлектрический запрос, генерацию и принятие кандидата, обновление веса и истории;
7. завершить траекторию проводящим терминалом либо управляющим состоянием escape/restart;
8. преобразовать терминальный результат во взвешенный вклад Hᵢⱼ и обновить стратифицированные статистические суммы;
9. после каждого пакета вычислить средние, дисперсии, effective-area показатели и проверить набор целей сходимости;
10. после завершения всех активных целей выполнить иерархическую проекцию, агрегацию total/coupling оценок и сформировать C.

19. Границы детализации математической модели

Описанная модель фиксирует устойчивую композицию физических и алгоритмических блоков. При этом следующие элементы намеренно остаются абстрактными операторами: распределение табличного кандидата 𝒬; вероятность принятия 𝒜; весовые функции 𝒯₀ и 𝒯; полный набор правил escape/restart; оператор терминального вклада ℋ; нормировка 𝒩; цели сходимости 𝓔_g; postprocessing 𝒫_C.

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

20. Заключение

Random Walk FS представляет собой вероятностный 3D-солвер, в котором электростатическая связь между проводящими сетями вычисляется как статистическое математическое ожидание терминальных исходов локальных случайных траекторий. Геометрия организована в прямоугольные объёмы и обслуживается раздельными пространственными индексами для проводников и диэлектриков. Начальные точки генерируются на стратифицированных поверхностях запуска, а специальный первый переход преобразует поверхностную выборку в оценку нормального электрического потока.

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

Результаты множества траекторий объединяются по поверхностным стратам с учётом эффективной площади, знака вклада, выборочной дисперсии и иерархии сетей. Пакетный контроллер добавляет эксперименты до выполнения total- и coupling-целей точности. Итоговая матрица ёмкостей формируется из статистически оценённых полных и взаимных связей посредством отдельного физического postprocessing. Таким образом, модель является не матричной аппроксимацией глобального поля, а локально-геометрическим, вероятностным и статистически управляемым способом решения той же электростатической задачи.

Список литературы

1. Y. L. Le Coz, R. B. Iverson. A stochastic algorithm for high speed capacitance extraction in integrated circuits. Solid-State Electronics, 35(7), 1005–1012, 1992. https://doi.org/10.1016/0038-1101(92)90332-7
2. R. B. Iverson, Y. L. Le Coz. A floating random-walk algorithm for extracting electrical capacitance. Mathematics and Computers in Simulation, 55(1), 59–66, 2001. https://doi.org/10.1016/S0378-4754(00)00246-9
3. W. Yu, H. Zhuang, C. Zhang, G. Hu, Z. Liu. RWCap: A Floating Random Walk Solver for 3-D Capacitance Extraction of Very-Large-Scale Integration Interconnects. IEEE TCAD, 32(3), 353–366, 2013. https://doi.org/10.1109/TCAD.2012.2224346. Полный текст PDF: https://numbda.cs.tsinghua.edu.cn/papers/tcad13.pdf
4. J. N. Jere, Y. L. Le Coz. An improved floating-random-walk algorithm for solving the multi-dielectric Dirichlet problem. IEEE Transactions on Microwave Theory and Techniques, 41(2), 325–329, 1993. https://doi.org/10.1109/22.216475
5. M. Song, M. Yang, W. Yu. Floating Random Walk Based Capacitance Solver for VLSI Structures with Non-Stratified Dielectrics. DATE, 2020. https://doi.org/10.23919/DATE48585.2020.9116553. Полный текст PDF: https://past.date-conference.com/proceedings-archive/2020/pdf/0182.pdf
6. Z. Xu, C. Zhang, W. Yu. Floating Random Walk-Based Capacitance Extraction for General Non-Manhattan Conductor Structures. IEEE TCAD, 36(1), 120–133, 2017. https://doi.org/10.1109/TCAD.2016.2561968
7. Y. Le Coz, H. J. Greub, R. B. Iverson. Performance of random-walk capacitance extractors for IC interconnects: A numerical study. Solid-State Electronics, 42(4), 581–588, 1998. https://doi.org/10.1016/S0038-1101(97)00283-9
8. M. Song, M. Yang, W. Yu. Efficient Floating Random Walk Based Techniques for Capacitance Extraction of Structures with a Large Number of Non-Stratified Dielectrics. Journal of Computer-Aided Design & Computer Graphics, 36(3), 435–442, 2024. https://doi.org/10.3724/SP.J.1089.2024.19808