US5134690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Augumented multiprocessor networks
Assignee: Individual
•
Filing: 1989-06-26
•
Granted: 1992-07-28
•
Expires: 2009-06-26
Abstract
Abstract An augmented De Bruijn multiprocessor network. Multiple microprocessors having a constant number of I/O ports are connected according to a network technique which yields a machine of predetermined degree. A modified binary De Bruijn graph of degree four, DG(2,k), is used as the basis for the preferred implementation. An augmentation technique supplements the basic De Bruijn topology with a 2D-mesh in a first set of steps and with a 3D-mesh in a second set of steps. The resulting machine topology contains substantially all of the problem-solving techniques important in multiprocessing, while maintaining a machine of constant degree.
Inventors
- 👤 Maheswara R. Samatham
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:06
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17343
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
122 words
A multiprocessor network having a plurality N of processors connected together by a plurality of communications links, each processor adapted for parallel computation of an executable program with the other processors, said network comprising: N processors, each having P communications ports, said communications ports connecting said N processors in the network by said plurality of communications links, wherein each port is adapted for sending and receiving data and instructions; each of said N processors having a distinct address and having some of said communications links configured as a binary De Bruijn graph DG(2, k) of diameter k and of degree 4, where N=2 k ; and each of said N processors having some of the remaining communications links configured as a 2D-Mesh.
Claim 2
Dependent Claim
122 words
A multiprocessor network having a plurality N of processors connected together by a plurality of communications links, each processor adapted for parallel computation of an executable program with the other processors, said network comprising: N processors, each having P communications ports, said communications ports connecting said N processors in the network by said plurality of communications links, wherein each port is adapted for sending and receiving data and instructions; each of said N processors having a distinct address and having some of said communications links configured as a binary De Bruijn graph DG(2, k) of diameter k and of degree 4, where N=2 k ; and each of said N processors having some of the remaining communications links configured as a 2D-Mesh.
Claim 3
Dependent Claim
26 words
The multiprocessor network as set forth in claim 1, wherein: each of said N processors has some of the remaining communications links configured as a 3D-Mesh.
Claim 4
Dependent Claim
28 words
The multiprocessor network as set forth in claim 2, wherein: the total number of communications links is Y, wherein Y is larger than N, but less than 12N.
Claim 5
Dependent Claim
22 words
The multiprocessor network as set forth in claim 3, wherein: 4N of said Y communications links are configured as a DG (2,k).
Claim 6
Dependent Claim
21 words
The multiprocessor network as set forth in claim 4, wherein: Y-4N of said Y communications links are configured as a 2D-Mesh.
Claim 7
Dependent Claim
21 words
The multiprocessor network as set forth in claim 4, wherein: Y-6N of said Y communications links are configured as a 3D-Mesh.
Claim 8
Dependent Claim
23 words
The multiprocessor network as set forth in claim 2, wherein: the number P of communications ports is constant for all values of N.
Claim 9
Dependent Claim
21 words
The multiprocessor network as set forth in claim 7, wherein: the number P of communications ports is not less than 8.
Claim 10
Dependent Claim
20 words
The multiprocessor network as set forth in claim 2, wherein: said number of processors N is not less than 16.
Claim 11
Dependent Claim
21 words
The multiprocessor network as set forth in claim 2, wherein: said multiprocessor network having a 3D-Mesh has a degree of 8.
Claim 12
Dependent Claim
26 words
The multiprocessor network as set forth in claim 2, wherein: the number of communications links connected to each processor is constant for all values of N.
Claim 13
Dependent Claim
21 words
The multiprocessor network as set forth in claim 1, wherein: said multiprocessor network having a 2D-Mesh has a degree of 6.
Claim 14
Independent Claim
153 words
A method for forming a network from N processors each having a constant number of communication ports supporting communication links between the processors, said method comprising the steps of: forming said N processors into an undirected binary De Bruijn Multiprocessor (BDM) network of degree 4 and diameter k, where N=2 n 2 k ; determining a Hamiltonian path through said BDM network; arranging said Hamiltonian path in a two-dimensional array of i rows and j columns where i×j=2 k ; augmenting said BDM network by adding communication links between processors which are in adjacent rows and columns if they do not exist from the Hamiltonian path; augmenting said BDM network by adding communication links between processors in the first row and last row which are in the same column; and augmenting said BDM network by adding communication links between processors in the first column and last column which are in the same row.
Claim 15
Independent Claim
153 words
A method for forming a network from N processors each having a constant number of communication ports supporting communication links between the processors, said method comprising the steps of: forming said N processors into an undirected binary De Bruijn Multiprocessor (BDM) network of degree 4 and diameter k, where N=2 n 2 k ; determining a Hamiltonian path through said BDM network; arranging said Hamiltonian path in a two-dimensional array of i rows and j columns where i×j=2 k ; augmenting said BDM network by adding communication links between processors which are in adjacent rows and columns if they do not exist from the Hamiltonian path; augmenting said BDM network by adding communication links between processors in the first row and last row which are in the same column; and augmenting said BDM network by adding communication links between processors in the first column and last column which are in the same row.
Claim 16
Dependent Claim
75 words
The method for forming a network as defined in claim 13, which further comprises the steps of: segmenting said two-dimensional array into l smaller arrays of size p×q where p×g×l=2 k ; stacking said l smaller arrays sequentially to form a three-dimensional stack; and augmenting said BDM network by adding communication links between each processor to a corresponding processor in the array preceding it in said stack and the array following it in said stack.
Claim 17
Dependent Claim
38 words
The method for forming a network as defined in claim 13, wherein: said forming step includes the step of modifying said BDM network to provide a communications link between the first and last nodes of the BDM network.
Claim 18
Dependent Claim
44 words
The method for forming a network as defined in claim 13, wherein: said forming step includes the step of modifying said BDM network to provide a communications link between each of the first and last nodes of the BDM network and external input/output devices.
Claim 19
Independent Claim
126 words
A method for augmenting a linear ring multiprocessor network of processor nodes, each having a constant number of communication ports and supporting communication links between the processor nodes, said method comprising the steps of: arranging the linear ring network in a two-dimensional array of i rows and j columns; augmenting the linear ring network by adding communication links between nodes which are in adjacent rows and columns if they do not exist from the linear ring network; augmenting the linear ring network by adding communication links between nodes in the first row and last row which are in the same column; and augmenting the linear ring network by adding communication links between nodes in the first column and last column which are in the same row.
Claim 20
Independent Claim
126 words
A method for augmenting a linear ring multiprocessor network of processor nodes, each having a constant number of communication ports and supporting communication links between the processor nodes, said method comprising the steps of: arranging the linear ring network in a two-dimensional array of i rows and j columns; augmenting the linear ring network by adding communication links between nodes which are in adjacent rows and columns if they do not exist from the linear ring network; augmenting the linear ring network by adding communication links between nodes in the first row and last row which are in the same column; and augmenting the linear ring network by adding communication links between nodes in the first column and last column which are in the same row.
Claim 21
Dependent Claim
74 words
The method for augmenting a linear ring multiprocessor network as defined in claim 17, which further comprises the steps of: segmenting said two-dimensional array into l smaller arrays of size p×q; stacking said l smaller arrays sequentially to form a three-dimensional stack; and augmenting said three-dimensional stack by adding communication links between each node to a corresponding node in the array preceding it in said stack and the array following it in said stack.
Claim 22
Dependent Claim
106 words
A multiprocessor network having a plurality N of processors connected together by a plurality of communications links, each processor adapted for parallel computation of an executable program with the other processors, said network comprising: N processors, each having a distinct address and having P communications ports, said communications ports connecting said N processors in the network by said plurality of communications links, wherein each port is adapted for sending and receiving data and instructions; each of said N processors configured as a linear ring multiprocessor network having a degree 2; and each of said N processors having at least some communications links configured as a 2D-Mesh.
Claim 23
Dependent Claim
106 words
A multiprocessor network having a plurality N of processors connected together by a plurality of communications links, each processor adapted for parallel computation of an executable program with the other processors, said network comprising: N processors, each having a distinct address and having P communications ports, said communications ports connecting said N processors in the network by said plurality of communications links, wherein each port is adapted for sending and receiving data and instructions; each of said N processors configured as a linear ring multiprocessor network having a degree 2; and each of said N processors having at least some communications links configured as a 2D-Mesh.
Claim 24
Dependent Claim
25 words
The multiprocessor network as set forth in claim 19, wherein: each of said N processors having at least some communications links configured as a 3D-Mesh.
Claim 25
Dependent Claim
21 words
The multiprocessor network as set forth in claim 20, wherein: said multiprocessor network having a 3D-Mesh has a degree of 6.
Claim 26
Dependent Claim
21 words
The multiprocessor network as set forth in claim 19, wherein: said multiprocessor network having a 2D-Mesh has a degree of 4.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-07-28 | 1996-01-27 | 1996-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-07-28 | 2000-01-27 | 2000-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-07-28 | 2004-01-27 | 2004-07-28 | $7700.00 | Window Closed / Lapsed |