문제 소개

안녕하세요. 마키나락스 Combinatorial Optimization Problem(이하 COP)팀입니다. 저희는 산업 현장에서 효율 개선이 필요한 부분을 찾고, 여러 프로젝트를 통해 문제들을 해결하고 있습니다. 이러한 방향성의 일환으로 2021년 5월부터 약 1년 반에 걸쳐 주문형 반도체(ASIC) floorplan 자동화 프로젝트를 진행하였습니다.

재작년 12월에는 저복잡도 소자 배치 문제에 대해 강화학습을 어떻게 적용했는지 설명드렸습니다.(Floorplan 자동화 - Part I, Part II). 이번에 프로젝트가 성공적으로 끝나게 되면서 그에 대한 결과를 기쁜 마음으로 공유드리려고 합니다. 다양한 시행착오를 통해 더 복잡한 문제에서 반도체 설계 전문가들의 결과보다 더 적은 시간 내에 더 좋은 성능을 갖는 배치를 생성하는데 성공했습니다. 본 포스팅에서는 보다 복잡하고 현실에 더 가까운 문제에 도전하며 저희가 어떻게 목표를 달성할 수 있었는지에 대해 소개드리겠습니다.

[그림1] - 강화학습을 통한 소자들의 최적 위치를 학습하는 과정. 약 3000 iteration 동안 학습했으며, 네모난 점들은 직사각형 모양의 macro 소자들의 중앙을 나타냅니다. 연결관계가 강한 소자들은 같은 색으로 표시했습니다. 학습이 진행됨에 따라서 연결관계가 강한 macro들이 근거리에 배치 된 것을 볼 수 있습니다.

Application Specific Integrated Circuit(이하 ASIC) 이란 수요자에 따라 주문 제작되는 반도체입니다. 4차 산업혁명의 흐름에 힘입어 많은 종류의 ASIC에 대한 수요가 증가하였습니다. 이에 따라 ASIC을 효율적으로 설계할 필요성이 점차 증가하고 있습니다.

ASIC의 설계 과정 중 physical design은 소자들의 물리적 위치를 결정하는 단계로 복잡한 경우 수 개월이 걸릴 정도로 많은 시간을 요구합니다. Physical design은 canvas위에 소자를 배치하고 연결하여 물리적 설계도를 그리는 작업으로 [그림 2]와 같은 과정을 통해 진행됩니다. ASIC의 소자들은 크기가 크고 복잡한 연산을 수행하는 macro와 비교적 단순한 연산을 수행하는 standard cell* 로 나눌 수 있습니다. Macro를 배치하는 과정은 floorplan이라 하고, standard cell을 배치하고 연결하는 과정을 Placement & Routing(이하 P&R††)이라 합니다. P&R은 일반적으로 자동화 솔루션을 제공하는 Synopsys사의 ICC2 등의 Electronic Design Automation (EDA)툴을 이용해 진행됩니다. 이러한 EDA툴들은 성능이 충분히 검증되어 널리 사용되고 있습니다.

* 반도체 소자는 크게 MACRO와 STANDARD CELL로 나눌 수 있습니다. MACRO는 사전에 설계된 큰 단위의 소자를 말합니다 (RAM / CPU 등). 대체로 백만개 이상의 트랜지스터를 포함하고 있어 큰 크기를 가집니다. 반면 STANDARD CELL은 LOGIC을 이루는 작은 단위 소자들이라고 할 수 있습니다. MACRO에 비해 굉장히 작은 크기를 가지지만, 백만개/천만개 단위의 많은 수의 STANDARD CELL들이 P&R 과정에서 배치됩니다.

†† PLACEMENT & ROUTING의 약자로써 MACRO를 배치하는 FLOORPLAN 단계 이후 진행됩니다. 많은 수의 STANDARD CELL들을 모두 배치하고 이 소자들을 연결하기 위한 ROUTING을 진행하는 과정입니다.

P&R과는 다르게 Macro들을 배치하는 floorplan에 대해서는 아직 충분한 성능과 속도를 보장하는 자동화 솔루션이 없습니다. Floorplan 과정에서는 이후에 배치될 모든 소자들의 위치와 연결을 예측해야 하므로 최적의 배치를 찾는 자동화 솔루션을 만드는 것이 현실적으로 어렵기 때문입니다. 이에 실제 산업 현장에서는 엔지니어가 본인의 경험에 따라 직접 floorplan을 수행해야 합니다.

[그림2] - Physical design 과정

엔지니어는 floorplan과 P&R의 과정을 거쳐 설계를 마무리한 뒤, 결과를 분석해 목표 성능을 달성하기 위한 수정 작업을 반복합니다. 규모가 큰 반도체 디자인의 경우 P&R을 1회 수행하는데만 10일 이상이 소요되기도 합니다. 따라서 floorplan과 P&R 등의 과정 몇 번만 반복해도 설계에 굉장히 많은 시간이 소요됩니다. 또한 현재의 floorplan은 엔지니어의 경험이나 실력에 크게 의존하고 있기 때문에 작업자에 따라 수행 시간 및 배치 품질의 변동성이 크다는 문제점도 있습니다.

최근 산업계에서 (Synopsys, Kadence, Google 등) AI 기술을 활용해 floorplan을 자동화하려는 연구가 활발히 진행되고 있습니다[1, 2]. 최적의 floorplan을 생성할 수 있는 자동화 솔루션이 있다면 설계시간을 크게 단축시킬 수 있을 뿐만 아니라, 설계 결과의 편차를 줄일 수 있어 예측 가능한 작업흐름을 구성할 수 있습니다. COP팀에서도 이러한 연구의 일환으로 강화학습을 사용한 floorplan 자동화 문제에 도전했습니다.

강화학습을 활용한 솔루션

저희는 floorplan 과정을 자동화하기 위해 강화학습을 활용했습니다. 강화학습은 머신러닝 방법의 하나로 에이전트라는 행동의 주체가 설정되어 환경과 상호작용하며 피드백에 따라 행동을 개선시키는 알고리즘입니다. 본 프로젝트에서 설계된 에이전트는 macro를 배치하고 평가하기를 반복하면서 학습을 진행해 나갑니다.

강화학습을 활용한 floorplan 문제에서 학습 시간의 가장 큰 병목은 에이전트의 macro 배치를 평가할 때 발생합니다. EDA 툴을 통해서 하나의 macro 배치를 평가하는 데에는 netlist에 따라서 일주일이 넘게 걸릴 수 있습니다. 따라서 빠른 시간 안에 학습을 완료하기 위해서는 생성된 macro 배치를 평가하는 시간을 줄이는 것 이 중요합니다. 이를 해결하기 위해서 EDA 대신 빠른 시간 내에 macro 배치를 평가할 수 있는 metric을 활용했습니다.

에이전트를 학습시키기 위해 설계한 환경은 [그림 3]과 같습니다. 여기에 자체적으로 설계한 standard cell cluster 배치 방식과 평가 함수를 적용하여 위에서 설명한 빠른 시뮬레이션이 가능했습니다. 이 환경 속에서 강화학습 에이전트는 macro를 여러 형태로 배치해보며 좋은 결과를 만들기 위한 전략을 스스로 학습합니다. 에이전트가 만들어낸 결과는 ASIC의 성능과 연관된 다음 3개의 metric으로(Half-Perimeter WireLength(HPWL), Routing Congestion, Cell Density) 측정되며 에이전트는 이를 보상으로 받아들입니다.

[그림3] - 강화학습 솔루션 구조

학습된 에이전트를 이용해 연결관계를 고려한 배치를 얻을 수 있습니다. 에이전트가 생성한 배치는 별도의 후처리 작업[부록]을 거치게 되고 EDA툴을 이용해 최종 배치의 성능을 평가합니다. 실제 현업에서 엔지니어가 수행하는 작업과는 다르게 EDA툴을 최종배치의 평가를 위해 단 1회 수행하기 때문에 많은 시간을 줄일 수 있습니다.

강화학습 vs. Human Expert

저희가 제안한 알고리즘의 성능을 평가하기 위해, 강화학습 기반 알고리즘의 배치 결과와 실제 엔지니어의 똑같은 반도체 디자인을 이용해 floorplan 작업을 수행한 결과를 비교하였습니다.

문제 준비

저희는 알고리즘의 성능을 검증하기 위해 ASIC 디자인의 규모에 따라 단계적으로 세 가지의 목표를 설정하였습니다[그림 4]. 고복잡도의 경우 저사양 pc에 들어가는 칩 정도의 복잡도를 가지고 있습니다.

[그림4] - 단계별 목표

성능 측정 방식

Floorplan은 일반적으로 엔지니어의 경험에 기반해 진행되므로 엔지니어의 경험에 따라 수행 속도 및 품질에 편차가 생기게 됩니다. 평가 결과에 대한 신뢰도를 높이기 위해 각 복잡도별로 서로 다른 4개의 floorplan 결과를 만들고 평가를 진행하였습니다. Human expert의 경우 2~7년차 엔지니어 4명이 각 복잡도 별 설계를 진행하였습니다. 그리하여 각 복잡도별로 4개의 결과, 총 12개의 floorplan 결과를 얻었습니다. 강화학습의 경우 각 복잡도 별로 한 번의 학습과 4번의 추론을 통해 4개의 floorplan 결과를 얻었고, 마찬가지로 총 12개의 floorplan 결과를 얻었습니다. 자세한 측정 방식은 [그림 5]를 참고해주세요.

[그림5] - 성능 측정 방식

결과 비교

[그림6] - Human expert와 강화학습 기반 알고리즘의 평균 성능 비교

수행 시간

저/중/고 복잡도 평균 수행시간은 human expert 대비 69.2% 감소하였습니다. Human expert의 경우 좋은 floorplan 결과를 얻어내기 위하여 EDA 툴을 이용해 여러 번의 floorplan ~ routing 과정을 거쳐야 합니다. 반면 강화학습의 경우 단 한번의 floorplan으로 결과를 완성하기 때문에 수행 시간이 크게 개선되었습니다.

Floorplan 이후 진행되는 timing closure 과정에서 timing 분석, 설계 수정 등 엔지니어가 작업을 진행해야하기 때문에 강화학습 알고리즘을 사용해도 physical design이 완전히 자동화되는 것은 아닙니다. 하지만 강화학습을 사용해 초기에 빠르게 좋은 품질의 floorplan 결과를 만들어낼 수 있다는 점은 굉장히 고무적입니다. 이를 통해 저희의 솔루션을 실제 프로젝트에 적용할 수 있다면 설계 수행 시간을 크게 감소시킬 수 있는 효과를 낼 수 있을 것으로 기대하고 있습니다.

PPA (Power, Performance, Area)

저희는 floorplan 결과의 품질을 비교하기 위한 수단으로 power, performance, area를 통칭하는 PPA를 사용합니다. Power와 area은 매우 직관적인 지표로, 각각 칩의 전력 소모량과 크기를 나타냅니다. Performance를 측정하기 위해서는 Worst Negative Slack*과 Total Negative Slack(TNS)이라는 두가지 수치를 사용합니다. WNS는 여러가지 전기신호가 전달되는 경로 중 가장 좋지 않은 negative slack이 어느정도인지를 나타냅니다. WNS는 특정 기준 수치 이하일 경우 floorplan 단계를 마무리하고 후속 과정으로 이관한다는 협업사의 의견을 근거로 pass&fail로 판단하였습니다. TNS는 칩 전체의 negative slack의 합으로 작을수록 좋은 값입니다. 즉, TNS는 chip의 전체적 timing performance를 나타낸다고 할 수 있습니다. 위에서 설명드린 각 항목은 모두 사람대비 개선된 정도를 측정하며 각 수치의 평균값을 PPA라고 정의합니다.

* SLACK이란 신호가 도착해야하는 목표 시간과 실제 도착 시간의 차이를 말합니다. SLACK이 음수 값을 가지게 되면(NEGATIVE SLACK) 목표 TIMING 성능에서 얼마나 미달되는지를 나타냅니다.

PPA=Avg.(TNS,Power,Area)���=Avg.(���,�����,����)

하나의 복잡도 문제에 대해 4명의 엔지니어가 각각 floorplan을 진행하기 때문에 결과적으로 각각의 복잡도에서 4개의 PPA 수치를 얻을 수 있습니다. 먼저 얼마나 안정적으로 성능을 달성할 수 있는지 알기 위해 “4개 PPA 수치의 평균 값”을 비교하였습니다. 전문가가 배치한 결과 대비 약 10.82%의 성능 개선(저 복잡도: 7.99% |, 중 복잡도: 7.33% | 고 복잡도: 17.14%)이 있었습니다. 추가로, 강화학습이 얼마나 높은 성능을 가질 수 있는지 측정하기 위해 “4개 PPA 수치의 최고 값”을 비교하였습니다. 사람이 배치한 결과 대비 평균적으로 약 10.22%(저 복잡도: 8.89% | 중 복잡도: 17.19% | 고 복잡도: 4.57%)의 성능향상을 달성할 수 있었습니다. 결과적으로 저희 강화학습 기반의 알고리즘을 사용했을 때 안정적으로 높은 성능을 얻을 수 있다는 것을 알 수 있습니다.

결론

최종적으로 주어진 저/중/고 복잡도 문제에서 강화학습의 결과가 엔지니어 대비 수행 시간은 69.2% 감소, 성능 지표는 평균 10.2% 개선되는 결과를 보여주었습니다. 실험 결과를 통해 floorplan 과정을 강화학습을 통해 자동화하는 것이 가능함을 확인할 수 있었습니다. 또한 강화학습 알고리즘이 실제 엔지니어 대비 준수한 성능을 가지는 floorplan 결과를 한번에 만들어낼 수 있다는 가능성 역시 보여주고 있습니다.

Future Work

이번 프로젝트를 통해 저희가 개발한 강화학습 기반의 알고리즘을 이용해 주어진 저/중/고 복잡도 문제에서 좋은 성능을 내는 것을 확인하였습니다. 하지만, 실제 산업에서 사용되는 더 다양하고 더 복잡한 디자인을 학습하기 위해서는 추가적인 성능 개선이 필요합니다. 예를 들어, static timing analysis 등을 활용해, 디자인의 timing 병목 지점을 더 자세하고 정확하게 예측할 수 있습니다. 또한, 인공신경망의 강력한 연산능력을 활용해 여러 netlist* 혹은 보지 못했던 netlist에 대해 최소한의 학습만으로도 좋은 품질의 배치를 얻을 수 있습니다. 저희는 이를 위해 더 많은 데이터를 확보하고 저희 솔루션의 성능을 검증할 예정이며. 더 짧은 시간 내에 더 높은 성능의 floorplan 결과를 만들 수 있는 방법에 대해 연구를 진행하려 합니다.

* NETLIST는 반도체 회로의 설계도라고 할 수 있습니다. 설계된 회로도에는 여러 소자들이 있고, 소자들은 각각 연결성을 가지고 있습니다. 이 연결성을 나타는 파일을 NETLIST 파일이라고 부릅니다.

마무리하며

저희 마키나락스의 COP 팀은 산업의 여러 조합 최적화 문제를 해결하고자 하는 목표의 일환으로 이번 floorplan 자동화 프로젝트를 진행하였습니다. 프로젝트를 진행하면서 강화학습을 포함하여 많은 알고리즘들에 대해 연구해보고 적용해 볼 수 있었습니다. 특히, 가중치 그래프로 표현되는 대상을 최적화하는 많은 기술적 노하우를 쌓을 수 있었습니다. 소개해드린 알고리즘은 반도체 소자 배치 문제 이외에도 다양한 영역에 적용될 수 있습니다. 예를 들어,

공장 설비 배치 최적화

물류 최적화

시나리오 최적화

등등으로 다양합니다. 위 문제들은 하나의 공통점을 가지고 있습니다. 바로, 서로 상관관계를 가지고 있는 대상들이 물리적 위치에 따라 효율성 혹은 품질이 개선될 수 있는 문제들입니다. 저희의 개발한 알고리즘은 이런 종류의 문제들에 대해 최소한의 변경으로 자유롭게 시도해 볼 수 있습니다. 산업 현장의 더 많은 문제를 해결할 수 있도록 노력하겠습니다.

회고

마키나락스 COP 팀원들(우식, 지윤, 승주, 원준)

우식: 다사다난했던 1년 반의 시간동안 함께 고생해준 팀원분들께 감사합니다. 덕분에 프로젝트가 성공적으로 끝났네요. 다양한 문제에서 다양한 알고리즘을 적용해 문제를 해결하고, 직접 만든 알고리즘이 실제 현장에서 쓰이는 것을 보는 것이 최종 목표입니다.

지윤: 문제에 직접 부딪히며 해결해나가는 과정에서 좋은 팀원들을 만나 많이 배울수 있었습니다. 앞으로도 같이 성장하면 좋겠습니다.

승주: COP팀과 floorplan 자동화 프로젝트를 하면서 많은 우여곡절이 있었지만 목표로 했던 KPI를 초과 달성하게 되어서 매우 기쁩니다. 이번 프로젝트는 layout planning의 가장 어려운 문제를 경험하면서 많은 성장을 할 수 있었던 계기였습니다. 팀 차원에서도 이번 프로젝트를 통해서 클러스터링, 분산 강화 학습등 많은 기술 스택을 쌓았고 업무 문화를 합의하에 형성하면서 같이 성장했던 경험을 나누었습니다. 앞으로 COP팀으로서 커리어가 기대됩니다.

원준: 실제 산업 현장의 조합최적화 문제에 AI 적용 가능성을 보여준 좋은 프로젝트였다고 생각합니다. 앞으로도 여러 분야에서 좋은 사례를 보여줄 수 있는 COP팀이 되었으면 좋겠습니다.

부록

부록에서는 복잡도가 높은 floorplan 문제를 해결하면서 더 좋은 성능을 위해 이전에 소개해드린 내용(Floorplan 자동화 - Part I, Part II)에서 어떤 기술적인 개선 사항들이 있었는지 설명합니다.

개선사항 1: Standard Cell Clustering & Placement

ASIC 디자인의 복잡도가 올라감에 따라 standard cell의 개수는 폭발적으로 증가합니다. 이전의 연구에서 상대적으로 영향력이 적었던 standard cell clustering & placement가 성능에 큰 영향을 주게되면서, 많아진 standard cell에 대해서 높은 성능을 낼 수 있는 방법에 대해 추가적인 연구를 진행하였습니다.

Standard Cell Clustering

Standard cell들의 연결관계는 복잡한 그래프로써 표현될 수 있습니다. 따라서, 다양한 네트워크 그래프 클러스터링 알고리즘들을 적용할 수 있으며*, 최적화 문제의 복잡도를 낮추기 위해 사용됩니다[그림 7]. 수십-수백만개의 standard cells에 clustering 알고리즘을 적용하여 수백-수천개로 배치 대상의 개수를 줄일 수 있습니다.

* NET은 하나의 엣지에 여러개의 노드가 달려있는 HYPER GRAPH로 표현됩니다. NORMAL GRAPH에 대한 알고리즘을 적용하기 위해서는 별도의 처리 과정을 거쳐야합니다.

[그림7] - clustering 개념

Clustering 알고리즘을 적용하는데에는 아래와 같은 가정이 있습니다.

“연결성이 강한 STANDARD CELL들은 실제 배치에서도 근거리에 배치 될 것”

하지만 실제로 EDA 툴을 이용해 배치 결과를 확인해 보면 같은 macro 배치에서도 학습 시에 예상한 standard cell 배치와 EDA툴의 standard cell 배치가 크게 다릅니다. 예를 들어, 같은 cluster에 있는 두 standard cell이 EDA 툴로 배치했을 때는 멀리 떨어져서 배치 될 수 있습니다. 이 경우 강화학습 agent와 EDA툴이 보고 있는 standard cell의 위치가 달라 성능 평가에 차이가 발생하게 됩니다. 이러한 차이를 clustering 오차라고 부르겠습니다. 강화학습이 좋은 결과를 내기 위해서는 clustering을 할 때 netlist는 충분히 축약하면서 작은 clustering 오차를 가지도록 하는 것이 중요합니다.

Clusterin 오차가 작다면 [그림 8]의 왼쪽과 같이, 같은 cluster 내의 소자들은 EDA툴에서도 근거리에 배치될 것입니다. 이 경우 실제 EDA P&R 환경과 높은 유사도를 가지는 강화학습 환경을 만들 수 있습니다. 반면 [그림 8]의 오른쪽과 같이 같은 cluster 내의 소자들이 EDA 툴의 배치에서는 멀리 떨어지게 되면 clustering 오차가 큰 강화학습 환경을 만들게 되며, 정확한 학습을 할 수 없게 됩니다.

[그림8] - clustering에 의해 발생하는 오차

따라서 왜곡를 최소화하기 위해서는 “좋은 품질의 floorplan 결과에서 인접하게 배치되는 standard cell 끼리만, 같은 cluster로 분류하는 것”이 중요합니다. 하지만 좋은 품질의 floorplan 결과는 실제 탐색을 해보기 전에는 알 수 없습니다. 저희는 이러한 문제를 해결하기 위해 netlist가 포함하고 있는 연결관계에 주목했습니다. 연결관계를 직접적으로 활용해 clustering 방식을 여러 단계의 페이즈로 구성했습니다. 이러한 개선을 통해 clustering 오차를 최소화했으며 실제 학습 성능 향상에 큰 기여를 했습니다.

Force-directed Standard Cell Cluster Placement

이전 포스팅에서는 macro와 마찬가지로 standard cell cluster 또한 강화학습 agent가 배치하는 방식을 사용했습니다[3]. 하지만, 저희는 이 방식에서 두 가지 문제를 확인하였습니다.

첫째는 강화학습 agent가 배치한 standard cell cluster가 ICC2의 standard cell 배치를 잘 근사하지 못한다는 것 입니다. Macro 배치의 품질을 정확하게 평가하기 위해서는 EDA 툴인 ICC2의 결과를 최대한 정확하게 모사해야 합니다. 따라서, 강화학습 agent가 배치한 standard cell cluster가 ICC2의 standard cell 배치를 잘 근사하지 못한다면, 정확하게 학습할 수 없습니다.

둘째는 standard cell 개수가 증가함에 따라 학습의 난이도가 증가한다는 점 입니다. 이번에 진행한 프로젝트에서는 지난 포스팅에서 소개한 문제 대비 배치해야 할 standard cell의 개수가 많았기 때문에 학습이 잘 되지 않았습니다.

저희는 이 문제를 해결하기 위해 강화학습 agent는 macro cell만 배치하고 standard cell cluster는 force-directed placement(FDP)를 이용해 배치하는 방법을 도입했습니다. FDP 알고리즘은 두 소자간의 연결강도를 인력 혹은 척력으로 생각하고, 각 소자들의 위치에 대한 평형상태를 찾아가는 알고리즘입니다. 이는 전역 최적해를 보장하진 않지만 빠른 시간안에 비교적 좋은 품질의 배치를 보여줘 다양한 배치 최적화 논문[4, 5] 활용되고 있습니다. 따라서, ICC2의 standard cell 배치를 더 잘 근사함과 동시에 강화학습 agent가 배치해야 할 소자 수가 줄어들어 이전 포스팅에서 소개한 방법의 단점을 모두 해결할 수 있었습니다.

[그림9] - Forced directed method

같은 macro 배치에서 FDP를 이용해 배치된 그림과 실제 EDA툴의 배치 양상을 비교해보면 저희의 예측이 잘 이루어지고 있는지 확인할 수 있습니다. [그림 10]은 동일한 macro 배치에 대하여 각각 standard cell placement를 진행한 결과입니다. 높은 연관성을 갖는 소자들은 같은 색으로 표현이 되어있고, 밀접하게 배치되는 것을 확인할 수 있습니다. FDP의 결과는 상용 EDA툴의 배치와 높은 유사도를 가지며, 이를 통해 빠르면서도 정확도가 높은 강화학습 환경을 구성할 수 있습니다.

[그림10] - FDP와 EDA툴의 배치 양상 비교

분산 강화학습

에이전트는 환경과 상호작용하며 더 좋은 보상을 위해 학습합니다. 일반적으로 에이전트가 더 많은 경험을 할 수록 보다 좋은 결과를 얻을 수 있습니다. 에이전트는 환경과 상호작용하며 일련의 “행동”을 취하고, 그에 대한 피드백으로 “보상”과 다음 “상태”를 전달 받습니다. 이러한 일련의 과정들을 episode, trajectory 등 여러 이름으로 불리기도 하지만 여기서는 학습을 위해 사용되므로 sample이라고 부르겠습니다. 분산 강화학습은 다수의 CPU/GPU 자원을 활용해 많은 양의 sample을 효율적으로 확보하여 학습의 성능을 향상시킵니다. 분산 강화학습은 [그림 11]와 같이 학습 모델을 따로두고, 다양한 sample을 수집하는 worker들이 분산되어 있는 방식으로 주로 구현됩니다.

[그림11] - 비동기 분산 강화학습

하지만 각 worker들이 수집한 sample들을 한번에 학습 모델에 전달하게 되면, 전송과정에서의 병목현상이 발생합니다. 이러한 병목 현상을 제거하기 위해 기존의 Proximal Policy Optimization(PPO)[7]을 기반으로한 Decentralized Distributed Proximal Policy Optimization(DDPPO)[8]이 등장했습니다. DDPPO는 각 worker에 있는 인공신경망 모델에서 각각 학습을 진행한 후, 그 결과를 학습 모델에 전송하여 신경망 모델을 업데이트합니다. 전송해야하는 데이터가 업데이트에 사용되는 sample의 개수와 무관하기 때문에 기존에 발생한 병목을 제거할 수 있습니다. DDPPO를 사용했을 때 PPO 대비 훨씬 안정적으로 학습하며 성능도 크게 향상되었습니다. [그림 12]에서 볼 수 있는 것처럼 최종적으로 얻은 보상의 값이 약 10% 이상 차이 나기 때문에 학습 성능이 크게 개선되었다고 볼 수 있습니다.

[그림12] - PPO와 DDPPO 성능비교 : 동일한 samples/iteration 조건에서 비교

모델 개선

에이전트의 행동 정책으로 사용되는 인공 신경망 모델은 현재까지 경험한 내용들을 학습합니다. 학습된 데이터를 통해 현재 상태를 고려해 다음 macro를 어디에 놓을지 결정하는 역할을 수행합니다. 기존에는 Graph Neural Network (GNN)와 Convolution neural network (CNN)를 결합한 네트워크를 사용했습니다[2]. 하지만 문제의 복잡도가 높아졌을 때 기존의 모델은 목표성능을 달성하지 못했습니다. 저희는 이에 대한 원인 분석과 개선을 진행하였습니다.

분석한 첫번째 문제는 GNN의 연산량 입니다. 소자가 많아지면서 연결관계가 매우 복잡해졌고, GNN으로 인한 연산량이 크게 증가하며 학습속도가 저하되었습니다. 이를 개선하기 위해 GNN의 layer 수를 줄여가며 속도와 성능 사이의 균형을 찾는 실험을 진행했습니다. 그 결과 GNN을 사용하지 않더라도 성능하락 없이 학습 속도가 큰 폭으로 향상되었습니다. 이러한 실험 결과에 근거하여 GNN을 제거하고 CNN만을 사용하여 연결관계와 배치 정보를 모두 처리하도록 변경하였습니다.

두번째 문제점은 agent가 충분한 탐색을 하지 못하고 조기에 수렴하는 것입니다. 모델이 배치의 정보를 보다 잘 해석할 수 있도록 하기 위한 여러 구조를 시도하였고 그 중 가장 효과가 좋았던 [그림 13]의 convolution / de-convolution 구조를 사용하였습니다.

[그림13] - 개선된 모델 구조

개선 사항 3: 후처리 작업의 추가

Floorplan을 진행하다보면 배치 품질과 밀접한 관계가 있지만 저희가 설계한 알고리즘에 여러 이유로 적용하기 어려운 작업들이 존재합니다. 이러한 것들을 고려하기 위해 에이전트가 학습 후 floorplan 결과를 출력하면 그에 대해 후처리 작업을 진행합니다.

강화학습의 최종 floorplan 결과는 [그림 14]의 왼쪽과 같이 나타납니다. 그림을 보면 macro와 macro사이 혹은 macro와 가장자리 사이에 빈 공간들이 존재합니다. 이러한 빈 공간들을 deadspace라고 부릅니다. P&R 과정에서 deadspace에 standard cell들이 배치되면 routing에 악영향을 줍니다 [그림 15].

[그림14] - deadspace 제거 전(왼)과 후(오)의 macro 배치

[그림15] - Deadspace가 성능에 안좋은 영향을 미치는 원인

강화학습 결과에서 이러한 deadspace가 발생하는 원인은 두가지입니다. 첫째는 현재 저희가 설계한 배치 품질을 평가하는 보상이 위의 문제를 구별하지 못하기 때문이며, 둘째는 강화학습에서 복잡도를 낮추기 위해 chip die라는 연속공간을 grid 단위의 이산공간으로 변환 후 macro 위치를 결정하기 때문입니다. 저희는 이를 해결하기 위해 자체적인 deadspace 제거 알고리즘을 개발하여 floorplan 결과에 후처리 작업으로 적용하고 있습니다. 이를 통해 엔지니어의 추가적인 작업 없이 강화학습의 floorplan 결과가 좋은 성능을 가질 수 있었습니다.

References

Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., … & Dean, J. (2021). A graph placement methodology for fast chip design. Nature, 594(7862), 207-212.

Gao, X., Jiang, Y. M., Shao, L., Raspopovic, P., Verbeek, M. E., Sharma, M., … & Jalota, A. (2022, April). Congestion and Timing Aware Macro Placement Using Machine Learning Predictions from Different Data Sources: Cross-design Model Applicability and the Discerning Ensemble. In Proceedings of the 2022 International Symposium on Physical Design (pp. 195-202).

ASIC Floorplan Automation Part2 : https://makinarocks.github.io/ASIC-Floorplan-Automation-Part-2/

Cheong, S. H., & Si, Y. W. (2020). Force-directed algorithms for schematic drawings and placement: A survey. Information Visualization, 19(1), 65-91.

Kennings, A., & Vorwerk, K. P. (2006). Force-directed methods for generic placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(10), 2076-2087.

Force directed placement concept image : https://observablehq.com/@d3/simulation-tick?collection=@d3/d3-force

Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.

Wijmans, E., Kadian, A., Morcos, A., Lee, S., Essa, I., Parikh, D., … & Batra, D. (2019). Dd-ppo: Learning near-perfect pointgoal navigators from 2.5 billion frames. arXiv preprint arXiv:1911.00357.

Load Comments