Method and apparatus for parallel table lookup using SIMD...

Details Method and apparatus for parallel table lookup using SIMD... Method and apparatus for parallel table lookup using SIMD...

2003-07-01

2010-06-15

Malzahn, David H (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

07739319

ABSTRACT:
Method, apparatus, and program means for performing a parallel table lookup using SIMD instructions. The method of one embodiment comprises loading a table having a set of L data elements. A determination of whether the table fits into a single register is made. A data lookup into the table is performed with a packed data shuffle operation if the determination indicates that the table does fit into a single register. The table is divided into a plurality of sections if the table does not fit into a single register. Each of the sections is sized to fit into a single register. A plurality of packed data shuffle operations are executed on the plurality of sections to look up data in the table.

REFERENCES:
patent: 3711692 (1973-01-01), Batcher
patent: 3723715 (1973-03-01), Chen et al.
patent: 4139899 (1979-02-01), Tulpule et al.
patent: 4161784 (1979-07-01), Cushing et al.
patent: 4393468 (1983-07-01), New
patent: 4418383 (1983-11-01), Doyle et al.
patent: 4490786 (1984-12-01), Nakatani
patent: 4498177 (1985-02-01), Larson
patent: 4707800 (1987-11-01), Montrone et al.
patent: 4771379 (1988-09-01), Ando et al.
patent: 4903228 (1990-02-01), Gregoire et al.
patent: 4989168 (1991-01-01), Kuroda et al.
patent: 5019968 (1991-05-01), Wang et al.
patent: 5081698 (1992-01-01), Kohn
patent: 5095457 (1992-03-01), Jeong
patent: 5168571 (1992-12-01), Hoover et al.
patent: 5187679 (1993-02-01), Vassiliadis et al.
patent: 5268995 (1993-12-01), Diefendorff et al.
patent: 5321810 (1994-06-01), Case et al.
patent: 5390135 (1995-02-01), Lee et al.
patent: 5408670 (1995-04-01), Davies
patent: 5423010 (1995-06-01), Mizukami
patent: 5426783 (1995-06-01), Norrie et al.
patent: 5465374 (1995-11-01), Dinkjian et al.
patent: 5487159 (1996-01-01), Byers et al.
patent: 5497497 (1996-03-01), Miller et al.
patent: 5524256 (1996-06-01), Turkowski
patent: 5579253 (1996-11-01), Lee et al.
patent: 5594437 (1997-01-01), O'Malley
patent: 5625374 (1997-04-01), Turkowski
patent: 5680161 (1997-10-01), Lehman et al.
patent: 5781457 (1998-07-01), Cohen et al.
patent: 5805915 (1998-09-01), Wilkinson et al.
patent: 5819101 (1998-10-01), Peleg et al.
patent: 5819117 (1998-10-01), Hansen
patent: 5822619 (1998-10-01), Sidwell
patent: 5838984 (1998-11-01), Nguyen et al.
patent: 5909572 (1999-06-01), Thayer et al.
patent: 5933650 (1999-08-01), van Hook et al.
patent: 6041404 (2000-03-01), Roussel et al.
patent: 6115812 (2000-09-01), Abdallah et al.
patent: 6192467 (2001-02-01), Abdallah et al.
patent: 6211892 (2001-04-01), Huff et al.
patent: 6223277 (2001-04-01), Karguth
patent: 6288723 (2001-09-01), Huff et al.
patent: 6381690 (2002-04-01), Lee
patent: 6484255 (2002-11-01), Dulong
patent: 6546480 (2003-04-01), Mandavilli et al.
patent: 6745319 (2004-06-01), Balmer et al.
patent: 6816961 (2004-11-01), Rice et al.
patent: 7155601 (2006-12-01), Chennupaty et al.
patent: 2001/0016902 (2001-08-01), Abdallah et al.
patent: 2002/0002666 (2002-01-01), Dulong et al.
patent: 2002/0112147 (2002-08-01), Chennupaty et al.
patent: 2002/0159529 (2002-10-01), Wang et al.
patent: 2002/0172287 (2002-11-01), King
patent: 2003/0084082 (2003-05-01), Debes et al.
patent: 2003/0123748 (2003-07-01), Sebot et al.
patent: 2003/0131030 (2003-07-01), Sebot et al.
patent: 2003/0231711 (2003-12-01), Zhang et al.
patent: 2004/0054877 (2004-03-01), Macy et al.
patent: 2004/0054878 (2004-03-01), Debes et al.
patent: 2005/0188182 (2005-08-01), Hoyle et al.
patent: WO 97/08608 (1997-03-01), None
U.S. Appl. No. 10/612,061 Non-Final Office Action, mailed Aug. 16, 2006, pp. 1-8.
U.S. Appl. No. 10/612,061 Final Office Action, mailed Mar. 13, 2007, pp. 1-6.
U.S. Appl. No. 10/612,061 Final Office Action, mailed Sep. 26, 2007, pp. 1-6.
U.S. Appl. No. 10/612,061 Final Office Action, mailed Nov. 23, 2007, pp. 1-6.
U.S. Appl. No. 10/612,061 Final Office Action, mailed Feb. 8, 2008, pp. 1-5.
U.S. Appl. No. 10/612,061 Final Office Action, mailed Oct. 8, 2008, pp. 1-5.
U.S. Appl. No. 10/611,344 Non-Final Office Action, mailed Dec. 29, 2005, pp. 1-23.
U.S. Appl. No. 10/611,344 Final Office Action, mailed Sep. 20, 2006, pp. 1-27.
U.S. Appl. No. 10/611,344 Advisory Action, mailed Dec. 19, 2006, pp. 1-3.
U.S. Appl. No. 10/611,344 Non-Final Office Action, mailed Apr. 4, 2007, pp. 1-21.
U.S. Appl. No. 10/611,344 Final Office Action, mailed Dec. 27, 2007, pp. 1-16.
U.S. Appl. No. 10/611,344 Advisory Action, mailed Mar. 18, 2008, pp. 1-3.
U.S. Appl. No. 10/611,344 Notice of Abandonment, mailed Jul. 18, 2008, pp. 1-2.
Avaro, Olivier, et al.,MPEG-4 Systems Overview and Architecture, woody.imag.fr/MPEG4/syssite/syspub/docs/tutorial/, May 28, 1998, pp. 1-71 plus Yahoo site ref.
Bierling, M.,Displacement Estimation by Hierarchical Blockmatching, SPIE, vol. 1001, Visual Communications and Image Processing, May 1998, pp. 942-951.
Chan, Y.L and W.C. Siu,Adaptive Multiple-Candidate Hierarchical Search for Block Matching Algorithm, IEE Electronics Letters, vol. 31, No. 19, Sep. 14, 1995, pp. 1637-1639.
Chan, Yui-Lam and Wan-Chi Siu,New Adaptive Pixel Decimation for Block Motion Vector Estimation, IEEE Transactions on Circuits and Systems on Video Technology, vol. 6, No. 1, Feb. 1996, pp. 113-118.
Chen, Liang-Gee, Wai-Ting Chen, Yeu-Shen Jehng Tzi-Dar Chuieh,An Efficient Parallel Motion Estimation Algorithm for Digital Image Processing, IEEE Transactions on Circuits and Systems on Video Technology, vol. 1, No. 4, Dec. 1991, pp. 378-384.
Cheng, K.W., S.C. Chan,Fast Block Matching Algorithms for Motion Estimation, ICASSP96, 1996, pp. 2318ff.
Corbal, Jesus, et al.,DLP+TLP Processors for the Next Generation of Media Workloads, 0-7695-1019-1/01, IEEE, 2001, pp. 219-228..
Day, Neil, Ed.,Introduction to MPEG-7(v.3.0), International Organization for Standardization, ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio, #N4032, Mar. 2001, pp. 1-10.
Dufaux, Frederic, et al.,Efficient, Robust, and Fast Global Motion Estimation for Video Coding, 1057-7149/00, IEEE, 2000, pp. 497-501.
Eckart, Stefan, Chad Fogg,ISO/IEC MPEG-2 Software Video Codec, SPIE vol. 2419, Digital Video Compression: Algorithms and Technologies, 1995, San Jose, CA, 15 pages.
Edirisinghe, E.A., et al.,Shape Adaptive Padding for MPEG-4, 0098 3063/00, IEEE, 2000, pp. 514-520.
Feng, J., Lo, K. T. Mehrpour, H. Karbowiak, A.E,Adaptive Block-Matching Motion Estimation Algorithm for Video Coding, IEE Electronics Letters, vol. 31, No. 18, 1995, pp. 1542-1543.
Furht, Botho, Joshua Greenberg, Raymond Westwater,Motion Estimation Algorithm for Video Compression, Kluwer Academic Publishers, Boston, 1997, pp. cover-vi, 11, 49-95.
Ghanbari, M.,The Cross-Search Algorithm for Motion Estimation, IEEE Transactions on Communications, vol. 38, No. 7, Jul. 1990, pp. 950-953.
He, Zhongli, M.L. Liou,A High Performance Fast Search Algorithm for Block Matching Motion Estimation, IEEE Transactions on Circuits and Systems on Video Technology, vol. 7, No. 5, Oct. 1997, pp. 826-828.
He, Zhong-Li, M.L. Liou,Design of Fast Motion Estimation Algorithm based on Hardware Consideration, IEEE Transactions on Circuits and Systems on Video Technology, vol. 7, No. 5, Oct. 1997, pp. 819-823.
Heising, G., et al.,MoMuSys: MPEG-4 Version 2 Video Reference Software Package, AC098/HHI/WP5.1/DS/P/049/B1, 1998, Abstract and pp. 1-8.
Intel Corporation,Block-Matching in Motion Estimation Alforithms Using Streaming SIMD Extensions 2(SSE2), Vers. 2.0 Sep. 22, 2000, Order No. 248605-001, pp. 1-13, A-1, A-2.
International Organisation for Standardisation,Optimization Model, Version 2.0, ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio, #N3675, Oct. 2000, 12 pages.
International Organisation for Standardisation,New MPEG-4 Profiles Under Consideration, ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio, #N3932, Jan. 2001, pp. 1-35.
Jain, J., A. Jain,Displacement Measurement and its Application in Interframe Image Coding, IEEE Transactions on Communications, vol. 29, No. 12, Dec. 1981, pp. 1799-1808.
Ju, John C.-H., et al.,A Fast Rate-Optimized Motion Estimation Algorithm for Low-Bit-Rate Video Coding, 1051-8215/99, IEEE, 1999, pp. 994-1002.
Jung, Hae Mook, Duch

Affiliated with

Also associated with

Rating

Method and apparatus for parallel table lookup using SIMD... 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 parallel table lookup using SIMD..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for parallel table lookup using SIMD... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4215590