Systolic array for solving cyclic loop dependent algorithms

Details Systolic array for solving cyclic loop dependent algorithms Systolic array for solving cyclic loop dependent algorithms

1984-07-13

1987-10-06

Harkcom, Gary V.

Boots, shoes, and leggings

364754, 364402, G06F 940

Patent

active

046987517

ABSTRACT:
A systolic array (1) for reducing the time required to solve an algorithm having cyclic loop dependency, i.e., nested loops in which values calculated by inner loops depend upon indices of said inner loops and upon indices of outer loops. The array (1) comprises a chain of several identical serially connected and sequentially accessed cells. In the preferred embodiment, each cell, except for first and last cells in the chain, is connected to its two adjacent cells only. Multiprocessing is employed: at certain times during the algorithm solving, more than one cell is simultaneously activated to perform portions of the solving, so that the total time required to solve the algorithms is shortened to be a linear function of n.times.m. The algorithm can represent measurement of the distance between two symbolic strings, or other problems in artificial intelligence or logic. The algorithm is broken up into nm subalgorithms D(i,j); at each processing step, those subalgorithms D(i,j) are solved for which sufficient information exists for their solution. In the illustrated example, this condition is represented by diagonally time-slicing a two-dimensional matrix having as elements each of the subalgorithms D(i,j).

REFERENCES:
patent: 3568156 (1971-03-01), Thompson
patent: 4041461 (1977-08-01), Kratz et al.
patent: 4210962 (1980-07-01), Marsh et al.
patent: 4286330 (1981-08-01), Isaacson
patent: 4290115 (1981-09-01), Pitt et al.
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 4490811 (1984-12-01), Yianilos et al.
patent: 4493048 (1985-01-01), Kung et al.
patent: 4533993 (1985-08-01), McCanny et al.
"Approximate String Matching", Hall et al., Dec. 1980, ACM Computing Surveys, vol. 12, No. 4, pp. 381-402.
Kai Hwang, Computer Architecture and Parallel Processing, 1984, pp. 769-774.
"Microprocessor Arrays for Pattern Recognition", Boxer et al., Jun. 1977, pp. 59-65.
Kung, H. T., Warp: A Programmable Systolic Array Processor, Proc. Spie Int. Soc. Opt. Eng. vol. 495-Abstract.
Kung, H. T., "Systolic Algorithms for the CMU Warp Processor, 7th Internat. Conference on Pattern Recognition, 570-7, vol. 1-1984-Abstract.
"Systolic Array Processor Developments", Kung, H. T., CMU Conference on ULSI Systems and Comp.-1981-Abstract.
Kung, H. T., "Systolic Algorithms for CMU Warp Processor", 7th Internat. Conference on Pattern Recognition, 1984, Abstract, 570-7, vol. 1.
Electronic Design, Davis, etc., "Single--Chip Systolic Array Brings New Dimensions to Processing, Data, Oct. 31, 1984 (all pages).
Integrated Circuits, Davis, etc., "Systolic Architecture Tackles Image Feature Extraction", Mar. 1985, (all pages).
NCR--Geometric Arithmetic Parallel Processor Specification, 1984, all pages.
"Chip Compares Complex Strings", on pp. 81 and 84 of Electronic Engineering Times, Dec. 19, 1983.
Wagner, R. A., and Fischer, M. J., "The String-to-String Correction Problem", Journal of the Association for Computing Machinery, vol. 21, No. 1, (Jan. 1974), pp. 168-173.
Parvin, B. A., "A Structural Classifier for Ship Targets" to be published Jul. 1984 in the Proceedings of the 7th International Symposium on Pattern Recognition, Montreal, Canada.

Affiliated with

Also associated with

Rating

Systolic array for solving cyclic loop dependent algorithms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Systolic array for solving cyclic loop dependent algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systolic array for solving cyclic loop dependent algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2121982