Array mapping in behavioral synthesis

ABSTRACT

Abstract: This paper discusses the mapping of arrays in a behavior to memories in an implementation. We introduce a design representation based on a variety of array grouping techniques and the binding of array groups to memory components with different dimensions, access times, and number of ports. The results of design actions are computed in terms of the number of memory components and the length of schedules in the behavior. We demonstrate the ability of a synthesis tool using this representation to generate designs that span the entire range of the memory design space.

REFERENCES

• 1: M. Balakrishnan, A. Majmudar, D. Banerji, J. Linders, and J. Majithia, "Allocation of Multiport Memories in Data Path Synthesis," IEEE Trans. on CAD, April 1988.
• 2: Richard J. Cloutier , Donald E. Thomas, The combination of scheduling, allocation, and mapping in a single algorithm, Proceedings of the 27th ACM/IEEE conference on Design automation, p.71-76, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123230]
• 3: C. Coroyer and Z. Liu, Effectiveness of Heuristics and Simulated Annealing for the Scheduling of Concurrent Tasks: an Empirical Comparison. INRIA report 1379, 1991.
• 4: David Karchmer , Jonathan Rose, Definition and solution of the memory packing problem for field-programmable systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.20-26, November 06-10, 1994, San Jose, California, United States
• 5: Taewhan Kim , C. L. Liu, Utilization of multiport memories in data path synthesis, Proceedings of the 30th international conference on Design automation, p.298-302, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164900]
• 6: P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
• 7: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 8: E. Ochotta and T. Mukherjee, "Programmer's Guide to the Reconfigurable Simulated Annealing Library (anneal)," Report No. CMUCAD-94-35, Carnegie Mellon University, August 1994.
• 9: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 10: L. Ramachandran, D. D. Gajski, and V. Chaiyakul, "An Algorithm for Array Variable Clustering," Proc. of European Design and Test Conference (EDAC), 1994.
• 11: H. Schmit and D. E. Thomas, "Array Mapping for Behavioral Synthesis," Report No. CMUCAD-94-46, Carnegie Mellon University, October 1994.
• 12: H. Schmit , D. Thomas, Hidden Markov modeling and fuzzy controllers in FPGAs, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.214, April 19-21, 1995
• 13: Donald E. Thomas , Elizabeth D. Lagnese , John A. Nestor , Jayanth V. Rajan , Robert L. Blackburn , Robert A. Walker, Algorithmic and Register-Transfer Level Synthesis: The System Architect's Workbench, Kluwer Academic Publishers, Norwell, MA, 1989
• 14: Donald E. Thomas , Jay K. Adams , Herman Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test, v.10 n.3, p.6-15, July 1993 [doi>10.1109/54.232468]
• 15: Jan Vanhoof , Ivo Bolsens , Karl Van Rompaey , Gert Goossens , Hug De Man, High-Level Synthesis for Real-Time Digital Signal Processing, Kluwer Academic Publishers, Norwell, MA, 1993
• 16: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**; Formal models**

General Terms:
Design, Languages, Performance

Keywords:
access times, array grouping, array mapping, behavioral synthesis, binding, data structures, design representation, hardware description languages, hardware synthesis, memory architecture, memory components, memory design space, schedule length, scheduling, synthesis tool