입력 슬루와 출력 로드를 고려한 덧셈트리 생성 알고리즘

Abstract

빠른 속도를 요구하는 시스템에서 빠른 연산기의 합성은 가장 중요한 고려사항 중 하나이다. 그 중에서도 전가산기(full adder)를 이용하여 각 비트별로 더해 나가는 것은 고전적이면서도 꽤 좋은 성능을 보여준다. 이 논문에서는 이에 관한 선행 연구에서의 두 가지 문제점을 해결하여 성능을 향상시켰다. 그 두 가지 문제점이란, (1) 입력 단자의 슬루와 (2) 출력 단자의 로드 모두를 고려하지 않고 덧셈 트리를 설계한 것이다. 이러한 두 가지 요소를 고려하지 않고 전가산기의 지연 시간을 상수로 가정하여 덧셈 트리를 설계하게 되면 더하려는 피연산자의 개수가 적을 경우에는 큰 차이가 없지만 피연산자의 개수가 많아질수록 앞에서 언급한 두 가지 요소를 고려하여 덧셈 트리를 만든 경우에 비해서 지연 시간이 점점 더 늘어나게 된다. 이 논문에서는 실제 DSP와 같은 회로에서 많이 등장하는 연산에 대해서 이 논문에서 제시하는 알고리즘과 기존의 가장 유명한 덧셈 트리 생성 알고리즘과의 성능을 비교하여 지연 시간 측면에서 평균 12% 의 성능 향상이 있음을 보인다.

Synthesis of fast arithmetic circuit is the most considerable factor in the timing-driven system. Above all, adding with a full adder is not only classic but also shows pretty good performance. In this paper, we improved performance of the previous work that has two limitations: (1) unawareness of slew rate in the input port and (2) unawareness of capacitance load in the output port. In this paper, we proposed a methodology for generating an adder tree with full adders considering those two limitations. From our algorithm, the critical path delay reduces 12% on average compared with the previous work in many arithmetic expressions which often appears in the arithmetic circuit such as DSP.