New methods are presented for bounding and approximating the mean execution time of partitioning algorithm, and these methods are compared to previous approaches. Distribution-driven and program-driven simulations show that two of the methods are usually accurate to within 10% and give good estimates even when certain independence assumptions are violated. Asymptotic approximations and upper bounds are derived for the average execution time of multiphase algorithms when there is no contention for processes in the parallel phase. In addition, the authors bound the average execution time under static and dynamic scheduling policies and determine the optimum number of parallel tasks to be created to minimize the execution time bounds with constant scheduling overhead.>

No abstract available.

The simulation of parallel computers is discussed. In particular, a technique, called cross-profiling, that can be used to improve the efficiency of these simulations substantially is presented and evaluated. Cross-profiling, along with another simulation technique called execution-driven simulation, can be used to simulate one processor's instruction set (the target processor) with another processor that has a different instruction set (the host processor). Moreover, this technique is significantly faster than the usual method where several host instructions are executed to emulate the effect of executing a single instruction of the target processor. The cross-profiling technique is introduced, and it is shown how it can be combined with execution-driven simulation. The results of several experiments that demonstrate that the error introduced by cross-profiling is typically less than 1% are presented.>

Article Free Access Share on The rice parallel processing testbed Authors: R. C. Covington Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , S. Madala Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , V. Mehta Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , J. R. Jump Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile , J. B. Sinclair Rice Univ., Houston, TX Rice Univ., Houston, TXView Profile Authors Info & Claims SIGMETRICS '88: Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systemsMay 1988 Pages 4–11https://doi.org/10.1145/55595.55596Online:01 May 1988Publication History 87citation426DownloadsMetricsTotal Citations87Total Downloads426Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A program whose execution is distributed among several processors in a broadcast system has a total execution cost equal to the sum of processor costs and communication costs, which are functions of the amount of data transmitted and the average transmission delays. A critical delay x is a value of average transmission delay such that no assignment is minimum-cost for average delays both smaller and larger than x. An algorithm is presented for finding the set of all q critical delays of a program that requires computing O(q) optimal assignments at fixed values of average delay. For p=2 processors, H.S. Stone's (1977) assignment graph approach can be used to find an optimal assignment, while for p>2, S.H. Bokhari's (1981) dynamic programming approach for programs with tree-structured calls graphs, or an A* algorithm for the more general case, can be used. When more than one optimal assignment exists, an efficient algorithm is described for finding optimal assignments with minimum channel utilization for p=2 that involves the creation of a compact graphical representation of all optimal assignments of the program. Bokhari's algorithm and the A* algorithm can be easily extended to find optimal assignments with minimum transmission costs when p>2.>