Summary Measuring execution time is one of the most used performance evaluation techniques in computer science research. Inaccurate measurements cannot be used for a fair performance comparison between programs. Despite the prevalence of its use, the intrinsic variability in the time measurement makes it hard to obtain repeatable and accurate timing results of a program running on an operating system. We propose a novel execution time measurement protocol (termed EMP) for measuring the execution time of a compute‐bound program on Linux, while minimizing that measurement's variability. During the development of execution time measurement protocol, we identified several factors that disturb execution time measurement. We introduce successive refinements to the protocol by addressing each of these factors, in concert, reducing variability by more than an order of magnitude. We also introduce a new visualization technique, what we term ‘dual‐execution scatter plot’ that highlights infrequent, long‐running daemons, differentiating them from frequent and/or short‐running daemons. Our empirical results show that the proposed protocol successfully achieves three major aspects—precision, accuracy, and scalability—in execution time measurement that can work for open‐source and proprietary software. Copyright © 2017 John Wiley & Sons, Ltd.

This paper studies the effects of overheads in massively parallel processing. The execution times for tasks on individual processors are modeled as independent and identically but arbitrarily distributed random variables. The time to execute a process fork is assumed to be distributed exponentially. The main result bounds (in expectation) the overhead time in forking a large number of tasks across n machines and then waiting for the join event. The model used is appropriate for massive parallelism (when n is large): in fact, the bound serves as a heavy traffic limit approached as n→ ∞ and for task times that are large in comparison to the time to execute a fork. In this model, the expected total time to reach the final join consists of a forking overhead that grows linearly with the number of processors n, a time for parallel execution of tasks that decreases in n, and finally a synchronization delay that is a concave sublinear function of ρ = EX/EA, which is the ratio of expected task time to the expected time needed to fork a new process. This overhead function is typically no worse than o(ρ). An interesting aspect of the analysis is that the original problem reduces to a previously studied problem in queueing theory: estimating total end-to-end delay in an infinite-server resequencing system. The new results thus provide new bounds and heavy-traffic approximations (in distribution and in expectation) for the theory of M/GI/∞ resequencing queues. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Suppose m stochastically identical iterative processes are run in parallel. Each iteration of the process runs for a random time X, distributed identically and independently for each iteration. At the end of each iteration, each process checks a shared variable to see whether some global event has occurred; if it has, the process terminates and instantly joins a rendezvous with the other processes that have detected the event. The synchronization overhead is the time R(m)(t) needed to complete the rendezvous, measured from the time t of occurrence of the event (t is assumed to be independent of the m processes). It is not true (for general X) that ER(m)(t)≤EX, because t will more probably occur during a long iteration than a short one, and because R(m)(t) is an extreme value of a sample of size m. In renewal theory the random variable R(1)(t) is called the excess at t, and R(m)(t) will be the extreme of m i.i.d. excesses. While exact expressions for ER(m)(t) are impossible to obtain in practice, we give useful upper bounds. The bounds get tighter depending on information known about the underlying distribution of X. Results include: (1) a general bound valid for any X having finite third moment, (2) a better bound valid if X is dominated by an exponential in stochastic variability ordering, (3) an even better bound if X has bounded mean residual life, and (4) a bound valid when X has decreasing failure rate. The results are applied to searching a table in parallel and to on-line makespan scheduling. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The problem of scheduling tasks on m processors to minimize the schedule length (makespan) is NP-complete. Here we study the behavior of list schedules under the assumptions that there are no task precedence constraints and that task times are chosen from a uniform distribution. We show that, given a desired degree of confidence $1 - \varepsilon $, we can find a minimum sample size N such that if $n \geqq N$ and the n task times $\bar X = (X_1 , \cdots ,X_n )$ are chosen from any uniform distribution, then \[ {\bf P}\left[ {\frac{{L(\bar X)}}{{{\operatorname{OPT}}(\bar X)}} < 1 + \frac{{4(m - 1)}}{n}} \right] > 1 - \varepsilon \] where $L(\bar X)$ is the length of any list schedule and ${\operatorname{OPT}}(\bar X)$ is the length of the optimal schedule. Thus for n sufficiently large, the performance of any list schedule can be made arbitrarily close to that of the optimal policy with any desired degree of confidence. For example, for $m = 2$ and $\varepsilon = 0.01$, the ratio is bounded by 1.11 when $n = 36$ and bounded by 1.03 when $n = 100$.

Distributed systems make possible both a high degree of concurrency and robustness in the face of failure. One approach to achieving these goals is to employ pools of servers implementing major system functions. This paper describes the concept of pools of servers, and presents logically distributed, robust algorithms for one problem arising in this approach: the allocation of servers to clients. Three types of allocation problems are identified: free servers, preferred servers, and retentive servers. Allocation protocols based upon the idea of hash addressing are described and analyzed.

The problems of minimizing the expected makespan and minimizing the expected tic for a finite set of independent tasks with exponential service-time distributions on m ~ 2 it processors are considered.It is shown that a scheduling policy minimizes the expected flow timq only if it is shortest expected processing time tint, and that a policy minimizes the expected make and only if it is longest expected processing time fast.

Consider an m-processor distributed system having both local node and network traffic. Because users have incomplete information about the state of the queues at remote nodes, they can be tempted to shorten the expected completion time of a job by running multiple incarnations of each task in parallel on all m processors. To assess the temptation of such a “user countermeasure,” a job consisting of a sequence of n tasks to be performed sequentially is considered. Under simple assumptions about execution and network times, users can cut their expected job completion time by a factor of the square root of m. The implications of such user countermeasures on system design are discussed.

Given a sequence $n_1 , \cdots ,n_m $ of positive integers, what is the smallest number of additions needed to compute all m integers starting with 1? This generalization of the addition chain ($m = 1$) problem will be called the addition-sequence problem. We show that the sequence $\{ 2^0 ,2^1 , \cdots ,2^{n - 1} ,2^n - 1\} $ can be computed with $n + 2.13\sqrt n + \log n$ additions, and that $n + \sqrt n - 2$ is a lower bound. This lower bound result is applied to show that the addition-sequence problem is NP-complete.

Let G be a directed graph such that for each vertex v in G, the successors of v are ordered Let C be any equivalence relation on the vertices of G.The congruence closure C* of C is the finest equivalence relation containing C and such that any two vertices having corresponding successors equivalent under C* are themselves equivalent under C* Efficient algorithms are described for computing congruence closures in the general case and in the following two special cases.0) G under C* is acyclic, and (it) G is acychc and C identifies a single pair of vertices.The use of these algorithms to test expression eqmvalence (a problem central to program verification) and to test losslessness of joins in relational databases is described KEY WORDS AND PHRASES common subexpresslon, congruence closure, decision procedure, expression equivalence, graph algorithm, lossless join, relational database, theory of equality, unification, uniform word problem CR CATEGORIES 4 12, 4.33, 4 34, 5.24, 5 25, 5 32

The classical common subexpression problem in program optimization is the detection of identical subexpressions. Suppose we have some extra information and are given pairs of expressions ei1=ei2 which must have the same value, and expressions fj1≠fj2 which must have different values. We ask if as a result, h1=h2, or h1≠h2. This has been called the uniform word problem for finitely presented algebras, and has application in theorem-proving and code optimization. We show that such questions can be answered in O(nlogn) time, where n is the number of nodes in a graph representation of all relevant expressions. A linear time algorithm for detecting common subexpressions is derived. Algorithms which process equalities, inequalities and deductions on-line are discussed.

Stratght line programs with assignment statements involving both simple and array variables are considered Two such programs are equivalent if they compute the same values as a function of the inputs.Testing the equivalence of array programs ts shown to be NP-hard If array variables are updated but never subsequently referenced, equivalence can be tested in polynomial time Programs without array varmbles can be tested for equivalence in expected linear t~me

In this paper we consider the problem of sequencing classes of tasks with deadlines in which there is a set-up time or a changeover cost associated with switching from tasks in one class to another. We consider the case of a single machine and our results delineate the borderline between polynomial-solvable and $NP$-complete versions of the problem. This is accomplished by giving polynomial time reductions, pseudo-polynomial time algorithms and polynomial time algorithms for various restricted cases of these problems.

Straight line programs in which array elements can be referenced and set are considered. Two programs are equivalent if they compute the same expression as a function of the inputs. Testing the equivalence of programs with arrays is shown to be NP-complete, while programs without arrays can be tested for equivalence in linear time. Equivalence testing takes polynomial time when programs have either no references or no assignments to array elements.

This paper considers simple, LISP-like languages for the recursive definition of functions. We focus on the connections between formal computation rules for calculation with recursive definitions, and the mathematical semantics of such definitions. A computation rule is correct when it is capable of computing the least fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.

This paper considers simple LISP-like languages for the recursive definition of functions, focusing upon the connections between formal computation rules for calculation and the mathematical semantics of recursive definitions. A computation rule is correct when it is capable of computing the minimal fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.