Adaptive resource allocation with different numbers of machine nodes provides more flexibility and significantly better potential performance for local job and grid scheduling. With the emergence of parallel computing in every-day life on multi-core systems, such schedulers will likely increase in practical relevance. A major reason why adaptive schedulers are not yet practically used is lacking knowledge of the scalability curves of the applications. Existing white-box approaches for scalability prediction are too expensive to apply them routinely. We present ADEPT, a speedup and runtime prediction tool, which is inexpensive and easy-to-use. ADEPT employs a black-box model and can be practically applied at large scale without user or administrator involvement. ADEPT requires neither program analysis and measurements nor user guesses but makes highly accurate predictions with only few observations of application runtime over different numbers of nodes/cores. ADEPT performs efficient model fitting by introducing an envelope-derivation technique to constrain the search. Additionally, ADEPT is capable of handling deviations from the underlying model by detection and automatic correction of anomalies via a fluctuation metric and by considering specific scalability patterns via multi-phase modeling. ADEPT also performs reliability judgment with potential proposal for placement of additional observations. Using MPI and OpenMP implementations of the NAS benchmarks and seven real applications, we demonstrate the effectiveness and high prediction accuracy of ADEPT for both speedup and runtime prediction, including interpolative and extrapolative cases, and show the capability of ADEPT to successfully handle special cases.

QoS criteria in cloud computing require guarantees about application runtimes, even if CMP servers are shared among multiple parallel or serial applications. Performance of computation-intensive application depends significantly on memory performance and especially cache performance. Recent trends are toward configurable caches that can dynamically partition the cache among cores. Then, proper cache partitioning should consider the applications' different cache needs and their sensitivity towards insufficient cache space. We present a simple, yet effective and therefore practically feasible black-box model that describes application performance in dependence on allocated cache size and only needs three descriptive parameters. Learning these parameters can therefore be done with very few sample points. We demonstrate with the SPEC benchmarks that the model adequately describes application behavior and that curve fitting can accomplish very high accuracy, with mean relative error of 2.8% and maximum relative error of 17%.

Grid schedulers which need to decide on which sites the jobs are best allocated require controlled and predictable service. Fair-share scheduling has become widely used but lacks a formal model and depends on the current machine load. Existing approaches for response-time prediction still show significant prediction errors, mostly due to problems in dynamic arrival of jobs with potentially higher priority and hard-to-anticipate packing and backfilling effects. Thus, we propose a different job scheduler (Scojo-PECT) which provides a more suitable framework for predictability and service guarantees by employing preemption with coarse-grain time sharing. We formalize the approach via a queuing model to determine the resource shares necessary to meet target service levels. As further extension, Scojo-PECT can adapt resource shares within certain limits to variations in machine load, while maintaining predictability and service guarantees. We demonstrate the feasibility of service control, the tightness of the 95% prediction intervals (0-30% from average), and the high predictability obtained.

Simultaneous parallel computational grid jobs require reservation by the local job schedulers to ensure allocation of matching time slots at the different sites involved. However, reservations create road blocks in the local schedule, leading to only a small percentage of reservations being tolerable. A large number of reservations typically has adverse effects on local response times and machine utilization. We have extended our SCOJO scheduler to enable advance reservations. SCOJO can perform space sharing or gang scheduling and can run as either adaptive or traditional non-adaptive variant. We show that gang scheduling is more flexible than space sharing in regards to tolerating reservations. We also show that, for space sharing and a low multiprogramming level, the adaptive variants can tolerate reservations better than the non-adaptive variants.

Job scheduling typically focuses on the CPU with little work existing to include I/O or memory. Time-shared execution provides the chance to hide I/O and long-communication latencies though potentially creating a memory conflict. Hyperthreaded CPUs support coscheduling without any context switches and provide additional options for CPU-internal resource sharing. We present an approach that includes all possible resources into the schedule optimization and improves utilization by coscheduling two jobs if feasible. Our LOMARC approach partially reorders the queue by lookahead to increase the potential to find good matches. In simulations based on the workload model of Lublin and Feitelson, we have obtained improvements between 30 percent and 50 percent in both response times and relative bounded response times on hyperthreaded CPUs (i.e., cut times to two third or to half)

Modern job schedulers move towards applying dynamic approaches like time sharing or adaptive resource allocation to accommodate grid jobs or to better utilize local resources. Also, the resources may be heterogeneous and a proper distribution of the application's workload be hard to estimate. Our ScoPro monitoring tool permits to obtain and to store resource-related behavior information for parallel applications. This information is used to create an application signature for predictive use in future runs and to dynamically check competition under time-shared execution and imbalances of workload on heterogeneous resources. ScoPro is applicable to production runs on standard clusters. As main innovative contributions ScoPro can be triggered by job-scheduling events, can monitor several coscheduled jobs concurrently for accurate prediction of slowdowns, and performs realtime short-period measurements with low intrusion during the monitoring, while avoiding any intrusion overhead for the non-monitored part of the job execution

Loosely coordinated (implicit/dynamic) coscheduling is a time-sharing approach that originates from network of workstations environments of mixed parallel/serial workloads and limitedsoftware support. It is meant to be an easy-to-implement and scalable approach. Considering that the percentage of clusters in parallel computing is increasing and easily portable software is needed, loosely coordinated coscheduling becomes an attractive approach for dedicated machines. Loose coordination offers attractive features as a dynamic approach. Static approaches for local job scheduling assign resources exclusively and non-preemptively. Such approaches still remain beyond the desirable resource utilization and average response times. Conversely, approaches for dynamic scheduling of jobs can preempt resources and/or adapt their allocation. They typically provide better resource utilization and response times. Existing dynamic approaches are full preemption with checkpointing, dynamic adaptation of node/CPU allocation, and time sharing via gang or loosely coordinated coscheduling. This survey presents and compares the different approaches, while particularly focusing on the less well-explored loosely coordinated time sharing. The discussion particularly focuses on the implementation problems, in terms of modification of standard operating systems, the runtime system and the communication libraries. Copyright © 2005 John Wiley & Sons, Ltd.

Job scheduling typically focuses on the CPU with little work existing to include I/O or memory. Time-shared execution provides the chance to hide I/O and long-communication latencies though potentially creating a memory conflict. We consider two different cases: standard local CPU scheduling and coscheduling on hyperthreaded CPUs. The latter supports coscheduling without any context switches and provides additional options for CPU-internal resource sharing. We present an approach that includes all possible resources into the schedule optimization and improves utilization by coscheduling two jobs if feasible. Our LOMARC approach partially reorders the queue by lookahead to increase the potential to find good matches. In simulations based on the workload model of [12], we have obtained improvements of about 50% in both response times and relative bounded response times on hyperthreaded CPUs (i.e. cut times by half) and of about 25% on standard CPUs for our LOMARC scheduling approach. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The paper presents PowerMANNA, a distributed-memory parallel computer system based on the 64-Bit PowerPC processor MPC620. The PowerMANNA node architecture supports all the sophisticated features of the MPC620 and incorporates important architectural concepts that allow us to exploit the performance of modern superscale microprocessor in the context of massively parallel supercomputing. The two-way processor nodes of PowerMANNA are embedded in a powerful communication system supporting low-latency communication and maximum connectivity. Processing and communication performance of an eight-node prototype are shown and compared with shared-memory machines and clusters. In the course of the presentation, experience gained with the PowerPC MP620 processor is discussed.

S.124-135

Multithreading has been promoted as an effective mechanism to hide inter-processor communications and remote data access latencies by quickly switching among a set of ready threads. In this paper, we show that multitreading provides an immunity to the performance variations due to changes in data distributions in a distributed-memory multiprocessor. First, toe propose two performance metrics to quantify the sensitivity of performance to data-locality. Second, we perform a quantitative comparison of data-locality sensitivity with both single-threaded and multithreaded computations. These experiments are performed on a 20-node EARTH-MANNA system. Our results show that not only does a multithreaded computation yields higher performance than the single-threaded version, but also that its performance is more robust (less affected) by variations in data-locality.