Contributions of the Research

The primary contribution of this research is demonstrating the effectiveness of a scheduled router on a range of dynamic and multi-phase applications. The results demonstrate its ability to generate better cycle counts for some classes of applications, and similar cycle counts (and thus presumably faster wall-clock time) for other, arbitrary applications. Similarly, the provided results demonstrate that reprogrammable scheduled routing is a relatively general solution for routing. A secondary contribution is the design of a language that expresses the communication requirements of an application, in a way that simultaneously separates communication from computation, yet still provides sufficient semantic information to guide a routing compiler in producing efficient scheduled routing code.

Within this domain, this thesis contributes a variety of specific techniques for reprogrammable scheduled routers that allow for specific functionality or that improve performance.

• A wide variety of approaches for implementing a given communications operator, particularly when the operator involves data-dependent communications.
• An implementation of a virtual online router that allows for arbitrary communications to be issued by the application when absolutely necessary.
• Techniques for managing `continuing operators' extending across multiple phases, without losing data from the continuing operators during phases changes, and without compromising other operators at phase-switch time.
• Algorithms for determining how to switch a node safely from running one phase to running another, without losing data in the current phase.
• Algorithms for determining what times are safe to communicate between nodes, given the possible presence of neighboring nodes that have not changed phases synchronously.
• A model for treating the router as a cache of currently-active scheduling information, handling such issues as optional phases (or phases selected at run time), as well as managing cache placement for groups of resources simultaneously.
• An algorithm for placing router-updating code in the application that allows for nodes uninvolved in a subset to nonetheless support communications for that subset.
• An approach for partitioning a mesh such that different threads of control can run independently, based only on which nodes are included in each communication operator and whether groups of operators are specified as running sequentially or in parallel.
• An algorithm for choosing how to partition a program optimally into communication phases, and simultaneously how to implement each communication operator most effectively.

Using these techniques, two backends for the COP compiler have been implemented, one for traditional dynamic routing and one for a reprogrammable scheduled router (NuMesh). Comparisons of the two backends are presented, examining the performance of the communications generated in each case.

This research does not include two critical components of scheduled routing. The first component is the process used to extract a communication-language program from a high-level language such as Fortran. The second component is the process used to schedule a single phase of static streams on a mesh. The research falls, in a sense, between the two levels, interfacing a high-level language to a low-level scheduling router.