This paper introduces Schedgehammer, a general-purpose auto-scheduling framework that optimizes program execution across diverse compiler infrastructures. Unlike existing auto-schedulers that are tightly coupled to specific intermediate representations or rely on template-based search, Schedgehammer provides a generic, reusable framework for optimization schedules by modeling them as graph-structured objects. This approach captures dependencies among transformations and parameters across compilers, enabling systematic mutation and validation.

We introduce pyATF -- a new, language-independent, open-source auto-tuning tool that fully automatically determines optimized values of performance-critical program parameters. A major feature of pyATF is its support for constrained parameters, e.g., the value of one parameter has to divide the value of another parameter. A further major feature of pyATF is its user interface which is designed with a particular focus on expressivity and usability for real-world demands, and which is offered in the increasingly popular Python programming language. We experimentally confirm the practicality of pyATF using real-world studies from the areas of quantum chemistry, image processing, data mining, and deep learning: we show that pyATF auto-tunes the complex parallel implementations of our studies to higher performance than achieved by state-of-practice approaches, including hand-optimized vendor libraries.

We develop a novel autoscaling service (autoscaler) to provide elasticity for Real-Time Online Interactive Applications (ROIA) running on clouds for thousands of concurrent users. High-performance ROIA include real-time 3D product configurators, multiplayer online gaming, digital twins for the industry 4.0 market, and e-learning. Using our autos caler for ROIA on clouds facilitates meeting high demands on Quality of Experience (QoE) and the economic utilization of cloud resources. Compared to existing autoscaling solutions (e.g., in Kubernetes), our autoscaler is based not on the classical metrics (CPU/GPU load, memory usage, etc.), but rather on the session slots which limit the number of concurrent sessions for a service instance. We design a novel auto scaling algorithm using linear regression of the session slots usage, and we mathematically analyze and experimentally evaluate autoscaler's dynamic reaction to changing workload while avoiding overswinging (creating more service instances than needed). We also report our preliminary experimental results.

Graphics Processing Units (GPU) offer tremendous computational power by following a throughput oriented paradigm where many thousand computational units operate in parallel. Programming such massively parallel hardware is challenging. Programmers must correctly and efficiently coordinate thousands of threads and their accesses to various shared memory spaces. Existing mainstream GPU programming languages, such as CUDA and OpenCL, are based on C/C++ inheriting their fundamentally unsafe ways to access memory via raw pointers. This facilitates easy to make, but hard to detect bugs, such as data races and deadlocks . In this paper, we present Descend : a safe GPU programming language. In contrast to prior safe high-level GPU programming approaches, Descend is an imperative GPU systems programming language in the spirit of Rust, enforcing safe CPU and GPU memory management in the type system by tracking Ownership and Lifetimes . Descend introduces a new holistic GPU programming model where computations are hierarchically scheduled over the GPU’s execution resources : grid, blocks, warps, and threads. Descend’s extended Borrow checking ensures that execution resources safely access memory regions without data races. For this, we introduced views describing safe parallel access patterns of memory regions, as well as atomic variables. For memory accesses that can’t be checked by our type system, users can annotate limited code sections as unsafe . We discuss the memory safety guarantees offered by Descend and evaluate our implementation using multiple benchmarks, demonstrating that Descend is capable of expressing real-world GPU programs showing competitive performance compared to manually written CUDA programs lacking Descend’s safety guarantees.

We introduce a new scheduling language, based on the formalism of Multi-Dimensional Homomorphisms (MDH). In contrast to existing scheduling languages, our MDH-based language is designed to systematically "de-compose" computations for the memory and core hierarchies of architectures, and "re-compose" the computed intermediate results back to the final result -- we say "(de/re)-composition" for short. We argue that our scheduling langauge is easy to use and yet expressive enough to express well-performing (de/re)-compositions of popular related approaches, e.g., the TVM compiler, for MDH-supported computations (such as linear algebra routines and stencil computations). Moreover, our language is designed as auto-tunable, i.e., any optimization decision can optionally be left to the auto-tuning engine of our system, and our system can automatically recommend schedules for the user, based on its auto-tuning capabilities. Also, by relying on the MDH approach, we can formally guarantee the correctness of optimizations expressed in our language, thereby further enhancing user experience. Our experiments on GPU and CPU confirm that we can express optimizations that cannot be expressed straightforwardly (or at all) in TVM's scheduling language, thereby achieving higher performance than TVM, and also vendor libraries provided by NVIDIA and Intel, for time-intensive computations used in real-world deep learning neural networks.

Real-Time Online Interactive Applications (ROIA) include use cases like product configurators, e-learning, multiplayer online gaming, and Industry 4.0 market. While core components of ROIA, e.g., interactive real-time 3D rendering, still widely run on local devices, it is very desirable to run them on a multi-cloud to benefit from better access to high-performance compute resources and prevent 'vendor lock-in‘. One challenge when running applications on a multi-cloud is to establish an efficient and secure communication between the cloud nodes that are distributed over several geographic locations and local area networks (LANs). In this paper, we propose and implement a novel OpenVPN-based node interconnection in multi-clouds. Compared to previous work, our solution is not vendor-specific and can handle multi-clouds consisting of both Windows and Linux nodes. Furthermore, it works for an arbitrary combination of private and public cloud deployments. Additionally, we implement two Python scripts to automate the process of dynamically adding new cloud deployments in an efficient manner. We describe our proof-of-concept implementation in a Kubernetes-based service deployment architecture for ROIA and report the preliminary experimental results.

We develop a novel multi-cloud container orchestration architecture for high-performance Real-Time Online Interactive Applications (ROIA), with use cases including product configurators, multiplayer online gaming, e-learning and - training. Running the core components of ROIA, e.g., real-time 3D rendering, on a multi-cloud enables access to high-performance resources and prevents proprietary ‘vendor lock-in’. Our container orchestration facilitates: (1) strict Quality of Service (QoS) requirements, (2) secure communication between cluster nodes from different clouds, (3) automatic scalability, and (4) resource usage optimization. We improve previous work by using session slots that set a limit on the number of concurrent user sessions for a service instance without loss of QoS. Our implementation provides a vendor-independent, OpenVPN-based interconnection between cloud nodes, both Linux and Windows, possibly located in different LANs of a multi-cloud. We experimentally evaluate our orchestration approach on a Kubernetes-based cluster using a prototype of an interactive car configurator.

A challenging aspect in developing and deploying distributed systems with strict real-time constraints is how to evaluate the performance of the system running in a production environment without disrupting its regular operation. The challenge is even greater when the System Under Evaluation (SUE) is a poorly documented legacy system with database-centric architecture that works within a resource-sharing environment. Current performance evaluation methods dealing with this challenge require live monitoring software or distributed tracing software tools that are typically unavailable in legacy systems and hard to establish. In this paper, we propose an alternative approach RAST (Regression Analysis, Simulation, and load Testing); it evaluates the response time as the major performance characteristic of a distributed real-time legacy system using the available system's log files. Our use case is a commercial alarm system in productive use that is provided and further developed by the GS company group in Germany. We show in extensive experiments that our approach allows to adequately estimate to what degree the workload of a legacy production system can rise in the future while complying with the strict requirements on the response time. We provide a GitHub repository with non-proprietary parts of our predictive model generation, simulation, and load testing software to reproduce our experiments.

Crowd simulations are widely used to study and predict the human behavior in disaster scenarios. In this paper, we introduce real-time user interactivity into the simulation process of virtual environments (e.g., buildings with rooms and doors between them). We develop a new tactical path-planning model that translates the interactive virtual environment into an abstract graph in order to calculate the shortest paths in real time. Our extension of the Vadere simulation framework with interactivity features allows the users to better understand the actual problem situations and to analyze them. Our experiments demonstrate the effectiveness of the approach by simulating the evacuation of students in groups and as individuals from the Schloss Muenster (the administrative building of the University of Muenster) in Germany. During simulation run time, the user can interact with the virtual environment spontaneously (e.g., by opening and closing doors) while our model recalculates the shortest paths for agents in real time.

Auto-tuning is a popular approach to program optimization: it automatically finds good configurations of a program’s so-called tuning parameters whose values are crucial for achieving high performance for a particular parallel architecture and characteristics of input/output data. We present three new contributions of the Auto-Tuning Framework (ATF), which enable a key advantage in general-purpose auto-tuning : efficiently optimizing programs whose tuning parameters have interdependencies among them. We make the following contributions to the three main phases of general-purpose auto-tuning: (1) ATF generates the search space of interdependent tuning parameters with high performance by efficiently exploiting parameter constraints; (2) ATF stores such search spaces efficiently in memory, based on a novel chain-of-trees search space structure; (3) ATF explores these search spaces faster, by employing a multi-dimensional search strategy on its chain-of-trees search space representation. Our experiments demonstrate that, compared to the state-of-the-art, general-purpose auto-tuning frameworks, ATF substantially improves generating, storing, and exploring the search space of interdependent tuning parameters, thereby enabling an efficient overall auto-tuning process for important applications from popular domains, including stencil computations, linear algebra routines, quantum chemistry computations, and data mining algorithms.

Mobile Event-Based Social Network (EBSN) platforms, such as Meetup and Plancast, have become increasingly popular for online organization of offline (in-person) events. The problem of the existing techniques in ESBN is that they do not reflect the bilateral (two-way) nature of efficient event planning: 1) events enroll more influential participants, and 2) participants are arranged to events they are most interested in. In this paper, we address this weakness by formally defining the bilateral recommendation problem and making two contributions to solving this problem: (a) by analyzing all types of the user’s behaviors during the selection session, we can accurately predict which event the users will eventually choose to participate in, and (b) by introducing the concepts of interpersonal similarity and interaction strength in EBSNs, we can calculate the interactive influence of users. We report the results of extensive experiments on real datasets that confirm the improved precision, effectiveness and scalability of our proposed bilateral recommendation strategy as compared to the state of the art.

Optimizing programs to run efficiently on modern parallel hardware is hard but crucial for many applications. The predominantly used imperative languages - like C or OpenCL - force the programmer to intertwine the code describing functionality and optimizations. This results in a portability nightmare that is particularly problematic given the accelerating trend towards specialized hardware devices to further increase efficiency. Many emerging DSLs used in performance demanding domains such as deep learning or high-performance image processing attempt to simplify or even fully automate the optimization process. Using a high-level - often functional - language, programmers focus on describing functionality in a declarative way. In some systems such as Halide or TVM, a separate schedule specifies how the program should be optimized. Unfortunately, these schedules are not written in well-defined programming languages. Instead, they are implemented as a set of ad-hoc predefined APIs that the compiler writers have exposed. In this functional pearl, we show how to employ functional programming techniques to solve this challenge with elegance. We present two functional languages that work together - each addressing a separate concern. RISE is a functional language for expressing computations using well known functional data-parallel patterns. ELEVATE is a functional language for describing optimization strategies. A high-level RISE program is transformed into a low-level form using optimization strategies written in ELEVATE . From the rewritten low-level program high-performance parallel code is automatically generated. In contrast to existing high-performance domain-specific systems with scheduling APIs, in our approach programmers are not restricted to a set of built-in operations and optimizations but freely define their own computational patterns in RISE and optimization strategies in ELEVATE in a composable and reusable way. We show how our holistic functional approach achieves competitive performance with the state-of-the-art imperative systems Halide and TVM.

Stencil computations are a widely used type of algorithm, found in applications from physical simulations to machine learning. Stencils are embarrassingly parallel, therefore fit on modern hardware such as Graphic Processing Units perfectly. Although stencil computations have been extensively studied, optimizing them for increasingly diverse hardware remains challenging. Domain-specific Languages (DSLs) have raised the programming abstraction and offer good performance; however, this method places the burden on DSL implementers to write almost full-fledged parallelizing compilers and optimizers. Lift has recently emerged as a promising approach to achieve performance portability by using a small set of reusable parallel primitives that DSL or library writers utilize. L ift ’s key novelty is in its encoding of optimizations as a system of extensible rewrite rules which are used to explore the optimization space. This article demonstrates how complex multi-dimensional stencil code and optimizations are expressed using compositions of simple 1D L ift primitives and rewrite rules. We introduce two optimizations that provide high performance for stencils in particular: classical overlapped tiling for multi-dimensional stencils and 2.5D tiling specifically for 3D stencils. We provide an in-depth analysis on how the tiling optimizations affects stencils of different shapes and sizes across different applications. Our experimental results show that our approach outperforms existing compiler approaches and hand-tuned codes.

We address a key challenge in programming high-performance applications - achieving portable performance, i.e., the same source code achieves a consistent, high level of performance over the variety of modern parallel processors, including multi-core CPU and many-core Graphics Processing Unit (GPU), and over the variety of input sizes. Our approach relies on the algebraic formalism of Multi-Dimensional Homomorphisms (MDH), which enables expressing data-parallel computations uniformly via a higher-order function (a.k.a. parallel pattern). For MDHs, we develop a novel code generation approach based on a generic OpenCL implementation. Our implementation efficiently exploits the OpenCL's abstract platform and memory model, generically for arbitrary MDH functions, by incorporating a parameterized parallelization and tiling strategy - on both layers of the OpenCL's two models and in all dimensions of the multi-dimensional input. We achieve performance portability for MDHs by auto-tuning the parameters of our two strategies, thereby enabling fully automatically optimizing our code for any combination of an MDH function, target device, and input size. We demonstrate for computations from four popular domains - dense linear algebra (BLAS), stencil computations, data mining, and tensor contractions - how we express them in the MDH formalism, and we experimentally show that our automatically generated and auto-tuned code for them achieves competitive and often significantly better performance than several state-of-practice approaches on both Intel multi-core CPU and NVIDIA many-core GPU - speedups of up to 5x over the state-of-the-art performance-portable approaches, and competitive or even better performance as compared to hand-optimized approaches such as Intel MKL and NVIDIA cuBLAS on real-world input data as used in deep learning.

Simulating large crowds of individuals is socially important, e.g., for developing and studying evacuation or rescuing in dangerous situations. Such simulations remain complex due to the scalability challenge: simulating thousands of virtual characters is computationally expensive, especially when taking into account psychological factors and group-specific behavior that play a crucial role, e.g., in panic situations and highly crowded environments. In this paper, we make two new contributions: 1) we extend the HiDAC agent-based modeling approach with the aspects of group formation and movement, and 2) we implement our approach within the CrowdSim system, including the possibility to distribute the simulation process across several compute servers for better performance. We report experimental results on scaling the distributed simulation of a real-world evacuation scenario in a building using several compute servers.

When vectorizing programs for modern processors with SIMD extensions, IF-statements pose a challenge: existing vectorization approaches often introduce redundant computations or they resort to inefficient masked instructions.

Summary We describe the Auto‐Tuning Framework (ATF) — a simple‐to‐use, generic approach and its implementation, as a framework for automatic program optimization by choosing the most suitable values of program parameters such as the number of parallel threads, tile sizes, etc. ATF combines four major advantages over the state‐of‐the‐art auto‐tuning: i) it is generic regarding the programming language, application domain, tuning objective (eg, high performance and/or low energy consumption), and search technique; ii) it can auto‐tune a broader class of applications by allowing tuning parameters to be interdependent, eg, when one parameter is divisible by another parameter; iii) it allows tuning parameters to have substantially larger ranges by implementing an optimized search space generation process; and iv) it is arguably simpler to use, eg, the ATF user prepares an application for auto‐tuning by annotating its source code with simple tuning directives. We demonstrate ATF's efficacy by comparing it to the state‐of‐the‐art auto‐tuning approaches, OpenTuner and CLTune; ATF shows better tuning results with less programmer's effort.

Stencil computations are widely used from physical simulations to machine-learning. They are embarrassingly parallel and perfectly fit modern hardware such as Graphic Processing Units. Although stencil computations have been extensively studied, optimizing them for increasingly diverse hardware remains challenging. Domain Specific Languages (DSLs) have raised the programming abstraction and offer good performance. However, this places the burden on DSL implementers who have to write almost full-fledged parallelizing compilers and optimizers.

The state-of-the-art parallel programming approaches OpenCL and CUDA require so-called host code for pro-gram's execution. Implementing host code is often a cumbersome task, especially when executing OpenCL and CUDA programs on systems with multiple devices, e.g., multi-core CPU and Graphics Processing Units (GPUs): the programmer is responsible for explicitly managing system's main memory and devices' memories, synchronizing computations with data transfers between main and/or devices' memories, and optimizing data transfers, e.g., by using pinned main memory for accelerating data transfers and overlapping the transfers with comnutations. In this paper, we present OCAL (DpenCL/CUDA Abstraction Layer) - a high-level approach to simplify the development of host code. OCAL combines five major advantages over the state-of-the-art high-level approaches: 1) it simplifies implementing both OpenCL and CUDA host code by providing a simple-to-use, uniform high-level host code abstraction API; 2) it supports executing arbitrary OpenCL and CUDA programs; 3) it simplifies implementing data-transfer optimizations by providing specially-optimized memory buffers, e.g., for conveniently using pinned main memory; 4) it optimizes memory management by automatically avoiding unnecessary data transfers; 5) it enables interoperability between OpenCL and CUDA host code by automatically managing the communication between OpenCL and CUDA data structures and by automatically translating between the OpenCL. and CUDA programming constructs. Our experiments demonstrate that OCAL significantly simplifies implementing host code with a low runtime overhead for abstraction.

Verifying the reliability of software systems formally is difficult due to the complexity of system correctness requirements. Specification patterns allow us to describe typical requirements in a natural language, while their formal semantics enable expressing these requirements in the input language of some verification tool. In this paper, we propose an ontology of specification patterns that combines patterns from existing requirement classifications with new patterns. Our ontology can be used to express combinations of requirements of the following types: qualitative, real and branching time, with combined events, quantitative characteristics of events, and simple statements about data. The advantage of our approach is the ability to formally verify the compatibility of multiple requirements. As an illustrating use case, we describe the requirements for the real-world vacuum control system of the Large Solar Vacuum Telescope.

Real-Time Online Interactive Applications, e.g., multiplayer online games, connect a high number of users who interact with the application and with each other in real time, i.e., a response to a user's input should happen virtually immediately. We address the problem of reproducing the communication behavior of such applications in order to study the effect of various design decisions (application logic, underlying infrastructure, network protocols, etc.) at early stages of application development. We develop a flexible, lightweight simulator as an alternative to the state-of-the-art simulation approaches that rely on the recorded communication traffic of real applications. The advantage of our approach is that we can easily adapt to a particular application design and its underlying infrastructure and we can measure various communication metrics, without relying on existing application prototypes and real users. Our experiments demonstrate that the simulator realistically reproduces communication behavior for high numbers of users and that simulation results are very near to the communication patterns of recorded communication traffic, e.g., for the commercially successful multiplayer game Counter Strike.

BACKGROUND: Multi-label classification has recently gained great attention in diverse fields of research, e.g., in biomedical application such as protein function prediction or drug resistance testing in HIV. In this context, the concept of Classifier Chains has been shown to improve prediction accuracy, especially when applied as Ensemble Classifier Chains. However, these techniques lack computational efficiency when applied on large amounts of data, e.g., derived from next-generation sequencing experiments. By adapting algorithms for the use of graphics processing units, computational efficiency can be greatly improved due to parallelization of computations. RESULTS: Here, we provide a parallelized and optimized graphics processing unit implementation (eccCL) of Classifier Chains and Ensemble Classifier Chains. Additionally to the OpenCL implementation, we provide an R-Package with an easy to use R-interface for parallelized graphics processing unit usage. CONCLUSION: eccCL is a handy implementation of Classifier Chains on GPUs, which is able to process up to over 25,000 instances per second, and thus can be used efficiently in high-throughput experiments. The software is available at http://www.heiderlab.de .

In the Semantic Web, the Resource Description Framework (RDF) has become the standard representation to describe Internet resources. RDF data is structured in triples comprising a subject, a predicate and an object: the predicate defines the relation between subject and object. The RDF Schema (RDFS) extends raw RDF data with a standardized vocabulary to allow for entailment, e.g., type inheritance or type inference. Processing large RDF data sets, which are commonly stored as text files, is a time-intensive task: querying and entailment on RDF data requires a huge amount of computational power and storage. We propose TripleID – a framework for RDF querying and entailment processing. TripleID provides a novel, compressed file format for RDF data and utilizes Graphics Processing Units (GPUs) for accelerated, highly parallelized data processing. We demonstrate the advantages of our framework on real-world RDF data: TripleID reduces storage size for RDF data by up to 75% and accelerates querying and entailment processing up to 40 times as compared to the state-of-the-art tools that use conventional CPUs.

SUMMARY: Next-generation sequencing (NGS) has a large potential in HIV diagnostics, and genotypic prediction models have been developed and successfully tested in the recent years. However, albeit being highly accurate, these computational models lack computational efficiency to reach their full potential. In this study, we demonstrate the use of graphics processing units (GPUs) in combination with a computational prediction model for HIV tropism. Our new model named gCUP, parallelized and optimized for GPU, is highly accurate and can classify >175 000 sequences per second on an NVIDIA GeForce GTX 460. The computational efficiency of our new model is the next step to enable NGS technologies to reach clinical significance in HIV diagnostics. Moreover, our approach is not limited to HIV tropism prediction, but can also be easily adapted to other settings, e.g. drug resistance prediction. AVAILABILITY AND IMPLEMENTATION: The source code can be downloaded at http://www.heiderlab.de CONTACT: [email protected].

We consider a challenging class of highly interactive virtual environments, also known as Real-Time Online Interactive Applications (ROIA). Popular examples of ROIA include multi-player online computer games, e-learning and training based on real-time simulations, and other challenging applications. ROIA combine high demands on scalability and real-time user interactivity with the problem of an efficient and economic utilization of resources, which is difficult to achieve due to the changing number of users. This paper proposes a generic scalability model for ROIA that analyzes the application performance during runtime and predicts the demand for load balancing, i.e., when to add/remove resources or redistribute workload. We prove the practical relevance of the model by incorporating it into our RTF-RMS resource management system where it is used to predict the influence of different load-balancing actions on the application scalability. Our model is utilized by RTF-RMS for finding efficient load-balancing actions and thresholds for how often these actions should be applied. We report experimental results on the load balancing of a multi-player online game using predictions from the scalability model.

Real-time Online Interactive Applications (ROIA) like multiplayer online games usually work in a persistent environment (also called virtual world) which continues to exist and evolve also while the user is offline and away from the application. This paper deals with storing persistent data of real-time interactive applications in modern relational databases. We describe a preliminary design of the Entity Persistence Module (EPM) middleware which liberates the application developer from writing and maintaining complex and error-prone, application-specific code for persistent data management.

Application programming for modern heterogeneous systems which comprise multiple accelerators (multi-core CPUs and GPUs) is complex and error-prone. Popular approaches, like OpenCL and CUDA, are low-level and offer no support for the two most complicated issues: 1) programming multiple GPUs within a stand-alone computer, and 2) managing distributed systems that integrate several such computers. In particular, distributed systems require application developers to use a mix of different programming models, e.g., MPI together with OpenCL or CUDA. We propose a uniform approach based on OpenCL for programming both stand-alone and distributed systems with GPUs. The approach implementation is based on two parts: 1) the SkelCL library for high-level application programming on heterogeneous stand-alone computers with multi-core CPUs and multiple GPUs, and 2) the dOpenCL middleware for transparent execution of OpenCL programs on several stand-alone computers connected over a network.

This paper describes how the performance potential of multi-core processors can be used to accelerate multi-user online games and other interactive applications. We developed DependenTS (Dependent Task Scheduler) - a task scheduling C++ library for multi-core systems. DependenTS is used within our Real-Time Framework (RTF) in order to overlap the application computations with communication-related actions. By executing the overlapped actions on multiple cores, we improve the application performance, in particular we increase the maximal number of players which can access a game simultaneously.

We consider a challenging class of emerging, highly interactive virtual environments which we call Real-Time Online Interactive Applications (ROIA). Popular examples include multi-player online computer games, e-learning and training applications based on real-time simulations, etc. ROIA combine tough demands on the level of scalability and highly intensive user interactivity with real-time QoS requirements on distributed performance. A major problem in this context is the efficient and economic utilization of server resources for distributed service provision, which is very difficult to achieve due to the variable numbers of users. In this paper, we propose a novel combination of two platforms that address this challenge by utilizing Cloud Computing for ROIA provision: we extend the Real-Time Framework (RTF) by the novel Cloud resource management system RTF-RMS. RTF is a high-level development platform that provides suitable management and scalability mechanisms for ROIA. RTF-RMS is a resource management system on top of RTF that implements workload analysis and distribution techniques. We illustrate how RTF-RMS interacts with RTF and describe how both platforms are used together to scale application servers up and down during runtime to conform to a changing number of users.

Abstract Multi‐core processors offer a huge potential of parallelism but pose a challenge of program development for achieving high performance in real applications. We compare three popular parallel programming models—POSIX threads (Pthreads), OpenMP, and Threading Building Blocks (TBB)—regarding their use for multi‐core systems. We analyze how these models can be employed for implementing various parallelizations of a real‐world application from the area of medical imaging, and we conduct extensive runtime experiments to measure performance. Our main contribution is a comprehensive comparison of Pthreads, OpenMP, and TBB with respect to the following criteria: program development effort, programming style, level of abstraction, and runtime performance on multi‐cores. Copyright © 2010 John Wiley & Sons, Ltd.

Large-scale Massively Multiplayer Online Games (MMOGs) and other networked applications pose challenging performance requirements such as low response times (down to 100 ms for action games like First-Person Shooters) and high update rates (up to 50 Hz). They require multi-server architectures in order to scale to higher player numbers (up to 105 in a single application session). During the application development process, it is necessary to study performance properties such as response time to user actions or CPU consumption in order to optimize the application. To analyse performance properties, the application developer needs to (i) model these properties, (ii) collect information about the variables of interest, and (iii) process the collected information to study the results. In this paper, we propose a novel tool set (Netlag) that supports the collection and processing of variables of interest in the context of MMOGs. The tool set consists of a C++ library that allows to collect and store information in a generic way, as well as a Java application that visualises the collected information. As a case study, we conduct how Netlag is used to evaluate the performance and scalability of an example MMOG application. Furthermore, we describe measurements of the overhead introduced by Netlag which demonstrate that its application intrusion is minimal, thus proving its good applicability for MMOGs and other networked applications.

This paper deals with networked applications in the emerging field of online virtual worlds. Example applications include, e.g., Massively Multiplayer Online Computer Games (MMOG), networked e-learning, training and simulations, etc. Highly interactive virtual worlds bring a new security challenge: the multiple participants of such applications do not always show cooperative and intended behavior, but rather may act in an illegal way (cheating) which is harmful for other participants, thus intentionally or accidentally procuring illicit advantages for themselves. The paper studies the new challenge of cheating in virtual-world applications in three areas: a) system and application programming, b) economics, and c) law. The main contributions of our work are as follows: 1) We present a systematic classification of cheating threats in virtual worlds, and describe software solutions that help prevent them in future Internet-based applications; 2) We enhance the classical economic analysis of crime and punishment for applying it to virtual worlds; 3) We describe our development approach for networked virtual worlds and its implementation as the Real-Time Framework (RTF) which has been designed at the University of Muenster; 4) Finally, we explore the law aspects of cheating in virtual applications in the context of the legal system in Germany. The consideration of informatics aspects together with the corresponding problems of economics and law allows us to tackle virtual-world security in a holistic, systematic manner.

We propose a novel cyberinfrastructure for an emerging class of Internet-based real-time online interactive applications (ROIA). The most challenging representative of this application class are massively multi-player online games. We present the results of the European project Edutain@Grid on the development of efficient cyberinfrastructure and scalable applications. We report experimental results demonstrating the performance and scalability of our approach.

Reactive systems work in an online manner, accepting inputs from the environment or from the user and producing outputs which are then consumed by the environment. Important examples of reactive applications include online computer games, operating systems, simulation environments, etc. Software development for reactive systems is a challenge, because the usual verification and testing techniques are hardly applicable for them. We describe a novel development approach based on using the formal mechanism of State Transition Rules (STR) for specifying a reactive system. Our main contribution is the transformation method for refining system's STR into a Lyee program specification, which allows the developer to generate a provably correct target program. We illustrate our approach using an example of the interactive Othello game.

Real-Time Online Interactive Applications (ROIA) are an increasingly important class of applications including multiplayer online computer games and simulation-based e-learning. They are usually expected to support high user numbers and thus require mechanisms to accommodate increasing load by using additional resources. This paper presents first results of the research and development project edutain@grid, including a comprehensive analysis of the application class and the new challenges regarding software development. We propose a novel, high-level development approach for ROIA which integrates three distribution mechanisms in today's online games – zoning, instancing and replication. As a first implementation of the approach, we describe the RTF (Real-Time Framework) middleware system which liberates the developer from low-level tasks and allows him to stay at high level of design abstraction. We explain how RTF supports the implementation of single and multi-server online games and how RTF incorporates various distribution mechanisms during the development process.

This paper addresses the challenge of developing correct reactive software systems using declarative specifications. We consider the promising Lyee software development system and extend it by means of the STR – State Transition Rules. The use of STR allows verifying the desired properties of reactive systems and thus producing Lyee programs of a higher quality than it is possible without verification. We demonstrate how the STR-based approach works for an illustrative example of the highly interactive Othello game.

Massively Multiplayer Online Games (MMOGs) are an increasingly popular class of real-time interactive distributed applications that require scalable architectures and parallelization approaches. While games of the role-playing genre already allow thousands of users to concurrently participate in a single game session, there are important genres, in particular action and strategy games, which have not been scaled to the massively multiplayer realm so far. These games have hard requirements in terms of scalability, in particular regarding density: many players tend to congregate in small locations. In this paper, we outline our novel approach of replication-based parallelisation for scaling the density of players. The practical impact of our work is demonstrated by porting the popular action game QFusion, based on the famous Quake 2, onto our proxy-server system architecture using the replication approach. The experiments with the ported QFusion demonstrate its high responsiveness and show that our approach allows to almost triple the maximum number of simultaneous players on four servers as compared with a single-server version.

An increasingly popular application programming model for Grids is to deploy often-used functionalities as remote services on high-performance hosts, following the principles of a service-oriented architecture. Complex applications are created by using several services and specifying a workflow between them. We discuss how workflows of Grid applications can be described easily as High-Level Petri Nets (HLPN), in order to orchestrate and execute distributed applications on the Grid automatically. In order to simplify the handling of complex and large-scale workflows, we introduce hierarchical Grid workflows, making use of the Petri Net refinement paradigm that allows to represent sub-workflows by single graph elements. We show how a complex application, the Barnes-Hut algorithm for N-Body simulation can be expressed as a hierarchical HLPN, using our platform-independent, XML-based Grid Workflow Description Language (GWorkflowDL). We discuss how the GWorkflowDL can be adapted to current Grid technologies, in particular to Java/RMI and the recent WSRF framework.

Grid applications are increasingly being developed as workflows built of well-structured, reusable components. We develop a user-transparent scheduling approach for Higher-Order Components (HOCs) . parallel implementations of typical programming patterns, accessible and customizable via Web services. We introduce a set of cost functions for a reusable scheduling: when the workflow recurs, it is mapped to the same execution nodes, avoiding the need for a repeated scheduling phase. We prove the efficiency of our scheduling by implementing it within the KOALA scheduler and comparing it with KOALA's standard Closeto- File policy. Experiments on scheduling HOC-based applications achieve a 40% speedup in communication and a 100% throughput increase.

Clayworks is a software system which integrates collaborative real-time modeling and distributed computing. It addresses the challenge of developing a collaborative workspace with a seamless access to high-performance servers. Clayworks allows modeling of virtual clay objects and running computation-intensive deformation simulations for objects crashing into each other. To integrate heterogeneous computational resources, we adopted modern Grid middleware and provided the users with an intuitive graphical interface. We parallelized the computation of simulations using a Higher-Order Component (HOC) which abstracts over the Globus Web service resource framework (WSRF) used to interconnect our worksuite to the computation server. Clayworks is a representative of a large class of demanding systems which combine collaborative modeling with performance-critical computations, e.g., crash-tests or simulations for biological population evolution.

Current commercial real-time computer games increasingly provide game designs suitable for a high number of players, forming the class of massive multiplayer games (MMG). To support MMG, the scalability of network topologies becomes critically important, i.e., their ability to maintain the game service for an increasing number of players. This paper presents GSM - an analytical scalability model for a detailed investigation of massively multiplayer capabilities of different networking topologies. We use the GSM to discuss the suitability of the client-server and peer-to-peer topology, as well as our own concept of a multi-server topology, for the important classes of first person shooter (FPS) and real-time strategy (RTS) games whose designs are still rarely adopted in MMGs. We verify our analytical model in scalability experiments in which we were able to forecast the maximum numbers of players in a non-congested game session with un error of less than 7 %.

During the software crisis of the 1960s, Dijkstra's famous thesis "goto considered harmful" paved the way for structured programming. This short communication suggests that many current difficulties of parallel programming based on message passing are caused by poorly structured communication, which is a consequence of using low-level send-receive primitives. We argue that, like goto in sequential programs, send-receive should be avoided as far as possible and replaced by collective operations in the setting of message passing. We dispute some widely held opinions about the apparent superiority of pairwise communication over collective communication and present substantial theoretical and empirical evidence to the contrary in the context of MPI (Message Passing Interface).

Metacomputing infrastructures couple multiple clusters (or MPPs) via wide-area networks. A major problem in programming parallel applications for such platforms is their hierarchical network structure: latency and bandwidth of WANs often are orders of magnitude worse than those of local networks. Our goal is to optimize MPI's collective operations for such platforms. In this paper we focus on optimized utilization of the (scarce) wide-area bandwidth. We use two techniques: selecting suitable communication graph shapes, and splitting messages into multiple segments that are sent in parallel over different WAN links. To determine the best graph shape and segment size, we introduce a performance model called parameterized LogP (P-LogP), a hierarchical extension of the LogP model that covers messages of arbitrary length. With P-LogP, the optimal segment size and the best broadcast tree shape can be determined at runtime. (For conciseness, we restrict our discussion to the broadcast operation). An experimental performance evaluation shows that the new broadcast has significantly improved performance (for large messages) and that there is a close match between the theoretical model and the measured completion times.

Presents a systematic approach to the development of message passing programs. Our programming model is SPMD, with communications restricted to collective operations: scan, reduction, gather, etc. The design process in such an architecture-independent language is based on correctness-preserving transformation rules that are provable in a formal functional framework. We develop a set of design rules for composition and decomposition. For example, scan followed by reduction is replaced by a single reduction, and global reduction is decomposed into two faster operations. The impact of the design rules on the target performance is estimated analytically and tested in machine experiments. As a case study, we design two provably correct, efficient programs using the Message Passing Interface (MPI) for the famous maximum segment sum problem, starting from an intuitive, but inefficient, algorithm specification.

List homomorphisms are functions that are parallelizable using the divide-and-conquer paradigm. We study the problem of finding homomorphic representations of functions in the Bird–Meertens constructive theory of lists, by means of term rewriting and theorem proving techniques. A previous work proved that to each pair of leftward and rightward sequential representations of a function, based on cons - and snoc -lists, respectively, there is also a representation as a homomorphism. Our contribution is a mechanizable method to extract the homomorphism representation from a pair of sequential representations. The method is decomposed to a generalization problem and an inductive claim, both solvable by term rewriting techniques. To solve the former we present a sound generalization procedure which yields the required representation, and terminates under reasonable assumptions. The inductive claim is provable automatically. We illustrate the method and the procedure by the systematic parallelization of the scan -function (parallel prefix) and of the maximum segment sum problem.

Abstract An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived by formal refinement (transformation) of the specification schema. The specification is in the form of a mutually recursive functional definition. In a first phase, a parallel functional program schema is constructed which consists of a communication tree and a functional program that is shared by all nodes of the tree. The fact that this phase proceeds by semantics-preserving transformations in the Bird-Meertens formalism of higher-order functions guarantees the correctness of the resulting functional implementation. A second phase yields an imperative distributed message-passing implementation of this schema. The derivation process is illustrated with an example: a two-dimensional numerical integration algorithm.