ON BUFFERLESS ROUTING OF VARIABLE-LENGTH MESSAGES IN LEVELED NETWORKS

We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct le ngths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatch ed ever to be delayed on their routes. By insisting on oblivious route s for messages, we convert the communication problem to a pure schedul ing problem. We introduce the notion of a virtual chatting schedule, a nd we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategi es far producing efficient virtual chatting schedules on a variety of network topologies.