An algorithm for synthesis of large time-constrained heterogeneous adaptive systems

ABSTRACT

Large time-constrained applications are highly computer-intensive and are often implemented as a complex organization of pipelined data parallel tasks on a pool of embedded processors, DSP processors, and FPGAs. The large number of design alternatives available at each task level, the application as a whole, and the special needs of the reconfigurable devices (such as the FPGA) make the manual synthesis of such systems very tedious. The automatic synthesis algorithm in this paper combines exact (MILP-based) and heuristic techniques to solve this problem, which basically involves (1) propagation of timing constraints; (2) pipelining the loops to meet throughput requirements; (3) resource selection and scheduling, keeping the processing requirements and the timing constraints in view; (4) scheduling the resources across the tasks to ensure maximum utilization; and (5) hiding the reconfiguration delays of the FPGAs. While the use of MILP techniques helps in getting high-quality results, combining them with heuristics ensures acceptable synthesis times, striking a good balance between quality of results and synthesis time. Our experimental evaluation of the algorithm shows an average 40% in resource cost reduction (compared to manual synthesis) with synthesis times from minutes to as low as a few seconds in some cases.

REFERENCES

• 1: Smita Bakshi , Daniel D. Gajski, Hardware/software partitioning and pipelining, Proceedings of the 34th annual conference on Design automation, p.713-716, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266349]
• 2: BERKELAAR. 2001. lp_solve version 2.1. ftp://ftp.es.ele.tue.nl/pub/lp_solve.
• 3: BROWN,R.AND LINDERMAN, R. 1997. Algorithm development for an airborne real-time STAP demonstration. In Proceedings of the IEEE National Conference on Radar. IEEE Computer Society Press, Los Alamitos, CA.
• 4: Pai H. Chou , Ross B. Ortega , Gaetano Borriello, The Chinook hardware/software co-synthesis system, Proceedings of the 8th international symposium on System synthesis, p.22-27, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224491]
• 5: CHOUDHARY, A., LIO, W., WEINER, D., VARSHNEY, P., LINDERMAN, R., AND LINDERMAN, M. 1998. Design, implementation and evaluation of parallel pipelined STAP on parallel computers. In Proceedings of the 12th International Symposium on Parallel Processing.
• 6: DAVE,B.AND JHA, N. 1998. CORHA: Hardware-software C-synthesis of hierarchical distributed embedded system architectures. IEEE Trans. Comput.-Aided Des. 17 (Oct.), 900-919.
• 7: Y. G. DeCastelo-Vide-e-Souza , M. Potkonjak , Alice C. Parker, Optimal ILP-based approach for throughput optimization using simultaneous algorithm/architecture matching and retiming, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.113-118, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217516]
• 8: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 9: Robert P. Dick , Niraj K. Jha, CORDS: hardware-software co-synthesis of reconfigurable real-time distributed embedded systems, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.62-67, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288561]
• 10: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 11: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 12: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 13: GUPTA,R.AND DEMICHELI, G. 1992. System-level synthesis using re-programmable components. In Proceedings of the European Conference on Design Automation (EDAC '92, Brussels, Belgium, Mar. 16 - 19). IEEE Computer Society Press, Los Alamitos, CA, 2-7.
• 14: KALAVADE,A.AND LEE, E. 1992. Hardware/software co-design using Ptolemy: A case study. In Proceedings of the IFIP International Workshop on Hardware/Software Co-Design. IFIP.
• 15: Ireneusz Karkowski , Henk Corporaal, Design space exploration algorithm for heterogeneous multi-processor embedded system design, Proceedings of the 35th annual conference on Design automation, p.82-87, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277060]
• 16: PRAKASH,S.AND PARKER, A. C. 1992. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. J. Parallel Distrib. Comput. 16, 4 (Dec.), 338-351.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
delay/cost table, hierarchical control data-flow graph, list scheduling, mixed integer linear programming, pipelining, reconfigurable computing, time-constrained synthesis