Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2004-03-15
2008-09-16
Huisman, David J (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S240000
Reexamination Certificate
active
07426628
ABSTRACT:
A method for run-time prediction of a next caller of a shared functional unit, wherein the shared functional unit is operable to be called by two or more callers out of a plurality of callers. The shared functional unit and the plurality of callers are operable to execute in parallel on a parallel execution unit. The run-time prediction is used for data flow programs. The run-time prediction detects a calling pattern of the plurality of callers of the shared functional unit and predicts the next caller out of the plurality of callers of the shared functional unit. The run-time prediction then loads state information associated with the next caller out of the plurality of callers.
REFERENCES:
patent: 5265213 (1993-11-01), Weiser et al.
patent: 5903750 (1999-05-01), Yeh et al.
patent: 6247121 (2001-06-01), Akkary et al.
patent: 6282639 (2001-08-01), Puziol et al.
patent: 6289444 (2001-09-01), Nair
Thomas et al., “Using Dataflow Based Context for Accurate Value Prediction,” IEEE, 2001, pp. 107-117.
Hennessy and Patterson, “Computer Architecture—A Quantitative Approach, 2ndEdition,” 1996, p. 711.
Tarek Abdelzaher, Ella M. Atkins and Kang G. Shin; “QoS Negotiation in Real-Time Systems and Its Application to Automated Flight Control”; IEEE Transactions on Computers; Nov. 2000; pp. 1170-1183.
Hugo A. Andrade and Scott Kovner; “Software Synthesis from Dataflow Models for G and LabVIEW”; Thirty-Second Asilomar Conference on Signals, Systems & Computers; Nov. 1998; pp. 1705-1709.
Joseph Tobin Buck; “Scheduling dynamic dataflow graphs with Bounded Memory Using the Token Flow Model”; PhD Thesis, University of California at Berkeley; 1993; http://ptolemy.eecs.berkeley.edu/papers/jbuckThesis.
Giorgio Buttazzo and Luca Abeni; “Adaptive Rate Control through Elastic Scheduling”; IEEE Conference on Decision and Control; Dec. 2000; pp. 4883-4888.
Brendon Cahoon and Kathryn S. McKinley; “Data Flow Analysis for Software Prefetching Linked Data Structures in Java”; International Conference on Parallel Architectures and Compilation Techniques; 2001; pp. 280-291.
Po-Yung Chang, Eric Hao and Yale N. Patt; “Target Prediction for Indirect Jumps” 24th Annual International Symposium on Computer Architecture; 1997; pp. 274-283.
Marius Evers, Sanjay J. Patel, Robert S. Chappell and Yale N. Patt; “An Analysis of Correlation and Predictability: What Makes Two Level Branch Predictors Work”; 25th Annual International Symposium on Computer Architecture; 1998; pp. 52-61.
Edward A. Lee and Thomas M. Parks; “Dataflow Process Networks”; in Proceedings of the IEEE; Mar. 27, 1995; pp. 773-801.
Zhong Wang, Timothy W. O'Neil, and Edwin Hsing-Mean Sha, “Optimal Loop Scheduling for Hiding Memory Latency Based on Two-Level Partitioning and Prefetching” IEEE Transactions on Signal Processing; Nov. 2001; pp. 2853-2864.
Tse-Yu Yeh and Yale N. Patt; “Alternative Implementations of Two-Level Adaptive Branch Prediction”; 19th Annual International Symposium on Computer Architecture; 1992; pp. 124-134.
T.-Y. Yeh and Y. N. Patt; “Two-level adaptive training branch prediction”; Proceedings of the 24th Annual ACM/IEEE International Symposium on Microarchitecture; 1991; pp. 51-61.
Newton G. Petersen and Martin R. Wojcik; “Feasibility Analysis of Caller Prediction”; Mar. 21, 2002; 4 pages; The Department of Electrical and Computer Engineering—The University of Texas at Austin.
Newton G. Petersen and Martin R. Wojcik; “Node Prefetch Prediction in Dataflow Graphs—Literature Survey”; Mar. 25, 2002; 9 pages; The Department of Electrical and Computer Engineering—The University of Texas at Austin.
Newton G. Petersen and Martin R. Wojcik; “Node Prefetch Prediction in Dataflow Graphs—Final Presentation” Apr. 29, 2002; 9 pages; The Department of Electrical and Computer Engineering—The University of Texas at Austin.
Newton G. Petersen and Martin R. Wojcik; “Node Prefetch Prediction in Dataflow Graphs—Final Report”; May 8, 2002; The Department of Electrical and Computer Engineering—The University of Texas at Austin.
Kurt Keutzer; “Lecture 9: Digital Signal Processors: Applications and Architectures”; Computer Science 252, Spring 2000.
David B. Skillicorn and Domenico Talia; “Models and Languages for Parallel Computation”; ACM Computing Surveys; Oct. 1996; 55 pages; vol. 30, No. 2.
Zhong Wang, Michael Kirkpatrick and Edwing Hsing-Mean Sha; “Optimal Two Level Partitioning and Loop Scheduling for Hiding Memory Latency for DSP Applications”; Design Automation Conference; 2000; 5 pages.
Piet Wauters, Marc Engels, Rudy Lauwereins and J.A. Peperstraete; “Cyclo-Dynamic Dataflow”; 4th EUROMICRO Workshop on Parallel and Distributed Processing; Jan. 1996; pp. 319-326.
Stephen Edwards, Luciano Lavagno, Edward A. Lee and Alberto Sangiovanni-Vincentelli; “Design of Embeded System: Formal Models, Validation, and Synthesis”; Proceedings of the IEEE; Mar. 1997; pp. 366-387; vol. 85, Iss. 3.
Newton G. Petersen and Martin R. Wojcik; “Node Prefetch Prediction in Dataflow Graphs”; IEEE Workshop on Signal Processing Systems; Oct. 2004; pp. 310-315.
Gilles Kahn and David B. MacQueen; “Coroutines and Networks of Parallel Processes”; Information Processing 77—Proceedings of IFIP Congress 77; Toronto, Canada; Aug. 8-12, 1977; pp. 993-998.
Hood Jeffrey C.
Huisman David J
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
Wojcik Martin R.
LandOfFree
Run-time node prefetch prediction in dataflow graphs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Run-time node prefetch prediction in dataflow graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Run-time node prefetch prediction in dataflow graphs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3978611