Topologically-distributed-memory multiprocessor computer

• US 4,855,903 A
• Filed: 01/22/1988
• Issued: 08/08/1989
• Est. Priority Date: 12/20/1984
• Status: Expired due to Fees

• Current Assignee: State University of New York
• Original Assignee: State University of New York
• Inventors: Carleton, Herbert R., Broughton, Jeremy Q.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/147,595
• Time in Patent Office: 564 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 709/248
• CPC Class Codes: G06F 13/1657 Access to multiple memories
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15

Abstract

A modular, expandable, topologically-distributed-memory multiprocessor computer comprises a plurality of non-directly communicating slave processors under the control of a synchronizer and a master processor. Memory space is partitioned into a plurality of memory cells. Dynamic variables may be mapped into the memory cells so that they depend upon processing in nearby partitions. Each slave processor is connected in a topologically well-defined way through a dynamic bi-directional switching system (gateway) to different respective ones of the memory cells. Access by the slave processors to their respective topologically similar memory cells occurs concurrently or in parallel in such a way that no data-flow conflicts occur. The topology of data distribution may be chosen to take advantage of symmetries which occur in broad classes of problems. The system may be tied to a host computer used for data storage and analysis of data not efficiently processed by the multiprocessor computer.

Claims

1. A multiprocessor computer, comprising:

a grid-like network of processors and memory cells, said processors and memory cells defining the nodes of said grid and being logically configured in an alternating sequence within said grid, such that individual processors are logically interposed between surrounding memory cells and individual memory cells are logically interposed between surrounding processors;

communication means for providing direct, parallel communications between the individual processors and their logically surrounding memory cells and between the individual memory cells and their logically surrounding processors, such that nearest adjacent processors articulate at least two common memory cells and nearest adjacent memory cells are articulated by at lest two common processors;

switching means provided logically between the individual processors and each of their surrounding memory cells and between the individual memory cells and each of their surrounding processors, and cooperating with said communications means, for enabling/disabling communication between each individual processor and a particular one of it surrounding memory cells and between each individual memory cell and a particular one of its surrounding processors; and

synchronizing means, cooperating with said switching means, for synchronizing the switching of communications between the individual processors and particular ones of their surrounding memory cells, and between the individual memory cells and particular ones of their surrounding processors.

2. A multiprocessor computer, as recited in claim 1, wherein said synchronizing means is adapted to enable each of said processors to be connected, in parallel, to alternate topologically similar ones of their surrounding memory cells.

3. A multiprocessor computer, as recited in claim 2, wherein said processors are slave processors and further comprising a master processor coupled to said slave processors for supervising the operation of said slave processors.

4. A multiprocessor computer, as recited in claim 1, wherein said network is modular such that additional processors and memory cells may be directly added to the system by interposing communications and synchronizing means between one processor located at a logical boundary of the grid-like network and one of said additional memory cells, and between one memory cell located at a logical boundary of the grid-like network and one of said additional processors.

5. A multiprocessor computer, as recited in claim 3, wherein said master processor is further coupled to said synchronizing means for supervising the operation of said synchronizing means.

6. A multiprocessor computer, as recited in claim 3, wherein said slave processors communicate only indirectly, through the master processor and through said memory cell.

7. A multiprocessor computer, as recited in claim 3, wherein said switching means includes bi-directional controlled pathway elements across which said slave processors access said memory cells.

8. A multiprocessor computer, as recited in claim 3, wherein the relationship between each slave processor and its associated memory cells comprises a four-fold coordination.

9. A multiprocessor computer, as recited in claim 3, further comprising communications and synchronizing means between each processor and a further memory cell logically neighboring its respectively surrounding memory cells, and wherein the relationship between each slave processor and its associated memory cells comprises a five-fold coordination.

10. A multiprocessor computer, as recited in claim 3, wherein said master processor is adapted to partition data variables into said memory cells.

11. A multiprocessor computer, as recited in claim 3, wherein said slave processors have their own instruction memory and are independently programmable.

12. A multiprocessor computer, as recited in claim 3, wherein said memory cells define memory space, wherein said memory space is connected in a periodic fashion using boundary conditions and wherein said master processor is adapted for mapping data variables into memory space in relation to values of said variables.

13. A multiprocessor computer, comprising:

a plurality of processors;

first means, connected to each of said processors for providing parallel communications to and from each of said processors;

a data memory space comprising a plurality of memory cells;

second means, connected to each of said memory cells, for providing parallel communications to and from each of said memory cells;

means, connected between said first means and said second means, for switchably connecting each processor to a plurality of logically adjacent ones of said memory cells, each processor being associated with a different plurality of memory cells, each such plurality comprising a different subset of the set of the memory cells comprising said memory space, logically neighboring processors being thereby associated with logically neighboring memory cells in an overlapping manner, each of said memory cells being thereby switchably associated with a plurality of said processors which is a different plurality than is associated with a logically neighboring memory cell;

synchronizing means in communication with said switchably connecting means for synchronizing the switching of connections between processors and memory cells, such that, simultaneously, each of said processors is connected, in parallel, to a topologically similar one of it respectively associated memory cells; and

means cooperating with said synchronizing means for alternating said parallel connections between said processors and different, topologically similar ones of their respectively associated memory cells.

14. A multiprocessor computer, as recited in claim 13, wherein said multiprocessor computer is adapted to enable each processor to be connected, in parallel, to alternate topologically similar ones of their respectively associated memory cells.

15. A multiprocessor computer, as recited in claim 13, wherein said processors are slave processors and further comprising a master processor coupled to said slave processors for supervising the operation of said slave processors.

16. A multiprocessor computer, as recited in claim 13, wherein said computer is modular such that additional processors and memory cells may be directly added by interposing communications and synchronizing means between at least one of said additional memory cells and one processor located at a logical boundary of a grid-like network comprising said plurality of processors and said plurality of memory cells, and between at least one of said additional processors and one memory cell located at a logical boundary of the grid-like network.

17. A multiprocessor computer, as recited in claim 13, wherein said master processor is further coupled to said synchronizing means for supervising the operation of said synchronizing means.

18. A multiprocessor computer, as recited in claim 13, wherein said slave processors communicate only indirectly, through the master processor and through said memory cells.

19. A multiprocessor computer, as recited in claim 13, wherein said switching means includes bi-directional controlled pathway elements across which said slave processors access said memory cells.

20. A multiprocessor computer, as recited in claim 13, wherein the relationship between each salve processor and its associated memory cells comprises a four-fold coordination.

21. A multiprocessor computer, as recited in claim 13, further comprising communications and synchronizing means between each processor and a further memory cell logically proximate to its respectively neighboring memory cells, and wherein the relationship between each slave processor and its associated memory cells comprises a five-fold coordination.

22. A multiprocessor computer, as recited in claim 13, wherein said master processor is adapted to partition data variables into said memory cells.

23. A multiprocessor computer, as recited in claim 13, wherein said slave processors have their own instruction memory and are independently programmable.

24. A multiprocessor computer, as recited in claim 13, wherein said memory cells define memory space, wherein said memory space is connected in a periodic fashion using boundary conditions, and wherein said master processor is adapted for mapping data variables into memory space in relation to values of said variables.

25. In a computer system comprising a plurality of processors, a data memory space further comprising a plurality of memory cells, communications means linking each processor to a different subset of the set of memory cells comprising said data memory space, the members of each of said subsets being logically neighboring memory cells, and switching means cooperating with said communications means for enabling/disabling communications between each processor and a particular one of its associated memory cells, a method of electronic computation comprising the steps of:

(a) causing said switching means to provide non-conflicting access between each processor and a topologically-similar one of their respectively associated memory cells;

(b) processing, in parallel, data within each of said topologically-similar memory cells using the respectively accessing processor;

(c) causing said switching means to synchronously switch access for each of said processors to a non-conflicting, topologically-similar memory cell other than the cell most recently accessed thereby;

(d) processing, in parallel, data from said topologically-similar memory cells using the currently respectively accessing ones of said plurality of processors; and

(e) repeating steps (c) and (d) until a pre-determined condition is satisfied.

26. The method of electronic computation recited in claim 25, further comprising the step of processing data in adjacent memory cells in an overlapping manner using a plurality of ones of said processors.

27. The method of electronic computation recited in claim 25, further comprising an initial memory loading step, wherein during said memory loading step, variables having values are mapped into memory cells in relation to the values of the variables.

28. The method of electronic computation recited in claim 25, further comprising the step of supervising said processing using a master processor in communication with said processors.

29. The method of electronic computation recited in claim 25, further comprising an initial memory loading step wherein during said memory loading step, data is distributed to said memory cells according to values of variables in such a manner as to thereby partition an inputted computational problem comprising said variables having values.

30. The method of electronic computation recited in claim 29, further comprising the initial step of assigning values to said variables representative of three-dimensional physical location.

31. The method of electronic computation recited in claim 29, further comprising the step of implicitly representing said variables by their location in memory.

32. The method of electronic computation recited in claim 25, further comprising the step of concurrently executing different algorithms in two of said processors.

33. The method of electronic computation recited in claim 29, further comprising the step of connecting memory space in a periodic fashion using boundary conditions.

34. The method of electronic computation recited in claim 25, further comprising the steps of processing data between said processors and their associated memory cells in five-fold coordination.

35. The method of electronic computation recited in claim 25, further comprising the steps of processing data between said processors and their associated memory cells in four-fold coordination.

36. A multiprocessor computer, comprising:

a plurality of slave processors;

first means, coupled to each of said slave processors, for providing communications to and from said slave processors;

a data memory space partitioned into a plurality of memory cells;

second means, coupled to each of said memory cells, for providing communications to and from said memory cells;

gateway means, coupled between said first and second means, for switchably associating individual ones of said slave processors each with a different plurality of ones of said memory cells such that individual ones of said memory cells are likewise switchably associated each with a different plurality of individual ones of said slave processors;

synchronizing means, coupled to said gateway means, for synchronizing direct parallel connections between said slave processors and their respectively associated memory cells; and

a master processor, in communication with said slave processors and said synchronizing means, for supervising the operation of said slave processors and said synchronizing means, said master processor being adapted to cause said synchronizing means to synchronize connections in said gateway means in phases in such a manner as to switchably connect the individual ones of said slave processors respectively each to a particular one of a first set of topologically similar ones of their respectively associated memory cells during a first phase and to a different particular one of a second set of topologically similar ones of their respectively associated memory cells during a second phase.

37. A multiprocessor computer, as recited in claim 36, wherein the relationship between said slave processors and their associated memory cells comprises a five-fold coordination.

38. A multiprocessor computer, as recited in claim 36, wherein the relationship between of said slave processors and their associated memory cells comprises a four-fold coordination.

39. A multiprocessor computer, as r®

cited in claim 36, wherein said slave processors and said memory cells are configured in a pipeline architecture.

40. A multiprocessor computer, as recited in claim 36, wherein said memory space is connected in a periodic fashion using boundary conditions and wherein said master processor is adapted to map variables having values into memory space in relation to values of said variables.

41. A multiprocessor computer, comprising:

a plurality of slave processors;

first means, coupled to each of said slave processors, for providing communications to and from said slave processors;

a data memory space partitioned into a plurality of memory cells;

second means, coupled to each of said memory cells, for providing communications to and from said memory cells;

gateway means, coupled between said first and second means, for switchably associating individual ones of said slave processors each with a different plurality of ones of said memory cells such that individual ones of said memory cells are likewise switchably associated each with a different plurality of individual ones of said slave processors;

synchronizing means, coupled to said gateway means, for synchronizing direct concurrent connections between said slave processors and their respectively associated memory cells; and

a master processor, in communication with said slave processors and said synchronizing means, for supervising the operation of said slave processors and said synchronizing means, said master processor being adapted to cause said synchronizing means to synchronize connections in said gateway means in phases in such a manner as to switchably connect the individual ones of said slave processors respectively each to a particular one of a first set of topologically similar ones of their respectively associated memory cells during a first phase and to different particular one of a second set of topologically similar ones of their respectively associated memory cells during a second phase

42. A multiprocessor computer, as recited in claim 41, wherein the relationship between said slave processors and their associated memory cells comprises a five-fold coordination.

43. A multiprocessor computer, as recited in claim 41, wherein the relationship between of said slave processors and their associated memory cells comprises a four-fold coordination.

44. A multiprocessor computer, as recited in claim 41, wherein said slave processors and said memory cells are configured in a pipeline architecture.

45. A multiprocessor computer, as recited in claim 41, wherein said memory space is connected in a periodic fashion using boundary conditions and wherein said master processor is adapted to map variables having values into memory space in relation to values of said variables.