Hardware Compilation of Application-Specific Memory Access Interconnect

 

IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems

Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein

25(5):756–771

2006

Abstract

A major obstacle to successful high-level synthesis (HLS) of large-scale application-specified integrated circuit systems is the presence of memory accesses to a shared-memory subsystem. The latency to access memory is often not statically predictable, which creates problems for scheduling operations dependent on memory reads. More fundamental is that dependences between accesses may not be statically provable (e.g., if the specification language permits pointers), which introduces memory-consistency problems. Addressing these issues with static scheduling results in overly conservative circuits, and thus, most state-of-the-art HLS tools limit memory systems to those that have predictable latencies and limit programmers to specifications that forbid arbitrary memory-reference patterns. A new HLS framework for the synthesis and optimization of memory accesses (SOMA) is presented. SOMA enables specifications to include arbitrary memory references (e.g., pointers) and allows the memory system to incorporate features that might cause the latency of a memory access to vary dynamically. This results in raising the level of abstraction in the input specification, enabling faster design times. SOMA synthesizes a memory access network (MAN) architecture that facilitates dynamic scheduling and ordering of memory accesses. The paper describes a basic MAN construction technique that illustrates how dynamic ordering helps in efficiently maintaining memory consistency and how dynamic scheduling helps alleviate the variable-latency problem. Then, it is shown how static analysis of the access patterns can be used to optimize the MAN. One optimization changes the MAN interconnect topology to increase concurrence. A second optimization reduces the synchronization overhead necessary to maintain memory consistency. Postlayout experiments demonstrate that SOMA’s application-specific MAN construction significantly improves power and performance for a range of benchmarks.

download pdf


@article{venkataramani-tcad06,
  title = {Hardware Compilation of Application-Specific Memory Access
     Interconnect},
  author = {Venkataramani, Girish and Bjerregaard, Tobias and Chelcea,
     Tiberiu and Goldstein, Seth Copen},
  journal = {IEEE Transactions on Computer Aided Design of Integrated
     Circuits and Systems},
  year = {2006},
  volume = {25},
  number = {5},
  pages = {756--771},
  issn = {0278-0070},
  abstract = {{A major obstacle to successful high-level synthesis
     (HLS) of large-scale application-specified integrated circuit
     systems is the presence of memory accesses to a shared-memory
     subsystem. The latency to access memory is often not statically
     predictable, which creates problems for scheduling operations
     dependent on memory reads. More fundamental is that dependences
     between accesses may not be statically provable (e.g., if the
     specification language permits pointers), which introduces
     memory-consistency problems. Addressing these issues with static
     scheduling results in overly conservative circuits, and thus,
     most state-of-the-art HLS tools limit memory systems to those
     that have predictable latencies and limit programmers to
     specifications that forbid arbitrary memory-reference patterns. A
     new HLS framework for the synthesis and optimization of memory
     accesses (SOMA) is presented. SOMA enables specifications to
     include arbitrary memory references (e.g., pointers) and allows
     the memory system to incorporate features that might cause the
     latency of a memory access to vary dynamically. This results in
     raising the level of abstraction in the input specification,
     enabling faster design times. SOMA synthesizes a memory access
     network (MAN) architecture that facilitates dynamic scheduling
     and ordering of memory accesses. The paper describes a basic MAN
     construction technique that illustrates how dynamic ordering
     helps in efficiently maintaining memory consistency and how
     dynamic scheduling helps alleviate the variable-latency problem.
     Then, it is shown how static analysis of the access patterns can
     be used to optimize the MAN. One optimization changes the MAN
     interconnect topology to increase concurrence. A second
     optimization reduces the synchronization overhead necessary to
     maintain memory consistency. Postlayout experiments demonstrate
     that SOMA's application-specific MAN construction significantly
     improves power and performance for a range of benchmarks.}},
  keywords = {Asychronous Circuits, Spatial
     Computing,Phoenix,Network-on-a-chip},
  url = {http://www.cs.cmu.edu/~seth/papers/venkataramani-tcad06.pdf}
}

Related Papers

Spatial Computing
Hardware Compilation of Application-Specific Memory Access Interconnect
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 25(5):756–771,2006.
Leveraging Protocol Knowledge in Slack Matching
Girish Venkataramani and Seth Copen Goldstein. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), November, 2006.
Modeling the Global Critical Path in Concurrent Systems
Girish Venkataramani, Tiberiu Chelcea, Mihai Budiu, and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-06-144, August, 2006.
Tartan: Evaluating Spatial Computation for Whole Program Execution
Mahim Mishra, Timothy J Callahan, Tiberiu Chelcea, Girish Venkataramani, Mihai Budiu, and Seth Copen Goldstein. In 12th ACM International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS), pages 163–174, October, 2006.
Dataflow: A Complement to Superscalar
Mihai Budiu, Pedro V. Artigas, and Seth Copen Goldstein. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 177–186, March, 2005.
SOMA: A Tool for Synthesizing and Optimizing Memory Accesses in ASICs
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES-ISSS), pages 231–236, September, 2005.
HLS Support for Unconstrained Memory Accesses
Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 14th International Workshop on Logic Synthesis (IWLS), June, 2005.
Spatial Computation
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 14–26, October, 2004.
Translating ANSI C to Asynchronous Circuits
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In 10th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC '04), April, 2004.
C to Asynchronous Dataflow Circuits: An End-to-End Toolflow
Girish Venkataramani, Mihai Budiu, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 13th International Workshop on Logic Synthesis (IWLS), June, 2004.
Defect Tolerance After the Roadmap
Mahim Mishra and Seth Copen Goldstein. In Proceedings of the 10th International Test Synthesis Workshop (ITSW), March, 2003.
Defect Tolerance at the End of the Roadmap
Mahim Mishra and Seth Copen Goldstein. In Proceedings of the International Test Conference (ITC), 2003, September, 2003.
Molecules, Gates, Circuits, Computer
Seth Copen Goldstein and Mihai Budiu. In Molecular Nanoelectronics,, January, 2003.
Optimizing Memory Accesses For Spatial Computation
Mihai Budiu and Seth Copen Goldstein. In Proceedings of the 1st International ACM/IEEE Symposium on Code Generation and Optimization (CGO 03), pages 216–227, March, 2003.
Compiling Application-Specific Hardware
Mihai Budiu and Seth Copen Goldstein. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications, pages 853–863, September, 2002.
Factors Influencing the Performance of a CPU-RFU Hybrid Architecture
Girish Venkataramani, Suraj Sudhir, Mihai Budiu, and Seth Copen Goldstein. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL), pages 955–965, September, 2002.
Pegasus: An Efficient Intermediate Representation
Mihai Budiu and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-02-107, pages 20, May, 2002.
NanoFabrics: Spatial Computing Using Molecular Electronics
Seth Copen Goldstein and Mihai Budiu. In Proceedings of the 28th International Symposium on Computer Architecture (ISCA), pages 178–189, July, 2001.
BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
Mihai Budiu, Majd Sakr, Kevin Walker, and Seth Copen Goldstein. In Proceedings of the 2000 Europar Conference, volume 1900, pages 969–979,August, 2000. Also appeared as CMU CS Technical Report, CMU-CS-00-141, October 2000..
Asychronous Circuits
Heterogeneous Latch-Based Asynchronous Pipelines
Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. Asynchronous Circuits and Systems, International Symposium on, pages 83–92, 2008.
Slack Analysis in the System Design Loop
Girish Venkataramani and Seth Copen Goldstein. In IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES-ISSS), pages 231–236, October, 2008.
Area Optimizations for Dual-Rail Circuits Using Relative-Timing Analysis
Tiberiu Chelcea, Girish Venkataramani, and Seth Copen Goldstein. In Proceedings of the 13th IEEE International Symposium on Asynchronous Circuits and Systems, pages 117–128, March, 2007.
Global Critical Path: A Tool for System-Level Timing Analysis
Girish Venkataramani, Mihai Budiu, Tiberiu Chelcea, and Seth Copen Goldstein. In Proceedings of the 44th ACM/IEEE Design Automation Conference, pages 783–786, June, 2007.
Operation Chaining Asynchronous Pipelined Circuits
Girish Venkataramani and Seth Copen Goldstein. In ICCAD, November, 2007.
Self-Resetting Latches for Asynchronous Micro-Pipelines
Tiberiu Chelcea, Girish Venkataramani, and Seth Copen Goldstein. In Proceedings of the 44th ACM/IEEE Design Automation Conference, pages 986–989, June, 2007.
Hardware Compilation of Application-Specific Memory Access Interconnect
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 25(5):756–771,2006.
Leveraging Protocol Knowledge in Slack Matching
Girish Venkataramani and Seth Copen Goldstein. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), November, 2006.
Modeling the Global Critical Path in Concurrent Systems
Girish Venkataramani, Tiberiu Chelcea, Mihai Budiu, and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-06-144, August, 2006.
Tartan: Evaluating Spatial Computation for Whole Program Execution
Mahim Mishra, Timothy J Callahan, Tiberiu Chelcea, Girish Venkataramani, Mihai Budiu, and Seth Copen Goldstein. In 12th ACM International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS), pages 163–174, October, 2006.
Adding Faster with Application Specific Early Termination
David Ryan Koes, Tiberiu Chelcea, Charles Onyeama, and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-05-101, pages 20, May, 2005.
SOMA: A Tool for Synthesizing and Optimizing Memory Accesses in ASICs
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES-ISSS), pages 231–236, September, 2005.
HLS Support for Unconstrained Memory Accesses
Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 14th International Workshop on Logic Synthesis (IWLS), June, 2005.
Spatial Computation
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 14–26, October, 2004.
Translating ANSI C to Asynchronous Circuits
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In 10th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC '04), April, 2004.
C to Asynchronous Dataflow Circuits: An End-to-End Toolflow
Girish Venkataramani, Mihai Budiu, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 13th International Workshop on Logic Synthesis (IWLS), June, 2004.
Molecules, Gates, Circuits, Computer
Seth Copen Goldstein and Mihai Budiu. In Molecular Nanoelectronics,, January, 2003.
Phoenix
Hardware Compilation of Application-Specific Memory Access Interconnect
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 25(5):756–771,2006.
Tartan: Evaluating Spatial Computation for Whole Program Execution
Mahim Mishra, Timothy J Callahan, Tiberiu Chelcea, Girish Venkataramani, Mihai Budiu, and Seth Copen Goldstein. In 12th ACM International Conference on Architecture Support for Programming Languages and Operating Systems (ASPLOS), pages 163–174, October, 2006.
Dataflow: A Complement to Superscalar
Mihai Budiu, Pedro V. Artigas, and Seth Copen Goldstein. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 177–186, March, 2005.
Inter-iteration Scalar Replacement in the Presence of Conditional Control Flow
Mihai Budiu and Seth Copen Goldstein. In 3rd Workshop on Optimizations for DSO and Embedded Systems, March, 2005. Also appeared as CMU CS Technical Report, CMU-CS-04-103.
SOMA: A Tool for Synthesizing and Optimizing Memory Accesses in ASICs
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES-ISSS), pages 231–236, September, 2005.
HLS Support for Unconstrained Memory Accesses
Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 14th International Workshop on Logic Synthesis (IWLS), June, 2005.
Defect Tolerance at the End of the Roadmap
Mahim Mishra and Seth Copen Goldstein. In Nano, Quantum and Molecular Computing: Implications to High Level Design and Validation, 2004.
Inter-Iteration Scalar Replacement in the Presence of Conditional Control-Flow
Mihai Budiu and Seth Copen Goldstein. Carnegie Mellon University Technical Report, February, 2004. See budiu-odes05.
Programmer Specified Pointer Independence
David Ryan Koes, Mihai Budiu, Girish Venkataramani, and Seth Copen Goldstein. In Proceedings of the 2004 workshop on Memory system performance (MSP), pages 51–59, June, 2004. Also appeared as Carnegie Mellon University TR CMU-CS-03-123.
Spatial Computation
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 14–26, October, 2004.
Translating ANSI C to Asynchronous Circuits
Mihai Budiu, Girish Venkataramani, Tiberiu Chelcea, and Seth Copen Goldstein. In 10th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC '04), April, 2004.
C to Asynchronous Dataflow Circuits: An End-to-End Toolflow
Girish Venkataramani, Mihai Budiu, Tiberiu Chelcea, and Seth Copen Goldstein. In IEEE 13th International Workshop on Logic Synthesis (IWLS), June, 2004.
Defect Tolerance After the Roadmap
Mahim Mishra and Seth Copen Goldstein. In Proceedings of the 10th International Test Synthesis Workshop (ITSW), March, 2003.
Defect Tolerance at the End of the Roadmap
Mahim Mishra and Seth Copen Goldstein. In Proceedings of the International Test Conference (ITC), 2003, September, 2003.
Optimizing Memory Accesses For Spatial Computation
Mihai Budiu and Seth Copen Goldstein. In Proceedings of the 1st International ACM/IEEE Symposium on Code Generation and Optimization (CGO 03), pages 216–227, March, 2003.
Compiling Application-Specific Hardware
Mihai Budiu and Seth Copen Goldstein. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications, pages 853–863, September, 2002.
Factors Influencing the Performance of a CPU-RFU Hybrid Architecture
Girish Venkataramani, Suraj Sudhir, Mihai Budiu, and Seth Copen Goldstein. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications (FPL), pages 955–965, September, 2002.
Pegasus: An Efficient Intermediate Representation
Mihai Budiu and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-02-107, pages 20, May, 2002.
Scalable Defect Tolerance for Molecular Electronics
Mahim Mishra and Seth Copen Goldstein. In Proceedings of the 1st Workshop on Non-Silicon Computing (NSC-1), 2002.
NanoFabrics: Spatial Computing Using Molecular Electronics
Seth Copen Goldstein and Mihai Budiu. In Proceedings of the 28th International Symposium on Computer Architecture (ISCA), pages 178–189, July, 2001.
BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
Mihai Budiu, Majd Sakr, Kevin Walker, and Seth Copen Goldstein. In Proceedings of the 2000 Europar Conference, volume 1900, pages 969–979,August, 2000. Also appeared as CMU CS Technical Report, CMU-CS-00-141, October 2000..
Network-on-a-chip
Hardware Compilation of Application-Specific Memory Access Interconnect
Girish Venkataramani, Tobias Bjerregaard, Tiberiu Chelcea, and Seth Copen Goldstein. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 25(5):756–771,2006.


Back to publications list