Drawbacks to Scheduled Routing

  Unfortunately, scheduled routing is not a panacea, and some applications will be unlikely to benefit from simple scheduled routing.

High-bandwidth applications that require primarily short-lived, highly-dynamic communications are not well-suited to scheduled routing. All three qualifiers are important to this limitation, however:

• When applications are low-bandwidth, it is easy to create multiple streams at compile time and choose among them at run time.
• When the connections are long-lived, extra setup time can be expended to create appropriate routing schedules and still benefit from high cycle speeds and low contention.
• Lastly, when communications are constant, or data-dependent in a structured manner, the scheduled router can support them directly at full speed.

Only when all of the above qualifiers are true does communication using scheduled routing become slower than dynamic routing; in this case scheduled routing must use a form of dynamic routing, as discussed in Section 4.2.

Applications with little or no compile-time knowledge of the order of communications are problematic in the same way as applications with short-lived dynamic communications. The notion of communication phases is dependent on being able to separate communications into sets, each with some temporal locality. If an application has a large number of possible communication streams, the result is much like the application with short-lived dynamic communications, just expressed somewhat differently.

While the thesis explicitly ignores the issue of converting high-level language inputs into structured communications, this process can be either helped or hindered by the choice of high-level language. Some languages, such as HPF [46] or Crystal [15], provide high-level communications operators; these operators easily allow for suitable communication schedules to be generated. Other languages, such as Mul-T [38] and Linda [14], have less emphasis on high-level operations and are harder to extract structured communications from.

For languages with lower-level primitives, the burden falls to the compiler to extract the necessary structured communications. As discussed above, if the compiler can only find short-lived, highly-dynamic communications in the language, the performance on a scheduled router will suffer. If the code only contains send and receive operations, or fork and join, the compiler must be relatively sophisticated to ascertain such things as a broadcast from a run-time source or a reduction.

One way to handle the problem of applications with dynamic communication characteristics is to include dynamic-routing hardware in the scheduled router. Doing so allows the compiler to schedule a certain amount of bandwidth to devote to dynamic routing; effectively, adding such support allows the hardware to support scheduled routing and dynamic routing both.