Umut A Acar

Arthur Charguéraud
email: arthur.chargueraud@inria.fr

Mike Rainey
email: mike.rainey@inria.fr

Acar

Charguéraud

Rainey

Oracle-Guided Scheduling for Controlling Granularity in Implicitly Parallel Languages

Keywords:

A classic problem in parallel computing is determining whether to execute a thread in parallel or sequentially. If small threads are executed in parallel, the overheads due to thread creation can overwhelm the benefits of parallelism, resulting in suboptimal efficiency and performance. If large threads are executed sequentially, processors may spin idle, resulting again in suboptimal efficiency and performance. This "granularity problem" is especially important in implicitly parallel languages, where the programmer expresses all potential for parallelism, leaving it to the system to exploit parallelism by creating threads as necessary. Although this problem has been identified as an important problem, it is not well understood-broadly applicable solutions remain elusive.

In this paper, we propose techniques for automatically controlling granularity in implicitly parallel programming languages to achieve parallel efficiency and performance. To this end, we first extend a classic result, Brent's theorem (a.k.a. the work-time principle) to include thread-creation overheads. Using a cost semantics for a general-purpose language in the style of lambda calculus with parallel tuples, we then present a precise accounting of thread-creation overheads and bound their impact on efficiency and performance. To reduce such overheads, we propose an oracle-guided semantics by using estimates of the sizes of parallel threads. We show that, if the oracle provides accurate estimates in constant time, then the oracle-guided semantics reduces the thread-creation overheads for a reasonably large class of parallel computations.

We describe how to approximate the oracle-guided semantics in practice by combining static and dynamic techniques. We require the programmer to provide the asymptotic complexity cost for each parallel thread and use runtime profiling to determine hardware-specific constant factors. We present an implementation the proposed approach as an extension of the Manticore compiler for Parallel ML. Our empirical evaluation shows that our techniques can reduce thread-creation overheads, leading to good efficiency and performance.

Introduction

Explicitly threaded programming provides full control over parallelism resources by offering primitives for creating, scheduling, and synchronizing parallel threads. As a result, the programmer can write efficient parallel programs by performing a careful cost-benefit analysis to determine which threads should be executed in parallel and under what conditions. This approach, however, requires reasoning about low-level execution details, such the effects of scheduling, data races or concurrent effects, which is known to be notoriously hard. In addition, such low-level programming can lead to over-engineering of software and harm portability. For example, the resulting code may perform well on a particular hardware setting but not on others.

The complexities of programming with explicitly threaded languages have motivated interest in implicitly threaded or implicitly parallel languages, such as Multilisp [START_REF] Halstead | Multilisp: a language for concurrent symbolic computation[END_REF], NESL [START_REF] Blelloch | Implementation of a portable nested data-parallel language[END_REF], Cilk [START_REF] Blumofe | Scheduling multithreaded computations by work stealing[END_REF], Parallel Haskell [START_REF] Chakravarty | Data parallel Haskell: a status report[END_REF]Peyton Jones et al., 2008), Parallel ML in Manticore [START_REF] Fluet | A scheduling framework for generalpurpose parallel languages[END_REF][START_REF] Fluet | Implicitly threaded parallelism in Manticore[END_REF] and in MultiMlton [START_REF] Sivaramakrishnan | Multimlton: A multicoreaware runtime for standard ml[END_REF]. In explicit threading, all programs accept a sequential (serial) semantics. It is the responsibility of the run-time system of the programming language to fulfill the intended semantics by creating and scheduling threads as needed. Implicit threading can therefore simplify writing parallel programs significantly. For example, the programmer can express parallelism at a high level by using parallel versions of a variety of serial data types such as sequences, arrays, and tuples.

As an implicit parallel program executes, it exposes opportunities for parallelism. The language run-time system exploits the potential for parallelism by creating lightweight threads (variously called tasks, strands, fibers etc.) as needed and by mapping them to the processors or cores for fast execution. To achieve efficiency, implicit programming languages rely on a scheduler for distributing threads among the processors to perform load balancing. Many scheduling techniques and practical schedulers have been developed, including work-stealing schedulers (e.g., [START_REF] Blumofe | Scheduling multithreaded computations by work stealing[END_REF]), and depth-firstsearch schedulers [START_REF] Blelloch | A provable time and space efficient implementation of NESL[END_REF].

Experience with implicitly parallel programs shows that one of the most important decisions that any implicitly parallel language must make is determining whether to exploit an opportunity for parallelism by creating a parallel thread or to forgo the opportunity by falling back to sequential execution. On the one hand, creating a thread for each parallelism opportunity can lead to poor efficiency, because the cost of creating and managing parallel threads can be very high. On the other hand, foregoing a parallelism opportunity can lead to suboptimal performance because of the lost opportunity for parallelization of a large chunk of work. Therefore, solving this dilemma requires finding just the right "sweet spot", where no more than necessary threads are created to achieve the best performance. This granularity problem is important because the overhead of managing parallelism matters: since the speedups achievable via parallel computation is bounded by the number of processors, often a small constant factor, any increase in the overhead can impact performance negatively.

Even though the granularity problem is broadly accepted to be an important problem, it is a poorly understood one. Theoretical analyses often ignore thread-creation overheads, Oracle-Guided Scheduling 3 offering no significant clues about how such overheads may affect efficiency. Practical implementations often focus on reducing thread-creation overheads, instead of controlling granularity so that fewer threads can be created without harming parallelism. As a result, practitioners try to solve the granularity problem by estimating the amount of work that would be sufficiently large to justify parallel execution. More specifically, programmers try to determine the input sizes at which threads become too small to amortize the cost of parallel thread creation and sequentialize such threads. Since the running time of a thread depends on the hardware, the programmer must make the best decision they can by taking into account the specifics of the hardware. This manual granularity control is thus bound to yield code whose performance is specific to the hardware and therefore likely not portable [START_REF] Tzannes | Lazy scheduling: A runtime adaptive scheduler for declarative parallelism[END_REF].

In this paper, we propose theoretical and practical techniques for solving the granularity problem in implicitly parallel programming languages. First, we present theorems that take into account thread-creation overheads and characterize their impact on parallel run time.

Our theorems show such impact to be significant (Section 4). We then consider a cost semantics for a calculus that extends the lambda calculus with parallel tuples (Section 5) and propose a technique for controlling granularity based on an oracle (Section 6). We show that if the oracle can be implemented efficiently and accurately, it can be used to improve efficiency for a relatively large class of computations.

Based on this result, we propose a practical realization of the oracle that uses complexity functions defined by the user to approximate accurately the work of the computations involved (Section 7). We then describe a compilation scheme for implementing the oracleguided semantics based on such complexity functions (Section 8). We present an evaluation of the proposed approach on a subset of ML extended with parallel tuples and complexity annotations (Section 9). We conclude with a discussion of the limitations of our implementation of the oracle based on complexity functions (Section 11).

Overview

We present a high-level overview of our the techniques proposed in this paper.

Brent's theorem [START_REF] Brent | The parallel evaluation of general arithmetic expressions[END_REF], which leads to the work-time scheduling principle, characterizes arguably the most important property of parallel programs: that they can be scheduled to execute efficiently with multiple processors-within a factor of two of the optimal. More precisely, Brent shows that a level-by-level schedule can execute a parallel computation with w work and s span in no more than w/P + s steps on P processors. This theorem generalizes to any greedy schedule, that is, any schedule that never leaves processors idle when there is work to do. Prior research shows that greedy schedules can be computed by online scheduling algorithms such as the work-stealing algorithm (e.g., [START_REF] Blumofe | Scheduling multithreaded computations by work stealing[END_REF]) under modest assumptions.

The work-time scheduling principle ignores an important factor: the overhead for creating threads or parallelism, which is assumed to be zero. To understand the impact of thread-creation overheads, we start with this fundamental theorem and generalize it to take the overheads into account (Section 4). Specifically, we consider the standard directedacyclic-graph (DAG) mode for parallel computations and show that a computation with total work W and total span S, where both include the thread-creation overheads, can be executed in no more than W/P + S steps. What is somewhat special about thread-creation overheads are that they are not divisible. Nevertheless, the generalized theorem follows by a modest extension of an existing proof.

Having established the contribution of thread-creation overheads to parallel run time, we then move on to the problem of determining precisely the overheads of thread creation in implicitly parallel programs. To this end, we consider a lambda calculus with parallel tuples and present a cost-semantics for evaluating expression of this language (Section 5). The cost semantics yield raw work/span and total work/span of each evaluated expression. Using this cost semantics, we show that thread-creation overheads can be significant: a multiplicative factor times the raw work. When applied to the generalized Brent's theorem, this result implies that such multiplicative increases in work affect the parallel run-time directly. To reduce thread-creation overheads, we propose an alternative oracle-guided semantics that captures a known principle for avoiding the thread-creation overheads: for a thread, create a parallel thread and evaluate it in parallel only if the thread is sufficiently large, i.e., greater than some constant κ. We show that the oracle semantics can decrease the overheads of thread-creation by any (desired) constant factor κ, but only at the cost of increasing the total span by a similar factor. This result suggests that in practice some care will be needed to select κ, because otherwise it can reduce an important quantity called parallel slackness [START_REF] Valiant | A bridging model for parallel computation[END_REF].

The bounds with the oracle-guided semantics suggest that we can reduce the threadcreation overheads significantly, if we can realize the semantics in practice. Such a realization is impossible, unfortunately, because it requires the ability to determine a priori the running time of a thread and do so without incurring other overheads. We show, however, that a realistic oracle that can give constant-factor approximations to the thread running times can still result in similar reductions in the overheads for a reasonably broad class of computations (Section 6.2). We also show that, unless care is taken, the realistic oracle can actually further increase the overheads, due to the direct cost of evaluating the oracle. This outcome, i.e., that attempts at controlling the granularity can actually backfire and slow down the program further, is an interesting outcome of our analysis. For a broad class of computations, including many recursive, divide-and-conquer computations, we show that this worst case can be avoided.

While the oracle-guided semantics is effective in controlling the cost of thread creation without detrimentally harming parallelism, it is technically impossible to realize in practice because it requires predicting the work (sequential run-time) of computations. As we describe in Section 7, however, the work to be performed by a given thread can be approximated by using a combination of static and dynamic information. Specifically, we describe an approximation technique that relies on an estimator that uses asymptotic cost functions (asymptotic complex bounds) and judicious use of run-time profiling techniques to estimate actual run-times accurately and efficiently. This approach combines data from the asymptotic complexity bounds and the profiling techniques to approximate the work to be performed by a given thread. In this work, we only consider simple recursive functions for which the execution time is proportional to the value obtained by evaluating the asymptotic complexity expression. We refer to Section 11 for discussion of more general patterns. Oracle-Guided Scheduling

5

We present a prototype implementation of the proposed approach (Section 8) by extending the ML to support parallel tuples, and complexity functions, and translating programs written in this extended language to the PML (Parallel ML) language [START_REF] Fluet | Implicitly threaded parallelism in Manticore[END_REF]. Although our implementation requires the programmer to enter the complexity information, these could also be inferred in some cases cases via static analysis (e.g., [START_REF] Jost | Static determination of quantitative resource usage for higher-order programs[END_REF] and references thereof). We extend the Manticore compiler for PML to support oracle-guided scheduling and use it to compile generated PML programs. Our experiments (Section 9) show that our oracle implementation can reduce the overheads of a single processor parallel execution to 3 and 13 percent of the sequential time. When using 16 processors, we achieve 7-to 15-fold speedups on our benchmark machine.

Terminology

In this paper, we consider implicitly parallel programs, where a program executes by employing two kinds of threads: system-level threads and user-level threads. An execution creates one system-level thread per processor and usually pins the system-level thread to that processor. It then dynamically creates lighter-weight, user-level threads and maps them to the system-level threads. A key property of implicitly parallel programs is that the number of user-level threads created during an execution can be very large relative to the number of system-level threads. For example, an execution may create millions of userlevel threads mapped to 10 system-level threads, which are then mapped to 10 processors or cores by the system. For the purpose of succinctness, throughout the paper, we refer to "user-level threads" simply as "threads" and to "system-level threads" as "processes."1 4 Generalizing Brent's Theorem

We represent a parallel computation with a directed acyclic graph (dag), called computation dag. Vertices in the dag represent atomic computations, or operations. For simplicity, we refer to each vertex as an operation. Edges between operations represent precedence relations, in the sense that an edge from u to v indicates that the execution of u must be completed before the execution of v can start. Every computation dag includes a source operation and a sink operation, representing the starting and the end points of the computation, respectively. All operations of a computation dag are reachable from the source, and the sink is reachable from all operations. An example computation dag appears in Figure 1.

Traditionally, every operation in the dag is considered to take a single unit of time and given a weight of 1. In this setting, we can define the standard notion of work and span, which we here call raw work and raw span. The raw work of a computation graph is equal to the total number of operations that it contains. The raw span of the computation dag is equal to the total number of operations along the longest path. Brent proved the following bound, which we recall since our aim is to generalize it.

Proof

Consider scheduling the operations level-by-level, that is, starting with operations at depth 1, then executing operations at depth 2, and so on, ending with operations at depth s. Let w i denote the number of operations at depth i in the dag. These operations can be scheduled on P processors in w i P rounds, each lasting exactly one unit of time. Summing up over all the possible depths, we deduce that the total execution time is bounded by:

s ∑ i=1 w i P ≤ s ∑ i=1 w i P + 1 ≤ ∑ s i=1 w i P + s ≤ w p + s.
Observe that the optimal execution time cannot be less than w P , which corresponds to having all processors busy at all time, and that it cannot be less than s, which corresponds to the length of a critical path. Therefore, Brent's bound, expressed as w p + s, is never more than a factor 2 away from the optimal.

Brent's theorem does not take into account the overheads associated with thread creation. Our goal is to refine the model and generalize Brent's theorem to take thread-creation costs into account. To that end, we assign to each operation with out-degree two or greater a weight of 1 + τ instead of just 1. We then define the total work as the sum of the weights of all the operations in this revised computation dag. Similarly, we define the total span as the maximum weight of a path from the source to the sink in the revised dag.

Theorem 4.2 generalizes Brent's theorem for weighted dags and arbitrary greedy schedules (rather that level-by-level schedules). The proof is a relatively straightforward generalization of that of Arora et al [START_REF] Arora | Thread scheduling for multiprogrammed multiprocessors[END_REF]. Oracle-Guided Scheduling Consider any greedy execution of the dag G. At each execution step, each processor places a token in the work bucket if it is busy at this step, otherwise it places a token in the idle bucket. The work bucket contains exactly W tokens at the end of the execution. Let I denote the number of tokens contained in the idle bucket at the end of the execution, and let T denote the total number of steps in the execution. Because a total T P tokens are created during the T execution steps, T P = W + I. In order to establish the result T ≤ W P + S, it thus suffices to establish the inequality I ≤ P S.

7 v ::= x | n | (v, v) | inl v | inr v | fun f .x.e e ::= v | let x = e 1 in e 2 | (v v) | fst v | snd v | case v of {inl x.
Consider a given time step. If all processors execute an operation at that step then the idle bucket receives zero tokens. Otherwise, a number of processors are idle. In this case, the idle bucket receives between one and P -1 tokens. If one or more processors are idle, then the idle processors cannot find a ready operation to execute, because otherwise this schedule would not be a greedy schedule. It follows that, at this step, all the ready operations (operations whose ancestor have been executed) are executed. Therefore, at such a time step, the span of the sub-dag induced by the operations that are not yet executed decreases by one. Therefore, there are at most S such steps and thus (P -1) S tokens in the idle bucket.

Source Language and Cost Semantics

To give an accurate account of the cost of thread creation, and to specify later our compilation strategy, we consider a source language in the style of λ -calculus and present a dynamic cost semantics for it. The semantics and the costs are parameterized by τ and φ that represent the cost of creating a parallel thread and the cost of consulting an external oracle.

Syntax

The source language includes recursive functions, pairs, sum types, and parallel tuples. Parallel tuples enable expressing computations or branches that can be performed in parallel, similar to the fork-join or nested data parallel computations. More precisely, in (|e 1 , e 2 |), we refer to e 1 and e 2 as (parallel) branches. We note that although we only consider parallel tuples of arity two, our results generalize to fixed (constant) arity trivially.

To streamline the presentation, we assume programs to be in A-normal form, with the exception of pairs and parallel pairs, which we treat symmetrically because our compilation strategy involves translating parallel pairs to sequential pairs. Figure 2 illustrates the abstract syntax of the source language. We note that, even though the presentation is only concerned with a purely-functional language, it is easy to add local mutable state (i.e. mutable memory cells that are not subject to concurrent accesses); in this case, however, they contribute no additional insight and thus are omitted for clarity.

Dynamic Cost Semantics

We define a dynamic semantics where parallel tuples are evaluated selectively either in parallel or sequentially, as determined by their relative size compared with some constant κ, called the cutoff value and such that κ ≥ 1. To model this behavior, we present an evaluation semantics that is parameterized by an identifier that determines the mode of execution, i.e., sequential or not. For the purpose of comparison, we also define a (fully) parallel semantics where components of a parallel tuple are always evaluated in parallel regardless of their size. The mode of an evaluation is sequential (written seq), parallel (written par), or oracle (written orc). We let α range over modes:

α ::= seq | par | orc.
In addition to evaluating expression, the dynamic semantics also returns cost measures including raw work and raw span denoted by w and s (and variants), and total work and total span, denoted by W and S (and variants). Dynamic semantics, whose inductive definition appears in Figure 3, is presented in the style of a natural (big-step) semantics and consists of evaluation judgments of the form e ⇓ α v, (w, s), (W, S).

This judgment states that evaluating expression e in mode α yields value v resulting in raw work of w and raw span of s and total work of W and total span of S.

Figure 3 shows the complete inductive definition of the dynamic cost semantics judgment e ⇓ α v, (w, s), (W, S). When evaluating any expression that is not a parallel tuple, we calculate the (raw or total) work and the (raw or total) span by summing up those of the premises (subexpressions) and adding one unit to include the cost of the judgment. For all expressions, including parallel tuples, each evaluation step contributes 1 to the raw work or raw span. When calculating total work and total span, we take into account the cost of creating a parallel thread τ and the cost of making an oracle decision φ .

Evaluation of parallel tuples vary depending on the mode.

• Sequential mode. Parallel tuples are treated exactly like sequential tuples: evaluating a parallel tuple simply contributes 1 to the raw and the total work (span), which are computed as the sum of the work (span) of the two branches plus 1. In the sequential mode, raw and total work (span) are the same. • Parallel mode. The evaluation of parallel tuples induces an additional constant cost τ. The span is computed as the maximum of the spans of the two branches of the parallel tuple plus 1, and work is computed as the sum of the work of the two branches plus τ. • Oracle mode. The scheduling of a parallel tuple depends on the amount of raw work involved in the two branches. If the raw work of each branch is more than κ, then the tuple is evaluated in parallel in the oracle mode. Otherwise, the raw work of at least one branch is less than κ, and the tuple is evaluated sequentially. In this case, the evaluation mode of each branch depends on the work of the branch. If a branch contains more than κ units of raw work, then it is evaluated in oracle mode, otherwise it is evaluated in sequential mode. This switch to sequential mode on small If the parallel tuple is evaluated sequentially, then the raw/total work and span are both calculated as the sum of the span of the branches plus one. If the parallel tuple is evaluated in parallel, then an extra τ is included in the total work and span and the span is computed as the maximum of the span of the two branches.

(ptuple-orc-parallelize) w 1 ≥ κ ∧ w 2 ≥ κ e 1 ⇓ orc v 1 , (w 1 , s 1 ), (W 1 , S 1 ) e 2 ⇓ orc v 2 , (w 2 , s 2 ), (W 2 , S 2 ) (|e 1 , e 2 |) ⇓ orc (v 1 , v 2 ) , (w 1 + w 2 + 1, max (s 1 , s 2 ) + 1), (W 1 + W 2 + 1 + τ + φ , max (S 1 , S 2 ) + 1 + τ + φ ) (ptuple-orc-sequentialize) w 1 < κ ∨ w 2 < κ e 1 ⇓ (if w 1 <κ then seq else orc) v 1 , (w 1 , s 1 ), (W 1 , S 1 ) e 2 ⇓ (if w 2 <κ then seq else orc) v 2 , (w 2 , s 2 ), (W 2 , S 2 ) (|e 1 , e 2 |) ⇓ orc (v 1 , v 2 ) , (w 1 + w 2 + 1, s 1 + s 2 + 1), (W 1 + W 2 + 1 + φ , S 1 + S 2 + 1 + φ )
Theorem 5.1 makes it possible to apply directly the greedy-scheduling theorem to the cost semantics. The basic idea of the proof is to show a correspondence between the cost semantics and dags.

Theorem 5.1 (Greedy scheduling for the cost semantics) Assume e ⇓ orc v, (w, s), (W, S) to hold for some v, w and s. Any greedy scheduler executes the expression e in no more than W P + S computations steps on P processors.

Proof

In order to invoke Theorem 4.2, which applies to computation dags, we build the computation dag associated with the execution of the expression e, including vertices that represent the cost of scheduling. To that end, we describe a recursive algorithm for turning an expression e with total work W and total span S into the corresponding computation dag, in which the sum of the weights of the vertices is equal to W, and the maximal weight of a path is S. The algorithm follows the structure of the derivation that e has total work W and total span S.

• If the last rule has zero premises, then e is an atomic expression and W = S = 1. We build the corresponding dag as a single vertex of unit weight. • If the last rule has one premise, then W takes the form W 1 + 1 and S takes the form S 1 + 1. Let G 1 be the dag corresponding to the sub-expression described in the premise. We build G by extending G 1 with one unit-weight vertex at the bottom, that is, by sequentially composing G 1 with a dag made of a single vertex. • Otherwise the last rule has two premises. First, consider the case where e is a letexpression. W takes the form W 1 + W 2 + 1 and S takes the form S 1 + S 2 + 1. Let G 1 and G 2 be the dags corresponding to the two sub-expressions. We build G by sequentially composing G 1 with a single unit-weight vertex and then with G 2 . • Consider now the case of a parallel tuple that is sequentialized. W takes the form

W 1 + W 2 + 1 + φ and S takes the form S 1 + S 2 + 1 + φ . Let G 1
and G 2 be the dags corresponding to the two branches. We build G by sequentially composing a vertex of weight 1 + φ with the sequential composition of G 1 and G 2 .

• Finally, consider the case of a parallel tuple that is parallelized. W takes the form W 1 +W 2 +1+τ +φ and S takes the form max (S 1 , S 2 )+1+τ +φ . Let G 1 and G 2 be the dags corresponding to the two branches. We build G by sequentially composing a vertex of weight 1 + τ + φ with the parallel composition of G 1 and G 2 .

It is straightforward to check that, in each case, W and S match the sum of the weights of the vertices and the total span of the dag being produced. We analyze the impact of thread-creation overheads on parallel execution time and show how these costs can be reduced dramatically by using our oracle semantics. For our analysis, we first consider an ideal oracle that always makes perfectly accurate predictions (about the raw work of expressions) without any overhead (i.e., φ = 0). Such an ideal oracle is unrealistic, because it is practically impossible to determine perfectly accurately the raw work of computations. We therefore consider a realistic oracle that approximates the raw work of computations by performing constant work. Our main result is a theorem that shows that the realistic oracle can reduce the thread-creation overheads to any desired constant fraction of the raw work with some increase in span, which we show to be small for a reasonably broad class of computations.

Ideal Oracle

Theorem 6.1 quantifies the relationships between raw work / raw span and total work / total span for the three possible modes.

Theorem 6.1 (Work and span) Consider an expression e such that e ⇓ α v, (w, s), (W, S).

Assume φ = 0. The following tight bounds can be obtained for total work and total span, on a machine with P processors where the cost of creating parallel threads is τ.

α Bound on total work Bound on total span seq

W = w S = s = w par W ≤ (1 + τ 2 ) w S ≤ (1 + τ) s orc W ≤ (1 + τ κ+1 ) w S ≤ (1 + max (τ, κ)) s Proof
Results for the sequential mode is straightforward by inspection of the semantics of the source language (Figure 3). The other results can be obtained by specializing the general bounds that we present later in this section (Theorem 6.2 and Theorem 6.3). In what follows, we give examples that attain the bounds for the parallel and the oracle modes.

• For the work in parallel mode, consider an expression consisting only of parallel tuples with n leaves, and thus n -1 "internal nodes". The raw work w is equal to n + (n -1) while the total work W is equal to n + (n -1)(1 + τ). The ratio W/w can be rewritten as 1 + (n-1)τ 2n-1 , which tends to 1 + τ 2 as n grows. • For the span in parallel mode, we can use the same example. Each parallel tuple accounts for 1 in the raw span but for 1 + τ in the total span. So, the total span can be as much as 1 + τ times greater than the raw span.

• For the work in oracle mode, consider an expression with n nested parallel tuples, where tuples are always nested in the right branch of their parent tuple. The tuples are built on top of expressions that involve κ units of work. In the oracle semantics, all the tuples are executed in parallel. The raw work w is equal to n + (n + 1)κ, and the total work W is equal to n(1 + τ) + (n + 1)κ. The ratio W/w is equal to 1 + nτ n(κ+1)+κ , which tends to 1 + τ κ+1 when n gets large. Acar, Charguéraud, Rainey

• For the span in oracle mode, in the case τ ≥ κ, we use the same example as for the work. The raw span is n + 1 and the total span is n(1 + τ) + κ. The ratio S/s is equal to 1 + nτ+κ-1 n+1 , which approaches 1 + τ as n grows. • For the span in oracle mode, in the case κ ≥ τ, we change the example slightly so that now the tuples are built on leaves that involve just less than κ units of work. In the oracle semantics, all the tuples thus get executed sequentially. In this case the raw span is n + κ and the total span is equal to the total work, which is n + (n + 1)κ. The ratio S/s can be expressed as 1 + nκ n+κ , which approaches 1 + κ as n grows. This theorem leads to some important conclusions. First, the theorem shows that threadcreation (scheduling) costs matter a great deal. In a parallel evaluation, the total work and total span can be as much as τ times larger than the raw span and raw work. This essentially implies that a parallel program can be significantly slower than its sequential counterpart. If τ is large compared to the number of processors, then even in the ideal setting, where the number of parallel processors is small relative to τ, we may observe no speedups. In fact, it is not uncommon to hear anecdotal evidence of this kind of slowdown in modern computer systems.

Second, the theorem shows that evaluation of a program with an ideal oracle can require as much as κ 2 less work than in the parallel mode. This comes at a cost of increasing the span by a factor of up to κ τ . Increasing the span of a computation can hurt parallel execution time because many parallel schedulers rely on parallel slackness, i.e., the availability of large degree of parallelism to achieve optimal speedups, or w P s. Unless done carefully, increasing the span can dramatically reduce parallel slackness. In the common case, however, where there is large amounts of parallel slackness, we can safely increase span by a factor of κ τ to reduce the thread-creation overheads. Concretely, if parallel slackness is high, then, in the oracle mode, we can select κ such that parallel slackness is preservedtotal span remains small compared to w P , because κs remains relatively small compared to w P -and the total work is reduced approximately by a factor of κ 2 .

Realistic Oracles

The analysis that we present above makes two unrealistic assumptions about oracles: 1) that they can accurately predict the raw work for a thread, and 2) that the oracle can make predictions in zero time. Realizing a very accurate oracle in practice is difficult, because it requires determining a priori the execution time of a thread. We therefore generalize the analysis by considering an approximate or realistic oracle that can make errors up to a multiplicative factor µ when estimating raw work. For example, an oracle can approximate raw work up to a constant factor of µ = 3, i.e., a thread with raw work w would be estimated to perform raw work between w 3 and 3w. Additionally, we allow the oracle to take some fixed time, written φ , to provide its answer.

We show that even with a realistic oracle, we can reduce thread-creation overheads. We start with bounding the span; the result implies that the total span is no larger than µκ times the raw span when κ is large compared to τ and φ . Theorem 6.2 (Span with realistic oracle)

e ⇓ orc v, (w, s), (W, S) ⇒ S ≤ (1 + max (τ, µκ) + φ ) s ZU064-05-FPR main
5 December 2016 16:9

Oracle-Guided Scheduling

13

Proof Let ρ denote 1 + max (τ, µκ) + φ ; we want to prove that S ≤ ρs. The proof is by induction on the derivation e ⇓ orc v, (w, s), (W, S).

• For a rule with zero premise, we have S = s = 1. Because ρ ≥ 1, it follows that S ≤ ρs.

• For a rule with one premise, we know by induction hypothesis that S ≤ ρs. Using again the fact that ρ ≥ 1, we can deduce the inequality S + 1 ≤ ρ(s + 1).

• For a rule with two premises that does not correspond to a parallel tuple, we can similarly establish the conclusion S 1 + S 2 + 1 ≤ ρ(s 1 + s 2 + 1) using the induction hypotheses S 1 ≤ ρs 1 and S 2 ≤ ρs 2 .

• Now, consider the case of a parallel tuple. First, assume that the two branches of this tuple are predicted to be large. In this case, the tuple is executed in parallel and the branches are executed in oracle mode. We exploit the induction hypotheses S 1 ≤ ρs 1 and S 2 ≤ ρs 2 to conclude as follows.

S = max (S 1 , S 2 ) + 1 + τ + φ ≤ max (ρs 1 , ρs 2 ) + 1 + max (τ, µκ) + φ ≤ max (ρs 1 , ρs 2 ) + ρ ≤ ρ (max (s 1 , s 2 ) + 1) ≤ ρs
• Consider now the case where both branches are predicted to be small. In this case, the tuple is executed sequentially. Because the oracle predicts the branches to be smaller than κ, they must be actually smaller than µκ. So, we have w 1 ≤ µκ and w 2 ≤ µκ. Moreover, both branches are executed according to the sequential mode, so we have S 1 = w 1 and S 2 = w 2 . It follows that S 1 ≤ µκ and S 2 ≤ µκ. Below, we also exploit the fact that max (s 1 , s 2 ) ≥ 1, which comes from the fact that raw span is at least one unit. We conclude as follows.

S = S 1 + S 2 + 1 + φ ≤ µκ + µκ + 1 + φ ≤ (1 + µκ + φ ) * 2 ≤ (1 + max (τ, µκ) + φ ) • (max (s 1 , s 2 ) + 1) ≤ ρs
• It remains to consider the case where one branch is predicted to be smaller than the cutoff while the other branch is predicted to be larger than the cutoff. In this case again, both branches are executed sequentially. Without loss of generality, assume that the second branch is predicted to be small. In this case, we have w 2 ≤ µκ. This second branch is thus executed according to the sequential mode, so we have S 2 = s 2 = w 2 . It follows that S 2 ≤ µκ. For the first branch, which is executed according to the oracle mode, we can exploit the induction hypothesis S 1 ≤ ρs 1 . We conclude as follows: This ends our analysis of the span. Now, let us focus on the work. The fact that every call to the oracle can induce a cost φ can lead the work to be multiplied by a factor in proportion with φ . For example, consider a program made of a complete tree made of 2n leaves, n parallel tuples on the last layer of the tree, and n -1 sequential tuples in the upper layers of the tree. This program has raw work equal to (n -1) + n + 2n, and total work equal to (n -1) + nφ + 2n. Thus, the increase in work W/w is equal to (3+φ )n-1 4n-1 , which is close to φ 4 when n and φ are not small. This example shows that a program executed according to the oracle semantics can slow down by as much as a factor φ 4 compared with a purely sequential execution.

S = S 1 + S 2 + 1 + φ ≤ ρs 1 + µκ + 1 + φ ≤ ρs 1 + (1 + max (τ, µκ) + φ ) ≤ ρ (s 1 + 1) ≤ ρ (max (s 1 , s 2 ) + 1) ≤ ρs
The problem with the above example is that the oracle is called infrequently-only at the leaves of the computation-preventing us from amortizing the cost of the oracle towards larger pieces of computations. Fortunately, most programs do not exhibit this pathological behavior, because parallel tuples are often performed close to the root of the computation, allowing us to detect smaller pieces of work early.

One way to prevent the oracle from being called on smaller pieces of work is to make sure that it is called at regular intervals. For proving a strong bound on the work, we will simply assume that the oracle is not called on small threads by restricting our attention to balanced programs. To this end, we define balanced programs as programs that call the oracle only on expressions that are no smaller than some constant γ off from the value κ µ , for some γ ≥ 1. Note that we use κ µ as a target and not κ so as to accommodate possible over-estimations in the estimations of raw work. The formal definition follows. Definition 6.1 (Balanced programs) For γ ≥ 1, a program or expression e is γ-balanced if evaluating e in the oracle mode invokes the oracle only for subexpressions whose raw work is no less than κ µγ . Note that if a program is γ-balanced and if γ < γ , then this program is also γ -balanced. We will later give a sufficient condition for proving that particular programs are balanced (Section 6.4). For balanced programs, we are able to bound the total work with respect to the raw work. Theorem 6.3 (Work with a realistic oracle) Let e be a γ-balanced program.

e ⇓ orc v, (w, s), (W, S) ⇒ W ≤ 1 + µ(τ + γφ ) κ + 1 w Proof
We establish the following slightly tighter inequality (tighter because γ ≥ 1 and µ ≥ 1).

W ≤ 1 + τ κ/µ + 1 + φ κ/(µγ) + 1 w
Define κ as a shorthand for κ/µ and κ as a shorthand for κ/(µγ). Note that, because γ ≥ 1, we have κ ≤ κ . Let x + be defined as the value x when x is nonnegative and as zero otherwise. We establish the following inequality by induction.

W ≤ w + τ (w-κ ) + κ +1 + φ (w-κ ) + κ +1
ZU064-05-FPR main 5 December 2016 16:9

Oracle-Guided Scheduling 15 This is indeed a strengthened result because we have:

τ (w-κ ) + κ +1 ≤ τ w κ +1 ≤ τ κ/µ+1 w and φ (w-κ ) + κ +1 ≤ φ w κ +1 ≤ φ κ/(µγ) + 1 w.
The proof is conducted by induction on the derivation of the reduction hypothesis.

• For a rule with zero premises, which describe an atomic operation, we have W = w = 1, so the conclusion is satisfied.

• For a rule with a single premise, the induction hypothesis is:

W ≤ w + τ (w-κ ) + κ +1 + φ (w-κ ) + κ +1
.

So, we can easily derive the conclusion:

W + 1 ≤ (w + 1) + τ ((w+1)-κ ) + κ +1 + φ ((w+1)-κ ) + κ +1
.

• For a rule with two premises, we exploit the mathematical inequality n q + m q ≤ n+m q

. We have:

W = W 1 + W 2 + 1 ≤ w 1 + τ (w1-κ ) + κ +1 + φ (w1-κ ) + κ +1 + w 2 + τ (w2-κ ) + κ +1 + φ (w2-κ ) + κ +1 + 1 ≤ w + τ (w1-κ ) + +(w 2 -κ ) + κ +1 + φ (w1-κ ) + +(w 2 -κ ) + κ +1
.

To conclude, we need to establish the following two mathematical inequalities.

(w 1 -κ ) + + (w 2 -κ ) + ≤ ((w 1 + w 2 + 1) -κ ) + (w 1 -κ ) + + (w 2 -κ ) + ≤ ((w 1 + w 2 + 1) -κ ) +
The two equalities can be proved in a similar way. Let us establish the first one. There are four cases to consider. First, if both w 1 and w 2 are less than κ , then the right-hand side is zero, so we are done. Second, if both w 1 and w 2 are greater than κ , then all the expressions are nonnegative, and we are left to check the inequality w 1κ + w 2κ ≤ w 1 +w 2 +1-κ . Third, if w 1 is greater than κ and w 2 is smaller than κ , then the inequality becomes (w 1κ ) + ≤ ((w 1κ ) + (w 2 + 1)) + , which is clearly true. The case w 1 ≥ κ and w 2 < κ is symmetrical. This concludes the proof.

• Consider now the case of a parallel tuple where both branches are predicted to involve more than κ units of work. This implies w 1 ≥ κ and w 2 ≥ κ . In this case, a parallel thread is created. Note that, because κ ≤ κ , we also have w 1 ≥ κ and w 2 ≥ κ . So, all the values involved in the following computations are nonnegative. Using the induction hypotheses,

W = W 1 + W 2 + 1 + τ + φ ≤ w 1 + τ w 1 -κ κ +1 + φ w 1 -κ κ +1 + w 2 + τ w 2 -κ κ +1 + φ w 2 -κ κ +1 + 1 + τ + φ ≤ (w 1 + w 2 + 1) + τ( w 1 -κ κ +1 + w 2 -κ κ +1 + 1) + φ ( w 1 -κ κ +1 + w 2 -κ κ +1 + 1) ≤ w + τ (w 1 -κ )+(w 2 -κ )+(κ +1) κ +1 + φ (w 1 -κ )+(w 2 -κ )+(κ +1) κ +1 ≤ w + τ (w 1 +w 2 +1)-κ κ +1 + φ (w 1 +w 2 +1)-κ κ +1 ≤ w + τ w-κ κ +1 + φ w-κ κ +1 .
• Assume now that the two branches are predicted to be less than the cutoff. This implies w 1 ≤ κ and w 2 ≤ κ . Both these threads are executed sequentially, so W 1 = w 1 and W 2 = w 2 . Since the program is γ-balanced, we have w 1 ≥ κ and w 2 ≥ κ . Those inequalities ensure that we are able to pay for the cost of calling the oracle, that is, the cost φ . Indeed, since we have

w 1 + w 2 + 1 -κ ≥ κ + 1, we know that w 1 +w 2 +1-κ κ +1
≥ 1. Therefore:

W = W 1 + W 2 + 1 + φ ≤ w 1 + w 2 + 1 + φ ≤ (w 1 + w 2 + 1) + φ w 1 +w 2 +1-κ κ +1 ≤ w + τ (w-κ ) + κ +1 + φ w-κ κ +1 .
• It remains to consider the case where one branch is predicted to be bigger than the cutoff while the other is predicted to be smaller than the cutoff. For example, assume w 1 ≥ κ and w 2 ≤ κ . The parallel tuple is thus executed as a sequential tuple. The first thread is executed in oracle mode, whereas the second thread is executed in the sequential mode. For the first thread, we can invoke the induction hypothesis W 1 ≤ w 1 +τ w 1 -κ κ +1 +φ w 1 -κ κ +1 . For the second thread, which is executed sequentially, we have W 2 = w 2 . Moreover, since the oracle is invoked to predict the size of this second thread, we know by the hypothesis of γ-balance that w 2 ≥ κ/(µγ) = κ . Hence, we have w 2 +1 κ +1 ≥ 1. We conclude:

W = W 1 + W 2 + 1 + φ ≤ w 1 + τ w 1 -κ κ +1 + φ w 1 -κ κ +1 + w 2 + 1 + φ ≤ w 1 + τ w 1 -κ κ +1 + φ w 1 -κ κ +1 + w 2 + 1 + φ w 2 +1 κ +1 ≤ w + τ w 1 +w 2 +1-κ κ +1 + φ w 1 +w 2 +1-κ κ +1 ≤ w + τ w-κ κ +1 + φ w-κ κ +1 .
ZU064-05-FPR main 5 December 2016 16:9

Oracle-Guided Scheduling

17

We are now ready to combine the version of Brent's theorem adapted to our cost semantics with the bounds that we have established for the total work and span in γ-balanced parallel programs executed under the oracle semantics. Theorem 6.4 (Execution time with a realistic oracle) Assume an oracle that costs φ and makes an error by a factor not exceeding µ. Assume κ > τ, which is always the case in practice. The execution time of a parallel γ-balanced program on a machine with P processors under the oracle semantics with a greedy scheduler does not exceed the value:

1 + µ(τ + γφ ) κ w P + (κ µ + φ + 1) s.

Proof

The bound follows by our generalized version of Brent's theorem (Theorem 5.1), and by the bounds established in Theorem 6.3 and Theorem 6.2. For simplicity, we replace the denominator κ + 1 with κ. This change does not loosen the bound significantly because κ is usually large compared to the unit cost. Also for simplicity, we have replaced the term max (τ, µκ) with µκ, exploiting the assumption κ > τ and the fact that µ ≥ 1.

Choice of the Cutoff

Theorem 6.4 shows that the running time of a parallel program can be controlled by changing the constant κ. The formula reveals an interesting tradeoff: we can reduce taskcreation overheads but this comes at the cost of increasing the span. To see this connection better, consider the bound that appears in the statement of Theorem 6.4 and notice that as the value of κ increases, the work (first) term decreases but the span (second) term increases. The parallel run time thus decreases as we increase κ up to some inflection point and then starts increasing. We compute the optimal value for κ by solving for the root of the derivative. We obtain:

κ * = τ + γφ • w Ps .
Thus, with prior knowledge of the raw work and raw span of a computation, we can pick κ to ensure efficiency of parallel programs. Such knowledge, however, is often unavailable. As we now show, we can improve efficiency of parallel programs by selecting a fixed κ that guarantees that the task creation overheads can be bounded by any constant fraction of the raw work, without increasing the span of the computation significantly. Theorem 6.5 (Run time with fixed κ) Consider an oracle with φ cost and µ error. For any γ ≥ 1 and for any constant r such that 0 < r < 1, there exists a constant κ and a constant c such that the evaluation with the oracle semantics of a γ-balanced program reduces task creation overheads to a fraction r of the raw work, while in the same time increasing the total span by no more than a factor c r . With a greedy scheduler, the total parallel run time on P processors of such a program thus does not exceed (1 + r) w P + c r s. Furthermore, by Theorem 6.2 we know that the total span is bounded by (max (τ, µκ) + φ + 1) s. Plugging in the same value for κ yields the following bound on total span:

S ≤ max τ, µ 2 (τ + γφ ) r + φ + 1 s.
Using µ ≥ 1 and r < 1, we can derive the inequality

S ≤ µ 2 (τ + γφ ) r + φ + 1 r s.
Choosing c = µ 2 (τ + γφ ) + φ + 1 therefore ensures that the total span does not exceed the desired bound c r s. The run-time bound follows by an application of our generalized version of Brent's theorem (Theorem 5.1).

This final theorem enables us to reduce task creation overheads to any desired constant fraction of the raw work by choosing a κ that is independent of the specific inputs. This comes at the cost of increasing the span, but only by a constant factor of c r . In the common case, when the work is asymptotically greater than span, e.g., Θ(n) versus O(log n), the resulting run-time guarantees that the increase in span remain small: specifically, the span term itself is a fraction of the work term for all but a constant number of small inputs.

Balanced Programs

Our bounds with the realistic oracle hold only for what we called γ-balanced programs, where the oracle is not called on small threads. This assumption can be satisfied by calling the oracle "regularly." It seems likely that this assumption would hold for many programs without requiring any changes to the program code. In this section, we show that recursive, divide-and-conquer programs are γ-balanced.

To that end, we introduce the notion of γ-regularity. Intuitively, a program is γ-regular if, between any two calls to the oracle involved in the execution of this program, the amount of work does not reduce by more than a factor γ. We will then establish that any γ-regular program is a γ-balanced program. Before giving the formal definition of γ-regularity, we need to formally define what it means for a parallel tuple to be dominated by another parallel tuple. Definition 6.2 (Domination of a parallel branch) A branch e of a parallel tuple is said to be dominated by the branch e i of another parallel tuple (|e 1 , e 2 |) if the expression e is involved in the execution of the branch e i . Definition 6.3 (Regularity of a parallel program) A program is said to be γ-regular if, for any parallel branch involving, say, w units of raw work, either w is greater than κ/(µγ) or this branch is dominated by another parallel branch that involves less than γw units of work.

ZU064-05-FPR main

5 December 2016 16:9

Oracle-Guided Scheduling

19

Remark: the condition "w is greater than κ/(µγ)" is typically used to handle the outermost parallel tuples, which are not dominated by any other tuple. Note that the regularity of a program is always greater than 2. Indeed, if one of the branch of a parallel tuple is more than half of the size of the entire tuple, then the other branch must be smaller than half of that size. On the one hand, algorithms that divide their work in equal parts are γ-regularity with γ very close to 2. On the other hand, ill-balanced programs can have a very high degree of regularity. Observe that every program is ∞-regular.

For example, consider a program that traverses a complete binary tree in linear time. A call on a tree of size n has raw work nc, for some constant c. If the tree is not a leaf, its size n has to be at least 3. The next recursive call involves raw work n-1 2 c, The ratio between those two values is equal n/ n-1 2 . This value is always less than 3 when n ≥ 3. So, the traversal of a complete binary tree is a 3-regular algorithm.

The following lemma explains how the regularity assumption can be exploited to ensure that the oracle is never invoked on threads of size less than κ/(µγ). This suggests that, for the purpose of amortizing well the costs of the oracle, a smaller regularity is better. Lemma 6.1 (From regularity to balanced) If a program is γ-regular then it is γ-balanced.

Proof

We have to show that, during the execution of a γ-regular program according to oracle semantics, the oracle is never invoked on subexpressions involving less than κ/(µγ) raw work. Consider a particular subexpression e involving w units of raw work, and assume that the oracle is invoked on this subexpression. Because the oracle is being invoked, e must correspond to the branch of a parallel tuple. By the regularity assumption, either w is no less than κ/(µγ), in which case the conclusion holds immediately, or the branch e is dominated by a branch e i that involves that involves w units of work, with w ≤ γw. For the latter case, we need to establish w ≥ κ/(µγ). To that end, it suffices to prove that w ≥ κ/µ, which amounts to showing that the amount of raw work associated with the dominating branch e i contains at least κ/µ raw work.

We conclude the proof by establishing the inequality w ≥ κ/µ. Because the oracle is being invoked on the subexpression e, it means that e is being evaluated in the mode orc. Therefore, the call to the oracle on the dominating branch e i must have predicted e i to contain more than κ raw work. (Otherwise e i and its subexpression e would have both been executed in the sequential mode.) Given that the oracle makes error by no more than a factor µ, if e i is predicted to contain more than κ units of raw work, then e i must contain at least κ/µ units of raw work. So, w ≥ κ/µ.

Approximating the Oracle-Guided Semantics

In the previous section, we have established that, if we have access to an oracle that can estimate actual raw work, i.e., sequential run-time, of an expression within a factor of no more than µ and at a cost of no more than a constant φ , then we can effectively control the thread-creation overheads and thus enable efficient parallel execution. In this section, we describe how to approximate such an oracle by combining certain information from the programmer along with run-time measurements. We first describe our approximation algorithm and then, in Section 8, show how some of the information needed by the algorithm can be derived via a program transformation.

The basic idea behind our approximation algorithm is to use some crucial information provided by the programmer to estimate the actual raw work of a computation. More precisely, we require the user to provide a cost function for each function in the program. When applied to an argument v, a cost function of f returns an abstract cost of the rawwork of application of f to v. A crucial property of the abstract costs is that they should be abstract enough that the programmer can write the cost functions without necessarily knowing the details of the hardware where the programs will be executed on. Yet, abstract costs should provide sufficient information to estimate the actual run times.

Asymptotic complexity specifications serve as a natural cost function by satisfying both of these properties. Since they eliminate hardware specific constants, they can be specified easily. Using complexity functions, we can approximate the actual run time of sequentially executed functions by simply determining the constants hidden by the asymptotic complexity notation. Such an approximation can be performed, e.g., by using the least squares method or similar techniques for data fitting from known samples. To perform this approximation we use an estimator data structure, that, given abstract cost samples for a function, can estimate the raw work for that function on a given argument.

Figure 4 shows the interface for the estimator. To perform accurate estimates, the estimator utilizes profiling data obtained from actual execution times. The sampling operation report(t, c, d) adds a cost c and an execution time d to the set of samples in an estimator t. An estimate of the actual execution time is obtained by calling predict. Given an estimator t and cost c, the call predict(t, c) returns a predicted execution time.

Since the abstract cost simply a measure of the asymptotic work of a function, all that remains for the estimator data structure is to calculate at run-time the actual constant factors for the hardware, where execution takes place. In our implementation, we represent a value of type cost as an integer that represents the application of the complexity function applied to the input size. We approximate the actual run time by calculating a single constant, assuming that the constants in all terms of the asymptotic complexity are the same. Although assuming a single constant can decrease the precision of the approximations, we believe that it suffices because we only have to compute lower bounds for our functions; i.e., we only need to determine whether they are "big enough" for parallel execution. We note that, for our theoretical bounds to apply, complexity expressions should require constant time to evaluate, which is usually the case because, in the common case, the cost functions are relatively simple functions. Oracle-Guided Scheduling

21

To ensure lightweight execution, our implementation simply computes the constant factor for each reported cost, and averages such constants over a period of time, which it then uses for prediction. The constants calculated for each reported cost may evolve over time. For example, if the current program is sharing the machine with another program, a series of memory reads by the other program may slow down the current program. For this reason, we do not just compute the average across the entire history, but instead maintain a moving average, that is, an average of the values gathered across a certain number of runs.

Computing averages is not entirely straightforward. On the one hand, storing the average in a memory cell that is shared by all processors is not satisfying, because it would involve some synchronization problems. On the other hand, using a different memory cell for every processor is not satisfying either, because it leads to slower updates of the constants when they change. In particular, in the beginning of the execution of a program it is important that all processors quickly share a relatively good estimate of the constant factors.

For these reasons, we have opted for an approach that uses not only a shared memory cell but also one data structure local to every processor. The shared memory cell associated with each estimator contains the estimated value for the constant that is read by all the processors when they need to predict execution times. The local data structures are used to accumulate statistics on the value of the constant. Those statistics are reported on a regular basis to the shared memory cell, by computing a weighted mean between the value previously stored in the shared memory cell and the value obtained out of the local data structure. We treat initializations somewhat specially: for the first few measures, a processor always begins by reporting its current average to the shared memory cell. This policy ensures a fast propagation of the information gathered from the first runs, so as to quickly improve the accuracy of the predictions.

In the rest of this section we present a more detailed description of our implementation of estimators. An estimator is represented as (1) a shared floating-point value storing the global estimated value, (2) an integer value storing, in the early phases, the number of times that the shared value has been updated, and (3) a processor-indexed array of pairs, each made of an integer and a floating-point value, for storing the number of measures and the sum of the constant factors measured. We define the local average value associated with a given processor as the ratio between the sum of the measured constants and the number of those measures.

The function create allocates a fresh estimator. It sets all fields to zero, except the global constant which is set to a very pessimistic constant, e.g., 1 microsecond. As a result, in the first few calls, the estimator largely over-approximates the work, leading only very small pieces of computation to be executed sequentially.

The function predict simply computes the product of the global estimated value of the constant with the integer cost produced by the user-provided asymptotic cost function.

The function report refines the estimation of the constant factor. First, it updates the pair of values associated with the processor that performed the measure, by incrementing the number of measures and adding to the sum field the ratio between the execution time and the complexity value being reported. Second, it decides whether the local average value of the constant should be reported to the global value. It does so if either (a) the number of measures exceeds c * P, for some real constant c, or if (b) the number of times that the Acar, Charguéraud, Rainey shared value has been updated is less than a fixed bound. The latter condition helps for fast propagation of the constant in the early phases.

When the function report decides to report its local average value to the global value, it writes into the shared value field a weighted average of the local average value and of the previous global value. For safety (that is, to avoid potentially sequentializing too large pieces of computations), we limit a single change to the global value to be of at most one order of magnitude (e.g., a factor 10). Besides, as an optimization, we skip the write operation if we notice that the new value is not significantly different from the old (e.g., when the value would change by less than 20%). After updating the shared value, the function resets to zero the pair of values associated with the current processor, in order to begin a new round of measurements. Moreover, in case the update of the shared value has been triggered by the condition (b) described above, the function also increments the shared field that stores the number of updates to the global value.

Note that the write operation that updates the shared value may sometimes get discarded as a result of a data race between processors. Such races, however, are benign.

When implementing the oracle, we faced three technical difficulties. First, we had to pay attention to the fact that the memory cells allocated for the different processors are not allocated next to each other. Otherwise, those cells would fall in the same cache line, in which case writing in one of these cells would make the other cells be removed from caches, making subsequent reads more costly. Second, we observed that the time measures typically yield a few outliers. Those are typically due to the activity of the garbage collector or of another program being scheduled by the operating system on the same processor. Fortunately, we have found detecting these outliers to be relatively easy because the measured times are at least one or two orders of magnitude greater than the cutoff value. Third, the default system function that reports the time is only accurate by one microsecond. This is good enough when the cutoff is greater than 10 microseconds. However, if one were to aim for a smaller cutoff, which could be useful for programs exhibiting only a limited amount of parallelism, then more accurate techniques would be required, for example using the specific processor instructions for counting the number of processor cycles.

Implementation via Source-to-Source Translation

We describe how to compile parallel codes with complexity annotations into codes that implement our oracle-guided semantics. Our compilation technique performs a source-tosource translation and relies on the technique described in Section 7. The idea is to compile every piece of code in two versions: one for the sequential semantics (seq mode), where all parallel pairs are simply erased to sequential pairs, and one for the oracle-guided semantics (orc mode), where parallel pairs are instrumented in such a way as to perform predictions and possibly measures, and to decide whether to execute the branches sequentially or in parallel.

For simplicity, we assume that constituents of parallel tuples are function applications, i.e., they are of the form

(| f 1 v 1 , f 2 v 2 |).
Note that this assumption does not cause loss of expressiveness, because a term e can always be replaced by a trivial application of a "thunk", a function that ignores its argument (typically of type "unit") and evaluates e to a dummy Oracle-Guided Scheduling

23 x ≡ x (v 1 , v 2 ) ≡ ( v 1 , v 2 ) inl v ≡ inl v inr v ≡ inr v fun f .
x.e b [e c |r] ≡ (r, (fun .

x. e c seq ), (fun f .x. e b seq ), (fun f .x. e b orc ))

v α ≡ v v 1 v 2 seq ≡ proj 3 v 1 v 2 v 1 v 2 orc ≡ proj 4 v 1 v 2 (e 1 , e 2 ) α ≡ ( e 1 α , e 2 α ) let x = e 1 in e 2 α ≡ let x = e 1 α in e 2 α fst v α ≡ fst v snd v α ≡ snd v case v of {inl x.e 1 , inr x.e 2 } α ≡ case v of {inl x. e 1 α , inr x. e 2 α } (| f 1 v 1 , f 2 v 2 |) seq ≡ proj 3 f 1 v 1 , proj 3 f 2 v 2 (| f 1 v 1 , f 2 v 2 |) orc ≡    let (b 1 , k 1 ) = MakeBranch( f 1 , v 1 ) in let (b 2 , k 2 ) = MakeBranch( f 2 , v 2 ) in if (b 1 && b 2 ) then (|k 1 (), k 2 ()|) else (k 1 (), k 2 ())
Fig. 5. Translation for oracle scheduling argument. Throughout, we write "fun f .x.e b [e c ]" to denote a function "fun f .x.e b " for which the cost function for the body e b is described by the expression e c . This expression e c , which may refer to the argument x, should be an expression whose evaluation always terminates and produces a cost of type cost.

To associate an estimator with each function, in a simple pass over the source code, we allocate and initialize an estimator for each syntactic function definition. For example, if the source code contains a function of the form "fun f .x.e b [e c ]", then our compiler allocates an estimator specific to that function definition. Specifically, if the variable r refers to the allocated estimator, then the translated function, written "fun f .x.e b [e c |r]", is annotated with r.

The second pass of our compilation scheme uses the allocated estimators to approximate the actual raw work of function applications and relies on an MakeBranch function to determine whether an application should be run in the oracle or in the sequential mode. Figure 5 defines more precisely the second pass. We write v for the translation of a value v, and we write e α for the translation of the expression e according to the semantics α, which can be either seq or orc. When specifying the translation, we use triples, quadruples, projections, sequence, if-then-else statements, and unit value; these constructions can all be easily defined in our core programming language.

Translation of values other than functions does not depend on the mode and is relatively straightforward. We translate functions, which are of the form "fun f .x.e b [e c |r]", into a quadruple consisting of the estimator r, a sequential cost function, the sequential version of the function, and the oracle versions of the function. Translation of a function application depends on the mode. In the sequential mode, the sequential version of the function is selected (by projecting the third component of the function) and used in the application. Similarly, in the oracle mode, the oracle version of the function is selected and used in

MakeBranch ( f , v) ≡ let r = proj 1 f in let m = proj 2 f v in let b = predict(r, m) > κ in let fun k seq () = proj 3 f v in let fun k seq () = MeasuredRun(r, m, k seq ) in let fun k orc () = proj 4 f v in let k = if b then k orc else k seq in (b, k) MeasuredRun (r, m, k) ≡ let t = get time () in let v = k () in let t = get time () in report (r, m, (t -t)); v
Fig. 6. Auxiliary meta-functions used for compilation the application. To translate a tuple, we recursively translate the subexpression, while preserving the mode. Similarly, translation of the let, projections, and case constructs are entirely structural.

In the sequential mode, a parallel tuple is turned into a simple tuple. In the oracle mode, the translation applies the oracle-based scheduling policy with the aid of the metafunction MakeBranch. This meta-function, shown in Figure 6, describes the template of the code generated for preparing the execution of a parallel tuple. MakeBranch expects a (translated) function f and its (translated) argument v, and it returns a boolean b indicating whether the application of f to v is expected to take more or less time than the cutoff κ, and a thunk t to execute this application. On the one hand, if the application is predicted to take more time than the cutoff (in which case b is true), then the thunk t corresponds to the application of the oracle-semantics version of the function f . On the other hand, if the application is predicted to take less time than the cutoff (in which case b is false), then the thunk t corresponds to the application of the sequential-semantics version of the function f . Moreover, in the latter case, the time taken to execute the application sequentially is measured. This time measure is reported to the estimator by the auxiliary meta-function MeasuredRun (Figure 6), so as to enable its approximations.

Observe that the translation introduces many quadruples and applications of projection functions. However, in practice, the quadruples typically get inlined so most of the projections can be computed at compile time. Observe also that the compilation scheme involves some code duplication, because every function is translated once for the sequential mode and once for the oracle mode. In theory, the code could grow exponentially when the code involves functions defined inside the body of other functions. In practice, the code the growth is limited because functions are rarely deeply nested. If code duplication was a problem, then we can use flattening to eliminate deep nesting of local functions, or pass the mode α as an extra argument to functions. In this section, we evaluate the effectiveness of our implementation through several experiments. We consider results from a range of benchmarks run on a machine with sixteen processors. The results show that, in each case, our oracle implementation improves on the plain work-stealing implementation. Furthermore, the results show that the oracle implementation scales well with up to sixteen processors.

Implementation in Manticore

In this section, we describe the implementation of our scheduling technique in an actual language and system. In our approach, source programs are written in our own dialect of the Caml language [START_REF] Leroy | The Objective Caml system[END_REF], which is a strict functional language. Our Caml dialect corresponds to the core Caml language extended with syntax for parallel pairs and complexity annotations. We use the Caml type checker to obtain a typed syntax tree, on which we perform the oracle-scheduling translation defined in Figure 5. We then produce code in the syntax of Parallel ML (PML) [START_REF] Fluet | Implicitly threaded parallelism in Manticore[END_REF], a parallel language close to Standard ML. The translation from Caml to PML is straightforward because the two languages are relatively similar. We compile our source programs to x86-64 binaries using Manticore, which is the optimizing PML compiler.

The original theorem of Brent as well as our generalization both assume a greedy scheduler that can find available work (threads to execute) immediately with no overhead. This assumption is unrealistic of course in a literal sense, but work-stealing schedulers are able to control the overheads for balancing work remarkably well, both in theory [START_REF] Blumofe | Scheduling multithreaded computations by work stealing[END_REF][START_REF] Arora | Thread scheduling for multiprogrammed multiprocessors[END_REF][START_REF] Acar | Scheduling parallel programs by work stealing with private deques[END_REF] and in practice [START_REF] Frigo | The implementation of the Cilk-5 multithreaded language[END_REF]. On the one hand, overheads related to queueing threads are tiny, and, on the other hand, the delay due to steals is tamed by the fact that steals are relatively rare. Work stealing has also been shown to have good locality behavior, which further improves its effectiveness [START_REF] Acar | The data locality of work stealing[END_REF].

In Manticore's work-stealing scheduler, all system processors are assigned to collaborate on the computation. Each processor owns a deque (doubly-ended queue) of threads represented as thunks. Processors treat their own deques like call stacks. When a processor starts to evaluate a parallel-pair expression, it creates a thread for the second subexpression of the pair and pushes the thread onto the bottom of the deque. Processors that have no work left try to steal threads from others. More precisely, they repeatedly select a random processor and try to pop a thread from this processor's deque.

Manticore's implementation of work stealing [START_REF] Rainey | Effective scheduling techniques for high-level parallel programming languages[END_REF] adopts a code-specialization scheme, called clone translation, taken from Cilk-5's implementation [START_REF] Frigo | The implementation of the Cilk-5 multithreaded language[END_REF].2 With clone translation, each parallel-pair expression is compiled into two versions: the fast clone and the slow clone. The purpose of a fast clone is to optimize the code that corresponds to evaluating on the local processor, whereas the slow clone is used when the second branch of a parallel-pair is migrated to another processor. A common aspect between clone translation and our oracle translation (Figure 5) is that both generate specialized code for the sequential case. But the clone translation differs in that there is no point at which parallelism is cut off entirely, as the fast clone may spawn threads.

The scheduling cost involved in the fast clone is a (small) constant, because it involves just a few local operations, but the scheduling cost of the slow clone is variable, because it involves inter-processor communication. It is well established, both through analysis and experimentation, that (with high probability) no more than O(P S) steals occur during the evaluation [START_REF] Arora | Thread scheduling for multiprogrammed multiprocessors[END_REF]. So, for programs that exhibit parallel slackness (W P S), we do not need to take into account the cost of slow clones because there are relatively few of them. We focus only on the cost of creating fast clones, which correspond to the cost τ. A fast clone needs to package a thread, push it onto the deque and later pop it from the deque. So, a fast clone is not quite as fast as the corresponding sequential code. The exact slowdown depend on the implementation, but in our case we have observed that a fast clone is 3 to 5 times slower than a simple function call.

Test Machine

Our test machine has four quad-core AMD Opteron 8380 processors running at 2.5GHz. Each core has 64Kb each of L1 instruction and data cache, and a 512Kb L2 cache. Each processor has a 6Mb L3 cache that is shared with the four cores of the processor. The system has 32Gb of RAM and runs Debian Linux (kernel version 2.6.31.6-amd64).

Measuring Scheduling Costs

We report estimates of the thread-creation overheads for each of our test machine. To estimate, we use a synthetic benchmark expression e whose evaluation sums integers between zero and 30 million using a parallel divide-and-conquer computation. We chose this particular expression because most of its evaluation time is spent evaluating parallel pairs. First, we measure w s : the time required for executing a sequentialized version of the program (a copy of the program where parallel tuples are systematically replaced with sequential tuples). This measure serves as the baseline. Second, we measure w w : the time required for executing the program using work stealing, on a single processor. This measure is used to evaluate τ. Third, we measure w o : the time required for executing a version of the program with parallel tuples replaced with ordinary tuples but where we still call the oracle. This measure is used to evaluate φ .

We then define the work-stealing overhead c w = w w w s . We estimate the cost τ of creating a parallel thread in work stealing by computing w w -w s n , where n is the number of parallel pairs evaluated in the program. We also estimate the cost φ of invoking the oracle by computing w o -w s m , where m is the number of times the oracle is invoked. Our measures are as follows: c w = 4.86 and τ = 0.09 microseconds and φ = 0.18 microseconds. The first value indicates that work stealing alone can induce a slowdown by a factor of 4 or 5, for programs that create a huge number of parallel tuples. The value of τ, close to one tenth of a microsecond, indicates, that the cost of creating parallel threads is roughly between 200 and 300 processor cycles (since our benchmark machine runs at

2.5GHz

). This cost is quite significant in front of basic operations that execute in just a few cycles.

The oracle cost φ is even larger than τ -about twice larger. The fact that the oracle is associated with significant costs is not surprising: recall that the estimations and measures associated with our implementation of the oracle involve functions calls and memory operations. However, also keep in mind that our investment in performing oracle predictions is supposed to pay off as soon as we are able to sequentialize large pieces of computation. Indeed, as we have established, the cost of the oracle can be expected to be well amortized and to only account for a tiny fraction of the total execution time.

In our experiments, we used the cutoff value κ = 26 microseconds. We use Theorem 6.4 to estimate an upper-bound on the overheads associated with thread creation and oracle predictions. To that end, we first need to evaluate µ and γ. We can estimate µ, the bound on the relative error associated with the predictions, by performing runs where we logged both our predictions and our measures. We observed that, apart from a few outliers (i.e. exceptionally large measures for sequentialized threads), our oracle is always accurate within a factor 2. So, we assume µ = 2. Besides, our benchmark programs are fairly regular: we can assume γ = 3 for all of them. Now, Theorem 6.4 tells us that, for programs exhibiting sufficient parallelism, the overheads are essentially bounded by µ(τ+γφ ) κ . In our setting, this ratio evaluates to just below 5% -we actually set the value of κ to meet this target. In practice, since the errors associated with our time predictions tend to balance out, the µ term that appears in front of the bound does not impact us as much as it could in theory. Likewise, the irregularity factor φ does not actually reach 3 for every parallel tuple executed. For these reasons, we believe that, in practice, overheads usually do not exceed 3%.

Benchmarks

We used five benchmarks in our empirical evaluation. Each benchmark program was originally written by other researchers and ported to our dialect of Caml.

The Quicksort benchmark sorts a sequence of 2 million integers. Our program is adapted from a functional, tree-based algorithm [START_REF] Blelloch | Parallelism in sequential functional languages[END_REF]. The algorithm runs Acar, Charguéraud, Rainey with O(n log n) raw work and O(log 2 n) raw depth, where n is the length of the sequence. Sequences of integers are represented as binary trees in which sequence elements are stored at leaf nodes and each internal node caches the number of leaves contained in its subtree.

The Quickhull benchmark calculates the convex hull of a sequence of 3 million points contained in 2-d space. The algorithm runs with O(n log n) raw work and O(log 2 n) raw depth, where n is the length of the sequence. The representation of points is similar to that of Quicksort, except that leaves store 2-d points instead of integers.

The Barnes-Hut benchmark is an n-body simulation that calculates the gravitational forces between n particles as they move through 2-d space (Barnes & Hut, 1986). The Barnes-Hut computation consists of two phases. In the first, the simulation volume is divided into square cells via a quadtree, so that only particles from nearby cells need to be handled individually and particles from distant cells can be grouped together and treated as large particles. The second phase calculates gravitational forces using the quadtree to accelerate the computation. The algorithm runs with O(n log n) raw work and O(log n) raw depth. Our benchmark runs 10 iterations over 100,000 particles generated from a random Plummer distribution [START_REF] Plummer | On the problem of distribution in globular star clusters[END_REF]. The program is adapted from a Data-Parallel Haskell program (Peyton Jones, 2008). The representation we use for sequences of particles is similar to that of Quicksort.

The SMVM benchmark multiplies an m×n matrix with an n×1 dense vector. Our sparse matrix is stored in the compressed sparse-row format. The program contains parallelism both between dot products and within individual dot products. We use a sparse matrix of dimension m = 500,000 and n = 448,000, containing 50,400,000 nonzero values.

The DMM benchmark multiplies two dense, square n × n matrices using the recursive divide-and-conquer algorithm of Frens and Wise [START_REF] Frens | Auto-blocking matrix-multiplication or tracking blas3 performance from source code[END_REF]. We have recursion go down to scalar elements. The algorithm runs with O(n 3 ) raw work and O(log n) raw depth. We selected n = 512.

Performance

For every benchmark, we measure several values. replacing each parallel tuple with an ordinary tuple and erasing complexity functions, so that the sequential version includes none of the thread-creation overheads. T P par denotes the execution time with work stealing on P processors. T P orc denotes the execution time of our oracle-based work stealing on P processors.

The most important results of our experiments come from comparing plain work stealing and our oracle-based work stealing side by side. Figure 7 shows the speedup on sixteen processors for each of our benchmarks, that is, the values T 16 par /T seq and T 16 orc /T seq . The The fact that some benchmarks benefit more from our oracle implementation than others is explained by Figure 8. This plot shows execution time for one processor, normalized with respect to the sequential execution times. In other words, the values plotted are 1, T 1 orc /T seq and T 1 par /T seq . The values T 1 orc /T seq range from 1.03 to 1.13 (with an average of 1.07), indicating that the thread-creation overheads in the oracle implementation do not exceed 13% of the raw work in any benchmark. The cases where we observe large improvements in speedup are the same cases where there is a large difference between sequential execution time and plain work-stealing execution time. When the difference is large, there is much room for our implementation to improve on work stealing, whereas when the difference is small we can only improve the execution time by a limited factor.

Figure 9 shows speedup curves for each of our experiments, that is, values of T P par /T seq and T P orc /T seq against the number of processors P. The curves show that our oracle implementation generally scales well up to sixteen processors. There is one exception, which is the quickhull benchmark. For this benchmark, the curve tails off after reaching twelve processors. We believe that this tailing is either due to a lack of parallelism in the program or to a bottleneck on memory accesses. Notice, however, that our scheduler does not fall below plain work stealing.

10 Related Work

Cutting Off Excess Parallelism

This study is not the first to propose using cost prediction to determine when to cut off parallelism. One approach, developed in early work in functional programing, uses list size to determine cut offs [START_REF] Huelsbergen | Using the run-time sizes of data structures to guide parallel-thread creation[END_REF]. Using list size alone is limited, because the technique assumes linear work complexity for every parallel operation.

Another way to handle cost prediction is to use the depth and height of the recursion tree [START_REF] Weening | Parallel execution of lisp programs[END_REF][START_REF] Pehoushek | Low-cost process creation and dynamic partitioning in Qlisp[END_REF]. But depth and height are not, in general, the most direct means to predict the execution time of subcomputations. In our oracle scheduling, we ask for either the programmer or compiler to provide for each function a cost function that expresses the asymptotic cost of applying the function.

Lopez et. al. take this approach as well, but in the context of logic programming [START_REF] Lopez | A methodology for granularity-based control of parallelism in logic programs[END_REF]. On the surface, their technique is similar to our oracle scheduling, except that their cost estimators do not utilize profiling to estimate constant factors. An approach without constant-factor estimation is overly simplistic for modern processors, because it relies on complexity function predicting execution time exactly. On modern processors, execution time depends heavily on factors such as caching, pipelining, etc. and it is not feasible in general to predict execution time from a complexity function alone.

Reducing Thread-Creation Cost

One approach to the granularity problem is to focus on reducing the cost of creating a thread, rather than limiting the number of threads created. This approach is taken by implementations of work stealing with lazy thread creation [START_REF] Mohr | Lazy task creation: a technique for increasing the granularity of parallel programs[END_REF][START_REF] Feeley | A message passing implementation of lazy task creation[END_REF]ZU064-05-FPR main 5 December 2016 16:9

Oracle-Guided Scheduling 31 [START_REF] Feeley | An efficient and general implementation of futures on large scale sharedmemory multiprocessors[END_REF][START_REF] Frigo | The implementation of the Cilk-5 multithreaded language[END_REF][START_REF] Rainey | Effective scheduling techniques for high-level parallel programming languages[END_REF][START_REF] Hiraishi | Backtracking-based load balancing[END_REF][START_REF] Sanchez | Flexible architectural support for fine-grain scheduling[END_REF][START_REF] Tzannes | Lazy scheduling: A runtime adaptive scheduler for declarative parallelism[END_REF]. In lazy thread creation, the work stealing scheduler is implemented so as to avoid, in the common case, the major scheduling costs, in particular, those of interprocessor communication. But, in even the most efficient lazy thread creation, there is still a non-negligable scheduling cost for each implicit thread. Lazy Binary Splitting (LBS) is an improvement to lazy thread creation that applies to parallel loops [START_REF] Tzannes | Lazy scheduling: A runtime adaptive scheduler for declarative parallelism[END_REF]. The crucial optimization comes from extending the representation of a thread so that multiple loop iterations can be packed into a single thread. This representation enables the scheduler to both avoid creating closures and executing deque operations for most iterations. A limitation of LBS is that it addresses only parallel loops whose iteration space is over integers. Lazy Tree Splitting (LTS) generalizes LBS to handle parallel aggregate operations that produce and consume trees, such as map and reduce [START_REF] Bergstrom | Lazy tree splitting[END_REF]. LTS is limited, however, by the fact that it requires a special cursor data structure to be defined for each tree data structure.

Amortizing Per-Thread Costs

Aharoni et al. study the granularity problem in the setting of distributed computing [START_REF] Aharoni | A run-time algorithm for managing the granularity of parallel functional programs[END_REF], where the crucial issue is how to minimize the cost of inter-processor communication. In their setting, the granularity problem is modeled as a staging problem, in which there are two stages. The first stage consists of a set of processor-local thread pools and the second stage consists of a global thread pool. Moving a thread to the global thread pool requires inter-processor communication. The crucial decision is how often each processor should promote threads from its local thread pool to the global thread pool. We consider a different model of staging in which there is one stage for parallel evaluation and one for sequential evaluation.

The approach proposed by Aharoni et al. is based on an online algorithm called CG. In this approach, it is assumed that the cost of moving a thread to the global thread pool is an integer constant, called g. The basic idea is to use amortization to reduce the scheduling total cost of moving threads to the global thread pool. In particular, for each thread that is moved to the global thread pool, CG ensures that there are at least g + 1 threads added to the local thread pool. Narlikar describes a similar approach based on an algorithm called DFDeques [START_REF] Narlikar | Space-efficient scheduling for parallel, multithreaded computations[END_REF]. Just as with work stealing, even though the scheduler can avoid the communication costs in the common case, the scheduler still has to pay a nonnegligable cost for each implicit thread.

Flattening and Fusion

Flattening is a well-known program transformation for nested parallel languages [START_REF] Blelloch | Compiling collection-oriented languages onto massively parallel computers[END_REF]. Implementations of flattening include NESL [START_REF] Blelloch | Implementation of a portable nested data-parallel language[END_REF]Data Parallel Haskell (Peyton Jones, 2008). Flattening transforms the program into a form that maps well onto SIMD architectures. Flattened programs are typically much simpler to schedule at run time than nested programs, because much of the schedule is predetermined by the flattening [START_REF] Spoonhower | Scheduling deterministic parallel programs[END_REF]. Controlling the granularity of such programs is correspondingly much simpler than in general. A limitation of existing flattening is that certain [START_REF] Blelloch | A provable time and space efficient implementation of NESL[END_REF], as a consequence of the transformation making changes to data structures defined in the program. Our transformation involves no such changes. The NESL [START_REF] Blelloch | Implementation of a portable nested data-parallel language[END_REF] and Data Parallel Haskell (Peyton Jones, 2008) compilers implement fusion transformation in order to increase granularity. Fusion transforms the program to eliminate redundant synchronization points and intermediate arrays. Although fusion reduces scheduling costs by combining adjacent parallel loops, it is not relevant to controlling granularity within loops. As such, fusion is orthogonal to our oracle based approach.

Scheduling and Locality

In our approach, we make scheduling decisions based on a property of the intrinsic semantics of pieces of computation: the work of parallel threads. In other related work on scheduling for data locality [START_REF] Acar | The data locality of work stealing[END_REF][START_REF] Blelloch | Effectively sharing a cache among threads[END_REF], recent work showed that basing scheduling decisions on the space usage of parallel threads, a different property of intrinsic semantics, can be helpful in improving locality. For example, a class of "space-bounded schedulers" [START_REF] Chowdhury | Oblivious algorithms for multicores and network of processors[END_REF][START_REF] Blelloch | Scheduling irregular parallel computations on hierarchical caches[END_REF][START_REF] Cole | Resource oblivious sorting on multicores[END_REF]) are shown to be well suited for improved locality on deep memory hierarchies. Since space usage of a parallel thread can be bounded by its work, our techniques may be helpful in scheduling for improved data locality.

Cost Semantics

To give an accurate accounting of thread-creation of overheads in implicitly parallel languages we use a cost semantics, where evaluation steps (derivation rules) are decorated with work and span information or "costs". This information can then be used directly to bound running time on parallel computers by using standard scheduling theorems that realize Brent's bound. Many previous approaches also use the same technique to study workspan properties, some of which also make precise the relationship between cost semantics and the standard directed-acyclic-graph models [START_REF] Blelloch | Parallelism in sequential functional languages[END_REF][START_REF] Blelloch | A provable time and space efficient implementation of NESL[END_REF][START_REF] Spoonhower | Space profiling for parallel functional programs[END_REF]. The idea of instrumenting evaluations to generate cost information goes back to the early 90s [START_REF] Sands | Calculi for time analysis of functional programs[END_REF][START_REF] Rosendahl | Automatic complexity analysis[END_REF].

Inferring Complexity Bounds

Our implementation of oracle scheduling requires the programmer to enter complexity bounds for all parallel tasks. In some cases, these bounds can be inferred by various static analyses, for example, using type-based and other static analyses (e.g., [START_REF] Crary | Resource bound certification[END_REF][START_REF] Jost | Static determination of quantitative resource usage for higher-order programs[END_REF]), symbolic techniques (e.g., [START_REF] Goldsmith | Measuring empirical computational complexity[END_REF][START_REF] Gulwani | Speed: precise and efficient static estimation of program computational complexity[END_REF]). Our approach can benefit from these approaches by reducing the programmer burden, making it ultimately easier to use the proposed techniques in practice. Since the publication of the conference version of this paper [START_REF] Acar | Oracle scheduling: Controlling granularity in implicitly parallel languages[END_REF], we have conducted additional research that further validates the proposed techniques, extends their applicability, and explores extensions to other problem domains outside of the fork-join idiom considered here. In addition to the ML library described in this paper, we implemented our techniques as an optimized, lower-level library for the C++ language (Acar et al., 2015a), which uses a highly optimized work-stealing scheduler to achieve efficiency [START_REF] Acar | Scheduling parallel programs by work stealing with private deques[END_REF]. This library offers techniques for writing parallel programs in the full generality of the C++ language and is now a reasonably mature software system. We used the library in undergraduate teaching at Carnegie Mellon University (Acar & Blelloch, 2015a;[START_REF] Acar | Algorithm design: Parallel and sequential[END_REF] and elsewhere in intensive courses on parallelism. Our experience in developing this library and the feedback from over 500 students taught thus far suggest that the techniques proposed in this paper can be implemented and used in practice. More recently, we have also started researching the granularity problem in more unstructured parallel-computing problems, including for example graphs, and presented an algorithm for unordered parallel depth-first-search that achieves its efficiency by carefully controlling granularity (Acar et al., 2015b). We are currently working on extending the automatic granularity-control techniques presented here to such unstructured problems.

Challenges for Programming with Complexity Functions

The oracle-guided semantics that we presented is relatively general purpose and broadly applicable. Our implementation of this semantics based on the approximation algorithm (Section 7) and the translation (Section 8), however, make the following two assumptions.

• Each complexity function in the given parallel program is accurate and efficient.

• Our approximation algorithm can always approximate constant factors effectively.

Although these two requirements are easily met for large classes of programs, there are challenging cases. In what follows, we describe several such challenging cases that we have encountered.

Complexity Functions Requiring Auxiliary Data Structures

There are programs for which providing a constant-time function that computes the complexity of a computation requires the pre-computation of an auxiliary data structure. We ran into such an example when implementing the sparse-matrix by dense vector multiplication benchmark program. Essentially, we needed to pre-compute a prefix sum array over the input data in order to determine the number of non-zero values covered by a range of consecutive rows in the sparse matrix. Fortunately, the cost of this pre-computation turned out to be relatively small in front of the rest of the computations, so the overhead associated with the introduction of the complexity function was limited. For additional details on this example, we refer to the evaluation section of an earlier description of our work [START_REF] Acar | Oracle scheduling: Controlling granularity in implicitly parallel languages[END_REF]. Another challenge is that of providing complexity functions for higher-order functions.

Consider for example a "map" function that can be used to apply a given function f to all the leaves of a binary tree. Clearly, the asymptotic complexity of a call of the map function to a function f and a tree depends not just on the tree but also on the evaluation of the asymptotic complexity function f on the various leaves of the tree. It is far from obvious how to handle the general case properly. Nevertheless, there are at least two large classes of f functions for which we are able to implement a useful asymptotic complexity function for predicting the cost of calls to map.

The first class includes constant-time functions. If we map a constant function to all the leaves of a binary tree, then the asymptotic cost is proportional to the number of leaves in the tree. Therefore, to evaluate the cost of the map function on any subtree, it suffices to precompute and store, for each node from the tree, the size of the subtree rooted at this node. Of course, caching additional values in the data structures and maintaining those values upon changes induce additional overheads, but it seems hard to control granularity without any form of additional information.

This approach generalizes to the application of map to functions that do not necessarily take constant time but take a time that depends on the weight of the leaf it is applied to, for some definition of weight. For example, consider a binary tree that stores lists of integers in its leaves, and assume that we map to this tree a function that increments all the integers stored in the leaves. In this case, we define the weight of a leaf as the length of the list it stores, and define the weight of a subtree as the sum of the weight of its leaves. If we pre-compute the weight of every node in the tree, then we are able to provide a useful asymptotic cost function.

The implementation of the complexity function is not the only challenge associated with higher-order functions: evaluation of the constant factors is another. For example, the constant factors of the map function depend both on the constant factors of the function f passed to it and on constant factors inherent to the traversal of tree data structures. One possible solution is to allocate one different estimator for every instantiation of the map function. However, doing so results in imperfect sharing of constant factors, possibly leading to longer convergence phases. In summary, higher-order functions are associated with a number of open challenges.

Mismatch between Average and Worst-Case Complexity

Our ability to implement the oracle relies on the assumption that we are able to predict asymptotically the amount of work involved in a computation. However, there are cases where the amount of computation to be performed depends on the data itself, and not just on the size of the data.

For example, consider string comparison. On many pairs of input, the comparison terminates quickly because of a mismatch occurring in the first few characters of the two strings. However, the worst-case execution time is O(n). If we naively use O(n) as the complexity function, but the execution is most frequently O(1), we will conclude that the constant factors are tiny. At this point, if we receive a pair of two identical strings, we will Oracle-Guided Scheduling

35

incorrectly predict the comparison to run fast, and as a result we will fully sequentialize the linear-time comparison of the two strings, even though it could have been performed faster in parallel.

Another example is that of (non randomized) quick sort. The expected complexity is O(n log n), but in the worst case it can run in O(n 2 ). We are tempted to use O(n log n) for making predictions. What happens if we do so but then run on an input that triggers a quadratic behavior? We will likely sequentialize sub-computations of much larger size than we ideally aim for. However, it turns out that the inputs that triggers quadratic behavior are also those for which the quick sort algorithm does not exhibit any parallelism. In other words, we could not have sorted the items faster using quick sort by controlling granularity differently.

Initial Estimation of the Constant Factors

The approach described in this paper has another limitation related to the way that we currently handle the initial convergence phase for the estimation of the constant factors. This limitation may affect code whose structure is more complex than simple recursive divide-and-conquer functions.

To understand the limitation, recall that, when a program begins, we do not have any estimation for its constant factors, and that we initially consider a pessimistic (i.e. large) value for the constants. By doing so, we typically begin by sequentializing only tiny pieces of work; later, when a constant factor is measured to be actually smaller than its initial pessimistic value, we are then able to sequentialize larger pieces of work. This scheme suffices in the case of simple recursive functions, because the constant factors that are measured one level of recursion can be exploited to make predictions at a higher level of recursion.

Consider, however, the case of two nested loops, both implemented as basic divideand-conquer recursive functions. The constant-factor estimation for the inner loop will converge properly. However, the constant-factor estimation for the outer loop may never get updated because a measured run is not necessarily triggered. Even when the full execution of the inner loop is systematically sequentialized, consecutive iterations of the outer loop never get sequentialized, because the estimator of the outer loop, which does not share information with the estimator of the inner loop, continues to use the initial pessimistic constant estimation.

Intuitively, our approximation algorithm is facing a bootstrapping problem here: on the one hand, for sequentializing pieces of work, we need some reasonably accurate estimate of the constant factors; on the other hand, we may only obtain these estimations through sequentialized computations. We leave to future work the design of better approximation algorithms and runtime techniques for either propagating more information or for estimating upper bounds to the constant factors, so as to be able to escape this bootstrapping issue.

In this paper, we present an analysis of the impact of thread-creation costs on the performance of implicitly parallel programs and provide a solution for controlling these costs based on an oracle. We formulate our solutions in the context of a nested-parallel functional language and prove that it successfully controls thread-creation costs by using an amortization technique, known also as granularity control. We then present an approximation algorithm for realizing our oracle-guided semantics with the help of asymptotic complexity functions provided by the programmer. We implement our techniques and perform an experimental evaluation, which shows that the approach is effective in controlling the thread-creation costs without detrimentally affecting the performance in the benchmarks considered. While this paper makes important progress towards solving the granularitycontrol problem, it also shows that there is more work to be done. For example, we have seen theoretically that our approximation algorithm only works for certain kinds of computations. While we have also validated the techniques proposed in this paper in other research projects and in teaching (Section 10.8), our implementations and experiments are still relatively new and would benefit from a more thorough evaluation that considers larger and more varied benchmarks.

Fig. 1 .

 1 Fig. 1. An example computation dag.

  Theorem 4.2 (Greedy-scheduling of weighted dags) Let G be a computation dag with W total work and S total span. Any greedy P processors schedule of G takes O( W P + S) steps. Proof

Fig. 2 .

 2 Fig. 2. Abstract syntax of the source language

Fig

  Fig. 3. Dynamic cost semantics

  γ-balanced program with raw work w and raw span s, and consider its evaluation under the oracle semantics. By Theorem 6.3 we know that total work does not exceed 1 + µ(τ+γφ ) κ w. To achieve the desired bound on execution time, we take κ = µ(τ+γφ ) r . Plugging this value of κ into the formula yields (1 + r) w for total work, showing that task creation overheads are reduced to a fraction r of the raw work.

Fig. 7 .

 7 Fig. 7. Comparison of the speedup on sixteen processors. Higher bars are better.

Fig. 8 .

 8 Fig. 8. Comparison of execution times (normalized) on a single processor. Lower bars are better.

Fig. 9 .

 9 Fig. 9. Comparison between work stealing and oracle.

User-level threads are sometimes called "strands"; unfortunately, the same term is sometimes used to refer to hardware threads.

In the Cilk-5 implementation, it is called clone compilation.

December 2016 16:9

Acknowledgments

This research was partially supported by the National Science Foundation (grants CCF-1320563 and CCF-1408940), European Research Council (grant ERC-2012-StG-308246), and by Microsoft Research.