We present work that extends our previous Myrinet port for LAM/MPI, MPI-NP, with collective communication primitives on the NIC. This work is another step in our experiment of making the NIC MPI aware. We believe that an MPI aware control program on the NIC can deliver a richer set of performance enhancements, not just restricted to better bandwidth/latency, to MPI applications. MPI collective communication involves considerable interactions between the communication subsystems of the nodes that are not of any direct interest to the application. By migrating these talkative components to the Myrinet network interface card we allow this dialog between the nodes to happen with minimum latency. We explore the advantage of supporting several MPI collective communication routines on the NIC. These include MPI /spl I.bar/Bcast (), MPI/spl I.bar/Barrier and MPI/spl I.bar/Comm/spl I.bar/Create ().

MPI-NP II is a network processor based message manager for MPI. The objectives of MPI-NP II were to reduce host processing and to make use of the processor on the network interface board to do message scheduling and message matching. The design of MPI-NP II is based on microchannels and message rendezvous. MPI-NP II implements MPI nonblocking communication as asynchronous communication and is able to overlap computation with communication. We introduce the concept of k.safe programs to guarantee message delivery based on the available envelope resources independent of the message size. We achieve these benefits without unduly burdening the NIC processor. We obtain a latency of 22 microseconds and a bandwidth of 92 MB/s, which is comparable to other Myrinet MPI implementations that perform MPI message management on the host.

In this paper, we investigate the approach of using low cost PC cluster to parallelize the computation of iceberg-cube queries. We concentrate on techniques directed towards online querying of large, high-dimensional datasets where it is assumed that the total cube has net been precomputed. The algorithmic space we explore considers trade-offs between parallelism, computation and I/0. Our main contribution is the development and a comprehensive evaluation of various novel, parallel algorithms. Specifically: (1) Algorithm RP is a straightforward parallel version of BUC [BR99]; (2) Algorithm BPP attempts to reduce I/0 by outputting results in a more efficient way; (3) Algorithm ASL, which maintains cells in a cuboid in a skiplist, is designed to put the utmost priority on load balancing; and (4) alternatively, Algorithm PT load-balances by using binary partitioning to divide the cube lattice as evenly as possible.

In this paper, we describe the design, implementation, and modeling of a runtime kernel to support the processor farm paradigm on multicomputers. We present a general topology-independent framework for obtaining performance models to predict the performance of the start-up, steady-state, and wind-down phases of a processor farm. An algorithm is described, which for any interconnection network determines a tree-structured subnetwork that optimizes farm performance. The analysis technique is applied to the important case of k-ary tree topologies. The models are compared with the measured performance on a variety of topologies using both constant and varied task sizes.

Abstract The paper describes a new performance monitoring tool, calledTmon, that has been developed to help application programmers understand the run‐time behavior of a parallel system and tune the performance of their programs. Tmon measures resource utilization and traces process activities transparently during execution. A global interrupt technique used by Tmon allows measurement tasks to be executed simultaneously on different processors and an accurate global clock to be maintained with minimal overhead. Experimental results indicate that both the accuracy and the overhead of the monitor are well within an acceptable range. We introduce a performance model from which it is possible to derive several different parallel programming metrics. A weighted critical path analysis tool is also presented that focusses the user's attention on those parts of the program whose modification would most improve performance. An example in which the tool is used successfully to improve the performance of a parallel application is also presented. Tmon is currently implemented on top of the Trollius Operating System and runs on a 74‐node transputer‐based multicomputer.

An efficient execution model for tree structured computations is presented. A general framework for analyzing the performance of this type of computation for any given topology is discussed. The framework is used to derive models for two widely used parallel programming strategies: processor farms and divide and conquer. The models were validated on a large multicomputer, and it was shown that their accuracy is such that they can be used to predict the performance of applications that use the above strategies. The use of these models to evaluate performance and to restructure the application to improve performance is discussed.>