Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A Lower Bound Estimation on the number of LUT′s in Time-Multiplexed FPGA Synthesis

시분할 FPGA 합성에서 LUT 개수에 대한 하한 추정 기법

  • 엄성용 (서울여자대학교 정보통신공학부)
  • Published : 2002.08.01
Download PDF
⟨ Previous Next ⟩

Abstract

For a time-multiplexed FPGA, a circuit is partitioned into several subcircuits, so that they temporally share the same physical FPGA device by hardware reconfiguration. In these architectures, all the hardware reconfiguration information called contexts are generated and downloaded into the chip, and then the pre-scheduled context switches occur properly and timely. Since the maximum number of the LUT's required in the same time determines the size of the chip used in the synthesis, it needs to be minimized, if possible. Many previous work use their own approaches, which are very similar to either scheduling method in high level synthesis or multi-way circuit partitioning method, to solve the problem. In this paper, we propose a method which estimates the lower bound on the number of LUT's without performing any actual synthesis. The estimated lower bounds help to evaluate the results of the previous work. If the estimated lower bound on the number of LUT's exactly matches the number of LUT's of the result from the previous work, the result must be optimal. In contrast, if they do not match, the following two cases are expected : the more exact lower bound may exist, or we might find the new synthesis result better than the result from the previous work. Experimental results show that our lower bound estimation method is very accurate. In almost al] cases experimented, the estimated lower bounds on the number of LUT's exactly match those of the previous synthesis results respectively, implying that the best results from the previous work are optimal as well as our method predicted the exact lower bound for those examples.

주어진 논리 회로를 시분할 FPGA 칩으로 효과적으로 합성하기 위해서는 전체 회로를 여러 개의 부분회로로 나눈 후, 각 부분 회로가 동일한 하드웨어 회로를 시간차를 두고 공유하도록 하여야 한다. 이를 위해 칩에 대한 시간별 재구성 정보를 미리 만들어, 칩 내부의 특정 메모리 영역에 저장하여 두었다가 정해진 시간대가 되면 칩 전체를 재구성하도록 하여야 한다. 그런데, 시분할 FPGA 합성에서 사용하는 세부적인 재구성 기법(일반적으로 스케쥴링이나 다중 회로 분할 기법을 사용)에 따라 동일 시간대에 필요한 LUT의 개수, 즉 FPGA의 용량이 달라질 수 있다. 본 논문에서는 입력되는 논리 회로를 직접 합성하지 않고서도 그 회로가 필요로 하는 전체 LUT 개수에 대한 하한을 추정함으로써 재구성 기법에 관계없이 필요한 최소한의 LUT 개수를 파악한다. 만일, 기존의 재구성 결과가 본 연구에서 추정된 하한과 일치할 경우, 그 결과는 최적의 결과를 의미한다. 반면에, 하한과의 차이가 있는 경우에는 기존의 연구 결과에 비해 더 좋은 재구성 결과가 존재하거나, 또는 본 연구에서 추정한 하한보다 더 좋은(큰, 정확한) 하한이 실제 존재함을 의미한다. 따라서 이러한 비교 분석을 통해, 기존 연구의 결과가 최적인지, 또는 개선의 여지가 있는지를 판단하는 좋은 지표를 제공할 수 있다. 실험 결과, 실험한 대부분의 예제에서, 기존의 연구 결과에서 출력한 결과와 본 논문에서 제안한 방법으로 추정한 하한이 정확히 일치하는 것을 발견할 수 있었는데, 이는 기존의 합성 시스템에서 생성한 결과의 최적성을 확인하게 하는 한편, 본 논문에서 제안한 하한 추정의 정확성을 반증하는 것으로 해석될 수 있다.

Keywords

References

  1. R. Murgai, K. Brayton, and A. Sangiovanni-Vincentelli, 'Logic Synthesis for Field Programmable Gate Arrays,' Kluwer Academic Publisher, 1995
  2. Kang Yi, Seong Y. Ohm, and Chu S. Jhon, 'An Efficient FPGA Technology Mapping Tightly Coupled with Logic Minimization,' IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E80-A, pp.1807-1812, Oct. 1997
  3. S. Timberger, 'A Time-Multiplexed FPGA,' Proceedings of IEEE Symposium on FPGAs for Custom Computing Machines, 1997 https://doi.org/10.1109/FPGA.1997.624601
  4. S. Trimberger, 'Scheduling Designs into a Time-Multiplexed FPGA,' Proceedings of International Symposium on the Field Programming Gate Array, 1998, pp. 153-160 https://doi.org/10.1145/275107.275135
  5. D. Chang et al, 'Buffer Minimization and Time-Multiplexed I/O on Dynamically Reconfigurable FPGAs,' ACM/SIGDA International Synposium on Field Programmable Gate Arrays, 1997, pp. 142-148 https://doi.org/10.1145/258305.258331
  6. D. Chang at al, 'Partitioning Sequential Circuits on Dynamically Reconfigurable FPGAs,' ACM/ SIGDA International Synposium on Field Programmable Gate Arrays, 1998. pp. 161-167 https://doi.org/10.1145/275107.275136
  7. H. Liu and D.F. Wong, 'Circuit Partitioning for Dynamically Reconfigurable FPGAs,' ACM/SIGDA Interrational Synposium on Field Programmable Gate Arrays, 1999. pp.187-194 https://doi.org/10.1145/296399.296456
  8. H. Liu and D.F. Wong, 'Network Flow Based Circuit Partitioning for Time-Multiplexed FPGAs,' Proceedings of International Conference on the Computer Aided Design, 1998, pp. 497-504
  9. H. L. and D. F. Wong, 'A Graph Theoretic Optimal Algorithm for Scheduling Compression in Time-Multiplexed FPGA Partitioning,' Proceedings of International Conference on the Computer Aided Design, 1999, pp. 400-405
  10. M. C. McFarland, A. C. Parker, and R. Composano, 'Tutorial on High Level Synthesis,' Proceedings of the 25th Design Automation Conference, pp.330-336, June 1988
  11. C. T. Hwang, J. H. Lee, and Y. C. Chu, 'A Formal Approach to the Scheduling Problem in High Level Synthesis,' IEEE Transactions on Computer-Aided Design, pp.464-475, April 1991
  12. P. G. Paulin and J. P. Knight, 'Force-directed Scheduling for the Behavioral Synthesis of ASIC's,' IEEE Transactions on Computer-Aided Design, pp.661-679, June 1989 https://doi.org/10.1109/43.31522
  13. 엄성용, 전주식, '하한 비용 추정에 바탕을 둔 최적 스케쥴링 기법', 대한전자공학회 논문지, 제28권 A편 제12호, pp.73-87, 1991년 12월
  14. Seong Y. Ohm, Chu S. Jhon, and Fadi J. Kurdahi, 'An Optimal Scheduling Approach using Lower Bound in High-Level Synthesis,' IEICE Transactions on Information and Systems, Vol. E78-D, No.3, pp.231-236, March 1995
  15. Hyun-Chul Shin and Chung-Hee Kim, 'A Simple Yet Efficient Techniques for Partitioning,' IEEE Transactions on VLSI Systems, Vol. 1, No.3, pp.380-386, 1993 https://doi.org/10.1109/92.238449
  16. Seong Y. Ohm, Fadi J. Kurdahi, Nikil Dutt, 'A Unified Lower Bound Estimation Technique for High-Level Synthesis,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No.5, pp.458-472, May 1997 https://doi.org/10.1109/43.631209