Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2007-11-27
2007-11-27
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C717S160000
Reexamination Certificate
active
09728441
ABSTRACT:
A processor method and apparatus that allows for the overlapped execution of multiple iterations of a loop while allowing the compiler to include only a single copy of the loop body in the code while automatically managing which iterations are active. Since the prologue and epilogue are implicitly created and maintained within the hardware in the invention, a significant reduction in code size can be achieved compared to software-only modulo scheduling. Furthermore, loops with iteration counts less than the number of concurrent iterations present in the kernel are also automatically handled. This hardware enhanced scheme achieves the same performance as the fully-specified standard method. Furthermore, the hardware reduces the power requirement as the entire fetch unit can be deactivated for a portion of the loop's execution. The basic design of the invention involves including a plurality of buffers for storing loop instructions, each of which is associated with an instruction decoder and its respective functional unit, in the dispatch stage of a processor. Control logic is used to receive loop setup parameters and to control the selective issue of instructions from the buffers to the functional units.
REFERENCES:
patent: 4626988 (1986-12-01), George
patent: 5579493 (1996-11-01), Kiuchi et al.
patent: 5664193 (1997-09-01), Tirumalai
patent: 5809308 (1998-09-01), Tirumalai
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5867711 (1999-02-01), Subramanian et al.
patent: 5898849 (1999-04-01), Tran
patent: 5898865 (1999-04-01), Mahalingaiah
patent: 6076159 (2000-06-01), Fleck et al.
patent: 6085315 (2000-07-01), Fleck et al.
patent: 6269440 (2001-07-01), Fernando et al.
patent: 6367071 (2002-04-01), Cao et al.
patent: 6421744 (2002-07-01), Morrison et al.
patent: 6598155 (2003-07-01), Ganapathy et al.
patent: 6832306 (2004-12-01), Ganapathy et al.
patent: 6988190 (2006-01-01), Park
Madhavi Gopal Valluri and R. Govindarajan. “Modulo-Variable Expansion Sensitive Scheduling”. High Performance Computing, 1998. HIPC '98. 5th International Conference on, Dec. 17-20, 1998. pp. 334-341.
InstantWeb. Online Computing Dictionary. Search term: interrupt □□http://www.instantweb.com/foldoc/foloc.cgi?query=interrupt.
P. Tirumalai, M. Lee, and M. Schlansker. “Parallelization of Loops with Exits on Piplined Architecutures”. Supercomputing '90. Processdings of, Nov. 12-16, 1990. pp. 200-212.
Uma Mahadevan, Kving Nomura, Roy Dz-ching Ju, and Rick Hank. “Applying Data Speculation in Modulo Scheduled Loops”. Parallel Architectures and Compilation Techniques, 2000. Proceedings International Conference on, Oct. 15-19, 2000. pp. 169-176.
Tanebaum, Andrew S. “Structured Computer Organization”. Second Edition. Englewood Cliffs, NJ: Prentice-Hall, Inc., © 1984. pp. 10-12.
B. R. Rau and C. D. Glaeser, Some Scheduling Techniques and An Easily Schedulable Horizonal Architecture for High Performance Scientific Computing,inProceedings of the 20thAnnual Workshop on Microprogramming and Microarchitecture, pp. 183-198, Oct. 1981.
J. C. Dehnert, P. Y. Hsu, and J. P. Bratt, Overlapped Loop Support in the Cydra 5,inProceedings of the 3rdInternational Conference on Architectural Support for Programming Languages and Operating Systems, pp. 26-38. Apr. 1989.
TMS320C6000 CPU and Instruction Set Reference Guide,Tech. Rep. SPRU189F, Texas Instruments, Oct. 2000, Chapters 1 and 2.
TMS320C6000 Programmers Guide, Rep. SPRU198G, Texas Instruments, Aug. 2002, pp. 5-32 to 5-149.
M. S. Lam, Software pipelining: An effective scheduling technique for VLIW machines,inProceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pp. 318-328, Jun. 1998.
B. R. Rau, M. S. Schlansker, and P. Tirumalai, Code generation schemas for modulo scheduled do-loops and white-loops, Tech. Rep. HPL-92-47, Hewlett Packard Labs, Apr. 1992.
D. M. Lavery,Modulo Scheduling for Control-Intensive General-Purpose Programs. Ph.D. thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1997.
Hwu Wen-mei W.
Merten Matthew C.
Chan Eddie
Impact Technologies, Inc.
Li Aimee J
Pillsbury Winthrop et al.
LandOfFree
Method and apparatus for modulo scheduled loop execution in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for modulo scheduled loop execution in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for modulo scheduled loop execution in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3825132