 |
|
|
|
|
|
 Title: |
US4698751:
Systolic array for solving cyclic loop dependent algorithms
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Parvin, Bahram A.; Fountain Valley, CA
|
| Assignee: |
Ford Aerospace & Communications Corporation, Detroit, MI
other patents from FORD AEROSPACE CORPORATION (204010) (approx. 538)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1987-10-06
/ 1984-07-13
|
| Application Number: |
US1984000630615
|
| IPC Code: |
Advanced:
G06F 9/44;
G06F 15/80;
Core:
G06F 15/76;
more...
IPC-7:
G06F 9/40;
|
| U.S. Class: |
Current:
712/019;
Original:
364/200;
364/754;
364/402;
|
| Field of Search: |
364/754,402,200 MS,300
|
| Priority Number: |
| 1984-07-13 |
US1984000630615 |
|
| 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×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).
|
| Attorney, Agent or Firm: |
Radlo, Edward J. ;
Zerschling, Keith L. ;
|
| Primary / Asst. Examiners: |
Harkcom, Gary V.; Lacasse, Randy
|
| Maintenance Status: |
E2 Expired Check current status
CC Certificate of Correction issued
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
DE FR GB
|
| Family: |
Show 8 known family members
|
First Claim:
Show all 9 claims |
What is claimed is:
1. A systolic array for solving an algorithm having cyclic loop dependency, in which two nested loops are executed n and m times, respectively; and the systolic array solves the algorithm in n+m+1 steps said array comprising:
- many identical cells serially connected to form a chain, so that each cell, except for first and last cells in the chain, is connected only to its two adjacent cells, while the first and last cells in the chain are connected only to their sole adjacent cells; wherein
- at certain moments during said algorithm solving, more than one cell is activated to perform a part of said solving so that the total time required to solve the algorithm is a linear function of the numbers of times the loops are executed.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 39 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G86-022686
|
| Other References: |
"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.
(6 pages)
Cited by 17 patents
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.
|
|
 Nominate this for the Gallery...
|
|
