For service providers of multi-tiered component-based applications, such as web portals, assuring high performance and availability to their customers without impacting revenue requires effective and careful capacity planning that aims at minimizing the number of resources, and utilizing them efficiently while simultaneously supporting a large customer base and meeting their service level agreements. This paper presents a novel, hybrid capacity planning process that results from a systematic blending of 1) analytical modeling, where traditional modeling techniques are enhanced to overcome their limitations in providing accurate performance estimates; 2) profile-based techniques, which determine performance profiles of individual software components for use in resource allocation and balancing resource usage; and 3) allocation heuristics that determine minimum number of resources to allocate software components. Our results illustrate that using our technique, performance (i.e., bounded response time) can be assured while reducing operating costs by using 25% less resources and increasing revenues by handling 20% more clients compared to traditional approaches.

Service providers hosting multi-tiered applications require accurate analytical models of the applications they will host for different system management activities, such as capacity planning, configuration management, cost analysis and feedback control. Due to the complexity of real world scenarios, developing accurate analytical models is hard. This paper presents the commonly faced challenges in developing these analytical models that stem from real-world issues, such as excessive system activity, presence of multiple cores or processors, and concurrency management. Presence of multi-tiered applications further compounds the challenges faced. We sketch preliminary ideas based on application-specific and/or domain-specific modeling techniques to overcome these limitations.

Soft real-time systems sometimes operate under uncertain and unpredictable environmental conditions which makes event arrival times unreliable and variable. Input to such systems also change from time to time making event processing times variable. Due to such variations, traditional techniques using worst case times to estimate system performance deviate far from actual expected behavior.This paper presents a Method of Stages based Analysis of soft Real Time systems (MoSART). MoSART takes into account variance in both the arrival and execution time and can model the performance of different scheduling algorithms. Sensitivity analysis, experimental validation, and the discovery of state dependent algorithms that outperform popular algorithms are demonstrated.

The purpose of this study is to develop an adaptive model of a very large scale data processing and storage environment. The target environment includes grid applications such as health-care and finance in which the data may be located primarily within the resources of a worldwide corporation. The approach is to use phase identification techniques that can detect over-utilized grid resources, and then to make dynamic decisions to reassign additional resources to that portion of the application processing. Two phase identification techniques are proposed, a variation technique and a real-time threshold-based technique. The techniques are validated with a simulation model and a case study using measured data from a production grid environment. The case study demonstrates that phase identification techniques can be used as the intelligent component of a reactive mechanism for a grid to adapt to changing environmental conditions by dynamic automatic reconfiguration. Results show that threshold based phase identifying techniques combined with dynamic resource allocation capabilities are effective in alleviating performance hot spots and improving response time in a large scale data grid.

Given a typical parallel system and a collection of applications that are to execute on the system, a common problem is determining an effective allocation of processors among the applications. In this paper a learning approach is applied to processor allocation. The approach is to use a stochastic learning automaton (SLA) as a decision tool. An SLA uses values of the current state description, makes an allocation decision, evaluates its decision at some later time, modifies its decision making process, and tries to find the best allocation strategy by learning from its previous mistakes. The method is applied to the problem of allocating processors to parallel applications in a distributed system such as a cluster of workstations, and is validated through simulation. The result of this study show that a learning approach that utilizes a stochastic learning automaton is effective at making processor allocation decisions in a parallel system.

In this paper, processor scheduling policies that "save" processors are introduced and studied. In a multiprogrammed parallel system, a "processor saving" scheduling policy purposefully keeps some of the available processors idle in the presence of work to be done. The conditions under which processor saving policies can be more effective than their greedy counterparts, i.e., policies that never leave processors idle in the presence of work to be done, are examined. Sensitivity analysis is performed with respect to application speedup, system size, coefficient of variation of the applications' execution time, variability in the arrival process, and multiclass workloads. Analytical, simulation, and experimental results show that processor saving policies outperform their greedy counterparts under a variety of system and workload characteristics.

This paper introduces the circulating processor model for parallel computer systems. Models of parallel systems tend to be computationally complex due to synchronization constraints such as task forking and joining. However, product form queuing network models remain computationally efficient as the size of the system grows by calculating only the mean performance metrics of the system. The circulating processor model is a product form queuing network model that differs from more traditional models in that the processors circulate among the parallel applications. In traditional models, the tasks of the parallel application circulate among the processors. Behaviors such as forking and joining of tasks and barrier synchronizations are better captured using this new approach. The circulating processor model may be load-dependent or load-independent. For systems that contain a single parallel application, the load-dependent circulating processor model is exact, while the load-independent model is not. In the latter case, an exact error can be calculated. For systems that contain multiple parallel applications, the load-dependent circulating processor model is a good approximation to the actual system, while the load-independent model is not. A case study using Parallel Virtual Machine (PVM) on a network of workstations illustrates the applicability of the circulating processor model.

Soft real-time environments consist of jobs that must receive service within a particular time interval. If service for a specific job is not completed by the end of its time interval, it is said to be lost; in addition, the computation time expended on the job is wasted, and any further computation for the job is discontinued. The goal of a system designer is to provide an environment that minimizes the number of jobs that are lost. If a parallel environment is available, the system designer has two options: Allow each processor to execute a job individually, or let multiple processors cooperate in executing a job. This article shows, for two classes of static allocation policies, that simple comparative analytical models may be used to indicate which option minimizes the number of lost jobs, as a function of workload intensity. The first class of policies, called equal partitions, statically decomposes the system into equal-size sets of processors and executes one job per partition. These policies are frequently employed in other contexts. The second class of policies, called two partitions, statically partitions the processors into two sets, not necessarily of the same size. Surprisingly, it is observed mathematically that even for statistically identical jobs, this class of policies is superior to equal partitions under certain loadings. The analysis is validated experimentally with a workload executed on a 16-node iPSC/2 hypercube.>

Kendall Square Research introduced the KSR1 system in 1991. The architecture is based on a ring of rings of 64-bit microprocessora. It is a distributed, shared memory system and is scalable. The memory structure is unique and is the key to understanding the system. Different levels of caching eliminates physical memory addressing and leads to the ALLCACHE™ scheme. Since requested data may be found in any of several caches, the initial access time is variable. Once pulled into the local (sub) cache, subsequent access times are fixed and minimal. Thus, the KSR1 is a Cache-Only Memory Architecture (COMA) system.This paper describes experimentation and an analytic model of the KSR1. The focus is on the poststore programmer option. With the poststore option, the programm er can elect to broadcast the updated value of a variable to all processors that might have a copy. This may save time for threads on other processors, but delays the broadcasting thread and places additional traffic on the ring. The specific issue addressed is to determine under what conditions poststore is beneficial. The analytic model and the experimental observations are in good agreement. They indicate that the decision to use poststore depends both on the application and the current system load.

In a closed, separable, queuing network model of a computer system, the number of customer classes is an input parameter. The number of classes and the class compositions are assumptions regarding the characteristics of the system's workload. Often, the number of customer classes and their associated device demands are unknown or are unmeasurable parameters of the system. However, when the system is viewed as having a single composite customer class, the aggregate single-class parameters are more easily obtainable. This paper addresses the error made when constructing a single-class model of a multi-class system. It is shown that the single-class model pessimistically bounds, the performance of the multi-class system. Thus, given a multi-class system, the corresponding single-class model can be constructed with the assurance that the actual system performance is better than that given by the single-class model. In the worst case, it is shown that the throughput given by the single-class model underestimates the actual multi-class throughput by, at most, 50%. Also, lower bounds are provided for the number of necessary customer classes, given observed device utilizations. This information is useful to clustering analysis techniques as well as to analysts who must obtain class-specific device demands.

Parallel programs are characterized by their speedup behavior. As more processors are allocated to a particular parallel program, the program (potentially) executes faster. However, there is often a point of diminishing returns, beyond which extra allocated processors cannot be used effectively. Extra processors would be better utilized by allocating them to another program. Thus, given a set of processors in a multiprocessor system, and a set of parallel programs, a partitioning problem naturally arises which seeks to allocate processors to programs optimally.

Abstract The development of computing systems with large numbers of processors has been motivated primarily by the need to solve large, complex problems more quickly than is possible with uniprocessor systems. Traditionally, multiprocessor systems have been uniprogrammed, i.e., dedicated to the execution of a single set of related processes, since this approach provides the fastest response for an individual program once it begins execution. However, if the goal of a multiprocessor system is to minimize average response time or to maximize throughput, then multiprogramming must be considered. In this paper, a model of a simple multiprocessor system with a two‐program workload is reviewed; the model is then applied to an Intel iPSC/2 hypercube multiprocessor with a workload consisting of parallel wavefront algorithms for solving triangular systems of linear equations. Throughputs predicted by the model are compared with throughputs obtained experimentally from an actual system. The results provide validation for the model and indicate that significant performance improvements for multiprocessor systems are possible through multiprogramming.

A computer system's workload is represented by its multiprogramming level, which is defined as the number of tasks (jobs, customers) which actively compete for resources within the system. In a product-form queuing network model of the system, the workload is modeled by assuming that the multiprogramming level is either fixed (i.e., closed model) or that the multiprogramming level depends upon an outside arrival process (i.e., open model). However, in many actual systems, closed and open models are both inappropriate since the multiprogramming level is neither fixed nor governed by an outside arrival process.

The performance of a computer system depends upon the efficiency of its swapping mechanisms. The swapping efficiency is a complex function of many variables. The degree of multiprogramming, the relative loading on the swapping devices, and the speed of the swapping devices are all interdependent variables that affect swapping performance.