US5428803A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for a unified parallel processing architecture
Assignee: Morgan Stanley and Co LLC
•
Filing: 1992-07-10
•
Granted: 1995-06-27
•
Expires: 2012-07-10
Abstract
Abstract A unified parallel processing architecture connects together an extendible number of clusters of multiple numbers of processors to create a high performance parallel processing computer system. Multiple processors are grouped together into four or more physically separable clusters, each cluster having a common cluster shared memory that is symmetrically accessible by all of the processors in that cluster; however, only some of the clusters are adjacently interconnected. Clusters are adjacently interconnected to form a floating shared memory if certain memory access conditions relating to relative memory latency and relative data locality can create an effective shared memory parallel programming environment. A shared memory model can be used with programs that can be executed in the cluster shared memory of a single cluster, or in the floating shared memory that is defined across an extended shared memory space comprised of the cluster shared memories of any set of adjacently interconnected clusters. A distributed memory model can be used with any programs that are to be executed in the cluster shared memories of any non-adjacently interconnected clusters. The adjacent interconnection of multiple clusters of processors to a create a floating shared memory effectively combines all three type of memory models, pure shared memory, extended shared memory and distributed shared memory, into a unified parallel processing architecture.
Inventors
- 👤 Steve S. Chen
- 👤 Douglas R. Beard
- 👤 George A. Spix
- 👤 Edward C. Priest
- 👤 John M. Wastlick
- 👤 James M. VanDyke
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 15:04
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/16; G06F13/1605; G06F13/1652; G06F13/1657; G06F1/00; G06F1/04; G06F1/10; G06F13/1663; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17356; G06F15/17368; G06F15/17381
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
270 words
A unified parallel processing architecture for connecting together an extendible number of clusters of multiple numbers of processors to create a parallel processing computer system, the unified parallel processing architecture comprising: four or more clusters of multiprocessors, each cluster comprising: a cluster shared memory means for storing and retrieving data and instructions for one or more parallel tasks of one or more computer programs; two or more processor means for executing the instructions and operating directly on the data for the parallel tasks that are stored in the cluster shared memory means; one or more input/output port means for transferring the data and instructions for the parallel tasks between the cluster shared memory means and one or more external data sources via one or more block-by-block communication paths; and connection node means for connecting the cluster shared memory means with all of the processor means in the cluster such that access to the clustered shared memory means by all of the processor means in the cluster is symmetrical; means for providing a plurality of floating shared memories by adjacently connecting some, but not all of the clusters, via one or more word-by-word communication paths to create a floating shared memory that is defined by the cluster shared memory means of the cluster and the cluster shared memory means of any adjacently interconnected clusters and that can be programmed using a shared memory model; and means for providing an extended distributed memory among any non-adjacently interconnected clusters that defines an extendible address space encompassing the cluster shared memory means of all clusters that can be programmed using a distributed memory model.
Claim 2
Dependent Claim
270 words
A unified parallel processing architecture for connecting together an extendible number of clusters of multiple numbers of processors to create a parallel processing computer system, the unified parallel processing architecture comprising: four or more clusters of multiprocessors, each cluster comprising: a cluster shared memory means for storing and retrieving data and instructions for one or more parallel tasks of one or more computer programs; two or more processor means for executing the instructions and operating directly on the data for the parallel tasks that are stored in the cluster shared memory means; one or more input/output port means for transferring the data and instructions for the parallel tasks between the cluster shared memory means and one or more external data sources via one or more block-by-block communication paths; and connection node means for connecting the cluster shared memory means with all of the processor means in the cluster such that access to the clustered shared memory means by all of the processor means in the cluster is symmetrical; means for providing a plurality of floating shared memories by adjacently connecting some, but not all of the clusters, via one or more word-by-word communication paths to create a floating shared memory that is defined by the cluster shared memory means of the cluster and the cluster shared memory means of any adjacently interconnected clusters and that can be programmed using a shared memory model; and means for providing an extended distributed memory among any non-adjacently interconnected clusters that defines an extendible address space encompassing the cluster shared memory means of all clusters that can be programmed using a distributed memory model.
Claim 3
Dependent Claim
19 words
The parallel processing architecture of claim 1 further comprising: means for providing an extendible clock signal to each cluster.
Claim 4
Dependent Claim
60 words
The parallel processing architecture of claim 1 further comprising: means for providing an extendible control mechanism for each cluster that is accessible by a distributed operating system program executing on any of the processor means in any of the clusters for distributively controlling the communication and coordination among a plurality of processes executing in parallel in the computer processing system.
Claim 5
Dependent Claim
100 words
The parallel processing architecture of claim 1 wherein the means for providing a plurality of floating shared memories comprises: two or more cluster connection means for each cluster for adjacently connecting all of the processor means in the cluster with the cluster shared memory means in two or more, but not all, of the other clusters via one or more word-by-word communication paths such that the processor means can execute the instructions and operate directly on the data for the parallel tasks that are stored in any of the cluster shared memory means of any of the adjacently connected clusters.
Claim 6
Dependent Claim
56 words
The parallel processing architecture of claim 4 wherein either an input/output port means or a cluster connection means can be interchangeably connected to shared memory means via the connection node means and wherein the total number of input/output port means and cluster connection means is fixed for each cluster and the ratio of input/output is configurable.
Claim 7
Dependent Claim
57 words
The parallel processing architecture of claim 1 wherein the means for providing an extended distributed memory comprises: a message passing scheme implemented in an operating system program executing in one or more processors of each cluster such that messages may be passed among the processor means in all of the clusters in the parallel processing computer system.
Claim 8
Dependent Claim
78 words
The parallel processing architecture of claim 1 wherein the means for providing an extended distributed memory comprises: a floating scheme implemented in an operating system program executing in one or more of the processor means in each cluster such that one or more segments of data or instructions for a parallel task are moved from the floating shared memory of one set of adjacently interconnected clusters to the floating shared memory of another set of adjacently interconnected clusters.
Claim 9
Dependent Claim
64 words
The parallel processing architecture of claim 1 where the connection node means comprises: two or more arbitration node means, each arbitration node means having two or more unique unidirectional direct connection paths between the cluster shared memory means and a unique two or more of the processor means for symmetrically multiplexing the unique two or more processor means to the clustered shared memory means.
Claim 10
Dependent Claim
93 words
The parallel processing architecture of claim 1 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster memory access by a processor means in one cluster to the cluster shared memory means of another cluster is less than ten times greater than the average memory latency of an intra-cluster memory access by a processor means to the cluster shared memory means within that cluster and the average number of the inter-cluster memory accesses is less than ten percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 11
Dependent Claim
64 words
The parallel processing architecture of claim 9 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster memory access is less than five times greater than the average memory latency of an intra-cluster memory access and the average number of the inter-cluster memory accesses is less than five percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 12
Dependent Claim
63 words
The parallel processing architecture of claim 9 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster access is less than about two times greater than the average memory latency of an intra-cluster access and the average number of the inter-cluster memory accesses is less than one percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 13
Independent Claim
193 words
A method for providing a unified parallel processing architecture for a parallel processing computer system that can process one or more computer programs in parallel, each computer program having a problem space of a predetermined size, the method comprising the steps of: (a) providing 4 or more clusters of multiprocessors, each cluster having 2 or more processors that are symmetrically connected to a cluster shared memory such that each processor in the cluster has a similar average memory latency when accessing the cluster shared memory; (b) adjacently interconnecting each cluster to some, but not all, of the other clusters; (c) remotely interconnecting each cluster to all other clusters to which that cluster is not adjacently interconnected; (d) using a shared memory model to process in parallel any computer programs having a problem space of a size that is less than the size of a floating shared memory defined by the collective cluster shared memories of a set of adjacently interconnected clusters; and (e) using a distributed memory model to process in parallel any computer programs having a problem space of a size that is greater than the size of the floating shared memory.
Claim 14
Independent Claim
193 words
A method for providing a unified parallel processing architecture for a parallel processing computer system that can process one or more computer programs in parallel, each computer program having a problem space of a predetermined size, the method comprising the steps of: (a) providing 4 or more clusters of multiprocessors, each cluster having 2 or more processors that are symmetrically connected to a cluster shared memory such that each processor in the cluster has a similar average memory latency when accessing the cluster shared memory; (b) adjacently interconnecting each cluster to some, but not all, of the other clusters; (c) remotely interconnecting each cluster to all other clusters to which that cluster is not adjacently interconnected; (d) using a shared memory model to process in parallel any computer programs having a problem space of a size that is less than the size of a floating shared memory defined by the collective cluster shared memories of a set of adjacently interconnected clusters; and (e) using a distributed memory model to process in parallel any computer programs having a problem space of a size that is greater than the size of the floating shared memory.
Claim 15
Dependent Claim
86 words
The method of claim 12 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster memory access by a processor in one cluster to the cluster shared memory of another cluster is less ten times greater than the average memory latency of an intra-cluster memory access by a processor to the cluster shared memory within that cluster and the average number of the inter-cluster memory accesses is less than ten percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 16
Dependent Claim
62 words
The method of claim 13 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster memory access is less than five times greater than the average memory latency of an intra-cluster memory access and the average number of the inter-cluster memory accesses is less than five percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 17
Dependent Claim
61 words
The method of claim 13 wherein clusters are adjacently interconnected if the average memory latency of an inter-cluster access is less than about two times greater than the average memory latency of an intra-cluster access and the average number of the inter-cluster memory accesses is less than one percent of the number of intra-cluster memory accesses for an average parallel task.
Claim 18
Dependent Claim
19 words
The method of claim 12 further comprising the step of: (f) providing each cluster with an extendible clock signal.
Claim 19
Dependent Claim
59 words
The method of claim 12 further comprising the step of: (f) providing each cluster with an extendible control mechanism that is accessible by a distributed operating system program executing on any of the processors in any of the clusters for distributively controlling the communication and coordination among a plurality of processes executing in parallel in the computer processing system.
Claim 20
Dependent Claim
46 words
The method of claim 12 wherein step (e) comprises: using a message passing scheme implemented in an operating system program executing in one or more processors of each cluster to pass messages among the processors in all of the clusters in the parallel processing computer system.
Claim 21
Dependent Claim
69 words
The method of claim 12 wherein step (e) comprises: using a floating scheme implemented in an operating system program executing in one or more of the processor means in each cluster to move one or more segments of data or instructions for a parallel task from the floating shared memory of one set of adjacently interconnected clusters to the floating shared memory of another set of adjacently interconnected clusters.
Claim 22
Dependent Claim
163 words
A unified parallel processing architecture for connecting multiple processors to multiple memory components to form a parallel processing computer system comprising: four or more cluster means for connecting a plurality of processors to one or more memory components such that the processors can symmetrically access the one or more memory components using a shared memory model; two or more floating shared memory means for uniquely and adjacently connecting some, but not all, of the plurality of the cluster means such that the processors in a floating shared memory means can access any of the memory components in the floating shared memory means using an extended shared memory model; and distributed memory communication means for providing communication among any of the cluster means that are not adjacently connected by a floating shared memory means such that any of the processors in the parallel processing computer system can access any of the memory components in the parallel processing computer system using a distributed memory model.
Claim 23
Dependent Claim
163 words
A unified parallel processing architecture for connecting multiple processors to multiple memory components to form a parallel processing computer system comprising: four or more cluster means for connecting a plurality of processors to one or more memory components such that the processors can symmetrically access the one or more memory components using a shared memory model; two or more floating shared memory means for uniquely and adjacently connecting some, but not all, of the plurality of the cluster means such that the processors in a floating shared memory means can access any of the memory components in the floating shared memory means using an extended shared memory model; and distributed memory communication means for providing communication among any of the cluster means that are not adjacently connected by a floating shared memory means such that any of the processors in the parallel processing computer system can access any of the memory components in the parallel processing computer system using a distributed memory model.
Claim 24
Dependent Claim
271 words
A multiprocessor cluster adapted to be connected to other similar clusters in a parallel processing computer system, the multiprocessor cluster comprising: a cluster shared memory means for storing and retrieving data and instructions for one or more parallel tasks of one or more computer programs; two or more processor means for executing the instructions and operating directly on the data for the parallel tasks that are stored in the cluster shared memory means; one or more input/output port means for transferring the data and instructions for the parallel tasks between the cluster shared memory means and one or more external data sources via one or more block-by-block communication paths; connection node means for connecting the cluster shared memory means with all of the processor means in the cluster such that access to the clustered shared memory means by all of the processor means in the cluster is symmetrical; and two or more cluster connection means for adjacently connecting all of the processor means in the cluster with the cluster shared memory means of two or more other clusters via one or more word-by-word communication paths such that the processor means can execute the instructions and operate directly on the data for the parallel tasks that are stored in any of the cluster shared memory means of any of the adjacently connected clusters, wherein the input/output port means and the cluster connection means can be interchangeably connected to the shared memory means via the connection node means and wherein the total number of input/output port means and cluster connection means is fixed for each cluster and the ratio of input/output is configurable.
Claim 25
Dependent Claim
271 words
A multiprocessor cluster adapted to be connected to other similar clusters in a parallel processing computer system, the multiprocessor cluster comprising: a cluster shared memory means for storing and retrieving data and instructions for one or more parallel tasks of one or more computer programs; two or more processor means for executing the instructions and operating directly on the data for the parallel tasks that are stored in the cluster shared memory means; one or more input/output port means for transferring the data and instructions for the parallel tasks between the cluster shared memory means and one or more external data sources via one or more block-by-block communication paths; connection node means for connecting the cluster shared memory means with all of the processor means in the cluster such that access to the clustered shared memory means by all of the processor means in the cluster is symmetrical; and two or more cluster connection means for adjacently connecting all of the processor means in the cluster with the cluster shared memory means of two or more other clusters via one or more word-by-word communication paths such that the processor means can execute the instructions and operate directly on the data for the parallel tasks that are stored in any of the cluster shared memory means of any of the adjacently connected clusters, wherein the input/output port means and the cluster connection means can be interchangeably connected to the shared memory means via the connection node means and wherein the total number of input/output port means and cluster connection means is fixed for each cluster and the ratio of input/output is configurable.
Claim 26
Dependent Claim
63 words
The multiprocessor cluster of claim 21 wherein the connection node means comprises: two or more arbitration node means, each arbitration node means having two or more unique unidirectional direct connection paths between the cluster shared memory means and a unique two or more of the processor means for symmetrically multiplexing the unique two or more processor means to the clustered shared memory means.
Claim 27
Dependent Claim
31 words
The multiprocessor cluster of claim 22 wherein each arbitration node means also provides a unique connection to the shared memory means for two input/output port means or one cluster connection means.
Claim 28
Dependent Claim
148 words
The multiprocessor cluster of claim 23 wherein the cluster communication means comprises: an inter-cluster dispatch means operably connected to all of the arbitration node means for receiving one or more inter-cluster memory accesses from any of the processors in the multiprocessor cluster; a cluster connection output port means operably connected to one of the arbitration node means for transferring one or more inter-cluster memory accesses from the inter-cluster dispatch means to any adjacently connected cluster; and a cluster connection input port means operably connected to the same one of the arbitration node means for receiving one or more inter-cluster memory accesses from any of the processors in any adjacently connected cluster and presenting the one or more inter-cluster memory accesses from any of the processors in any adjacently connected cluster to the cluster shared memory of the multiprocessor cluster via the same one of the arbitration node means.
References Cited (Backward Citations)
US4130865A
Cited
US4707781A
Cited
US4365292A
Cited
US4400768A
Cited
US4445171A
Cited
US4636942A
Cited
US4901230A
Cited
US5113523A
Cited
US4745545A
Cited
US4754398A
Cited
US4720780A
Cited
US4827403A
Cited
US4873626A
Cited
US4891751A
Cited
US4834483A
Cited
US5081575A
Cited
US5055999A
Cited
US5056000A
Cited
US5072371A
Cited
US5165038A
Cited
US5179702A
Cited
US5197130A
Cited
US5208914A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-06-26 | 1998-12-26 | 1999-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-06-26 | 2002-12-26 | 2003-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-06-26 | 2006-12-26 | 2007-06-27 | $7700.00 | Window Closed / Lapsed |