Related to 강화학습, 산업의 난제에 도전하다! - ASIC 반도체 설계 (Floorplan) 자동화 (Naver Deview 21 발표 영상) 주문형 반도체 (ASIC) Floorplan 자동화 - Part I 프로젝트 소개 FIGURE ABSTRACT 위 애니메이션은 약 1500 iterations 정도의 학습 과정을 보여주고 있습니다. 녹색의 큰 사각형은 Macro, 청색의 작은 사각형은 Standard Cell Cluster를 나타냅니다. 어느 정도 학습이 진행된 후, 사각형의 움직임이 눈에 띄게 줄어들며 안정된 모습을 보여줍니다. 에이전트는 Macro는 Chip Canvas 영역의 바깥쪽, Standard Cell Cluster는 안쪽에 위치시키도록 학습합니다. 위 실험을 하기까지의 과정에 대한 자세한 설명은 본 포스팅을 참고해주세요. Introduction 본 프로젝트의 목적은 강화학습을 이용해 주문형 반도체 (Application-Specific Integrated Circuit, ASIC)의 제조 공정 중 하나인 Floorplan 단계에서의 배치 최적화 문제를 해결하는 것입니다. 주요 기술 내용은 지난 2020년 6월 구글에서 발표해 Nature 등재로 화제가 되었던 A graph placement methodology for fast chip design[1][2] 논문에 기초를 두고 있습니다. Floorplan은 트랜지스터가 아닌 블록 단위의 배치를 하는 과정이며, 수십~수백만 개 단위의 트랜지스터와의 연결성을 고려하며 블록들을 배치해야 하기 때문에 시간이 많이 소요되는 작업 중 하나입니다. 본 포스팅을 통해 약 5개월간 경험한 Floorplan 문제의 이해부터 솔루션 구현까지의 과정을 공유드리려고 합니다. 먼저 본문에서 자주 언급하는 주요 용어들과 뜻입니다. Macro: Floorplan 과정에서 배치되는 소자의 종류 중 하나, 메모리 구성 요소로 Standard Cell 대비 훨씬 큰 크기를 가지고 있음 Standard Cell: NAND, NOR, XOR과 같은 논리 게이트, 크기가 매우 작으며 수십~수백만 개 단위의 소자가 사용됨 Net: Macro와 Standard Cell들의 연결 관계를 정의하는 Wire Netlist: Net들의 집합체 Is this a Real Problem? Floorplan 과정은 일반적으로 사람의 손에 의해 수행됩니다. Chip Canvas라는 2차원의 연속 공간에서 복잡한 연결 관계를 고려하며 수백 개에 달하는 Macro들을 배치하는 작업은 큰 탐색공간(Search Space)으로 인해 높은 복잡도를 가지고 있는 문제입니다. 또한, 직접 Macro를 배치한 후 그 뒤의 설계과정을 전용 Electronic Design Automation(EDA) Tool을 통해 수행하고 나서야 배치에 대한 평가를 할 수 있습니다. 만약 평가 결과가 좋지 않다면, Macro를 배치하는 작업부터 다시 수행해야 하므로 기술자의 숙련도에 따라서 필요한 시간이 크게 달라지곤 합니다. 또한 숙련된 기술자라도 며칠에서 몇 주의 시간을 소요하기도 합니다. 현업에서 종사하시는 전문가분들과의 협업을 통해 알게 된 Floorplan의 주요 문제점은 아래와 같이 정리할 수 있습니다. Macro의 배치를 수작업으로 진행 후, EDA Tool을 이용해 결과를 확인하는 작업을 여러 번 반복해야 하는 만큼 시간이 오래 걸림 사람의 경험이 매우 중요하기 때문에, 숙련도에 따라 품질과 요구되는 시간의 편차가 큼 이 포스팅에서는 문제정의와 해결 방법 관련된 기술적인 내용을 중점적으로 설명합니다. (연구 배경 및 의의에 대한 더욱 자세한 설명은 ASIC-Chip-Placement 1부을 참고해주세요.) How to solve? 기존의 배치 최적화 문제에 적용되는 많은 Classic한 방법들(Simulated Annealing[3], Genetic Algorithm[4])은 좋은 성능을 보여주지만, 새로운 문제를 만나면 같은 도메인이라도 초기 상태부터 다시 최적화를 진행해야 한다는 단점이 있습니다. 한번 학습된 모델이 다르게 정의된 문제에서 별다른 추가 학습 없이 어느 수준 이상의 해답을 찾는 것을 일반화(Generalize)라고 합니다. 많은 연구[8][9]에서 인공 신경망을 적용한 강화학습은 강력한 Generalize 수준을 보여주고 있습니다. 강화학습의 이러한 강점을 이용한다면 여러 구조와 크기의 Netlist에 대해서 추가적인 학습 없이 또는 최소한의 학습 시간만을 가지고 좋은 배치를 찾을 수 있습니다. (예: 소자 5개, 10개로 구성된 Netlist 들의 배치를 학습하여 20개 규모의 Netlist에 대해서도 일정 수준 이상으로 배치) 저희는 이점에 주목하여 강화학습을 주요 알고리즘으로써 사용했습니다. 본 포스팅에는 최종 목표(Gneneralization)에 도달하기에 앞서, 강화학습을 사용한 단일 Netlist의 Floorplan 학습 과정을 소개합니다. * 배치 최적화 문제: 대상의 물리적인 위치를 통해 목표함수를 최적화하는 문제 강화학습이란? 강화학습은 에이전트(Agent)가 환경(Environment)과 상호작용에서의 시행착오(Trial and Error)를 통해 더 높은 보상(Reward)을 얻을 수 있는 행동(Action)들을 학습하는 알고리즘입니다. 환경은 에이전트의 행동마다 다음 상태(State)와 보상을 반환하며, 에이전트는 전달받은 상태를 고려해 다시 행동을 결정하게 됩니다. 강화학습은 Markov Decision Process[5] (MDP)에 기반해, 차례로 어떤 의사결정(Decision Process)을 해야 하는 문제들에 많이 적용됩니다. [그림 ] - Markov Decision Process 결국 에이전트는 학습하는 과정 중에 Sampling 되는 모든 에피소드(Episode)에 대한 보상의 기댓값을 최대화하기 위한 행동들을 학습합니다. 당연하게도, 강화학습은 그 구성 요소들(에이전트, 상태, 행동, 보상)의 정의방법에 따라 다른 학습양상을 보여줍니다. 아래에서는 저희가 환경과 에이전트를 어떻게 정의했는지 설명하겠습니다. * 에피소드: 에이전트가 일련의 행동들을 수행하고 보상들을 얻는 (상태, 행동, 보상)의 Sequence, 에피소드가 종료되면 환경은 초기상태로 리셋된다. Technical Overview 먼저 환경과 모델이 어떻게 동작하는지 전체적인 흐름을 설명하고 이후 강화학습의 각 요소에 대해서 구체적으로 정의하겠습니다. [그림 ] - Technical Overview 환경 정의 에이전트는 환경의 주요 구성요소인 상태, 행동, 보상을 통해 환경과 상호작용하며 학습합니다. 그러므로 에이전트를 효과적으로 학습시키기 위해서는 각 요소를 적절히 정의해야 합니다. 배치 최적화에서 환경의 각 요소는 아래와 같은 역할을 수행해야 합니다. 상태: 행동을 결정하기 위한 판단에 필요한 정보를 담고 있어야 함 행동: 더 좋은 Chip Design을 얻을 수 있게 하는 행동의 집합 보상: Chip Design의 품질 저희가 설계한 환경은 아래와 같은 순서로 진행됩니다. 빈 Chip Canvas인 초기 상태에서 시작하여 행동 한 번에 소자 한 개를 배치 마지막 배치 외의 모든 배치에 대해 0의 보상을 반환 1~2번 반복 후, 모든 소자들의 배치가 완료되면 보상을 계산 1~3번 반복하며 학습 진행 상태, 행동, 보상 정의을 정의하기에 앞서 모델 설계를 먼저 알아보도록 하겠습니다. 모델 설계 [그림 ] - 모델의 역할 뉴럴넷 모델은 환경으로부터 전달받은 상태의 정보들을 인식해 행동을 결정할 확률분포를 계산하는 역할을 수행합니다. 이 프로젝트의 경우, 소자의 물리적 특성과 연결정보를 바탕으로 이미 배치된 소자들에 대한 정보와 앞으로 배치할 소자들에 대한 정보를 알아야 합니다. 이를 구현하기 위해, Graph Neural Network(GNN)과 Convolutional Neural Network(CNN)으로 이루어진 모델을 설계했습니다. 각각의 목적은 아래와 같습니다. GNN: Graph 형태의 Netlist의 정보를 효과적으로 Embedding하기 위해 선택했습니다 CNN: 배치가 완료된 소자들의 지역적인 정보를 효과적으로 학습할 수 있는 CNN 구조를 선택했습니다 모델의 각 구조에 대한 자세한 설명은 Model Description 장에서 드리도록 하겠습니다. 강화학습 환경 정의하기 State Representation 상태는 현재 환경이 어떤 상태에 있는지에 대한 정보를 담고 있습니다. 상태는 에이전트가 좋은 행동을 결정하기 위해 도움이 되는 정보들을 전달해야 합니다. 칩 설계의 전문가분들이 소자들의 연결 관계와 물리적 특성을 고려해 배치하는 것에 착안하여 에이전트가 다음 행동을 결정하기 위해 필요한 정보를 아래와 같이 정의했습니다. 소자들 간의 연결 관계 각 소자의 물리적 정보 (width, height, is_macro, n_pins etc.) 이번에 배치할 소자의 정보 지금까지의 배치 정보 각 소자들 간의 연결 관계가 아래와 같은 Hypergraph의 형태를 띠고 있는 만큼, 소자들의 물리적 특성들을 Node Features로 정의할 수 있습니다. * Hypergraph: 한 Edge에 둘 이상의 Vertex가 연결되어 있는 그래프 구조 [ 그림 ] - Hypergraph 예시 (출처: Wikipedia ) 수백개 단위의 Macro를 배치하는 것에 비해, 수십~수백만 개 단위의 Standard Cell들을 배치하는 일은 굉장히 높은 복잡도를 가지고 있습니다. Standard Cell을 배치하는 과정을 간소화 하기 위해 소자들을 Clustering 합니다. Clustering을 진행하면 배치하려는 대상의 개수가 줄어들어 문제 복잡도가 감소합니다. 저희는 Hypergraph를 graph로 변환할 때 발생하는 정보손실을 최소화하기 위해 Hypergraph Clustering Algorithm인 hMETIS[6] 알고리즘을 사용했습니다. 추후 배치 과정에서 한 Cluster에 속해있는 소자들을 묶어 하나의 독자적인 소자로 취급합니다. Action Representation 행동은 에이전트가 상태의 정보들(소자들의 물리적 특성, 현재 배치상태 등)을 이용해 현재 배치할 소자를 어느 위치에 둘 것인지 결정짓는 역할을 합니다. 에이전트가 얻는 보상을 최대화하기 위해서는 충분한 탐험(Exploration)이 필요합니다. 탐험을 효율적으로 하기 위해서는 적절한 크기의 탐색공간을 정의해야 합니다. 저희는 이러한 점들을 고려해 연속공간의 Chip Canvas를 2차원 Grid의 이산 공간으로 정의했습니다. 에이전트가 Neural Network로부터 얻어진 확률분포에서 특정 Grid Cell을 선택하면 배치될 소자의 중앙이 해당 Grid Cell의 중앙에 위치하도록 구현했습니다. * Grid Cell: 2차원 Grid에서 한 칸에 해당하는 단위 [그림 ] - Action Canvas를 Grid로 정의하면 탐색공간을 줄이면서 배치 결과를 평가하기 위한 Approximated Metric을 단순하게 정의할 수 있다는 장점이 있습니다. Grid로 정의할 때 고려되어야 할 아래 issue들을 어떻게 해결했는지는 APPENDIX를 참고해주세요. A.1. Grid Cell Size Decision A.2. Invalid Action Masking Reward Representation 보상은 에이전트에게 수행한 행동이 얼마나 유익한지를 알려주는 중요한 요소입니다. 일반적으로 ASIC의 Floorplan 결과는 ICC2와 같은 전용 EDA Tool을 사용하여 측정됩니다. Floorplan 이후의 배치 결과를 평가하기 위해 EDA Tool에서 수행하는 추가 설계과정은 보통 수 시간이 소요됩니다. 강화학습은 다량의 샘플을 통해 학습하는 방법이기 때문에 계산 속도를 고려했을 때 Tool의 결과를 직접적으로 보상으로써 정의하기에는 다소 무리가 있습니다. 그렇기 때문에 동일 시간 내에 더 많은 Sample을 확보하기 위하여 빠른 시간 내에 배치결과의 품질을 근사하는 함수를 설계해야 합니다. 배치결과의 품질을 적절히 근사하려면 먼저 좋은 배치가 무엇인지를 알아야 합니다. 산업에서는 일반적으로 PPA (Performance, Power, Area)라는 기준들을 사용합니다. 각 항목에 대응되는 효과는 아래와 같습니다. Performance - 높은 클럭 주파수(Hz) Power - 적은 전력 소모 Area - 작은 Chip Canvas 에이전트의 보상함수로 근사함수를 사용하기 위해서는 위의 3가지 사항이 모두 고려되어야 합니다. 언뜻보면 소자들을 가깝게 배치하면 데이터를 전달하는 Path의 길이가 짧아지면서 더 높은 Power, Performance와 더 낮은 Area를 얻을 수 있으리라 생각할 수 있습니다. 하지만, 소자들을 배치할 Chip Canvas에는 Routing Resources라는 것이 존재합니다. 이 말인즉슨, 소자끼리 Data를 주고받을 Routing Path가 필요한데 이를 지원하는 Routing Resources가 한정적이라는 것입니다. 그래서 소자들을 무작정 가깝게 배치해 단위 구역에 제공되는 Routing Resources보다 많은 Routing Path가 생기면 아래 그림처럼 다른 쪽으로 우회해서 신호를 전달해야 합니다. [그림 ] - Routing Detour 위의 그림에서 Macro 2와 Standard Cell 5의 가장 짧은 Routing Path가 적색 선입니다. 하지만 적색 영역에 너무 많은 Routing Path가 집중되어 있어 실제 신호 전달 시에는 녹색 선으로 우회해서 신호가 전달됩니다. 이러한 예시를 통해 우리의 목표를 아래와 같이 정의할 수 있습니다. '소자들의 거리(Wire Length)는 최대한 가깝게 하되, 한곳에 너무 많은 Routing path(Congestion)들이 몰리지 않게 !' 위의 목표를 생각해 봤을 때, 배치 최적화 문제는 소자들의 위치는 최대한 가까워야 하지만, 또 너무 근접하면 안 되는, Multi-objective Optimization Problem 입니다. 이를 달성하기 위해 설계한 보상함수는 아래와 같습니다. [R_(p,g)=-\alpha \cdot WireLength(p,g) - \beta \cdot Congestion(p,g) \qquad \text(S.t. ) \text(density*)(p,g) \leq \text(max)\text(density)] * Density: 단위면적에 배치되는 소자들의 밀도 Wire Length는 소자들을 가깝게 배치해주기 위한 역할, Congestion은 Routing Path들이 한곳에 너무 집중되지 않게 하기 위한 역할을 합니다. 아래 내용에서 각 항목이 어떻게 계산되고 적용되는지 설명합니다. Wire Length 계산복잡도를 줄이기 위해 Wire Length를 근사한 Half-Perimeter Wire Length(HPWL)를 사용합니다. 모든 Net에 대하여, 각 Net에 속해있는 소자들에 대해 경계 상자를 그린 후, 그 둘레의 절반을 Wire Length로 근사하는 것입니다. HPWL은 가장 일반적으로 사용되는 Wire Length 추정 모델입니다. 계산이 매우 간단하고 소자의 Pin 수가 2 또는 3인 Net에 대해서 직교 Steiner Tree*를 사용해 얻어진 길이와 정확히 일치한다는 장점이 있습니다. 수식으로 표현하면 아래와 같습니다. * 직교 Steiner Tree: Edge끼리 직각을 이루는 Steiner Tree, 소자들의 Wire Length를 추정할 때 가장 많이 쓰이는 방법 중 하나. [\begin(aligned) HPWL(i) = (\max(b\in i)(x_b) - \min_(b\in i)(x_b) + 1) \ + (\max_(b\in i)(y_b) - \min_(b\in i)(y_b) + 1) \end(aligned)] [그림 ] - HPWL 계산 왼쪽의 그림에서 Routing Path의 색깔이 각기 다른 Wire를 나타낸다고 했을 때, HPWL은 아래와 같이 계산됩니다. [HPWL(Red)=(2 - 1 + 1) + (2 - 1 + 1) = 4 \ HPWL(Green)=(4 - 1 + 1) + (1 - 1 + 1) = 5 \ HPWL(Yellow)=(3 - 1 + 1) + (4 - 1 + 1) = 7] 이렇게 전체 Wire Length의 근사치는 4 + 5 + 7 = 16이 됩니다. 이러한 계산방식으로 Net들의 Wire Length를 구합니다. Example Code def calculate_hpwl(net: Net) -> float: """Calculate HPWL given Net.""" min_row, min_col, max_row, max_col = get_boundary_coordinate_of_net(net) hpwl = (max_row - min_row + 1.0) + (max_col - min_col + 1.0) return hpwl Congestion Congestion은 Routing Path들이 특정 지역에만 모이지 않게 하기 위해 적용됩니다. 전용 Tool을 이용해야만 정확한 측정이 가능한 지표로써, 저희가 환경 설계 과정에서 굉장히 많이 고민했던 부분이기도 합니다. Congestion은 특정 구역에서 제공되는 Routing Resources (supply)와 해당 위치에 놓인 Net의 Routing Path (demand)로 정의됩니다[7]. Horizontal과 Vertical의 Routing Resources는 독립적으로 고려됩니다. [그림 ] - Congestion 정의[7] Supply는 저희가 갖고 있는 데이터로는 측정할 수 없습니다. 따라서 Supply는 모두 일정하다고 가정하였습니다. 이러한 가정하에서 Congestion은 Demand에 의해 결정됩니다. 이러한 점을 고려해, 저희는 아래와 같이 계산한 Demand의 추정치를 Congestion 값으로 사용합니다. [그림 ] - Congestion 계산 과정 Example Code def accumulate_local_congestion( global_congestion_map: np.ndarry, net: Net ) -> None: """Accumulate local congestions into the global congestion map."""

get edges through MST or Steiner Tree

edges = get_edges(net)

for edge in edges: # Calculate all path number to source / target for all grid cells. paths = get_paths(two_pnt_net) # Calculate partial congestion map horizontally and vertically congestion_maps = get_congestion_map(paths) global_congestion_map += congestion_maps 보상 함수 설계 시 고려되어야 할 Issue들은 아래 APPENDIX에 정리했습니다. B.1. Normalization & Reward Coefficient B.2. Invalid Episode Handling B.3. Convolution Filter Model Description 모델은 환경으로부터 전달받은 상태정보들을 활용해 행동을 결정하기 위한 확률분포를 계산합니다. State Representation에서 설명해 드린 것처럼 좋은 행동을 얻기 위해서 Netlist의 연결 구조와 현재 배치 상태 등을 인식해야 합니다. 이를 위해, GNN과 CNN으로 이루어진 2-Stage의 모델을 설계했습니다. GNN은 Netlist 정보를 Embedding 하고, CNN은 앞서 Embedding 된 정보와 현재 배치 상태에 대한 정보를 활용해 행동에 대한 확률분포를 계산합니다. 대부분의 GNN 모델들은 Ordinary Graph*를 Input Data로써 정의합니다. 그러므로, 범용적으로 쓰이는 GNN 모델들을 사용하기 위해 Hypergraph 형태의 Netlist를 Ordinary Graph로 바꿔주는 전처리를 진행합니다. 아래에서는 전처리 과정을 포함해 2-Stage 모델에 대해 설명합니다. *