Online Scheduled Routing

  For some communication patterns, the most efficient implementation involves simply providing online routing. In particular, any communication pattern where the communication sources and destinations change rapidly relative to the message size, and where there is no constraint on the values of the sources and destinations, is likely to be most efficiently implemented by online routing.

Furthermore, providing support for online routing in a scheduled router is a guarantee of generality: by providing the same functionality as a dynamic router, the compiler ensures that any application that can be run on the dynamic router can be run on the scheduled router. For applications that require a great deal of online routing, scheduled routing will not perform as well as dynamic routing; however, it seems likely that a large class of applications have sufficient exploitable regularity in their message traffic that the fraction of online routing necessary will be low enough not to compromise the overall run time significantly.