Обзор физико-математической модели и алгоритмического тракта

Аннотация

В статье рассматривается структура панельного 3D-солвера, предназначенного для экстракции паразитных ёмкостей проводящих структур. Модель формулируется как электростатическая задача Максвелла, сводимая к интегральному уравнению для поверхностной плотности заряда. Поверхности проводников дискретизируются на панели, после чего строится оператор потенциальных коэффициентов, связывающий панельные заряды и панельные потенциалы. Для больших задач действие оператора целесообразно реализовывать иерархически, с прямой обработкой ближних взаимодействий и агрегированным вычислением дальних вкладов. Численное решение выполняется Krylov-подпространственным методом с процессом Арнольди и малой задачей наименьших квадратов. Завершающий этап состоит в суммировании панельных зарядов по проводникам и формировании разреженного представления матрицы ёмкостей. Описание дано в абстрактной терминологии, но отражает solver pipeline, реализованный автором в библиотеке на C++20.

Ключевые слова: parasitic extraction, capacitance extraction, boundary-element method, method of moments, potential coefficient matrix, Krylov subspace, GMRES, fast multipole method, sparse capacitance output.

1. Введение

Паразитные ёмкости межсоединений являются одним из основных факторов, определяющих задержки, перекрёстные наводки и форму переходных процессов в интегральных схемах. Для современных трёхмерных топологий простые табличные модели недостаточны: поле зависит от пространственного расположения проводников, торцов, экранов, via-структур, соседних линий и диэлектрической среды. Поэтому в задачах parasitic extraction используется класс 3D field-solver-моделей, в которых геометрия проводников преобразуется в дискретную электростатическую задачу.

Физическая основа такой задачи задаётся электростатическим пределом уравнений Максвелла. В учебной форме электростатическая задача сводится к системе div E = ρ/ε₀, curl E = 0, далее к представлению поля через скалярный потенциал E = −grad φ и к уравнению Пуассона для φ [1]. В вычислительной постановке для идеальных проводников неизвестное распределение заряда находится на поверхностях проводников, а заданными величинами являются потенциалы проводников.

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

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

Пусть имеется система из m идеальных проводников, помещённых в диэлектрическую среду. На уровне проводников связь между вектором полных зарядов Q и вектором потенциалов V линейна и задаётся матрицей ёмкостей C:

Столбец матрицы C получается из отдельной задачи возбуждения: один проводник переводится в единичный потенциал, остальные фиксируются на нулевом потенциале, затем суммарные заряды всех проводников образуют соответствующий столбец C. Такая процедура прямо используется в классической постановке FastCap для multiconductor capacitance extraction [2].

На непрерывном уровне требуется найти поверхностную плотность заряда σ(x) на границах проводников. Потенциал на поверхности задаётся интегральным уравнением первого рода через функцию Грина:

Для свободного пространства G(x, x′) пропорциональна 1 / ||x − x′||. После нахождения σ полный заряд i-го проводника равен интегралу σ по его поверхности. Именно эта формулировка — заданные потенциалы проводников, неизвестный поверхностный заряд, последующее суммирование зарядов — является базой boundary-element capacitance extraction [2].

3. Панельная дискретизация поверхностей

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

Здесь P — матрица потенциальных коэффициентов. В литературе по FastCap такая матрица строится после разбиения проводящих поверхностей на панели; элементы P выражают вклад заряда одной панели в потенциал другой, а q и p являются panel-level, а не conductor-level векторами [2].

3.1. Абстрактные определения

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

Определение 2. Вектор панельных зарядов. Вектор q содержит коэффициенты дискретного представления поверхностного заряда. Далее q_k считается интегральным зарядом k-й панели. Если в реализации неизвестной является поверхностная плотность заряда σ_k, то при агрегации используется произведение σ_kA_k, где A_k — площадь k-й панели.

Определение 3. Вектор панельных потенциалов. Вектор p содержит заданные или вычисляемые значения потенциала на панелях. Для задачи вычисления столбца C он формируется из потенциалов проводников: 1 В на возбуждаемом проводнике и 0 В на остальных заданных проводниках.

4. Оператор потенциальных коэффициентов

Оператор P является дискретизацией однослойного потенциала. Его элемент P_ij задаёт потенциал на тестовой панели i, создаваемый единичным зарядовым коэффициентом на исходной панели j. В collocation-форме элементы выражаются интегралами кулоновского ядра по поверхности панели. В FastCap такая конструкция явно формулируется как матрица потенциальных коэффициентов, связывающая n панельных зарядов с n панельными потенциалами [2].

где A_j — площадь j-й панели.

Для прямоугольных панелей часть таких интегралов может быть сведена к аналитическим выражениям с sqrt, log и atan. В практической реализации оператор может содержать несколько вычислительных путей: точный kernel для геометрически сложных или близких пар; быстрый approximate path; split/refinement path; cutoff-oriented path для слабых и дальних вкладов. Все эти пути относятся к одному и тому же объекту — коэффициенту потенциального влияния между панелями.

5. Граничные условия и reduced system

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

При наличии fixed-potential проводников значения панельных потенциалов задаются из граничных условий, а неизвестными остаются панельные зарядовые коэффициенты. Для floating-групп дополнительно вводятся неизвестные потенциалы групп и constraint-уравнения, например условия на полный заряд. После исключения явно заданных величин или после добавления constraint-уравнений получается расширенная или редуцированная система, эквивалентная исходной boundary-integral-постановке. Такая редукция не меняет физическую модель; она меняет только набор неизвестных, реально передаваемых в численный solve-loop.

6. Иерархическое ускорение оператора

Полная матрица P имеет размер n × n, где n — число панелей. Для больших трёхмерных структур прямое хранение и применение такой матрицы становится дорогостоящим. Методы граничных элементов естественно приводят к плотным матричным задачам; именно это указано в FastCap как основная причина необходимости ускорения [2].

Классический способ ускорения — иерархическая декомпозиция пространства и использование multipole-like представлений для дальних взаимодействий. Fast multipole method был введён как метод быстрого вычисления потенциалов и сил в системах с большим числом источников [3]. В capacitance extraction аналогичная идея применяется для ускорения вычисления действия оператора P на вектор q: ближние взаимодействия вычисляются напрямую, дальние передаются через кластерные агрегированные представления [2], [3], [6].

7. Итерационный solve-loop

После построения P или matrix-free operator apply требуется решить систему Pq = p. Для больших задач используется Krylov-подпространственный итерационный метод. GMRES в классической работе Saad-Schultz определяется как метод, который на каждом шаге минимизирует норму вектора невязки на Krylov-подпространстве и строится на процессе Арнольди [4].

Абстрактный solve-loop имеет следующий вид:

• вычислить начальную невязку r₀ = p − Pq₀;
• нормировать r₀ и построить первый вектор базиса;
• на каждой итерации применить оператор P к текущему базисному вектору;
• ортогонализовать результат относительно предыдущих базисных векторов;
• сформировать элементы малой верхней Hessenberg-матрицы;
• решить малую least-squares задачу для минимизации нормы невязки;
• обновить приближение q и проверить критерии останова.

Малая задача наименьших квадратов может быть решена через QR/LQ-факторизацию. В LAPACK процедура DGELS предназначена для решения overdetermined или underdetermined real linear systems через QR или LQ factorization и включает least-squares варианты min ||B − AX|| [5].

8. Алгоритмические режимы модели

В рассматриваемом pipeline одна физическая постановка может обслуживаться несколькими численными режимами. Эти режимы различаются не уравнениями электростатики, а способом применения оператора, политикой итераций, cutoff/refinement logic и правилами формирования итогового разреженного выхода.

Такая организация близка к практическим fast capacitance solvers: одна и та же boundary-integral-постановка может решаться через различные комбинации итерационных методов, предобусловливания, иерархического ускорения и выходной фильтрации [2], [4], [6].

9. Агрегирование зарядов и формирование выхода

Решение системы Pq = p даёт panel-level вектор q. Однако circuit-level модель требует conductor-level матрицу C. Поэтому после solve-loop выполняется суммирование панельных зарядов по проводникам или сетям. Для j-го возбуждения элемент C_ij получается как сумма зарядов всех панелей i-го проводника. В FastCap эта формула задаётся явно: C_ij вычисляется суммированием panel charges на i-м проводнике для решения с возбуждением j-го проводника [2].

Здесь предполагается, что q_k является интегральным зарядом k-й панели. Если неизвестной величиной является поверхностная плотность заряда σ_k, то суммирование выполняется в форме Σ σ_kA_k.

Полная Maxwell capacitance matrix в общем случае является плотной. Однако в extraction-flow часто сохраняется не плотная таблица C, а разреженное выходное представление значимых self/mutual capacitance terms после пороговой фильтрации.

В Maxwell capacitance matrix диагональные элементы положительны, а взаимные off-diagonal элементы обычно отрицательны. В circuit-level представлениях, включая SPICE/DSPF-подобные форматы, coupling capacitance между двумя узлами часто записывается положительным числом. Поэтому знак взаимной ёмкости зависит от выбранного соглашения записи.

10. Сводный алгоритмический тракт

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

1. Получить геометрию проводников и диэлектрических границ.
2. Выполнить поверхностную дискретизацию: построить набор панелей.
3. Назначить панелям принадлежность к conductors/nets и задать граничные условия.
4. Для каждого возбуждения сформировать вектор панельных потенциалов p.
5. Построить оператор потенциальных коэффициентов P или matrix-free operator apply.
6. Организовать пространственную иерархию для ускоренного применения P.
7. Запустить предобусловленный Krylov/Arnoldi solve-loop для Pq = p.
8. Решить малую least-squares задачу на каждом шаге и проверить невязку.
9. Получить панельные заряды q.
10. Суммировать q по проводникам/сетям и сформировать столбец C.
11. Повторить для всех нужных возбуждений.
12. Записать итоговые self/mutual terms в разреженный capacitance output.

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

11. Обсуждение

Существенная особенность такой модели состоит в разделении двух уровней матриц. Матрица P является panel-level оператором потенциальных коэффициентов, связывающим панельные заряды и панельные потенциалы. Матрица C является conductor-level выходом, связывающим полные заряды проводников и потенциалы проводников. Эти матрицы нельзя отождествлять.

Вторая важная особенность — возможность не хранить P явно. Для больших задач solver может реализовывать только действие P на вектор q, используя иерархические near/far decompositions. Это позволяет совместить BEM/MoM-постановку с итерационным Krylov-solver и избежать прямого решения плотной n × n системы.

Третья особенность — инженерная постобработка. В практическом parasitic extraction важна не только физическая точность зарядового решения, но и формат выходной circuit-level модели. Поэтому после решения вводятся правила отбора, нормировки и записи self/mutual capacitance entries.

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

Рассмотренная структура представляет собой типичный pipeline 3D capacitance extraction: электростатическая постановка Максвелла, поверхностная панельная дискретизация, оператор потенциальных коэффициентов, иерархическое ускорение matrix-vector product, Krylov/Arnoldi/least-squares solve-loop и агрегация панельных зарядов в матрицу ёмкостей. Такая организация соответствует классической линии FastCap/BEM capacitance extraction и современным fast hierarchical solver-подходам [1]-[6].