[VLSI CAD] 최적해가 어려운 이유: NP-hard, heuristic, AI EDA

TL;DR

• 반도체 설계의 핵심 최적화 문제들은 대부분 NP-hard / NP-Complete / PSPACE-complete라서, “최적해”를 보장하는 알고리즘은 스케일이 커지면 사실상 못 돈다. (예를들어 2가지 경우의 수가 40개만 되어도, 1조개의 경우의 수이다.)
• 그래서 EDA 툴은 처음부터 끝까지 heuristic + 근사 + 반복 개선로 설계된다. 이건 “툴이 구려서”가 아니라 문제 성질 때문이다.
• AI/ML은 NP-hard를 “최적해”를 효율적으로 찾진 못한다. 대신 현실적으로는 모델로 방향을 잡아주고, 자동화하고, 문제를 좁혀서 이득을 낸다.

1) Physical Design: 왜 NP-hard인가

Physical Design의 첫 단계인 Logic Synthesis에서 가장 고전적인 “hard”는 two-level Boolean minimization이다. 예를 들면 Truth table을 만족하는 최소 SOP(DNF) 를 찾는 문제.

• two-level Boolean minimizatio 문제는 NP-complete로 알려져 있다.

Quine-McCluskey(QM) Case:

QM은 디지털 공학에서 배우는 Boolean function 간략화 방법이다.

• 목표: Boolean function을 최소한의 prime implicant로 덮는 것인데,
• 절차:
  1. 모든 prime implicant 생성
  2. 모든 minterm 나열
  3. Covering table 만듦 (행=minterm, 열=prime)
  4. 최소 열 선택 → minimum covering problem

👉 문제는 4번이다.

• 실제 회로에서는 “가능한 후보 term 조합”이 엄청나게 큰데, QM은 지수 복잡도를 갖는다.
• QM의 covering table에서 prime implicant 조합을 찾는 과정은 set cover / exact cover 구조로 떨어지고, 이게 대표적인 NP-complete다.

중요 포인트는 이거다.

VLSI CAD (EDA Tool)가 느리고 어려운 건 구현이 못해서가 아니라, 문제 자체가 가능한 경우의 수가 엄청나게 많다는 것이다.

그래서 “SATisfaction/Integer Linear Programming로 풀면 되지 않나?”라는 말이 나오는데, 그건 이렇게 정리하면 된다.

• SAT는 NP-complete, ILP도 NP-hard 범주다.
• 즉, 형식을 바꿔도 여전히 NP-complete, NP-hard이다.

2) EDA 단계들에 그렇게 NP-Hard, NP-Complete가 많은가?

EDA flow는 단계가 바뀌어도 본질이 비슷하다.

“Component를 배치/선택/연결해서 Cost optimization”
이 구조가 대부분 NP-hard로 귀결된다.

아래는 “최적화 목표 → 왜 hard인지”만 남긴 압축판이다.

2.1 Multi-level logic (AIG, DAG rewriting)

• 목표: gate 수, depth, power proxy 등을 줄이기
• Why hard?: 회로 구조 자체를 바꾸는 “global restructuring”은 조합 탐색이 된다. multi-output/minimization 류도 NP-hard로 알려져 있다.

• Alternative solution: Local transform (algebraic rewriting, AIG rewriting)

2.2 Technology Mapping

• 목표: DAG를 standard cell 또는 LUT로 매핑하면서 area/delay 최소화
• 왜 hard: 일반 DAG에서 optimal mapping은 NP-hard로 알려져 있다.
• 예외: tree 구조면 DP로 풀리는 경우가 있지만, 실제는 DAG라서 깨진다.

https://hjemmesider.diku.dk/~jegeblad/thesis.pdf

2.3 Placement

• 목표: cell을 좌표에 배치해 wirelength/congestion 최소화
• 단순화해도 partitioning/bin packing류로 환원되며 NP-hard로 알려져 있다.
• 그래서 현실: analytic placement + partitioning + heuristic refinement.

이외에도, Routing, CTS, ... 많은 것들이 NP Problem이다.

3) decision vs optimization vs multi-objective

EDA가 어려운 이유는, 회로설계자들이 원하는 것은 decision이 아니라 optimization이고, 게다가 multi-objective이기 때문이다.

• Decision problem: “가능해/불가능해?” (예: timing 1ns 만족 가능한가?)
• Optimization problem: “최소/최대가 뭐야?” (예: wirelength 최소 배치)
• Multi-objective: Performance Power Area 같이, 여러가지 목표가 있다.

현실에서 하는 건 이런 형태다.

• “timing은 무조건 맞춰라” (hard constraint)
• “area/power는 penalty로 줄여라” (soft constraint)
• 그리고 여러 번 돌리면서 trade-off를 조정한다.

즉, EDA는 처음부터 “정답 1개”를 찾는 게임이 아니라
제약과 타협을 설계하는 게임에 가깝다.

4) 그래서 heuristic이 ‘선택’이 아니라 ‘필수’다

EDA에서 heuristic이 필수인 이유는 네 가지로 정리하면 끝난다.

1. Global optimal이 안 나온다 → local improvement를 쌓는다.
   1. Global Optimal는 모든 경우의 수를 나열하고, 이것보다 더 좋은 경우의 수가 없음이 증명된 최적해를 의미한다.
2. 추상화 레벨이 다르다 → Logic synthesis에서 좋던 게 Placement에서 망할 수 있다.
3. cost function이 지저분하다 → 비선형/비볼록/계단형이라 “정석 최적화”가 잘 안 먹힌다.
4. incremental loop가 기본 → 한 번에 끝내는 게 아니라 “수정→분석→수정”이 본체다.

요약:

EDA 툴은 원래부터 “heuristic을 잘 엮는 시스템”이다.

5) AI/ML driven EDA의 어디서 현실적으로 먹히나?

AI가 NP-hard를 “Solving”한다는 말은 위험하다. 그런데 IT 커뮤니케이터들은 조회수를 목적으로 과도한 홍보를 하곤한다.

아래처럼 분류하면, 좀 더 맞는 말이다. 이것도 약간 부족한 느낌이지만.

A) AI가 잘하는 영역: “풀기”가 아니라 “예측/점수화”

• surrogate model: expensive simulation/analysis를 대신하는 predictor
• placement/routing에서 congestion, timing hotspot을 빨리 예측해서 탐색 방향을 잡는다.

AI는 solver가 아니라 scoring function으로 들어갈 때 안정적이다.

B) AI가 실제로 돈 되는 영역: “EDA Tool을 여러 번 돌리는 일을 AI가 자동으로 돌려, 설계자의 effort를 최소화함.”

많은 EDA 회사들의 AI-EDA 같은 접근 중 하나이다.

• EDA 엔진 자체를 바꾸기보다, “옵션/flow/parameter”를 AI가 탐색해서 사람 튜닝 노동을 줄인다.
• 이건 현실적으로 ROI가 크다.
• 여기서 본질은 “AI가 placement를 새로 발명”이 아니라search automation이다.

C) AI가 현재 약한 영역: “정확성 0% error가 필요한 곳”

• Signoff나 formal verification은 최종적으로 도장을 찍어줄 책임 수준의 proof가 필요하다. ML은 보조는 가능해도 대체는 어렵다.
• end-to-end로 SAT를 풀거나, end-to-end로 전체 chip을 설계하는 건 일반화/검증에서 막힌다.

6) AI driven EDA 유명 사례 한 줄 평가

아래 기술은 유망하다. 그러나 언론에서 과대 평가하는 경향도 있다.

• Google RL macro placement (Nature): 임팩트는 컸다. 대신 재현/비교가 약하다.
• DSO.ai / Cerebrus: AI를 “solver”로 포장하기보다, flow tuning 자동화로 가치를 만든 케이스다.
• agentic EDA / LLM: 아직은 “가능성”이 크고, 검증/책임/데이터 문제는 그대로다.

7) 정리

• “AI면 NP-hard 해결?”
  • 아님. AI도 최적해를 찾는 방법이 아니다.
• “SAT+AI면 optimal synthesis?”
  • 아님. 탐색공간이 그대로 남는다.
• “cloud compute면 해결? 컴퓨터 리소스 더 늘리면 해결?”
  • 아님. 복잡도가 지수라서, 지수가 매우 크면, 지구의 컴퓨터 다 가져와도 못 하는데, 현대 반도체 설계들은 지수가 매우 크다.
• “AI driven EDA가 설계자를 대체?”
  • 아직은 아님. 요구 조건 설계+최종 검증+책임질 사람이 필요.