Sökning: onr:"swepub:oai:DiVA.org:kth-91063" >
Spanning Graphs for...
Spanning Graphs for Optimum Broadcasting and Personalized Communication in Hypercubes
-
- Johnsson, Lennart (författare)
- KTH,Parallelldatorcentrum, PDC
-
Ho, Ching-Tien (författare)
-
(creator_code:org_t)
- Institute of Electrical and Electronics Engineers (IEEE), 1989
- 1989
- Engelska.
-
Ingår i: IEEE Transactions on Computers. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9340 .- 1557-9956. ; 38:9, s. 1249-1268
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Four different communication problems are addressed in Booleann-cube configured multiprocessors: (1) one-to-all broadcasting: distribution of common data from a single source to all other nodes; (2) one-to-all personalized communication: a single node sending unique data to all other nodes; (3) all-to-all broadcasting: distribution of common data from each node to all other nodes; and (4) all-to-all personalized communication: each node sending a unique piece of information to every other node. Three communication graphs (spanning trees) for the Booleann-cube are proposed for the routing, and scheduling disciplines provably optimum within a small constant factor are proposed. With appropriate scheduling and concurrent communication on all ports of every processor, routings based on these two communication graphs offer a speedup of up ton/2, and O(√n) over the routings based on the spanning binomial tree for cases (2)-(4) respectively. All three spanning trees offer optimal communication times for cases (2)-(4) and concurrent communication on all ports of every processor. Timing models and complexity analysis are verified by experiments on a Boolean-cube-configured multiprocessor
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas