---
title: "논리 노드를 줄였는데 공유 경로가 더 느려지는 이유"
author: "브레이브브라우저쓰자"
published_at: "2026-10-21T22:33:04.627Z"
updated_at: "2026-10-06T01:33:11.730Z"
tags: ["boolean dag 재작성"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/%EB%85%BC%EB%A6%AC-%EB%85%B8%EB%93%9C%EB%A5%BC-%EC%A4%84%EC%98%80%EB%8A%94%EB%8D%B0-%EA%B3%B5%EC%9C%A0-%EA%B2%BD%EB%A1%9C%EA%B0%80-%EB%8D%94-%EB%8A%90%EB%A0%A4%EC%A7%80%EB%8A%94-%EC%9D%B4%EC%9C%A0"
ai_assisted: true
---

# 논리 노드를 줄였는데 공유 경로가 더 느려지는 이유

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/%EB%85%BC%EB%A6%AC-%EB%85%B8%EB%93%9C%EB%A5%BC-%EC%A4%84%EC%98%80%EB%8A%94%EB%8D%B0-%EA%B3%B5%EC%9C%A0-%EA%B2%BD%EB%A1%9C%EA%B0%80-%EB%8D%94-%EB%8A%90%EB%A0%A4%EC%A7%80%EB%8A%94-%EC%9D%B4%EC%9C%A0)

공통 부분을 하나로 묶었더니 게이트 수가 줄었다. 그런데 실제 타이밍은 더 나빠진다. Boolean DAG 재작성에서 흔히 만나는 간극이다. **논리 그래프의 노드 수와 실리콘에서 신호가 전달되는 비용은 서로 관련이 있지만 같은 값은 아니다.** 공유를 통해 얻은 이득을 어떤 비용 모델로 평가했는지 봐야 한다.

## 식의 반복을 그래프의 공유로 바꾸기

1비트 입력 a·b·c·d에서 두 출력 `y0 = (a & b) | c`, `y1 = (a & b) | d`를 만든다고 하자. 두 식을 별도 회로로 만들면 a&b의 AND가 두 개, 각 출력의 OR가 두 개로 총 네 논리 노드를 쓴다.

공통 노드 p=a&b를 만들고 y0=p|c, y1=p|d로 연결하면 AND 하나와 OR 두 개, 총 세 노드가 된다. 출력까지의 논리 단계는 두 경우 모두 AND→OR의 두 단계다. 네 입력의 16조합에서 두 출력이 그대로라는 점도 확인할 수 있다.

이런 공유를 자연스럽게 나타내는 표현이 DAG, 즉 방향성 있는 비순환 그래프다. 논리식을 트리처럼 각 출력에서 따로 펼치면 같은 부분을 여러 번 셀 수 있지만, DAG에서는 여러 사용처가 하나의 노드를 가리킨다. 따라서 재작성의 비용은 새 부분식의 길이뿐 아니라 이미 존재하는 노드와 무엇을 공유하는지에 달린다.

Mishchenko·Chatterjee·Brayton의 2006년 논문은 AIG의 작은 부분 그래프를 같은 함수의 다른 구조로 바꾸는 방식을 다룬다. 원문 3절에서는 기존 부분을 참조 해제할 때 실제로 없어지는 노드와 새 구조를 연결할 때 실제로 추가되는 노드를 세어 이득을 계산한다. 다른 곳에서도 쓰는 노드는 해당 부분을 바꿔도 사라지지 않는다는 관점이다. [DAG-aware AIG rewriting 원 논문](https://people.eecs.berkeley.edu/~alanmi/publications/2006/dac06_rwr.pdf)

논문의 AIG는 두 입력 AND와 반전된 에지로 함수를 표현한다. 위의 AND·OR 예는 공유의 의미를 설명하기 위한 일반 Boolean 그래프다. 세 노드라는 계산을 그대로 논문의 AIG 노드 수나 특정 공정의 셀 수라고 부르면 서로 다른 표현의 비용을 혼동하게 된다.

## 단계 수가 같아도 공유 노드의 부하는 달라진다

위 회로를 가상 지연 모델로 비교하자. AND의 지연을 `40ps + 20ps/fF × 출력 부하`로 두고, OR의 지연은 두 구현 모두 30ps라고 하자. OR 입력 한 개의 정전용량은 1fF다. 공유된 p에는 두 OR 입력과 2fF의 배선이 붙고, 복제된 AND 각각에는 OR 입력 하나와 0.5fF의 배선만 붙는다고 가정한다.

공유 노드의 부하는 1+1+2=4fF다. AND 지연은 120ps이며 OR를 거쳐 출력이 준비되기까지 150ps가 걸린다. 복제 구현의 AND 하나는 1+0.5=1.5fF를 구동하므로 지연이 70ps, 출력까지는 100ps다. 논리 단계는 같은 두 단계여도 공유된 경로가 50ps 늦다.

모든 게이트를 같은 10단위 면적으로 세면 공유 구현은 30단위, 복제 구현은 40단위다. 면적만 보면 25% 절감이지만, 이 지연 가정에서는 더 느리다. 실제 공정·배치 결과가 아니라 부하와 공유의 관계를 분리해 계산한 사례다. 공유 구현을 더 강한 셀로 바꾸거나 버퍼를 넣으면 지연이 달라지고 면적 이득도 다시 계산해야 한다.

원 논문은 노드 수와 논리 레벨을 활용하며, 4절의 매핑 비교에서 부하와 독립적인 타이밍 모델을 사용했다고 명시한다. 그 비용 모델에서 레벨을 늘리지 않는 재작성이 실제 배선 부하를 포함한 모든 경로의 지연까지 같게 유지한다는 뜻은 아니다. 좋은 연구 결과를 실무에 적용하려면 이 모델의 경계를 함께 가져와야 한다.

## 하나의 작은 지표로 결론내리지 않기

그래프 재작성은 같은 논리를 더 좋은 구조로 만들 기회를 준다. 공통 항을 찾는 공유뿐 아니라, 깊은 조합 경로의 묶음 순서를 바꿔 레벨을 줄이는 균형화도 가능하다. 원 논문이 재작성과 균형화를 번갈아 적용하는 것도 구조의 크기와 깊이를 함께 개선하려는 선택이다. 단일 노드의 식을 짧게 만드는 데서 멈추지 않는다.

실제 회로의 판단에는 매핑된 셀의 부하와 배선 정보가 더 필요하다. OpenSTA의 공식 예제는 Liberty 모델로 셀 지연을 계산하며, 추출된 기생 성분을 읽지 않으면 핀 정전용량만 지연 계산에 사용한다고 설명한다. 타이밍 수치를 볼 때도 어떤 물리 정보가 들어갔는지 확인해야 한다. [OpenSTA의 지연 모델과 기생 성분](https://opensta.readthedocs.io/en/latest/Examples/)

공유 노드를 풀어 복제하는 선택 역시 무조건 빠른 해법은 아니다. 입력 쪽의 fan-out이 늘고 배선이 달라질 수 있으며, 다른 출력에서 재사용하던 구조를 잃을 수도 있다. 바뀐 부분만 세지 말고 전체 공유 관계와 실제 중요한 경로를 비교한다.

노드가 줄었다면 논리 표현의 비용이 개선됐다는 좋은 신호다. 그다음에는 같은 기능인지 확인하고, 논리 레벨, 공유 노드의 부하, 매핑과 배치 이후 지연을 차례로 평가하면 된다. **작은 그래프를 만드는 목표와 사용할 수 있는 회로를 만드는 목표를 같은 비용 모델로 연결해야** 재작성의 이득을 정확히 읽을 수 있다.