Hongyang Sun

Redouane Elghazi

Ana Gainaru

Guillaume Aupy

Padma Raghavan

Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling

Scheduling in High-Performance Computing (HPC) has been traditionally centered around computing resources (e.g., processors/cores). The ever-growing amount of data produced by modern scientific applications start to drive novel architectures and new computing frameworks to support more efficient data processing, transfer and storage for future HPC systems. This trend towards data-driven computing demands the scheduling solutions to also consider other resources (e.g., I/O, memory, cache) that can be shared amongst competing applications. In this paper, we study the problem of scheduling HPC applications while exploring the availability of multiple types of resources that could impact their performance. The goal is to minimize the overall execution time, or makespan, for a set of moldable tasks under multiple-resource constraints. Two scheduling paradigms, namely, list scheduling and pack scheduling, are compared through both theoretical analyses and experimental evaluations. Theoretically, we prove, for several algorithms falling in the two scheduling paradigms, tight approximation ratios that increase linearly with the number of resource types. As the complexity of direct solutions grows exponentially with the number of resource types, we also design a strategy to indirectly solve the problem via a transformation to a single-resource-type problem, which can significantly reduce the algorithms' running times without compromising their approximation ratios. Experiments conducted on Intel Knights Landing with two resource types (processor cores and high-bandwidth memory) and simulations designed on more resource types confirm the benefit of the transformation strategy and show that pack-based scheduling, despite having a worse theoretical bound, offers a practically promising and easy-to-implement solution, especially when more resource types need to be managed.

I. INTRODUCTION

Scientific discovery now relies increasingly on data and its management. Large-scale simulations produce an evergrowing amount of data that has to be processed and analyzed. As an example, it was estimated that the Square Kilometer Array (SKA) could generate an exabyte of raw data a day by the time it is completed [START_REF] Barwick | SKA telescope to generate more data than entire Internet in[END_REF]. In the past, scheduling in High-Performance Computing (HPC) has been mostly compute-based (with a primary focus on the processor/core resource) [START_REF] Yoo | Slurm: Simple linux utility for resource management[END_REF]. In general, data management is deferred as a second step separate from the data generation. The data created would be gathered and stored on disks for data scientists to study later. This will no longer be feasible, as studies have shown that these massive amounts of data are becoming increasingly difficult to process [START_REF] Gainaru | Scheduling the I/O of HPC applications under congestion[END_REF].

To cope with the big-data challenge, new frameworks such as in-situ and in-transit computing [START_REF] Dreher | A flexible framework for asynchronous in situ and in transit analytics for scientific simulations[END_REF] have emerged. The idea is to use a subset of the computing resources to process data as they are created. The results of this processing can then be used to re-inject information in the subsequent simulation in order to move the data towards a specific direction. In addition, architectural improvements have been designed to help process the data at hand. Emerging platforms are now equipped with more levels of memory/storage (e.g., NVRAM, burst buffers, data nodes) and better data transfer support (e.g., high-bandwidth memory, cache-partitioning technology) that can be exploited by concurrent applications.

In view of such trend towards data-driven computing, this work presents techniques on how to efficiently schedule competing applications given this multi-tier memory hierarchy. We go even further by considering in our scheduling model any resource (e.g., I/O, memory, cache) that can be shared or partitioned amongst these applications and that can impact their performance. The goal is to design, analyze and evaluate scheduling solutions that explore the availability of these multiple resource types in order to reduce the overall execution time, or makespan, for a set of applications. The applications in this work are modeled as independent moldable tasks whose execution times vary depending on the different resources available to them (see Section III for the formal definition of moldable tasks). This general model is particularly representative of the in-situ/in-transit workflows, where different analysis functions have to be applied to different subsets of the data generated.

We focus on two scheduling paradigms, namely, list scheduling and pack scheduling. In list scheduling, all tasks are first organized in a priority list. Then, the tasks are assigned in sequence to the earliest available resources that can fit them. In pack scheduling, the tasks are first partitioned into a series of packs, which are then executed one after another. Tasks within each pack are scheduled concurrently and a pack cannot start until all tasks in the previous pack have completed. Both scheduling paradigms have been studied by the literature, mostly under a single-resource constraint (see Section II for a literature review). Figure 1 shows an example of applying both scheduling paradigms to a same set of tasks under a single-resource constraint.

Compared to some more sophisticated scheduling algorithms that could guarantee better theoretical bounds (e.g., [START_REF] Mounié | A 3/2-approximation algorithm for scheduling independent monotonic malleable tasks[END_REF], [START_REF] Jansen | Linear-time approximation schemes for scheduling malleable parallel tasks[END_REF]), list-based and pack-based algorithms often produce simple yet efficient schedules that can be easily implemented by practical runtime systems. Furthermore, these algorithms can be adopted to the online and/or heterogeneous scheduling environment with minimal change, thus offering more general applicability to a wide range of scheduling scenarios. Between these two paradigms, list scheduling can make better use of the available resources (at least in theory) by reducing the idle times between the tasks and thus maximizing the resource utilization. However, pack scheduling has been advocated by some recent studies [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF], [START_REF] Shantharam | Speedup-aware co-schedules for efficient workload management[END_REF] for being practically valuable due to its ease of implementation (as batch processing) and for incurring less scheduling overhead. The relative merits of the two scheduling paradigms are yet to be evaluated under multiple-resource constraints.

In this paper, we provide a comprehensive study of the two scheduling paradigms through both theoretical analyses and experimental evaluations in the presence of multiple resource types. In this context, we make the following contributions:

• We present several scheduling algorithms under multipleresource constraint in both list and pack scheduling paradigms, and prove tight approximation ratios for these algorithms (2d for list and 2d + 1 for pack, where d is the number of resource types). • We design a transformation strategy that reduces the problem of scheduling multiple resource types to singleresource-type scheduling, thereby significantly reducing the algorithms' running times without compromising the approximation ratios. • We conduct experimental evaluations of these scheduling algorithms on the Intel Xeon Phi Knights Landing (KNL) processor, which offers two resource management options (processor cores and high-bandwidth memory). • We project the performance of both list-and pack-based scheduling solutions under more than two resource types using simulations on synthetic parallel workloads that extend some classical speedup profiles. Overall, the experimental/simultion results confirm the benefit of the transformation strategy and show that pack scheduling, despite having a slightly worse theoretical bound, can indeed offer a practically promising yet easy-to-implement solution compared to its list counterpart, especially when more resource types need to be managed. The insights derived from these results will be especially relevant to the emerging architectures that will likely offer in the resource management systems more scheduling possibilities across the memory hierarchy to embrace the shift towards data-driven computing.

The rest of this paper is organized as follows. Section II reviews some related work. Section III formally defines the multiple-resource-type scheduling model. Section IV presents several scheduling solutions and proves their approximation ratios. Section V is devoted to experimental evaluation of different algorithms and heuristics. Finally, Section VI concludes the paper with hints on future directions.

II. RELATED WORK A. Parallel Task Models

Many parallel task models exist in the scheduling literature. Feitelson [START_REF] Feitelson | Job scheduling in multiprogrammed parallel systems (extended version)[END_REF] classified parallel tasks into three categories, namely, rigid tasks, moldable tasks and malleable tasks. A rigid task requires a fixed amount of resources (e.g., number of processors) to execute. A moldable task can be executed with a varying amount of resources, but once the task has started the resource allocation cannot be changed. The most flexible model is the one of malleable tasks, which allows the amount of resources executing the task to vary at any time during the execution. For the latter two models, two important parameters are the speedup function and the total area (or work). The speedup function relates the execution time of a task to the amount of resources allocated to it, and the total area is defined as the product of execution time and resource allocation. Many prior works [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF], [START_REF] Belkhale | An approximate algorithm for the partitionable independent task scheduling problem[END_REF], [START_REF] Mounié | A 3/2-approximation algorithm for scheduling independent monotonic malleable tasks[END_REF] have assumed that the speedup of a task is a non-decreasing function of the amount of allocated resources (hence the execution time is a non-increasing function) and that the total area is a nondecreasing function of the allocated resources. One example is the well-known Amdahl's law [START_REF] Amdahl | Validity of the single processor approach to achieving large scale computing capabilities[END_REF], which specifies the speedup of executing a parallel task with s sequential fraction using p processors as 1/(s + 1-s p ). Another example used by some scheduling literature [START_REF] Beaumont | Task scheduling for parallel multifrontal methods[END_REF], [START_REF] Sanders | Efficient parallel scheduling of malleable tasks[END_REF], [START_REF] Guermouche | Scheduling trees of malleable tasks for sparse linear algebra[END_REF] is the speedup function p α , where p represents the amount of allocated resources to the task and α ≤ 1 is a constant. In particular, this function has been observed for processor resources when executing parallel matrix operations [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF] as well as for characterizing the cache behaviors in terms of the miss rate of data access (which is directly related to the execution time) [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2? J. Instruction-Level Parallelism[END_REF]. We refer to this function as the power law.

All works above apply to the case with a single resource type, and, to the best of our knowledge, no explicit speedup model is known to include multiple resource types. In Section V, we extend these speedup functions to construct synthetic parallel tasks with multiple-resource demands. We also perform a profiling study of the Stream benchmark [START_REF] Mccalpin | STREAM: Sustainable memory bandwidth in high performance computers[END_REF] on a recent Intel Xeon Phi architecture that includes two resource types (processor core and high-bandwidth memory).

B. Parallel Task Scheduling

Scheduling a set of independent parallel tasks to minimize the makespan is known to be strongly NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], thus much attention has been directed at designing approximation or heuristic algorithms. Most prior works focused on allocating a single resource type (i.e., processors) to the tasks, and the constructed schedules are either pack-based (also called shelf-based or level-based) or list-based.

Approximation Algorithms: Scheduling rigid tasks with contiguous processor allocation can be considered as a rectangle packing or 2D-strip packing problem. For this problem, Coffman et al. [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] showed that the Next-Fit Decreasing Height (NFDH) algorithm is 3-approximation and the First-Fit Decreasing-Height (FFDH) algorithm is 2.7-approximation. Both algorithms pack rectangles onto shelves, which are equivalent to creating pack-based schedules. The first result (i.e., 3-approximation) has also been extended to the case of moldable task scheduling [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF], [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]. Turek et al. [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] presented a strategy to extend any algorithm for scheduling rigid tasks into an algorithm for scheduling moldable tasks in polynomial time. The strategy preserves the approximation ratio provided that the makespan for the rigid-task problem satisfies certain conditions. The complexity of such an extension was improved in [START_REF] Ludwig | Scheduling malleable and nonmalleable parallel tasks[END_REF] with possibly a worse schedule than the one obtained in [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] but without compromising the approximation ratio. Thanks to these strategies, a 2-approximation algorithm was devised for moldable tasks based on list scheduling [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], [START_REF] Ludwig | Scheduling malleable and nonmalleable parallel tasks[END_REF], extending the same ratio previously known for rigid tasks [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF]. Using dual-approximation techniques, Mounie et al. [START_REF] Mounié | A 3/2-approximation algorithm for scheduling independent monotonic malleable tasks[END_REF] presented a 1.5-approximation algorithm for moldable tasks while assuming that the total area of a task is a non-decreasing function of the allocated processors. Also for moldable tasks, Jansen and Porkolab [START_REF] Jansen | Linear-time approximation schemes for scheduling malleable parallel tasks[END_REF] presented, for any > 0, a (1 + )-approximation scheme when the number of processors is a fixed constant. While all results above are for scheduling under a single resource type, only a few papers have considered scheduling under multiple resource types. Garey and Graham [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF] proved that a simple list-scheduling algorithm is (d + 1)approximation for rigid tasks, where d is the number of resource types. He et al. [START_REF] He | Adaptive scheduling of parallel jobs on functionally heterogeneous resources[END_REF] proved the same asymptotic result for scheduling a set of malleable jobs, each represented as a direct acyclic graph (DAG) of unit-size tasks. For moldable tasks, Shachnai and Turek [START_REF] Shachnai | Multiresource malleable task scheduling[END_REF] presented a technique to transform a c-approximation algorithm on a single resource type to a c • d-approximation algorithm on d types of resources. Partially inspired by these results, this paper presents techniques and algorithms with improved approximations for pack scheduling and new algorithms for list scheduling under multiple resource types.

Heuristics: Some papers have proposed heuristic solutions for multiple-resource-type scheduling under various different models and objectives. Leinberger et al. [START_REF] Leinberger | Job scheduling in the presence of multiple resource requirements[END_REF] considered rigid tasks and proposed two heuristics that attempt to balance the usage of different resource types through backfilling strategies. He et al. [START_REF] He | Scheduling functionally heterogeneous systems with utilization balancing[END_REF] studied online scheduling of DAGbased jobs and proposed a multi-queue balancing heuristic to balance the sizes of the queues that contain ready tasks under different resource types. Ghodsi et al. [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF] proposed Dominant Resource Fairness (DRF), a multiple-resource-type scheduling algorithm for user tasks with fixed resource demands. It aims at ensuring the resource allocation fairness among all users by identifying the dominant resource share for each user and maximizing the minimum dominant share across all users. Grandl et al. [START_REF] Grandl | Multi-resource packing for cluster schedulers[END_REF] considered scheduling malleable tasks under four resource types (CPU, memory, disk and network), and designed a heuristic, called Tetris, that packs tasks to a cluster of machines. This is similar to pack-based scheduling but instead of creating packs in time it creates them in space. Tetris works by selecting a task with the highest correlation between the task's peak resource demands and the machine's resource availabilities, with the aim of minimizing resource fragmentation. NoroozOliaee et al. [START_REF] Noroozoliaee | Online multi-resource scheduling for minimum task completion time in cloud servers[END_REF] considered a similar cluster scheduling problem but with two resources only (CPU and memory). They showed that the simple Best Fit plus Shortest Task First scheduling outperforms other packing heuristics (e.g., First Fit, FCFS) in terms of resource utilization and task queueing delays.

III. MODEL

This sections presents a formal model of the scheduling problem, which we call d-RESOURCE-SCHEDULING. Suppose a platform has d different types of resources subject to allocation (e.g., processor, memory, cache). For each resource type i, there is a total amount P (i) of resources available. Consider a set of n independent tasks (or jobs), all of which are released at the same time on the platform, so the problem corresponds to scheduling a batch of applications in HPC environment. For each task j, its execution time t j ( p j ) is a function of the resource allocation vector p j = (p

(1) j , p (2) j , • • • , p (d) j )
, where p (i) j denotes the amount of the ith resource allocated to task j. In reality, the execution times are typically obtained by application profiling or interpolation and curve-fitting from historic data. Suppose p j and q j are two resource allocation vectors, and we define p j q j if p

(i) j ≤ q (i) j for all 1 ≤ i ≤ d.
Here, the execution time is assumed to be a non-increasing function of the resource allocation, i.e., p j q j implies t j ( p j ) ≥ t j ( q j ). This means that increasing the allocation of any one type of resource without decreasing the others will not increase the execution time 1 . We also assume that the resource allocations p (i) j 's and the total amount of resources P (i) 's are all integer values. This holds naturally true for discrete resources such as processors 2 . For other resources (e.g., memory, cache), it can be justified as most practical resource management systems allocate the resources in discrete chunks (e.g., memory blocks, cache lines). Note that some tasks may not require all resource types in order to execute, hence its resource allocation p (i) j for a particular resource can be zero, in which case the execution time remains validly defined. In contrast, other tasks may require a minimum amount of certain resource in order to execute. In this case, the execution time can be defined as infinity for any amount of resource below this threshold. The model is flexible to handle both scenarios.

In this paper, we focus on moldable task scheduling [START_REF] Feitelson | Job scheduling in multiprogrammed parallel systems (extended version)[END_REF], where the amount of resources allocated to a task can be freely selected by the scheduler at launch time but they cannot be changed after the task has started the execution. Moldable task scheduling strikes a good balance between practicality and performance by incurring less overhead than malleable task scheduling yet achieving more flexible task executions than rigid task scheduling. For the d-RESOURCE-SCHEDULING problem, the scheduler needs to decide, for each task j, a resource allocation vector p j along with a starting time s j . At any time t, a task is said to be active if it has started but not yet completed, i.e., t ∈ [s j , s j + t j ( p j )). Let J t denote the set of active tasks at time t. For a solution to be valid, the resources used by the active tasks at any time should not exceed the total amount of available resources for each resource type, i.e., j∈Jt p (i) j

≤ P (i) for all t and i. The objective is to minimize the maximum completion time, or the makespan, of all tasks, i.e., T = max j (s j + t j ( p j )).

Since d-RESOURCE-SCHEDULING is a generalization of classical makespan minimization problem with a single re-

For platform d

Number of resource types

P (i) Total amount of i-th type of resource (i = 1, • • •, d) For any task j p (i) j
Amount of i-th type of resource allocated to task j pj Resource allocation vector of task j tj( pj)

Execution time of task j with vector pj aj( pj)

Area of task j with vector pj sj Starting time of task j For set of all tasks n Number of all tasks p Resource allocation matrix for all tasks A(p)

Total area of all tasks with matrix p tmax(p) Maximum execution time of all tasks with matrix p T (p)

Makespan of all tasks with matrix p L(p, s)

Maximum of A(p)/s and tmax(p) for any s > 0 Lmin(s) Minimum L(p, s) over all matrix p source type, it is strongly NP-complete. Hence, we are interested in designing approximation and heuristic algorithms. In this paper, we will focus on and compare two major scheduling paradigms, namely, list scheduling and pack scheduling. A scheduling algorithm S is said to be c-approximation if its makespan satisfies T S ≤ c • T OPT for any instance, where T OPT denotes the makespan by an optimal moldable scheduler. Note that the optimal scheduler needs not be restricted to either list scheduling or pack scheduling.

IV. THEORETICAL ANALYSIS

In this section, we present polynomial-time algorithms for the d-RESOURCE-SCHEDULING problem under both list-and pack-scheduling paradigms, and we prove tight approximation ratios for these algorithms.

A. Preliminaries

We start with some preliminary definitions that will be used throughout the analysis. Table I provides a summary of the main notations used.

Definition 1. Define p = ( p 1 , p 2 , • • •, p n ) T
to be a resource allocation matrix for all tasks, where p j = (p

(1) j , p (2) j , • • •, p (d) j
) is a resource allocation vector for task j. Definition 2. Given a resource allocation matrix p for the d-RESOURCE-SCHEDULING problem, we define the following:

• For task j, a j ( p j ) = d i=1 p (i) j P (i) •t j ( p j ) is the task's area 3 ; • A(p) = n j=1 a j ( p j ) is the total area of all tasks; • t max (p) = max j t j ( p j ) is the maximum execution time of all tasks; • L(p, s) = max A(p)
s , t max (p) for any s > 0. The last quantity L(p, s) is related to the lower bound of the makespan. In particular, we define

L min (s) = min p L(p, s) , (1)
and we will show later that it is a lower bound on the makespan when s is set to be d.

In the following, we will present two general techniques for constructing the scheduling solutions. The first technique is a two-phase approach, similarly to the one considered in scheduling under a single resource type [START_REF] Ludwig | Scheduling malleable and nonmalleable parallel tasks[END_REF]: 3 Rigorously, we define

a j ( p j ) = ∞ if ∃i, s.t. p (i) j = 0 and t j ( p j ) = ∞.
• Phase 1: Determines a resource allocation matrix for all the tasks; • Phase 2: Constructs a rigid schedule based on the fixed resource allocation of the first phase. The second technique is a transformation strategy that reduces the d-RESOURCE-SCHEDULING problem to the 1-RESOURCE-SCHEDULING problem, which is then solved and whose solution is transformed back to the original problem.

Section IV-B presents a resource allocation strategy (Phase 1). Section IV-C presents a transformation strategy, followed by rigid task scheduling schemes (Phase 2) in Section IV-D under both pack and list scheduling. Finally, Section IV-E puts these different components together and presents several complete scheduling solutions.

B. A Resource Allocation Strategy

This section describes a resource allocation strategy for the first phase of the scheduling algorithm. It determines the amounts of resources allocated to each task, which are then used to schedule the tasks in the second phase as a rigid task scheduling problem.

The goal is to find efficiently a resource allocation matrix that minimizes L(p, s), i.e.,

p s min = arg min p L(p, s) . (2)
Let P = d i=1 (P (i) + 1) denote the number of all possible allocations for each task, including the ones with zero amount of resource under a particular resource type. A straightforward implementation takes O(P n ) time, which grows exponentially with the number of tasks n. Algorithm 1 presents a resource allocation strategy RA d (s) that achieves this goal in O(nP (log P + log n + d)) time. Note that when the amounts of resources under different types are in the same order, i.e., P (i) = O(P max ) for all i = 1, • • •, d, where P max = max i P (i) , the running time grows exponentially with the number of resource types d, i.e., the complexity contains O(P d max ). Since the number of resource types is usually a small constant (less than 4 or 5), the algorithm runs in polynomial time under most realistic scenarios.

The algorithm works as follows. First, it linearizes and sorts all P resource allocation vectors for each task and eliminates any allocation that results in both a higher execution time and a larger total area (Lines 2-17), for such a vector can be replaced by another one that leads to the same or smaller L min (s) (Equation ( 1)). Each task then ends up with an array of admissible allocations in increasing order of execution time and decreasing order of total area. The complexity for this part is O n(P log P + P d) , which is dominated by sorting each task's allocations and computing its area. Then, the algorithm goes through all possible t max , i.e., the maximum execution time, from the remaining admissible allocations, and for each t max considered, it computes the minimum total area A and hence the associated L value (Lines 18-40). This is achieved by maintaining the tasks in a priority queue with their longest execution times as priorities and updating the queue with a task's new priority when its next longest execution time is considered. The algorithm terminates either when at least one task has exhausted its admissible allocations, in which case the priority queue will have fewer than n tasks (Line 20), or when L becomes dominated by A s (Line 30), since the total area only increases and the maximum execution time decreases during this process. As the allocation is only changed for one task when a new t max is considered, the total area can be updated by keeping track of the area change due to this task alone (Line 36). The algorithm considers at most nP possible t max values and the complexity at each step is dominated by updating the priority queue, which takes O(log n) time, and by updating the total area, which takes O(d) time, so the overall complexity for this part is O nP (log n + d) . Now, we show that the resource allocation matrix p s min returned by Algorithm 1 while setting the parameter s to be d can be used by a rigid task scheduling strategy in the second phase to achieve good approximations.

T R d (p d min ) ≤ c • L min (d) , (3)
then the two-phase algorithm RA d (d)+R d is c-approximation for the d-RESOURCE-SCHEDULING problem.

To prove the above theorem, let us define p OPT to be the resource allocation matrix of an optimal schedule, and let T OPT denote the corresponding optimal makespan. We will show in the following lemma that L min (d) serves as a lower bound on T OPT . Then, Theorem 1 follows directly, since

T RA d (d)+R d = T R d (p d min ) ≤ c • L min (d) ≤ c • T OPT . Lemma 1. T OPT ≥ L min (d).
Proof. We will prove that, given a resource allocation matrix p, the makespan produced by any rigid task scheduler using p must satisfy T (p) ≥ t max (p) and T (p) ≥ A(p) d . Thus, for the optimal schedule, which uses p OPT , we have

T OPT ≥ max t max (p OPT ), A(pOPT) d = L(p OPT , d) ≥ L min (d).
The last inequality is because L min (d) is the minimum L(p, d) among all possible resource allocations including p OPT (Equation ( 1)).

The first bound T (p) ≥ t max (p) is trivial since the makespan of any schedule should be at least the execution time of the longest task. For the second bound, we have, in any valid schedule with makespan T (p), that:

A(p) = n j=1 d i=1 p (i) j P (i) • t j ( p j ) = d i=1 1 P (i) n j=1 p (i) j • t j ( p j ) ≤ d i=1 1 P (i) • P (i) • T (p) = d • T (p) .
The inequality is because P (i) • T (p) is the maximum volume for resource type i that can be allocated to all the tasks within a total time of T (p).

C. A Transformation Strategy

This section describes a strategy to indirectly solve the d-RESOURCE-SCHEDULING problem via a transformation to the 1-RESOURCE-SCHEDULING problem.

Algorithm 2 presents the transformation strategy TF, which contains three steps. First, any instance I of the d-RESOURCE-SCHEDULING problem is transformed to an instance I of the 1-RESOURCE-SCHEDULING problem. Then, I is solved by any moldable task scheduler under a single resource type. Lastly, the solution obtained for I is transformed back to obtain a solution for the original instance I. The complexity of the transformation alone (without solving the instance I ) is O(nQd), dominated by the first step of the strategy, where Q is defined as the Least Common Multiple (LCM) of all the P (i) 's. Note that if Q is in the same order as the maximum amount of resource P max = max i P (i) among all resource types (e.g., when P (i) 's are in powers of two), the complexity becomes linear in P max . In contrast, the complexity of solving the problem directly (by relying on Algorithm 1) contains P d max . Thus, the transformation strategy can greatly reduce an algorithm's running time, especially when more resource types need to be scheduled (see our simulation results in Section V-D).

In the subsequent analysis, we will use the following notations:

• For the transformed instance I : Let q = (q 1 , q 2 , • • • , q n ) T denote the resource allocation for the transformed tasks. L min (s) is the minimum L (q, s) as defined in Equation ( 1), and T M1 denotes the makespan produced by a moldable task scheduler M 1 for the 1-RESOURCE-SCHEDULING problem.

Algorithm 2: Transformation Strategy TF Input: Set of n tasks, execution time t j ( p) ∀j, p, resource limit P (i) ∀i Output: Starting time s j and resource allocation vector p j ∀j (1) Transform d-RESOURCE-SCHEDULING instance I to 1-RESOURCE-SCHEDULING instance I ;

• I has the same number n of tasks as I;

• The resource limit for the only resource of

I is Q = lcm i=1•••d P (i) ;
• For any task j in I , its execution time with any amount of resource q ∈ {0, 1, 2, • • • , Q} is defined as t j (q) = t j (( • For any task j in I, its starting time is s j = s j , where s j is the starting time of task j in I , and its resource allocation vector is

q•P (i) Q ) i=1•••d ); (
p j = ( q j •P (i) Q ) i=1•••d
, where q j is the allocation of the only resource for task j in I .

• For the original instance I: Recall that L min (s) denotes the minimum L(p, s) defined in Equation ( 1), and let T TF+M1 denote the makespan produced by the algorithm TF + M 1 , which combines the transformation strategy TF and the scheduler M 1 for a single resource type.

We show that the transformation achieves good approximation for the d-RESOURCE-SCHEDULING problem if the solution for the 1-RESOURCE-SCHEDULING problem satisfies certain property.

Theorem 2. For any transformed instance I of the 1-RESOURCE-SCHEDULING problem, if a moldable task scheduler M 1 under a single resource type produces a makespan

T M1 ≤ c • L min (d) , (4)
then the algorithm TF + M 1 is c-approximation for the d-RESOURCE-SCHEDULING problem.

Before proving the approximation, we first show that the schedule obtained for I via the transformation strategy is valid and that the makespan for I is preserved. Lemma 2. Any valid solution by scheduler M 1 for I transforms back to a valid solution by algorithm TF + M 1 for I, and T TF+M1 = T M1 .

Proof. According to Steps (1) and (3) of the transformation, the execution time for each task j in I is the same as that of j in I , i.e., t j ( p j ) = t j (q j ). Hence, the makespan is equal for both I and I , since the corresponding tasks also have the same starting time, i.e., s j = s j .

If the schedule for I is valid, i.e., j ∈J t q j ≤ Q ∀t, then we have j∈Jt p

(i) j = j∈Jt q j •P (i) Q ≤ P (i)
Q j ∈J t q j ≤ P (i) ∀i, t, rendering the schedule for I valid as well.

The following lemma relates the makespan lower bound of the transformed instance to that of the original instance.

Lemma 3. L min (d) ≤ L min (d).
Proof. We will show that given any resource allocation p for I, there exists an allocation q(p) for I such that L (q(p), d) ≤ L(p, d). Thus, for p d min that leads to L min (d), there is a corresponding q(p d min ) that satisfies L (q(p d min ), d) ≤ L(p d min , d) = L min (d), and therefore

L min (d) = min q L (q, d) ≤ L (q(p d min ), d) ≤ L min (d).
Consider any resource allocation p = ( p 1 , p 2 , • • • , p n ) T for I. For each task j, let k j denote its dominating resource type in terms of the proportion of resource used, i.e., k j = arg min i p (i) j P (i) . We construct q(p) = (q 1 , q 2 , • • • , q n ) T for I by setting, for each task j , an allocation q j = p (k j ) j

•Q P (k j ) . As P (kj ) divides Q, q j is an integer and hence a valid allocation.

According to Step (1) of the transformation, the execution time of task j in I satisfies t j (q j ) = t j (( p (kj ) j

• P (i)

P (kj ) ) i=1•••d ) ≤ t j ( p j ) .
The inequality is because p

(i) j ≤ p (k j ) j •P (i) P (k j )
∀i, which we get by the choice of k j and the integrality of p

(i)
j , and because we assumed that the execution time is a non-increasing function of each resource allocation (in Section III). As a result, the area of each task j in I also satisfies

a j (q j ) = q j Q t j (q j ) ≤ p (kj ) j P (kj ) t j ( p j ) ≤ d i=1 p (i) j P (i) t j ( p j ) = a j ( p j ).
Hence, the maximum execution times and the total areas for the two instances I and I satisfy t max (q(p)) = max j t j (q j ) ≤ max j t j ( p j ) = t max (p) and A (q(p)) = j a j (q j ) ≤ j a j ( p j ) = A(p). This leads to L (q(p), d)

= max A (q(p)) d , t max (q(p)) ≤ max A(p) d , t max (p) = L(p, d).
(Proof of Theorem 2). Based on the above results, we can derive:

T TF+M1 = T M1 (Lemma 2) ≤ c • L min (d) (Equation (4)) ≤ c • L min (d) (Lemma 3) ≤ c • T OPT .
(Lemma 1)

D. Rigid Task Scheduling

This section presents strategies to schedule rigid tasks under fixed resource allocations. The strategies include both listbased and pack-based scheduling. The results extend the theoretical analyses of single-resource-type scheduling [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF] to account for the presence of multiple resource types.

1) List Scheduling: We first present a list-based scheduling strategy for a set of rigid tasks under multiple resource types. A list-based algorithm arranges the set of tasks in a list. At any moment starting from time 0 and whenever an existing task completes execution and hence releases resources, the algorithm scans the list of remaining tasks in sequence and schedules the first one that fits, i.e., there is sufficient amount of resource to satisfy the task under each resource type. Algorithm 3 presents the list scheduling strategy LS d with d resource types, and it extends the algorithm presented in [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] for scheduling under a single resource type. The complexity of the algorithm is O(n 2 d), since scheduling each task incurs a cost of O(nd) by scanning the taskList and updating the resource availability for the times in sortedT imeList.

The following lemma shows the performance of this list scheduling scheme. Lemma 4. For a set of rigid tasks with a resource allocation matrix p, the list scheduling algorithm LS d achieves, for any

T LS d (p) ≤ 2s • L(p, s) .
(

) 5
Proof. We will prove in the following that

A(p) = TLS d (p) t=0 d i=1 U (i) t dt = T LS d (p) 2 t=0 d i=1 U (i) t + U (i) t dt ≥ T LS d (p) 2 .
2) Pack Scheduling: We now present a pack-based scheduling strategy. Recall that a pack contains several concurrently executed tasks that start at the same time and the tasks in the next pack cannot start until all tasks in the previous pack have completed. Algorithm 4 presents the pack scheduling strategy PS d with d resource types. It extends the algorithm presented in [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF] for scheduling under a single resource type. Specifically, the tasks are first sorted in non-increasing order of execution times (which are fixed due to fixed resource allocations). Then, they are assigned one by one to the last pack if it fits, i.e., there is sufficient amount of resource under each resource type. Otherwise, a new pack is created and the task is assigned to the new pack. The complexity of the algorithm is O n(log n + d) , which is dominated by the sorting of the tasks and by checking the fitness of each task in the pack.

The following lemma shows the performance of this pack scheduling scheme.

Lemma 5. For a set of rigid tasks with a resource allocation Algorithm 4: Packing Scheduling Strategy PS d Input: Resource allocation matrix p for the tasks and resource limit

P (i) ∀i Output: Set of packs {B 1 , B 2 , • • • } containing
T PS d (p) ≤ (2s + 1) • L(p, s) . (6)
Proof. We will prove in the following that T PS d (p) ≤ 2A(p) + t max (p), which will then lead to

T PS d (p) ≤ (2s + 1) • max A(p) s , t max (p) = (2s + 1) • L(p, s
). Suppose the algorithm creates M packs in total. For each pack B m , where 1 ≤ m ≤ M , let A m denote the total area of the tasks in the pack, i.e., A m = j∈Bm a j ( p j ), and let T m denote the total execution time of the pack, which is the same as the execution time of the longest task in the pack, i.e., T m = max j∈Bm t j ( p j ).

Consider the time when the algorithm tries to assign a task j to pack B m and fails due to insufficient amount of i-th resource, whose remaining amount is denoted by p (i) . As the tasks are handled by decreasing execution time, we have A m ≥ 1 -p (i) P (i) t j ( p j ). Also, because task j cannot fit in pack B m , it means that its allocation p (i) j on resource i is at least p (i) . This task is then assigned to pack B m+1 , so we have A m+1 ≥ a j ( p j ) ≥ p (i) P (i) t j ( p j ). Since task j is the first task put in the pack and all the following tasks have smaller execution times, we have T m+1 = t j ( p j ). Hence,

A m + A m+1 ≥ t j ( p j ) = T m+1 .
Summing the above inequality over m, we get

M m=2 T m ≤ 2 M m=1 A m = 2A(p).
Finally, as the longest task among all tasks is assigned to the first pack, i.e., T 1 = t max (p), we get the makespan

T PS d (p) = M m=1 T m ≤ 2A(p)+t max (p).

E. Putting Them Together

This section combines various strategies presented in the previous sections to construct several moldable task scheduling algorithms under multiple resource types. Two solutions are presented for the d-RESOURCE-SCHEDULING problem under each scheduling paradigm (list vs. pack) depending on if the problem is solved directly or indirectly via a transformation to the 1-RESOURCE-SCHEDULING problem.

The following shows the combinations of the two solutions:

Direct-based solution: RA d (d) + R d Transform-based solution: TF + RA 1 (d) + R 1
Here, RA denotes the resource allocation strategy (Algorithm 1), TF denotes the transformation strategy (Algorithm 2), and R denotes the rigid task scheduling strategy LS or PS (Algorithm 3 or 4). Four algorithms can be resulted from the above combinations, and we call them D(IRECT)-PACK, D(IRECT)-LIST, T(RANSFORM)-PACK and T(RANSFORM)-LIST, respectively.

We point out that when the LCM of all the P (i) 's is dominated by P max (e.g., when P (i) 's are powers of two), the transform-based solution will reduce the overall complexity of the direct-based solution exponentially, thus significantly improving the algorithms' running times. The approximation ratios of the transform-based solutions, however, will not be compromised. The following theorem proves the ratios of these algorithms. Proof. We prove the approximation ratios for the two packbased scheduling algorithms. The proof for the list-based algorithms is very similar and hence omitted. For T-PACK (TF + RA 1 (d) + PS 1 ): Applying PS 1 to the transformed instance using q d min found by RA 1 (d), we have The proof on the tightness of these bounds omitted due to space constraint and can be found in the full version [START_REF] Sun | Scheduling parallel tasks under multiple resources: List scheduling vs. pack scheduling[END_REF].

T RA1(d)+PS1 = T PS1 (q d min ) ≤ (2d + 1) • L (q d min , d) = (2d + 1) • L min (d) from

V. EXPERIMENTS

In this section, we conduct experiments and simulations whose goals are twofold: (i) to validate the theoretical underpinning of moldable task scheduling; and (ii) to compare the practical performance of various list-and pack-scheduling schemes under multiple resource types.

Experiments are performed on an Intel Xeon Phi Knights Landing (KNL) machine with 64 cores and 112GB available memory, out of which 16GB are high-bandwidth fast memory (MCDRAM) and the rest are slow memory (DDR). MCDRAM has ≈5x the bandwidth of DDR [START_REF] Sodani | Knights Landing: Secondgeneration Intel Xeon Phi product[END_REF], thus offering a higher data-transfer rate. The applications we run are from a modified version of the Stream benchmark [START_REF] Mccalpin | STREAM: Sustainable memory bandwidth in high performance computers[END_REF] configured to explore the two available resources of KNL (cores and fast memory) with different resource allocations. Simulations are further conducted to project the performance under more resource types using synthetic workloads that extend some classical speedup profiles.

A. Evaluated Algorithms

Each algorithm in Section IV-E is evaluated with two variants, depending on if it is list-based or pack-based. A listbased algorithm can arrange the tasks according to two widely applied heuristics: Shortest Processing Time First (SPT) and Longest Processing Time First (LPT), before scheduling them as shown in Algorithm 3. For pack-based scheduling, Algorithm 4 applies the Next Fit (NF) heuristic, which assigns a task to the last pack created. First Fit (FF) is another heuristic that assigns a task to the first pack in which the task fits. From the analysis, the approximation ratio can only be improved with this heuristic. Coupling these heuristics with the two solutions (direct vs. transformation) under the two scheduling paradigms (list vs. pack), we have a total of eight scheduling algorithms that we will evaluate in the experiments.

B. Application Profiling

In order to manage the fast memory as a resource, we first configure the KNL machine in flat mode [START_REF] Sodani | Knights Landing: Secondgeneration Intel Xeon Phi product[END_REF], where MCDRAM and DDR together form the entire addressable memory. We will also explore MCDRAM in cache mode later (see next subsection). The applications in the Stream benchmark are then modified by allocating a specified portion of their memory footprints on MCDRAM (and the remaining on DDR), thereby impacting the overall data-transfer efficiency and hence the execution time. The profiles are obtained by varying both the number of cores (1-64) and the amount of fast memory (16GB divided into 20 chunks) allocated to each application and recording their corresponding execution times. In addition, we vary the total memory footprints of the applications to create tasks of different sizes.

Figure 2 shows the profiles of the triad application when its memory footprint occupies 100%, 80% and 60% of the fast memory, respectively. Similar profiles are also observed for the other applications (e.g., write, ddot) in the benchmark. First, we observe that the execution time is inversely proportional to the number of allocated cores, suggesting that the application has nearly perfect speedup. Also, the execution time reduces linearly as more fast memory is allocated to the point where the application's memory footprint fits entirely in fast memory; after that the execution time remains fairly constant since allocating additional fast memory no longer benefits the execution. The profiled data for different applications under various sizes are subsequently used to compute the schedules by different algorithms.

C. Experimental Results

In order to validate our theoretical analysis and to compare the performance of different algorithms, we implement a basic scheduler that executes the tasks according to the schedules given by these algorithms based on the application profiles. Each task is launched at the specified time using the specified amount of resources (cores and fast memory) on the KNL machine. If any required resource of a task is not available at start time because of the delays in the preceding tasks (possibly due to performance variations), the execution of the task will be correspondingly delayed until there are enough resources available. We expect the delay (if any) to be small for each task but the effect can accumulate throughout the course of the schedule. This additional overhead is assessed in our experiments.

Figure 3(a) shows the makespans of the eight scheduling algorithms normalized by the theoretical lower bound (Equation (1) with s = d; see also Lemma 1) while running 150 tasks. We have also varied the number of tasks but observed no significant difference in their relative performance. First, we can see that the scheduling overhead, which manifests as the difference between the theoretical prediction and the experimental result, is less than 10% for all algorithms. In general, list scheduling (left four) and pack scheduling (right four) have comparable performance despite that the former admits a better theoretical bound. Moreover, transform-based solutions fare slightly better than direct-based solutions due to the balanced resource requirements of different applications in the benchmark. Lastly, in line with the intuition and conventional wisdom, LPT and FF are effective for reducing the makespan for list and pack scheduling, respectively, except for the T-LIST algorithm, which incurs a larger overhead with the LPT variant in the actual execution. Figure 3(b) further compares the makespans of four transform-based algorithms when MCDRAM is not used in flat mode (in which case all data are allocated on the slow DDR memory), and when KNL is configured in cache mode (in which case MCDRAM serves as a last-level cache to DDR). In both cases, only one type of resource (i.e., cores) is scheduled, and as a result, the transformation produces the same solutions as the direct-based schedules. Not surprisingly, cores-only scheduling in flat mode has the worst makespan for all algorithms, since MCDRAM is completely unutilized in this case. Having MCDRAM as cache to DDR significantly improves the makespan, but due to interference from concurrently running applications, the makespan is still worse than scheduling both cores and MCDRAM in flat mode. The results confirm the benefit of explicitly managing multiple resource types for improving the application performance.

D. Simulation Results with More Resource Types

In this section, we conduct simulations to project the performance of list-based and pack-based scheduling algorithms under more resource types. We simulate up to four types of resources that could represent different types of components, such as CPUs, GPUs, fast memory, I/O bandwidth, all of which would be shared among different applications. The total amount of discrete resource for each type is set to be 64, 32, 16 and 8, respectively. Due to the lack of realistic application profiles under multiple-resource constraints, we generate synthetic workloads by extending two classical speedup functions (described in Section II-A) to model moldable applications:

• Extended Amdahl's law [1]: (i) 1/ s 0 + d i=1 si p (i) ; (ii) 1/ s 0 + 1-s0 d i=1 p (i) ; (iii) 1/ s 0 + max i=1..d si p (i) .
• Extended power law [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF], [START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2? J. Instruction-Level Parallelism[END_REF]

: (i) 1/ d i=1 si (p (i) ) α i ; (ii) d i=1 (p (i) ) αi ; (iii) 1/ max i=1..d si (p (i) ) α i .
The extension of both speedup laws comes in three different flavors (i.e., sum, product, max), characterizing how allocations of different resource types work together to contribute to the overall application speedup (i.e., sequential, collaborative, concurrent). In the simulations, we generate 150 tasks, each randomly selected from the six extended profiles. The sequential fraction s 0 is uniformly generated in (0, 0.2], and the parallel fraction s i for each resource type i is uniformly generated in (0, 1] and normalized to make sure that d i=1 s i = 1 -s 0 . The parameter α i is uniformly generated in [0.3, 1). The total work of a task is chosen uniformly from a range normalized between 0 and 1 (the relative performance of the algorithms is not affected by the normalization).

Figure 4 plots the performance distributions of the scheduling algorithms with up to four resource types. Each boxplot is obtained by running 100 instances. Only LPT (for list) and FF (for pack) are included, since they have better overall performance. First, we observe that the normalized makespans indeed increase with the number of resource types, corroborating the theoretical analyses, although they are far below those predicted by the worst-case approximation ratios. Also, listbased schedules now produce consistently smaller makespans compared to the pack-based ones, which we believe is due to the larger variability in the simulated task profiles than that of the Stream benchmark. This allows the list-based schedules to explore more effectively the gaps between successive task ex-ecutions (as reflected by the theoretical bounds). However, the makespan difference between the two scheduling paradigms becomes smaller with more resource types, suggesting that pack-based scheduling is promising when more resource types are to be managed. Finally, transform-based solutions are superior compared to the direct-based ones in terms of both makespan and algorithm running time (for which there are 2-3 orders of magnitude difference with more than two resource types). In general, for workloads with balanced resource requirements, transform-based scheduling is expected to offer both fast and efficient scheduling solutions.

Lastly, we point out that it may seem in Figure 4(a) that the makespan increases with more resource types. In fact, it is the ratio to the optimal solution (or lower bound), not the makespan itself, that increases with d. In practice, the value of that optimal solution will decrease with more resource types, since there is more room for optimization. Hence, scheduling more resource types potentially improves the overall makespan, which is what we observed experimentally when managing one and two types of resources as shown in Figure 3(b).

VI. CONCLUSION AND FUTURE WORK

List scheduling and pack scheduling are two scheduling paradigms that have been studied extensively in the past. While most prior works focused on scheduling under a single resource type, in this paper we joined a handful of researchers on scheduling under multiple-resource constraints in these two scheduling paradigms. Our analyses and evaluation results show that scheduling becomes more difficult with increasing number of resource types, but considering all available resources is essential for improving the application performance. Despite the better theoretical bound of list scheduling, pack scheduling has been shown to have comparable or, in some scenarios, even better performance, especially when more types of resources are included in the scheduling decision. The results offer useful insights to the design of emerging architectures and systems that need to incorporate multiple dimensions in the resource management.

Future work will be devoted to the design of improved list or pack scheduling algorithms (or any other practical algorithms beyond the two scheduling paradigms) with multipleresource constraints. An immediate open question is whether the 2d-approximation for list scheduling can be improved, e.g., to (d+1)-approximation as proven by Garey and Graham for rigid tasks [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF], which is equivalent to Phase 2 of our list-based algorithm but with fixed resource allocation. Given our list algorithm's lower bound of 2d for moldable tasks (Theorem 3), any improvement will likely be achieved through the design of more sophisticated resource allocation strategies (Phase 1) or through a more coupled design/analysis of the two phases. Prior work [START_REF] Mounié | A 3/2-approximation algorithm for scheduling independent monotonic malleable tasks[END_REF] on scheduling under a singleresource type has shed light on some possible directions (e.g., by using dual approximation).

Figure 1 .

 1 Figure 1. An example of list scheduling and pack scheduling for a same set of tasks under a single-resource constraint.

Theorem 1 .

 1 If a rigid task scheduling algorithm R d that uses the resource allocation matrix p d min obtained by the strategy RA d (d) produces a makespan

2 )

 2 Solve the 1-RESOURCE-SCHEDULING instance I ; (3) Transform 1-RESOURCE-SCHEDULING solution S back to d-RESOURCE-SCHEDULING solution S;

Theorem 3 .

 3 The list-based algorithms (D-LIST and T-LIST) are 2d-approximations and pack-based algorithms (D-PACK and T-PACK) are (2d + 1)-approximations. Moreover, the bounds are asymptotically tight for the respective algorithms.

  For D-PACK (RA d (d) + PS d ): Using p d min found by RA d (d), we have T PS d (p d min ) ≤ (2d + 1) • L(p d min , d) = (2d + 1) • L min (d) from Lemma 5 (by setting s = d). Then, based on Theorem 1, we get T RA d (d)+PS d ≤ (2d + 1) • T OPT .

  Lemma 5 (again by setting s = d). Then, based on Theorem 2, we get T TF+RA1(d)+PS1 ≤ (2d+1)•T OPT .

Figure 2 .Figure 3 .

 23 Figure 2. Profiles of the triad application in Stream benchmark when its memory footprint occupies 100%, 80% and 60% of the entire fast memory.

Figure 4 .

 4 Figure 4. (a) Normalized makespans and (b) running times of four scheduling algorithms with up to four different resource types.

Table I .

 I List of Notations.

Algorithm 1 :

 1 Resource Allocation Strategy RA d (s) Input: Set of n tasks, execution time t j ( p) ∀j, p and resource limit P (i) ∀i Output: Resource allocation matrix p s min = arg min p L(p, s) Linearize all P resource allocation vectors for task j in an array res alloc and sort it in non-decreasing order of task execution time;

	1 begin
	2	P ← d i=1 (P (i) +1);
	6	admissible allocations j ← list();
	7	min area ← ∞;
	8	for h = 1 to P do
	9	p ← res alloc(h);
	10	if a j ( p) < min area then
	11	min area ← a j ( p);
	12	admissible allocations j .append( p);
	13	end
	14	end
	15	p j ← admissible allocations j .last element();
	28	end
	29 30	if A s ≥ tmax then break;
	38	end
	39	end
	40 end

3

A ← 0; 4 for j = 1 to n do 5 16

A ← A + a j ( p j ); 17 end 18 Build a priority queue Q of n tasks with their longest execution time t j ( p j )'s as priorities; 19 L min = ∞; 20 while Q.size() = n do 21 k ← Q.highest priority element(); 22 p k ← admissible allocations k .last element(); 23 tmax = t k ( p k ); 24 L = max A s , tmax ; 25 if L < L min then 26 L min ← L; 27 p s min ← ( p 1 , p 2 , • • • , pn) T ; 31 end 32 admissible allocations k .pop last(); 33 Q.remove highest priority element(); 34 if admissible allocations k .nonempty() then 35 p k ← admissible allocations k .last element(); 36 A ← A + a k ( p k ) -a k ( p k ); 37 Q.insert element(k) with priority t k ( p k );

Algorithm 3 :

 3 List Scheduling Strategy LS d Input: Resource allocation matrix p for the tasks and resource limit P (i) ∀i Output: Starting time s j ∀j begin Arrange the tasks in a list taskList; sortedT imeList ← {0}; while taskList.nonempty() do t = sortedT imeList.pop f irst(); for j = 1 to taskList.size() do if task j fits at time t then Schedule task j at time t, i.e., s j = t; sortedT imeList.insert(s j + t j ( p j ));

	Update available resources for all times before
	s j + t j ( p j );
	end
	end
	end
	end
	parameter s ≥ 1, a makespan

  First, suppose the makespan satisfies T LS d (p) ≤ 2t max (p), then the claim holds trivially. Otherwise, we will show T LS d (p) ≤ 2A(p), thus proving the claim. To this end, consider any time t ∈ [0, for otherwise any active task at time t could have been scheduled by the algorithm at time t or earlier. Thus, we can express the total area as:

	Since t max (p) <	TLS d (p) 2 TLS d (p) 2 by our assumption, any task TLS d (p) . 2
	that is active at time t has not been scheduled at time t. Define U (i) t = j∈Jt (i) p j P (i) to be the total utilization for resource of type i at time t. Therefore, we should have
	∃i, s.t. U t + U (i)	(i)

T LS d (p) ≤ 2 • max t max (p), A(p) . For any s ≥ 1, it will then lead to T LS d (p) ≤ 2s • max t max (p), A(p) s = 2s • L(p, s).

], and define t = t + t ≥ 1,

  the tasks and starting times Sm for each pack Bm begin Sorted the tasks in non-increasing order of execution time t j ( p j ); Sm ← S m-1 + max j∈B m-1 t j ( p j ); end end end matrix p, the pack scheduling algorithm PS d achieves, for any parameter s > 0, a makespan

	m ← 1;
	B 1 ← ∅;
	S 1 ← 0;
	for j = 1 to n do
	if task j fits in pack Bm then
	Bm ← Bm ∪ {j};
	else
	m ← m + 1;
	Bm ← {j};

This assumption is not restrictive, as we can discard an allocation q j that satisfies p j q j and t j ( p j ) < t j ( q j ). This is because any valid schedule that allocates q j to task j can be replaced by a valid schedule that allocates p j to the task without increasing the execution time, thus rendering q j useless.

We do not allow fractional processor allocation (typically realized by timesharing a processor among several tasks) as assumed by some prior work.

ACKNOWLEDGEMENTS

We would like to thank Nicolas Denoyelle for sharing the code to run the modified Stream benchmark on KNL. This research is supported in part by the National Science Foundation under the award CCF 1719674. Finally, we thank the anonymous reviewers for useful comments.