RTX5090 칩설계는 원본 자료에 grader의 비용 함수(wireLengthCost·pathTimingCost)와 검증 함수(deploy·verify), 구조체(Cell·Net·Path)가 공개돼 있으나 — process() 본문은 비어 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 라인 단위 해부 대신, grader가 노출한 두 비용 함수를 정밀하게 읽어 VLSI 셀 배치(placement) 문제로 정식화하고, "force-directed 초기 배치 + 시뮬레이티드 어닐링 미세조정"이라는 베스트 해법을 설계하고 논증한다. 추측이 들어가는 곳은 "설계 제안"임을 명시한다.
노후화된도로처럼, RTX5090의 grader도 점수를 계산하는 함수 본문을 통째로 공개한다. wireLengthCost()와 pathTimingCost() — 이 두 함수가 우리가 최소화해야 할 목적 함수의 정확한 정의다. 해법 설계는 이 함수들을 읽는 데서 시작한다.
CHIP_SIZE × CHIP_SIZE = 1024 × 1024 격자다.gCellCount ∈ [256, 512]개. 각 셀은 직사각형 {x, y, width, height}이며 width·height ≤ 32×32.{toCell, pinCount}를 가진다. 셀당 net 수는 netCount ≤ 32.gPathCount ∈ [64,128]개. 각 경로는 셀 인덱스 열 cells[](길이 8~16)과 timeSpec을 가진다.verify()가 두 셀이라도 겹치면 false, 곧 PENALTY 10¹¹.gOrgCells)과 호환돼야 한다. 위반하면 그 셀의 PENALTY가 해소되지 않고 남는다.wireLengthCost() + pathTimingCost(). SCORE를 최소로.deploy()의 첫 줄은 gTotalCost += PENALTY, 마지막 줄은 gTotalCost -= PENALTY다. 중간의 어떤 검증이라도 실패해 return하면 — 차감이 실행되지 않아 PENALTY 10¹¹이 그대로 남는다. 즉 deploy()는 "유효한 배치면 비용 0, 무효하면 10¹¹"을 부과하는 게이트다. 베스트 해법의 첫 번째 의무는 점수 최적화가 아니라 — 모든 deploy 호출이 끝까지 통과하도록 제약을 한 치도 어기지 않는 것이다.
이 통찰에서 베스트 해법이 세 층으로 정해진다.
wire + timing 합을 점진적으로 낮춘다.이 분해는 "필수 제약(완전성)을 먼저 거의 공짜로 확보하고, 그 위에서 점수를 다툰다"는 — 로봇청소기 № 01이 보였던 정신과 같다.
baseline부터 잡는다. grader의 두 비용 함수를 정확히 읽어 — 무엇이 비용을 키우는지, 그리고 둘이 왜 충돌하는지를 수식으로 못박는다.
pathTimingCost()는 경로의 각 hop from→to에 대해 from의 net 중 toCell == to인 것을 찾는다. 그런 net이 없으면 즉시 return PENALTY다.
그러나 deploy()는 net의 toCell을 원본과 동일하게 강제하고(원본 net은 변경 불가, 추가 net만 허용) — 경로는 init()이 셀 인덱스를 무작위로 잇는다. 즉 경로의 hop이 원본 net 위에 놓이도록 보장하는 것은 grader의 데이터 구조이며, 배치(좌표)는 net의 존재 여부를 바꾸지 않는다. 좌표만 옮기는 한 이 불변식은 자동으로 유지된다 — 우리가 깨뜨릴 수 있는 것은 net 자체가 아니라 net의 길이(거리)뿐이다.
wireLengthCost와 pathTimingCost는 둘 다 셀 간 거리의 증가 함수다 — 셀을 가깝게 두면 두 비용이 함께 줄어든다. 그러나 한 다이는 유한하므로 모든 셀 쌍을 동시에 가깝게 둘 수는 없다. 어떤 net 쌍을 붙이면 다른 net 쌍은 멀어진다. 따라서 최적화는 "어느 연결을 짧게 우대할 것인가"의 자원 배분 문제다.
두 비용 모두 거리에 비례하지만 pinCount가 정반대로 작용한다. wireLengthCost에서 한 net의 기여는 거리 · pinCount — pinCount가 클수록 그 net을 짧게 두는 것이 중요하다. pathTimingCost의 delay에서 한 hop의 기여는 거리 / pinCount — pinCount가 작을수록 그 hop이 delay를 키운다.
따라서 같은 net이라도 두 목적에서 우선순위가 다르다. 핀이 굵은 net은 wireLength 관점에서 최우선으로 짧게 둬야 하고, 핀이 가는 net이 포함된 timing 경로는 path 관점에서 위태롭다. 한 배치로 두 목적을 모두 만족시키려면 — 굵은 net을 우선 압축하되, 가는 net으로 이어진 timing 경로가 timeSpec을 넘지 않는 선을 지켜야 한다. 두 목적의 가중치가 pinCount에 대해 비대칭이라는 것이, "단순히 모두 가깝게"가 통하지 않는 이유이며 — 국소 개선(어닐링)이 필요한 근본 원인이다.
pathTimingCost는 delay ≤ timeSpec이면 비용 0이고, 넘는 순간에만 100·(delay−timeSpec)가 부과된다. 이것은 wireLength처럼 매끄러운 비용이 아니라 임계값 비용이다. 따라서 timing 경로는 "최대한 짧게"가 아니라 — "timeSpec 아래로만 내리면 그 이상 줄여도 점수 이득이 없다." 어닐링의 비용 함수에 이 포화(saturation)를 반영하지 않으면, 이미 spec을 만족한 경로를 더 줄이려고 굵은 net의 wireLength를 희생하는 잘못된 교환을 한다.
풀이 코드가 없으므로 전체 골격은 의사코드로, 어닐링의 핵심부만 C++로 스케치한다. 전략은 "force-directed 초기 배치 → 시뮬레이티드 어닐링 미세조정 → 겹침 제거 → deploy"이다.
// 베스트 해법 골격 — VLSI placement
process(cells, paths):
// (1) 초기 배치 — net 무게중심으로 force-directed
grid_seed(cells) // 균등 격자로 무겹침 시작
repeat F times:
for each cell c:
target = weighted_centroid(c) // net으로 이어진 셀들의 가중 평균
c.pos = move_toward(c.pos, target)
legalize(cells) // 겹침/경계 위반 복구
// (2) 시뮬레이티드 어닐링 — 비용 합 최소화
T = T0
while T > T_min:
for it in 1..K:
(i, j) = random_pair()
d = swap_or_move_delta(i, j) // §2 두 비용의 변화량
if d < 0 or rand() < exp(-d / T):
apply(i, j)
T *= COOL // 0.95 등
// (3) 최종 정당화 + 배치 확정
legalize(cells)
for each cell c: deploy(c.index, c) // 모든 호출이 통과해야 함
// 한 셀의 비용 변화 — 어닐링 수락 판정의 핵심
swap_or_move_delta(i, j):
before = local_wire(i) + local_wire(j) + affected_paths_timing()
tentatively move/swap i, j
after = local_wire(i) + local_wire(j) + affected_paths_timing()
return after - before
핵심은 어닐링의 수락 판정 — 비용 변화량 delta의 부호와, 음수가 아니어도 확률 exp(-delta/T)로 받아들이는 부분이다. 설계 제안 — 비용 함수는 grader 공식 그대로지만, "어떤 이웃 연산(swap/move)을, 어떤 온도 스케줄로" 쓸지는 실험적으로 튜닝할 영역이다.
// grader 공식 그대로 — timing은 timeSpec 초과분만 비용 (포화)double pathTiming(const Path &p, const Cell c[]) { double delay = 0.0; for (int h = 0; h < p.length - 1; ++h) { int from = p.cells[h], to = p.cells[h + 1]; int pin = pinOfNet(c[from], to); // from→to net의 pinCount delay += cellDist(c[from], c[to]) / (double)pin; } return (delay > p.timeSpec) ? 100.0 * (delay - p.timeSpec) : 0.0;}// 한 어닐링 스텝 — 셀 하나를 무작위 이동, delta로 수락 판정void annealStep(Cell c[], double T) { int i = randCell(); Cell old = c[i]; double before = localCost(c, i); // i가 닿는 net+path 비용 c[i].x = clampX(old.x + jitter(T)); // 온도에 비례한 이동폭 c[i].y = clampY(old.y + jitter(T)); if (overlapsAny(c, i)) { c[i] = old; return; } // 겹침 → 즉시 기각 double after = localCost(c, i); double delta = after - before; if (delta > 0 && randUnit() >= exp(-delta / T)) c[i] = old; // 악화 이동은 확률적으로만 수락}
pathTiming의 마지막 줄이 §2 함정의 직접 구현이다 — delay ≤ timeSpec이면 0을 반환해, 이미 만족한 경로를 더 줄이려는 헛된 교환을 비용 함수 차원에서 차단한다. localCost(c,i)는 셀 i가 닿는 net과 path만 다시 계산한다 — 전체 비용을 매 스텝 재계산하면(셀 512·net 32) 어닐링이 너무 느려진다. overlapsAny로 겹침을 먼저 거르는 것이 verify()의 PENALTY를 원천 차단하는 안전장치다. jitter(T)는 온도가 높을 때 큰 폭, 식으면 작은 폭으로 이동해 — 초반 탐색, 후반 수렴의 어닐링 본질을 만든다.
한 셀 i를 옮길 때 변하는 비용은 — i에서 나가는 net(최대 32개)과 i로 들어오는 net, 그리고 i를 포함하는 timing 경로뿐이다. 전체 비용(O(셀·net + 경로·길이) ≈ 512·32 + 128·16 ≈ 1.8×10⁴)을 매 스텝 재계산하는 대신, localCost는 O(32 + 영향받는 경로 수·16)로 떨어진다. 어닐링 스텝 수 K가 수십만이라도 — 국소 평가 덕에 한 TC가 시간 제한(5초) 안에 든다. 전(全) 비용 재계산과 국소 평가의 이 격차가, 어닐링을 현실적으로 만드는 결정적 최적화다.
§3의 어닐링은 국소 탐색이다 — 시작 배치가 나쁘면 좋은 골짜기에 도달하기 전에 시간이 끝난다. 그래서 초기 배치의 품질이 어닐링만큼 중요하다.
각 net을 용수철로 모델링한다. net으로 이어진 두 셀은 서로를 끌어당기고, 인력의 세기는 pinCount에 비례한다(§2: 굵은 net일수록 짧아야 하므로). 한 셀의 평형 위치는 — 그 셀에 붙은 모든 net 상대 셀들의, pinCount 가중 무게중심이다.
force-directed는 셀을 무게중심으로 끌어당기므로 — 강하게 묶인 셀들이 같은 좌표로 몰려 겹친다. 이대로 deploy()하면 verify()가 PENALTY를 부과한다.
따라서 매 force 반복 뒤 정당화(legalization)가 필요하다: 겹친 셀을 가장 가까운 빈 자리로 밀어내 — "어떤 두 셀도 겹치지 않고, 모든 셀이 다이 [0, 1024) 안에 있다"는 불변식을 회복한다. 1024² 다이에 셀 512개·각 32²는 면적의 절반 이하이므로 무겹침 배치는 항상 존재한다 — 정당화가 실패하지 않음이 보장된다.
실전 설계는 두 단계를 분업시킨다. force-directed가 net 토폴로지를 반영한 거친 초기 해를 빠르게 만들고(굵은 net이 이미 짧음), 정당화가 그것을 합법화하며, 그 위에서 어닐링이 국소 미세조정으로 timing 경로의 임계값 위반을 마지막으로 다듬는다. force-directed가 구조를, 어닐링이 적응을 담당하는 — 교차로신호제어 № 07의 "그린 웨이브 + 탐욕"과 똑같은 분업 패턴이다.
| 전략 | PENALTY 회피 | 비용 경향 | 계산량 | 평가 |
|---|---|---|---|---|
| 균등 격자 배치만 | 보장 | 높음 | 낮음 | net 토폴로지 무시 — 무겹침은 쉽지만 wire가 크다 |
| force-directed만 (어닐링 없음) | 위험 | 중간 | 낮음 | 거친 좋은 해이나 정당화 후 timing 임계값을 못 다듬는다 |
| 전역 최적 배치 (정수계획) | 보장 | 최소 | 불가 | 겹침 제약 있는 512셀 배치는 NP-난해 — 5초 안에 못 푼다 |
| force-directed + 정당화 + 어닐링 | 보장 | 낮음 | 중간 | 구조적 초기해(force) + 임계값 적응(anneal)의 분업 |
표는 설계 비교다 — 측정된 점수가 아니라 각 전략이 SCORE에 어떻게 작용하는지를 정리한다. 균등 격자는 무겹침을 거의 공짜로 주지만(verify 통과) net 토폴로지를 완전히 무시해 wireLength가 크다. force-directed 단독은 굵은 net을 짧게 만드는 좋은 초기 해를 주나 — §2의 임계값 비용(timing)을 못 다듬어, 정당화 과정에서 셀이 밀려나며 경로 delay가 timeSpec을 넘을 수 있다. 전역 최적 배치는 이론적 최소를 주지만 겹침 제약이 있는 512셀 배치는 NP-난해라 5초 시간 제한 안에서 불가능하다. 따라서 — force-directed로 구조적 초기 해를 깔고, 정당화로 무겹침을 회복하고, 어닐링으로 timing 임계값에 적응하는 3층 설계가 §1의 feasibility-우선 원칙과 §2 Theorem 1(두 비용의 충돌)을 모두 만족하는 최선의 후보다.
deploy()는 += PENALTY 후 검증을 통과해야만 -= PENALTY한다. 중간 return이 한 번이라도 일어나면 10¹¹이 그대로 누적된다. 모든 deploy 호출 전에 — 셀이 다이 안, net 호환, 핀 합 ≤ 32를 직접 확인하라.
verify()는 모든 셀 쌍의 겹침을 검사하고, 하나라도 겹치면 PENALTY 후 즉시 break다. force-directed가 셀을 무게중심으로 몰아 겹치게 만드는 것은 정상 동작이므로 — 매 배치 변경 후 정당화로 무겹침을 회복하라.
pathTimingCost는 delay ≤ timeSpec이면 0이다. 어닐링 비용 함수에 이 포화를 빼먹으면 — 이미 spec을 만족한 경로를 더 줄이려고 굵은 net의 wireLength를 희생하는 잘못된 교환을 수락한다.
wireLengthCost + pathTimingCost를 다시 부르면(셀 512·net 32) 5초 안에 충분한 스텝을 못 돈다. Theorem 2대로 — 옮긴 셀이 닿는 net·path만 평가하는 localCost를 써라.
01번과 달리 이 페이지는 측정된 SCORE를 제시할 수 없다 — 검증된 통과 코드가 없기 때문이다. 다만 RTX5090은 grader가 비용 함수와 검증 함수를 모두 공개하므로 검증 기반이 단단하다: 비용 모델은 추측이 아니라 grader 코드에서 직접 도출된 사실이다. 정직한 검증 기준은 — 설계가 grader의 확정 제약(무겹침·deploy 호환·timing 임계값)과 모순되지 않는가이다.
wireLengthCost·pathTimingCost·verify·deploy로부터 베스트 해법을 설계하고 그 정당성을 논증한 것이다. "force-directed 초기 배치 + 정당화 + 시뮬레이티드 어닐링"이라는 골격은 grader 코드에서 직접 연역된 비용 모델(§2)과 PENALTY 게이트 구조(§1) 위에 서 있고, 어닐링·force 파라미터만이 SCORE 측정을 요구하는 설계 제안이다. 이 페이지의 가치는 정답 코드가 아니라 — "grader가 두 충돌하는 비용 함수를 공개했을 때, 그것을 어떻게 VLSI placement 문제로 정식화하고 메타휴리스틱으로 공략하는가"라는 사고의 골격에 있다.