Highly scalable parallel applications can efficiently solve expensive computational problems when run on a large number of compute nodes. However, selecting the optimal number of nodes for a compute job of a given size is non-trivial, and allocating too few or too many nodes may not yield the expected performance. Knowing the scaling behavior of an application in advance enables us, for example, to make optimal use of the available hardware resources. We introduce a novel, portable approach to predict the scalability of parallel applications written in modern high-level programming models. We propose a predictive compiler-runtime framework based on Celerity, a task-based distributed runtime system that enables executing SYCL codes on clusters. The framework targets a broad range of computing systems, from CPU to GPU clusters, and proposes a model that combines machine learning, communication modeling and DAG heuristics. Experimental results on two large-scale clusters, JUWELS and Marconi-100, show accurate scalability prediction of unseen single and multi-task applications.

LoRaWAN has become a foundational technology in the Internet of Things (IoT) landscape due to its long-range communication and energy efficiency. However, its default Adaptive Data Rate (ADR) mechanism struggles to adapt to dynamic environments and dense network deployments, where co-channel interference and the coupling between transmission parameters limit its ability to ensure reliable and energy-efficient communication. To address these challenges, this paper proposes MARLTC, an ADR mechanism based on Multi-Agent Rein-forcement Learning (MARL) that jointly optimizes spreading factor and transmission power using realistic observable metrics, including recent transmission history, observed signal-to-noise ratios, and distribution of spreading factors in the network. The transmission configuration problem is modeled as a cooperative Markov Game and solved using the Centralized Training and Decentralized Execution (CTDE) paradigm, where pre-trained policies are deployed at end devices to infer suitable transmission parameters with reduced convergence time. The results using a realistic LoRaWAN simulator show that MARLTC achieves up to 67.9% faster convergence, 62.1% higher energy efficiency, and a 5.0% better packet delivery ratio compared to state-of-the-art approaches, highlighting its scalability and responsiveness in dense deployments. The practical feasibility of MARLTC is further validated using physical LoRaWAN hardware, proving that the resulting policies meet the memory and timing constraints of resource-constrained IoT devices.

The rapid growth of cloud computing and the expansion of edge and IoT technologies are becoming essential for meeting the performance, scalability, and latency requirements of modern distributed service-based applications. While these applications facilitate the accommodation of real-world workloads, their placement across a computing continuum spanning the cloud, edge, and IoT remains challenging. Existing service scheduling works often rely on simulations or orchestration systems limited to a single cluster. While simulations fail to capture real-world constraints, single-cluster orchestration systems introduce significant overhead and cannot capture the heterogeneity, network latency, and cross-cluster dependencies across cloud, edge, and IoT layers. In this paper, we introduce Pulse, a fully distributed scheduling system designed to optimize the deployment of distributed service-based applications across multi-cluster environments. Pulse leverages a two-phase distributed multi-objective optimization approach: locally optimizing for monetary cost and fairness within clusters, and globally optimizing for monetary cost and latency across multiple clusters. Pulse is built atop a lightweight orchestration framework, which enables service coordination across cloud, edge, and IoT layers, ensuring adaptability to heterogeneous infrastructures and the latency among geo-distributed clusters. To validate our approach, we conduct a comprehensive real-world evaluation on the Grid’5000 infrastructure, demonstrating that Pulse outperforms state-of-the-art scheduling methods by improving total resource utilization by 34.5%, reducing monetary cost by 82.6%, and lowering the average end-to-end network latency among services by 75.0%. These results highlight Pulse’s effectiveness in managing large-scale, service-based applications in realistic, multi-cluster environments.

The relentless growth of mobile Internet of Things (IoT) devices has shifted computation toward a distributed computing continuum, spanning edge, fog, and cloud layers, where energy efficiency, low latency, and dynamic node mobility are critical yet often conflicting goals. Existing scheduling frameworks struggle to balance these demands under real-world conditions, especially as device movement and heterogeneous workloads increase system complexity. We present MOSAIC, a mobility-aware scheduling and resource management framework designed to optimize performance in dynamic IoT environments. Our approach introduces three key innovations. First, a refined five-tier architecture extends the traditional edge-fog-cloud hierarchy by adding proximity, local, and regional mobility layers, enabling computation to follow mobile users more effectively and reducing unnecessary network traffic. Second, MOSAIC integrates a preemption-aware dynamic scheduler with an Adaptive-$\lambda$reinforcement learning-based resource manager that adapts based on workload changes and mobility patterns, prioritizing energy-efficient edge execution while meeting strict deadlines. Third, the framework utilizes real-world mobility traces, including Levy-Walk, Random-Walk, and Geolife, to drive reconfiguration and improve decision accuracy. We evaluate MOSAIC through a large-scale deployment across three geographically distributed regions of the Grid'5000 testbed, using realistic workflows and mixed periodic/DAG task loads. Our results show that, compared to state-of-the-art schedulers, MOSAIC reduces energy consumption by 35.9%–×1.5, lowers latency by 42.8%–×4.9, and shortens makespan by 22.6%–×7.2, all while maintaining 100% deadline satisfaction across diverse mobility scenarios.

Adaptive resource provisioning has become crucial for cloud-based applications, especially those managing real-time traffic like Voice over IP (VoIP), which experience rapidly fluctuating workloads. Traditional static provisioning methods often fall short in these dynamic environments, leading to inefficiencies and potential service disruptions. Existing solutions struggle to maintain performance under varying traffic conditions, particularly for time-sensitive applications. This paper introduces ScaleIP, a hybrid autoscaling solution for containerized VoIP services that offers real-time adaptability and efficient resource management. ScaleIP leverages Deep Reinforcement Learning to make dynamic and efficient scaling decisions, improving call latency, increasing the number of successfully routed calls, and maximizing resource utilization. We evaluated ScaleIP through extensive experiments conducted on a real testbed utilizing the customer Call Detail Record (CDR) from 2023 provided by World Direct, encompassing over 89 million calls. The results show that ScaleIP consistently maintains call latency below 2 s, increases the number of successfully routed calls by 3.26 ×, and increases the resource utilization up to 60 % compared to state-of-the-art autoscaling methods.

Many data-intensive and distributed applications rely on low-latency and scalable key–value storage systems across the Computing Continuum. Key–value storage systems typically use consistent hashing or hash slot-sharding mechanisms to distribute data across storage nodes, which ensures load balancing but often leads to sub-optimal response times and monetary costs, particularly in geo-distributed systems where nodes might have different unit prices and be widely dispersed. In this paper, we propose SmartKV , a cost-efficient geo-distributed key–value store that optimizes data placement dynamically, abstracting the intricacies of data organization, transfer, access, and processing. SmartKV integrates a decentralized data placement algorithm that optimizes the replication factor and selects suitable locations for key–value pairs and replicas, balancing cost and access latency while keeping optimization overhead low. We employ a realistic cost model based on public and private Cloud and Edge providers that consider data transfer, request, and storage costs. In addition to conventional key–value pairs, SmartKV supports active key–value pairs, which enable the definition of custom data types and the execution of user-defined functions directly on the storage side. This contributes to reducing data transfer costs and round-trip times. We thoroughly evaluate SmartKV across different regions of the Chameleon testbed using several realistic workloads. Results show that the utilized decentralized data placement strategy allows SmartKV to reduce round trip times between 9 and 84% while reducing costs up to 4.84 × under different client workloads and consistency models compared to state-of-the-art data placement strategies. • Novel geo-distributed KV store with custom data placement strategies. • Decentralized data placement algorithm to optimize costs and round trip times. • Active KV pairs support remote execution to reduce costs and round trip times.

Scientific workflows are increasingly adopting hy-brid Edge-Cloud infrastructures to benefit from the computational and storage capacity of the Cloud and the cost savings and data locality of the Edge. Workflow scheduling is one of the most challenging problems for the Edge-Cloud continuum. State-of-the-art workflow schedulers often rely on a centralized runtime system and are based on static algorithms that either focus on Cloud or Edge systems (but not both). In this paper, we introduce a novel, open-source, and dynamic scheduler for scientific workflows that targets the Edge-Cloud continuum by design using fully decentralized runtime system instances. This not only reduces data transfer times but also leverages the benefits of the continuum. The proposed scheduler optimizes for runtime while adhering to a given cost limit by dynamically mapping tasks to resources and orchestrating groups of workflow tasks on runtime system instances. Furthermore, the scheduler adapts to real-time updates in task durations, accommodating for variations in resource performance, to efficiently use the cost limit and to reduce the total runtime of the workflow. We compare our approach against a state-of-the-art dynamic scheduler (JIT-C) for four well-known scientific workflows. Experiments demonstrate that by using the smallest cost derived by JIT-C as a cost limit for our scheduler, we achieve an average runtime improvement of 56% and an average cost reduction of 34% compared to JIT-C.

Even though the initial design of LoRa did not specifically aim at provisioning mobile devices, onboard IoT devices are paving the way for safer, more efficient, and ultimately, autonomous transportation. The LoRaWAN Adaptive Data Rate (ADR) mechanism enables the minimization of energy consumption and the optimization of data rates and airtime values. However, it has been demonstrated to have limited adaptability in mobile devices. In this paper, we propose a proactive ADR mechanism for LoRaWAN based on trajectory estimation and well-known machine-learning methods used to forecast the signal-to-noise ratio (SNR). This enables the efficient selection of the most suitable transmission parameters beforehand. We compare our approach with existing mechanisms in a realistic simulator and several urban environments. Results prove that our method achieves a proper balance between minimizing energy consumption and satisfying performance constraints over time even in highly dynamic and unpredictable environments.

While domain-specific HPC software packages continue to thrive and are vital to many scientific communities, a general purpose high-productivity GPU cluster programming model that facilitates experimentation for non-experts remains elusive. We demonstrate how Celerity, a high-level C++ programming model for distributed accelerator computing based on the open SYCL standard, allows for the quick development of - and experimentation with - distributed applications. To achieve scalability on large machines, we replace Celerity's existing master/worker scheduling model with a fully distributed scheme that reduces the worst-case scheduling complexity from quadratic to linear while maintaining the existing programming interface. We then show how this declarative, data-flow based API paired with a point-to-point communication model with eager data pushing can effectively expose and leverage opportunities for latency hiding and computation/communication overlapping with minimal or no manual guidance. We demonstrate how Celerity exhibits very good scalability on multiple benchmarks from several scientific domains and up to 128 GPUs.

Today digital revolution is having a dramatic impact on the pharmaceutical industry and the entire healthcare system. The implementation of machine learning, extreme-scale computer simulations, and big data analytics in the drug design and development process offers an excellent opportunity to lower the risk of investment and reduce the time to the patient.

Most well-known cloud providers offer advanced support for serverless applications that goes beyond single function invocation by enabling developers to build entire workflows, which are known as serverless function choreographies (FCs). Current support for FCs by many FaaS systems uncovered important problems including maximum number of parallel function executions, unexpected considerable delays, and provider lock-in. These limitations can result in longer execution times or even failure to execute individual functions or entire FCs. To overcome some of these limitations, we introduce a scalable middleware service xAFCL that can schedule and execute different functions of the same FC across multiple FaaS systems (currently supporting all top five providers). In order to support scheduling under xAFCL, we introduce a novel FaaS model which estimates the completion time of functions by considering FaaS system limitations, submission delays, and overheads for executing functions. Experimental results demonstrate that xAFCLs FaaS model shows very low inaccuracy of up to 2.9% for AWS and 20% for IBM for real-life BWA data-bound FC that uses S3. Moreover, xAFCL outperforms an earliest start time (EST) scheduler by up to 43% for makespan and 2.7x for throughput.

[J1C2 Presentation Abstract at IEEE SERVICES 2021 for IEEE Transactions on Services Computing DOI 10.1109/TSC.2021.3128137]

Summary Time‐of‐flight camera systems are an essential component in 3D scene analysis and reconstruction for many modern computer vision applications. The development and validation of such systems require testing in a large variety of scenes and situations. Accurate room impulse response simulation greatly speeds up development and validation, as well as reducing its cost, but large computational overhead has so far limited its applicability. While the overall algorithmic requirements of this simulation differ significantly from 3D rendering, the recently introduced hardware raytracing support in GPUs nonetheless provides an interesting new implementation option. In this article, we present a new room response simulation method, implemented in a vendor‐independent fashion with Vulkan compute shaders and leveraging NVIDIA VKRay hardware raytracing. We also extend this method to multi‐GPU computation with asynchronous streaming and introduce a domain‐specific high‐performance compression scheme in order to overcome the limitations of on‐board GPU memory and PCIe bandwidth when simulating very large scenes. Our implementation is, to the best of our knowledge, the first ever combined application of Vulkan hardware raytracing and multi‐GPU compute in a non‐rendering simulation setting. Compared to a state‐of‐the‐art multicore CPU implementation running on 12 CPU cores, we achieve an overall speedup factor of up to 20 on a single consumer GPU, and 71 on four GPUs.

Porting existing monoliths to the Function-as-a-Service (FaaS) (FaaSification) can be very challenging for software developers due to different architectural styles. For a successful porting, developers need to resolve various dependencies, such as method invocations of external packages or user-defined codes, as well as global and local variables used in and after the code block that should be faasified. To bridge the gap and automatize FaaSification, this paper introduces M2FaaS, a FaaSifier that automatically converts a Node.js monolith into a hybrid by faasifying annotated code blocks as serverless functions on multiple FaaS providers. M2FaaS is a novel FaaSifier that resolves many challenges for the resulting monolith to work properly after the FaaSification. Developers may annotate all dependencies that need to be resolved for the generated functions to run properly and specify variables that should be returned by the function to the monolith because they are used later in the monolith. Moreover, M2FaaS is the first FaaSifier that faasifies arbitrary code blocks. The current M2FaaS prototype supports FaaSification of individual functions on two FaaS providers, AWS Lambda and IBM Cloud Functions. Finally, M2FaaS introduces an optional annotation for alternative functions to be invoked in case the primary faasified function fails. The resulting hybrid application invokes the automatically deployed serverless functions, while the original code remains executable. Experiments with four complementary monoliths demonstrate that M2FaaS outperforms state-of-the-art FaaSifiers in terms of development effort by up to 73.3%. Moreover, with the fault tolerance support, M2FaaS finishes all submitted functions, thereby achieving by 18.5% higher throughput than the other FaaSifiers.

The cloud has been widely used as a distributed computing platform for running scientific workflow applications. Most of the cloud providers encourage the use of their underutilized resources as spot instances for much cheaper prices compared with common resources as on-demand instances, however, the promise of lower costs for resources results in the volatility such that spot instances can be interrupted at any time by cloud providers. Many workflow scheduling algorithms have been proposed to deal with volatile resources. In this article, we consider the two most important features of the volatile resources namely fulfillment and interruption rates to fully model the instability of the cloud infrastructure. Subsequently, we propose a novel evolutionary multi-objective workflow scheduling approach to generate a set of trade-off solutions that outperform state-of-the-art algorithms in both makespan and economic costs. In addition, we explore the fluctuation of makespan and costs for our obtained schedules under different levels of fulfillment and interruption rates. Experimental results with the five well-known real-world workflows demonstrate that our evolutionary multi-objective workflow scheduling algorithm is competitive in terms of makespan and cost compared with state-of-the-art on-demand scheduling techniques.

Cloud applications often benefit from deployment on serverless technology Function-as-a-Service (FaaS), which may instantly spawn numerous functions and charges users for the period when serverless functions are running. Maximum benefit is achieved when functions are orchestrated in a workflow or function choreographies (FCs). However, many provider limitations specific for FaaS, such as maximum concurrency or duration often increase the failure rate, which can severely hamper the execution of entire FCs. Current support for resilience is often limited to function retries or try-catch, which are applicable within the same cloud region only. To overcome these limitations, we introduce rAFCL, a middleware platform that maintains reliability of complex FCs in federated clouds. In order to support resilient FC execution under rAFCL, our model creates an alternative strategy for each function based on the required availability specified by the user. Alternative strategies are not restricted to the same cloud region, but may contain alternative functions across five providers, invoked concurrently in a single alternative plan or executed subsequently in multiple alternative plans. With this approach, rAFCL offers flexibility in terms of cost-performance trade-off. We evaluated rAFCL by running three real-life applications across three cloud providers. Experimental results demonstrated that rAFCL outperforms the resilience of AWS Step Functions, increasing the success rate of entire FC by 53.45%, while invoking only 3.94% more functions with zero wasted function invocations. rAFCL significantly improves availability of entire FCs to almost 1 and survives even after massive failures of alternative functions.

Publikationen von Forschenden. Knorr, Fabian; Thoman, Peter; Fahringer, Thomas: ndzip: a high-throughput parallel lossless compressor for scientific data. In: Proceedings 2021 Data Compression Conference (DCC) / Bilgin, Ali; Marcellin, Michael W.; Serra-Sagrista, Joan; Storer, James A. IEEE, 2021

Accelerator clusters are an ongoing trend in high performance computing, continuously gaining traction and forming a ubiquitous hardware resource for domain scientists to run large-scale simulations on. However, there is often a gap between new hardware technologies and adoption by legacy code bases. Porting real-world applications to new programming models is a difficult undertaking, aggravated by the need for support for both distributed-memory and accelerator parallelism. In this work, we present a case study of porting Cronos, a real-world code from the field of magnetohydrodynamics, to Celerity, a high-level programming model for distributed-memory accelerator clusters. We discuss the numerical, algorithmic and implementation properties of the application and motivate our decisions for adapting them where necessary. Preliminary results show a parallel efficiency of up to 87% for 16 GPUs.

Lossless data compression is a promising software approach for reducing the bandwidth requirements of scientific applications on accelerator clusters without introducing approximation errors. Suitable compressors must be able to effectively compact floating-point data while saturating the system interconnect to avoid introducing unnecessary latencies.

Serverless workflow applications or function choreographies (FCs), which connect serverless functions by data- and control-flow, have gained considerable momentum recently to create more sophisticated applications as part of Function-as-a-Service (FaaS) platforms. Initial experimental analysis of the current support for FCs uncovered important weaknesses, including provider lock-in, and limited support for important data-flow and control-flow constructs. To overcome some of these weaknesses, we introduce the Abstract Function Choreography Language (AFCL) for describing FCs at a high-level of abstraction, which abstracts the function implementations from the developer. AFCL is a YAML-based language that supports a rich set of constructs to express advanced control-flow (e.g. parallelFor loops, parallel sections, dynamic loop iterations counts) and data-flow (e.g multiple input and output parameters of functions, DAG-based data-flow). We introduce data collections which can be distributed to loop iterations and parallel sections that may substantially reduce the delays for function invocations due to reduced data transfers between functions. We also support asynchronous functions to avoid delays due to blocking functions. AFCL supports properties (e.g. expected size of function input data) and constraints (e.g. minimize execution time) for the user to optionally provide hints about the behavior of functions and FCs and to control the optimization by the underlying execution environment. We implemented a prototype AFCL environment that supports AFCL as input language with multiple backends (AWS Lambda and IBM Cloud Functions) thus avoiding provider lock-in which is a common problem in serverless computing. We created two realistic FCs from two different domains and encoded them with AWS Step Functions, IBM Composer and AFCL. Experimental results demonstrate that our current implementation of the AFCL environment substantially outperforms AWS Step Functions and IBM Composer in terms of development effort, economic costs, and makespan.

Teaching parallel programming and HPC is a difficult task. There is a large number of sophisticated hardware and software components, each complex on their own and often showing non-intuitive interaction when used in combination. We consider education in HPC among the more difficult topics in computer science due to the fact that larger distributed memory systems are ubiquitous yet inaccessible and intangible to students. In this work, we present the Cluster Coffer, a miniature cluster computer based on 16 ARM compute boards that we believe is suitable for reducing the entry barrier to HPC in teaching and public outreach. We discuss our design goals for providing a portable, inexpensive system that is easy to maintain and repair. We outline the implementation path we took in terms of hardware and software, in order to provide others with the information required to reproduce and extend our work. Finally, we present two use cases for which the Cluster Coffer has been used multiple times, and will continue to be used in the upcoming years.

Many techniques such as scheduling and resource provisioning rely on performance prediction of workflow tasks for varying input data. However, such estimates are difficult to generate in the cloud. This paper introduces a novel two-stage machine learning approach for predicting workflow task execution times for varying input data in the cloud. In order to achieve high accuracy predictions, our approach relies on parameters reflecting runtime information and two stages of predictions. Empirical results for four real world workflow applications and several commercial cloud providers demonstrate that our approach outperforms existing prediction methods. In our experiments, our approach respectively achieves a best-case and worst-case estimation error of 1.6 and 12.2 percent, while existing methods achieved errors beyond 20 percent (for some cases even over 50 percent) in more than 75 percent of the evaluated workflow tasks. In addition, we show that the models predicted by our approach for a specific cloud can be ported with low effort to new clouds with low errors by requiring only a small number of executions.

In Infrastructure as a Service (IaaS) Clouds, users are charged to utilize cloud services according to a pay-per-use model. If users intend to run their workflow applications on cloud resources within a specific budget, they have to adjust their demands for cloud resources with respect to this budget. Although several scheduling approaches have introduced solutions to optimize the makespan of workflows on a set of heterogeneous IaaS cloud resources within a certain budget, the hourly-based cost model of some well-known cloud providers (e.g., Amazon EC2 Cloud) can easily lead to a higher makespan and some schedulers may not find any feasible solution. In this article, we propose a novel resource provisioning mechanism and a workflow scheduling algorithm, named Greedy Resource Provisioning and modified HEFT (GRP-HEFT), for minimizing the makespan of a given workflow subject to a budget constraint for the hourly-based cost model of modern IaaS clouds. As a resource provisioning mechanism, we propose a greedy algorithm which lists the instance types according to their efficiency rate. For our scheduler, we modified the HEFT algorithm to consider a budget limit. GRP-HEFT is compared against state-of-the-art workflow scheduling techniques, including MOACS (MultiObjective Ant Colony System), PSO (Particle Swarm Optimization), and GA (Genetic Algorithm). The experimental results demonstrate that GRP-HEFT outperforms GA, PSO, and MOACS for several well-known scientific workflow applications for different problem sizes on average by 13.64, 19.77, and 11.69 percent, respectively. Also in terms of time complexity, GRP-HEFT outperforms GA, PSO and MOACS.

Many researchers rely on simulations to analyze and validate their researched methods on Cloud infrastructures. However, determining relevant simulation parameters and correctly instantiating them to match the real Cloud performance is a difficult and costly operation, as minor configuration changes can easily generate an unreliable inaccurate simulation result. Using legacy values experimentally determined by other researchers can reduce the configuration costs, but is still inaccurate as the underlying public Clouds and the number of active tenants are highly different and dynamic in time. To overcome these deficiencies, we propose a novel model that simulates the dynamic Cloud performance by introducing noise in the computation and communication tasks, determined by a small set of runtime execution data. Although the estimating method is apparently costly, a comprehensive sensitivity analysis shows that the configuration parameters determined for a certain simulation setup can be used for other simulations too, thereby reducing the tuning cost by up to 82.46 percent, while declining the simulation accuracy by only 1.98 percent on average. Extensive evaluation also shows that our novel model outperforms other state-of-the-art dynamic Cloud simulation models, leading up to 22 percent lower makespan inaccuracy.

Effectively implementing scientific algorithms in distributed memory parallel applications is a difficult task for domain scientists, as evident by the large number of domain-specific languages and libraries available today attempting to facilitate the process. However, they usually provide a closed set of parallel patterns and are not open for extension without vast modifications to the underlying system. In this work, we present the AllScale API, a programming interface for developing distributed memory parallel applications with the ease of shared memory programming models. The AllScale API is closed for modification but open for extension, allowing new, user-defined parallel patterns and data structures to be implemented based on existing core primitives and therefore fully supported in the AllScale framework. Focusing on high-level functionality directly offered to application developers, we present the design advantages of such an API design, detail some of its specifications and evaluate it using three real-world use cases. Our results show that AllScale decreases the complexity of implementing scientific applications for distributed memory while attaining comparable or higher performance compared to MPI reference implementations.

Amazon EC2's spot instances (SIs) represent a competitive Cloud resource in terms of price compared to reliable and fixed price options. The drawback, however, is that SIs may not always be available and they can be revoked at any given time. In this paper, we describe a comprehensive experimental evaluation for EC2 SIs to characterize their performance and behavior in three different regions each of which in a different continent. We describe the life cycle of SIs with the most important phases of an SI, introduce the most relevant events that can prevent a user from obtaining SIs, and draw important conclusions that can be exploited by the research community to effectively use the spot market. Our results reveal the fulfillment rate of requests for SIs, waiting time until requested SIs become fulfilled, details about the frequency of SI interruption, and how long SIs run before being interrupted. Our study also indicates that the SI frequency of interruption influences the fulfillment rate, SIs are highly reliable in the first 20 to 30 minutes after deployment, and SIs can be reclaimed by EC2 regardless of an SI's bid price and current workload when EC2 lacks resources for On-Demand and Reserved instances.

Contemporary state-of-the-art runtime systems underlying widely utilized general purpose parallel programming languages and libraries like OpenMP, MPI, or OpenCL provide the foundation for accessing the parallel capabilities of modern computing architectures. In the tradition of their respective imperative host languages those runtime systems' main focus is on providing means for the distribution and synchronization of operations - while the organization and management of manipulated data is left to application developers. Consequently, the distribution of data remains inaccessible to those runtime systems. However, many desirable system-level features depend on a runtime system's ability to exercise control on the distribution of data. Thus, program models underlying traditional systems lack the potential for the support of those features. In this paper, we present a novel application model granting parallel runtime systems system-wide control over the distribution of user-defined shared data structures. Our model utilizes the high-level nature of parallel programming languages, in particular, the usage of well-typed data structures and the associated hiding of implementation details from the application developers. By being based on a generalization of such data structures and extending the resulting abstraction with features facilitating the automated management of the distribution of those, our model enables runtime systems to dynamically influence the placement and replication of shared data. This paper covers a rigorous formal description of our application model, as well as details on our prototype implementation and experimental results demonstrating its ability to efficiently and scalably manage various data structures in real-world environments.

Summary Based on a pay‐as‐you‐go model, cloud computing provides the possibility of hosting pervasive applications from both academic and business domains. However, data centers hosting cloud applications consume huge amounts of electrical energy, contributing to high operational costs and large carbon footprints to the environment. Energy‐aware resource provisioning is an effective solution to diminish the energy consumption of cloud data centers. Recently, a growing trend has emerged, where cloud technology is used to run periodic real‐time applications such as multimedia, telecommunication, video gaming, and industrial applications. In order for a real‐time application to be able to use cloud services, cloud providers have to be able to provide timing guarantees. In this paper, we introduce an energy‐aware resource provisioning mechanism for cloud data centers, which are capable of serving real‐time periodic tasks following the Software as a Service model. The proposed method is compared against an energy‐aware version of the RT‐OpenStack. RT‐OpenStack is a recently proposed approach to provide a time‐predictable version of OpenStack. The experimental results manifest that our proposed resource provisioning method outperforms energy‐aware version of the RT‐OpenStack by 16.01%, 25.45%, and 25.45% in terms of energy consumption, number of used servers, and average utilization of used servers, respectively. Moreover, from the scalability perspective, the preference of the proposed method for large‐scale data centers is more considerable.

Summary Recently, a growing trend has emerged toward using Internet of Things (IoT) in the context of industrial systems, which is referred to as industrial IoT. To deal with the time‐critical requirements of industrial applications, it is necessary to consider reliability and timeliness during the design of an industrial IoT system. Through the separation of the control plane and the data plane, software‐defined networking provides control units (controllers) coexisting with sink nodes, efficiently coping with network dynamics during run‐time. It is of paramount importance to select a proper number of these devices (i.e., software‐defined networking controllers and sink nodes) and locate them wisely in a network to reduce deployment cost. In this paper, we optimize the type and location of sinks and controllers in the network, subject to reliability and timeliness as the prominent performance requirements in time‐critical IoT systems through ensuring that each sensor node is covered by a certain number of sinks and controllers. We propose PACSA‐MSCP, an algorithm hybridizing a parallel version of the max‐min ant system with simulated annealing for multiple‐sink/controller placement. We evaluate the proposed algorithm through extensive experiments. The performance is compared against several well‐known methods, and it is shown that our approach outperforms those methods by lowering the total deployment cost by up to 19%. Moreover, the deviation from the optimal solution achieved by CPLEX is shown to be less than 2.7%.

Task-based programming models for shared memory—such as Cilk Plus and OpenMP 3—are well established and documented. However, with the increase in parallel, many-core, and heterogeneous systems, a number of research-driven projects have developed more diversified task-based support, employing various programming and runtime features. Unfortunately, despite the fact that dozens of different task-based systems exist today and are actively used for parallel and high-performance computing (HPC), no comprehensive overview or classification of task-based technologies for HPC exists. In this paper, we provide an initial task-focused taxonomy for HPC technologies, which covers both programming interfaces and runtime mechanisms. We demonstrate the usefulness of our taxonomy by classifying state-of-the-art task-based environments in use today.

Virtualization is a key enabling technology in Cloud computing that allows users to run multiple virtual machines (VMs) with their own application environment on top of physical hardware. It permits scaling up and down of applications by elastic on-demand provisioning of VMs in response to their variable load to achieve increased utilization efficiency at a lower operational cost, while guaranteeing the desired level of Quality of Service (QoS) to the end-users. Typically, VMs are created using provider-specific templates that are stored in proprietary repositories, leading to provider lock-in and hampering portability or simultaneous usage of multiple federated Clouds. In this context, optimization at the level of the virtual machine image is needed both by the applications and by the underlying Cloud providers for improved resource usage, operational costs, elasticity, storage use, and other desired QoS-related features. To overcome those issues, the ENTICE project researches and creates a novel VM repository and operational environment for federated Cloud infrastructures. There exists a large variety of industrial applications that can strongly benefit by the ENTICE environment. In this paper we present an interesting selection of complementary use cases that drive the definition of the essential requirements for the ENTICE environment, and more importantly, validate the introduced innovations.

Code multi-versioning is an increasingly widely adopted tool for implementing optimizations which respond to unknown or dynamically changing runtime conditions, without the performance overhead of just-in-time compilation. A common concern in its use is instruction cache performance, due to larger binary sizes increasing cache pressure on the one hand and more unpredictable branching on the other. Despite this ongoing interest, there has been no comprehensive study of the impact of multi-versioning so far - particularly in a multi-threaded setting. In this paper, we present a categorization of the parameter space potentially affecting multi-versioned performance, a toolset for exploring this space, and an in-depth characterization of three hardware platforms using this toolset.

Shared memory machines continue to increase in scale by adding more parallelism through additional cores and complex memory hierarchies. Often, executing multiple applications concurrently, dividing among them hardware threads, provides greater efficiency rather than executing a single application with large thread counts. However, contention for shared resources can limit the improvement of concurrent application execution: orchestrating the number of threads used by each application and is essential. In this article, we contribute SCALO, a solution to orchestrate concurrent application execution to increase throughput. SCALO monitors co-executing applications at runtime to evaluate their scalability. Its optimizing thread allocator analyzes these scalability estimates to adapt the parallelism of each program. Unlike previous approaches, SCALO differs by including dynamic contention effects on scalability and by controlling the parallelism during the execution of parallel regions. Thus, it improves throughput when other state-of-the-art approaches fail and outperforms them by up to 40% when they succeed.

Task clustering has proven to be an effective method to reduce execution overhead and to improve the computational granularity of scientific workflow tasks executing on distributed resources. However, a job composed of multiple tasks may have a higher risk of suffering from failures than a single task job. In this paper, we conduct a theoretical analysis of the impact of transient failures on the runtime performance of scientific workflow executions. We propose a general task failure modeling framework that uses a maximum likelihood estimation-based parameter estimation process to model workflow performance. We further propose three fault-tolerant clustering strategies to improve the runtime performance of workflow executions in faulty execution environments. Experimental results show that failures can have significant impact on executions where task clustering policies are not fault-tolerant, and that our solutions yield makespan improvements in such scenarios. In addition, we propose a dynamic task clustering strategy to optimize the workflow's makespan by dynamically adjusting the clustering granularity when failures arise. A trace-based simulation of five real workflows shows that our dynamic method is able to adapt to unexpected behaviors, and yields better makespans when compared to static methods.

Providing standardized building blocks for task-parallel programs within a language and its standard library has several advantages over other solutions. Close integration with compilers and runtime systems allows for potentially higher performance and portability facilitates wide-spread use. In the recently ratified C++11 standard, language constructs have been added along with a memory model to provide the developer with such building blocks. They allow accessing task parallelism and synchronization in a flexible and standardized way, potentially removing the need for third-party solutions. Nevertheless, since parallelization aims at high performance, an examination of the quality of implementation of these standardized means is necessary to determine their suitability for replacing established solutions. To that end, we present INNCABS, a new cross-platform cross-library benchmark suite consisting of 14 benchmarks with varying task granularities and synchronization requirements. Based on these benchmarks, we demonstrate that the performance of C++11 parallelism constructs in the three most commonly employed C++ runtime libraries prevents their use as a full replacement for third-party solutions due to simplistic parallelism implementations and high synchronization overheads.

Summary A random field (RF) is a set of correlated random variables associated with different spatial locations. RF generation algorithms are of crucial importance for many scientific areas, such as astrophysics, geostatistics, computer graphics, and many others. Current approaches commonly make use of 3D fast Fourier transform (FFT), which does not scale well for RF bigger than the available memory; they are also limited to regular rectilinear meshes. We introduce random field generation with the turning band method (RAFT), an RF generation algorithm based on the turning band method that is optimized for massively parallel hardware such as GPUs and accelerators. Our algorithm replaces the 3D FFT with a lower‐order, one‐dimensional FFT followed by a projection step and is further optimized with loop unrolling and blocking. RAFT can easily generate RF on non‐regular (non‐uniform) meshes and efficiently produce fields with mesh sizes bigger than the available device memory by using a streaming, out‐of‐core approach. Our algorithm generates RF with the correct statistical behavior and is tested on a variety of modern hardware, such as NVIDIA Tesla, AMD FirePro and Intel Phi. RAFT is faster than the traditional methods on regular meshes and has been successfully applied to two real case scenarios: planetary nebulae and cosmological simulations. Copyright © 2015 John Wiley & Sons, Ltd.

Energy consumption optimization of HPC applications inherently requires measurements for reference and comparison. However, most of today's systems lack the necessary hardware support for power or energy measurements. Furthermore, in-band data availability is preferred for specific optimization techniques such as auto-tuning. For this reason, we present in-band energy consumption models for the IBM POWER7 processor based on hardware counters. We demonstrate that linear regression is a suitable means for modeling energy consumption, and we rely on already available, high-level benchmarks for training instead of self-written or hand-tuned micro-kernels. We compare modeling efforts for different instruction mixes caused by two compilers (GCC and IBM XL) as well as various multi-threading usage scenarios, and validate across our training benchmarks and two real-world applications. Results show mean errors of approximately 1% and overall max errors of 5.3% for GCC.

SUMMARY Task parallelism is a programming technique that has been shown to be applicable in a wide variety of problem domains. A central parameter that needs to be controlled to ensure efficient execution of task parallel programs is the granularity of tasks. When they are too coarse grained, scalability and load balance suffer, while very fine‐grained tasks introduce execution overheads. We present a combined compiler and runtime approach that enables automatic granularity control. Starting from recursive, task parallel programs, our compiler generates multiple versions of each task, increasing granularity by task unrolling. Subsequently, we apply a parallelism‐aware optimizing transformation to remove superfluous task synchronization primitives in all generated versions. A runtime system then selects among these task versions of varying granularity by locally tracking task demand. Benchmarking on a set of task parallel programs using a work‐stealing scheduler demonstrates that our approach is generally effective. For fine‐grained tasks, we can achieve reductions in execution time exceeding a factor of 6, compared with state‐of‐the‐art implementations. Additionally, we evaluate the impact of two crucial algorithmic parameters, the number of generated code versions and the task queue length, on the performance of our method. Copyright © 2014 John Wiley & Sons, Ltd.

Large-scale compute clusters of heterogeneous nodes equipped with multi-core CPUs and GPUs are getting increasingly popular in the scientific community. However, such systems require a combination of different programming paradigms making application development very challenging. In this article we introduce libWater, a library-based extension of the OpenCL programming model that simplifies the development of heterogeneous distributed applications. libWater consists of a simple interface, which is a transparent abstraction of the underlying distributed architecture, offering advanced features such as inter-context and inter-node device synchronization. It provides a runtime system which tracks dependency information enforced by event synchronization to dynamically build a DAG of commands, on which we automatically apply two optimizations: collective communication pattern detection and device-host-device copy removal. We assess libWater's performance in three compute clusters available from the Vienna Scientific Cluster, the Barcelona Supercomputing Center and the University of Innsbruck, demonstrating improved performance and scaling with different test applications and configurations.

Programming standards like OpenMP, OpenCL and MPI are frequently considered programming languages for developing parallel applications for their respective kind of architecture. Nevertheless, compilers treat them like ordinary APIs utilized by an otherwise sequential host language. Their parallel control flow remains hidden within opaque runtime library calls which are embedded within a sequential intermediate representation lacking the concepts of parallelism. Consequently, the tuning and coordination of parallelism is clearly beyond the scope of conventional optimizing compilers and hence left to the programmer or the runtime system. The main objective of the Insieme compiler is to overcome this limitation by utilizing INSPIRE, a unified, parallel, highlevel intermediate representation. Instead of mapping parallel constructs and APIs to external routines, their behavior is modeled explicitly using a unified and fixed set of parallel language constructs. Making the parallel control flow accessible to the compiler lays the foundation for the development of reusable, static and dynamic analyses and transformations bridging the gap between a variety of parallel paradigms. Within this paper we describe the structure of INSPIRE and elaborate the considerations which influenced its design. Furthermore, we demonstrate its expressiveness by illustrating the encoding of a variety of parallel language constructs and we evaluate its ability to preserve performance relevant aspects of input codes.

Public commercial clouds emerged as new and attractive resource provisioning option for scientific computing. This new alternative raises new challenges for users of such clouds, since optimizing the completion time of scientific applications might substantially increase the monetary cost of leasing cloud resources. In this paper, we first propose a set of basic rescheduling operations covering a broad set of scenarios for reducing the costs of running scientific workflows in clouds. Based on them, we design two heuristic scheduling algorithms. The first algorithm aims at reducing the cost of resource provisioning while still attaining the optimal make span. The second algorithm further reduces the costs to meet a budget constraint with a small increase in the make span. The experiments conducted using real-world and synthetic workflow applications demonstrate important benefits compared to related state-of-the-art approaches.

Clusters of heterogeneous nodes composed of multi-core CPUs and GPUs are increasingly being used for High Performance Computing (HPC) due to the benefits in peak performance and energy efficiency. In order to fully harvest the computational capabilities of such architectures, application developers often employ a combination of different parallel programming paradigms (e.g. OpenCL, CUDA, MPI and OpenMP), also known in literature as hybrid programming, which makes application development very challenging. Furthermore, these languages offer limited support to orchestrate data and computations for heterogeneous systems.

Unleashing the full potential of heterogeneous systems, consisting of multi-core CPUs and GPUs, is a challenging task due to the difference in processing capabilities, memory availability, and communication latencies of different computational resources.

In this paper we propose a novel approach which automatizes task partitioning in heterogeneous systems. Our framework is based on the Insieme Compiler and Runtime infrastructure. The compiler translates a single-device OpenCL program into a multi-device OpenCL program. The runtime system then performs dynamic task partitioning based on an offline-generated prediction model. In order to derive the prediction model, we use a machine learning approach that incorporates static program features as well as dynamic, input sensitive features. Our approach has been evaluated over a suite of 23 programs and achieves performance improvements compared to an execution of the benchmarks on a single CPU and a single GPU only.

The ultimate goal of cloud providers by providing resources is increasing their revenues. This goal leads to a selfish behavior that negatively affects the users of a commercial multicloud environment. In this paper, we introduce a pricing model and a truthful mechanism for scheduling single tasks considering two objectives: monetary cost and completion time. With respect to the social cost of the mechanism, i.e., minimizing the completion time and monetary cost, we extend the mechanism for dynamic scheduling of scientific workflows. We theoretically analyze the truthfulness and the efficiency of the mechanism and present extensive experimental results showing significant impact of the selfish behavior of the cloud providers on the efficiency of the whole system. The experiments conducted using real-world and synthetic workflow applications demonstrate that our solutions dominate in most cases the Pareto-optimal solutions estimated by two classical multiobjective evolutionary algorithms.

Traditional scheduling research usually targets make span as the only optimization goal, while several isolated efforts addressed the problem by considering at most two objectives. In this paper we propose a general framework and heuristic algorithm for multi-objective static scheduling of scientific workflows in heterogeneous computing environments. The algorithm uses constraints specified by the user for each objective and approximates the optimal solution by applying a double strategy: maximizing the distance to the constraint vector for dominant solutions and minimizing it otherwise. We analyze and classify different objectives with respect to their impact on the optimization process and present a four-objective case study comprising make span, economic cost, energy consumption, and reliability. We implemented the algorithm as part of the ASKALON environment for Grid and Cloud computing. Results for two real-world applications demonstrate that the solutions generated by our algorithm are superior to user-defined constraints most of the time. Moreover, the algorithm outperforms a related bi-criteria heuristic and a bi-criteria genetic algorithm.

Message passing has been adopted as the main programming paradigm for many-core processors with on-chip networks for inter-core communication. To this end, message-passing libraries such as MPI can be used, as they provide well-known interfaces to application developers. Since MPI implementations were originally developed for macroscopic computer networks, the different characteristics of on-chip networks may require rethinking existing solutions. With the example of All reduce, we identify points where collective operations benefit from routines optimized for on-chip networks. The identified issues are then applied to additional collectives including Broadcast, All gather and All to all. The effectiveness of the proposed optimizations is demonstrated on the Single-Chip Cloud Computer (SCC), a many-core research chip created by Intel Labs. Experiments show that collective operations subjected to the identified optimizations are accelerated by factors roughly between 2 to 3 compared to current state of the art implementations. In addition to synthetic benchmarks, we show that the use of the optimized routines accelerates a scientific application by more than 40%.

Several researchers investigated the placing of communication calls in message-passing parallel codes. The current rule of thumb it to maximize communication/computation overlap with early binding. In this work, we demonstrate that this is not the only design constraint because CPU caches can have a significant impact on communications. We conduct an empirical study of the interaction between CPU caching and communications for several different communication scenarios. We use the gained insight to formulate a set of intuitive rules for communication call placement and show how our rules can be applied to practical codes. Our optimized codes show an improvement of up to 40% for a simple stencil code. Our work is a first step towards communication optimizations by moving communication calls. We expect that future communication-aware compilers will use our insights as a standard technique to move communication calls in order to optimize performance.

Today, the use of GPUs as coprocessors to accelerate high-performance scientific applications is becoming an important practice. Still, some of the high-level programming languages such as Java require extensions or new interfaces for utilising the huge parallelism of these new devices. In this paper, we propose extensions to an existing Java-based programming and parallel computing environment called Java Symphony to enable Java applications use accelerating devices such as GPUs with little API programmability change. With Java Symphony, a parallel Java application can be uniformly programmed and executed on heterogeneous platforms consisting of conventional parallel computers enhanced with data-parallel coprocessors such as GPUs. We report results on using Java Symphony for programming and improving the performance of six real applications and benchmarks in a heterogeneous environment consisting of a combination of different multi-core CPU and GPU devices.

The Message Passing Interface (MPI) provides bindings for the three programming languages commonly used in High Performance Computing (HPC): C, C++ and Fortran. Unfortunately, MPI supports only the lowest common denominator of the three languages, providing a level of abstraction far lower than typical C++ libraries. Lately, after the decision of the MPI committee to deprecate and remove the C++ bindings from the MPI standard, programmers are forced to use either the C API or rely on third-party libraries. In this paper we present a lightweight, header-only C++ interface to MPI which uses object oriented and generic programming concepts to improve its integration into the C++ programming language. We compare our wrapper with a related approach called Boost. MPI showing how MPP facilitates the interaction with C++ objects. Performance wise, MPP outperforms Boost. MPI by reducing the interface overhead by a factor of eight. Additionally, MPP's handling of user-defined data types allows transferring of STL containers (e.g. std::list) up to 20 times faster than Boost. MPI for small linked lists by relying on software serialization.

In this paper we introduce a multi-objective autotuning framework comprising compiler and runtime components. Focusing on individual code regions, our compiler uses a novel search technique to compute a set of optimal solutions, which are encoded into a multi-versioned executable. This enables the runtime system to choose specifically tuned code versions when dynamically adjusting to changing circumstances. We demonstrate our method by tuning loop tiling in cache-sensitive parallel programs, optimizing for both runtime and efficiency. Our static optimizer finds solutions matching or surpassing those determined by exhaustively sampling the search space on a regular grid, while using less than 4% of the computational effort on average. Additionally, we show that parallelism-aware multi-versioning approaches like our own gain a performance improvement of up to 70% over solutions tuned for only one specific number of threads.

Commercial distributed systems such as Clouds are managed by selfish providers that strategically try to increase their revenues regardless of the utility of other providers and users. These selfish behaviors affect the efficiency of using such environments. In this paper, based on a general game theoretic truthful reverse auction mechanism, we investigate the scheduling problem of dependent tasks on distributed Cloud resources owned by selfish providers. The social cost of the game is to minimize the make span and monetary cost simultaneously. Extensive simulation experiments show that the schedules obtained are approximately Pareto optimal.

Over the past years there has been a steady change in CPU design towards both many-core processors and power-aware hardware architectures. These two trends are combined in the Intel Single-chip Cloud Computer (SCC), an experimental prototype with 48 Pentium cores created by Intel Labs. The SCC is a highly configurable many-core chip which provides unique opportunities to optimize run time, communication and memory access as well as power/energy consumption of parallel programs. The aim of this paper is to characterize the performance behavior of the chip with various power settings, mappings of processes/cores to memory controllers, etc through benchmarking. Analytical models are used to verify and interpret the results. Conclusions drawn from our benchmark outcomes are that data exchange based on message passing is faster than shared memory data exchange. Contrary to popular belief, lowest energy consumption is not achieved for the fastest execution time. Furthermore in order to improve the memory access behavior one should increase the clock frequency of both, mesh network and memory controllers. In general, the results of our investigations can be used to analyze the effect of power settings and architecture properties on the performance and energy consumption of parallel programs as well as assist in choosing appropriate settings for specific workloads.

Performance evaluations of large-scale systems require the use of representative workloads with certifiable similar or dissimilar characteristics. To quantify the similarity of the characteristics, we describe a novel measure comprising two efficient methods that are suitable for large-scale workloads. One method uses the discrete wavelet transform to assess the periodic time and frequency characteristics in the workload. The second method evaluates dependencies in descriptive attributes via association rule learning. Both methods are evaluated to find the limits of their similarity spaces. Additionally, the wavelet method is evaluated against existing similarity methods and tested for noise robustness and random bias. An empirical study using workloads from seven operational large-scale systems evaluates the measure's accuracy. The results show that our measure is highly resistant to noise, well-suited for large-scale workloads, covers 87% of the possible similarity space, and improves accuracy by 24.5% and standard deviation by 10.8% when compared to existing work.

Today, highly successful Massively Multiplayer Online Games (MMOGs) have millions of registered users and hundreds of thousands of active concurrent players. To sustain their highly variable load, game operators over-provision a large static infrastructure capable of sustaining the game peak load, even though a large portion of the resources is unused most of the time. This inefficient resource utilisation has negative economic impacts by preventing any but the largest hosting centres from joining the market and dramatically increases prices.In this paper, we propose a new business model of hosting and operating MMOGs based on Cloud computing principles involving four actors: resource provider, game operator, game provider, and client. Our model efficiently provisions on-demand virtualised resources to game sessions based on their dynamic client load, which dramatically decreases prices and gives small and medium enterprises the opportunity of joining the market through zero initial investment.We validate our new model and its underlying business relationships through trace-based simulations utilising six months worth of monitoring data from a real-life MMOG using emulated resources from 16 of the largest Cloud resource providers currently on the market. We demonstrate that our model can operate state-of-the-art MMOGs with an average monthly gross profit of nearly $6 million excluding game purchase prices, overheads and taxation, while being able to maintain and control the QoS offered to all clients. Finally, we show how our approach is capable of operating next generation very highly interactive MMOGs with a small increase of 5.8% in the subscription price.

Cloud computing is an emerging commercial infrastructure paradigm that promises to eliminate the need for maintaining expensive computing facilities by companies and institutes alike. Through the use of virtualization and resource time sharing, clouds serve with a single set of physical resources a large user base with different needs. Thus, clouds have the potential to provide to their owners the benefits of an economy of scale and, at the same time, become an alternative for scientists to clusters, grids, and parallel production environments. However, the current commercial clouds have been built to support web and small database workloads, which are very different from typical scientific computing workloads. Moreover, the use of virtualization and resource time sharing may introduce significant performance penalties for the demanding scientific computing workloads. In this work, we analyze the performance of cloud computing services for scientific computing workloads. We quantify the presence in real scientific computing workloads of Many-Task Computing (MTC) users, that is, of users who employ loosely coupled applications comprising many tasks to achieve their scientific goals. Then, we perform an empirical evaluation of the performance of four commercial cloud computing services including Amazon EC2, which is currently the largest commercial cloud. Last, we compare through trace-based simulation the performance characteristics and cost models of clouds and other scientific computing platforms, for general and MTC-based scientific computing workloads. Our results indicate that the current clouds need an order of magnitude in performance improvement to be useful to the scientific community, and show which improvements should be considered first to address this discrepancy between offer and demand.

Non-periodic bursts are prevalent in workloads of large scale applications. Existing workload models do not predict such non-periodic bursts very well because they mainly focus on repeatable base functions. We begin by showing the necessity to include bursts in workload models by investigating their detrimental effects in a petabyte-scale distributed data management system. This work then makes three contributions. First, we analyse the accuracy of five existing prediction models on workloads of data and computational grids, as well as derived synthetic workloads. Second, we introduce a novel averages-based model to predict bursts in arbitrary workloads. Third, we present a novel metric, mean absolute estimated distance, to assess the prediction accuracy of the model. Using our model and metric, we show that burst behaviour in workloads can be identified, quantified and predicted independently of the underlying base functions. Furthermore, our model and metric are applicable to arbitrary kinds of burst prediction for time series.

Grid schedulers require individual activity performance predictions to map workflow activities on different Grid sites. The effectiveness of the scheduling systems is hampered by inaccurate predictions due to the inability of existing predictors to effectively model the dynamic and heterogeneous nature of Grid resources, or the wide range of problem sizes and runtime arguments. To address this deficiency, we propose a hybrid Bayesian-neural network approach to dynamically model and predict the execution time of activities in real workflow applications. Bayesian network is used for a high-level representation of activities performance probability distribution against different factors affecting the performance. The important attributes are dynamically selected by the Bayesian network and fed into a radial basis function neural network to make further predictions. Our approach is generic to any type of scientific applications, and flexible to import expert knowledge to further improve accuracies. Experimental results for activities from three realworld workflow applications are presented to show effectiveness of our approach.

Workflow execution time predictions for Grid infrastructures is of critical importance for optimized workflow executions, advance reservations of resources, and overhead analysis. Predicting workflow execution time is complex due to multeity of workflow structures, involvement of several Grid resources in workflow execution, complex dependencies of workflow activities and dynamic behavior of the Grid. In this paper we present an online workflow execution time prediction system exploiting similarity templates. The workflows are characterized considering the attributes describing their performance at different Grid infrastructural levels. A ldquosupervised exhaustive searchrdquo is employed to find suitable templates. We also make a provision of including expert user knowledge about the workflow performance in the procession of our methods. Results for three real world applications are presented to show the effectiveness of our approach.

We present a probabilistic tracing method that captures both user and system behaviour for large-scale distributed applications. Our method extends the notion of data stream monitoring to work within what we define as concealed environments. We detail the conceptual design and implementation of our method. Additionally, we evaluate the scalability of the tracing method in a real petabyte-scale distributed data management system. Finally, we demonstrate the usefulness of the collected trace data in three scenarios. First, we use collected trace data to examine the arrival of user events and find self-similar processes. Second, we examine the behaviour and performance of mass storage systems in a grid under concurrent requests. Third, we develop a model for prediction of user event arrivals based on historical data. Our results suggest that a probabilistic tracing method is scalable, straightforward to integrate with existing applications, and provides useful insight into the behaviour of very large-scale applications.

Even though highly distributed environments such as Clouds and Grids are increasingly used for e-science high performance applications, they still cannot deliver the robustness and reliability needed for widespread acceptance as ubiquitous scientific tools. To overcome this problem, existing systems resort to fault tolerance mechanisms such as task replication and task resubmission. In this paper we propose a new heuristic called resubmission impact to enhance the fault tolerance support for scientific workflows in highly distributed systems. In contrast to related approaches, our method can be used effectively on systems even in the absence of historic failure trace data. Simulated experiments of three real scientific workflows in the Austrian Grid environment show that our algorithm drastically reduces the resource waste compared to conservative task replication and resubmission techniques, while having a comparable execution performance and only a slight decrease in the success probability.

The workflow paradigm is one of the most important programming models for the Grid. The composition of Grid workflows has been widely studied in the Grid community. However, there is still a lack of a general and efficient approach for automatic composition of Grid workflows. In this paper, we present a STRIPS (Stanford Research Institute Problem Solver) based formal definition of the Grid workflow composition problem, followed by a novel graph based algorithm for automatic composition of high quality (portable, fault tolerant and optimized) Grid workflows. Our algorithm searches for semantic descriptions of workflow activities, i.e., Activity Functions (AFs), defined by ontologies and composes them into Grid workflows using AF Data Dependence (ADD) graphs. The composition process consists of three phases: ADD graph creation, workflow extraction, and workflow optimization. The worst case complexity of our algorithm is quadratic in the number of AFs. An extension of our algorithm to compose Grid workflows with branches and loops is also presented. Experimental results illustrate the effectiveness and efficiency of our approach: (i) the measured worst case execution time of our algorithm further proofs the analyzed time complexity; (ii) the composition of the real world meteorology Grid workflow application MeteoAG with our algorithm takes approximate half a second; and (iii) the execution time of the MeteoAG workflow when running on the Austrian Grid is reduced by up to 25% and the speedup is increased by up to 2.24 by applying our workflow optimization techniques.

Workflow execution time prediction is widely seen as a key service to understand the performance behavior and support the optimization of Grid workflow applications. In this paper, we present a novel approach for estimating the execution time of workflows based on Local Learning. The workflows are characterized in terms of different attributes describing structural and runtime information about workflow activities, control and data flow dependencies, number of Grid sites, problem size, etc. Our local learning framework is complemented by a dynamic weighing scheme that assigns weights to workflow attributes reflecting their impact on the workflow execution time. Predictions are given through intervals bounded by the minimum and maximum predicted values, which are associated with a confidence value indicating the degree of confidence about the prediction accuracy. Evaluation results for three real world workflows on a real Grid are presented to demonstrate the prediction accuracy and overheads of the proposed method.

The grid is inherently unreliable due to its geographical dispersion, heterogeneity and the involvement of multiple administrative domains. The most general case of failures are so-called Byzantine failures where no assumptions about the behavior of faulty components can be made. In this paper a novel system is described that allows to diagnose and tolerate byzantine faults based on service replication. We suggest, briefly describe and compare two fail-stop and two byzantine fault tolerance algorithms. Given that many scientific larger-scale grid applications have complex outputs the comparison of replica results as needed to implement byzantine fault tolerance becomes a non-trivial task. Therefore we include an automation mechanism based on a generic description language and code generation for this particualar problem. Our approach has been implemented as extension to the Otho Toolkit, a system that synthesizes tailor-made wrapper services for a given application, grid environment and resource. An analysis of performance and overheads for three real-world applications completes our work.

The functional heterogeneity of computational Grids has highly increased due to inclusion of resources other than dedicated to Grid, like from non-dedicated desktop Grids, on-demand systems and even from P2P systems and mobile Grids. At such a diversified scale, resources exhibit different availability properties mainly due to administrators' policies for resource availability in the Grid, and their failure/unavailability properties. These make resources' availability predictions for optimized resource selection, a challenging problem. Addressing this problem, we characterize resource availability properties against their availability policies to understand their availability behavior and quantify it through availability models. We further exploit the availability/failure properties to make predictions about their availability through pattern recognition and classification. We have achieved, on average, accuracy of more than 90% and 75% in our predictions for resource instance availability and lifetime respectively.

The drift towards new challenges in grid computing, including the utility grid paradigm and service level agreements based on quality-of-service guarantees, implies the need for new, robust, multi-criteria scheduling algorithms that can be applied by the user in an intuitive way. Multiple scheduling criteria addressed by the related grid research include execution time, the cost of running a task on a machine, reliability, and different data quality metrics. The existing bi-criteria scheduling approaches are usually dedicated for certain criterion pairs only that require the user to define one's preferences either as weights assigned to the criteria or as fixed constraints defined for one of the criteria. These requirements are often not feasible for the user and not suited to the specificity of the multi- criteria scheduling problem. We propose a novel requirement specification method based on a sliding constraint, and we model the problem as an extension of the multiple-choice knapsack problem. We propose a general bi-criteria scheduling heuristic called dynamic constraint algorithm (DCA) based on dynamic programming, dedicated to the problem model defined by us. In the experimental study, we show that in most of the problem variants, DCA outperforms two existing algorithms designed for the same problem. It also shows relatively low scheduling times for workflows of medium size.

Classification turns chaotic knowledge into regularity by systematizing a domain and providing a common vocabulary. Currently there is a lack of systematic and comprehensive studies in organization and classification of Grid faults. We address this gap with a multi-perspective Grid fault taxonomy describing an incident using eight different characteristics. It is hard to define a taxonomy of broad validity and acceptance that satisfies the vast number of requirements of the many Grid user communities. Nevertheless we proof that our taxonomy can serve as a solid basis for defining project-specific custom classification schemes by giving a concrete example created for a state-of-the-art Grid middleware environment.

Today's massively multiplayer online games (MMOGs) can include millions of concurrent players spread across the world. To keep these highly-interactive virtual environments online, a MMOG operator may need to provision tens of thousands of computing resources from various data centers. Faced with large resource demand variability, and with misfit resource renting policies, the current industry practice is to maintain for each game tens of self-owned data centers. In this work we investigate the dynamic resource provisioning from external data centers for MMOG operation. We introduce a novel MMOG workload model that represents the dynamics of both the player population and the player interactions. We evaluate several algorithms, including a novel neural network predictor, for predicting the resource demand. Using trace-based simulation, we evaluate the impact of the data center policies on the resource provisioning efficiency; we show that dynamic provisioning can be much more efficient than its static alternative.

Existing knowledge based grid workflow languages and composition tools require sophisticated expertise of domain scientists in order to automate the process of managing workflows and its components (activities). So far semantic workflow specification and management has not been addressed from a general and integrated perspective. This paper presents a novel domain oriented approach which features separations of concerns between data meaning and data representation and between activity function (semantic description of workflow activities) and activity type (syntactic description of workflow activities). These separations are implemented as part of abstract grid workflow language (AGWL) which supports the development of grid workflows at a high level (semantic) of abstraction. The corresponding workflow composition tool simplifies grid workflow composition by (i) enabling users to compose grid workflows at the level of data meaning and activity function that shields the complexity of the grid, any specific implementation technology (e.g. Web or Grid service) and any specific data representation, (ii) semi-automatic data flow composition, and (iii) automatic data conversions. We have implemented our approach as part of the ASKALON grid application development and computing environment. We demonstrate the effectiveness of our approach by applying it to a real world meteorology workflow application and report some preliminary results. Our approach can also be adapted to other scientific domains by developing the corresponding ontologies for those domains.

Grid economy models have long been considered as a promising alternative for the classical Grid resource management, due to their dynamic and decentralized nature, and because the financial valuation of resources and services is inherent in any such model. In particular, auction models are widely used in the existing Grid research, as they are easy to implement and are shown to successfully manage resource allocation on the Grid market. The focus on the current work is on workflow scheduling in the Grid resource allocation model based on Continuous Double Auctions (CDA). We analyze different scheduling strategies that can be applied by the user to execute workflows in such an environment, and try to identify the general behavioral patterns that can lead to a fast and cheap workflow execution. In the experimental study, we show that under certain circumstances some benefit can be gained by applying an ldquoaggressiverdquo scheduling strategy.

Quick and accurate identification of the root cause of failures is an important prerequisite for any reliable system. However with increasing Grid size and complexity, the manual diagnosis of application faults becomes impractical, tedious and time-consuming. So far there has been a lack of systematic and comprehensive studies in organization and classification of Grid faults. We address this gap with a multi-perspective Grid fault taxonomy precisely describing an incident using eight different characteristics. Based on that, we develop a pragmatic model-based technique for application-specific fault diagnosis using indicators, symptoms and rules. Customized wrapper services then apply this knowledge to reason about the root causes of failures. In addition to applying user-provided diagnosis models we demonstrate that given a set of past classified fault events it is possible to automatically extract new models through learning. We investigated and compared several supervised classification learning and cluster analysis algorithms for this purpose. Our approach was implemented as part of the Otho Toolkit, a framework for "service-enabling" legacy applications by synthesizing tailor-made wrapper service.

Scientific workflows are a topic of great interest in the grid community that sees in the workflow model an attractive paradigm for programming distributed wide-area grid infrastructures. Traditionally, the grid workflow execution is approached as a pure best effort scheduling problem that maps the activities onto the grid processors based on appropriate optimization or local matchmaking heuristics such that the overall execution time is minimized. Even though such heuristics often deliver effective results, the execution in dynamic and unpredictable grid environments is prone to severe performance losses that must be understood for minimizing the completion time or for the efficient use of high-performance resources. In this paper, we propose a new systematic approach to help the scientists and middleware developers understand the most severe sources of performance losses that occur when executing scientific workflows in dynamic grid environments. We introduce an ideal model for the lowest execution time that can be achieved by a workflow and explain the difference to the real measured grid execution time based on a hierarchy of performance overheads for grid computing. We describe how to systematically measure and compute the overheads from individual activities to larger workflow regions and adjust well-known parallel processing metrics to the scope of grid computing, including speedup and efficiency. We present a distributed online tool for computing and analyzing the performance overheads in real time based on event correlation techniques and introduce several performance contracts as quality-of-service parameters to be enforced during the workflow execution beyond traditional best effort practices. We illustrate our method through postmortem and online performance analysis of two real-world workflow applications executed in the Austrian grid environment.

On-demand synthesis of grid activities can play a significant role in automatic workflow composition and in improving quality of the grid resource provisioning. However, in the grid, synthesis of activities has been largely ignored due to the limited expressiveness of the representation of activity capabilities and the lack of adapted resource management means to take advantage of such activity synthesis. This paper introduces a new mechanism for automatic synthesis of available activities in the grid by applying ontology rules. Rule-based synthesis combines multiple primitive activities to form new compound activities. The synthesized activities can be provisioned as new or alternative options for negotiation as well as advance reservation. This is a major advantage compared to other approaches that only focus on resource matching and brokerage. Furthermore, the new synthesized activities provide aggregated capabilities that otherwise may not be possible, leading towards an automatic generation of grid workflows. We developed a prototype to demonstrate advantages of our approach.

Scheduling large-scale applications on the Grid is a fundamental challenge and is critical to application performance and cost. Large-scale applications typically contain a large number of homogeneous and concurrent activities which are main bottlenecks, but open great potentials for optimization. This paper presents a new formulation of the well-known NP-complete problems and two novel algorithms that addresses the problems. The optimization problems are formulated as sequential cooperative games among workflow managers. Experimental results indicate that we have successfully devised and implemented one group of effective, efficient, and feasible approaches. They can produce soultuins of significantly better performance and cost than traditional algorithms. Our algorithms have considerably low time complexity and can assign 1,000,000 activities to 10,000 processors within 0.4 second on one Opteron processor. Moreover, the solutions can be practically performed by workflow managers, and the violation of QoS can be easily detected, which are critical to fault tolerance.

Existing work does not provide a flexible dataset-oriented data flow mechanism to meet the complex requirements of scientific Grid workflow applications. In this paper we present a sophisticated approach to this problem by introducing a data collection concept and the corresponding collection distribution constructs, which are inspired by HPF, however applied to Grid workflow applications. Based on these constructs, more fine-grained data flows can be specified at an abstract workflow language level, such as mapping a portion of a dataset to an activity, independently distributing multiple datasets, not necessarily with the same number of data elements, onto loop iterations. Our approach reduces data duplication, optimizes data transfers as well as simplifies the effort to port workflow applications onto the Grid. We have extended AGWL with these concepts and implemented the corresponding runtime support in ASKALON. We apply our approach to some real world scientific workflow applications and report performance results.

Extraordinary long lifecycles of many scientific applications commonly surpass multiple generations of Grid technologies. Therefore the smooth adaptation and migration to newer environments remains as interesting research question. This paper presents the Otho Toolkit for synthesis of application-specific Grid service wrappers based on specifications of scientific legacy programs. The services are customised and tailor-made for a specific application, service hosting environment and computational infrastructure and include source code for optional manual refinement. We demonstrate its unique combination of advanced features like support for multiple service platforms, parameter sweeping, iterative and parallel programs, progress-reporting, filestaging and security credential management. Moreover our services reliably identify program termination-causes based on programmatically evaluated post-mortem program states. We applied the Otho Toolkit recursively to itself to synthesise a sophisticated Factory service that creates application-specific Grid services on-demand^1.

Application execution time prediction is of key importance in making decisions about efficient usage of Grid resources. Grid services lack support of a generic application execution time prediction service due to environment specific solutions provided by the existing prediction techniques. To remedy this, we present a generic and comprehensive system to provide execution time predictions of applications on different Grid-sites. Our system is based on a two layered training phase to minimize the training effort, which is our first main contribution. The training phase is driven by a novel experimental design. We also introduce a mechanism of sharing performance measurements across the Grid, on the basis of soft benchmarks, which is our second contribution. Both of these phases support our prediction engine to serve robust predictions. Experiments from the prototype implementation are shown to demonstrate the effectiveness of our proposed system.

Static scheduling and execution of Grid workflows is prone to severe performance losses due to inaccurate predictions or the dynamic nature of the Grid environment. In this paper we present an online tool for analysing the performance overheads that appear during the real-time execution of workflow applications in Grid environments. We employ event correlation techniques and a distributed superpeer architecture in which each peer correlates local lowlevel activity and middleware events to infer performance overheads related to larger workflow regions at a higher level of abstraction. The rule-based correlation technique provides full extensibility to our approach that requires no source code modification. We demonstrate the functionality of our tool through online performance analysis of a real-world workflow application executed in a Grid environment. We present automatically generated online graphs of correlated events that promptly signal to the end-users the real reasons of run-time performance overheads in their executions.

Grid workflows for e-science are complex and prone to failures. However, there is a lack of performance monitoring and analysis tools for supporting the user as well as workflow middleware to monitor and understand the performance of complex interactions among Grid applications, middleware and resources involved in workflow executions. In this paper, we present a novel integrated environment which supports online performance monitoring and analysis of service-oriented workflows. Performance monitoring and analysis of Grid workflows and infrastructure is conducted through a Web portal. Performance overheads of Grid workflows are analyzed in a systematic way, and performance problems can be detected during runtime. Moreover, we present several languages that alleviate the interaction among performance monitoring and analysis services and their clients. Our system has been integrated into the K-WfGrid knowledge-based workflow system. It plays a key role in supporting the user and developer to analyze their workflows and in providing performance knowledge for constructing and executing workflows.

QoS (Quality of Service) parameters play a key role in selecting Grid resources and optimizing resources usage efficiently. Although many works have focused on using QoS metrics, surprisingly few tools support the monitoring and analysis of QoS metrics of Grid services. This paper presents a novel framework which supports the monitoring and analysis of QoS metrics in the Grid. Our approach is that, firstly, we develop a classification of important QoS metrics for Grid services that should be monitored and analyzed. Secondly, sensors are developed to monitor QoS of disparate Grid services by using a peer-to-peer Grid monitoring middleware. The dependencies among Grid services are modeled. Based on that, several techniques are used to analyze QoS metrics of dependent Grid services

In this paper we present an extension to devise and implement advance reservation as part of the scheduling and resource management services of the ASKALON Grid application development and runtime environment. The scheduling service has been enhanced to offer a list of resources that can execute a specific task and to negotiatewith the resource manager about resources capable of processing tasks in the shortest possible time. We introduce progressive reservation approach which tries to allocate resources based on a fair-share principle. Experiments are shown that demonstrate the effectiveness of our approach, and that reflect different QoS parameters including performance, predictability, resource usage and resource fairness.

This paper describes a novel approach to fault detection and prediction on the grid based on data mining techniques. Data mining techniques are here applied as a mean to effectively process the significant amount of captured data from grid sites, services, workflows and activities. The paper provides a first approach of proposed techniques in terms of its ability of utilizing relevant information and the fault tolerance requirements. Such approach is one intelligent, distributed framework of fault detection and prediction for anomaly and failed activity by using resource- and workflow-based information. We use fault predictions to improve the performance of the workflow execution by avoiding potential faults of activities

We propose a novel approach for bi-criteria scheduling of scientific workflows on the grid, using dynamic programming to balance the trade-off between the two contradicting criteria. We determine the primary and the secondary criterion, and establish a flexible limit for the primary criterion. We identify different classes of criteria and adjust the solution for different variants of the problem

Summary form only given. While grid infrastructures can provide massive compute and data storage power, it is still an art to effectively harness the power of grid computing. Current application development for grid commonly requires the programmer to deal with many low level and complex details such as selecting software components on specific grid computers, mapping applications onto the grid, explicitly specify data transfer operations, etc. In this talk we present the ASKALON environment whose goal is to create an invisible grid for both grid users and application developers. ASKALON is centered around a set of high level services for transparent and effective grid access, including a scheduler for optimized mapping of workflows onto the grid, an enactment engine for reliable application execution, a resource manager covering both computers and application components, and a performance prediction and analysis service based on a training phase, analytical models and dynamic measurements. A sophisticated XML-based programming interface that shields the user form the grid middleware details, allows the high level composition of workflow applications. ASKALON is used to develop and port scientific applications as workflows in the Austrian grid. Experimental results using several real world scientific applications to demonstrate the effectiveness of ASKALON is demonstrated

Advance reservation of Grid resources can play a key role in enabling Grid middleware to deliver on-demand resource provision with significantly improved Quality-of-Service (QoS). However, in the Grid, advance reservation has been largely ignored due to the dynamic Grid behavior, under-utilization concerns, multi-constrained applications, and lack of support for agreement enforcement. These issues force the Grid middleware to make resource allocations at runtime with reduced QoS. To remedy these, we introduce a new, 3-layered negotiation protocol for advance reservation of the Grid resources. We model resource allocation as an on-line strip packing problem and introduce a new mechanism that optimizes resource utilization and QoS constraints while generating the contention-free solutions. The mechanism supports open reservations to deal with the dynamic Grid and provides a practical solution for agreement enforcement. We have implemented a prototype and performed experiments to demonstrate the effectiveness of our approach.

Currently grid application developers often configure available application components into a workflow of tasks that they can submit for executing on the grid. In this paper, we present an abstract grid workflow language (AGWL) for describing grid workflow applications at a high level of abstraction. AGWL has been designed such that the user can concentrate on specifying grid applications without dealing with either the complexity of the grid or any specific implementation technology (e.g. Web service). AGWL is an XML-based language which allows a programmer to define a graph of activities that refer mostly to computational tasks. Activities are connected by control and data flow links. A rich set of constructs (compound activities) is provided to simplify the specification of grid workflow applications which includes compound activities such as if, forEach and while loops as well as advanced compound activities including parallel sections, parallel loops and collection iterators. Moreover, AGWL supports a generic high level access mechanism to data repositories. AGWL is the main interface to the ASKALON grid application development environment and has been applied to numerous real world applications. We describe a material science workflow that has been successfully ported to a grid infrastructure based on an AGWL specification. Only a dozen AGWL activities are needed to describe a workflow with several hundred activity instances.

This paper deals with the challenging problem of performance analysis for Java programs. We describe procedures and requirements for instrumenting, monitoring, and analyzing distributed Java codes, and introduces Aksum, a highly customizable and flexible system for performance analysis that helps programmers to semi-automatically locate and understand performance problems in parallel and distributed Java programs. We also describe a sophisticated agent architecture as part of Aksum for static and dynamic instrumentation of Java programs. Experiments are presented for a widely distributed application running on a heterogeneous set of machines with different operating systems to illustrate the usefulness of our approach.

To understand the performance of grid workflows, performance analysis tools have to select, measure and analyze various performance metrics of the workflows. However there is a lack of a comprehensive study of performance metrics which can be used to evaluate the performance of a workflow executed in the grid. This paper presents performance metrics that performance monitoring and analysis tools should provide during the evaluation of the performance of grid workflows. Performance metrics are associated with many levels of abstraction. We introduce an ontology for describing performance data of grid workflows. We describe how the ontology can he utilized for monitoring and analyzing the performance of grid workflows.

Although new Java virtual machines provide an API to obtain raw performance data, it is still the task of a skillful performance analysis tool to take all the strategic decisions for instrumentation and performance analysis of distributed Java programs. In this paper we demonstrate two new tools. Twilight and Aksum, which try to automatically instrument code regions, to determine what performance data to collect, to interpret performance data, and to relate the bottlenecks found back to source code. We present experiments with a widely distributed Java application running on a heterogeneous set of machines with different operating systems to demonstrate the efficacy of our tools

Resource management is a key concern for implementing effective Grid middleware and shielding application developers from low level details. Existing resource managers concentrate mostly on physical resources. However, some advanced Grid programming environments allow application developers to specify Grid application components at high level of abstraction which then requires an effective mapping between high level application description (activity types) and actual deployed software components (activity deployments). This paper describes GLARE framework that provides dynamic registration, automatic deployment and on-demand provision of application components (activities) that can be used to build Grid applications. GLARE simplifies description and presentation of both activity types and deployments so that they can easily be located in the Grid and thus become available on-demand. GLARE has been implemented based on a super-peer model with support for activity leasing, self management, and fault tolerance. Experiments are shown to reflect the effectiveness of the GLARE.

Abstract There has been an increasing research interest in extending the use of Java towards performance‐oriented programming for distributed and concurrent applications. JavaSymphony is a Java‐based programming paradigm that allows the programmer to control parallelism, load balancing, and locality at a high level of abstraction. Objects can be explicitly distributed and migrated based on a high‐level API to static/dynamic system parameters and dynamic virtual distributed architectures, which impose a virtual hierarchy on a distributed system of physical computing nodes. In this paper we describe various extensions to the original JavaSymphony API, which includes a generalization of virtual architectures that can be used to specify and to request arbitrary heterogeneous distributed and concurrent architectures inside of a JavaSymphony program. The number of threads that execute an object's methods can be controlled dynamically through single‐ and multi‐threaded objects. Conventional Java objects can be dynamically converted to JavaSymphony objects. A (un)lock mechanism has been introduced in order to avoid inconsistent modifications of objects or virtual architectures. A sophisticated event mechanism for asynchronous communication, coordination, and interaction is provided. Several synchronization constructs including distributed barrier synchronization and synchronization for asynchronous method invocations have been included. Several experiments are presented to demonstrate the effectiveness and efficiency of JavaSymphony. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Performance engineering of parallel and distributed applications is a complex task that iterates through various phases, ranging from modeling and prediction, to performance measurement, experiment management, data collection, and bottleneck analysis. There is no evidence so far that all of these phases should/can be integrated into a single monolithic tool. Moreover, the emergence of computational Grids as a common single wide‐area platform for high‐performance computing raises the idea to provide tools as interacting Grid services that share resources, support interoperability among different users and tools, and, most importantly, provide omnipresent services over the Grid. We have developed the ASKALON tool set to support performance‐oriented development of parallel and distributed (Grid) applications. ASKALON comprises four tools, coherently integrated into a service‐oriented architecture. SCALEA is a performance instrumentation, measurement, and analysis tool of parallel and distributed applications. ZENTURIO is a general purpose experiment management tool with advanced support for multi‐experiment performance analysis and parameter studies. AKSUM provides semi‐automatic high‐level performance bottleneck detection through a special‐purpose performance property specification language. The PerformanceProphet enables the user to model and predict the performance of parallel applications at the early stages of development. In this paper we describe the overall architecture of the ASKALON tool set and outline the basic functionality of the four constituent tools. The structure of each tool is based on the composition and sharing of remote Grid services, thus enabling tool interoperability. In addition, a data repository allows the tools to share the common application performance and output data that have been derived by the individual tools. A service repository is used to store common portable Grid service implementations. A general‐purpose Factory service is employed to create service instances on arbitrary remote Grid sites. Discovering and dynamically binding to existing remote services is achieved through registry services. The ASKALON visualization diagrams support both online and post‐mortem visualization of performance and output data. We demonstrate the usefulness and effectiveness of ASKALON by applying the tools to real‐world applications. Copyright © 2005 John Wiley & Sons, Ltd.

In previous work we have introduced JavaSymphony, a system whose purpose is to simplify the development of distributed and parallel Java applications. JavaSymphony is a Java library that allows to control parallelism, load balancing, and locality at a high level. Objects can be explicitly distributed and migrated within virtual architectures, which impose a virtual hierarchy on a distributed system of physical computing nodes. In this paper we present the design of the JavaSymphony Runtime System and the JavaSymphony Shell. Moreover, we discuss details about an agent-based implementation of the JavaSymphony Runtime System which comprises the Network Agent, Object Agent, and Event Agent. We present a detailed comparison of the functionality provided by JavaSymphony with several related systems.

Abstract Many existing performance analysis tools lack the flexibility to control instrumentation and performance measurement for code regions and performance metrics of interest. Performance analysis is commonly restricted to single experiments. In this paper we present SCALEA, which is a performance instrumentation, measurement, analysis, and visualization tool for parallel programs that supports post‐mortem performance analysis. SCALEA currently focuses on performance analysis for OpenMP, MPI, HPF, and mixed parallel programs. It computes a variety of performance metrics based on a novel classification of overhead. SCALEA also supports multi‐experiment performance analysis that allows one to compare and to evaluate the performance outcome of several experiments. A highly flexible instrumentation and measurement system is provided which can be controlled by command‐line options and program directives. SCALEA can be interfaced by external tools through the provision of a full Fortran90 OpenMP/MPI/HPF frontend that allows one to instrument an abstract syntax tree at a very high‐level with C‐function calls and to generate source code. A graphical user interface is provided to view a large variety of performance metrics at the level of arbitrary code regions, threads, processes, and computational nodes for single‐ and multi‐experiment performance analysis. Copyright © 2003 John Wiley & Sons, Ltd.

In the past few years, increasing interest has been shown in using Java as a language for performance-oriented distributed and parallel computing. Most Java-based systems that support portable parallel and distributed computing either require the programmer to deal with intricate low level details of Java which can be a tedious, time-consuming and error-prone task, or prevent the programmer from controlling locality of data. In contrast to most existing systems, JavaSymphony - a class library written entirely in Java - allows to control parallelism, load balancing and locality at a high level. Objects can be explicitly distributed and migrated based on virtual architectures which impose a virtual hierarchy on a distributed/parallel system of physical computing nodes. The concept of blocking/nonblocking remote method invocation is used to exchange data among distributed objects and to process work by remote objects. We evaluate the JavaSymphony programming API for a variety of distributed/parallel algorithms which comprises backtracking, N-body, encryption/decryption algorithms and asynchronous nested optimization algorithms. Performance results are presented for both homogeneous and heterogeneous cluster architectures. Moreover, we compare JavaSymphony with an alternative well-known semi-automatic system.

The need to conduct and manage large sets of experiments for scientific applications dramatically increased over the last decade. However, there is still very little tool support for this complex and tedious process. We introduce the ZENTURIO experiment management system for parameter studies, performance analysis, and software testing for cluster and Grid architectures. ZENTURIO uses the ZEN directive-based language to specify arbitrary complex program executions. ZENTURIO is designed as a collection of Grid services that comprise: (1) a registry service which supports registering and locating Grid services; (2) an experiment generator that parses files with ZEN directives and instruments applications for performance analysis and parameter studies; (3) an experiment executor that compiles and controls the execution of experiments on the target machine. A graphical user portal allows the user to control and monitor the experiments and to automatically visualise performance and output data across multiple experiments. ZENTURIO has been implemented based on Java/Jini distributed technology. It supports experiment management on cluster architectures via PBS and on Grid infrastructures through GRAM. We report results of using ZENTURIO for performance analysis of an ocean simulation application and a parameter study of a computational finance code.

This paper describes ZEN, a directive-based language for the specification of arbitrarily complex program executions by varying the problem, system, or machine parameters for parallel and distributed applications. ZEN introduces directives to substitute strings and to insert assignment statements inside arbitrary files, such as program, input, script, or make-files. The programmer thus can invoke experiments for arbitrary value ranges of any problem parameter, including program variables, file names, compiler options, target machines, machine sizes, scheduling strategies, data distributions, etc. The number of experiments can be controlled through ZEN constraint directives. Finally, the programmer may request a large set of performance metrics to be computed for any code region of interest. The scope of ZEN directives can be restricted to arbitrary file or code regions. We implemented a prototype tool for automatic experiment management that is based on ZEN. We report results for the performance analysis of an ocean simulation application and for the parameter study of a computational finance code.

Abstract Debuggers play an important role in developing parallel applications. They are used to control the state of many processes, to present distributed information in a concise and clear way, to observe the execution behavior, and to detect and locate programming errors. More sophisticated debugging systems also try to improve understanding of global execution behavior and intricate details of a program. In this paper we describe the design and implementation of SPiDER, which is an interactive source‐level debugging system for both regular and irregular High‐Performance Fortran (HPF) programs. SPiDER combines a base debugging system for message‐passing programs with a high‐level debugger that interfaces with an HPF compiler. SPiDER, in addition to conventional debugging functionality, allows a single process of a parallel program to be expected or the entire program to be examined from a global point of view. A sophisticated visualization system has been developed and included in SPiDER to visualize data distributions, data‐to‐processor mapping relationships, and array values. SPiDER enables a programmer to dynamically change data distributions as well as array values. For arrays whose distribution can change during program execution, an animated replay displays the distribution sequence together with the associated source code location. Array values can be stored at individual execution points and compared against each other to examine execution behavior (e.g. convergence behavior of a numerical algorithm). Finally, SPiDER also offers limited support to evaluate the performance of parallel programs through a graphical load diagram. SPiDER has been fully implemented and is currently being used for the development of various real‐world applications. Several experiments are presented that demonstrate the usefulness of SPiDER. Copyright © 2002 John Wiley & Sons, Ltd.

In this paper we present JavaPSL, a Performance Specification Language that can be used for a systematic and portable specification of large classes of experiment-related data and performance properties for distributed and parallel programs. Performance properties are described in a generic and normalized way, thus interpretation and comparison of performance properties is largely alleviated. Moreover, JavaPSL provides meta-properties in order to describe new properties based on existing ones and to relate properties to each other.JavaPSL uses Java and its powerful mechanisms, in particular, polymorphism, abstract classes, and reflection to describe experiment-related data and performance properties. JavaPSL can also be considered as a performance information interface based on which sophisticated performance tools can be built or other tools can access performance data in a portable way.We have implemented a prototype performance tool that uses JavaPSL to automatically detect performance bottlenecks for MPI, OpenMP, and mixed OpenMP and MPI programs. Several experiments with realistic codes demonstrate the usefulness of JavaPSL.

In this paper we give an overview of SCALEA, which is a new performance analysis tool for OpenMP, MPI, HPF, and mixed parallel/distributed programs. SCALEA instruments, executes and measures programs and computes a variety of performance overheads based on a novel overhead classification. Source code and HW-profiling is combined in a single system which significantly extends the scope of possible overheads that can be measured and examined, ranging from HW-counters, such as the number of cache misses or floating point operations, to more complex performance metrics, such as control or loss of parallelism. Moreover, SCALEA uses a new representation of code regions, called the dynamic code region call graph, which enables detailed overhead analysis for arbitrary code regions. An instrumentation description file is used to relate performance information to code regions of the input program and to reduce instrumentation overhead. Several experiments with realistic codes that cover MPI, OpenMP, HPF, and mixed OpenMP/MPI codes demonstrate the usefulness of SCALEA.

Abstract Several large real‐world applications have been developed for distributed and parallel architectures. We examine two different program development approaches. First, the usage of a high‐level programming paradigm which reduces the time to create a parallel program dramatically but sometimes at the cost of a reduced performance; a source‐to‐source compiler, has been employed to automatically compile programs—written in a high‐level programming paradigm—into message passing codes. Second, a manual program development by using a low‐level programming paradigm—such as message passing—enables the programmer to fully exploit a given architecture at the cost of a time‐consuming and error‐prone effort. Performance tools play a central role in supporting the performance‐oriented development of applications for distributed and parallel architectures. SCALA—a portable instrumentation, measurement, and post‐execution performance analysis system for distributed and parallel programs—has been used to analyze and to guide the application development, by selectively instrumenting and measuring the code versions, by comparing performance information of several program executions, by computing a variety of important performance metrics, by detecting performance bottlenecks, and by relating performance information back to the input program. We show several experiments of SCALA when applied to real‐world applications. These experiments are conducted for a NEC Cenju‐4 distributed‐memory machine and a cluster of heterogeneous workstations and networks. Copyright © 2001 John Wiley & Sons, Ltd.

Most Java-based systems that support portable parallel and distributed computing either require the programmer to deal with intricate low-level details of Java which can be a tedious, time-consuming and error-prone task, or prevent the programmer from controlling locality of data. In this paper we describe JavaSymphony, a programming paradigm for distributed and parallel computing that provides a software infrastructure for wide classes of heterogeneous systems ranging from small-scale cluster computing to large scale wide-area meta-computing. The software infrastructure is written entirely in Java and runs on any standard compliant Java virtual machine. In contrast to most existing systems, JavaSymphony provides the programmer with the flexibility to control data locality and load balancing by explicit mapping of objects to computing nodes. Virtual architectures are specified to impose a virtual hierarchy on a distributed system of physical computing nodes. Objects can be mapped and dynamically migrated to arbitrary components of virtual architectures. A high-level API to hardware/software system parameters is provided to control mapping, migration, and load balancing of objects. Objects can interact through synchronous asynchronous and one-sided method invocation. Selective remote class loading may reduce the overall memory requirement of an application. Moreover; objects can be made persistent by explicitly storing and loading objects to/from external storage. A prototype of the JavaSymphony software infrastructure has been implemented. Preliminary experiments on a heterogeneous cluster of workstations are described that demonstrate reasonable performance values.

Performance analysis is an important step in tuning performance critical applications. It is a cyclic process of measuring and analyzing performance data which is driven by the programmers hypotheses on potential performance problems. Currently this process is controlled manually by the programmer. The implicit knowledge applied in this cyclic process must be formalized in order to be reused in the automation of performance analysis tools. This article describes the performance property specification language ASL developed in the APART Esprit IV working group. ASL allows the specification of performance data via an object model and of performance properties via a specially designed notation. Performance bottlenecks can then be identified based on the specification since bottlenecks are viewed as performance properties with a huge negative impact. We present the ASL language in the context of MPI applications.

In this paper, we report on experiences with P/sup 3/T+, a performance estimator for distributed and parallel programs which is used to examine at compile time the performance outcome of changes in code, problem and machine sizes, and target architectures. P/sup 3/T+ computes a variety of performance parameters including work distribution, number of transfers, amount of data transferred, transfer times, computation times, and number of cache misses. It is unique in that it models programs, code transformations and parallel and distributed architectures and derives a performance prediction based on all three of these elements. P/sup 3/T+ is the successor tool of P/sup 3/T which computed a similar set of performance parameters, however for parallel programs only. P/sup 3/T+ has been re-designed and re-implemented from scratch and goes beyond P/sup 3/T by extending the class of programs that cart be handled and by employing several novel estimation methods (symbolic analysis, simulation, pre-measured kernel codes, etc.). The core part of this paper reports on the evaluation of P/sup 3/T+ to demonstrate both accuracy and usefulness of this tool for realistic kernel codes taken from real-world applications (pricing of financial derivatives and quantum mechanical calculations of solids).

It is well accepted that pointers are a common source of memory anomalies such as loosing references to dynamic records without deallocating them (also known as memory leaks). This paper presents a novel pointer analysis framework that detects memory leaks by statically analyzing the behavior of programs.

The quality of many optimizations and analyses of parallelizing compilers depends significantly on the ability to evaluate symbolic expressions and on the amount of information available about program variables at arbitrary program points. In this paper, we describe an effective and unified symbolic evaluation framework that statically determines the values of variables and symbolic expressions, assumptions about and constraints between variable values, and the condition under which control flow reaches a program statement. We introduce the program context, a novel representation for comprehensive and compact control and data flow analysis information. Program contexts are described as first order logic formulas, which allows us to use public domain software for standard symbolic manipulation. Computations are represented as algebraic expressions defined over a program's problem size. Our symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays, and procedures. All of our techniques target both linear, as well as nonlinear, expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. A variety of examples, including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication, are used to illustrate the effectiveness of our approach. We present results from a preliminary implementation of our framework, which is used as part of a parallelizing compiler that demonstrates the potential performance gains achievable by employing symbolic evaluation to support program parallelization.

A major difficulty in restructuring compilation, and in parallel programming in general, is how to compare parallel performance over a range of system and problem sizes. Execution time varies with system and problem size and an initially fast implementation may become slow when system and problem size scale up. This paper introduces the concept of range comparison. Unlike conventional execution time comparison in which performance is compared for a particular system and problem size, range comparison compares the performance of programs over a range of ensemble and problem sizes via scalability and performance crossing point analysis. A novel algorithm is developed to predict the crossing point automatically. The correctness of the algorithm is proven and a methodology is developed to integrate range comparison into restructuring compilations for data-parallel programming. A preliminary prototype of the methodology is implemented and tested under Vienna Fortran Compilation System. Experimental results demonstrate that range comparison is feasible and effective. It is an important asset for program evaluation, restructuring compilation, and parallel programming.

A major difficulty in restructuring compilation is how to compare parallel performance over a range of system and problem sizes. This study introduces the concept of range comparison for data-parallel programming. Unlike conventional execution time comparison in which performance is compared for a particular system and problem size, range comparison compares the performance of programs over a range of ensemble and problem sizes via scalability and performance crossing point analysis. An algorithm is developed to predict the crossing point automatically. The correctness of the algorithm is proved and a methodology is developed to integrate range comparison into restructuring compilations. A preliminary prototype of the methodology is implemented and tested under Vienna Fortran Compilation System. Experimental results demonstrate that range comparison is feasible and effective.

In this paper we describe efficient symbolic evaluation techniques to compute the values of variables and symbolic expressions, and to determine the condition under which control flow reaches a program statement at compile time. Computations are represented as algebraic expressions over the input data which maintains the crucial relationship between input data and the resulting analysis information. Our symbolic evaluation techniques comprise accurate modeling of assignment and conditional statements, loops, recurrences, arrays (including indirect accesses) and procedures. Efficiency and accuracy is highly improved by aggressive usage of simplification techniques. Examples including program verification, dependence analysis, array privatization, communication vectorization, and elimination of redundant communication are used to illustrate how our symbolic evaluation techniques support program optimization in the context of a distributed memory parallelizing compiler. 1 Introduction I...

In order to improve a parallel program's performance it is critical to evaluate how even the work contained in a program is distributed over all processors dedicated to the computation. Traditional work distribution analysis is commonly performed at the machine level. The disadvantage of this method is that it cannot identify whether the processors are performing useful or redundant (replicated) work. The paper describes a novel method of statically estimating the useful work distribution of distributed-memory parallel programs at the program level, which carefully distinguishes between useful and redundant work. The amount of work contained in a parallel program, which correlates with the number of loop iterations to be executed by each processor, is estimated by accurately modeling loop iteration spaces, array access patterns and data distributions. A cost function defines the useful work distribution of loops, procedures and the entire program. Lower and upper bounds of the described parameter are presented. The computational complexity of the cost function is independent of the program's problem size, statement execution and loop iteration counts. As a consequence, estimating the work distribution based on the described method is considerably faster than simulating or actually compiling and executing the program. Automatically estimating the useful work distribution is fully implemented as part of P3T, which is a static parameter based performance prediction tool under the Vienna Fortran Compilation System (VFCS). The Lawrence Livermore Loops are used as a test case to verify the approach.

Threads provide a useful programming model for asynchronous behavior because of their ability to encapsulate units of work that can then be scheduled for execution at runtime, based on the dynamic state of a system.Recently, the threaded model has been applied to the domain of data parallel scientific codes, and initial reports indicate that the threaded model can produce performance gains over non-threaded approaches, primarily through the use of overlapping useful computation with communicant ion latency.However, overlapping computation with communication is possible without the benefit of threads if the communication system supports asynchronous primitives, and this comparison has not been made in previous papers.This paper provides a critical look at the utility of lightweight threads as applied to data parallel scientific programming.

This paper presents a Parameter based Performance Prediction Tool (PPPT) which is part of the Vienna Fortran Compilation System (VFCS), a compiler that automatically translates Fortran programs into message passing programs for massively parallel architectures.

In order to take on the challenge of fully automatic program parallelizing, one of the last and probably the most decisive missing tool is a performance estimation system. In this paper a new performance prediction tool is introduced, which automatically derives performance estimates for single program multiple data (SPMD) parallel Fortran 77 programs based on distributed memory systems (DMS). The underlying methodology is based on static and dynamic techniques. This paper discusses in particular a high level abstract description of the parallel program, which is utilized to derive performance estimates. The salient features of the overall design of this tool and its components are described.