SOMA: a tool for synthesizing and optimizing memory accesses in ASICs

ABSTRACT

Arbitrary memory dependencies and variable latency memory systems are major obstacles to the synthesis of large-scale ASIC systems in high-level synthesis. This paper presents SOMA, a synthesis framework for constructing Memory Access Network (MAN) architectures that inherently enforce memory consistency in the presence of dynamic memory access dependencies. A fundamental bottleneck in any such network is arbitrating between concurrent accesses to a shared memory resource. To alleviate this bottleneck, SOMA uses an application-specific concurrency analysis technique to predict the dynamic memory parallelism profile of the application. This is then used to customize the MAN architecture. Depending on the parallelism profile, the MAN may be optimized for latency, throughput or both. The optimized MAN is automatically synthesized into gate-level structural Verilog using a flexible library of network building blocks. SOMA has been successfully integrated into an automated C-to-hardware synthesis flow, which generates standard cell circuits from unrestricted ANSI-C programs. Post-layout experiments demonstrate that application specific MAN construction significantly improves power and performance.

REFERENCES

• 1: Tobias Bjerregaard , Jens Sparso, A Scheduling Discipline for Latency and Bandwidth Guarantees in Asynchronous Network-on-Chip, Proceedings of the 11th IEEE International Symposium on Asynchronous Circuits and Systems, p.34-43, March 14-16, 2005 [doi>10.1109/ASYNC.2005.7]
• 2: Mihai Budiu , Seth C. Goldstein, Optimizing memory accesses for spatial computation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 3: A. Bystrov , D. J. Kinniment , A. Yakovlev, Priority Arbiters, Proceedings of the 6th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.128, April 02-06, 2000
• 4: C Level Design, http://www.cleveldesign.com/. C2HDL.
• 5: Gwenole Corre , Eric Senn , Pierre Bomel , Nathalie Julien , Eric Martin, Memory Accesses Management During High Level Synthesis, Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04), p.42-47, September 08-10, 2004 [doi>10.1109/CODES+ISSS.2004.39]
• 6: CoWare, http://www.coware.com/. N2C.
• 7: Frontier Design, http://www.frontierd.com/. A|rt Builder.
• 8: Abhijit Ghosh , Joachim Kunkel , Stan Liao, Hardware synthesis from C/C++, Proceedings of the conference on Design, automation and test in Europe, p.82-es, January 1999, Munich, Germany [doi>10.1145/307418.307529]
• 9: Pravil Gupta , Alice C. Parker, SMASH: a program for scheduling memory-intensive application-specific hardware, Proceedings of the 7th international symposium on High-level synthesis, p.54-59, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 10: Michael Hind , Anthony Pioli, Evaluating the effectiveness of pointer alias analyses, Science of Computer Programming, v.39 n.1, p.31-55, Jan. 2001 [doi>10.1016/S0167-6423(00)00014-9]
• 11: Takashi Kambe , Akihisa Yamada , Koichi Nishida , Kazuhisa Okada , Mitsuhisa Ohnishi , Andrew Kay , Paul Boca , Vince Zammit , Toshio Nomura, A C-based synthesis system, Bach, and its application (invited talk), Proceedings of the 2001 conference on Asia South Pacific design automation, p.151-155, January 2001, Yokohama, Japan [doi>10.1145/370155.370309]
• 12: P. G. Kjeldsberg , F. Catthoor , E. J. Aas, Storage requirement estimation for optimized design of data intensive applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.2, p.133-158, April 2004 [doi>10.1145/989995.989996]
• 13: David J. Kolson , Alexandru Nicolau , Nikil Dutt, Integrating program transformations in the memory-based synthesis of image and video algorithms, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.27-30, November 06-10, 1994, San Jose, California, United States
• 14: E. Larson, S. Chatterjee, et al. MASE: A novel architecture for detailed microarchitectural modeling. In ISPASS, November 4--6 2001.
• 15: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Stan Y. Liao, Towards a new standard for system-level design, Proceedings of the eighth international workshop on Hardware/software codesign, p.2-6, May 2000, San Diego, California, United States [doi>10.1145/334012.334013]
• 17: Chun-Gi Lyuh , Taewhan Kim, Memory access scheduling and binding considering energy minimization in multi-bank memory systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996596]
• 18: Gaurav Mittal , David C. Zaretsky , Xiaoyong Tang , P. Banerjee, Automatic translation of software binaries onto FPGAs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996678]
• 19: Seong Y. Ohm , Fadi J. Kurdahi , Nikil Dutt , Min Xu, A comprehensive estimation technique for high-level synthesis, Proceedings of the 8th international symposium on System synthesis, p.122-127, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224528]
• 20: Joonseok Park , Pedro C. Diniz, Synthesis of pipelined memory access controllers for streamed data applications on FPGA-based computing engines, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500054]
• 21: 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]
• 22: Jaewon Seo , Taewhan Kim , Preeti R. Panda, An integrated algorithm for memory allocation and assignment in high-level synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514072]
• 23: Greg Stitt , Zhi Guo , Walid Najjar , Frank Vahid, Techniques for synthesizing binaries to an advanced register/memory structure, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046208]
• 24: I. E. Sutherland, Micropipelines, Communications of the ACM, v.32 n.6, p.720-738, June 1989 [doi>10.1145/63526.63532]
• 25: G. Venkataramani, M. Budiu, et al. C to asynchronous dataflow circuits: An end-to-end toolflow. In IWLS, pages 501--508, June 2004. (full paper).
• 26: 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]
• 27: Kazutoshi Wakabayashi, C-based synthesis experiences with a behavior synthesizer, “cyber”, Proceedings of the conference on Design, automation and test in Europe, p.83-es, January 1999, Munich, Germany [doi>10.1145/307418.307530]
• 28: W. Wang , T. K. Tan , J. Luo , Y. Fei , L. Shang , K. S. Vallerio , L. Zhong , A. Raghunathan , N. K. Jha, A comprehensive high-level synthesis system for control-flow intensive behaviors, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764812]
• 29: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 30: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310074]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Topology (e.g., bus, point-to-point)

General Terms:
Design, Experimentation, Performance

Keywords:
high-level synthesis, memory synthesis