carry-chain 배치에서 논리적으로 같은 덧셈이 다른 연결을 요구하는 이유
덧셈의 bit들을 각각 같은 진리표로 구현했는데, 배치 위치를 바꾸자 전용 carry 경로를 쓸 수 없게 됐다. 수식은 맞지만 구조의 연결 조건이 바뀐 것이다. carry-chain 배치는 작은 adder들의 개수와 함께, 어느 bit의 carry가 다음 어디로 가는지를 지켜야 한다.
bit 순서는 carry의 의존 순서다
계산용 ripple adder에서 bit i의 carry는 ci+1=ai·bi+(ai⊕bi)·ci이고 sum은 si=ai⊕bi⊕ci다. 다음 bit는 이 carry를 기다린다. 별도의 병렬 carry 계산을 도입하지 않는 한, bit를 임의로 재배열해서 같은 인접 연결을 쓰기는 어렵다.
FPGA의 전용 carry 연결은 이 의존 경로를 일반 routing보다 직접적으로 만들 수 있다. 다만 직접 연결이 어느 블록의 어떤 입력까지 도달하는지가 정해져 있으므로, adder를 아무 위치에 놓고 연결만 전용으로 바꾸는 방식으로 생각하면 안 된다.
VTR은 carry처럼 제한된 구조에 맞는 atom들을 pack pattern으로 묶을 수 있게 한다. 별도의 direct 연결은 블록 간 상대 위치를 기술한다. VTR Pack Patterns와 Direct Inter-block Connections
다섯 bit를 세 tile에 넣는 자체 예
가상의 tile마다 1bit adder 두 개가 있고 첫 adder의 carry가 두 번째로 연결된다고 하자. tile의 carry output은 같은 x 좌표에서 y가 하나 작은 tile의 carry input으로만 전용 연결된다고 정한다. 실제 특정 FPGA의 tile 규칙을 가져온 것은 아니다.
5bit adder는 bit 0·1, bit 2·3, bit 4의 세 묶음으로 나뉜다. 앞 두 묶음은 두 adder를 채우고 마지막은 하나를 사용한다. tile을 각각 (2,4), (2,3), (2,2)에 놓으면 묶음 사이의 carry가 정한 연결 방향을 따른다. 마지막 tile의 남는 adder는 이 예에서 사용하지 않는다.
입력을 31과 1, 최초 carry를 0으로 넣으면 낮은 다섯 sum bit는 0이고 마지막 carry는 1이다. bit 0에서 만든 carry가 나머지 bit를 순서대로 통과한다. 전체 32×32 입력 쌍의 정답과, 그 정답을 만드는 전용 경로의 합법적인 배치는 별도로 확인할 대상이다.
가운데 tile만 옮겨도 전용 경로가 끊긴다
중간 묶음을 (3,3)으로 옮기면 앞 묶음에서 중간 묶음으로 가는 x 변화가 +1, 중간에서 마지막으로 가는 변화가 −1이 된다. 정한 전용 연결의 x 변화 0을 만족하지 않는다. adder의 Boolean 함수는 그대로지만 두 연결을 같은 전용 edge로 구현할 수 없다.
일반 routing으로 우회할 수 있는 구조라면 기능을 유지할 가능성은 있다. 그러나 그 경로의 delay는 별도로 계산해야 한다. 일반 연결을 통한 fallback이 불가능한 모드라면 배치 자체를 다시 해야 한다. 모든 FPGA에서 자동 우회된다는 가정은 이 예에 포함하지 않는다.
자체 delay 모델에서 각 bit carry 단계가 0.05ns, tile 간 전용 연결이 0.08ns라고 지정하자. 5bit carry 전달 경로는 5×0.05+2×0.08=0.41ns다. 같은 두 tile 간 연결을 각각 0.45ns의 일반 경로로 대체하면 1.15ns다. 이는 지정한 직렬 carry 경로의 산술 비교이며 제품의 최고 주파수나 실제 route 결과가 아니다.
논리 최적화 뒤에 연결 계약을 다시 본다
adder를 줄였거나 중간 carry를 다른 logic에도 보내도록 바꾸면 전용 경로에 맞는 묶음이 달라질 수 있다. carry chain의 신호가 다른 소비자를 가진 경우에는 그 fanout을 구조가 밖으로 꺼낼 수 있는지도 확인한다. 추가 소비자가 있다는 이유만으로 전용 경로가 항상 유지되는 것은 아니다.
이때 netlist의 bit 순서, packing된 묶음, 상대 위치, 실제 routing과 timing을 이어서 추적한다. 전용 연결의 존재를 보고 모든 관련 경로가 자동으로 빨라졌다고 판단하지 않고, 시작 입력부터 어느 sum이나 carry endpoint가 critical한지 확인한다.
carry-chain 배치는 덧셈을 맞게 계산하는 문제에 공간적인 연결 계약을 더한다. 낮은 bit에서 높은 bit로 이어지는 순서를 실제 tile의 허용 방향과 맞추고, 배치 변경이나 최적화가 그 계약을 보존하는지 확인해야 한다. 전용 carry의 이득은 이 조건을 만족하는 경로에서 비로소 나타난다.