Efficient communications from fine-grain distributed computers

One of the most important contemporary issues in concurrent computing is network performance, for without efficient communications the benefits of concurrency are severely limited. Inter-processor communication latency must be reduced to levels at least comparable with fine-grained task execution times, and yet, as more concurrency is exploited in applications, tasks naturally become shorter, and, to support more processors, networks become larger. The role of the communication network in concurrent machines is fundamental, and the highest possible performance is essential. This thesis is solely concerned with optimizing network performance. The approach taken is simple; to reduce network latency to an absolute minimum all unnecessary constraints on data movement must be removed. Three new concepts are introduced which together form an approach to designing networks that comes close to this ideal. The mad postman routing strategy allows packets of data to propagate through a network at the fastest possible physical rate, with negligible overheads. Virtual Networks enable any shortest path to be taken through a network whilst still avoiding the possibility of deadlock, and, finally, the data-driven model of routing provides a basis from which to construct networks supporting all forms of concurrent communications, rather than solely point-to-point routing. Simulation results are presented that show conclusively the significant benefits to be gained from this approach, and details are given of a semi-custom VLSI routing chip that embodies many of the concepts discussed and developed. In addition to point-to-pointrouting, broadcasting and multi-stage piggy-backing are also fully supported in this prototype as fundamental routing operations. A 1024 two-dimensional mesh network built from this component can maintain a constant network load of 1024 randomly-addressed, two-byte messages, with an average message latency of around 2.5μs. A more state-of-the-art implementation could reduce this figure to well below 1μs.