Naïve objections to implementing online routing on top of scheduled routing include that it would require all the operators in a phase to be routed online; or, if not, that it might consume wire bandwidth out of proportion to the actual communication needs; or, for a 6-neighbor network, that every node would need 12 interface addresses dedicated to online routing. All of these statements turn out to be false.
While it is possible to dedicate all the timeslots in a phase to online routing, doing so is not necessary. If an operator that uses online routing shares a phase with an operator that does not, communications for the two operators can be scheduled in the same proportional manner that is used to schedule timeslots for offline-routed operators. Furthermore, fewer online-routing timeslots can be scheduled between nodes that have less online communications volume.
To ascertain how much online-routing bandwidth to allocate and how many interface addresses are required, the compiler iterates through the operators that are using online routing in the phase. For each operator, it examines the possible source/destination combinations that might exist, and allocates bandwidth along the e-cube routing path taken for each case. Thus, each operator yields a set of links that may be expected to support a certain data volume from that operator in this phase. For each link, all the contributions for all the operators in the phase are included. Two operators running sequentially during the phase would contribute the MAX of their bandwidths to the link, whereas two operators running in parallel would contribute the sum of the bandwidths to the link.
Consider the example of a 2D mesh with one stream (A) specified with unknown source and destination, and another stream (B) in parallel with A, whose destination is unknown but whose source is always processor zero.
In this case, a fixed bandwidth is allocated for every link corresponding to operator A; the bandwidth allocations on all the positive-going x links in the first row, and all positive-going y links, are then increased, corresponding to the e-cube delivery patterns of operator B.
The streams associated with online routing are associated with the phase itself, rather than any specific operator. When the stream information is passed to the stream router, the phase's online-routing streams are included along with any streams from operators using offline routing. On return from the stream router, the resulting bandwidth for each online-implemented operator can be computed by re-walking all the links, and, for each operator, setting its bandwidth to the MIN of all the links in all the paths its data might use.
Online routing would normally be considered to consume one interface address for read and one for write for each direction (up to twelve for a six-neighbor mesh). However, as for bandwidth, online-routing interface addresses can be assigned only where needed by the specific operator(s) implemented with online routing. For example, a stream operator with runtime source and dest on a one-dimensional subset of the network would only need a total of four interface addresses (and only two on the nodes at the ends of the subset). Assigning interface addresses on a per-node basis can thus noticeably reduce interface address pressure.