Short List ---------- IPPS94-bandwidth.ps.Z IPPS '94 How to Get Good Performance from the CM-5 Data Network Brewer and Kuszmaul STOC94-scalable.ps.Z STOC '94 Scalable Expanders: Exploiting Hierarchical Random Wiring Brewer, Chong and Leighton TR516-proteus.ps.Z MIT/LCS/TR-516 Proteus: A High-Performance Parallel-Architecture Simulator Brewer, Dellarocas, Colbrook and Weihl TR539-pipes.ps.Z MIT/LCS/TR-539 Pipes: Linguistic Support for Ordered Asynchronous Invocations Colbrook, Brewer, Hsieh, Wang, and Weihl WPDD93-simulation.ps.Z WPDD '93 Developing Parallel Applications Using High-Performance Simulation Brewer and Weihl Abstracts: ---------- IPPS94-bandwidth.ps.Z IPPS '94 How to Get Good Performance from the CM-5 Data Network Eric A. Brewer and Bradley C. Kuszmaul [To appear at the 1994 International Symposium on Parallel Processing] Programmers of the Connection Machine CM-5 data network can improve the performance of their data movement code more than a factor of three by selectively using global barriers, by limiting the rate at which messages are injected into the network, and by managing the order in which they are injected. Barriers eliminate target-processor congestion, and allow the programmer to schedule communications globally. Injection-reordering improves the statistical independence of the various packets in the network at any given time. Barriers and tuned injection rates provide forms of flow control. Barriers also provide a composition of performance property: if you understand the performance of parallel computations $A$ and $B$, then you understand the performance of ``$A$; barrier; $B$''. Architectural support for global barriers, injection reordering, and flow control may be worthwhile for achieving good communications performance. Although our evidence comes from the CM-5, we expect these techniques to apply to most parallel machines. STOC94-scalable.ps.Z Scalable Expanders: Exploiting Hierarchical Random Wiring Eric A. Brewer, Frederic T. Chong, and F. Thomson Leighton [To appear at the 1994 Symposium on the Theory of Computing] Recent work has shown many advantages to randomly wired expander-based networks. Unfortunately, the wiring complexity of such networks becomes physically problematic as they become large. This paper introduces a technique for scaling expanders that avoids this wiring complexity. Specifically, we make the following contributions: 1) We introduce HIERARCHICAL EXPANDERS, a method of scaling small expanders to larger ones while maintaining practical physical construction. We present an example of such a scalable network, called the METABUTTERFLY, which is scaled from the randomly wired multibutterfly. 2) We present a proof that we can scale any (a, B, M, N)- expander with aM >= 1 into an (a', B', kM, kN)- expander, for any k, with probability at least 1 - 2e^(-aM), where a' = (a^2)/(B^2 e^4 + 4a) and B' = B - 2. 3) We present empirical evidence that the performance and fault tolerance of metabutterflies equals that of traditional randomly wired multibutterflies, despite the greatly simplified wiring of the metabutterfly. TR516-proteus.ps.Z Proteus: A High-Performance Parallel-Architecture Simulator Eric A. Brewer, Chrysanthos N. Dellarocas, Adrian Colbrook, William E. Weihl Proteus is a high-performance simulator for MIMD multiprocessors. It is fast, accurate, and flexible: it is one to two orders of magnitude faster than comparable simulators, it can reproduce results from real multiprocessors, and it is easily configured to simulate a wide range of architectures. Proteus provides a modular structure that simplifies customization and independent replacement of parts of architecture. There are typically multiple implementations of each module that provide different combinations of accuracy and performance; users pay for accuracy only when and where they need it. Finally, Proteus provides repeatability, nonintrusive monitoring and debugging, and integrated graphical output, which result in a development environment superior to those available on real multiprocessors. Keywords: Execution-driven simulation, parallel algorithm design and evaluation, parallel architecture, parallel debugging TR539-pipes.ps.Z Pipes: Linguistic Support for Ordered Asynchronous Invocations Adrian Colbrook, Eric A. Brewer, Wilson C. Hsieh, Paul Wang, William E. Weihl We describe pipes, a new linguistic mechanism for sequences of ordered asynchronous procedure calls in multiprocessor systems. Pipes allow a sequence of remote invocations to be performed in order, but asynchronously with respect to the calling thread. Using pipes results in programs that are easier to understand and debug than those with explicit synchronization between asynchronous invocations. The semantics of pipes make no assumptions about the underlying architecture, which enhances code portability. However, the implementation of pipes by the language compiler can be optimized so as to take advantage of any underlying message ordering a particular architecture may provide. Pipes also provide application-transparent flow control for asynchronous invocations and are able to throttle invocations from multiple calling threads. We present four implementations of pipes and show that the performance and space overheads associated with pipes are low. Keywords: linguistic mechanism, ordered asynchronous invocations, serialization, message-layer implementation, flow control. WPDD93-simulation.ps.Z Developing Parallel Applications Using High-Performance Simulation Eric A. Brewer and William E. Weihl Researchers already use high-performance simulators for algorithm development and architectural studies. Advances in simulation technology and workstation performance have made program development on top of simulators --- debugging, testing, and some tuning --- fast enough for real applications. Simulators provide many advantages over running directly on a multiprocessor, including versatility, trivial repeatability, and detailed nonintrusive data collection and debugging. We make the case for application development via simulation and address simulation's traditional disadvantages. We also propose a development methodology that integrates simulation into the multiprocessor development environment. Finally, we examine the software engineering issues required by this integration and the use of parallel simulators for development.