A Linear-Time Algorithm for Steady-State Analysis of Electromigration in General Interconnects

이 논문은 Blech 기준과 Black 의 방정식과 같은 기존 방법의 한계를 극복하고, 전자기 이동을 물리 법칙에 기반하여 일반 트리 및 메쉬 구조의 모든 금속 세그먼트에 대해 선형 시간 복잡도로 정상 상태 스트레스와 불사성을 정확하게 분석하는 효율적인 알고리즘을 제안합니다.

핵심

이 논문은 반도체 칩을 만드는 데 있어 매우 중요한 '전선 수명' 문제를 해결하는 새로운, 그리고 매우 빠른 방법을 제안합니다.

너무 어렵게 느껴질 수 있는 기술 용어들을 일상적인 비유로 풀어서 설명해 드릴게요.

1. 문제: 칩 속의 '모래시계'와 '전선'

반도체 칩 안에는 아주 미세한 구리 전선들이 빽빽하게 깔려 있습니다. 전기가 흐르면 전자들이 이 전선을 타고 이동하는데, 이때 전자가 금속 원자들을 밀어내서 원자들이 한쪽으로 쏠리게 됩니다.

• 비유: 전선을 좁은 터널이라고 상상해 보세요. 수많은 사람들 (전자) 이 터널을 지나가다가, 앞사람을 밀어내며 지나갑니다. 시간이 지나면 터널의 한쪽 끝 (음극) 은 사람들이 빠져나가서 구멍 (Void) 이 생기고, 다른 쪽 끝 (양극) 은 사람들이 몰려서 뭉개집니다.
• 결과: 구멍이 생기면 전선이 끊어지고, 칩이 고장 납니다. 이를 전기이동 (Electromigration, EM) 이라고 합니다.

2. 기존 방법의 한계: "단순한 자로 재기"

기존에는 전선이 고장 날지 말지 판단할 때, 블레치 (Blech) 기준이라는 간단한 규칙을 썼습니다.

• 기존 방식: "전류가 얼마나 세고 (j), 전선이 얼마나 길까 (l)?"를 곱해서 일정 기준보다 작으면 "이 전선은 영원히 (Immortal) 쓰일 수 있어!"라고 판단했습니다.
• 문제점: 이 규칙은 단일한 직선 전선에만 통합니다. 하지만 실제 칩의 전선은 나무 가지처럼 갈라지거나 (Tree), 그물망처럼 (Mesh) 복잡하게 연결되어 있습니다.
• 비유: 마치 복잡한 도로망에서 "차량이 많은 길만 막히지"라고 생각하다가, 실제로는 작은 골목길에서 교통 체증이 발생해 메인 도로가 막히는 경우를 놓치는 것과 같습니다. 기존 방법은 이런 복잡한 구조에서는 엉뚱한 결론을 내거나, 불필요하게 많은 전선을 "고장 날 것 같다"고 오해하여 칩을 불필요하게 두껍게 만들게 했습니다.

3. 이 논문의 해결책: "복잡한 도로망의 수리공"

이 논문은 복잡한 전선 구조에서도 정확하고 매우 빠르게 수명을 예측하는 두 가지 새로운 방법을 개발했습니다.

핵심 아이디어: "물 (원자) 의 양은 변하지 않는다"

전자가 원자를 밀어내서 한쪽으로 보낸다고 해서, 전선 전체의 원자 수가 늘어나거나 줄어드는 것은 아닙니다. 그냥 분포만 바뀝니다.

• 비유: 물탱크에 물을 퍼서 한쪽으로 옮기면, 한쪽은 비고 다른 쪽은 차지만 물탱크 전체의 물 양은 그대로입니다. 이 논문의 수학은 바로 이 '물 양의 보존' 법칙을 이용해, 전선 어디에 얼마나 스트레스가 쌓일지 계산합니다.

두 가지 새로운 방법

방법 1: 전류 흐름을 따라 걷기 (Current-Density Based)

• 방식: 전선 구조를 나무처럼 생각해서, 뿌리에서 잎사귀까지 하나씩 걸어가며 전류가 얼마나 강하게 흐르는지 계산합니다.
• 비유: 등산로를 따라 올라가며, "여기서부터 저기까지 얼마나 힘들었나?"를 하나씩 더해서 정상의 피로도를 계산하는 방식입니다.
• 장점: 직관적이고 정확합니다.

방법 2: 전압을 이용한 '순간 이동' (Voltage-Based)

• 방식: 전선 구조를 이미 설계할 때 계산해 둔 전압 (전위) 값을 그대로 가져옵니다. 전압 차이와 전선 길이를 알면, 굳이 전선을 따라 걷지 않아도 스트레스를 계산할 수 있습니다.
• 비유: 지도 앱을 켜서 "A 지점에서 B 지점까지의 거리"를 바로 보여주는 것처럼, 복잡한 길을 다 돌아다니지 않고 순간 이동으로 결과를 얻는 방식입니다.
• 장점: 가장 빠릅니다. 전선을 하나하나 따라다니는 수고를 아껴줍니다.

4. 왜 이 방법이 대단한가요?

1. 속도 (선형 시간): 전선 조각 (Segment) 의 수가 10 배가 되면, 계산 시간도 10 배만 걸립니다. 기존 복잡한 시뮬레이션은 전선이 많아질수록 계산 시간이 기하급수적으로 늘어났는데, 이 방법은 선형적으로만 늘어납니다.
   • 비유: 기존 방법은 100 개의 집을 다 찾아다니며 수리를 확인하는 방식이었다면, 이 방법은 한 번에 전체 지도를 스캔해서 문제 집을 찾아냅니다.
2. 정확도: 복잡한 그물망 구조에서도 물리 법칙을 정확히 따르므로, 기존 방법보다 훨씬 정확한 "고장 예측"이 가능합니다.
3. 실용성: 이 방법을 사용하면, 칩 설계자가 불필요하게 전선을 두껍게 만들 필요가 없어져 칩을 더 작고 저렴하게 만들 수 있습니다.

5. 결론

이 논문은 **"복잡한 칩 속 전선들의 수명을, 걷지 않고도 순식간에 정확히 예측하는 방법"**을 찾아냈습니다.

기존의 "단순한 자" (Blech 기준) 는 복잡한 현실을 제대로 반영하지 못했지만, 이 새로운 방법은 **물리 법칙의 핵심 (물 양 보존)**을 이용해 **가장 빠른 '순간 이동' 기술 (전압 기반)**로 칩의 신뢰성을 높여줍니다. 이는 앞으로 더 작고 빠른 반도체를 만드는 데 큰 도움이 될 것입니다.

기술 요약

이 논문은 심층 스케일링 기술 노드에서 발생하는 전자기이동 (Electromigration, EM) 신뢰성 문제를 해결하기 위해, 일반적인 트리 (Tree) 및 메쉬 (Mesh) 인터커넥트 구조에 대한 선형 시간 (Linear-Time) 정상 상태 분석 알고리즘을 제안합니다.

기존의 경험적 방법 (Blech 기준 및 Black's 방정식) 의 한계를 극복하고, 물리 법칙에 기반한 정확한 해를 선형 시간 복잡도로 도출하는 것이 이 연구의 핵심입니다.

다음은 논문의 상세한 기술 요약입니다.

---

1. 문제 정의 (Problem Statement)

• 배경: 전자기이동 (EM) 은 고전류가 흐르는 금속 배선에서 원자가 이동하여 공동 (Void) 이 형성되거나 단선이 발생하는 신뢰성 고장 메커니즘입니다. 특히 FinFET 기술에서 하위 금속 층에서도 EM 핫스팟이 중요한 이슈로 대두되었습니다.
• 기존 방법의 한계:
  • Blech 기준: 단일 세그먼트 (두 단자 간) 의 전류 밀도 ($j$) 와 길이 ($l$) 의 곱 ($jl$) 이 임계값보다 작으면 배선이 불사 (Immortal) 라고 판단합니다. 그러나 실제 온칩 구조는 여러 세그먼트로 구성된 트리나 메쉬 형태이며, 각 세그먼트의 전류 밀도가 다릅니다. 이러한 복잡한 구조에 Blech 기준을 적용하면 정확도가 떨어집니다.
  • Black's 방정식: 경험적 모델로, EM 취약 배선을 식별하는 데 주로 사용되지만 EM 의 물리적 메커니즘을 직접적으로 반영하지는 않습니다.
  • 물리 기반 방법의 비효율성: EM 의 물리 법칙 (전자 바람과 역압력) 을 기반으로 한 미분 방정식을 푸는 방법은 정확하지만, 수치 시뮬레이션 (예: COMSOL) 을 통해 수행되므로 계산 비용이 매우 높고 시간이 오래 걸립니다.
• 목표: 일반적인 트리 및 메쉬 구조의 모든 세그먼트에 대해 불사 (Immortality) 여부를 판단할 수 있는 선형 시간 복잡도 ($O(|V| + |E|)$) 의 정확한 분석 알고리즘 개발.

2. 방법론 (Methodology)

저자들은 EM 의 물리적 원리 (전자 바람과 역압력) 를 기반으로 한 기본 응력 (Stress) 방정식을 출발점으로 삼아 두 가지 주요 알고리즘을 제안했습니다.

A. 물리적 모델링

• 정상 상태 (Steady-State) 가정: 과도 현상이 소멸된 후, 배선 내 응력 ($\sigma$) 은 선형적으로 분포하며, 그 기울기는 전류 밀도 ($j$) 에 비례합니다 ($\frac{\partial \sigma}{\partial x} = -\beta j$).
• 질량 보존 법칙: EM 으로 인해 원자가 이동하지만, 배선 내 총 원자 수는 변하지 않습니다. 이는 배선 전체에 걸친 응력의 적분이 0 이 되어야 함을 의미합니다.
• 경계 조건: 배선 끝단 (Terminus) 에서는 플럭스 (Flux) 가 0 이어야 하며, 내부 노드에서는 인접 세그먼트 간의 응력이 연속적이어야 합니다.

B. 제안된 두 가지 알고리즘

1. 전류 밀도 기반 방법 (Current-Density-Based Method):

   • 그래프의 스패닝 트리 (Spanning Tree) 를 구성합니다.
   • 기준 노드 (Leaf node) 에서 시작하여 BFS 또는 DFS 와 같은 그래프 순회 (Traversal) 를 수행합니다.
   • 각 경로를 따라 "Blech 합" (algebraic sum of $jl$) 을 계산하여 각 노드의 응력을 도출합니다.
   • 질량 보존 법칙을 적용하여 기준 노드의 절대 응력 값을 구한 후, 모든 노드의 정상 상태 응력을 계산합니다.

2. 전압 기반 방법 (Voltage-Based Formulation):

   • 핵심 통찰: 세그먼트를 따른 $jl$ 값의 감소 (drop) 는 해당 세그먼트의 IR 강하 (IR drop) 와 직접적으로 비례합니다 ($jl = \Delta V / \rho$).
   • 기존 회로 시뮬레이션 (Nodal analysis) 을 통해 이미 계산된 노드 전압 (Node Voltages) 을 재사용합니다.
   • 그래프 순회 (Traversal) 가 필요 없이, 각 노드의 전압과 평균 전압을 이용하여 직접 응력을 계산할 수 있습니다.
   • 이 방법은 순회 과정이 불필요하여 전류 밀도 기반 방법보다 상수 계수 면에서 더 빠릅니다.

C. 메쉬 구조 처리

• 메쉬 구조에는 사이클 (Cycle) 이 존재하지만, Theorem 1에 의해 사이클 내의 응력 방정식은 선형 종속 (Linearly Dependent) 임을 증명했습니다.
• 따라서 메쉬 구조에서 임의의 한 간선 (Edge) 을 제거하여 트리 구조로 변환한 후, 트리 분석 기법을 적용하면 모든 노드의 응력을 정확히 구할 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 선형 시간 복잡도 ($O(|V| + |E|)$): 일반적인 트리 및 메쉬 인터커넥트 구조에 대한 정상 상태 EM 분석을 위한 최초의 선형 시간 알고리즘을 제시했습니다.
2. 정확한 물리 기반 모델: 경험적 Blech 기준을 대체할 수 있는, 미분 방정식의 정확한 해를 기반으로 한 폐쇄형 (Closed-form) 해를 유도했습니다.
3. 순회 없는 (Traversal-Free) 계산: 회로 시뮬레이션에서 얻은 전압 정보를 활용하여 그래프 순회 없이도 응력을 계산하는 방법을 제안하여 계산 효율성을 극대화했습니다.
4. IR 강하와 EM 의 직접적 연관성 증명: 배선 세그먼트의 IR 강하와 양 끝단 간 응력 차이가 비례한다는 것을 수학적으로 증명했습니다. 이는 IR 최적화와 EM 최적화가 밀접하게 연관되어 있음을 시사합니다.
5. 확장성: 단일 세그먼트뿐만 아니라 복잡한 트리 및 메쉬 구조, 다양한 기술 노드 (12nm, 28nm, 45nm) 에 적용 가능한 범용성을 입증했습니다.

4. 실험 결과 (Results)

• COMSOL 시뮬레이션과의 비교:
  • 제안된 방법의 결과는 COMSOL 을 이용한 수치 시뮬레이션 결과와 거의 완벽하게 일치했습니다 (오차 미미).
  • COMSOL 은 정상 상태에 도달하기 위해 장시간의 과도 해석이 필요하지만, 제안된 방법은 밀리초 (ms) 단위로 결과를 도출했습니다.
• IBM Power Grid 벤치마크 평가:
  • 기존 Blech 필터는 다중 세그먼트 구조에서 많은 오검출 (False Positive: 불사 배선을 사망으로 판단) 및 누락 (False Negative: 사망 배선을 불사로 판단) 을 발생시켰습니다.
  • 제안된 방법은 대규모 메쉬 구조에서도 빠른 속도로 정확한 불사/사망 판별을 수행했습니다.
  • 성능: 전압 기반 방법이 전류 밀도 기반 방법보다 약 1.5~1.9 배 더 빨랐습니다.
• 현대 기술 노드 (12nm FinFET, 28nm FDSOI, 45nm) 적용:
  • OpenROAD 를 통해 생성된 다양한 회로에서 테스트되었으며, 기존 Blech 기준이 다중 세그먼트 배선에서 얼마나 부정확한지 (많은 False Positive 발생) 를 재확인했습니다.
  • 제안된 알고리즘은 모든 기술 노드에서 선형 시간 복잡도를 유지하며 확장 가능함을 입증했습니다.

5. 의의 및 결론 (Significance and Conclusion)

이 논문은 EM 신뢰성 분석 분야에서 중요한 전환점을 제시합니다.

• 기존 워크플로우 개선: 기존의 느리고 부정확한 Blech 필터링 단계를 이 새로운 선형 시간 알고리즘으로 대체함으로써, 설계 초기 단계에서 EM 취약 배선을 빠르고 정확하게 선별할 수 있게 되었습니다.
• 계산 효율성: 수 시간에서 수 일 걸리던 상세 시뮬레이션을 대신하여, 수 초 내에 전체 칩의 EM 상태를 평가할 수 있어 대규모 설계에 적합합니다.
• 통합 최적화 가능성: EM 제약 조건을 IR 강하 (전압) 변수로 직접 변환할 수 있음을 보였으므로, 향후 IR drop 과 EM 을 동시에 고려한 전력 그리드 최적화 (Power Grid Optimization) 문제 해결에 강력한 도구가 될 수 있습니다.

요약하자면, 이 연구는 물리 법칙에 기반한 정확한 EM 분석을 선형 시간 복잡도로 가능하게 함으로써, 차세대 반도체 설계의 신뢰성 보장을 위한 필수적인 도구로 자리 잡을 것으로 기대됩니다.