Search

Computation offloading between the edge and the cloud is an effective way for deployed service to fully utilize the resources at both sides for its QoS improvement and overall cost reduction. Although the offloading problem has been intensively studied in the context of mobile computing, existing algorithms in most cases cannot be effectively migrated to the edge-cloud environment because their inter-partition communication costs are always deemed as symmetric, and their intra-partition communication costs are often ignored, which, though reasonable to the traditional case, are not valid to our settings anymore. In this article, we propose a new algorithmic approach to the offloading problem in the edge-cloud environment, where a heterogeneous model is advocated to incorporate the communication cost between co-resident tasks while considering the asymmetry of communication costs between non-coresident tasks. We prove the offloading problem with respect to this model is NP-hard, and thereby designing an efficient algorithm to obtain a sub-optimal solution. Additionally, we also show that in a homogeneous case when the intra-partition and inter-partition communication costs between any pair of interactive tasks are symmetric, an optimal offloading algorithm can be devised by transforming the problem into a classical min-cut problem. We implemented and evaluated the algorithms by offloading a PageRank -based application in a controlled edge-cloud setting. Our empirical results show that the proposed algorithm for the heterogeneous case is always efficient to find a better offloading scheme, compared with the selected existing algorithms, while for the homogeneous case, the proposed solution can efficiently achieve the optimal strategy.

Parallel file system (PFS) is commonly used in high-end computing systems. With the emergence of solid state drives (SSDs), hybrid PFS, which consists of both HDD and SSD servers, provides a practical I/O system solution for data-intensive applications. However, most existing data layout schemes are inefficient for hybrid PFS due to their unawareness of server heterogeneities and workload changes in different parts of a file. In this study, we propose a heterogeneity-aware region-level data layout scheme, HARL, to improve the data distribution of a hybrid PFS. HARL first divides a file into fine-grained, varying sized regions according to the workload features of an application, then determines appropriate file stripe sizes on servers for each region based on the performance of heterogeneous servers. Furthermore, to further improve the performance of a hybrid PFS, we propose a dynamic region-level layout scheme, HARL-D, which creates multiple replicas for each region and redirects file requests to the proper replicas with the lowest access costs at the runtime. Experimental results of representative benchmarks and a real application show that HARL can greatly improve I/O system performance, and demonstrate the advantages of HARL-D over HARL.

Graphics processing units (GPU), due to their massive computational power with up to thousands of concurrent threads and general-purpose GPU (GPGPU) programming models such as CUDA and OpenCL, have opened up new opportunities for speeding up general-purpose parallel applications. Unfortunately, pre-silicon architectural simulation of modern-day GPGPU architectures and workloads is extremely time-consuming. This paper addresses the GPGPU simulation challenge by proposing a framework, called GPGPU-MiniBench, for generating miniature, yet representative GPGPU workloads. GPGPU-MiniBench first summarizes the inherent execution behavior of existing GPGPU workloads in a profile. The central component in the profile is the Divergence Flow Statistics Graph (DFSG), which characterizes the dynamic control flow behavior including loops and branches of a GPGPU kernel. GPGPU-MiniBench generates a synthetic miniature GPGPU kernel that exhibits similar execution characteristics as the original workload, yet its execution time is much shorter thereby dramatically speeding up architectural simulation. Our experimental results show that GPGPU-MiniBench can speed up GPGPU architectural simulation by a factor of 49 $\times$ on average and up to 589 $\times$ , with an average IPC error of 4.7 percent across a broad set of GPGPU benchmarks from the CUDA SDK, Rodinia and Parboil benchmark suites. We also demonstrate the usefulness of GPGPU-MiniBench for driving GPU architecture exploration.

Recent embedded middleware platforms enable the structuring of an application as a set of collaborating agents deployed on various nodes of the underlying wireless sensor network (WSN). Of particular importance is the network cost incurred due to agent communication, which in turn depends on how the agents are placed within the WSN system. In this paper, we present two agent migration algorithms with the aim of minimizing the total network overhead. The first one takes independent single agent migration decisions, while the second one considers groups of agents for migration. Both algorithms work in a fully distributed fashion based on the knowledge available locally at each node, and can be used both for one-shot initial application deployment as well as for the continuous updating of agent placement. We also propose two methodologies to tackle the problem when WSN nodes have limited capacity. We show through theoretical analysis that one of our algorithms (called GRAL$\ast$ ) always results in an optimal placement, while for the rest of the algorithms, we derive approximation ratios pertaining to their performance. We evaluate the performance of our algorithms through a series of simulation experiments. Results show that group migration algorithms are superior compared to single agent migration algorithms with the performance difference reaching 34% for some settings.

Resource discovery is critical to the usability and accessibility of grid computing systems. Distributed Hash Table (DHT) has been applied to grid systems as a distributed mechanism for providing scalable range-query and multi-attribute resource discovery. Multi-DHT-based approaches depend on multiple DHT networks with each network responsible for a single attribute. Single-DHT-based approaches keep the resource information of all attributes in a single node. Both classes of approaches lead to high overhead. In this paper, we propose a Low-Overhead Range-query Multi-attribute (LORM) DHT-based resource discovery approach. Unlike other DHT-based approaches, LORM relies on a single compound graph-based DHT network and distributes resource information among nodes in balance by taking advantage of the compound graph structure. Moreover, it has high capability to handle the large-scale and dynamic characteristics of resources in grids. Experimental results demonstrate the efficiency of LORM in comparison with other resource discovery approaches. LORM dramatically reduces maintenance and resource discovery overhead. In addition, it yields significant improvements in resource location efficiency. We also analyze the performance of the LORM approach rigorously by comparing it with other multi-DHT-based and single-DHT-based approaches with respect to their overhead and efficiency. The analytical results are consistent with experimental results, and prove the superiority of the LORM approach in theory.

Dynamic voltage scaling (DVS) is a promising technique for battery-powered systems to conserve energy consumption. Most existing DVS algorithms assume information about task periodicity or a priori knowledge about the task set to be scheduled. This paper presents an analytical model of general tasks for DVS assuming job timing information is known only after a task release. It models the voltage scaling process as a transfer function-based filtering system, which facilitates the design of two efficient scaling algorithms. The first is a time-invariant scaling policy and it is proved to be a generalization of several popular DVS algorithms for periodic, sporadic, and aperiodic tasks. A more energy efficient policy is a time-variant scaling algorithm for aperiodic tasks. It is optimal in the sense that it is online without assumed information about future task releases. The algorithm turns out to be a water-filling process with a linear time complexity. It can be applied to scheduling based on worst-case execution times as well as online slack distribution when jobs complete earlier. We further establish two relationships between computation capacity and deadline misses to provide a statistical real-time guarantee with reduced capacity

It is important to guarantee client-perceived end-to-end quality of service (QoS) under heavy load conditions. Existing work focuses on network transfer time or server-side request processing time. In this paper, we propose a novel framework, eQoS, to monitor and control client-perceived response time in heavy loaded Web servers. The response time is measured with respect to Web pages that contain multiple embedded objects. Within the framework, we propose an adaptive fuzzy controller, STFC, to allocate server resources. The controller assumes no knowledge of the pageview traffic model. It deals with the effect of process delay in resource allocation by its two-level self-tuning capabilities. We also prove the stability of the STFC. We implement a prototype of eQoS in Linux and conduct comprehensive experiments across wide-range server workload conditions on PlanetLab and simulated networks. Experimental results demonstrate the effectiveness of the framework: it controls the deviation of client-perceived pageview response time to be within 20 percent of a predefined target with both synthetic and real Web traffics. We also compare the STFC with other controllers, including static fuzzy, linear proportional integral (PI), and adaptive PI controllers. Experimental results show that, although the STFC works slightly worse than the static fuzzy controller in the environment where the static fuzzy controller is best tuned, because of its self-tuning capabilities, it has better performance in all other test cases by around 25 percent on average in terms of the deviation from the target response time. In addition, due to its model independence, the STFC outperforms the linear PI and adaptive PI controllers by 50 percent and 75 percent on average, respectively