Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-05-05
2003-09-02
Butler, Dennis M. (Department: 2185)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C713S502000
Reexamination Certificate
active
06615281
ABSTRACT:
TECHNICAL FIELD
The present invention relates to processing systems. More particularly, the present invention relates to multiple-node processing systems (e.g., parallel processing systems) in which the nodes require synchronization for events such as communication of processing results.
BACKGROUND OF THE INVENTION
Massive cache machines (“MCMs”) and other parallel processing systems require tightly synchronized nodes to share data synchronously, regardless of the type of compute model used. For example, in tightly-coupled single instruction multiple data (“SIMD”) system models, each node runs the same instruction from a common source, but operates on its own data. In the more loosely-coupled multiple instruction multiple data (“MIMD”) system model, each node independently runs its own instructions on its own data. With reference to
FIG. 1
, such computer systems
100
may include parallel CPU processing nodes
101
a
. . .
101
n
, commonly coupled by a bus
104
to, for example, an interrupt control unit
103
and/or a storage unit
102
.
The “compute” modes discussed above are usually accompanied by “communicate” modes during which the results of the computations must be communicated between the nodes. However, the nodes may be ready to communicate at different times, out of synchronization. Node synchronization is therefore usually required regardless of the type of compute mode employed.
To effect the required communication, without perfect synchronization, data buffering can be used on storage unit
102
. The writing node deposits its data in a buffer, to be read later by the reading node. The problems with this approach are well-known, and include buffer space limitations, buffer deadlock, and extra read/write cycles.
Nodes can also be required to poll memory locations or registers that have values controlling synchronization. Polling, however, requires extra processing cycles, which can become excessive if all nodes are required to continuously poll for synchronization during their otherwise routine processing tasks.
Interrupts can also be used to synchronize nodes. However, interrupting a node from its routine processing creates problems, such as requiring the reading node to perform a context switch from its compute mode to its communicate mode. A context switch occasioned by an interrupt can be costly in terms of lost processing time, and can also interrupt critical processing.
In the previously issued, commonly assigned U.S. Pat. No. 5,778,221 entitled “System for Executing Asynchronous Branch and Link in Parallel Processor,” (incorporated herein by reference in its entirety) a technique for a lighter-weight context switch is disclosed, triggered by a “special interrupt.” That patent discusses easing the costs of a context switch, but the problem of issuing the interrupt triggering the context switch remains. Improved synchronization techniques are still required to generate interrupts only when absolutely needed, and to minimize their effects on ongoing processing.
SUMMARY OF THE INVENTION
The above problems are addressed, and further advantages are provided, by the present invention which in one aspect is a method and system for synchronizing at least two processing nodes for an event. At least one state counter indicates at least two states including a first, non-impending event state within which nodes polling the state counter continue routine processing; and a second, impending event state within which nodes polling the state counter suspend routine processing to wait for the impending event. A stimulus source shifts the state counter between the at least two states; and an interrupt means is provided for generating an interrupt to synchronize non-waiting nodes for the event.
Nodes may refrain from further polling during the first, non-impending event state; but may poll while waiting during the second, impending event state.
The stimulus source may comprise a timing source, and a timing counter receiving transitions from the timing source, counting to respective, programmable state lengths, and shifting the state counter between its respective states. A respective state counter may be provided in each processing node, stimulated by a stimulus source shared by the processing nodes.
Additional states may be imposed, including a third, interrupt state at the end of which the interrupt is generated; and a fourth, event state within which the event occurs.
The synchronization technique of the present invention is particularly useful for synchronizing parallel processing nodes for the communication of processing results, but can be used for any arbitrary event for which node synchronization is necessary.
By providing the synchronized states of the present invention, which change the operation of the nodes from routine processing to waiting as the event approaches, a balance is struck between harsh, asynchronous interrupts and excessive polling. Here, interrupts are used to interrupt non-waiting nodes only, and nodes which “arrived” during the impending event state are spared interruption and wait for the event by, e.g., polling during that time.
REFERENCES:
patent: 4503497 (1985-03-01), Krygowski et al.
patent: 5083265 (1992-01-01), Valiant
patent: 5086500 (1992-02-01), Greub
patent: 5113523 (1992-05-01), Colley et al.
patent: 5192882 (1993-03-01), Lipovski
patent: 5241543 (1993-08-01), Amada et al.
patent: 5261067 (1993-11-01), Whelan
patent: 5276828 (1994-01-01), Dion
patent: 5307381 (1994-04-01), Ahuja
patent: 5329630 (1994-07-01), Baldwin
patent: 5361277 (1994-11-01), Grover
patent: 5384906 (1995-01-01), Horst
patent: 5448732 (1995-09-01), Matsumoto
patent: 5502819 (1996-03-01), Aldrich et al.
patent: 5778221 (1998-07-01), Temple
patent: 5923855 (1999-07-01), Yamazaki
patent: 5968135 (1999-10-01), Teramoto et al.
patent: 5978838 (1999-11-01), Mohamed et al.
patent: 42 21 278 (1992-06-01), None
Harper, IBM Technical Disclosure Bulletin, vol. 32 No. 12, 5/90, Method of Keeping and Synchronizing Time in a Message-Passing Distributed System, pp 422-425.
Butler Dennis M.
Ehrlich, Esq. Marc A.
Gonzalez, Esq. Floyd A.
Heslin Rothenberg Farley & & Mesiti P.C.
LandOfFree
Multi-node synchronization using global timing source and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-node synchronization using global timing source and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-node synchronization using global timing source and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089279