Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-11-21
2006-11-21
Bullock, Jr., Lewis A. (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S105000, C718S104000
Reexamination Certificate
active
07140019
ABSTRACT:
A method for scheduling a computation for execution on a computer with a number of interconnected functional units. The computation is representable by a data-flow graph with a number of nodes connected by edge. A loop-period of the computation is calculated and the nodes are scheduled for throughput by assigning an execution cycle and a functional unit to each node of the data-flow graph. The scheduling of flexible nodes is adjusted to minimize the number of interconnections required in each execution cycle. The edges of the data-flow graph are allocated to one or more of the interconnections between functional units. The scheduling method may be used, for example, to optimize the interconnection fabric design for an ASIC or as part of a compiler for a re-configurable streaming vector processor.
REFERENCES:
patent: 3718912 (1973-02-01), Hasbrouck et al.
patent: 4128880 (1978-12-01), Cray, Jr.
patent: 4744043 (1988-05-01), Kloker
patent: 4760545 (1988-07-01), Inagami et al.
patent: 4807183 (1989-02-01), Kung et al.
patent: 4825361 (1989-04-01), Omoda et al.
patent: 4918600 (1990-04-01), Harper et al.
patent: 5206822 (1993-04-01), Taylor
patent: 5317734 (1994-05-01), Gupta
patent: 5367494 (1994-11-01), Shebanow et al.
patent: 5390352 (1995-02-01), Kinoshita
patent: 5418953 (1995-05-01), Hunt et al.
patent: 5423040 (1995-06-01), Epstein et al.
patent: 5450607 (1995-09-01), Kowalczyk et al.
patent: 5495617 (1996-02-01), Yamada
patent: 5652909 (1997-07-01), Kodosky
patent: 5697788 (1997-12-01), Ohta
patent: 5717947 (1998-02-01), Gallup et al.
patent: 5719998 (1998-02-01), Ku et al.
patent: 5734863 (1998-03-01), Kodosky et al.
patent: 5742821 (1998-04-01), Prasanna
patent: 5764787 (1998-06-01), Nickerson
patent: 5790877 (1998-08-01), Nishiyama et al.
patent: 5805614 (1998-09-01), Norris
patent: 5821934 (1998-10-01), Kodosky et al.
patent: 5826080 (1998-10-01), Dworzecki
patent: 5881257 (1999-03-01), Glass et al.
patent: 5881263 (1999-03-01), York et al.
patent: 5887183 (1999-03-01), Agarwal et al.
patent: 5893143 (1999-04-01), Tanaka et al.
patent: 5936953 (1999-08-01), Simmons
patent: 5966528 (1999-10-01), Wilkinson et al.
patent: 5969975 (1999-10-01), Glass et al.
patent: 5999736 (1999-12-01), Gupta et al.
patent: 6052766 (2000-04-01), Betker et al.
patent: 6064819 (2000-05-01), Franssen et al.
patent: 6104962 (2000-08-01), Sastry
patent: 6112023 (2000-08-01), Dave et al.
patent: 6128775 (2000-10-01), Chow et al.
patent: 6173389 (2001-01-01), Pechanek et al.
patent: 6192384 (2001-02-01), Daily et al.
patent: 6202130 (2001-03-01), Scales et al.
patent: 6253372 (2001-06-01), Komatsu et al.
patent: 6370560 (2002-04-01), Robertazzi et al.
patent: 6381687 (2002-04-01), Sandstrom et al.
patent: 6430671 (2002-08-01), Smith
patent: 6437804 (2002-08-01), Ibe et al.
patent: 6442701 (2002-08-01), Hurd
patent: 6490612 (2002-12-01), Jones et al.
patent: 6513107 (2003-01-01), Ansari
patent: 6571016 (2003-05-01), Mehrotra et al.
patent: 6588009 (2003-07-01), Guffens et al.
patent: 6598221 (2003-07-01), Pegatoquet et al.
patent: 6629123 (2003-09-01), Hunt
patent: 6647546 (2003-11-01), Hinker et al.
patent: 6665749 (2003-12-01), Ansari
patent: 6732354 (2004-05-01), Ebeling et al.
patent: 6745160 (2004-06-01), Ashar et al.
patent: 6792445 (2004-09-01), Jones et al.
patent: 6898691 (2005-05-01), Blomgren et al.
patent: 7000232 (2006-02-01), Jones et al.
patent: 7010788 (2006-03-01), Rehg et al.
patent: 2002/0080795 (2002-06-01), Van Wageningen et al.
patent: 2002/0112228 (2002-08-01), Granston et al.
patent: 2002/0120923 (2002-08-01), Granston et al.
patent: 2003/0128712 (2003-07-01), Moriwaki et al.
Al-Mouhamed, Mayez A. “Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs.” IEEE. Dec. 1990.
Samadzadeh, Farideh A. et a. “A Heuristic Multiprocessor Scheduling Algorithm for Creating Near-Optimal Schedules Using Task System Graphs.” ACM. 1992.
Prasanna, G.N. Srinivasa et al. “Generalized Multiprocessor Scheduling for Directed Acylic Graphs.” IEEE. 1994.
Kwok, Yu-Kwong et al. “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors.” ACM. Dec. 1999.
Lam, Monica, “Software Pipelining: An Effective Scheduling Technique for VLIW Machines,” Procedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, Atlanta, Georgia, Jun. 22-24, 1988, pp. 318-323.
Lee, Tsing-Fa et al, “A Transformation-Based Method for Loop Folding,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 4, Apr. 1994, pp. 439-450.
Aiken, Alexander, et al., “Resource-Constrained Software Pipelining,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 12, Dec. 1995, pp. 1248-1270.
Talla, D.,Architectural techniques to Accelerate Multimedia Applications on General-Purpose Processors, Dissertation, Aug. 2001, pp. 94-125.
Wulf, W.A., Evaluation of the WM Architecture, Association for Comuting Machinery, 1992, pp. 382-390.
Kavi, K.M. et al., A Formal Definition of Data Flow Graph Models, IEEE Transactions on Computers, vol. C-35, No. 11, Nov. 1986, pp. 940-948.
Cooper, K.D. et al., Efficient Computation of Flow Insensitive Interprocedural Summary Information, SIGPLAN Notices, vol. 19, No. 6, Jun. 1984, pp. 247-258.
Strong, H.R., Vector Execution of Flow Graphs, Journal of the Association for Computing Machinery, vol. 39, No. 1, Jan. 1983, pp. 186-196.
Chiricescu Silviu
Essick, IV Raymond B.
Lucas Brian Geoffrey
May Philip E.
Moat Kent Donald
Bullock, Jr. Lewis A.
Motorola, inc.
LandOfFree
Scheduler of program instructions for streaming vector... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduler of program instructions for streaming vector..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduler of program instructions for streaming vector... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3664125