Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2003-08-29
2008-08-19
Dollinger, Tonia L. M. (Department: 2181)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S218000, C712S226000, C711S152000
Reexamination Certificate
active
07415601
ABSTRACT:
A method and apparatus for the elimination of prolog and epilog instructions in a vector processor. To eliminate the prolog, a functional unit of the vector processor has at least one input for receiving an input data value tagged with a data validity tag and an output for outputting an intermediate result tagged with a data validity tag. The data validity tags indicate the validity of the data. Before a loop is executed, the data validity tags are set to indicate that the associated data values are invalid. During execution of the loop body a functional unit checks the validity of input data. If all of the input data values are valid the functional operation is performed, the corresponding data validity tag set to indicate that the result is valid. If any of the input data values is invalid, the data validity tag of the result is set to indicate that the result is invalid. To eliminate the epilog, an iteration counter is associated with each sink unit of the vector processor. When a specified number of data values have been produced by a particular sink, no more data values are produced by that sink. The instructions for the pipelined loop body may be repeated, without alteration, to eliminate prolog and epilog instructions.
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: 5021945 (1991-06-01), Morrison 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: 5542084 (1996-07-01), Lowe, Jr.
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: 5852729 (1998-12-01), Limberis et al.
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: 6795908 (2004-09-01), Lee 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: 2002/1002228 (2002-08-01), Granston et al.
patent: 2003/0128712 (2003-07-01), Moriwaki et al.
patent: 2004/0003206 (2004-01-01), May et al.
patent: 2004/0117595 (2004-06-01), Norris
patent: 2005/0053012 (2005-03-01), Moyer
patent: 2005/0055534 (2005-03-01), Moyer
patent: 2005/0055543 (2005-03-01), Moyer
Hennessy and Patterson, Computer Architecture A Quantative Approach, 1996, Morgan Kaufman Publishers, Inc., Second Edition, pp. 239-247.
Lam, M., Software Pipelining: An Effective Scheduling Technique for VLIW Machines, Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, Atlanta, Georgia, Jun. 22-24, 1988, pp. 318-328.
Lee, T. 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.
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.
Aiken, A. et al., Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 12, Dec. 1995, pp. 1248-1270.
Wulf, William A. “Evaluation of the WM Architecture.” Proceedings of the 19thAnnual International Symposium on Computer Architecture: 1992, pp. 382-390, ACM 0-89791-509-7/92/0005/0382.
Talla, D.,Architectural techniques to Accelerate Multimedia Applications on General-Purpose Processors, Dissertation, Aug. 2001, pp. 94-125.
Talla, D.,Bottlenecks in Multimedia Processing with SIMD Style Extensions and Architectural Enhancements, IEEE Transactions of Computers, Aug. 2003, pp. 1015-1031, vol. 62, No. 8, IEEE.
Al-Mouhamed, M., “Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs”, IEEE, Dec. 1990.
Samadzadeh, F. et al., “A Heuristic Multiprocessor Scheduling Algorithm for Creating Near-Optimal Schedules Using Task System Graphs”, ACM, 1992.
Prasanna, G.N., et al., “Generalized Multiprocessor Scheduling for Directed Acylic Graphs”, IEEE, 1994.
Kwok, Y. et al., “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors”, ACM, Dec. 1999.
Essick, IV Raymond B.
Lucas Brian G.
May Philip E.
Moat Kent D.
Norris James M.
Dollinger Tonia L. M.
Motorola Inc.
LandOfFree
Method and apparatus for elimination of prolog and epilog... 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 elimination of prolog and epilog..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for elimination of prolog and epilog... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4010435