US5432909A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for redistributing multiple distributed data sets in a ring connected multiprocessor
Assignee: Eastman Kodak Co
•
Filing: 1994-12-06
•
Granted: 1995-07-11
•
Expires: 2014-12-06
Abstract
Abstract A method and apparatus for interprocessor communication using a ring of processors linked together with independent direct memory access type communication interfaces. The interfaces simultaneously input and output data in both directions around the ring. Four I/O memory buffers to support simultaneous communication in both directions. The ring of processors together pass each data packet half way around the ring in each direction. As each data packet or data subset enters the processor it is stored either in a temporary I/O buffer for later retransmission around the ring in the same direction as originally travelling or stored in the final destination data array. The output of data stored locally destined for another processor is intermingled with the data which is retransmitted.
Inventors
- 👤 Ronald Steven Cok
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:03
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
195 words
A method of redistributing multiple distributed data sets in a ring of processors having first and second directions of communication, the data sets being distributed as data subsets in the processors, whereby each processor contains a subset from one of the data sets, the data subsets being redistributed such that every processor will contain one unique complete data set, the data subsets to be stored in a particular processor being local data subsets with respect to that particular processor, and the data subsets to be stored in other processors being foreign data subsets with respect particular processor, comprising the steps of: a) transmitting from each processor foreign data subsets stored in that processor in both the first and second directions; b) transmitting from each processor foreign data subsets in the first and second directions when received by that processor in the first and second directions, respectively; c) storing in each processor local data subsets when received from other processors in the first and second directions; and d) repeating steps b) and c) until every processor processor has received and stored every on of its own local data subsets to form a unite complete data set.
Claim 2
Independent Claim
195 words
A method of redistributing multiple distributed data sets in a ring of processors having first and second directions of communication, the data sets being distributed as data subsets in the processors, whereby each processor contains a subset from one of the data sets, the data subsets being redistributed such that every processor will contain one unique complete data set, the data subsets to be stored in a particular processor being local data subsets with respect to that particular processor, and the data subsets to be stored in other processors being foreign data subsets with respect particular processor, comprising the steps of: a) transmitting from each processor foreign data subsets stored in that processor in both the first and second directions; b) transmitting from each processor foreign data subsets in the first and second directions when received by that processor in the first and second directions, respectively; c) storing in each processor local data subsets when received from other processors in the first and second directions; and d) repeating steps b) and c) until every processor processor has received and stored every on of its own local data subsets to form a unite complete data set.
Claim 3
Dependent Claim
59 words
A method as recited in claim 1, wherein step (b) includes: (b1) in each processor, storing data subsets received in a temporary input buffer and storing data subsets to be transmitted in a temporary output buffer; and (b2) converting the temporary input buffer into the temporary output buffer and converting the temporary output buffer into the temporary input buffer.
Claim 4
Independent Claim
280 words
A method of redistributing multiple distributed data sets in a ring of processors, the ring having first and second directions of communication, the data sets being distributed as data subsets in the processors, whereby each processor contains a subset from one of the data sets, the data subsets being redistributed such that every processor will contain one unique complete data set, the data subsets to be stored in a particular processor being local data subsets with respect to that particular processor, and the data subsets to be stored in other processors being foreign data subsets with respect particular processor, said method comprising the steps for each processor i; (a) transmitting a data subset for the i-1th processor in the first direction, transmitting a data subset for the i+1th processor in the second direction, receiving and storing local data subsets for the ith processor received in the first and second directions; (b) transmitting a data subset for the i-nth processor in the first direction, transmitting a data subset for the i+nth processor in the second direction, receiving in the first direct. ion and storing temporarily a data subset for the i+(n-1)th processor, and receiving in the second direction and storing temporarily a data subset for the i-(n-1)th processor, where n starts at 2 and increments by 1 each time this stem is performed; (c) transmitting the temporarily stored data subsets in the first and second directions, respectively, and receiving and storing local data subsets received in the first and second directions; and d) repeating steps b) and c) until every processor i has received and stored every one of its own local data subsets to form a unique complete data set.
Claim 5
Independent Claim
280 words
A method of redistributing multiple distributed data sets in a ring of processors, the ring having first and second directions of communication, the data sets being distributed as data subsets in the processors, whereby each processor contains a subset from one of the data sets, the data subsets being redistributed such that every processor will contain one unique complete data set, the data subsets to be stored in a particular processor being local data subsets with respect to that particular processor, and the data subsets to be stored in other processors being foreign data subsets with respect particular processor, said method comprising the steps for each processor i; (a) transmitting a data subset for the i-1th processor in the first direction, transmitting a data subset for the i+1th processor in the second direction, receiving and storing local data subsets for the ith processor received in the first and second directions; (b) transmitting a data subset for the i-nth processor in the first direction, transmitting a data subset for the i+nth processor in the second direction, receiving in the first direct. ion and storing temporarily a data subset for the i+(n-1)th processor, and receiving in the second direction and storing temporarily a data subset for the i-(n-1)th processor, where n starts at 2 and increments by 1 each time this stem is performed; (c) transmitting the temporarily stored data subsets in the first and second directions, respectively, and receiving and storing local data subsets received in the first and second directions; and d) repeating steps b) and c) until every processor i has received and stored every one of its own local data subsets to form a unique complete data set.
References Cited (Backward Citations)
US4460994A
Cited
US4667287A
Cited
US4752924A
Cited
US5230073A
Cited
US5202971A
Cited
US5129093A
Cited
US5241540A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-07-10 | 1999-01-09 | 1999-07-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-07-10 | 2003-01-09 | 2003-07-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-07-10 | 2007-01-09 | 2007-07-11 | $7700.00 | Window Closed / Lapsed |