Leveraging Protocol Knowledge in Slack Matching

 

In IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

Girish Venkataramani and Seth Copen Goldstein

San Jose, CA

November, 2006

Abstract


download pdf


@inproceedings{venkataramani-iccad06,
  title = {Leveraging Protocol Knowledge in Slack Matching},
  author = {Venkataramani, Girish and Goldstein, Seth Copen},
  booktitle = {IEEE/ACM International Conference on Computer-Aided
     Design (ICCAD)},
  year = {2006},
  address = {San Jose, CA},
  month = {November},
  abstract = {{Stalls, due to mis-matches in communication rates, are
     a major performance obstacle in pipelined circuits. If the rate
     of data production is faster than the rate of consumption, the
     resulting design performs slower than when the communication rate
     is matched. This can be remedied by inserting pipeline buffers
     (to temporarily hold data), allowing the producer to proceed if
     the consumer is not ready to accept data. The problem of deciding
     which channels need these buffers (and how many) for an arbitrary
     communication profile is called the slack matching problem; the
     optimal solution to this problem has been shown to be
     NP-complete. \par In this paper, we present a heuristic that uses
     knowledge of the communication protocol to explicitly model these
     bottlenecks, and an iterative algorithm to progressively remove
     these bottlenecks by inserting buffers. We apply this algorithm
     to asynchronous circuits, and show that it naturally handles
     large designs with arbitrarily cyclic and acyclic topologies,
     which exhibit various types of control choice. The heuristic is
     efficient, achieving linear time complexity in practice, and
     produces solutions that (a) achieve up to 60\% performance
     speedup on large media processing kernels, and (b) can either be
     verified to be optimal, or the approximation margin can be
     bounded. }},
  keywords = {Asychronous Circuits, Spatial Computing, CAD, Global
     Critical Path},
  url = {http://www.cs.cmu.edu/~seth/papers/venkataramani-iccad06.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.
Global Critical Path
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.
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.
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.
CAD
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.
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.
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.
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.
MolSpice: Designing Molecular Logic Circuits
Seth Copen Goldstein, James Ellenbogen, David Almassiam, Matt Brown, Mark Cannarsa, Jesse Klein, Schuyler Schell, Geoff Washburn, and Matthew M Ziegler. In Ninth Foresight Conference on Molecular Nanotechnology, November, 2001.
Static Profile-driven Compilation for FPGAs
Srihari Cadambi and Seth Copen Goldstein. In Proceedings of the 11th International Conference on Field-Programmable Logic and Applications, August, 2001.
BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
Mihai Budiu and Seth Copen Goldstein. Carnegie Mellon University Technical Report, June, 2000. See budiu-europar00.
Efficient Place and Route for Pipeline Reconfigurable Architectures
Srihari Cadambi and Seth Copen Goldstein. In ICCD '00, September, 2000.
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..
CPR: A Configuration Profiling Tool
Srihari Cadambi and Seth Copen Goldstein. In 7th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '99), pages 104, April, 1999.


Back to publications list