Parallel neighborhood processing system and method

Claim 2

A processing system (8) for performing parallel processing operations upon data from a large array (40) of data having a plurality of rows and at least 2n columns, where n is an integer greater than one, by subdividing the large array into a plurality of subarrays (41, 42, 43, 44), where each subarray has a plurality of rows and only n columns, the system comprising and characterized by: an array (10) of n individual processing units (10a-10n) which includes an array (11) of n processing elements (11a-11n) which are linked together by a plurality of connections (14b-14n; 15a-15m), and an array (13) of n main memory means (13a-13n) for storing data to be processed, the array of n memory means being only n columns wide and having a sufficient number of rows to store at least two of the subarrays, each of the individual processing units including one of the processing elements and one of the main memory means, and at least a first co-memory means (21), associated with the first main memory means (13a), for storing the same data as stored in the first main memory means.

Claim 3

A system (8) as in claim 1, wherein the co-memory means (21) includes output means (23) for providing a nearest neighbor connection between itself and the nth processing element (11n).

Claim 4

A system (8) as in claim 2, wherein the output means (23) of the co-memory means is switchable in response to a control signal (32) received by the co-memory means to a predetermined state indicative of a first edge condition associated with the large array.

Claim 5

A system as in claim 3, further characterized by: means for selectively providing to the nearest neighbor connection associated with the output means (23) data indicative of the first edge condition of the large array; and memory address controller means (28) for providing row addresses to the array (13) of n main memory means and the one co-memory means (21) to specify which row within each of the main memory means and the one co-memory means is to be concurrently accessed, the controller means (28) including means for providing row addresses to the co-memory means which are displaced from the row addresses provided to the main memory means by an amount corresponding to the number of rows in the subarrays.

Claim 6

A system as in claim 1, in which the large array of data has H rows and at least 3n columns, and wherein the system performs parallel processing operations upon data from the large array by subdividing the large array into at least three subarrays of H rows by n columns each, and the array of n memory means has a sufficient number of rows to store at least the three subarrays, and the system further comprises: second co-memory means (25), associated with the nth main memory means (13n), for storing the same data as stored in the nth main memory means, includes output means (27) for providing a nearest neighbor connection between itself and the first processing element (11a), and wherein the output means of the second co-memory means is switchable in response to a control signal (33) received thereby to a predetermined state indicative of a second edge condition associated with the large array.

Claim 7

A processing system (8) for performing parallel processing operations upon data from a large array (40) of data having a plurality of rows and at least 2n columns, where n is an integer greater than one, by subdividing the large array into a plurality of subarrays (41, 42, 43, 44), where each subarray has a plurality of rows and only n columns, the system comprising and characterized by: an array (10) of n individual processing units (10a-10n) which includes an array (11) of neighborhood processing elements (11a-11n) linked together by a plurality or nearest neighbor connections, an array (12) of n data input and output means (12a-12n) for transferring data into and out of the array of processing units, and an array (13) of n memory means (13a-13n) for storing data associated with individual processing elements, each of the individual processing units including one of the neighborhood processing elements, one of the data input and output means, and one of the memory means, and the array (13) of n memory means (13a-13n) is sufficiently large to store at least two of the subarrays.

Claim 8

A processing system (8) for performing parallel processing operations upon data from a large array (40) of data having a plurality of rows and at least 2n columns, where n is an integer greater than one, by subdividing the large array into a plurality of subarrays (41, 42, 43, 44), where each subarray has a plurality of rows and only n columns, the system comprising and characterized by: an array (10) of n individual processing units (10a-10n) which includes an array (11) of neighborhood processing elements (11a-11n) linked together by a plurality or nearest neighbor connections, an array (12) of n data input and output means (12a-12n) for transferring data into and out of the array of processing units, and an array (13) of n memory means (13a-13n) for storing data associated with individual processing elements, each of the individual processing units including one of the neighborhood processing elements, one of the data input and output means, and one of the memory means, and the array (13) of n memory means (13a-13n) is sufficiently large to store at least two of the subarrays.

Claim 9

A system as in claim 6, wherein: the array of processing units include a plurality (16) of data lines (16a-16n) which interconnect each of the neighborhood processing elements to its respective data input and output means and its memory means, and each of the data lines in a bidirectional line and each of the processing units includes at least one such line.

Claim 10

A system as in claim 7, wherein: each of the memory means (13a-13n) is one-bit-wide, each of the data input and output means (12a-12n) are one-­bit-wide multibit shift registers, each of the neighborhood processing elements (11a-11n) include a set (60) of neighborhood input lines constituting the nearest neighbor connections, each of the sets including first and second lines for receiving data from two nearest neighborhood processing elements, each of the processing elements has neighborhood transformation means (64a-64n) for performing a transformation upon plural bits of input data received upon the set of neighborhood input lines associated with its processing element to produce an output, each of the processing elements (11) has a local multibit shift register (61, 62, 63) provided with first, second and third states, with each stage including an input and an output wherein the output of the first stage (61) is connected to the input of the second stage, and the output of the second stage is connected to the input of the third stage (63), and the set (60) of neighborhood input lines associated with each neighborhood processing element (11) further includes third, fourth and fifth lines respectively connected to the outputs of the first, second and third stages of the local multibit shift register which is part of its processing unit.

Claim 11

A system as in claim 8, wherein: the output of each neighborhood transformation means (64) is connected to the input of the first stage (61) of the local multibit shift register (12) of its processing element, the one bidirectional line connected to each neighborhood processing element is connected to the input of the first stage, and instruction controller means (35) for providing instructions to the array (10) of processing units, the instruction controller means including communication lines (36) connected to each of the neighborhood transformation means, and providing the same sequence of instructions to each of the neighborhood transformation means over the communication lines.

Claim 12

A system as in claim 6, wherein: the array (12) of data input and output means (12a-12n) is interconnected by a plurality (17) of nearest neighbor connections (17a-17n) between each of the data input and output means, each of the data input and output means includes a multistage shift register (61, 62, 63) having a serial input (65) and a serial output, and parallel inputs and parallel outputs (17) which provide parallel access to the individual stages thereof, the array of data input and output means includes means (20, 23, 30) for sequentially shifting in one direction through the multistage shift registers thereof a stream of data words having a plurality of bits equal in number to the number of stages in each of the shift registers, whereby each of the shift registers can be loaded with a distinct data word in the stream, and can output a distinct data word to the stream, and the means for sequentially shifting includes I/O controller means (23) for providing control signals to control the shifting of data words sequentially through the multistage shift registers.

Claim 13

In a processing system (8) for performing processing operations in parallel upon data from a large array (40) of data having at least a plurality of rows and 2n columns, where n is an integer greater than one, a method of storing data for subsequent processing by the system, comprising and characterized by the steps of: (a) providing, as at least part of the processing system, an array (10) of n processing units (10a-10n) each having local memory means (13a-13n) for storing plural units of data associated with distinct rows of the large array, first co-memory means (21), associated with the first local memory means (13a), for storing plural units of data, and second co-memory means (25), associated with the nth local memory means (13n), for storing plural units of data; (b) concurrently transferring a first row of n units of data from n columns of the large array into the n local memory means such that each unit of data is transferred into a distinct local memory means; and (c) concurrently with step (b) transferring into the first co-­memory means (21) the same unit of data being transferred into the first local memory means (13a), and into the second co-memory means (25) the same unit of data being transferred into the nth local memory means (13n).

Claim 14

In a processing system (8) for performing processing operations in parallel upon data from a large array (40) of data having at least a plurality of rows and 2n columns, where n is an integer greater than one, a method of storing data for subsequent processing by the system, comprising and characterized by the steps of: (a) providing, as at least part of the processing system, an array (10) of n processing units (10a-10n) each having local memory means (13a-13n) for storing plural units of data associated with distinct rows of the large array, first co-memory means (21), associated with the first local memory means (13a), for storing plural units of data, and second co-memory means (25), associated with the nth local memory means (13n), for storing plural units of data; (b) concurrently transferring a first row of n units of data from n columns of the large array into the n local memory means such that each unit of data is transferred into a distinct local memory means; and (c) concurrently with step (b) transferring into the first co-­memory means (21) the same unit of data being transferred into the first local memory means (13a), and into the second co-memory means (25) the same unit of data being transferred into the nth local memory means (13n).

Claim 15

A method as in claim 11, wherein each of the n units of data are one bit, and the n columns from which the data is taken constitute a first group of n contiguous columns, and the method further comprising and characterized by the steps of: (d) concurrently transferring a second row of n units of data from n columns of the large array into the n local memory means such that each unit of data is transferred into a distinct local memory means; (e) concurrently with step (d) transferring into the first co-memory means the same unit of data being transferred into the first local memory means (13a), and into the second co-memory means (25) the same unit of data being transferred into the nth local memory means (13n).

Claim 16

A method as in claim 12, wherein the method further comprising and characterized by the steps of: (f) concurrently transferring a first row of n units of data from a second group of n contiguous columns of the large array (40) into the n local memory means (13a-13n) such that each unit of data is transferred into a distinct local memory means; (g) concurrently with step (f) transferring into the first co-­memory means (21) the same unit of data being transferred into the first local memory means (13a), and into the second co-memory means (25) the same unit of data being transferred into the nth local memory means (13n); (h) concurrently transferring a second row of n units of data from the second group of n columns of the large array into the n local memory means such that each unit of data is transferred into a distinct local memory means; and (i) concurrently with step (h) transferring into the first co-­memory means (21) the same unit of data being transferred into the first local memory means (13a), and into the second co-memory means (25) the same unit of data being transferred into the nth local memory means (13n).

Claim 17

A method as in claim 11, for reading data as well as storing data, further characterized by the step of: (d) concurrently reading data from the local memory means (13) and at least one of the co-memory means (21), wherein the data is read from one row (70; 72; 75) of the n local memory means and a different row (71; 73; 76) of the at least one co-memory means (21).

Claim 18

A method as in claim 11, in which the large array (40) of data has at least H rows, and wherein: each of the local memory means (13a-13n) and each of the co-memory means (21; 25) can store at least 2H rows x 1 column of data, the data stored in the first H rows x n columns of the local memory means is from a first subarray (41) of H rows and a first set of n contiguous columns of the larger array, and the second H rows x n contiguous columns is from a second subarray (42) of the same H rows and a second set of n contiguous columns of the larger array, and the width of the columns of the local memory means and the co-memories are each one bit wide, and the method is further characterized by the step of: (d) concurrently reading data from the local memory means (13a-13n) and at least one of the co-memory means (21), wherein the data is read from one row (70; 72; 75) of the n local memory means and a different row (71, 73, 76) of the at least one co-memory means.

Claim 19

A method as in claim 11, for reading data as well as storing data, in which the large array (40) of data has at least H rows, wherein: each of the local memory means (13a-13n) and each of the co-memory means (21; 25) can store at least 3H rows x 1 column of data, the rows (80, 81, 82) in the n local memory means (13) and the co-memory means have corresponding row addresses, the data stored in the first H rows x n columns of the local memory means is from a first subarray (41) of H rows and a first set of n contiguous columns of the larger array, the data stored in the second H rows x n contiguous columns of the local memory means is from a second subarray (42) of the same H rows and a second set of n contiguous columns of the larger array, and the data stored in the third H rows x n contiguous columns of the local memory means is from a third subarray (43) of the same H rows and a third set of n contiguous columns of the larger array, and the method is further characterized by the step of: (d) concurrently reading data from the local memory means and the first and second co-memory means, with the data being read from one row (72) of the n local memory means, a different row (73) of the first co-memory means, and yet another row (74) of the second co-memory means, with the row addresses of the rows (73, 74) being concurrently read from the first and second co-memory means are H rows apart in different directions from the row address of the one row (72) of the n local memory means which is being read.