Mesh parallel computer architecture apparatus and associated methods

• US 5,590,356 A
• Filed: 08/23/1994
• Issued: 12/31/1996
• Est. Priority Date: 08/23/1994
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Gilbert, Ira H.
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US08/294,757
• Time in Patent Office: 861 Days
• Field of Search: 395/800, 395/200.01, 395/200.02, 395/309, 395/445, 395/495, 395/842, 364/131-133, 364/736, 364/780
• US Class Current: 712/31
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors

Abstract

A Monolithic Synchronous Processor (MeshSP) processes data and incorporates a mesh parallel computer architecture, primarily SIMD, thereby combining high data throughput with modest size, weight, power and cost. Each MeshSP processor node utilizes a single DSP processor element, a large internal memory of at least 128k-bytes, and separately operable computational and I/O processing sections. The processor element provides data throughput of at least 120 MFlops. The processor is programmed in ANSI C and without parallel extensions. A combination of on-chip DMA hardware and system software simplifies data I/O and interprocessor communication. The MeshSP is programmed to solve a wide variety of computationally demanding signal processing problems. A functional simulator enables MeshSP algorithms to be coded and tested on a personal computer.

Claims

1. Digital data processing apparatus for synchronously processing data from a host computer, comprising:

program memory means for storing data, and bus means connecting said program memory means to the host computer;

a master processor element and an array of slave processor elements, said master processor element having means to access said data within said program memory and for broadcasting instructions to said array; and

input/output module means connected to communicate with said bus means and having a plurality of data links connected to said array, each of said data links providing serial communication with selected slave processor elements;

wherein each of said slave processor elements comprises

(i) an input/output processor section having interprocessor communication links for communicating data through link ports to and from selected other processor elements within said array, and further having means for communicating data to and from said input/output module means, the input/output processor section being programmable to through-route data by defining transfer leg specifications including link port selection and leg durations,

(ii) internal memory means having a storage capacity of at least 128 kilobytes for storing executable code and data, and

(iii) a core processor section for processing said executable code and said instructions, each of said processor sections being operable independently from the other of said processor sections;

said slave processor elements synchronously executing at least one of said instructions and said executable code.

2. Digital data processing apparatus according to claim 1, wherein each of said slave processor elements further comprises means for supporting either SIMD or MIMD processing.

3. Digital data processing apparatus according to claim 1, further comprising a host computer having an interface for communicating with external users and means for controlling said apparatus.

4. Digital data processing apparatus according to claim 1 wherein said master processor element and said slave processor elements have identical architectures.

5. Digital data processing apparatus according to claim 1 wherein said processor elements are compatible with single instruction-stream multiple data-stream operation, and further comprising means for communicating data amongst said processor elements as a single instruction-stream multiple data-stream.

6. Digital data processing apparatus according to claim 1 wherein each of said slave processor elements further comprises means for communicating on a nearest-neighbor mesh with selected others of said slave processor elements.

7. Digital data processing apparatus according to claim 1, further comprising buffer means for electronically buffering said instructions between said program memory and said array.

8. Digital data processing apparatus according to claim 1, further comprising means for simultaneously providing data stored in said program memory to said master processor element and said array.

9. Digital data processing apparatus according to claim 1 wherein said input/output processor section comprises six interprocessor communication links, four of said interprocessor communication links providing nearest-neighbor mesh communication with four adjacent slave processor elements, two other interprocessor communication links providing fault tolerance with two of said four adjacent slave processor elements in the event of a failure.

10. Digital data processing apparatus according to claim 9 wherein said array is arranged with a sequence of slave processor elements located in the X direction and a sequence of slave processor elements located in the Y direction, and further comprising means for toroidally connecting said slave processor elements such that each slave processor element is no further than four X locations and four Y locations from any other of said slave processor elements.

11. Digital data processing apparatus according to claim 1 wherein said array comprises a plurality of columns of said slave processor elements, and wherein each of said data links connects to a separate column.

12. Digital data processing apparatus according to claim 11 wherein said input/output processor section provides at least five megabytes per second throughput, and wherein said bus means and each of said data links provide at least forty megabytes per second throughput.

13. Digital data processing apparatus according to claim 1, further comprising means for communicating a slave ready signal between said master processor and said array, and wherein said array comprises means for generating said slave ready signal after processing either of said instructions and said executable code.

14. Digital data processing apparatus according to claim 1, further comprising means for communicating an interrupt between said master processor and the host computer, and wherein said master processor comprises means for generating an interrupt to request selected services from the host computer.

15. Digital data processing apparatus according to claim 1, further comprising means for communicating control signals between the host computer and said master processor, said master processor further comprising means for responding to said control signals.

16. Digital data processing apparatus according to claim 1 wherein said apparatus is arranged as a PC-compatible printed circuit board, further comprising means for interfacing with additional printed circuit boards containing said slave processor elements.

17. Digital data processing apparatus according to claim 1 wherein each of said interprocessor communication links is a multiple bit-wide data path.

18. Digital data processing apparatus according to claim 1, further comprising means for specifying an arrangement of data as at least one transfer control block data structure, said data structure having a transmit data block and a receive data block, said transmit data block describing a data transfer to a slave processor element, said receive data block describing a data transfer from a slave processor element.

19. Digital data processing apparatus according to claim 18 wherein said input/output processor section further comprises a direct memory access controller having a transmit channel for transmitting data, and a receive channel for receiving data, each of said processor elements further comprising means for loading said transmit channel with said transmit data block, and for loading said receive channel with said receive data block.

20. Digital data processor apparatus according to claim 19 wherein said data structure has a word indicating whether additional transfer control blocks are connected to said transfer control block, and wherein said input/output processor section further comprises auto-chaining means for successively loading and unloading said data blocks in said channels when said word indicates additional connected transfer control blocks.

21. Digital data processing apparatus according to claim 19, wherein said core processor section further comprises means for storing a starting address of said transmit data block in said transmit channel, and for storing a starting address of said receive data block in said receive channel.

22. Digital signal processing apparatus according to claim 21 wherein said transfer control block data structure further includes a word indicating whether additional transfer control data blocks are included in a connecting group of data, said direct memory access controller further having means for interpreting said word and for automatically loading and unloading said additional data blocks without interfering with said core processor section.

23. Digital data processing apparatus according to claim 1 wherein a transfer through plural slave processor elements is controlled by the transfer leg specifications in the plural slave processor elements.

24. A digital data processing apparatus as claimed in claim 1 wherein:

the interprocessor communication means comprises a set of selectable link ports; and

the input/output processor section further comprises;

an input/output register set for holding data transferred between the internal memory means and the selectable link ports and data transferred between selectable link ports; and

an I/O controller which, for successive data elements, performs a direct memory access to read the data elements from the internal memory means to the input/output register set and, after a programmable number of cycles of data transfers between selectable ports through the input/output register set, performs a direct memory access to write the data elements from the input/output register set to the internal memory means.

25. A digital data processing apparatus as claimed in claim 24 wherein the I/O controller selects transmit and receive link ports and is programmed by means of a transfer control data structure which identifies memory addresses for the direct memory accesses, selects transmit and receive link ports and identifies the programmable number of cycles of data transfers.

26. A digital data processing apparatus as claimed in claim 25 wherein the transfer control data structure further comprises transmit and receive subarray parameters defining a two dimensional subarray and by which the I/O controller determines addresses from which data elements are read and addresses into which data elements are written.

27. A digital data processing apparatus as claimed in claim 25 wherein the data structure further comprises a chain pointer for pointing to subsequent transfer control data structures for automatic reprogramming of the I/O controller and continued data transfer.

28. A digital data processing apparatus as claimed in claim 24 wherein the I/O controller is programmable to write data into memory from the input/output register set in each of said programmable number of cycles in a broadcast communication mode.

29. A monolithic processor element for use in a synchronous digital data processing system, comprising:

(i) an input/output processor section having interprocessor communication means for transferring data through link ports to and from selected other monolithic processor elements in the system, and further having serial port means for transferring data to and from the system, the input/output processor section being programmable to through-route data by defining transfer leg specifications including link port selection and leg durations;

(ii) external port means for receiving instructions for the system, and for communicating interrupts to the system;

(iii) a core processor section for processing instructions and data, each of said processor sections being operable independently from the other of said processor sections; and

(iv) internal memory means having a storage capacity of at least 128 kilobytes for storing data and executable code, and further having bus means for communicating with said processor sections and said external port means;

said processor element being programmably operable to synchronously process data in conjunction with other processor elements in the system.

30. A monolithic processor element according to claim 29 wherein said processor element has a throughput rate of at least 120MFLOPS.

31. A monolithic processor element according to claim 29, further comprising means for processing data as either SIMD or MIMD compatible data.

32. A monolithic processor element according to claim 29 wherein said interprocessor communication means comprises a plurality of multiple bit-wide data paths.

33. A monolithic processor element according to claim 29 wherein said interprocessor communication means comprises six nibble ports for communicating on a nearest-neighbor mesh with other processing elements in the system, each of said nibble ports providing a 4-bit wide data path.

34. A monolithic processor element according to claim 29 wherein said input/output processor section further comprises means for transferring two-dimensional arrays of data.

35. A monolithic processor element according to claim 34 wherein said means for transferring two-dimensional arrays comprises a direct memory access controller having multiple data channels.

36. A monolithic processor element as claimed in claim 29 wherein:

the interprocessor communication means comprises a set of selectable link ports; and

the input/output processor section further comprises;

an input/output register set for holding data transferred between the internal memory means and the selectable link ports and data transferred between selectable link ports; and

an I/O controller which, for successive data elements, performs a direct memory access to read the data elements from the internal memory means to the input/output register set and, after a programmable number of cycles of data transfers between selectable ports through the input/output register set, performs a direct memory access to write the data elements from the input/output register set to the internal memory means.

37. A monolithic processor as claimed in claim 36 wherein the I/O controller selects transit and receive link ports and is programmed by means of a transfer control data structure which identifies memory addresses for the direct memory accesses, selects transmit and receive link ports and identifies the programmable number of cycles of data transfers.

38. A monolithic processor as claimed in claim 37 wherein the transfer control data structure further comprises transmit and receive subarray parameters defining a two dimensional subarray and by which the I/O controller determines addresses from which data elements are read and addresses into which data elements are written.

39. A monolithic processor as claimed in claim 37 wherein the data structure further comprises a chain pointer for pointing to subsequent transfer control data structures for automatic reprogramming of the I/O controller and continued data transfer.

40. A monolithic processor as claimed in claim 36 wherein the I/O controller is programmable to write data into memory from the input/output register set in each of said programmable number of cycles in a broadcast communication mode.