Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-01-02
2007-01-02
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
10683030
ABSTRACT:
Method and apparatus for reducing a number of storage elements in a synthesized synchronous circuit. In one embodiment, the circuit is represented as a directed, partitioned graph. The graph is divided into a plurality of time-ordered timeslots that are bounded by storage elements. The strongly-connected components (SCCs) in the graph are first identified. For each middle SCC where there is slack between the middle SCC and a first SCC and slack between the middle SCC and a second SCC, a time-slot-relative direction is selected for moving the middle SCC. The direction is selected as a function of a number of storage elements required for moving the middle SCC toward the first SCC versus moving the middle SCC toward the second SCC. The middle SCC is then moved in the selected time-slot-relative direction.
REFERENCES:
patent: 5822786 (1998-10-01), Widigen et al.
patent: 6421818 (2002-07-01), Dupenloup et al.
patent: 6453446 (2002-09-01), Van Ginneken
patent: 6460173 (2002-10-01), Schreiber
patent: 6507947 (2003-01-01), Schreiber et al.
patent: 6560754 (2003-05-01), Hakewill
patent: 6704909 (2004-03-01), Snider
patent: 6829716 (2004-12-01), Cook et al.
patent: 6941541 (2005-09-01), Snider
patent: 2002/0162097 (2002-10-01), Meribout
patent: 2003/0126580 (2003-07-01), Kurokawa et al.
Callahan et al., “Adapting Software Pipelining for Reconfigurable Computing”, Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems, 2000.
C. Leiscrson, J. Saxe. “Retiming Synchronous Systems.” Algorftmica, 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 Ratiming,”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, 1995.
M. Papaefthymiou, “Understanding Retiming through Maximum Average-Weight Cycles,” Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, 1991.
S. Kundu, L. Hisman, I. Nair, V. Iyengar, “A Small Test Generator for Large Designs,” International Test Conference, 1992.
C. Leiserson, J. Saxe, “Optimizing Sychronous 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.
P. Pan, G. Chen, “Optimal 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.
J. Tieman, “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, 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. Kathall, S. Mahike, S., Abraham, G. Snider “High-Level Synthesis of Nonprogrammable Hardware Accelerators,” HP Labs Technical Report HPL-2000-31.
V. Srinivasan, R. Vemuir, “A Retiming Base Relaxation Heuristic for Resource-Constained 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 Vectortzation,” 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. Devades, P. Ashar, A. Mauskar, “Scheduling 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. Cortadella Scheduling and Resource Binding for Low Power, Proceedings of the International Symposium on System Synthesis, 1995.
Levin Naum B.
Siek Vuthe
LandOfFree
Reduction of storage elements in synthesized synchronous... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reduction of storage elements in synthesized synchronous..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduction of storage elements in synthesized synchronous... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3739111