Temporal graph learning is crucial for dynamic networks where nodes and edges evolve over time and new nodes continuously join the system. Inductive representation learning in such settings faces two major challenges: effectively representing unseen nodes and mitigating noisy or redundant graph information. We propose GTGIB, a versatile framework that integrates Graph Structure Learning (GSL) with Temporal Graph Information Bottleneck (TGIB). We design a novel two-step GSL-based structural enhancer to enrich and optimize node neighborhoods and demonstrate its effectiveness and efficiency through theoretical proofs and experiments. The TGIB refines the optimized graph by extending the information bottleneck principle to temporal graphs, regularizing both edges and features based on our derived tractable TGIB objective function via variational approximation, enabling stable and efficient optimization. GTGIB-based models are evaluated to predict links on four real-world datasets; they outperform existing methods in all datasets under the inductive setting, with significant and consistent improvement in the transductive setting.

Individuals may have a range of opinions on controversial topics. However, the ease of making friendships in online social networks tends to create groups of like-minded individuals, who propagate messages that reinforce existing opinions and ignore messages expressing opposite opinions. This creates a situation where there is a decrease in the diversity of messages to which users are exposed ( diversity of exposure ). This means that users do not easily get the chance to be exposed to messages containing alternative viewpoints; it is even more unlikely that they forward such messages to their friends. Increasing the chance that such messages are propagated implies that an individuals’ susceptibility to persuasion is increased, something that may ultimately increase the diversity of messages to which users are exposed. This article formulates a novel problem which aims to identify a small set of users for whom increasing susceptibility to persuasion maximizes the diversity of exposure of all users in the network. We study the properties of this problem and develop a method to find a solution with an approximation guarantee. For this, we first prove that the problem is neither submodular nor supermodular and then we develop submodular bounds for it. These bounds are used in the Sandwich framework to propose a method which approximates the solution using reverse sampling. The proposed method is validated using four real-world datasets. The obtained results demonstrate the superiority of the proposed method compared to baseline approaches.

Influence maximization is a fundamental problem in social network analysis. This problem refers to the identification of a set of influential users as initial spreaders to maximize the spread of a message in a network. When such a message is spread, some users may be influenced by it. A common assumption of existing work is that the impact of a message is essentially binary: A user is either influenced (activated) or not influenced (non-activated). However, how strongly a user is influenced by a message may play an important role in this user’s attempt to influence subsequent users and spread the message further; existing methods may fail to model accurately the spreading process and identify influential users. In this article, we propose a novel approach to model a social network as a fuzzy graph where a fuzzy variable is used to represent the extent to which a user is influenced by a message (user’s activation level). By extending a diffusion model to simulate the spreading process in such a fuzzy graph, we conceptually formulate the fuzzy influence maximization problem for which three methods are proposed to identify influential users. Experimental results demonstrate the accuracy of the proposed methods in determining influential users in social networks.

Abstract Horizontal and vertical scalability have been widely studied in the context of computational resources. However, with the exponential growth in the number of connected objects, functional scalability (in terms of the size of software systems) is rapidly becoming a central challenge for building efficient service-oriented Internet of Things (IoT) systems that generate huge volumes of data continuously. As systems scale up, a centralized approach for moving data between services becomes infeasible because it leads to a single performance bottleneck. A distributed approach avoids such a bottleneck, but it incurs additional network traffic as data streams pass through multiple mediators. Decentralized data exchange is the only solution for realizing totally efficient IoT systems, since it avoids a single performance bottleneck and dramatically minimizes network traffic. In this paper, we present a functionally scalable approach that separates data and control for the realization of decentralized data flows in service-oriented IoT systems. Our approach is evaluated empirically, and the results show that it scales well with the size of IoT systems by substantially reducing both the number of data flows and network traffic in comparison with distributed data flows.

Abstract Cloud computing is an established paradigm for end users to access resources. Cloud infrastructure providers seek to maximize accepted requests, meet Service Level Agreements (SLAs), and reduce operational costs by dynamically allocating Virtual Machines (VMs) to physical nodes. Many solutions have been presented to manage cloud infrastructure, however, these tend to be centralized and suffer in their ability to maintain Quality of Service (QOS) and support data centers with thousands of nodes. Decentralized approaches, with no central management, can manage large data centers. However, these tend to reduce the ability to obtain an optimal resource allocation across the data center. To address this, we propose a hybrid hierarchical decentralized architecture that achieves lower SLA violations and lowers network traffic. We used simulation to evaluate our proposal in practice with a variety of existing VM placement policies.

Centrality measures have been widely used to capture the properties of different nodes in a social network, particularly when the edges are fully deterministic. Various models have also been proposed to calculate nodes’ centrality in graphs where there might be some uncertainty in relation to the edges. Their common characteristic is that graph uncertainty is essentially embedded into the calculation of centrality to compute a single crisp value. However, as the degree of uncertainty may vary, centrality values may also vary. In this paper, making use of fuzzy set theory, we assume that a social network is modelled by a fuzzy graph and a fuzzy variable is used to describe the truth degree of an edge between two nodes. Based on this formulation, appropriate definitions are given to determine the truth degree of different centrality values for a node and thereby centrality as a fuzzy relation. Three well-known centrality measures, degree, h-index and k-shell, are extended to calculate the truth degree for the centrality of a node in a fuzzy graph. Experimental results demonstrate that the proposed centrality measures can determine the importance of nodes in a fuzzy graph more accurately than other fuzzy or deterministic centrality measures.

Network graphs are widely used to model a variety of real-world interactions. In such graphs, nodes do not have the same importance in the graph structure as a result of the graph's topological properties. This may have various implications concerning a network's behaviour as, for example, how different nodes operate (even a node's failure) may not have the same impact for the whole network. The differences in the structural properties of the nodes imply that each node has different importance, which, in turn, gives rise to the notion of importance inequality in a graph. This paper defines and addresses the problem of importance inequality minimization, which may be useful to achieve certain properties in a network. Given a network graph and an integer$k$, the problem aims to identify$k$edges to connect non-adjacent nodes, in a way that minimizes the importance inequality of the graph. The paper provides a formal definition of the problem and proves its NP-hardness. Then, a naive greedy method is proposed, which is enhanced by heuristics that make its use practical. Experiments using 8 real-world networks are conducted to evaluate the proposed methods in terms of effectiveness and efficiency.

Synchronous dataflow graphs are widely used to model digital signal processing and multimedia applications. Self-timed execution is an efficient methodology for the analysis and scheduling of synchronous dataflow graphs. In this article, we propose a communication-aware self-timed execution approach to solve the problem of scheduling synchronous dataflow graphs on multicore systems with communication delays. Based on this communication-aware self-timed execution approach, four communication-aware scheduling algorithms are proposed using different allocation rules. Furthermore, a code-size-aware mapping heuristic is proposed and jointly used with a proposed scheduling algorithm to reduce the code size of SDFGs on multicore systems. The proposed scheduling algorithms are experimentally evaluated and found to perform better than existing algorithms in terms of throughput and runtime for several applications. The experiments also show that the proposed code-size-aware mapping approach can achieve significant code size reduction with limited throughput degradation in most cases.

This poster describes work in progress that is concerned with requirements engineering in the context of big data. Drawing experience from a H2020 project, this poster argues for a classification of requirements from different perspectives that can be used to guide the requirements elicitation process and form the basis of a common methodology for requirements engineering in big data applications.

Abstract With the increasing demand for dynamic and customised resource provisioning for computational experiments in e-Science, solutions are required to mediate different participants’ varied demands for such resource provision. This paper presents a novel negotiation protocol based on a new collaboration model. The protocol allows e-Scientists, the manager of an e-Scientist’s collaboration, and resource providers to reach resource provisioning agreements. By considering the manager of an e-Scientist collaboration for negotiation decisions, the protocol enables fine-grained accountable resource provision on a per job basis for e-Scientist collaborations, without binding the e-Scientist collaboration to resource providers. A testbed built with the protocol is also presented, making use of a production e-Science gateway, use cases, and infrastructures. The testbed is experimentally evaluated, via designed scenarios and comparison with existing production tools. It demonstrates that the proposed negotiation protocol can facilitate accountable resource provision per job, based on resource sharing rules defined and managed by e-Scientist collaborations.

New pricing policies are emerging where cloud providers charge resource provisioning based on the allocated CPU frequencies. As a result, resources are offered to users as combinations of different performance levels and prices which can be configured at runtime. With such new pricing schemes and the increasing energy costs in data centres, balancing energy savings with performance and revenue losses is a challenging problem for cloud providers. CPU frequency scaling can be used to reduce power dissipation, but also impacts virtual machine (VM) performance and therefore revenue. In this paper, we first propose a non-linear power model that estimates power dissipation of a multi-core CPU physical machine (PM) and second a pricing model that adjusts the pricing based on the VM's CPU-boundedness characteristics. Finally, we present a cloud controller that uses these models to allocate VM and scale CPU frequencies of the physical machine (PM) to achieve energy cost savings that exceed service revenue losses. We evaluate the proposed approach using simulations with realistic VM workloads, electricity price and temperature traces and estimate energy savings of up to 14.57 percent.

In cloud data centers, cloud providers can offer computing infrastructure as a service in the form of virtual machines (VMs). With the help of virtualization technology, cloud data centers can consolidate VMs on physical machines to minimize costs. VM placement is the process of assigning VMs to the appropriate physical machines. An efficient VM placement solution will result in better VM consolidation ratios which ensures better resource utilization and hence more energy savings. The VM placement process consists of both the initial as well as the dynamic placement of VMs. In this paper, we are experimenting with a dynamic VM placement solution that considers different resource types (namely, CPU and memory). The proposed solution makes use of a genetic algorithm for the dynamic reallocation of the VMs based on the actual demand of the individual VMs aiming to minimize under-utilization and over-utilization scenarios in the cloud data center. Empirical evaluation using CloudSim highlights the importance of considering multiple resource types. In addition, it demonstrates that the genetic algorithm outperforms the well-known best-fit decreasing algorithm for dynamic VM placement.

Databases as software components may be used to serve a variety of smart applications. Currently, the Internet of Things (IoT), Artificial Intelligence (AI) and Cloud technologies are used in the course of projects such as the Horizon 2020 EU-Korea DECENTER project in order to implement four smart applications in the domains of Smart Homes, Smart Cities, Smart Construction and Robot Logistics. In these smart applications the Big Data pipeline starts from various sensor and video streams to which AI and feature extraction methods are applied. The resulting information is stored in database containers, which have to be placed on Edge, Fog or Cloud infrastructures. The placement decision depends on complex application requirements, including Quality of Service (QoS) requirements. Information that must be considered when making placement decisions includes the expected workload, the list of candidate infrastructures, geolocation, connectivity and similar. Software engineers currently perform such decisions manually, which usually leads to QoS threshold violations. This paper aims to automate the process of making such decisions. Therefore, the goals of this paper are to: (1) develop a decision making method for database container placement; (2) formally verify each placement decision and provide probability assurances to the software engineer for high QoS; and (3) design and implement a new architecture that automates the whole process. A new optimisation method is introduced, which is based on the theory and practice of stochastic Markov Decision Processes (MDP). It uses as input monitoring data from the container runtime, the expected workload and user-related metrics in order to automatically construct a probabilistic finite automaton. The generated automaton is used for both automated decision making and placement success verification. The method is implemented in Java. It also uses the PRISM model-checking tool. Kubernetes is used in order to automate the whole process when orchestrating database containers across Edge, Fog and Cloud infrastructures. Experiments are performed for NoSQL Cassandra database containers for three representative workloads of 50000 (workload 1), 200000 (workload 2) and 500000 (workload 3) CRUD database operations. Five computing infrastructures serve as candidates for database container placement. The new MDP-based method is compared with the widely used Analytic Hierarchy Process (AHP) method. The obtained results are used to analyse container placement decisions. When using the new MDP based method there were no QoS violations in any of the placement cases, while when using the AHP based method the placement results in some QoS threshold violations in all workload cases. Due to its properties, the new MDP method is particularly suitable for implementation. The paper also describes a multi-tier distributed computing system that uses multi-level (infrastructure, container, application) monitoring metrics and Kubernetes in order to orchestrate database containers across Edge, Fog and Cloud nodes. This architecture demonstrates fully automated decision making and high QoS container operation.

The proliferation of Big Data applications puts pressure on improving and optimizing the handling of diverse datasets across different domains. Among several challenges, major difficulties arise in data-sensitive domains like banking, telecommunications, etc., where strict regulations make very difficult to upload and experiment with real data on external cloud resources. In addition, most Big Data research and development efforts aim to address the needs of IT experts, while Big Data analytics tools remain unavailable to non-expert users to a large extent. In this paper, we report on the work-in-progress carried out in the context of the H2020 project I-BiDaaS (Industrial-Driven Big Data as a Self-service Solution) which aims to address the above challenges. The project will design and develop a novel architecture stack that can be easily configured and adjusted to address cross-sectoral needs, helping to resolve data privacy barriers in sensitive domains, and at the same time being usable by non-experts. This paper discusses and motivates the need for Big Data as a self-service, reviews the relevant literature, and identifies gaps with respect to the challenges described above. We then present the I-BiDaaS paradigm for Big Data as a self-service, position it in the context of existing references, and report on initial work towards the conceptual specification of the I-BiDaaS software architecture.

In recent years, several new multipurpose Big Data platforms have emerged. They are used in various application domains with diverse requirements. Evaluating complex Big Data solutions is not a trivial task, due to the need to assess their utility in both quantitative and qualitative terms based on existing use cases. In this short paper, we discuss the requirements and the methodology for such an evaluation. We also discuss how benchmarking could be part of such an evaluation methodology.

Many emerging smart applications use sensor data, which are integrated by using various Big Data platforms. Such smart applications must address several requirements including high Quality of Service, privacy and security. Emerging fog computing technologies may provide some new possibilities to address these requirements through the design of multi-tier, container-based applications. In this work, we present the design of a smart application for the domain of civil engineering, which is currently undergoing testing and evaluation.

This paper develops a formal framework, founded on description logics, to assist decision making in relation to the manufacturing operation and control in modern enterprises that stand to benefit from the transition to Industry 4.0. The objective is to provide sophisticated support to individuals making decisions in the area of production operations management and in particular, production scheduling and material requirements planning. Using this framework, this paper demonstrates an approach to encode the domain knowledge of human experts managing the production as sets of formal rules. These rules can be implemented in an intelligent system that can assist and empower human experts, reducing difficulty when making decisions in complex manufacturing environments.

There is an increasing interest in applications where sensors or other devices (acting as publishers) may generate data that are processed and analyzed by specialized software components (acting as subscribers to this data) that extract useful information in a variety of scientific or industrial settings. As a result of the large volumes of data that are often generated, Cloud infrastructures may be used to handle the data links between publishers and subscribers. Assuming that a certain number of virtual machines of some given bandwidth have been booked for this purpose, the problem that this paper considers is how to allocate data links to the virtual machines so that the amount of data received by subscribers is maximized. An Integer Linear Programming formulation of the problem and two heuristics are presented, which are evaluated in a range of experiments.

Virtual machine (VM) placement is the process that allocates virtual machines onto physical machines (PMs) in cloud data centers. Reservation-based VM placement allocates VMs to PMs according to a (statically) reserved VM size regardless of the actual workload. If, at some point in time, a VM is making use of only a fraction of its reservation this leads to PM underutilization, which wastes energy and, at a grand scale, it may result in financial and environmental costs. In contrast, demand-based VM placement consolidates VMs based on the actual workload's demand. This may lead to better utilization, but it may incur a higher number of Service Level Agreement Violations (SLAVs) resulting from overloaded PMs and/or VM migrations from one PM to another as a result of workload fluctuations. To control the tradeoff between utilization and the number of SLAVs, parameter-based VM placement can allow a provider, through a single parameter, to explore the whole space of VM placement options that range from demand-based to reservation-based. The idea investigated by this paper is to adjust this parameter continuously at run-time in a way that a provider can maintain the number of SLAVs below a certain (predetermined) threshold while using the smallest possible number of PMs for VM placement. Two dynamic algorithms to select a value of this parameter on-the-fly are proposed. Experiments conducted using CloudSim evaluate the performance of the two algorithms using one synthetic and one real workload.

This paper reports the work in progress towards the specification of a conceptual architecture of a smart system for supporting the management of disruptions in the manufacturing domain. In particular, it proposes an approach to the description of the system architecture based on a number of interrelated viewpoints following the pertinent ISO 42010 standard. The approach is being developed in the context of the EU-funded H2020 DISRUPT project aiming to deliver a comprehensive data-driven solution for automated vertical and horizontal integration facilitating the transition into smart manufacturing.

Data-intensive scientific workflows, typically modelled by directed acyclic graphs, consist of inter-dependent tasks that exchange significant amounts of data and are executed on parallel/distributed clusters. However, the energy or monetary costs associated with large data transfers between tasks executing on different nodes may be significant. As a result, there is scope to explore the possibility of trading some communication for computation, aiming to reduce overall communication costs. In this work, we propose a scheduling approach that scales the weight of communication to increase its impact when building the schedule of a scientific workflow; the aim is to assign pairs of tasks with significant data transfers to the same computational node so that the overall communication cost is minimized. The proposed approach is evaluated using simulation and three real-world scientific workflows. The tradeoff between scientific workflow execution time and the size of data transfers is assessed for different weights and a different number of computational nodes.

Imprecise input data imposes special challenges to workflow scheduling. This paper introduces a robust scheduler based on particle swarm optimisation, called RobWE, which considers uncertainties of available bandwidth when producing schedules for workflow ensembles. The proposed scheduler is also a flexible scheduler since it allows the replacement of its objective function according to the user's needs. The effectiveness of the proposed RobWE scheduler is compared to a non-robust scheduler that does not consider the presence of such uncertainties. Results of simulations considering diverse scenarios, based on several degrees of uncertainty in available bandwidth estimates, characteristics of bandwidth estimations and workflow applications, demonstrate the advantages of the proposed RobWE scheduler.

Synchronous Dataflow Graphs (SDFGs) are widely used to model streaming applications (e.g. digital signal processing applications), which are commonly executed by embedded systems. The usage of on-chip resources is always strictly constrained in embedded systems. As the cost of instruction memory is a significant part of on-chip resource costs, code size reduction is an effective way to control the overall costs of on-chip resources. In this work, a code-size-aware mapping heuristic is proposed to decrease the code size for SDFGs on multicore systems. The mapping heuristic is jointly used with a self-timed scheduling heuristic to decrease the code size of the original schedule. In preliminary experiments, the proposed heuristic achieves significant code size reduction for all the tested SDFGs without affecting throughput.

Ever since the completion of the Human Genome Project in 2003, the human genome has been represented as a linear sequence of 3.2 billion base pairs and is referred to as the "Reference Genome". Since then it has become easier to sequence genomes of individuals due to rapid advancements in technology, which in turn has created a need to represent the new information using a different representation. Several attempts have been made to represent the genome sequence as a graph albeit for different purposes. Here we take a look at the Variant Calling Format (VCF) file which carries information about variations within genomes and is the primary format of choice for genome analysis tools. This short paper aims to motivate work in representing the VCF file as Directed Acyclic Graphs (DAGs) to run on a cloud in order to exploit the high performance capabilities provided by cloud computing.

A promising approach to increase the efficiency of infrastructure usage is to adapt the assignment of resources to workloads. This can be used, for example, to consolidate existing workloads so that the new capability can be used to serve new requests, or alternatively unused resources may be turned off to reduce energy consumption. Many architectural solutions have been presented for data centre management, however these tend to be centralised and may suffer in their ability to scale and support data centres with tens of thousands of nodes. Distributed approaches solve the scalability problem, however these do not have a global view of resources across the data centre. To address this, we propose a novel hybrid distributed hierarchical framework that is effective at providing the information needed for decision making at scale. We evaluate the performance of our approach by simulation, and demonstrate that a hybrid approach is a viable solution for managing large data centres, through rapid information dissemination and ability to make decisions using a global view.

A Grid information system resolves queries that may need to consider all information sources (Grid services), which are widely distributed geographically, in order to enable efficient Grid functions that may utilise multiple cooperating services. Fundamentally this can be achieved by either moving the query to the data ( query shipping ) or moving the data to the query ( data shipping ). Existing Grid information system implementations have adopted one of the two approaches. This paper explores the two approaches in further detail by evaluating them to the best possible extent with respect to Grid information system benchmarking metrics. A Grid information system that follows the data shipping approach based on the replication of information that aims to improve the currency for highly-mutable information is presented. An implementation of this, based on an Enterprise Messaging System, is evaluated using the benchmarking method and the consequence of the results for the design of Grid information systems is discussed.

E-Science is inherently a collaborative activity, which enables users from different institutions to share computational resources for analysing data. These rerources are provided by different distributed systems, e.g. Clouds, Grids, local Clusters. These can have different access and accounting mechanisms and the providers may have no direct connection to the institutions involved in the collaboration. We address the problem of how e-Science collaborations can manage access to such resources within the collaboration in a fair and accountable way. This requires accountable matchmaking on a fine grained level (e.g. per user request). This is enabled by a standard-based ontology in our work that extends models widely used for resource matching but provides extra functionality in the accounting domain.

New dynamic cloud pricing options are emerging with cloud providers offering resources as a wide range of CPU frequencies and matching prices that can be switched at runtime. On the other hand, cloud providers are facing the problem of growing operational energy costs. This raises a trade-off problem between energy savings and revenue loss when performing actions such as CPU frequency scaling. Although existing cloud controllers for managing cloud resources deploy frequency scaling, they only consider fixed virtual machine (VM) pricing. In this paper we propose a performance-based pricing model adapted for VMs with different CPU-bounded ness properties. We present a cloud controller that scales CPU frequencies to achieve energy cost savings that exceed service revenue losses. We evaluate the approach in a simulation based on real VM workload, electricity price and temperature traces, estimating energy cost savings up to 32% in certain scenarios.

In practical Cloud/Grid computing systems, DAG scheduling may be faced with challenges arising from severe uncertainty about the underlying platform. For instance, it could be hard to have explicit information about task execution time and/or the availability of resources, both may change dynamically, in difficult to predict ways. In such a setting, the development of various kinds of just-in-time scheduling schemes, which aim at maximizing the parallelism of ready tasks of DAG, seems to be a promising approach to cope with the lack of environment information and achieve efficient DAG execution. Although many attempts have been tried to develop such just-in-time scheduling heuristics, most of them are based on DAG decomposition, which results in complicated and suboptimal solutions for general DAGs. This paper presents a priority-based heuristic, which is not only easy to apply to arbitrary DAGs, but also exhibits comparable or better performance than the existing solutions.

Scientific workflows can be composed of many fine computational granularity tasks. The runtime of these tasks may be shorter than the duration of system overheads, for example, when using multiple resources of a cloud infrastructure. Task clustering is a runtime optimization technique that merges multiple short tasks into a single job such that the scheduling overhead is reduced and the overall runtime performance is improved. However, existing task clustering strategies only provide a coarse-grained approach that relies on an over-simplified workflow model. In our work, we examine the reasons that cause Runtime Imbalance and Dependency Imbalance in task clustering. Next, we propose quantitative metrics to evaluate the severity of the two imbalance problems respectively. Furthermore, we propose a series of task balancing methods to address these imbalance problems. Finally, we analyze their relationship with the performance of these task balancing methods. A trace-based simulation shows our methods can significantly improve the runtime performance of two widely used workflows compared to the actual implementation of task clustering.

Scientific workflows are a means of defining and orchestrating large, complex, multi-stage computations that perform data analysis and/or simulation. Task clustering is a runtime optimization technique that merges multiple short workflow tasks into a single job such that the job execution overhead is reduced and the overall runtime performance of the workflow is significantly improved. However, current task clustering strategies fail to consider the imbalance problem of both task runtime and task dependency. In our work, we first investigate the different causes of runtime imbalance and dependency imbalance. We then introduce a series of metrics based on our prior work to measure the severity of runtime and dependency imbalance respectively. Finally, we study a wide range of real scientific workflows to generalize the relationship between these metrics and balancing methods.

To guarantee the vision of Cloud Computing QoS goals between the Cloud provider and the customer have to be dynamically met. This so-called Service Level Agreement (SLA) enactment should involve little human-based interaction in order to guarantee the scalability and efficient resource utilization of the system. To achieve this we start from Autonomic Computing, examine the autonomic control loop and adapt it to govern Cloud Computing infrastructures. We first hierarchically structure all possible adaptation actions into so-called escalation levels. We then focus on one of these levels by analyzing monitored data from virtual machines and making decisions on their resource configuration with the help of knowledge management (KM). The monitored data stems both from synthetically generated workload categorized in different workload volatility classes and from a real-world scenario: scientific workflow applications in bioinformatics. As KM techniques, we investigate two methods, Case-Based Reasoning and a rule-based approach. We design and implement both of them and evaluate them with the help of a simulation engine. Simulation reveals the feasibility of the CBR approach and major improvements by the rule-based approach considering SLA violations, resource utilization, the number of necessary reconfigurations and time performance for both, synthetically generated and real-world data.

Cloud providers aim at guaranteeing Service Level Agreements (SLAs) in a resource-efficient way. This, amongst others, means that resources of virtual (VMs) and physical machines (PMs) have to be autonomically allocated responding to external influences as workload or environmental changes. Thereby, workload volatility (WV) is one of the crucial factors that influence the quality of suggested allocations. In this paper we devise a novel approach for self-adaptive and resource-efficient decision-making considering the three conflicting goals of minimizing the number of SLA violations, maximizing resource utilization, and minimizing the number of necessary time- and energy-consuming reconfiguration actions. We propose self-adaptive rule-based knowledge management for autonomic VM reconfiguration considering the rapidness of changes in the workload, i.e., WV. We introduce a novel WV categorization and present cost and volatility based methods for self-tuning. We evaluate these methods by a large variety of synthetically generated workloads, and by real-world measurements gathered from an image rendering application and a scientific workflow for RNA sequencing. Evaluation shows that in most cases the self-adaptive approach outperforms the static approach.

Abstract Workflows are widely used in applications that require coordinated use of computational resources. Workflow definition languages typically abstract over some aspects of the way in which a workflow is to be executed, such as the level of parallelism to be used or the physical resources to be deployed. As a result, a workflow management system has the responsibility of establishing how best to map tasks within a workflow to the available resources. As workflows are typically run over shared resources, and thus face unpredictable and changing resource capabilities, there may be benefit to be derived from adapting the task‐to‐resource mapping while a workflow is executing. This paper describes the use of utility functions to express the relative merits of alternative mappings; in essence, a utility function can be used to give a score to a candidate mapping, and the exploration of alternative mappings can be cast as an optimization problem. In this approach, changing the utility function allows adaptations to be carried out with a view to meeting different objectives. The contributions of this paper include: (i) a description of how adaptive workflow execution can be expressed as an optimization problem where the objective of the adaptation is to maximize a utility function; (ii) a description of how the approach has been applied to support adaptive workflow execution in execution environments consisting of multiple resources, such as grids or clouds, in which adaptations are coordinated across multiple workflows; and (iii) an experimental evaluation of the approach with utility measures based on response time and profit using the Pegasus workflow system. Copyright © 2010 John Wiley & Sons, Ltd.

Among the numerous DAG scheduling heuristics suitable for heterogeneous systems, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time. In this paper, we propose an improvement of HEFT, where the locally optimal decisions made by the heuristic do not rely on estimates of a single task only, but also look ahead in the schedule and take into account information about the impact of this decision to the children of the task being allocated. Preliminary simulation results indicate that the lookahead variation of HEFT can effectively reduce the makespan of the schedule in most cases without making the algorithm's execution time prohibitively high.

Workflows are widely used in applications that require coordinated use of computational resources. Workflow definition languages typically abstract over some aspects of the way in which a workflow is to be executed, such as the level of parallelism to be used or the physical resources to be deployed. As a result, a workflow management system has responsibility for establishing how best to map tasks within a workflow to the available resources. As workflows are typically run over shared resources, and thus face unpredictable and changing resource capabilties, there may be benefit to be derived from adapting the task-to-resource mapping while a workflow is executing. This paper describes the use of utility functions to express the relative merits of alternative mappings; in essence, a utility function can be used to give a score to a candidate mapping, and the exploration of alternative mappings can be cast as an optimization problem. In this approach, changing the utility function allows adaptations to be carried out with a view to meeting different objectives. The contributions of this paper include: (i) a description of how adaptive workflow execution can be expressed as an optimization problem where the objective of the adaptation is to maximize some property expressed as a utility function; (ii) a description of how the approach has been applied to support adaptive workflow execution in grids; and (iii) an experimental evaluation of the resulting approach for alternative utility measures based on response time and profit.

Abstract Workflows are widely used in applications that require coordinated use of computational resources. Workflow definition languages typically abstract over some aspects of the way in which a workflow is to be executed, such as the level of parallelism to be used or the physical resources to be deployed. As a result, a workflow management system has the responsibility of establishing how best to execute a workflow given the available resources. The Pegasus workflow management system compiles abstract workflows into concrete execution plans, and has been widely used in large‐scale e‐Science applications. This paper describes an extension to Pegasus whereby resource allocation decisions are revised during workflow evaluation, in the light of feedback on the performance of jobs at runtime. The contributions of this paper include: (i) a description of how adaptive processing has been retrofitted to an existing workflow management system; (ii) a scheduling algorithm that allocates resources based on runtime performance; and (iii) an experimental evaluation of the resulting infrastructure using grid middleware over clusters. Copyright © 2009 John Wiley & Sons, Ltd.

Self-managing solutions have recently attracted a lot of interest from the database community. The need for self-* properties is more evident in distributed applications comprising heterogeneous and autonomous databases and functionality providers. Such resources are typically exposed as Web Services (WSs), which encapsulate remote DBMSs and functions called from within database queries. In this setting, database queries are over WSs, and the data transfer cost becomes the main bottleneck. To reduce this cost, data is shipped to and from WSs in chunks; however the optimum chunk size is volatile, depending on both the resources' runtime properties and the query. In this paper we propose a robust control theoretical solution to the problem of optimizing the data transfer in queries over WSs, by continuously tuning at runtime the block size and thus tracking the optimum point. Also, we develop online system identification mechanisms that are capable of estimating the optimum block size analytically. Both contributions are evaluated via both empirical experimentation in a real environment and simulations, and have been proved to be more effective and efficient than static solutions.

Nowadays, Web Services (WS) play an important role in the dissemination and distributed processing of large amounts of data that become available on the Web. In many cases, it is essential to retrieve and process such data in blocks, in order to benefit from pipelined parallelism and reduced communication costs. This article deals with the problem of minimizing at runtime, in a self-managing way, the total response time of a call to a database exposed to a volatile environment, like the Grid, as a WS. Typically, in this scenario, response time exhibits a concave, nonlinear behavior depending on the client-controlled size of the individual requests comprising a fixed size task. In addition, no accurate profiling or internal state information is available, and the optimum point is volatile. This situation is encountered in several systems, such as WS Management Systems (WSMS) for DBMS-like data management over wide area service-based networks, and the widely spread OGSA-DAI WS for accessing and integrating traditional DBMS. The main challenges in this problem apart from the unavailability of a model, include the presence of noise, which incurs local minima, the volatility of the environment, which results in moving optimum operating point, and the requirements for fast convergence to the optimal size of the request from the side of the client rather than of the server, and for low overshooting. Two solutions are presented in this work, which fall into the broader areas of runtime optimization and switching extremum control. They incorporate heuristics to avoid local optimal points, and address all the aforementioned challenges. The effectiveness of the solutions is verified via both empirical evaluation in real cases and simulations, which show that significant performance benefits can be provided rendering obsolete the need for detailed profiling of the WS.

Data Grids provide transparent access to heterogeneous and autonomous data resources. The main contribution of this paper is the presentation of a data sharing system that (i) is tailored to data grids, (ii) supports well established and widely spread relational DBMSs, and (iii) adopts a hybrid architecture by relying on a peer model for query reformulation for retrieving semantically equivalent expressions, and on a wrapper-mediator integration model for accessing and querying distributed data sources. The system builds upon the infrastructure provided by the OGSA-DQP distributed query processor and the XMAP query reformulation algorithm. The paper discusses the implementation methodology, and also presents empirical evaluation results.

In this paper we examine the issue of optimizing disk usage and of scheduling large-scale scientific workflows onto distributed resources where the workflows are data- intensive, requiring large amounts of data storage, and where the resources have limited storage resources. Our approach is two-fold: we minimize the amount of space a workflow requires during execution by removing data files at runtime when they are no longer required and we schedule the workflows in a way that assures that the amount of data required and generated by the workflow fits onto the individual resources. For a workflow used by gravitational- wave physicists, we were able to improve the amount of storage required by the workflow by up to 57 %. We also designed an algorithm that can not only find feasible solutions for workflow task assignment to resources in disk- space constrained environments, but can also improve the overall workflow performance.

Abstract The aim of this paper is to argue for the benefits of increased expressiveness in service level agreements (SLAs). Such benefits may be obtained from the use of analytical expressions to specify a SLA's agreement terms as functions and not as variable or constant values or ranges. The main idea behind this thinking is that functions may contain variables defined in the SLA or be drawn from the known set of reference variables, such as wall‐clock time, job start time, current bandwidth of the resource, etc. Experiences and conclusions drawn are in the context of SLA‐based job management systems. We demonstrate that the use of analytical expressions in SLAs can potentially reduce the overheads associated with job renegotiation and/or reduce the number of failed agreements. Copyright © 2006 John Wiley & Sons, Ltd.

In this paper, we propose a Core Grid Ontology (CGO) that defines fundamental Grid-specific concepts, and the relationships between them. One of the key goals is to make this Core Grid Ontology general enough and easily extensible to be used by different Grid architectures or Grid middleware, so that the CGO can provide a common basis for representing Grid knowledge about Grid systems, including Grid resources, Grid middleware, services, applications, and Grid users. The Core Grid Ontology is designed and developed based on a general model ofGrid infrastructures, and described in the Web Ontology Language OWL. Such an ontology can play an important role in building Gridrelated Knowledge bases and in supporting the realization of the Semantic Grid.

Grid computational resources, as well as being heterogeneous, may also exhibit unpredictable, volatile behaviour. Therefore, query processing on the Grid needs to be adaptive in order to cope with evolving resource characteristics, such as machine load and availability. To address this challenge in a Grid environment, the non-adaptive OGSA-DQP1 system described in [1] has been enhanced with adaptive capabilities.

In the context of SLA based job scheduling for high performance grid computing, this paper investigates the behaviour of various scheduling heuristics to schedule SLA-bounded jobs onto a parallel computing resource. The key objective of this investigation is to evaluate the effectiveness of simple scheduling heuristics using as criteria the maximization of resource utilization (both in terms of time and SLAs serviced) and income. Our results suggest how each SLA constraint ought to be prioritized in order to improve the income.

The problem of scheduling a single DAG onto heterogeneous systems has been studied extensively. In this paper, we focus on the problem of scheduling more than one DAG at the same time onto a set of heterogeneous resources. The aim is not only to optimize the overall makespan, but also to achieve fairness, defined on the basis of the slowdown that each DAG would experience as a result of competing for resources with other DAGs. Two policies particularly focussing to deliver fairness are presented and evaluated along with another four policies that can be used to schedule multiple DAGs.

Current operating systems (OS) perceive the different contexts of simultaneous multithreaded (SMT) processors as multiple independent processing units, although, in reality, threads executed in these units compete for the same hardware resources. Furthermore, hardware resources are assigned to threads implicitly as determined by the SMT instruction fetch (Ifetch) policy, without the control of the OS. Both factors cause a lack of control over how individual threads are executed, which can frustrate the work of the job scheduler. This presents a problem for general purpose systems, where the OS job scheduler cannot enforce priorities, and also for embedded systems, where it would be difficult to guarantee worst-case execution times. In this paper, we propose a novel strategy that enables a two-way interaction between the OS and the SMT processor and allows the OS to run jobs at a certain percentage of their maximum speed, regardless of the workload in which these jobs are executed. In contrast to previous approaches, our approach enables the OS to run time-critical jobs without dedicating all internal resources to them so that non-time-critical jobs can make significant progress as well and without significantly compromising overall throughput. In fact, our mechanism, in addition to fulfilling OS requirements, achieves 90 percent of the throughput of one of the best currently known fetch policies for SMTs.

In Simultaneous Multithreaded (SMT) architectures most hardware resources are shared between threads. This provides a good cost/performance trade-off which renders these architectures suitable for use in embedded systems. However, since threads share many resources, they also interfere with each other. As a result, execution times of applications become highly unpredictable and dependent on the context in which an application is executed. Obviously, this poses problems if an SMT is to be used in a real-time system.In this paper, we propose two novel hardware mechanisms that can be used to reduce this performance variability. In contrast to previous approaches, our proposed mechanisms do not need any information beyond the information already known by traditional job schedulers. Nor do they require extensive profiling of workloads to determine optimal schedules. Our mechanisms are based on dynamic resource partitioning. The OS level job scheduler needs to be slightly adapted in order to provide the hardware resource allocator some information on how this resource partitioning needs to be done. We show that our mechanisms provide high stability for SMT architectures to be used in real-time systems: the real time benchmarks we used meet their deadlines in more than 98% of the cases considered while the other thread in the workload still achieves high throughput.

The simulation of large grids requires the generation of grid instances and an approximation of grid components' behaviour. To generate grid instances, this paper outlines a set of high-level properties of grids and considers ways to assign values to those properties. The paper also brings together existing application-level network and host models and discusses how they are used for the simulation of large grids. A grid instantiation is described in detail as part of a master-slave case study, and a large grid is simulated for the evaluation of a variety of scheduling strategies. The case study also motivates a performance prediction method, which is assessed against simulation results.

In a simultaneous multithreaded (SMT) architecture, the front end of a superscalar is adapted in order to be able to fetch from several threads while the back end is shared among the threads. In this paper, we describe different resource sharing models in SMT processors. We show that explicit resource allocation can improve SMT performance. In addition, it enables SMTs to solve other QoS requirements, not realizable before.

Summary form only given. This paper is motivated by the observation that different methods to compute the weights of nodes and edges when scheduling DAGs onto heterogeneous machines may lead to significant variations in the generated schedule. To minimize such variations, we present a novel heuristic for DAG scheduling, which is based upon solving a series of independent task scheduling problems. A novel heuristic for the latter problem is also included. Both heuristics compare favourably with other related heuristics.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

In this paper, we propose and evaluate practical, automatic techniques that exploit compiler analysis to facilitate simulation of very large message-passing systems.We use a compilersynthesized static task graph model to identify the control-flow and the subset of the computations that determine the parallelism, communication and synchronization of the code, and to generate symbolic estimates of sequential task execution times.This information allows us to avoid executing or simulating large portions of the computational code during the simulation.We have used these techniques to integrate the MPI-Sim parallel simulator at UCLA with the Rice dHPF compiler infrastructure.The integrated system can simulate unmodified High Performance Fortran (HPF) programs compiled to the Message-Passing Interface standard (MPI) by the dHPF compiler, and we expect to simulate MPI programs as well.We evaluate the accuracy and benefits of these techniques for three standard benchmarks on a wide range of problem and system sizes.Our results show that the optimized simulator has errors of less than 17% compared with direct program measurement in all the cases we studied, and typically much smaller errors.Furthermore, it requires factors of 5 to 2000 less memory and up to a factor of 10 less time to execute than the original simulator.These dramatic savings allow us to simulate systems and problem sizes 10 to 100 times larger than is possible with the original simulator.

This paper presents an overview of the activities carried out within the ESPRIT project OCEANS whose objective is to investigate and develop advanced compiler infrastructure for embedded VLIW processors. This combines high and low-level optimisation approaches within an iterative framework for compilation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Parallelising compilers typically need some performance estimation capability in order to evaluate the trade-offs between different transformations. Such a capability requires sophisticated techniques for analysing the program and providing quantitative estimates to the compiler's internal cost model. Making use of techniques for symbolic evaluation of the number of iterations in a loop, this paper describes a novel compile-time scheme for partitioning loop nests in such a way that load imbalance is minimised. The scheme is based on a property of the class of canonical loop nests, namely that, upon partitioning into essentially equal-sized partitions along the index of the outermost loop, these can be combined in such a way as to achieve a balanced distribution of the computational load in the loop nest as-a-whole. A technique for handling non-canonical loop nests is also presented; essentially, this makes it possible to create a load-balanced partition for any loop nest which consists of loops whose bounds are linear functions of the loop indices. Experimental results on a virtual shared memory parallel computer demonstrate that the proposed scheme can achieve better performance than other compile-time schemes.