TY - GEN
T1 - On bufferless routing of variable-length messages in leveled networks
AU - Bhatt, S. N.
AU - Bilardi, G.
AU - Pucci, G.
AU - Ranade, A.
AU - Rosenberg, A. L.
AU - Schwabe, E. J.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - We study the most general communication paradigm on a multiprocessor wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.
AB - We study the most general communication paradigm on a multiprocessor wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.
UR - http://www.scopus.com/inward/record.url?scp=0012524425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012524425&partnerID=8YFLogxK
U2 - 10.1007/3-540-57273-2_43
DO - 10.1007/3-540-57273-2_43
M3 - Conference contribution
AN - SCOPUS:0012524425
SN - 9783540572732
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 60
BT - Algorithms ESA 1993 – 1st Annual European Symposium, Proceedings
A2 - Lengauer, Thomas
T2 - 1st Annual European Symposium on Algorithms, ESA 1993
Y2 - 30 September 1993 through 2 October 1993
ER -