High-level synthesis of distributed logic-memory architectures

ABSTRACT

With the increasing cost of global communication on-chip, high-performance designs for data-intensive applications require architectures that distribute hardware resources (computing logic, memories, interconnect, etc.) throughout a chip, while restricting computations and communications to geographic proximities. In this paper, we present a methodology for high-level synthesis (HLS) of distributed logic-memory architectures, i.e., architectures that have logic and memory distributed across several partitions in a chip. Conventional HLS tools are capable of extracting parallelism from a behavior for architectures that assume a monolithic controller/datapath communicating with a memory or memory hierarchy. This work provides techniques to extend the synthesis frontier to more general architectures that can extract both coarse- and fine-grained parallelism from data accesses and computations in a synergistic manner. Our methodology selects many possible ways of organizing data and computations, carefully examines the trade-offs (i.e., communication overheads, synchronization costs, area overheads) in choosing one solution over another, and utilizes conventional HLS techniques for intermediate steps.We have evaluated the proposed framework on several benchmarks by generating register-transfer level (RTL) implementations using an existing commercial HLS tool with and without our enhancements, and by subjecting the resulting RTL circuits to logic synthesis and layout. The results show that circuits designed as distributed logic-memory architectures using our framework achieve significant (upto, 5.31X average of 3.45X) performance improvements over well-optimized conventional designs with small area overheads (upto 19.3%, 15.1% on average).

REFERENCES

• 1: 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
• 2: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 3: Ingrid M. Verbauwhede , Chris J. Scheers , Jan M. Rabaey, Memory estimation for high level synthesis, Proceedings of the 31st annual conference on Design automation, p.143-148, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196313]
• 4: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.517-521, Oct., 2000 [doi>10.1109/92.894155]
• 5: F. Catthoor, F. Franssen, S. Wuytack, L. Nachtergaele, and H. De Man, "Global communication and memory optimizing transformations for low power signal processing systems," in Proc. Int. Wkshp. Low Power Design, 1994, pp. 51--56.
• 6: Peter Marwedel, The MIMOLA design system: Detailed description of the software system, Proceedings of the 16th Conference on Design automation, p.59-63, June 25-27, 1979, San Diego, CA, United States
• 7: H. De Man, F. Catthoor, G. Goossens, J. V. Meerbergen, J. Rabaey, and J. Huisken, "Architecture driven synthesis techniques for mapping digital signal processing structures into silicon," Proc. IEEE, vol. 78, no. 2, pp. 319--335, Feb. 1990.
• 8: R. Cloutier and D. Thomas, "The combination of scheduling, allocation, and mapping in a single algorithm," in Proc. Int. Symp. Microarchitecture, Dec. 1996, pp. 126--137.
• 9: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 10: 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
• 11: L. Ramachandran, D. D. Gajski, and V. Chaiyakul, "An algorithm for array variable clustering," in Proc. European Design Automation Conf., Mar. 1994, pp. 262--266.
• 12: Herman Schmit , Donald E. Thomas, Synthesis of application-specific memory designs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.101-111, March 1997 [doi>10.1109/92.555990]
• 13: Preeti R. Panda , Nikil D. Dutt, Behavioral Array Mapping into Multiport Memories Targeting Low Power, Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, p.268, January 04-07, 1997
• 14: Pradip K. Jha , Nikil D. Dutt, High-level library mapping for memories, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.566-603, July 2000 [doi>10.1145/348019.348297]
• 15: O. Sentieys, D. Chillet, J. P. Diguet, and J. L. Phillipe, "Memory module selection for high-level synthesis," in Proc. VLSI Signal Processing IX, Oct. 1996, pp. 273--282.
• 16: N. D. Holmes , D. D. Gajski, Architectural exploration for datapaths with memory hierarchy, Proceedings of the 1995 European conference on Design and Test, p.340, March 06-09, 1995
• 17: F. Balasa, Background Memory Allocation for Multi-dimensional Signal Processing, Ph.D. thesis, ESAT/EE Dept., K.U.Leuven, Belgium, 1995.
• 18: Kamal S. Khouri , Ganesh Lakshminarayana , Niraj K. Jha, Memory binding for performance optimization of control-flow intensive behaviors, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.482-488, November 07-11, 1999, San Jose, California, United States
• 19: Julio L. da Silva, Jr. , Francky Catthoor , Diederik Verkest , Hugo de Man, Power exploration for dynamic data types through virtual memory management refinement, Proceedings of the 1998 international symposium on Low power electronics and design, p.311-316, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280944]
• 20: Luc Séméria , Koichi Sato , Giovanni De Micheli, Synthesis of hardware models in C with pointers and complex data structures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.743-756, 12/1/2001 [doi>10.1109/92.974889]
• 21: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 22: ATOMIUM Project, IMEC, http://www.imec.be/atomium.
• 23: F. Vahid, "Techniques for minimizing and balancing I/O during functional partitioning," IEEE Trans. Computer-Aided Design, vol. 18, no. 1, pp. 69--75, Jan. 1999.
• 24: Christoforos E. Kozyrakis , Stylianos Perissakis , David Patterson , Thomas Anderson , Krste Asanovic , Neal Cardwell , Richard Fromm , Jason Golbus , Benjamin Gribstad , Kimberly Keeton , Randi Thomas , Noah Treuhaft , Katherine Yelick, Scalable Processors in the Billion-Transistor Era: IRAM, Computer, v.30 n.9, p.75-78, September 1997 [doi>10.1109/2.612252]
• 25: Mark Oskin , Frederic T. Chong , Timothy Sherwood, Active pages: a computation model for intelligent memory, Proceedings of the 25th annual international symposium on Computer architecture, p.192-203, June 27-July 02, 1998, Barcelona, Spain
• 26: Y. Kang, M. Huang, S. Yoo, Z. Ge, D. Keen, V. Lam, P. Pattnaik, and J. Torrellas, "Flexram: Toward an advanced intelligent memory system," Oct. 1999.
• 27: Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
• 28: Anant Agarwal , David A. Kranz , Venkat Natarajan, Automatic Partitioning of Parallel Loops and Data Arrays for Distributed Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.943-962, September 1995 [doi>10.1109/71.466632]
• 29: Jennifer Anderson, Automatic Computation and Data Decomposition for Multiprocessors, Stanford University, Stanford, CA, 1997
• 30: Amy Wingmui Lim , Monica S. Lam, Improving parallelism and data locality with affine partitioning, 2001
• 31: J. Ramanujam and P. Sadayappan, "Tiling multidimensional iteration spaces for multicomputers," J. Parallel & Distributed Computing, vol. 16, no. 2, pp. 108--230, 1992.
• 32: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 33: Roni Potasman , Joseph Lis , Alexandru Nicolau , Daniel Gajski, Percolation based synthesis, Proceedings of the 27th ACM/IEEE conference on Design automation, p.444-449, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123333]
• 34: K. Wakabayashi, C-Based High-Level Synthesis System, "CYBER"-Design Experience-, vol. 41, pp. 264--268, July 2000.
• 35: SYNOPSYS Design Compiler, VSS and Cyclone User Manual, http://www.synopsys.com.
• 36: TSMC 0.25mm Process High-Density Single-Port SRAM (HD-SRAM-SP) Generator User Manual, http://www.artisan.com.
• 37: Cadence Openbook SE 5.3, IC 4.4.5 and LVD 3.0, http://www.cadence.com.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Experimentation, Standardization, Theory