Clock-frequency assignment for multiple clock domain systems-on-a-chip

ABSTRACT

Modern systems-on-a-chip platforms support multiple clock domains, in which different sub-circuits are driven by different clock signals. Although the frequency of each domain can be customized, the number of unique clock frequencies on a platform is typically limited. We define the clock-frequency assignment problem to be the assignment of frequencies to processing modules, each with an ideal maximum frequency, such that the sum of module processing times is minimized, subject to a limit on the number of unique frequencies. We develop a novel polynomial-time optimal algorithm to solve the problem, based on dynamic programming. We apply the algorithm to the particular context of post-improvement of accelerator-based hardware/software partitioning, and demonstrate 1.5x-4x additional speedups using just three clock domains.

REFERENCES

• 1: Atmel Corp. 2005. FPSLIC (AVR with FPGA), http://www.atmel.com/products/FPSLIC/.
• 2: Sudarshan Banerjee , Nikil Dutt, Efficient search space exploration for HW-SW partitioning, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016752]
• 3: Celoxica. http://www.celoxica.com.
• 4: Chattopadhyay, A., and Z. Zilic. GALDS: A Complete Framework for Designing Multiclock ASICs and SoCs. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, Vol. 13, No. 6, June 2005.
• 5: David E. Lackey , Paul S. Zuchowski , Thomas R. Bednar , Douglas W. Stout , Scott W. Gould , John M. Cohn, Managing power and performance for System-on-Chip designs using Voltage Islands, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.195-202, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774601]
• 6: Cray XD1. Cray Supercomputers. http://www.crav.com/products/xd1/index.html.
• 7: Critical Blue. 2005. http://www.criticalblue.com
• 8: Eles, P., Z. Peng, K. Kuchcinsky, and A. Doboli. System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search. Design Automation for Embedded Systems, vo12, no 1, 5--32 Jan. 1997
• 9: Excalibur. Altera Corp., http://www.altera.com
• 10: 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]
• 11: Jingcao Hu , Youngsoo Shin , Nagu Dhanwada , Radu Marculescu, Architecting voltage islands in core-based system-on-a-chip designs, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013283]
• 12: Asawaree Kalavade , P. A. Subrahmanyam, Hardware/software partitioning for multi-function systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.516-521, November 09-13, 1997, San Jose, California, United States
• 13: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 14: Rakesh Kumar , Keith I. Farkas , Norman P. Jouppi , Parthasarathy Ranganathan , Dean M. Tullsen, Single-ISA Heterogeneous Multi-Core Architectures: The Potential for Processor Power Reduction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.81, December 03-05, 2003
• 15: Muttersbach, J., T Villiger, H Kaeslin, N Felber, and W. Fichtner. Globally-Asynchronous Locally-Synchronous Architectures to Simplify the Design of On-Chip Systems. IEEE Int. ASIC/SOC Conference, 1999.
• 16: Mimosys. http://http://www.mimosys.com/.
• 17: Takashi Miyamori , Kunle Olukotun, A Quantitative Analysis of Reconfigurable Coprocessors for Multimedia Applications, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.2, April 15-17, 1998
• 18: Rota, Gian Carlo. The Number of Partitions of a Set. American Mathematical Monthly., Vol 71. No 5 pp 498--504. 1964.
• 19: Greg Semeraro , Grigorios Magklis , Rajeev Balasubramonian , David H. Albonesi , Sandhya Dwarkadas , Michael L. Scott, Energy-Efficient Processor Design Using Multiple Clock Domains with Dynamic Voltage and Frequency Scaling, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.29, February 02-06, 2002
• 20: Greg Stitt , Frank Vahid , Shawn Nematbakhsh, Energy savings and speedups from partitioning critical software loops to hardware in embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.218-232, February 2004 [doi>10.1145/972627.972637]
• 21: Greg Stitt , Frank Vahid , Gordon McGregor , Brian Einloth, Hardware/software partitioning of software binaries: a case study of H.264 decode, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084905]
• 22: Virtex II and IV. Xilinx Corp., http://www.xilinx.com
• 23: David W. Wall, Limits of instruction-level parallelism, ACM SIGARCH Computer Architecture News, v.19 n.2, p.176-188, Apr. 1991
• 24: Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513966]