Abstract The results indicate that iScheduling can improve both waiting time and overall turnaround time substantially for these workload classes, outperforming standard policies such as backfilling and moldable job scheduling. Efficiently executing resource-intensive parallel scientific applications in dynamic parallel and distributed production environments is a challenging problem. Performance depends on resource scheduling at several levels: job schedulers which multiplex different applications across limited system resources and application schedulers which request resources for their applications. Applications can experience large slowdowns in time-shared systems, or high wait times in space-shared systems, due to contention for these limited valuable resources. Part of the problem is that a limited set of shared resources can rapidly become 2 oversubscribed as the number of applications to execute increases. This is confirmed by several supercomputer workload studies [10] [11] [20] . However, we believe that inefficient resource allocation by job schedulers and inefficient resource utilization within the application further exacerbates this problem. The problem is that job schedulers for parallel machines are often built to optimize metrics that may not deliver the best possible application performance. For example, many job scheduling policies are geared to high resource utilization because large parallel machines are expensive, or fairness (e.g. firstcome-first-serve), or high throughput. In addition, job scheduling is static: job schedulers for parallel applications generally do not reconsider prior scheduling decisions. Another problem is that job scheduling may be minimally supported in distributed network environments. Without coordination, different application schedulers will make independent scheduling decisions that may lead to reduced application and system performance. Uncoordinated application schedulers may also encounter race conditions on shared resources. In addition, application schedulers typically select resources without regard for the negative impact this may have upon other applications. In some cases, application schedulers may even over-allocate resources with limited benefit to their application. This is particularly true when the end-user is performing application scheduling since it can be hard to manually determine the appropriate number of resources for applications with a high degree of variance or data-dependent behavior. We believe that the lack of performance delivered to applications is in part due to the functional gap between application scheduling and job scheduling. Application schedulers make resource allocation decisions solely on behalf of their application [3] [32] [33] . They exploit specific knowledge of the application to select resources that are predicted to yield performance that meets user objectives such as minimal response or completion time. In contrast, job scheduling takes a more global view and makes resource allocation decisions across a set of jobs [5] [9] [13] [15] [21] . Job scheduling approaches span space-sharing policies to time-sharing policies to combined approaches [35] . Each parallel application is assumed to be a black-box with little or no accompanying information. In this paper, we propose a novel integrated scheduling framework (iScheduler) that bridges the gap between application and job scheduling for parallel scientific applications. We assume that the job or application has already been decomposed into a parallel computation and that it has a special front-end (called an adaptive API) that will be described shortly. The most common model for iScheduler jobs is data parallel in which the parallel components are identical, though this is not a strict requirement. The iScheduler is an application-aware job scheduler as opposed to a general-purpose system scheduler. Application-aware means that the job scheduler can interact with the jobs as they are running. It dynamically controls resource allocation among a set of competing applications, but unlike a traditional job scheduler, it can interact directly with an application during execution to optimize resource allocation. In some cases, it can exploit 3 application-specific knowledge, e.g. it can use estimated execution time, and in others it makes more generic decisions. Application-awareness is achieved via the adaptive API. The iScheduler can be applied in two ways. A user-centric iScheduler can more effectively manage a pool of resources (e.g. a partition of a supercomputer or a cluster) for a set of related applications submitted by a single user. For example, many problems require the repeated execution of the same or similar applications such as parameter studies, monte-carlo models, and gene sequence comparison, in which results from each run are typically averaged for a final result, or input into subsequent runs, or simply collected as parts of the overall solution. Workload traces from supercomputer logs reveal a high degree of application repetition [30] and this has been confirmed by several informal surveys [8] and anonymized workload traces [11] . A system-centric iScheduler operates across a set of common applications submitted by different users. For example, domain-specific problem-solving environments (PSE) [2] [6] [19] [22] [27] can use the iScheduler to manage the resource allocation associated with each concurrent request (e.g. to solve a system of equations) submitted to a PSE. We have developed an iScheduler framework and applied it both to a supercomputer workload derived from trace data at several centers and to a stream of real parallel jobs that we have implemented. The results indicate that integrated scheduling improved both waiting time and the end-to-end finishing time of parallel applications when compared to several baseline scheduling policies including backfilling and moldable job scheduling, but over an order of magnitude improvement when compared to the default scheduling policy. The iScheduler The iScheduler is an application-aware job scheduler that is designed to exploit the advantages of application-and job-level scheduling. Traditional job scheduling is static: job schedulers for parallel applications generally do not reconsider prior scheduling decisions.The degree of interaction between a job scheduler and the application (or its scheduler) is minimal and usually consists of an initial resource request (e.g. the job wants P processors). In addition, if the initial resource request cannot be met, then the application must wait because there is often no mechanism to allow it to acquire resources later on, even if it could start with fewer resources. Finally, if some of the resources held by an application are needed by a higher priority application, then the job scheduler has no choice but to suspend the entire application. The iScheduler performs fluid resource management for an application (much like an application-level scheduler), but will perform resource management across a job stream (like a job-level scheduler). Such integration does not come for "free". It requires an API that provides application information (sensing) and the 4 ability to control the application's behavior (actuating). Sensing provides dynamic performance information such as per iteration execution cost, while actuating is used to take action on the application, e.g. adding or removing processors to it. Integrated scheduling requires application modification to support these sensing and actuating functions. The iScheduler makes scheduling decisions for a potentially dynamic collection of application instances across a resource pool, e.g. a cluster, parallel supercomputer, network of clusters, or computational Grid. It works in concert with application schedulers to make effective resource allocation decisions both statically and dynamically (Figure 1 ). In this paper, the resource on which we focus is processors. Unlike traditional scheduling approaches, resource management in the iScheduler is a fluid process in which resources may be allocated and deallocated throughout the lifetime of an application. iScheduler resource management is based on three core ideas: • cost prediction • adaptivity Figure 1: iScheduler architecture. iScheduler manages incoming application stream (shown as an application A i and its scheduler AS i ) and allocates resources across 16 CPUs. We have shown the application scheduler as decoupled from the application; however in some cases, the application scheduler may be embedded within the application. Application resource requirements (if known) and constraints may be provided -min is the required minimum amount of resource and ideal is the desired amount. There are two active applications (A 1 , A 2 ) and two queued applications (A 3 , A 4 ). Application A 1 has made a dynamic request for an additional 2 CPUs. iScheduler makes allocation decisions using information from all depicted sources. Cost prediction models allow the iScheduler to evaluate and assign candidate resources to its collective set of applications in a manner that meets performance objectives. It allows the iScheduler to assess the cost/ benefit of resource allocation and deallocation decisions. Adaptivity allows the application and the iScheduler to adjust their behavior in response to dynamic run-time events. It provides the iScheduler greater flexibility in making collective resource allocation decisions. Admission control is a decision that is made when a new application arrives to system. The iScheduler must decide whether to queue the application or to run it by admitting it into the system. This is particularly important when system resources are oversubscribed with respect to the application stream. When admitting an application, the iScheduler must ensure that there are sufficient resources for the application. This may require the iScheduler to take away resources from running applications. For example, suppose a parallel system contains 128 space-shared processors and a parallel application is running on 120 processors. Using traditional job schedulers, a newly arriving application requiring 16 processors would be queued (unless the new application had higher priority). Using a moldable job scheduling, the new job could be given the 8 free processors which would likely result in poor performance. In contrast, the iScheduler could draw 8 additional processors from the first application perhaps not affecting its run-time greatly, which would allow the new application to run. Also observe how this improves machine utilization relative to traditional job scheduling since the 8 processors are no longer idle. In many instances, there is a point of diminishing returns with respect to the amount of resources for many application classes, so the penalty of removing resources may not be substantial (see Figure 2 for some examples). The iScheduler makes resource management decisions as a function of predictive cost functions C, active applications AA (including their priority, performance history, age, current resource allocations and constraints, and pending resource requests if any), queued applications QA (including their priority, wait time, resource requirements and constraints), and available resources AR. The space of iScheduling deci- Figure 2 : Point of diminishing returns for (a) data parallel, (b) master-slave bag-of-tasks, and (c) pipeline applications (N is the problem size, P the # of processors). In a) and b), a parabolic shape is commonly seen. In a) the curve turns upwards as communication begins to offset any gains from parallelism. The constants depend on problem and network parameters. Similarly for b), the curve turns up when the overhead experienced by the master begins to dominate any gains. Lastly for c), suppose each stage can run in T i time serially, and the middle stage is parallel. Once T 1 or T 3 exceeds T 2 /P there is no benefit to adding more processors to the middle stage.  We have developed several policies for user-and system-centric iSchedulers that space-share processing resources with the goal of reduced completion time. These iSchedulers we have developed make resource allocation decisions when applications arrive and complete. The resource that is being managed is the number of processors. iScheduler fluid resource management policies will adjust resource consumption of both arriving and running applications. These policies come into play when there are insufficient resources to give all applications concurrent access to their ideal amount of resources. When an application arrives to the system, the iScheduler must decide whether to admit it into the system. If it cannot get its ideal resources an iScheduler can choose to "harvest" resources from running applications to enable it to run. Harvesting itself consists of several issues: when to harvest? from whom to harvest (the victims)? and how much to harvest? In this paper, we set the harvest parameter to the minimum resource amount (min) needed by the application. If this resource amount cannot be collected, then the application must be queued. An application cannot be harvested below its minimum resource requirements. When an application finishes, the iScheduler must decide how to distribute the available resources to both queued and possibly running applications. If minimizing wait time is desired, then preference should be given to queued applications increasing the degree of parallel job multiprogramming. iScheduler resource management policies have four components: control_policy, admission_policy, harvest_policy, and distribution_policy. The control_policy refers to global properties that all policies must respect. For example, for stability we may want to limit how many times an application can be harvested, or protect newly arriving applications from harvesting until they reach a certain age, or to insure that the benefit of an adaptive action outweighs its cost, etc. The harvest_policy determines the victim set and the amount that each application must relinquish. The distribution_policy determines what to do with the resources freed when an application finishes. In this paper, all distribution policies first ensure that the admission_policy is satisfied. In the large space of possible policies, we are exploring this set of options: 7 admission control policies achieve_mp (M): this policy will admit applications into the system FCFS to achieve a degree of multiprogramming at least equal to M. An application will be queued if M has been reached and insufficient free resources are available. never_harvest: do not harvest (but redistribution to running applications is allowed) even_harvest: this policy will try to harvest resources evenly from all running applications at each harvest request, irrespective of prior harvesting events. Processors are then taken from each application (one-at-a-time) in a round-robin fashion until the harvested allocation is satisfied. This policy only attempts to be fair within a single harvest event. fair_harvest: this policy is an extension of even_harvest and tries to extend the harvest policy across multiple harvest events. This policy tries to keep the number of harvest events experienced by all running applications the same. It does this by first computing the average number of harvest events suffered by the running applications. Only those applications below this average are candidates for release. long_harvest: this policy orders applications by their current run length (longest first). Processors are then taken from each application (one-at-a-time) in a round-robin fashion until the harvested allocation is satisfied. Only those applications with an age > T time units are candidate victims. T can be defined as the average age of all running applications. short_harvest 1 : this policy orders applications by the amount of run time left (largest first). Processors are then taken from each application (one-at-a-time) in a round-robin fashion until the harvested allocation is satisfied. Only those applications with an amount of time left > T time units are candidate victims. T can be defined as the average time left of all running applications. low_impact_harvest: this policy will try to harvest from the applications that are predicted to be least impacted. Impact is determined by the % of resources that an application will have relative to its desired ideal amount. For example, an application that has 2 resources allocated with its ideal resources = 4 will be much greater impacted if a resource was taken away than an application with 8 resources allocated with its ideal resources = 9 (1/4 vs. 7/9). The applications are ordered by the impact metric and resources are selected using this ordering. favor_running: this policy will distribute resources to running applications using the inverse of the harvest policy. For, example, if low_impact_harvest was selected, this policy will redistribute to applications that would be the most favorably impacted. favor_queued: this policy will distribute resources to queued applications to admit them into the system first. In this paper, the iScheduler policy options we have examined are even_harvest and low_impact_harvest with favor_running and favor_queued options for different values of M. We call these policies, Even-H-FR, Even-H-FQ, Low-Imp-FR, and Low-Imp-FQ. The general iScheduler logic and an example of the 1. This policy may not be feasible for all applications since the amount of time left may not be known. However, for some parallel applications (e.g. direct solvers) this information can be known. In other cases, historical run-time information can be possibly used. This becomes feasible for iSchedulers that are scheduling parallel job streams of the same type and can collect and exploit this information on-line. 8 Even-H-FQ heuristic is shown (Figure 3) . We compared these iScheduler policies against three baselines. The baselines do not allow any modification to the amount of resources held by running applications: Policy IDEAL-ONLY (no adaptation on running applications or arriving applications): arriving application is given its ideal resources; if ideal is not available, application is queued using FCFS. Policy MOLDABLE (no adaptation on running applications): arriving application is given max (min, ideal) resources; if min is not available, application is queued using FCFS. Policy IDEAL-BACKFILL. Backfilling will be used to relax FCFS if queue jumping does not delay applications. Each application is granted its ideal resources. iScheduler-aware applications must support an adaptive API to enable iSchedulers to implement fluid resource management policies. Otherwise, there are no other special requirements for applications: they by shaded circle and has (min, ideal) processor requirements. Jobs J 1 and J 2 arrive first to the idle machine and are allocated their ideal resources each (1). Later in (2), J 3 arrives with a min requirement of 4, yet no resources are available. Under Even-H, 2 resources are harvested from J 1 and J 2 allowing J 3 to run. After this, J 4 also arrives with a min of 4 but must be queued as it is not possible to harvest 4 resources without suspending the other jobs. Finally in (3), job J 3 finishes freeing 4 resources. Using FQ, these resources are given to the queued job J 4. (1) (2) 9 can use threads, message-passing, etc. Applications are presumed to have a run length that makes iScheduling profitable (minutes or hours as opposed to a few seconds). Consequently, they are assumed to be iterative, with adaptation events initiated and cost information collected, at iteration boundaries. The iScheduler will evaluate the cost and benefit of adaptive actions as part of its scheduling decisions. Clearly, the provision of adaptation within the application implies that it must be malleable with respect to system resources. Not all applications are capable of this requirement and thus would not be suitable for iScheduling. However, many parallel scientific applications, can be written or modified to work in this manner. In a recent survey, it was reported that at least 70% of supercomputer jobs could be malleable [7] . An important question is: why would an application-writer spend the effort to implement adaptivity, particularly the removal of resources? The first point to stress is that the provision of resource release may actually benefit (or at least not harm) the performance of the application. There are at least four reasons why resource release may be beneficial: (1) resource release may prevent application suspension due to the presence of higher priority jobs or a resource owner reclaiming resources, (2) resource release may not harm performance at the knee of the performance curve (Figure 2 ), (3) better resources may become available dynamically and weaker resources could be released, and (4) Another argument to make is that if the programmer is willing to expend the effort to have resources dynamically added to their application (a clear advantage in many cases), then the same adaptation code can be easily transformed to allow for resource release because issues relating to data redistribution, communication, load rebalancing, are the same in both cases. We have divided the adaptive API into two components, sensing and actuating. The resources sensing function provides information that can help the iScheduler make resource allocation decisions. The minimum value is particularly important as it serves as a constraint on resource allocation: the application must have at least the minimum amount to run. The ideal amount is a hint and is not required, though some application schedulers may be available to provide accurate values for it. For example, it can be determined from the sensing functions for regular data parallel applications as will be shown. Actuating functions are used to adjust the resource consumption of applications in support of fluid resource management. Sensing provides useful information to the iScheduler that can be used in the actuating process. For example, the iScheduler can use dynamic sensing information to adjust or tune scheduling decisions. The actuating functions are as follows: actuating_cost_benefit (adaptation_method, num_procs, &cost, &benefit) The iScheduler invokes these functions within the application to control its resource usage. For example, it may seek to remove processors from an application in order to give them to another, perhaps newly arriving application. It may also allow an application to gain additional processors when they become available such as when an application finishes. These functions represent basic mechanisms for resource adaptation within the application. How these functions are used is a policy decision made by the iScheduler. Predicting the cost and benefit of adaptation to the application is an important ingredient in building efficient iSchedulers. The actuating_cost_benefit function exports this information to the iScheduler. Performance prediction is fundamental to the application model, the iScheduler, and the adaptive API. It answers the questions: how will the application perform on a given set of resources and what is the costbenefit of adaptation in support of fluid resource management? In prior research, we have had success predicting performance for three models common to parallel scientific applications that use message-passing: SPMD data parallel, pipelines, and master-slave bag-of-tasks using the Prophet system [32] . Prophet schedules parallel applications with the objective of reduced completion time. It has been successfully applied to a wide range of applications including parallel gene sequence comparison, electromagnetic scattering using finite elements, and image processing pipelines. Prophet predicts the optimal number of processors for a given parallel application by constructing cost functions that predict application performance. It explores a sequence of processor configurations to find the knee of the curve (Figure 2 ). Prophet was modified to export internal cost information to the iScheduler. This cost information includes application performance on a candidate set of resources and the minimum number of required resources. In addition, Prophet also contains models that accurately predict the cost and benefit of adding, removing, migrating, and dynamically load balancing processors [34] . The prediction model achieved high accuracy for both the cost and benefit of adaptation: within 10% for a large variety of applications. The latter two adaptation methods (migration and dynamic load balancing) will be particularly useful when the environment contains non-iScheduler-aware applications, a topic of future investigation. In Prophet, the cost models it constructs rely on information provided by the application in the form of For other applications such as threaded-parallel, the formulation is different. The accuracy of Prophet's cost models is generally high even for complex multi-phase applications. This callback information is used 2. Communication function shown is for a shared 10 base-T ethernet network in which bandwidth is shared among the p communicating processors (hence the dependence on p). In a shared environment, communication and computation cost depends on the amount of available bandwidth the CPU cycles respectively. to support the adaptive API. For example, is used to implement the exec_time function as part of the sensing API. This information is also used to help determine the cost and benefit of adaptation. Continuing with the data parallel example, the benefit of adding a processor can be determined by plugging p+1 into the equations above. The cost of adding a processor is more complex, but is determined, in part, by the cost of data communication. This can be computed using a communication cost function (e.g. but with comm_complexity replaced by the amount of data to be redistributed). The adaptation cost model relies on other parameters not shown here and is omitted for brevity, details may be found in [34] . We have used Prophet callbacks to implement part of the sensing functionality in support of the adaptive API. In addition, the resource requirements of the application are also provided by callbacks. For example, min_requirements reports the min resources needed and the ideal resources can be determined internally within Prophet via its scheduling algorithms. Both of these are returned by the resources sensing function to the iScheduler. This is treated as a hint to the iScheduler because all application schedulers will not be able to accurately provide this information. The Prophet integration demonstrated that existing schedulers can be incorporated into the iScheduler framework with minimal difficulty. To evaluate the potential of the iScheduler paradigm, we have built an iScheduler framework and used it to construct several user-centric and system-centric iSchedulers which both were evaluated by simulation. The framework is currently being used as part of a "live" scheduler for parallel Prophet jobs on cluster networks. Here we report results on the simulation experiments. The user-centric iSchedulers were applied to schedule a stream of parallel jobs submitted from a single user and use the Prophet scheduling system internally to generate cost information needed for the trace-driven simulation. These jobs were initially run on our small cluster (an ATM cluster of 8 Sparc 20 nodes) to generate real cost information. Simulation allows us to "run on" larger clusters (e.g. at least 64 nodes) with larger problem sizes to produce  We built user-centric iSchedulers for three data parallel applications, an iterative jacobi solver (STEN), gaussian elimination with partial pivoting (GE), and parallel gene sequence comparison (CL), the details of these applications are described elsewhere [32] . These applications were modified to operate with the iScheduler (i.e. they implement the adaptive API) and represent a useful initial test of the applicability of the paradigm: the applications were not master-slave, but message-passing programs. CL, in particular, is a real application. The workload consisted of instances of each application with differing problem sizes and run lengths, as would be expected in a pool of submitted jobs. This scenario would be appropriate for a related set of parallel jobs submitted by a user or the workload requests to a PSE that offered fixed parallel services [6] [22]. In the supercomputer workload traces we examined, jobs submitted from the same user generally fell into three categories: batch or simultaneous submission, one-job-at-atime submission, and overlapping submission. We modelled each of these cases by adjusting the interarrival rate of the application instances (P is the total number of processors, is the average run-time for all application instances given their ideal number of processors, is the average ideal number of processors for all application instances, and β is a constant): The values for and were determined by Prophet.  and CL are equally likely. On our Sparc cluster running 100 Mb ethernet, we also determined the cost of shipping M bytes of data to be approximately: 1+ .00009M. For an adaptive event (either add or remove), data is first sent to a master processor and then redistributed. The amount of data (M) moved is the following: STEN: 2N 2 *8/P, GE: 2N 2 *8/P, and CL: 2NumSourceSeqs*SeqBlockSize/P For example, the overhead of removing a processor for STEN with N=128 at P=4 would be approximately 7 sec as compared with 1289 sec of runtime. The cost of adding is a little higher since process creation is needed, but this is a few hundred milliseconds at worst. An issue for future investigation is the issue of how iScheduling will scale to large, possibly multiphase applications that may be dynamic or irregular in structure. There is nothing within the paradigm in terms of mechanism that precludes extension to larger applications, but it is likely that new iScheduling policies will be needed. For example, it is possible that different iScheduling policies might be required for distinct phases of the application. The ability to add and release resources will be particularly useful for applications with different resource requirements in different phases. For irregular data-dependent applications, the minimum and ideal number of resources may also be data-dependent. Since these values are provided by the resources sensing function, this function can be programmed to be return values based on the input data. We built a system-centric iScheduler and used supercomputer center traces from the SDSC IBM SP2 (128 nodes), LANL SGI Origin 2000 (2048 nodes), and CTC IBM SP2 (512 nodes) to generate workloads [11] . Our model generates synthetic job traces by modelling the statistics of these published traces in terms of job interarrival times, job size, and job run times. We observed that for interarrival, more jobs arrive to RT ideal =244800 sec 15 the system during the day than during the night ( Figure 5 ). In order to capture the differences in the arrival rates, we used a non-stationary poisson process to model the job interarrival times in which the arrival rate λ is a function of time. The interarrival times are generated from an exponential distribution, the mean of which, 1/λ, varies according to the (simulated) time of day ( Figure 6 ). The x-axis represents the bins into which the interarrival times are placed. Each bin is 500 seconds in duration. Most of the interarrival times fall into the first bin, which indicates that most jobs arrive within 500 seconds of the preceding job. While the fit is not perfect, it captures the initial spike and tail-off effect. For our workload model, the size of a job is characterized by the number of processors it requests. In the actual workload traces, there are a few job sizes that are very common. The common job sizes are 1, and the power-of-two sizes 2, 4, 8, 16, 32, and 64. All other job sizes occur infrequently. For our simulated workloads, we use a discrete probability distribution that reflects the job sizes in an actual workload (Figure 7 ). Job run times have been modelled by a Weibull distribution (Figure 8 ). The figure shows a histogram of all job run times from the SDSC workload plotted against the Weibull distribution. Like the histograms for the interarrival times, the bin sizes are 500 seconds. Most jobs have short run times, while a few jobs run for very long periods of time. We use a single Weibull distribution with estimated shape parameter α and scale parameter β to model job run times for our simulated workloads. Each generated job in the trace has an arrival time (Figure 6 ), an ideal number of processors ( Figure   7 ), and an execution time given its ideal number of processors (Figure 8 ). For each application in a trace, we know how long it will take provided it is given its ideal or desired resources. We assume these are the values available in the trace via Figure 8 or Table 1 . However, for several scheduling policies including MOLDABLE and iScheduling policies, the execution time must be adjusted if an amount of resources less than the ideal is granted. Furthermore, the cost of harvesting must also be included since the application is suspended while resource re-allocation is being performed. For the experimental applications, an accurate measure of adaptation overhead has been developed [34] and was incorporated into simulation of the user-centric iSchedulers. Adaptation overhead is highly applicationdependent. It depends upon the amount of data transferred to achieve load balance which in turn depends on the problem size and number of processors. It includes the cost of data redistribution on the cluster network and process creation (for adding processors to the application). However, for the supercomputer workload traces, the jobs are essentially black boxes so this overhead cannot be known. However, the average run-length of these applications is in the 1000's of seconds and we have determined that adaptation overhead is typically on the order of a few seconds at worst [34] . In addition, our results indicate that the number of adaptive events is fairly small (1-3 per application). The small jobs are typically single CPU jobs (ideal = min = 1) which means they do not suffer adaptations, but can benefit from them. Therefore, the overhead is ignored for the system-centric iScheduler simulation, but is included for the user-centric iScheduler simulation. In addition, the minimum amount of CPU resources is also not available from the traces. Instead, we set this as a parameter, min_%_of_ideal, which sets the minimum number of required resources as a percentage of its ideal. For example, if min_%_of_ideal is 10%, and ideal was 100, then min would be 10. We vary this parameter in generating the workload traces. Adjusting application run length as a function of the number of resources is also an issue for the supercomputer jobs since they are black boxes. To address this issue, we have implemented two common execution models within the simulation, (i) linear and (ii) parabolic. The linear model does not consider communication and assumes that execution time is linear in P. The parabolic model assumes there is communication and that the ideal number of processors (P ideal ) is the true minimum execution time. This leads to the classic parabolic shape of execution time vs. processors (Figure 2 ). The real parallel applications are 17 parabolic, so this model is used for the user-centric iScheduler. The execution time for both models is as follows (P is the number of processors): If P changes during the execution of the application (if iScheduling is enabled), then these functions are applied for each value of P over the appropriate duration. We examine three basic questions in this study. First, does the iScheduling paradigm provide a performance benefit over baseline policies? Second, what is the most effective iScheduling policy given the large space of options. Third, what is the sensitivity of iScheduler performance to workload and system characteristics. We determined the performance sensitivity to M, the degree of multiprogramming, and to min_%_of_ideal, the minimum allowable % of ideal resources. In general, M will be varied from 3,6,9,12, and no_limit, and min_%_of_ideal from 50%, 40%, 30,%, 20%, and 10% of ideal. We generated 100 traces each containing 10000 jobs for each simulation experiment. The values presented are the average of the 100x10000 jobs. In the initial comparison, the baselines, IDEAL-ONLY, IDEAL-BACKFILL, and MOLDABLE, are compared against the simplest harvest-based policy, Even-H-FQ to see whether harvest-based policies are competitive with standard policies (Figure 9 ). The simulated machine contains 128 processors. We show results for both the linear and parabolic execution models. To enable a fair comparison with the baselines, M is set to be no_limit for Even-H-FQ, as this is the default settings for the baselines. It is evident immediately that IDEAL-ONLY performs quite badly with respect to wait time since it requires waiting for the ideal number of resources in a FCFS manner. Since the waiting time of IDEAL-ONLY dominates the total time (wait time + execution time), we omit it from the remaining graphs in Figure 9 as it is significantly worse than the other policies (we will return to this policy at the end of this section). The results show that Even-H-FQ achieved significantly lower waiting time than all of the baselines, but that execution time goes up because applications may be run with fewer resources under iScheduling. However, total completion time is better for iScheduling for certain values of min_%_of_ideal (larger values), but not for all values. This establishes that iScheduling (at least, Even-H-FQ) performs favorably for certain values of M and We now compare several harvest-based policies head-to-head. The comparative performance of the scheduling policies did not differ significantly between the linear and parabolic application execution models. Therefore in the remaining graphs for the system-centric iScheduler, we present results for the linear model only. We show waiting time and total time (waiting time + execution time) as the key metrics of interest. In the first set of results, we compare the waiting time under the four scheduling policies and their sensitivity to the degree of multiprogramming M (Figure 10 ). The results indicate that when min_%_of_ideal is 50%, *-FQ outperforms *-FR for M=3 and M=6. When it is 40%, FQ outperforms FR for M=3, 6, and 9. When it is 30%, *-FQ outperforms FR for M=3, 6, 9, and 12. The trend is clear: as min_%_of_ideal decreases, *-FQ outperforms *-FR for a wider range of M. The reason is that when min_%_of_ideal decreases, more jobs are likely to be eligible to enter the system, hence *-FQ is able to exploit this opportunity more easily. In general, as M increases for all policies, the waiting times decrease since the system is more likely to admit jobs onto the machine. When M increases to the point of no_limit, then the waiting times all converge to the same small value. The reason is that when a job finishes, the scheduling policies first try to satisfy the constraint on M, whether it is *-FR or *-FQ. Once the M constraint has been met, then either running or additional queued jobs are considered. So a value of no_limit is essentially the same as *-FQ. The performance of Low-Imp-* is slightly better than Even-H-* which is not surprising considering that it considers the impact on the harvested application. However, the performance is similar enough to suggest that simple policies such as Even-H-* are effective. However, it is clear that the FQ option reduces wait time. The next metric to observe is the total completion time dependence on M (Figure 11 ). The *-FR policies achieve better overall performance when compared with *-FQ as M increases. As M increases, the *- However, if reduced total time is desired, then either scheduling policy with the FR option will generally perform better than FQ at high degrees of multiprogramming M. The results suggest we should be running at high M since this yields reduced total time. FR is superior to FQ at high M since a high value of M admits more jobs into the system which in turn means that many jobs will be running below their ideal number of processors. Therefore, a distribution strategy that will favor these running jobs is better than giving additional greater priority to queued jobs (a large M already favors queued jobs to some extent). The next question we investigated was the comparative performance of the scheduling policies as a function of min_%_of_ideal. First, we show the waiting time as min_%_of_ideal is varied for fixed values of M (Figure 12 ). The results show that in general as min_%_of_ideal decreases, the waiting times for the *-FQ policies decrease. This trend is also observed for *-FR under low degrees of multiprogramming, but as the degree of multiprogramming increases for *-FR policies, a decrease in min_%_of_ideal leads to higher waiting times. The reason is that as min_%_of_ideal decreases there are more running jobs that are eligible to receive additional resources particularly for larger M. Hence, once M is satisfied, *-FR is more likely to distribute resources to running jobs, increasing the wait times of jobs on the queue. The next metric to observe is the total completion time dependence on min_%_of_ideal ( Figure 13
Weissman et al. REF describe an application-aware job scheduler that dynamically controls resource allocation among concurrent jobs, with processes sending data to the root node for data redistribution.
Integrated Scheduling: The Best of Both Worlds
Journal of Parallel and Distributed Computing
Computer Science