Bit-level scheduling of heterogeneous behavioural specifications

ABSTRACT

This paper presents a heuristic scheduling algorithm for heterogeneous specifications, those formed by operations of different types and widths. The algorithm extracts the common operative kernel of the operations, and binds afterwards operations to cycles with the aim of distributing uniformly the number of bits calculated per cycle. In consequence, operations may be fragmented and executed during a set of non-necessarily consecutive cycles, and over a set of several linked simple hardware resources. The proposed algorithm, in combination with allocation algorithms able to guarantee bit-level reuse of hardware resources, obtains considerably smaller datapaths than the ones proposed by conventional synthesis algorithms. In the datapaths produced the type, number, and width of the hardware resources are independent of the type, number, and width of the specification operations and variables.

REFERENCES

• 1: M. Molina , J. Mendias , R. Hermida, Multiple-Precision Circuits Allocation Independent of Data-Objects Length, Proceedings of the conference on Design, automation and test in Europe, p.909, March 04-08, 2002
• 2: R. Cmar , L. Rijnders , P. Schaumont , S. Vernalde , I. Bolsens, A methodology and design environment for DSP ASIC fixed point refinement, Proceedings of the conference on Design, automation and test in Europe, p.56-es, January 1999, Munich, Germany [doi>10.1145/307418.307503]
• 3: Y.N. Chang, and K.K. Parhi, "High-Performance Digit-Serial Complex-Number Multiplier-Accumulator". In Proceedings of ICCD, 1998.
• 4: H. Lee, and G.E. Sobelman. "FPGA-Based FIR Filters Using Digit-Serial Arithmetic". In Proceedings of the International ASIC Conference, 1997.
• 5: Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 6: Kayhan Küçükçakar , Alice C. Parker, Data path tradeoffs using MABAL, Proceedings of the 27th ACM/IEEE conference on Design automation, p.511-516, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123388]
• 7: Milos Ercegovac , Darko Kirovski , Miodrag Potkonjak, Low-power behavioral synthesis optimization using multiple precision arithmetic, Proceedings of the 36th ACM/IEEE conference on Design automation, p.568-573, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310000]
• 8: G. Constantinides , P. Cheung , W. Luk, Heuristic datapath allocation for multiple wordlength systems, Proceedings of the conference on Design, automation and test in Europe, p.791-797, March 2001, Munich, Germany
• 9: C.R. Baugh, and B.A. Wooley. "A two's Complement Parallel Array Multiplication Algorithm". IEEE Transactions on Computers, 1973.
• 10: P.G. Paulin, and J.P. Knight. "Force-Directed Scheduling for the Behavioral Synthesis of ASICS". IEEE Transactions on CAD, 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Experimentation, Theory