We consider energy minimization by speed-scaling of an open shop multiprocessor with n jobs and m machines. The paper studies the complexity of a primal-dual solution algorithm of [4], which was an open question in that paper. We prove that in a neighbourhood of the solution the complexity of the algorithm is O(mnlog 1/ε) if n ≠ m and e is the round off error of the computer. The paper demonstrates how linearization can be used to investigate the complexity of an algorithm close to the optimum. An estimate of the size of the neighbourhood where the linearization error is smaller than the computer's round off error is also given.

We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. Dhall's effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack - not on deadlines. We prove that if the load on the multiprocessor stays below (3 - radic5)/2 ap 38.197%, the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of- the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%).

Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down the load on these computers must be redistributed to other computers in the cluster. The redistribution is determined by the recovery scheme. The recovery scheme should keep the load as evenly distributed as possible even when the most unfavorable combinations of computers break down, i.e. we want to optimize the worst-case behavior. We define recovery schemes, which are optimal for a larger number of computers down than in previous results. We also show that the problem of finding optimal recovery schemes for a cluster with n computers corresponds to the mathematical problem of finding the longest sequence of positive integers for which the sum of the sequence and the sums of all subsequences modulo n are unique.

Consider a parallel program with n processes and a synchronization granularity z. Consider also two parallel architectures: an SMP with q processors and run-time reallocation of processes to processors, and a distributed system (or cluster) with k processors and no run-time reallocation. There is an inter-processor communication delay of t time units for the system with no run-time reallocation. In this paper, we define a function H(n,k,q,t,z) such that the minimum completion time for all programs with n processes and a granularity z is at most H(n,k,q,t,z) times longer using the system with no reallocation and k processors compared to using the system with q processors and run-time reallocation. We assume optimal allocation and scheduling of processes to processors. The function H(n,k,q,t,z) is optimal in the sense that there is at least one program, with n processes and a granularity z, such that the ratio is exactly H(n,k,q,t,z). We also validate our results using measurements on distributed and multiprocessor Sun/Solaris environments. The function H(n,k,q,t,z) provides important insights regarding the performance implications of the fundamental design decision of whether to allow run-time reallocation of processes or not. These insights can be used when doing the proper cost/benefit trade-offs when designing parallel execution platforms.

For the execution of an arbitrary parallel program P, consisting of a set of processes with any executable interprocess dependency structure, we consider two alternative multiprocessors. The first multiprocessor has q processors and allocates parallel programs dynamically; i.e., processes may be reallocated from one processor to another. The second employs cluster allocation with k clusters and u processors in each cluster: here processes may be reallocatedwithin a cluster only. Let T d (P,q) and T c (P,k,u) be execution times for the parallel program P with optimal allocations. We derive a formula for the program independent performance function $$ G(k,u,q)=\sup_{\mbox{{\footnotesize all parallel programs P}}} \:\frac{T_c(P,k,u)}{T_d(P,q)}. $$ Hence, with optimal allocations, the execution of P can never take more than a factor G(k,u,q) longer time with the second multiprocessor than with the first, and there exist programs showing that the bound is sharp. The supremum is taken over all parallel programs consisting of any number of processes. Overhead for synchronization and reallocation is neglected only. We further present a tight bound which exploits a priori knowledge of the class of parallel programs intended for the multiprocessors, thus resulting in a sharper bound. The function g(n,k,u,q) is the above maximum taken over all parallel programs consisting of n processes. The functions G and g can be used in various ways to obtain tight performance bounds, aiding in multiprocessor architecture decisions.

In this paper we derive a worst case formula comparing the number of cache hits for two different cache memories. From this various other bounds for cache memory performance may be derived. Consider an arbitrary program P which is to be executed on a computer with two alternative cache memories. The first cache is set-associative or direct-mapped. It has k sets and u blocks in each set; this is called a (k,u)-cache. The other is a fully associative cache with q blocks---a (1,q)-cache. We derive an explicit formula for the ratio of the number of cache hits h(P,k,u) for a (k,u)-cache compared to a (1,q)-cache for a worst case program P. We assume that the mappings of the program variables to the cache blocks are optimal. The formula quantifies the ratio $$ \inf_P \frac{h(P,k,u)}{h(P,1,q)}, $$ where the infimum is taken over all programs P with n variables. The formula is a function of the parameters n,k,u, and q only. Note that the quantity $h(P,k,u)$ is NP-hard. We assume the commonly used LRU (least recently used) replacement policy, that each variable can be stored in one memory block, and that each variable is free to be mapped to any set. Since the bound is decreasing in the parameter n, it is an optimal bound for all programs with at most n variables. The formula for cache hits allows us to derive optimal bounds comparing the access times for cache memories. The formula also gives bounds (these are not optimal, however) for any other replacement policy, for direct-mapped versus set-associative caches, and for programs with variables larger than the cache memory blocks.

We present an upper bound on the minimum Euclidean distance d/sub Emin/(C) for block-coded PSK. The bound is an analytic expression depending on the alphabet size q, the block length n, and the number of codewords |C| of the code C. The bound is valid for all block codes with q/spl ges/4 and with medium or high rate-codes where |C|>(q/3)/sup n/. There are several well-known block codes whose d/sub Emin/(C) is equal to our upper bound. Hence these codes are the best possible in the sense that there does not exist a code with the same q, n, and |C| and with a larger d/sub Emin/(C). It also follows that for many choices of q, n, and |C|, in particular for high rates, our upper bound on d/sub Emin/(C) is optimal.

The way the processes in a parallel program are scheduled on the processors of a multiprocessor system affects the performance significantly. Finding a schedule of processes to processors which results in minimum completion time is NP-hard. Therefore, one has to resort to heuristic schedules. However, it is often difficult to determine if a specific schedule is close to the optimal case or if it is worthwhile to look for other schedules. Based on information from previous executions of the parallel program, we present a formula for an upper bound on the minimum completion time of the program. The bound is a function of a set of parameters. Some of these parameters are obtained from the previous executions of the program and the others describe the target multiprocessor architecture for which we want to bound the minimum completion time. The bound is optimal when it is based on information from one previous execution. Using these results, we are able to decide if a certain schedule is close to optimal or if it is worthwhile to look for other schedules. This is demonstrated by evaluating the completion time of a specific schedule of a particular program. The proofs used for obtaining the bound are based on program transformations and combinatorial mathematics.

Consider a multiprocessor with k identical processors, executing parallel programs consisting of n processes. Let $T_{s}(P)$ and $T_{d}(P)$ denote the execution times for the program P with optimal static and dynamic allocations, respectively, i.e., allocations giving minimal execution time. We derive a general and explicit formula for the following maximal execution time ratio: $g(n, k) = \max T_{s}(P)/T_{d}(P)$, where the maximum is taken over all programs P consisting of n processes. Any interprocess dependency structure for the programs P is allowed only by avoiding deadlock. Overhead for synchronization and reallocation is neglected. Basic properties of the function $g(n, k)$ are established, from which we obtain a global description of the function. Plots of $g(n, k)$ are included. The results are obtained by investigating a mathematical formulation. The mathematical tools involved are essentially tools of elementary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to extremal programs. It is mathematically complicated but rapidly computed for reasonable n and k, in contrast to the np-completeness of the problems of finding optimal allocations.

We first consider an MIMD multiprocessor configuration with n processors. A parallel program, consisting of n processes, is executed on this system—one process per processor. The program terminates when all processes are completed. Due to synchronizations, processes may be blocked waiting for events in other processes. Associated with the program is a parallel profile vector v¯, index i (1≤i≤n) in this vector indicates the percentage of the total execution time when i processes are executing.