[Paper] Interconnect Stack Parameter Optimization Using Genetic Algorithm [1/2]

 

이번 포스팅은 제 학회 논문이자 학위 논문인 Interconnect Stack Parameter Optimization Using Genetic Algorithm 대해서 설명을 해보려고 합니다.

학위 논문 발표를 토대로 작성하는 거라서 논문을 읽는 것보다는 편할 것 같아요.

내용이 생각보다 많아져서 포스팅을 두 개로 나눠서 올려야 할 것 같아요 ㅎㅎ

---

 

논문의 제목을 보면 어느 정도 유추할 수 있지만, 이 논문은 interconnect stack이 가지고 있는 여러 layer에 대한 width, length, space 등과 같은 parameter들을 genetic algorithm을 사용해서 최적화하는 내용입니다.

 

먼저, 목차는 다음과 같습니다.

• 서론
• 배경 지식
• 제안 방법
  • 매개변수 후보 선택 (candidate selection)
  • 매개변수 필터링 (parameter filtering)
  • 초기 샘플링 (initial sampling)
• 실험 결과

 

---

서론

Interconnect stack은 metal stack이라고도 불리며, 아래의 그림처럼 여러 metal layer와 via layer로 구성됩니다.

여기서 metal은 수평으로 회로를 연결하는 역할을 하며, via는 수직으로 각 요소들을 연결하는 역할을 합니다.

실제로 5nm 공정에서는 약 10 ~ 15개의 metal layer와 via layer가 사용된다고 합니다.

 

Interconnect stack

 

이러한 interconnect stack에는 아래의 그림의 metal width, space, thickness 등과 같은 다양한 parameter가 존재합니다.

대부분의 parameter는 공정 단계에서 결정되기 때문에 설계 단계에서 이들을 바꾸려면 큰 비용이 발생합니다.

하지만, 큰 비용을 들이지 않고 변경할 수 있는 parameter도 존재하는데 대표적으로 metal width와 space입니다.

그래서 이 논문에서는 width와 space를 주로 다룹니다.

 

Interconnect stack parameters

---

배경 지식

Interconncet stack parameter는 직접적으로 wire resistance와 capacitance와 관련이 있습니다.

어떻게 관련이 있는 지를 간단한 wire res and cap 수식을 통해서 설명을 할텐데, 이해를 돕기 위해 아래의 그림을 토대로 설명하겠습니다. 먼저, 수식의 약자들은 다음과 같습니다.

• W: metal width
• S: metal space
• L: metal length
• T: metal thickness
• H: metal-to-substrate distance (height)

 

Interconnect stack example

 

Wire res는 간단하게 다음의 식을 따릅니다.

$$  R=\frac{\rho \times L} {W \times T} $$

이 식을 통해서 wire res는 length에 비례하며, width와 thickness에 반비례하다는 것을 유추할 수 있습니다.

이 논문에서는 width만 다루기 때문에 메인은 width에 있다는 것을 기억해 주세요.

 

다음으로 wire cap은 다음의 식을 따르는데, 이것은 위 그림처럼 세 개의 metal이 놓여 있을 때, 가운데 위치한 metal이 갖는 cap을 수식화한 것입니다.

설명을 하자면 아래의 substrate에 의한 cap이 1st term이고, 양 옆의 metal에 의한 cap이 2nd term입니다.

$$ \frac{C_3} {E_{ox}} = \frac{C_1} {E_{ox}} + 2 \begin{bmatrix} 0.03\frac{W}{H} + 0.83 \frac{T}{H} - 0.07 \frac{T}{H}^{0.22}   \end{bmatrix} \frac{S}{H}^{-1.34} $$

여기서 중요한 부분은 cap이 width에 비례하고, space에 반비례하다는 것입니다.

 

사실 "R, C를 줄이기 위해 space만 늘리면 되는 것이 아닌가?"라는 의문이 들 수 있는데, 이는 물리적인 제약 사항에 의해 큰 이득을 볼 수 없습니다. 그렇기에 이러한 RC trade-off 중 최적의 width, space를 찾는 것이 필요합니다.

 

이제, RC관점에서 더 나아가 circuit delay와 power의 관점으로 확인해 보면 interconnect parameter가 회로에 미치는 영향을 직접적으로 확인할 수 있습니다.

 

먼저, 아래의 회로를 Elmore delay 수식으로 delay를 정의하면 다음과 같습니다.

$$ Elmore\_delay=\sum_{n}^{i} R_i \sum_{k\_downstream\_of\_i}C_k$$

Elmore delay는 해당 node의 R과 해당 node까지의 C의 합을 곱한 형태로 수식화됩니다.

따라서 이는 R과 C가 delay에 미치는 영향에 차등은 있지만 동일하게 비례한다는 것을 알 수 있습니다.

 

 

 

Circuit power consumption의 관점에서 보기 위해서 아래의 dynamic power 수식을 참고해 보겠습니다.

$$ Dynamic\_power=\alpha C_{load} V^2_{dd} f $$

이 수식에는 RC의 영향을 직접적으로 확인할 수 있는 요소인 C가 포함되며, delay와 반비례 관계에 있는 frequency이 포함됩니다.

C의 경우는 단순히 낮추는 방향쪽으로 최적화를 하면 되지만, freq.의 경우는 delay를 줄이면 커지기 때문에 circuit speed와 trade-off 관계를 가집니다.

 

여기까지는 간략한 예시로 parameter가 회로에 미치는 영향을 체크한 것이고, 실제 회로에서는 더욱 복잡한 문제로 작용합니다. 따라서 최적의 interconnect stack parameter 조합을 빠르게 선정하는 방법이 필요합니다.

 

이 논문에서는 최적화를 위한 방법으로 genetic algorithm을 사용합니다.

Genetic algorithm은 이미 꽤 많은 곳에서 사용된 방법이므로 간략하게 소개하겠습니다.

이것은 자연계 생물의 유전과 진화 메커니즘을 모델화한 알고리즘입니다.

환경 적합도가 높은 개체의 유전자가 다음 세대로 전달이 되어 그 환경에 가장 최적화된 개체가 탄생하는 것입니다.

 

이를 interconnect stack parameter 조합 선정 문제에 적용하면 아래 그림과 같은 데이터 구조를 가집니다.

 

Data architecture

 

이 논문에서 쓰이는 생물학적 명칭의 의미는 다음과 같습니다.

• 유전자 (gene): 각 parameter value (ex. metal3 width, metal3 space, etc.)
• 염색체 (chromosome): parameter set
• 모집단 (population): 다수의 parameter set
• 세대 (generation): 프로세스 반복 횟수

이러한 데이터 구조를 기반으로 최적의 성능을 내는 염색체를 찾는 과정을 아래 그림처럼 수행합니다.

 

 

위의 과정을 수행하기 전에 먼저 적합도 함수를 설정하고 시작합니다.

적합도 함수는 단순하게 최적화의 objective라고 생각하시면 되는데,

예를 들어 나는 delay를 줄여서 circuit speed를 높이겠다! 라고 생각하면, 다음과 같이 설정할 수 있습니다.

$$ Fitness\_for \_ minimize=delay$$

실제로는 여러 objective를 weigth sum을 해서 다음과 같이 사용합니다.

$$ Fitness \_ for \_ minimize=\alpha delay + \beta power $$

이렇게 각 parameter set의 성능을 평가할 기준을 정하고 genetic alogrithm을 수행합니다.

 

과정은 다음과 같습니다.

• 부모 선택 (parents selection)
  • 적합도가 높은 염색체의 유전자를 다음 세대로 전달합니다. 위 그림에서는 두 번째 염색체가 가장 적합도가 높고, 뒤를 이어 첫 번째, 세 번째가 높다고 생각하시면 됩니다.
• 교차 (crossover)
  • 둘 이상의 염색체들에 기준 지점을 설정하고, 지점 뒷 부분을 서로 교환합니다. 위 그림의 1, 2번째 염색체는 중앙을 기준 지점으로 정하고, 그 위를 서로 교환했습니다.
• 돌연변이 (mutation)
  • 각 유전자마다 mutation이 발생될 확률이 존재하며, mutation이 발생되면, 기존의 값과 전혀 관계없는 지극히 랜덤한 값으로 변합니다.

이렇게 새로운 세대가 생기고, 이러한 과정을 반복합니다.

그렇게 하다보면 기존의 방법들보다 빠르고 정확한 최적화가 가능합니다.

 

다음은 실제로 제가 제안하는 방법들에 관한 것인데 너무 길어져서 다음 포스팅으로 넘기도록 하겠습니다.