Full system emulators provide virtual platforms for several important applications, such as kernel and system software development, co-verification with cycle accurate CPU simulators, or application development for hardware still in development. Full system emulators usually use dynamic binary translation to obtain reasonable performance. This paper focuses on optimizing the performance of full system emulators. First, we optimize performance by enabling classic control transfer optimizations of dynamic binary translation in full system emulation, such as indirect branch target caching and block chaining. Second, we improve the performance of memory virtualization of cross-ISA virtual machines by improving the efficiency of the software translation lookaside buffer (software TLB). We implement our optimizations on QEMU, an industrial-strength full system emulator, along with the Android emulator. Experimental results show that our optimizations achieve an average speedup of 1.98X for ARM-to-X86-64 QEMU running SPEC CINT2006 benchmarks with train inputs. Our optimizations also achieve an average speedup of 1.44X and 1.40X for IA32-to-X86-64 QEMU and AArch64-to-X86-64 QEMU on SPEC CINT2006. We use a set of real applications downloaded from Google Play as benchmarks for the Android emulator. Experimental results show that our optimizations achieve an average speedup of 1.43X for the Android emulator running these applications.

Dynamic binary translation (DBT) is a core technologyto many important applications such as system virtualization, dynamic binary instrumentation, and security. However, there are several factors that often impede its performance: 1) emulation overhead before translation; 2) translation and optimization overhead; and 3) translated code quality. The issues also include its retargetabilitythat supports guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs-an important feature to system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, and use a multithreaded approach to implement DBT. By running the translator and the dynamic binary optimizer on different cores with different threads, it could off-load the overhead incurred by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and Low-Level Virtual Machine (LLVM) as our building blocks, we demonstrated in a multithreaded DBT prototype, called Hybrid-QEMU (HQEMU), that it could improve QEMU performance by a factor of 2.6x and 4.1x on the SPEC CPU2006 integer and floating point benchmarks, respectively, for dynamic translation of x86 code to run on x86-64 platforms. For ARM codes to x86-64 platforms, HQEMU can gain a factor of 2.5x speedup over QEMU for the SPEC CPU2006 integer benchmarks. We also address the performance scalability issue of multithreaded applications across ISAs. We identify two major impediments to performance scalability in QEMU: 1) coarse-grained locks used to protect shared data structures, and 2) inefficient emulation of atomic instructions across ISAs. We proposed two techniques to mitigate those problems: 1) using indirect branch translation caching (IBTC) to avoid frequent accesses to locks, and 2) using lightweight memory transactions to emulate atomic instructions across ISAs. Our experimental results show that for multithread applications, HQEMU achieves 25X speedups over QEMU for the PARSEC benchmarks.

Most dynamic binary translators (DBT) and optimizers (DBO) target binary traces, i.e. frequently executed paths, as code regions to be translated and optimized. Code region formation is the most important first step in all DBTs and DBOs. The quality of the dynamically formed code regions determines the extent and the types of optimization opportunities that can be exposed to DBTs and DBOs, and thus, determines the ultimate quality of the final optimized code. The Next-Executing-Tail (NET) trace formation method used in HP Dynamo is an early example of such techniques. Many existing trace formation schemes are variants of NET. They work very well for most binary traces, but they also suffer a major problem: the formed traces may contain a large number of early exits that could be branched out during the execution. If this happens frequently, the program execution will spend more time in the slow binary interpreter or in the unoptimized code regions than in the optimized traces in code cache. The benefit of the trace optimization is thus lost. Traces/regions with frequently taken early-exits are called delinquent traces/regions. Our empirical study shows that at least 8 of the 12 SPEC CPU2006 integer benchmarks have delinquent traces.

Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. On the dynamic binary translator itself, the issues also include its retargetability to support guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs, an important feature for system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, using multithreaded approach to implement DBT. By running the translators and the dynamic binary optimizers on different threads on different cores, it could off-load the overhead caused by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as the support of its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU, that it could improve QEMU performance by a factor of 2.4X and 4X on the SPEC 2006 integer and floating point benchmarks for x86 to x86-64 emulations, respectively, i.e. it is only 2.5X and 2.1X slower than native execution of the same benchmarks on x86-64, as opposed to 6X and 8.4X slowdown on QEMU. For ARM to x86-64 emulation, HQEMU could gain a factor of 2.4X speedup over QEMU for the SPEC 2006 integer benchmarks.

This paper presents an LLVM+QEMU (LnQ)framework for building high performance and retargetable binary translators with existing compiler modules. Dynamic binary translation is a just-in-time (JIT) compilation from binary code of guest ISA to binary code of host ISA. The quality of translated code is critical to the performance of a dynamic binary translator, which translates code between different IS As, so the translated code is often carefully hand-optimized. As a result, it takes tremendous implementation efforts for software engineers to port an existing dynamic binary translator to anew host ISA. The goal of LnQ framework is to enable the process of building high performance and retarget able dynamic binary translators with existing optimizers and code generation back ends. LnQ framework consists of a translation module and an emulation engine. We design the translation module based on LLVM compiler infrastructure, and use QEMU as our emulation engine. We implement an x86-to-x86 64 dynamic binary translator with our LnQ framework to show that the framework is retarget able, and conduct experiments on SPECCPU2006 benchmarks to show that the resulting binary translator has good performance. The experiment results indicate that the x86-to-x86 64 LnQ translator achieves an average speedup of 1.62X in integer benchmarks, and 3.02X in floating point benchmarks than QEMU.

In recent years, Data Grid becomes a promising technology to collect geographically distributed storage resources and provide a large amount of storage capacity. Such resources include personal computers, clusters or high-end servers managed by different administrative domains. Although many production Data Grids have been developed for various usages, there remain no approaches to integrating them together. To solve the problem, we propose a federation middleware, called FedMi, to integrate heterogeneous Data Grids as a single Data Grid and provide users with a uniform access interface. In this paper, four issues, including interoperability among Data Grids, single sign-on, secure communication and high performance data transfer, are addressed. We also present the evaluation results of the approaches proposed to improve the performance of data transfer across Data Grids.

In the last decade, the evolution of distributed computing has shifted from cluster computing to Grid computing. Although bidding provides a useful means of resource allocation for this novel computing paradigm, there exist two challenges to scheduling metatasks in bidding-based Grid systems. (1) The scheduling algorithm has to avert collisions between the jobs of a metatask, as well as prevent contention between the metatasks submitted by different requesters. (2) There is no global information system to facilitate optimum decision-making; hence, requesters are only aware of partial information released by resource providers. To address these challenges, we propose a set of scheduling heuristics to minimize the makespan of each metatask, while simultaneously considering the level of information about competing metatasks revealed by providers. We also present the results of experiments conducted to evaluate the performance of the proposed heuristics.

In this paper, we propose a resource management model that extends the Contract Net Protocol by integrating the advantages of the matchmaking technique. Our model addresses the issues of matchmaker overload and the lack of up-to-date resource state information suffered by the original matchmaking model. It also enables resource requesters to obtain a list of qualified resources with which they can narrow down the selection of resources and reduce the number of ineffective communication messages. In addition, we present five strategies to facilitate resource selection on our model from the perspective of turnaround time and reporton experiments to evaluate their performance. The experiment results show that, in the presence of resource contention, the probabilistic strategies outperform random and the deterministic ones, and the performance of the presented strategies executed on our model is superior to their performance on the original matchmaking model.

We study the replication transition problem (RTP) in the Grid systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to data access pattern, and a good strategy can improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another in order to cope with the dynamic data access pattern. This paper focuses on the RTP problem for Grid systems in four communication models that have different communication capabilities, i.e., whether message forwarding is allowed and whether network capacity is uniform among different links. We show that there exists a polynomial time algorithm that provides optimal solution for the RTP problem when forwarding is not allowed and the communication links are uniform. We also propose heuristic algorithms for solving variants of the RTP problem and conduct experiments to evaluate their performances. The experimental results indicate that our proposed heuristics are very effective.

We study the replication transition problem in distributed hierarchical systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to the data access pattern, therefore a good strategy can effectively improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result, a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another, in order to cope with the dynamic access pattern. This paper focuses on solving the replication transition problem on tree topology, which is one of the most important models in data grid systems and Web proxy systems from the literature. To the best of our knowledge, our work is the first that proposes an optimal algorithm for the replication transition problem on tree topology. The algorithm has a time complexity of O(n log Deltalog(nLambda)), where n is the number of sites, Delta is the maximum degree in the tree and Lambda is the largest communication delay in the network.

As the number of data-intensive applications increases in various domains, scientists need to save, retrieve, and analyze increasingly large datasets. The huge volume of data and the long latency of data transfer on the Internet make it very difficult to ensure high-performance access to data grids. Thus, data replication techniques have been widely adopted to solve the latency problem. In this paper, we propose an efficient data replication algorithm for multi-source data transfer, whereby a data replica can be assembled in parallel from multiple distributed data sources and adapted to the variability of network bandwidths. The experimental results show that the proposed algorithm can obtain more aggregated bandwidth, reduce connection overheads, and achieve superior load balance.

This paper introduces a new graph theory problem called generalized edge coloring (g.e.c). A generalized edge coloring is similar to traditional edge coloring, with the difference that a vertex can be adjacent to up to k edges that share the same color. The concept of generalized edge coloring can be used to formulate the channel assignment problem in multi-channel multi-interface wireless networks. We provide theoretical analysis for this problem. Our theoretical findings can be useful for system developers of wireless networks. We show that when k = 3, there are graphs that do not have generalized edge coloring that could achieve the minimum number of colors for every vertex. On the contrary, when k = 2 we show that if we are given one extra color, we can find a generalized edge coloring that uses the minimum number of colors for each vertex. In addition, we show that for certain classes of graphs we are able to find a generalized edge coloring that uses the minimum number of colors for every vertex without the extra color. These special classes of graphs include bipartite graph, graphs with a power of 2 maximum degree, or graphs with maximum degree no more than 4