Cache burst architecture for parallel processing, such as for image processing

• US 5,557,734 A
• Filed: 06/17/1994
• Issued: 09/17/1996
• Est. Priority Date: 06/17/1994
• Status: Expired due to Fees

• Current Assignee: Applied Intelligent Systems, Inc. (MKS Instruments Incorporated)
• Original Assignee: Applied Intelligent Systems, Inc. (MKS Instruments Incorporated)
• Inventors: Wilson, Stephen S.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): CHAUHAN, ULKA J
• Application Number:
  US08/261,538
• Time in Patent Office: 823 Days
• Field of Search: 395/162-166, 395/800, 382/303, 382/304, 364/748
• US Class Current: 345/505
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

A parallel processing system for processing data matrices, such as images, is disclosed. The system includes a plurality of processing units, organized in four blocks of eight processing units per processing chip, and external cache burst memory, wherein each processing unit is associated with at least one column of the external memory. A barrel shifter connected between the memory and the processing units allows data to be shifted to adjacent processing chips, thus providing the means for connecting several of the chips into a ring structure. Further, digital delay lines are connected between the barrel shifter and the processing units, thus providing the capability of delaying, via a predetermined number of clock cycles, incoming column data. Each processing unit is provided with a nine bit cache memory. The system further includes a controller for each chip that sequences a burst of consecutive rows of a data matrix from the external cache burst memory, to be stored in either the cache memory associated with each of the processing units or routed directly to the processors included in each processing unit.

The barrel shifters and the delay lines cooperate to bring horizontally and vertically displaced data points in the external memory to a single processing unit in a single clock cycle period. The controller decodes instructions stored in the external memory, wherein each processing unit receives the same instruction at any given cycle; this decoded instruction is valid for subsequent data bursts from external memory, thus providing the means for allowing instructions and data to be stored in the same external memory without a significant performance penalty. Where the width of an image is greater than the number of processing units, the image must be segmented to be stored in memory. An efficient method of relating column data across segment boundaries is thus provided, using the cache memory of selected processing units.

Claims

1. In a processing system for performing processing operations in parallel upon a data matrix stored in a memory means having L rows and M columns, where L and M are integers greater than one, the system including M processing units wherein each of the M processing units is associated with a respective column of the memory means, a method of transferring data between the memory means and the processing units, comprising the step of:

(A) shifting, in a first clock cycle, each bit of a first row of M data bits from the memory means one or more column positions to the processing unit associated with respectively adjacent columns of the memory means.

2. The method of claim 1, further comprising the step of:

(B) transferring, in the first clock cycle, each bit of the first row of M data bits to the respectively associated processing unit wherein horizontally displaced data values from the memory means are presented to each of the M processing units in the first clock cycle.

3. The method of claim 2 wherein step (A) further includes the step of delaying, respectively, each bit in the first row of M data bits shifted in step (A) by one or more clock cycles, and wherein step (B) further includes the step of delaying, respectively, each bit in the first row of M data bits transferred from the memory means by one or more clock cycles, wherein vertically displaced data values from the memory means are presented to each of the M processing units in one clock cycle.

4. In a processing system for performing processing operations in parallel upon data from an array of data stored in a first memory means having L rows and M columns, where L and M are integers greater than one, the system including an array of M processing units wherein each processing unit is associated with a respective plurality of second memory means, a method of transferring data between the first memory means and the processing units, comprising the steps of:

(A) bursting data in sequential row order from a first plurality of consecutive rows of the first memory means to a first one of the second memory means associated with each of the M processing units wherein the bursted data is stored in the first one of the second memory means; and

(B) transferring array data stored in step (A) to the array of processing units, including bursting the array data stored in step (A) from each first one of the second memory means to the respective processing unit.

5. The method of claim 4 wherein step (A) includes the substeps of:

providing a starting address of the first plurality of consecutive rows to the first memory means;

providing plurality of clock pulses to the first memory means; and

outputting from the first memory means the first plurality of consecutive rows of data, including outputting a further consecutive row, starting from a row having the starting address, for each provided clock pulse.

6. The method of claim 5 further including the step of bursting array data in sequential row order from a second plurality of consecutive rows of the first memory means to the array of M processing units, and

wherein step (B) further includes the step of synchronizing the data being burst out from the first one of the second memory means with the array data from the second plurality of consecutive rows of the first memory means, and transferring the synchronized data to the array of M processing units.

7. The method of claim 4 further comprising the step of bursting data in sequential row order from a second plurality of consecutive rows of the first memory means to a respective second one of the second memory means associated with each of the M processing units wherein the bursted data is stored in the second one of the second memory means, and

wherein step (B) further includes the step of bursting the data stored in the second one of the second memory means with the data being burst from the first one of the second memory means to the respective processing unit such that parallel streams of data are transferred to the respective processing unit.

8. The method of claim 7 wherein step (B) further includes the step of synchronizing the data being bursted out from the first and second ones of the second memory means with data in sequential row order being bursted out from a third plurality of consecutive rows of the first memory means, and transferring the synchronized data to the array of processing units.

9. The claim of method 8 wherein said second memory means comprises cache memory means.

10. In a processing system for performing processing operations in parallel upon a data matrix having P columns stored in a first memory means having L rows and M columns, where L, M and P are integers greater than one and P is greater than M, and wherein the data matrix is stored in the first memory means in a plurality of segments, the system including an array of M processing units wherein each of the M processing units is associated with a column of the first memory means, each processing unit has associated therewith a plurality of second memory means, a method of relating column data across segment boundaries, comprising the steps of:

(A) shifting the columns of a first segment at least one column position such that the column of data adjacent a first segment boundary is shifted across the first segment boundary;

(B) storing the column shifted across the first segment boundary in step (A) in a first one of the second memory means of the processing unit to which the shifted column of data is associated;

(C) shifting the columns of a second segment the same number of column positions as the first segment was shifted in step (A) such that the column of data adjacent the first segment boundary is shifted away from the first segment boundary;

(D) transferring the shifted second segment of column data to the M processing units; and

(E) transferring the data stored in the first one of the second memory means in step (B) to the associated processing unit such that column data on both sides of the first segment boundary are accessible to the M processing units.

11. The method of claim 10 wherein steps (D) and (E) are performed simultaneously.

12. The method of claim 11 wherein the number of column positions shifted in step (A) is two, and wherein step (B) includes the further step of storing the two columns shifted across the first segment boundary in respective first ones of the second memory means of the processing unit to which the shifted columns of data are respectively associated, and wherein step (E) includes the further step of transferring the data stored in the respective first ones of the second memory means to the associated processing units, respectively.

13. The method of claim 12 wherein steps (A) and (B) are performed simultaneously during a first phase and steps (C), (D), and (E) are performed during a second phase.

14. The method of claim 13 wherein the second memory means comprises cache memory means.

15. In a processing system for performing processing operations in a parallel upon data stored in a first memory means having L rows and M blocks of N columns, where L, M, and N are integers greater than one, a method of transferring data between the first memory means and an array of M blocks of N processing units, wherein each of the M×

N processing units are associated with a respective one of the M×

N columns of the first memory means, comprising the steps of;

(A) selecting, for at least certain of the M blocks, one of the N processing units for receiving data;

(B) transferring, for blocks having selected processing units, from the first memory means a row of N data bits directly to the selected one processing unit; and

(C) storing, for the blocks having selected processing units, each respective row of N data bits transferred in step (B) in the respective processing unit selected in step (A).

16. The method of claim 15 wherein each of the M×

N processing units is associated with at least N second memory means, and

wherein step (A) includes the substep of generating, for each processing unit selected in step (A), a control signal for enabling the second memory means associated with each selected processing unit to receive a respective N bit row of data, and

wherein step (C) includes the substep of storing, for each enabled group of N second memory means, the respective row of N data bits therein.

17. The method of claim 16 wherein the generating and storing substeps are performed in one clock cycle period.

18. In a processing system for performing processing operations in parallel upon data stored in a first memory means having L rows and M blocks of N columns, where L, M, and N are integers greater than one, a method of transferring data between the first memory means and an array of M blocks of N processing units, wherein each of the M×

N processing units are associated with a respective one of the M×

N columns of the first memory means, and wherein each of the M×

N processing units is associated with at least N second memory means, comprising the steps of

(A) selecting, for at least certain of the M blocks, one of the N processing units for outputting data; and

(B) transferring, for the blocks having selected processing units, from each selected processing unit, a group of N data bits stored in the N second memory means associated with each selected processing unit to the first memory means and therein storing each transferred group of N data bits.

19. In a parallel processing system having M blocks of N processing units, where M and N are integers greater than 1, each processing unit being associated with a plurality of memory means contained therein, a method of retrieving data using indirect addressing comprising the steps of:

(A) selecting, for each of the M blocks, one of the N processing units;

(B) reading, for each of the M blocks, a respective indirect address from a first group of the plurality of memory means associated with each processing unit selected in step (A);

(C) broadcasting, for each of the M blocks, the respective indirect address read in step (B) to a second group to serve as the address of the second group, of the memory means in each of the N processing units of the respective block;

(D) outputting, for each of the M blocks, the data stored at the respective indirect address of the second group of the memory means in each of the N processing units, the collective output defining a respective data word.

20. The method of claim 19 wherein the first group of the memory means is a 1×

N array of cache memory means, and the second group of the memory means is a single cache memory means.

21. The method of claim 19 wherein steps (B), (C), and (D) are performed simultaneously.

22. The method of claim 20 wherein steps (B), (C), and (D) are performed simultaneously.

23. The method of claim 19 wherein steps (B), (C) and (D) are repeated a predetermined number of times to output a plurality of data words and wherein step (B) is performed by the substeps of providing a starting address to the first group of the memory means to read the indirect address, and successively incrementing, for each of the predetermined iterations of steps (C) and (D), the starting address to read another respective indirect address stored in consecutively addressed locations of said first group of memory means wherein another data word is outputted.

24. In a processing system for performing operations in parallel, the system including an array of M×

N processing units where M and N are integers greater than 1, a memory means, and a controlling means, a method of transferring instruction data and matrix data from the memory means to the array of M×

N processing units, comprising the steps of;

(A) transferring instruction data stored in the memory means to a controlling means;

(B) decoding the instruction data transferred in step (A) with the controlling means to condition the M×

N processing units to receive and process matrix data; and

(C) transferring matrix data from the memory means while the M×

N processing units remain conditioned from step (B).

25. The method of claim 24 wherein the memory means has a plurality of rows and M blocks of N columns, each of the M×

N processing units being associated with a respective one of the M X N columns of memory means, certain of the M×

N bit rows of the memory means collectively defining instruction data, and wherein step (A) includes the substep of transferring a plurality of M×

N bit rows of instruction data from the memory means to the controlling means.

26. The method of claim 24 wherein the memory means has a plurality of rows and M blocks of N columns, each of the M×

N processing units being associated with a respective one of the M×

N coles of memory means, certain of the M×

N bit rows of the memory means collectively defining instruction data and wherein step (B) includes the substeps of routing, according to at least the uppermost two bits of an M×

N bit instruction, the remaining bits of that instruction to a storage register, generating, using the remaining bits stored in the storage register, a plurality of control signals, and transferring the plurality of control signals to the M×

N processing units to condition the processing units for receiving and processing matrix data.

27. The method of claim 24 wherein the memory means has a plurality of rows and M blocks of N columns, each of the M×

N processing units being associated with a respective one of the M×

N columns of memory means, and wherein step (C) includes the substeps of providing a starting address of a first plurality of consecutive rows to the memory means, providing a plurality of clock pulses to the memory means, and outputting the first plurality of consecutive rows of matrix data in sequential row order, said outputting substep including outputting a further consecutive row, starting from a row having the starting address, for each provided clock pulse.

28. An apparatus for transferring data comprising:

memory means having L rows and M columns, where L and M are greater than 1, for storing a data matrix;

an array of M processing units, each of said processing units being respectively associated with one of the M columns of said memory means for performing operations in parallel upon said data matrix;

shifting means coupled to said memory means and with said array of M processing units for shifting, in a first clock cycle, each bit of a first row of M bits of matrix data from the M columns of memory means one or more column positions to one of M processing units associated with respectively adjacent columns of said memory means.

29. The apparatus of claim 28, further comprising:

means coupling each of said M processing units with the respectively associated column of said memory means for transferring, in said first clock cycle, each bit of said first row of M bits of matrix data from the M columns of memory means to the respectively associated one of M processing units wherein horizontally displaced data values from said memory means are presented to each of said M processing units in said first clock cycle.

30. The apparatus of claim 29 wherein each one of said M processing units includes delay means for delaying, respectively, each shifted bit in said first row of M data bits shifted by said shifting means by one or more clock cycles, and for delaying, respectively, each bit in said first row of M data bits transferred by said means for transferring by one or more clock cycles, wherein vertically displaced matrix data from said memory means are presented to each of said M processing units in one clock cycle.

31. The apparatus of claim 30 wherein said shifting means includes a barrel shifter.

32. The apparatus of claim 31 wherein said delaying means includes a digital delay line.

33. In a parallel processing system, an apparatus for transferring data, comprising:

a first memory means having L rows and M columns, where L and M are integers greater than 1, for storing an array of data;

an array of M processing units, each of said processing units being respectively associated with one of said M columns of said first memory means for performing operations in parallel upon said array of data, each of said processing units being associated with a plurality of second memory means;

first bursting means coupled to said M columns of first memory means and to said second memory means for bursting array data in sequential row order from a first plurality of consecutive rows of said first memory means to a first one of said second memory means for each of said M processing units and for storing said burst array data in said respective first one of said second memory means; and

means coupled with said second memory means and said M processing units for transferring stored array data from the respective first one of said second memory means to each one of said M processing units, said means for transferring including second bursting means for bursting said stored array data from each first one of said second memory means to the respectively associated one of said array of M processing units.

34. The apparatus of claim 33 wherein said first bursting means includes a controller means having a means for providing a starting address of said first plurality of consecutive rows to said first memory means, and a means for providing clock pulses the said first memory means, wherein said first memory means, upon being provided a further clock pulse, outputs a further consecutive row, starting from a row having the starting address.

35. The apparatus of claim 34 further comprising a third bursting means coupled with said M columns of first memory means and coupled with said array of M processing units for bursting array data in sequential row order from a second plurality of consecutive rows of said first memory means to said array of M processing units;

and

synchronizing means coupled with said first memory means and said second memory means for synchronizing said burst array data from each first one of said second memory means and said burst array data from said second plurality of consecutive rows of said first memory means, wherein said synchronized array data is transferred to said array of M processing units.

36. The apparatus of claim 33 wherein said first bursting means is operative to burst array data in sequential row order from a second plurality of consecutive rows of said first memory means to a second one of said second memory means for each of said M processing units, said first bursting means being further operative to store said bursted array data from said second plurality of consecutive rows in said respective second ones of said second memory means, and

wherein said second bursting means bursts said array data stored in respective second ones of said second memory means with said array data stored in respective first ones of said second memory means to the respective one of said M processing units such that parallel streams of data are transferred to each processing unit.

37. The apparatus of claim 36 wherein said third bursting means is operative to burst array data in sequential row order from a third plurality of consecutive rows of said first memory means to said M processing units in synchronization with said array of data stored in respective first and second ones of said second memory means of each of the M processing units.

38. The apparatus of claim 37 wherein said second memory means includes a plurality of cache memory means.

39. The apparatus of claim 35 wherein said first bursting means further includes a switch means connected to said first memory means for routing array data, a plurality of first selector means connected between said switch means and said second memory means, said first selector means being responsive to a first control signal for selectively passing burst array data from said switch means to said second memory means, and said controller means further having a means coupled to said first selector means for generating said first control signal.

40. The apparatus of claim 39 wherein said switch means includes a cross bar switch.

41. The apparatus of claim 40 wherein said second bursting means includes a plurality of second selector means coupled to said second memory means and said array of M processing units, said plurality of second selector means being responsive to a respective one of a plurality of second control signals for selectively passing array data stored in said second memory means to said M processing units, and said controller means further having a means coupled with said second plurality of second selector means for generating said plurality of second control signals.

42. The apparatus of claim 41 wherein said third bursting means includes said cross bar switch connected with said first memory means for routing array data from said first memory means, and further includes said plurality of second selectors.

43. The apparatus of claim 42 wherein said synchronization means includes said means for providing clock pulses.

44. The apparatus of claim 33, wherein each of said M processing units includes a numeric processor.

45. In a parallel processing system, an apparatus for relating column data across a segment boundary, comprising:

first memory means having L rows and M columns, where L and M are integers greater than 1, for storing a data matrix having P columns, where P is an integer greater than M, and wherein said data matrix is stored in said first memory means in a plurality of segments;

an array of M processing units for performing operations in parallel upon said data matrix, each of said processing units being respectively associated with one of said M columns of said first memory means, each of said processing units being associated with a plurality of second memory means;

shifting means coupled with said first memory means, said second memory means and said array of M processing units for shifting the columns of a first segment at least one column position such that a column of data adjacent a first segment boundary is shifted across said first segment boundary, wherein said shifted first segment of column data is stored in a first one of said second memory means of a processing unit to which said shifted column of data is associated, said shifting means being operative to shift the columns of a second segment the same number of column positions as said first segment was shifted such that a column of second segment data adjacent said first segment boundary is shifted away from said first segment boundary;

first transferring means coupled with said shifting means and said array of M processing units for transferring said shifted second segment of column data to said M processing units; and

second transferring means coupled with said first one of said second memory means and said processing unit associated therewith for transferring said shifted matrix data stored in said first one of said second memory means to said processing unit associated therewith wherein column data on both sides of said first segment boundary are accessible to said M processing units.

46. The apparatus of claim 45 wherein said first and second transferring means transfer, respectively, said shifted second segment of column data and said shifted data stored in said first one of said second memory means, to said M processing units simultaneously.

47. The apparatus of claim 46 wherein the number of column positions shifted by said shifting means is two such that two columns of said first segment are shifted across said first segment boundary, said two coles being stored in respective first ones of said second memory means of the processing units to which said two shifted coles of data are respectively associated, said second transferring means being operable to transfer data stored in said respective first ones of said second memory means to the associated processing units, respectively.

48. The apparatus of claim 47 wherein said shifting means shifts said first segment, and said column shifted across said first segment boundary is stored simultaneously during a first phase, wherein said shifting means shifts said second segment, and said first and second transferring means respectively transfers said shifted second segment of column data and said shifted data stored in said first one of said second memory during a second phase.

49. In a parallel processing system, an apparatus for transferring data, comprising:

a first memory means having L rows and M×

N columns, where L, M, and N are integers greater than 1, for storing a data array;

an array of M blocks of N processing units for performing operations in parallel upon said array of data, each of said M×

N processing units being associated with a respective one of said M×

N columns of said memory means;

selecting means coupled with said M×

N processing units for selecting, for at least certain of said M blocks, one of said N processing units for receiving data;

transposing means coupled with said first memory and each one of said M×

N processing units for transferring, for blocks having selected processing units, from said first memory means a row of N data bits to a respective block of N processing units wherein each transferred row is stored in said respective one processing unit selected by said selecting means.

50. The apparatus of claim 49 wherein each of said M×

N processing units is associated with at least N second memory means, and said apparatus further including a controller means, coupled with each of the M×

N processing units for generating, for selected processing units a control signal for enabling said second memory means associated with each selected processing unit to receive a respective N bit row of data wherein each row of N data bits is stored in the respective group of N second memory means enabled by said controller means.

51. The apparatus of claim 50 wherein said controller means generates said control signal and said rows of N data bits are stored in said enabled groups of N second memory means in one clock cycle period.

52. The apparatus of claim 51 wherein said selecting means includes a plurality of selectors, and wherein said transposing means includes, for each of said M blocks, a transpose-in bus.

53. In a parallel processing system, an apparatus for transferring, comprising:

a first memory means having L rows and M×

N columns, where L, M, and N are integers greater than 1, for storing a data array;

an array of M blocks of N processing units for performing operations in parallel upon said data array, each of said M×

N processing units being associated with a respective one of said M×

N columns of said first memory means, each of said M×

N processing units being associated with at least N second memory means;

selecting means coupled with, for each of the M×

N processing units, said N second memory means for selecting, for at least certain of said M blocks, one of said N processing units for outputting data; and

transposing means coupled with said selecting means and said first memory means for transposing and transferring a group of N data bits stored in said N second memory means associated with each selected processing unit to said first memory means and for storing each transferred group of N data bits.

54. In a parallel processing system, an apparatus for retrieving data using indirect addressing, comprising:

an array of M blocks of N processing units for performing operations in parallel, each of said M×

N processing units being associated with a plurality of memory means contained therein;

selecting means coupled with said plurality of memory means for selecting, for each of said M blocks, one of N processing units and for reading a respective indirect address from a first group of said plurality of memory means associated with each selected processing unit; and

broadcasting means responsive to said respective indirect address for broadcasting, for each of the M blocks, said respective indirect address to a respective second group of said plurality of memory means in each of N processing units of the respective block, wherein each block outputs data stored at said respective indirect address of said second group of said plurality of memory means in each of the N processing units, the collective output of N second groups for each block defining a respective data word, whereby said respective data word is retrieved as the collective output from said second group in each processing unit using an indirect address stored in said first group.

55. The apparatus of claim 54 wherein said first group of memory means is a 1×

N array of cache memory means, and said second group of memory means is a single cache memory means.

56. The apparatus of claim 54 wherein said selecting means selects processing units and reads indirect addresses, and said broadcasting means broadcasts said indirect addresses to output said data word in one clock cycle period.

57. The apparatus of claim 55 wherein said selecting means selects processing units and reads indirect addresses, and said broadcasting means broadcasts said indirect addresses to output said data word in one clock cycle period.

58. The apparatus of claim 54 wherein said selecting means, for each of said M blocks, reads another respective indirect address from said first group of memory means a predetermined number of times to output a plurality of data words, and

wherein said apparatus further includes a means for providing a starting address to said first group to read said respective indirect address, and for successively incrementing said starting address, for each indirect address;

and

wherein said selecting means reads another respective indirect address in response to said incremented starting address such that another data word is outputted by each block.

59. In a parallel processing system, an apparatus for transferring instructions and matrix data from a memory means, comprising:

a memory means;

an array of M blocks of N processing units coupled with said memory means for performing operations in parallel on matrix data according to instructions, wherein said matrix data and said instructions are stored in said memory means; and

a controller means coupled with said memory means and said array of processing units for fetching instructions from said memory means and for decoding said fetched instructions to condition said array of M×

N processing units to receive and process matrix data, wherein at least one instruction is fetched and decoded by said controller means, said controller means including data burst means coupled with said memory means for transferring matrix data from said memory means while said M×

N processing units remain conditioned in accordance with said instruction fetched and decoded by said controller means.

60. The apparatus of claim 59 wherein said memory means has a plurality of rows and M blocks of N columns, each one of said array of M×

N processing units being associated with a respective one of said M×

N columns of memory means, wherein certain of said M×

N bit rows of said memory means collectively define respective instructions, wherein said controller means fetches a plurality of M×

N bit consecutive rows of instructions from said memory means.

61. The apparatus of claim 59 wherein said memory means has a plurality of rows and M blocks of N columns, each one of said array of M×

N processing units being associated with a respective one of said M×

N columns of memory means, wherein certain of said M×

N bit rows of said memory means collectively defining respective instructions, said controller means including a storage register and routing means responsive to said fetched instruction for routing, according to at least the uppermost two bits of said fetched instruction, the remaining bits of said fetched instruction being routed to said storage register, said controller means further including control signal generating means for generating, using the remaining bits stored in said storage register, a plurality of control signals to condition said M×

N processing units for receiving and processing matrix data.

62. The apparatus of claim 59 wherein said memory means has a plurality of rows and M blocks of N columns, each one of said array of M×

N processing units being associated with a respective one of said M×

N columns of memory means, wherein said data burst means includes means for providing a starting address of a first plurality of consecutive rows of said memory means, means for providing a plurality of clock pulses to said memory means, wherein said first plurality of consecutive rows of matrix data are outputted in sequential row order starting from one of said rows having said starting address when said starting address is provided and, wherein a further consecutive row is outputted for each further provided clock pulse.