US5250943A
Expired / Lapsed
US
⏱️ 0.0 years remaining
GVT-NET--A Global Virtual Time Calculation Apparatus for Multi-Stage Networks
Assignee: International Business Machines Corp
•
Filing: 1991-08-21
•
Granted: 1993-10-05
•
Expires: 2011-08-21
Abstract
Abstract A GVT-NET apparatus for all processor nodes of a parallel system for repetitive calculation of the latest global virtual time (GVT) value quickly and accurately over the communication multi-stage network (NET) that normally transmits data between nodes as point-to-point communications, broadcast, multi-cast, or multi-sender transfers. For multi-processor synchronization, each processing node can free-run and keep track of its local time and synchronize with the other processors by polling all processors to determine the minimal of the individual local times and indicate how far the entire job has progressed. The multi-sender and multi-cast functions in the multi-stage network enable every node attached to the multi-stage network to participate in one common and simultaneous GVT calculation, where each processor node can simultaneously transmit the inverse of its local time to the network and at the same time monitor the network output. Through one joint network transfer, all processor nodes can work together to determine GVT (which local time is lowest). Each processor node compares the inverse local time value sent to the network to the composite OR value received back from the network, and takes itself out of the calculation if the values do not compare by transmitting all zeroes in place of its inverse local time. All processor nodes can store it (inverted) immediately to get the latest copy of GVT.
Inventors
- 👤 Philip L. Childs
- 👤 Howard T. Olnowich
- 👤 Joseph F. Skovira
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:32
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; G; G06; G06F; G06F13/00; G06F13/38; G06F13/40; G06F13/4004; G06F13/4022; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17375; G06F15/17393; G06F30/00; G06F30/30; G06F30/32; G06F30/33; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L49/00; H04L49/15; H04L49/25; H04L7/00; H04L7/02; H04L7/033; H04L7/0337; H04L7/0338; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; G06F11/00; G06F11/22; G06F11/26; G06F11/261; H04L12/1881; H04L49/10; H04L49/101; H04L49/1515; H04L49/1523; H04L49/20; H04L49/201; H04L49/253; H04L49/254; H04L49/30; H04L49/40; H04L49/55; H04L49/555; H04Q11/0001; H04Q11/0062; H04Q11/0066
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
135 words
A multi-stage interconnection network and Global Virtual Time apparatus (GVT-NET), jointly functioning in a system having n processor nodes, comprising: a plurality of transmitting elements; a plurality of receiving elements; a multi-sender switch apparatus means comprising a network for coupling said elements asynchronously through input to output port connections for establishing point to point input to output port connections, single input to multiple or all output port connections, and multiple or all input port connections to multiple or all output port connections; a GVT-NET apparatus located at every system element and comprised of identical functions at each element including: a local time register; a global virtual time register; a GVT-NET control function; a normal network traffic control function; a data selection multiplexer for selecting various data sources for transmission of data to the said network.
Claim 2
Dependent Claim
135 words
A multi-stage interconnection network and Global Virtual Time apparatus (GVT-NET), jointly functioning in a system having n processor nodes, comprising: a plurality of transmitting elements; a plurality of receiving elements; a multi-sender switch apparatus means comprising a network for coupling said elements asynchronously through input to output port connections for establishing point to point input to output port connections, single input to multiple or all output port connections, and multiple or all input port connections to multiple or all output port connections; a GVT-NET apparatus located at every system element and comprised of identical functions at each element including: a local time register; a global virtual time register; a GVT-NET control function; a normal network traffic control function; a data selection multiplexer for selecting various data sources for transmission of data to the said network.
Claim 3
Dependent Claim
152 words
The apparatus of claim 1 wherein the said GVT-NET and said network provide means for calculating GVT fast and accurately by requiring each individual system element to transmit its own unique local time value to the said network simultaneously with all other system elements, to subsequently compare the local time value sent to the network to the composite value received back from the said network which is the logical OR of all the individual local times sent to the said network, to continue to transmit the local time value to the said network if there is an identical compare detected or to change the transmission to all zeroes if there is not an identical compare detected, and finally to receive the final composite value from the network as the latest GVT value independent of whether each particular system element is transmitting all zeroes or the local time value to the said network.
Claim 4
Dependent Claim
33 words
The apparatus of claim 1 wherein the said GVT-NET apparatus provides a means whereby the GVT-NET works jointly with a node processor to respond individually to every joint calculation over the said network.
Claim 5
Dependent Claim
20 words
The apparatus of claim 1 wherein the GVT-NET interrupts a processing node and requests information, pertinent to a joint calculation.
Claim 6
Dependent Claim
33 words
The apparatus of claim 1 wherein a node processor provides requested data to the GVT-NET which in turn supplies the said data to the network for the purpose of performing a joint calculation.
Claim 7
Dependent Claim
24 words
The apparatus of claim 1 wherein the said GVT-NET apparatus provides a means enabling the local time register and the Global Virtual Time register.
Claim 8
Dependent Claim
59 words
The apparatus of claim 2 wherein the said GVT-NET apparatus provides a means for performing GVT calculations in a sequence of individual sub-calculations, and wherein each sub-calculation processes a portion of an entire GVT value, and the sub-calculations are combined to provide the correct over-all result for GVT, as if the calculation was all performed in one disjointed operation.
Claim 9
Dependent Claim
34 words
The apparatus of claim 2 wherein the said apparatus provides a means for continuing a multi-sender mode of operation established by a GVT-NET operation to perform further operations without breaking the existing network connections.
Claim 10
Dependent Claim
48 words
The apparatus of claim 2 wherein the said GVT-NET apparatus provides a means for using the network to find the minimum LOCAL TIME at any moment by polling all n processor nodes and then causing the new value of GVT to be loaded into all n processors simultaneously.
Claim 11
Dependent Claim
31 words
The apparatus of claim 2 wherein the said GVT-NET apparatus provides a means for using a maximizing network calculation circuit to perform a minimizing calculation by inverting the inputs and outputs.
Claim 12
Dependent Claim
64 words
The apparatus of claim 2 wherein the said GVT-NET apparatus provides a means for controlling a GVT calculation with one common set of logic which is adaptable to be used at a processor requesting the GVT calculation and at processors not requesting the GVT calculation and still cause them all to work together to provide the final result of calculating a new GVT value.
Claim 13
Dependent Claim
53 words
The apparatus of claim 2 wherein the said apparatus provides a means for enabling all system elements to function jointly and simultaneously in one common operation involving every element and network facility to calculate the highest priority network requestor and to grant the said highest priority requestor the immediate usage of network facilities.
Claim 14
Dependent Claim
42 words
The apparatus of claim 2 wherein the said network provides a means for enabling all system elements connected to network facilities to use the facilities of the said network to perform GVT calculations as commanded from any of the said system elements.
Claim 15
Dependent Claim
46 words
The apparatus of claim 2 wherein the said network provides a means for enabling all said system elements to contribute to one joint GVT calculation and a means for all said system elements to receive the result of the said joint GVT calculation simultaneously and identically.
Claim 16
Dependent Claim
51 words
The apparatus of claim 2 wherein the said network provides a means for enabling all the said system elements to transmit a data bit pattern simultaneously and to use network facilities to logically OR the said data bit patterns and to provide the result back to all said system elements simultaneously.
Claim 17
Dependent Claim
30 words
The apparatus of claim 2 wherein the said network provides a means for handling GVT calculations performed in the said network consistently and compatibly over any number of network stages.
Claim 18
Dependent Claim
45 words
The apparatus of claim 7 wherein the GVT-NET apparatus provides a means for affecting a compare required as part of a sub-calculation of GVT based on the results of a previous sub-calculation, such that a previous discompare will cause all subsequent compare sub-calculations to discompare.
Claim 19
Dependent Claim
50 words
The apparatus of claim 7 wherein the said network provides a means for enabling all said elements to receive a positive indication via a composite ACCEPT signal that joint GVT sub-calculations and the said over-all GVT result has been completed by all the means for performing and the system elements.
Claim 20
Dependent Claim
48 words
The apparatus of claim 8 wherein the means for continuing multi-sender operations after the present operation is based on the value (1or 0) transmitted on a predefined data line to and from the said network during the final portion of the said present operation over the said network.
Claim 21
Dependent Claim
45 words
The apparatus of claim 8 wherein a data line to the said network is driven to a logical 1 from every system element that wishes to continue the multi-sender operations and to a 0 from every system element that wishes to terminate the multi-sender operations.
Claim 22
Dependent Claim
36 words
The apparatus of claim 8 wherein the network performs a logical OR on all data transmitted to it from all the said system elements, and sends the composite OR value to all the said system elements.
Claim 23
Dependent Claim
56 words
The apparatus of claim 8 wherein a logical one dominates an OR function over the said network, so that if one or more system elements wish to continue multi-sender operations, all the said system elements will see a logical 1 on a composite OR data line from the said network and will continue the multi-sender operations.
Claim 24
Dependent Claim
45 words
The apparatus of claim 8 wherein if none of the said system elements wish to continue multi-sender operations, all the said system elements will see a logical 0 on the said composite Or data line from the said network and will terminate the multi-sender operations.
Claim 25
Dependent Claim
44 words
The apparatus of claim 11 wherein the said GVT-NET apparatus provides a means whereby the initiating requestor may not become the first or next highest priority requester and continues to control all the sequencing of the joint calculations until all joint calculations are exhausted.
Claim 26
Dependent Claim
48 words
The apparatus of claim 12 wherein a subsequent second highest priority requestor is granted the immediate usage of the said network facilities after the first highest priority requestor has finished using the network facilities and without changing the network connections previously established for said first highest priority requestor.
Claim 27
Dependent Claim
67 words
The apparatus of claim 12 wherein the system elements which are not high priority requestors withdraw from the present priority calculation, keep their individual requests pending, keep the network connections from changing, and continue to participate in subsequent priority calculations involving all the said system elements and network facilities until they become the high priority requestors and are granted the immediate usage of the said network facilities.
Claim 28
Dependent Claim
57 words
The apparatus of claim 12 wherein the said highest priority requestor is the GVT-NET or multiple numbers of GVT-NETs all simultaneously requesting GVT calculations, and in either said case the one or several requestors will all jointly use the network facilities simultaneously as multi-senders involved in the same and simultaneous immediate usage of the said network facilities.
Claim 29
Dependent Claim
74 words
The apparatus of claim 18 wherein the network provides a means for ANDing individual calculation complete indications in the form of individual ACCEPT lines from all said system elements to form the said composite ACCEPT signal and then to send it simultaneously or at about the same time to all system elements so that all system elements receive a consistent indication that the joint GVT sub-calculations and the over-all GVT result have been completed.
Claim 30
Dependent Claim
48 words
The apparatus of claim 27 wherein the said multiple highest priority GVT-NET requestors are all simultaneously satisfied by the single and immediate usage of the said network facilities and all said highest priority requestors withdraw their present request for the usage of the said network upon being satisfied.
References Cited (Backward Citations)
US3246298A
Cited
US3268866A
Cited
US4237447A
Cited
US4251879A
Cited
US4307446A
Cited
US4314233A
Cited
US4307378A
Cited
US4956772A
Cited
US4935866A
Cited
US4475188A
Cited
US4482996A
Cited
US4484325A
Cited
US4481623A
Cited
US4518960A
Cited
US4941084A
Cited
US4623996A
Cited
US4754395A
Cited
US4701906A
Cited
US4706080A
Cited
US4835674A
Cited
US4818984A
Cited
US4815105A
Cited
US4855899A
Cited
US4926375A
Cited
US4897834A
Cited
US4766592A
Cited
US4952930A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-10-04 | 1997-04-05 | 1997-10-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-10-04 | 2001-04-05 | 2001-10-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-10-04 | 2005-04-05 | 2005-10-05 | $7700.00 | Window Closed / Lapsed |