Reconfigurable signal processor

• US 5,020,059 A
• Filed: 03/31/1989
• Issued: 05/28/1991
• Est. Priority Date: 03/31/1989
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Oliver, Neal C., Gorin, Allen L., Morton, Nancy, Makofsky, Patrick A., Shively, Richard R., Stanziola, Christopher A.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/331,411
• Time in Patent Office: 788 Days
• Field of Search: 371/11.1, 371/11.3, 371/9.1, 364/200 MS File, 364/900 MS File
• US Class Current: 714/3
• CPC Class Codes: G06F 11/2005 using redundant communication controllers
• CPC Class Codes: G06F 11/2007 using redundant communication media
• 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/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G11C 29/006 at wafer scale level, i.e. wafer scale integration [WSI]

Abstract

An interconnection scheme among the processing elements ("PEs") of a multiprocessor computing architecture realizes, through PE reconfiguration, both fault tolerance and a wide variety of different processing topologies including binary trees and linear systolic arrays. By using a novel variant on a tree expansion scheme, the invention also allows for arbitrary up-sizing of the PE count to build virtually any size of tree network, with each size exhibiting same high degree of fault tolerance and reconfigurability. The invention may be practiced with 4-port PEs arrayed in a module comprising a 4×4 board-mounted PE lattice. Each PE has four physical ports, which connect to the similar ports of its lattice neighbors. Each PE has an internal capability to be configured to route signals to or from any of its neighbors. Thus, for tree topologies, any of the four neighbors of a given PE may be selected as the parent of the given PE; and any or all of the remaining three neighboring PEs may be selected as the child(ren) PEs. The PE ports are configured under the control of a remote host, which establishes an initial desired PE topology. The operability of the PEs is tested, and information on faulty PEs or communications paths is used to enable or disable nodes as necessary by revising the PE port configurations. The nodes thus are reorganized and can run or continue running, on a degraded basis.

Claims

1. A process for embedding a desired tree node topology in an assembly of processing elements fixedly interconnected through controllably enabled element ports, comprising the steps of:

defining a desired tree node interconnection topology,

determining a processor element port-to-port connection arrangement for the given said assembly which maximizes use of processors known to be operable,

modifying said port-to-port connection arrangement to minimize tree depth, and

embedding said modified processor element connection arrangement into said assembly of elements by enabling selected ones of said processor element ports.

2. A process pursuant to claim 1, comprising the further steps of:

monitoring the run performance of said operating processor elements to detect elements which become inoperable, and

re-modifying said port-to-port connection arrangements to minimize tree depth and to make maximum use of remaining operable said processor elements.

5. A process pursuant to claims 2 or 4, comprising the further steps of:

operating said enabled ports to serve as parent/child or child/parent paths.

3. A process for synthesizing a desired node interconnection topology in an assembly of processing elements under control of a Host, in which

each element comprises plural signal communication ports,

said elements are physically arrayed in x-y matrices on one or more mounting means,

each element of each said matrix other than elements located at the matrix corners is interconnected to four neighbor PEs,

each corner element is connected to its respective two neighbor elements and has two external connection paths, and

said assembly comprises means for effecting signal routing within each element between its said processing capability and any of said plural ports, said process comprising:

defining in said Host a desired processor element intra-board port interconnection topology for each board,

testing under Host control said elements for faults,

determining in said Host alternate processor element port interconnections which route signals around elements identified as faulted; and

reconfiguring selected ones of said ports based on said alternate processor element port interconnections.

4. The process of claim 3, wherein said desired topology is a tree, and said process comprises the further step of:

determining in said Host the minimum depth of tree leafs in said matrix, using the available unfaulted processor elements and communications paths.

6. Apparatus for expanding a tree multiprocessor topology while maintaining a constant number of root connection paths to said topology, and a constant number of expansion nodes, comprising:

first and second arrays of substantially identical processor elements, each element having plural ports,

means for selectively connecting ports of adjacent ones of all but two of said elements in each said array, to form in each array a two-root subtree of processor elements,

said two elements not used in said subtrees each comprising three-port expansion nodes,

said two roots and said three-port expansion nodes thereby furnishing eight connection paths to each said array,

means for connecting the subtree and a first expansion node in said first array to the corresponding parts of said second array, thereby forming a further two-root subtree,

the second said expansion node of each said array being available to replace elements in its respective array, and

said two roots of said further subtree and said last-named nodes thereby comprising a total of eight connection paths to the combined assemblages of said first and said second processor element arrays.

7. Apparatus in accordance with claim 6, wherein each said processor element comprises four ports.

8. Apparatus in accordance with claim 7, wherein said first and second arrays of processor elements comprise elements disposed in an X-Y matrix, with respective processor elements connected to their immediate neighbors.

9. In a system for performing concurrent computational processes in a controlled assembly of processing elements interconnected as processing nodes, means for embedding a desired topology of nodes into a fixed lattice, comprising:

a remote command Host,

a plurality of processor elements arrayed in one or more matrices of nodes, each said element having

plural exterior ports accessing the processing capability of said element, and

means for effecting signal routing within each said processor element between its said processing capability and any of said plural ports, and for blocking signal routing at selected ports,

means for connecting selected ports of the elements in each said matrix to selected ports of neighbor elements, and for connecting selected ports of designated elements either to selected element ports in a further matrix of processor elements or to said Host, and

means in said Host for conditioning said element ports to direct signals to and from only selected ones each element'"'"'s neighboring processor elements,

said conditioning means achieving a desired interconnection topology for the nodes of said system.

10. In a system for performing concurrent computational processes in an assembly of processing elements fixedly interconnected as processing nodes, means for synthesizing a desired node interconnection topology comprising:

a remote command Host,

a plurality of processor elements arrayed in one or more rectangular matrices of nodes,

each said element having four exterior ports accessing the processing capability of said element,

means for defining a desired node interconnection topology,

means for detecting inoperative processor elements,

means for determining a processor element port-to-port connection arrangement for the given said assembly which maximizes use of processor elements found to be operating, and

means in each said element under control of said Host for enabling signal routing within said operating processor elements between their said processing capability and any of their said four ports, and for blocking signal routing at selected ports.

11. A system in accordance with claim 10, wherein said desired topology is a tree, and said system further comprises:

means for modifying said port-to-port connection arrangement to minimize tree depth.

12. A system in accordance with claim 11, wherein said enabling means further comprises:

means responsive to indicia of the location in said matrices of detected inoperative processor elements for reconfiguring said port-to-port connection arrangement to utilize only operating ones of said elements.

13. A system pursuant to claim 12, further comprising:

means for connecting selected ports of said elements to selected processor element ports in a further matrix of processor elements or to said Host.

14. Apparatus in accordance with claim 12, further comprising;

means for orienting selected ones of said ports of each said element, to serve as parent/child or child/parent paths.