Abstract In this paper we present a predictive performance model for a key biomedical imaging application found as part of the U.K. e‐Science Information eXtraction from Images (IXI) project. This code represents a significant challenge for our existing performance prediction tools as it has internal structures that exhibit highly variable runtimes depending on qualities in the input data provided. Since the runtime can vary by more than an order of magnitude, it has been difficult to apply meaningful quality of service criteria to workflows that use this code. The model developed here is used in the context of an interactive scheduling system which provides rapid feedback to the users, allowing them to tailor their workloads to available resources or to allocate extra resources to scheduled workloads. Copyright © 2007 John Wiley & Sons, Ltd.

Container-managed persistence is an essential technology as it dramatically simplifies the implementation of enterprise data access. However it can also impose a significant overhead on the performance of the application at runtime. This paper presents a layered queuing performance model for predicting the effect of adding or removing container-managed persistence to a distributed enterprise application, in terms of response time and throughput performance metrics. Predictions can then be made for new server architectures - that is, server architectures for which only a small number of measurements have been made (e.g. to determine request processing speed). An experimental analysis of the model is conducted on a popular enterprise computing architecture based on IBM Websphere, using Enterprise Java Bean-based container-managed persistence as the middleware functionality. The results provide strong experimental evidence for the effectiveness of the model in terms of the accuracy of predictions, the speed with which predictions can be made and the low overhead at which the model can be rapidly parameterised.

This paper details the development and application of a model for predictive performance analysis of a pipelined synchronous wavefront application running on commodity processor cluster systems. The performance model builds on existing work (Cao et al.) by including extensions for modern commodity processor architectures. These extensions, including coarser hardware benchmarking, prove to be essential in countering the effects of modern superscalar processors (e.g. multiple operation pipelines and on-the-fly optimisations), complex memory hierarchies, and the impact of applying modern optimising compilers. The process of application modelling is also extended, combining static source code analysis with run-time profiling results for increased accuracy. The model is validated on several high performance SMP systems and the results show a high predictive accuracy (les 10% error). Additionally, the use of the performance model to speculate on the performance and scalability of this application on a hypothetical cluster with two different problem sizes is demonstrated. It is shown that such speculative techniques can be used to support system procurement, run-time verification and system maintenance and upgrading

Before an application modelled as a directed acyclic graph (DAG) is executed on a heterogeneous system, a DAG mapping policy is often enacted. After mapping, the tasks (in the DAG-based application) to be executed at each computational resource are determined. The tasks are then sent to the corresponding resources, where they are orchestrated in the pre-designed pattern to complete the work. Most DAG mapping policies in the literature assume that each computational resource is a processing node of a single processor, i.e. the tasks mapped to a resource are to be run in sequence. Our studies demonstrate that if the resource is actually a cluster with multiple processing nodes, this assumption will cause a misperception in the tasks' execution time and execution order. This will disturb the pre-designed cooperation among tasks so that the expected performance cannot be achieved. In this paper, a DAG mapping algorithm is presented for multicluster architectures. Each constituent cluster in the multicluster is shared by background workload (from other users) and has its own independent local scheduler. The multicluster DAG mapping policy is based on theoretical analysis and its performance is evaluated through extensive experimental studies. The results show that compared with conventional DAG mapping policies, the new scheme that we present can significantly improve the scheduling performance of a DAG-based application in terms of the schedule length.

This paper addresses workload allocation techniques for two types of sequential jobs that might be found in multicluster systems, namely, non-real-time jobs and soft real-time jobs. Two workload allocation strategies, the optimized mean response time (ORT) and the optimized mean miss rate (OMR), are developed by establishing and numerically solving two optimization equation sets. The ORT strategy achieves an optimized mean response time for non-real-time jobs, while the OMR strategy obtains an optimized mean miss rate for soft real-time jobs over multiple clusters. Both strategies take into account average system behaviors (such as the mean arrival rate of jobs) in calculating the workload proportions for individual clusters and the workload allocation is updated dynamically when the change in the mean arrival rate reaches a certain threshold. The effectiveness of both strategies is demonstrated through theoretical analysis. These strategies are also evaluated through extensive experimental studies and the results show that when compared with traditional strategies, the proposed workload allocation schemes significantly improve the performance of job scheduling in multiclusters, both in terms of the mean response time (for non-real-time jobs) and the mean miss rate (for soft real-time jobs).

Before an application modelled as a directed acyclic graph (DAG) is executed on a heterogeneous system, a DAG mapping policy is often enacted. After mapping, the tasks (in the DAG-based application) to be executed at each computational resource are determined. The tasks are then sent to the corresponding resources, where they are orchestrated in the pre-designed pattern to complete the work. Most DAG mapping policies in the literature assume that each computational resource is a processing node of a single processor, i.e. the tasks mapped to a resource are to be run in sequence. Our studies demonstrate that if the resource is actually a cluster with multiple processing nodes, this assumption will cause a mis-perception in the tasks' execution time and execution order. This will disturb the pre-designed cooperation among tasks so that the expected performance cannot be achieved. In this paper, a DAG mapping algorithm is presented for multicluster architectures. Each constituent cluster in the multicluster is shared by background workload (from other users) and has its own independent local scheduler. The multicluster DAG mapping policy is based on theoretical analysis and its performance is evaluated through extensive experimental studies. The results show that compared with conventional DAG mapping policies, the new scheme that we present can significantly improve the scheduling performance of a DAG-based application in terms of the schedule length.

For single-source, single-tree based peer-to-peer live media streaming, it is generally believed that a short (and wide) tree has a good comprehensive performance in terms of tree reliability and service delay. While the short tree directly benefits delay optimization, it is unclear whether such a structure maximizes tree reliability, which is sometimes more critical for a streaming Internet service. This paper studies several prevalent overlay construction algorithms in terms of (I) service reliability; (2) service delay and (3) protocol overhead. Two types of peer layout, bandwidth-ordered layout and time-ordered layout, are identified and their performance is evaluated. The analytical results show that, by appropriately placing peers according to their time properties, the tree can be much more reliable than a depth-optimized tree. We therefore propose a heap algorithm, which aims for combining the strengths of both bandwidth ordering and time ordering. It dynamically moves peers between difference layers of the tree according to a simple metric, and gradually adjusts the tree toward a layout partially ordered in time and partially ordered in bandwidth. In so doing the tree has advantages in both service reliability and delay, and maintains small protocol overheads. Extensive simulations demonstrate the effectiveness of this new algorithm.

Grid middleware development has advanced rapidly over the past few years to support component-based programming models and service-oriented architectures. This is most evident with the forthcoming release of the Globus toolkit (GT4), which represents a convergence of concepts (and standards) from both the grid and web-services communities. Grid applications are increasingly modular, composed of workflow descriptions that feature both resource and application dynamism. Understanding the performance implications of scheduling grid workflows is critical in providing effective resource management and reliable service quality to users. This paper describes a series of extensions to an existing performance-aware grid management system (TITAN). These extensions provide additional support for workflow prediction and scheduling using a multi-domain performance management infrastructure.

Abstract This paper describes a stateful service‐oriented middleware infrastructure for the management of scientific tasks running on multi‐domain heterogeneous distributed architectures. Allocating scientific workload across multiple administrative boundaries is a key issue in Grid computing and as a result a number of supporting services including match‐making, scheduling and staging have been developed. Each of these services allows the scientist to utilize the available resources, although a sustainable level of service in such shared environments cannot always be guaranteed. A performance‐based middleware infrastructure is described in which prediction data for each scientific task are calculated, stored and published through a Globus‐based performance information service. Distributing these data allows additional performance‐based middleware services to be built, two of which are described in this paper: an intra‐domain predictive co‐scheduler and a multi‐domain workload steering system. These additional facilities significantly improve the ability of the system to meet task deadlines, as well as enhancing inter‐domain load‐balancing and system‐wide resource utilization. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. Predictive performance models of e-Commerce applications allows grid workload managers to provide e-Commerce clients with qualities of service (QoS) whilst making efficient use of resources. We demonstrate the use of two 'coarse-grained' modelling approaches (based on layered queuing modelling and historical performance data analysis) for predicting the performance of dynamic e-Commerce systems on heterogeneous servers. Results for a popular e-Commerce benchmark show how request response times and server throughputs can be predicted on servers with heterogeneous CPUs at different background loads. The two approaches are compared and their usefulness to grid workload management is considered.

Summary form only given. Workload allocation and job dispatching are two fundamental components in static job scheduling for distributed systems. We address the static workload allocation techniques for two types of job stream in multicluster systems, namely, nonreal-time job streams and soft-real-time job streams, which request different qualities of service. Two workload allocation strategies (called ORT and OMR) are developed by establishing and numerically solving two optimisation equation sets. The ORT strategy achieves the optimised mean response time for the nonreal-time job stream; while the OMR strategy can gain the optimised mean miss rate for the soft-real-time job stream over multiple clusters (these strategies can also be applied in a single cluster system). The effectiveness of both strategies is demonstrated through theoretical analysis. The proposed workload allocation schemes are combined with two job dispatching strategies (weighted random and weighted round-robin) to generate new static job scheduling algorithms for multicluster environments. These algorithms are evaluated through extensive experimental studies and the results show that compared with static approaches without the optimisation techniques, the proposed workload allocation schemes can significantly improve the performance of static job scheduling in multiclusters, in terms of both the mean response time (for the nonreal-time jobs) and the mean miss rate (for soft-real-time jobs).

Grid computing is becoming a mainstream technology for large-scale distributed resource sharing and system integration. Workflow management is emerging as one of the most important grid services. In this work, a workflow management system for grid computing, called GridFlow, is presented, including a user portal and services of both global grid workflow management and local grid sub-workflow scheduling. Simulation, execution and monitoring functionalities are provided at the global grid level, which work on top of an existing agent-based grid resource management system. At each local grid, sub-workflow scheduling and conflict management are processed on top of an existing performance prediction based task scheduling system. A fuzzy timing technique is applied to address new challenges of workflow management in a cross-domain and highly dynamic grid environment. A case study is given and corresponding results indicate that local and global grid workflow management can coordinate with each other to optimise workflow execution time and solve conflicts of interest.

In this research, a scenario is assumed where periodic real-time jobs are being run on a heterogeneous cluster of computers, and new aperiodic parallel real-time jobs, modelled by directed acyclic graphs (DAG), arrive at the system dynamically. In the scheduling scheme presented in this paper, a global scheduler situated within the cluster schedules new jobs onto the computers by modelling their spare capabilities left by existing periodic jobs. Admission control is introduced so that new jobs are rejected if their deadlines cannot be met under the precondition of still guaranteeing the real-time requirements of existing jobs. Each computer within the cluster houses a local scheduler, which uniformly schedules both periodic job instances and the subtasks in the parallel realtime jobs using an early deadline first policy. The modelling of the spare capabilities is optimal in the sense that once a new task starts running on a computer, it will utilize all the spare capability left by the periodic real-time jobs and its finish time is the earliest possible. The performance of the proposed modelling approach and scheduling scheme is evaluated by extensive simulation; results show that the system utilization is significantly enhanced, while the real-time requirements of the existing jobs remain guaranteed.

It is envisaged that the grid infrastructure will be a large-scale distributed software system that will provide high-end computational and storage capabilities to differentiated users. A number of distributed computing technologies are being applied to grid development work, including CORBA and Jini. In this work, we introduce an A4 (Agile Architecture and Autonomous Agents) methodology, which can be used for resource management for grid computing. An initial system implementation utilises the performance prediction techniques of the PACE toolkit to provide quantitative data regarding the performance of complex applications running on local grid resources. At the meta-level, a hierarchy of identical agents is used to provide an abstraction of the system architecture. Each agent is able to cooperate with other agents to provide service advertisement and discovery to schedule applications that need to utilise grid resources. A performance monitor and advisor (PMA) is in development to optimize the performance of agent behaviours.

Resource management is an important infrastructure in the grid computing environment. Scalability and adaptability are two key challenges in the implementation of such complex software systems. We introduce a new model for resource management in a metacomputing environment using a hierarchy of homogeneous agents that has the capability of service discovery. The performance of the agent system can be improved using different combinations of optimisation strategies. A modelling and simulation environment has been developed in this work that enables the performance of the system to be investigated. A simplified model of the resource management infrastructure is given as a case study and simulation results are included that show the impact of the choice of performance optimisation strategies on the overall system performance.

With increasing requirements of distributed software systems, software agents are becoming a mainstream technology for software engineering and data management. Scalability and adaptability are two key challenges that must be addressed. In this work a new model is introduced for building large-scale distributed software systems with high dynamics, using a hierarchy of homogeneous agents that has the capability of service discovery. The performance of the agent system can be improved using different combinations of optimisation strategies. A modelling and simulation environment has been developed to aid the performance evaluation process. Two case studies are given and simulation results are included that show the impact of the agent mobility and the choice of performance optimisation strategies on the overall system performance.

Cache behavior is complex and inherently unstable, yet it is a critical factor affecting program performance. A method of evaluating cache performance is required, both to give quantitative predictions of miss-ratio and information to guide optimization of cache use. Traditional cache simulation gives accurate predictions of miss-ratio, but little to direct optimization, Also, the simulation time is usually far greater than the program execution time. Several analytical models have been developed, but concentrate mainly on direct-mapped caches, often for specific types of algorithm, or to give qualitative predictions. Novel analytical models of cache phenomena are presented, applicable to numerical codes consisting mostly of array operations in looping constructs. Set-associative caches are considered, through an extensive hierarchy of cache reuse and interference effects, including numerous forms of temporal and spatial locality. Models of each effect are given which, when combined, predict the overall miss-ratio. An advantage is that the models also indicate sources of cache interference. The accuracy of the models is validated through example program fragments. The predicted miss-ratios are compared with simulations and shown typically to be within 15 percent. The evaluation time of the models is shown to be independent of the problem size, generally several orders of magnitude faster than simulation.

This paper analyses the general properties of Current Mode Multiple Valued Logic (CMMVL) circuits, and presents a framework for further exploitation. A unified circuit view is proposed in which circuits are described in terms of CMMVL to voltage mode binary decoders, and binary to CMMVL encoders. The relative merits of various encodings are explored for a single digit multiplier. It is shown that CMMVL has an inherent advantage in the VLSI layout of fan-in dominated subsystems such as Wallace trees. The construction of CMMVL circuit cells for general logic is discussed.>

The use of a heterogeneous multiple-SIMD (M-SIMD) architecture with image-based measurements and optimal (Kalman) estimators for the analysis of image sequences is illustrated. The architecture integrates SIMD and MIMD processing paradigms, combining heterogeneity of processor types matched to the computation at each level and operational autonomy within an SIMD array. It is suited to real-time simultaneous data parallel (iconic) and control parallel (numeric) processing.>

The application of multiple-single instruction multiple-data (M-SIMD) processing techniques to the problem of finding straight lines in an image is described, and the advantages of using these techniques instead of direct SIMD computation are illustrated by reference to a hierarchical architecture: the Warwick pyramid machine. The advantages over conventional implementations of the Hough transform are discussed, and performance timings for a hierarchical implementation are provided.>

The Warwick Pyramid Machine, an architecture consisting of both SIMD and MIMD parts in a multiple SIMD organization which can operate effectively at all levels of an image analysis problem, is described. The hardware design is discussed, along with programming issues. Several image analysis algorithms that have been mapped onto the architecture are presented.>