Summary form only given. We describe an algorithm for partitioning 2-weighted geometric graphs, so that each of the two weights is evenly distributed among all partitions and cutsize is minimal. This algorithm is applicable to load balancing problems in parallel computing, including scientific computation or circuit optimization, in which computational load depends on multiple factors, and geometric proximity needs to be preserved. We first show that for two continuous weight distributions, there always exists an L-shape separator that divides the two weights exactly. Based on this fact, we then give a practical and efficient heuristic for 2/sup p/-way partitioning. Our heuristic relies on recursive bipartitioning and runs in O(nlgn+m2/sup p/) time, where n is the number of vertices and m is the number of rows in the graph. In experiments with geometric graphs obtained from placed benchmark VLSI circuits, our heuristic generates balanced partitions with imbalance no greater than 2%, very short runtimes, and good cutsizes. For example, given a geometric graph with n>100,000, our heuristic computes a 32-way partitioning with 0.46% maximum imbalance within 0.5 second.

Performance analysis of synchronization mechanisms for simple layered task systems has recently been reported. In this paper, we develop and validate performance models for general layered task systems which are applicable to a wider range of synchronization mechanisms and parallel task systems. Synchronization mechanisms considered include both strong (barrier) synchronization and weak (partial) synchronization. The models explicitly consider overheads due to synchronization waiting time and contention for shared software and hardware resources. The models are solvable for a number of commonly used task computation time distributions and are experimentally validated on two different shared-memory multiprocessors. It is shown that the task computation behavior, the amount of intertask dependencies, synchronization overheads, and throughput of the processor-memory interconnection network interact in a multi-dimensional, but predictable, way to impact overall performance. Approximate and asymptotic models are used to demonstrate these relationships, in both qualitative and quantitative terms.

This paper considers the class of parallel computations represented by directed, acyclic task graphs. These include parallel loops, multiphase algorithms, partitioning and merging algorithms, as well as any arbitrary parallel computation that can be structured by a task graph. The paper reviews the current state of the art in stochastic bound models of parallel programs and presents new stochastic bound performance models that predict the expected execution time of parallel programs on a given shared-memory multiprocessor system; and provide qualitative and quantitative description of the relationships between the structure of parallel programs, computation and synchronization behavior of the program, and architectural features of the underlying multiprocessor system.

Performance modeling for the class of parallel computa tions structured as simple layered task systems is consid ered. Specifically studied are the effects of using different forms of inter-layer sequencing mechanisms. The paper refines and generalizes an earlier analytical performance model and presents the results of experimental validation of the model on two different multiprocessor systems. The experimental validation results show that the model is quite accurate, with average prediction errors in the range of only a few percent. Finally, the paper uses the model to investigate performance tradeoff issues for lay ered task systems using barrier versus explicit intertask sequencing mechanisms and implemented on computing systems with differing architectural features. This study shows that the relationship between the type of sequenc ing mechanism, the nature of the computation, and the features of the underlying architecture, interact in com plex ways to impact overall performance. Several inter esting and non-intuitive results are shown.

Heterogeneous parallelism includes all forms of inter-instruction parallelism. This may include both explicitly coded and compiler generated forms. It is argued that support mechanisms are needed to efficiently manage heterogeneous subcomputations at run-time, and that the important issues in the design and implementation of these mechanisms are different from those previously studied for support of loop-level parallelism. An empirical study of an actual application is presented. The study was based on variational recursive dynamics simulation of a typical four wheel vehicle. The results of the empirical study indicate that the choice of an appropriate run-time parallel processing support mechanism can have a dramatic impact upon the ability to successfully extract heterogeneous parallelism for programs. In particular, the efficiency (lack of overhead) of the support mechanisms becomes critically important as the granularity of subcomputations becomes relatively fine. The use of simple, syntactically closed constructs is suggested.>