Efficient pipelining of synthesized synchronous circuits

Details Efficient pipelining of synthesized synchronous circuits Efficient pipelining of synthesized synchronous circuits

2005-09-06

2005-09-06

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06941541

ABSTRACT:
Method and apparatus for generating a pipelined synchronized circuit representation of a program loop. A dependence graph is generated from the program loop. The dependence graph represents operations and registers and connections therebetween. A minimum clock period and initiation interval are determined from the dependence graph. Until a scheduled graph is successfully generated, repeated attempts are made to generate a scheduled graph from operations and registers of the dependence graph using the minimum clock period and the initiation interval. With each failed attempt to generate a scheduled graph, the minimum clock period is increased prior to the next attempt to generate a scheduled graph.

REFERENCES:
patent: 6453446 (2002-09-01), van Ginneken
patent: 2003/0126580 (2003-07-01), Kurokawa et al.
C. Leiscrson, J. Saxe, “Retiming Synchronous Systems.” Algorithmica, 6(J), 1991.
C. Leiscrson, “Systolic and Semisystolic Design,” IEEE International Conference on Computer Designs / VLSI in Computers, 1983.
H. Touati, R. Brayton, “Computing the Initial States of Retimed Circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 1 Jan. 1993.
K. Eckl, J. Madre, P. Zepter, C. Legal, “A Practical Approach to Multiple-Class Retiming,”Proceedings of the 36thAMC/IEEE Conference on Design Automation, 1999.
V. Singhal, S. Malik, R. Brayton, “The Case for Retiming with Explicit Reset Circuitry,” International Conference on Computer-Aided Design, 1996.
B. Rau, “Iterative Modulo Scheduling,” HP Labs Technical Report HPL-94-115, Nov. 1995.
M. Papaefthymiou, “Understanding Retiming through Maximum Average-Weight Cycles,” Proceedings of the Third Annual ACM Symposium onn Parallel Algorithms and Architectures, 1991.
S. Kundu, L. Huisman, I. Nair, V. Iyengar, “A Small Test Generator for Large Designs,” International Test Conference, 1992.
C. Leiserson, J. Saxe, “Optimizing Synchronous Systems,” Journal of VLSI and Computer Systems, vol. 1, No. 1, 1983.
N. Shenoy, R. Rudell, “Efficient Implementation of Retiming,” 1994 IEEE/ACM International Conference on Computer-aided Design, 1994.
P. Pan, G. Chen, “Optical Retiming for Initial State Computation,” 12thInternational Conference on VLSI Design, Jan. 1999.
M. Wolfe, M. Lam, “A Loop Transformation Theory and Algorithm to Maximize Parallelism,” IEEE Transactions on Parallel and Distributed Systems, vol. 2, No. 4 Oct. 1991.
M. J. Wolfe, “More Iteration Space Tiling,” Proceedings of Supercomputing 89, 1989.
S. Hassoun, C. Ebeling, “Architectural Retiming: Pipelining Latency-Constrained Circuits,” 33rdDesign Automation Conference, 1996.
D. Maydan, J. Hennessy, M. Lam, “Efficient and Exact Data Dependence Analysis,” Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, 1991.
S. Mahike, “Exploiting Instruction-level Parallelism in the Presence of Conditional Branches,” Ph.D. Dissertation, University of Illinois, Sep. 1996.
J. Tiernan, “An Efficient Search Algorithm to Find the Elementary Circuits of a Graph,” Communication of the ACM, vol. 13 No. 12, Dec. 1970.
T. Callahan, J. Warwrzynek. “Adapting Software Pipelining for Reconfigurable Computing,” Proceedings of the International Conference on Compilers, Architectures, and Synthesis for Embedded Systems, Sep. 2000.
M. Gokhale, J. Stone. E. Gomersall, “Co-synthesis to a Hybrid RISC/FPGA Architecture,” Journal of VLSI Signal Processing Systems for Signal Image and Video Technology, vol. 24, No. 2, Mar. 2000.
R. Schreiber, S. Aditya, B. Rau, V. Kathali, S. Mahike, S. Abraham. G. Snider “High-Level Synthesis of Nonprogrammable Hardware Accelerators,” HP Labs Technical Report HPL-2000-31, 2000.
V. Srinivasan, R. Vemuir, “A Retiming Base Relaxation Heuristic for Resource-Constrained Loop Pipelining,” Proceedings of the Eleventh International Conference on VLSI Design: VLSI for Signal Processing, 1998.
P. Calland, A. Darte. Y. Robert, “Circuit Retiming Applied to Decomposed Software Pipelining.” IEEE Transactions on parallel and Distributed Systems, vol. 9, No. 1, Jan. 1998.
M. Weinhardt, W. Luk, “Pipeline Vectorization,” IEEE Transactions on Computer-Aided Designs of Integrated Circuits and Systems, vol. 20, No. 2, Feb. 2001.
T. O'Neil, S. Tongsima, E. Sha. “Optimal Scheduling of Data Flow Graphs Using Extended Retiming,” Proceedings of the ISCA 12thInternational Conference on Parallel and Distributed Computing Systems, 1999.
J. Monteiro, S. Devadas, P. Ashar, A. Mauskar, “Schedulig Techniques to Enable Power Mangement,” 33rdDesign Automation Conference, 1996.
H. Yun, J. Kim “Power-Aware Modulo Scheduling for High-Performance VLIW Processors.” International Symposium on Low Power Electronics and Design, 2001.
E. Musoll, J. Cordatella “Scheduling and Resource Binding for Low Power, ”Proceedings of the International Symposium on System Synthesis, 1995.

Affiliated with

Also associated with

Rating

Efficient pipelining of synthesized synchronous circuits does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient pipelining of synthesized synchronous circuits, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient pipelining of synthesized synchronous circuits will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3438397