Systolic array for solving cyclic loop dependent algorithms

• US 4,698,751 A
• Filed: 07/13/1984
• Issued: 10/06/1987
• Est. Priority Date: 07/13/1984
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Ford Aerospace & Communications Corporation (Galileo Parent, Inc.)
• Inventors: Parvin, Bahram A.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/630,615
• Time in Patent Office: 1,180 Days
• Field of Search: 364/754, 364/402, 364/200 MS, 364/300
• US Class Current: 712/19
• CPC Class Codes: G06F 15/8046 Systolic arrays

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).

Claims

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.

2. The systolic array of claim 1 wherein the cells are arranged and connected so as to employ techniques of dynamic programming.

3. The systolic array of claim 1 wherein the algorithm is broken up into several subalgorithms;

and

the systolic array solves the algorithm by completing a series of steps wherein, for each step, at least one cell is activated to solve those subalgorithms for which sufficient information exists to obtain a solution.

4. The systolic array of claim 1 wherein the number of cells is equal to the lesser of n and m.

5. The systolic array of claim 1 wherein the algorithm measures the distance between a first symbolic string having n symbols and a second symbolic string having m symbols.

6. A systolic array for solving a cyclic loop dependent algorithm having an inner loop that is executed m times and is nested within an outer loop that is executed n times, where values calculated by the inner loop depend upon the particular time at which the inner and outer loops are being executed and upon previous values, 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 n and m;

the array is architectured to break up the algorithm into n x m subalgorithms D(i,j) for all i between l and n inclusively, and for all j between 1 and m inclusively; and

the array performs n+m-1 steps;

during the first step, subalgorithm D(1,1) is solved by one of the cells;

during the second step, subalgorithms D(2,1) and D(1,2) are solved by two of the cells;

during the third step, if any, subalgorithms D(3,1), D(2,2), and D(1,3) are solved by three of the cells; and

in general, during the (n+m-1)st step subalgorithm D(n,m) is solved by one of the cells.

7. The array of claim 6 wherein each jth cell solves all the D(i,j) subalgorithms for all i.

8. The array of claim 6 wherein each ith cell solves all the D(i,j) subalgorithms for all j.

9. A systolic array for solving a cyclic loop dependent algorithm having an inner loop that is executed m times and is nested within an outer loop that is executed n times, where values calculated by the inner loop depend upon the particular time at which the inner and outer loops are being executed and upon previous values, 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 n and m;

the array is architectured to break up the algorithm into nxm subalgorithms D(i,j) for all i between l and n inclusively, and for all j between l and m inclusively; and

each cell comprises;

an arithmetic logic unit (ALU) having a ROM and a RAM, wherein the ROM comprises a stored program and a lookup table;

an upper storage register, an upper-left storage register, a left storage register, and a vector storage register, wherein each register is disposed to accept an input from a location external to the cell, and each register has an output connected to the ALU;

during said algorithm solving, an output of subalgorithm D(i,j) is passed to the upper storage register of the next adjacent cell in the chain, and to the left storage register of the instant cell;

a value of a vector provided by the ALU is passed to the vector storage register of the next adjacent cell in the chain;

the contents of the vector storage register are updated from a location external to the cell;

the contents of the upper storage register are passed to the upper-left storage register; and

the contents of the upper storage register are updated with an output of subalgorithm D(i+1,J).