Zhenzhong Zhang
email: zzzhang@cse.buaa.edu.cn

Limin Xiao
email: xiaolm@buaa.edu.cn

Xianchu Chen
email: chengxc@cse.buaa.edu.cn

Junjie Peng
email: jjie.peng@shu.edu.cn

A Scheduling Method for Multiple Virtual Machines Migration in Cloud

Keywords: Cloud Computing, Virtual Machine Schedule, Multiple Virtual Machines Migration, IaaS

Infrastructure as a Service(IaaS) is important in Cloud Computing, which provides on-demand virtual machines(VMs) to users. The resource management plays an important role in IaaS cloud, which deploys and relocates virtual machine on available hosts for different targets, such as load balance, power saving and resource utilization improving. The virtual machine placement problem can be considered as a bin packing problem. Many researchers use the heuristic algorithms based approach to solve this virtual machine placement problem. However, they all focus on how to find the optimization solution for the bin packing problem of virtual machine placement. However, these studies did not consider the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another. Because of the large overhead produced by virtual machine migration, the optimization of multiple virtual machines migration process could reduce the overhead of resource management in IaaS cloud, and accelerate the migration process. In this paper, we analyse and formal the multiple virtual machines migration problem, and propose a scheduling method to reduce the VM migration times and accelerate the migration process. Experiments show that our method can decrease the VM migration times, reduce the traffic and accelerate the process of multiple virtual machine migration.

Introduction

Cloud computing [START_REF] Armbrust | A view of cloud computing[END_REF] is a popular trend in current computing which attempts to provide cheap and easy access to computational resources. IaaS(Infrastructure as a Service) [START_REF] Zhang | Cloud computing: state-of-the-art and research challenges[END_REF] provides infrastructure or the actual hardware to customers who are responsible to install operating systems and necessary softwares. Based on virtualization technology [START_REF] Rosenblum | Virtual machine monitors: Current technology and future trends[END_REF], IaaS cloud is usually provided to users in the form of Virtual Machines (VMs), such as Amazon EC2 [START_REF]Amazon Elastic Compute Cloud[END_REF] and VMware vCloud [START_REF]vCloud[END_REF]. On IaaS cloud platform, resources are provided by need as services, and it guarantees to the subscribers that it sticks to the Service Level Agreement (SLA). IaaS cloud platform needs to dynamically deploy and relocate virtual machine onto proper physical hosts in order to meet different needs, such as avoid hotspot, power saving and load balancing [START_REF]vCloud[END_REF][START_REF] Ren | A dynamic load balancing strategy for cloud computing platform based on exponential smoothing forecast[END_REF][START_REF] Srikantaiah | Energy aware consolidation for cloud computing[END_REF]. Therefore, how to dynamically and efficiently schedule virtual machines among physical hosts to meet the needs of different targets becomes a problem. The traditional resource management methods usually schedule virtual machine or allocate resource in cloud when some certain conditions are triggered [START_REF]Resource management with VMware DRS[END_REF][START_REF] Song | A service-oriented priority-based resource scheduling scheme for virtualized utility computing[END_REF][START_REF] Zhang | A VM-based Resource Management Method Using Statistics[END_REF], such as threshold for load balancing. Due to the complexity and variability of a large number of virtual machines in IaaS cloud, traditional methods are difficult to carry out global resource optimization management. To address this issue, many optimization theory based virtual machine placement approaches are used to solve the resource management problem in IaaS cloud [START_REF] Bobroff | Dynamic placement of virtual machines for managing sla violations[END_REF][START_REF] Verma | pMapper: power and migration cost aware application placement in virtualized systems[END_REF]. In such scenario, the resource management problem is considered as a bin packing problem, which need to find the proper mapping of virtual machines to available physical machines.

Linear programming [START_REF] Lin | Interference-aware virtual machine placement in cloud computing systems[END_REF], genetic algorithm [START_REF] Campegiani | A general model for virtual machines resources allocation in multi-tier distributed systems[END_REF] and ant colony algorithm [START_REF] Gao | A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[END_REF] have been used to solve the bin packing problem, and obtained good results. All these researches are focused on how to find the actual mapping of virtual machines to available physical machines(V-P mapping). However, these studies did not consider the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another. Because the virtual machine migration process needs to copy large amounts of data(memory data or even virtual disk) from the source host to the destination host, it will produce large CPU overhead and network traffic, and cost much resource. Therefore, the optimization of multiple virtual machines migration process could reduce the overhead of resource management in IaaS cloud and accelerate the migration process. The optimization includes reducing the number of virtual machine migration, and migrating small VM instead of big VM.

In this paper, we study the multiple virtual machines migration problem, and propose a scheduling method to optimize multi-virtual machine migration process. The main contributions of this paper are concluded as the followings: (1)Modeling and formalization of the multiple virtual machines migration problem; (2)A scheduling method optimizing the multiple virtual machines migration process.

Related Work

For resource management in cloud data center, previous work has focused on the problem of placing and replacing VMs in servers, in order to optimize resource management for different criteria, including performance, power and cost. There are some molded products and research projects on virtualized resource management, such as VMware DRS [START_REF]Resource management with VMware DRS[END_REF]. They dynamically allocate the CPU, memory and I/O resources to partitioned virtual machines according to customer's requirements, but they ignore the QoS [START_REF] Song | A service-oriented priority-based resource scheduling scheme for virtualized utility computing[END_REF]. The work in [START_REF] Khanna | Application performance management in virtualized server environments[END_REF] minimized the number of physical machines using dynamic adaptation technique based on off-line analysis of application performance, which is seen as a function of machine utilization. The load forecasting techniques are also widely used in the management of cloud resources, such as load-balancing and re-source scheduling [START_REF] Prevost | Load prediction algorithm for multi-tenant virtual machine environments[END_REF]. In [START_REF] Wang | Coordinating power control and performance management for virtualized server clusters[END_REF], a model-predictive controller is proposed to minimize the total power consumption of the servers in an enclosure subject to a given set of QoS constraints.

Optimization and heuristic methods are wildly used by virtual machine scheduling and placement in IaaS cloud for different targets, such as load balancing or power saving. Integer Linear Programming is used to solve an interference-aware VM placement problem(IAWMP) [START_REF] Lin | Interference-aware virtual machine placement in cloud computing systems[END_REF]. They first formulate this problem by an Integer Linear Programming (ILP) model to solve it optimally. They also propose a polynomial-time heuristic algorithm to efficiently solve the IAWMP problem. In [START_REF] Campegiani | A general model for virtual machines resources allocation in multi-tier distributed systems[END_REF] a general model is proposed for resources allocation of virtual machines in multi-tier distributed environments. Their model describes each virtual machine and each physical host by a multi-dimensional resource vector, allowing the coexistence of both quantitative and qualitative resources, also handling different SLAs. [START_REF] Gao | A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[END_REF] proposes a multiobjective ant colony system algorithm for the virtual machine placement problem. Their method could efficiently obtain a set of non-dominated solutions that simultaneously minimize total resource wastage and power consumption. [START_REF] Liao | Towards a green cluster through dynamic remapping of virtual machines[END_REF] proposes a runtime virtual machine mapping framework(GreenMap), and designs a probabilistic, heuristic algorithm to mapping VMs onto a set of physical machines under the constraint of multi-dimensional resource consumptions. However, all above optimization and heuristic researches are focus on how to find the actual mapping of virtual machines to available physical machines(V-P mapping). Although some virtual machine migration research [START_REF] Liu | Performance and energy modeling for live migration of virtual machines[END_REF][START_REF] Jin | Live virtual machine migration with adaptive, memory compression[END_REF] can help to accelerate virtual machine migration process, however, the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another was rarely considered. Therefore, in this paper, we will study the multiple virtual machines migration problem, and propose a scheduling method to optimize multivirtual machine migration process.

3

Problem Analysis And Formulation

Analysis of multiple virtual machines migration problem

In this paper, the heuristics-based resource management methods are consist of two steps, which is shown in Figure 1. Firstly, the bin packing problem of virtual machine management is solved by a heuristic based algorithm, and the global approximate optimal virtual machine groups are obtained. The VMs mapping to same physical host are in same group, called a VM-cluster. Next, For the global optimal virtual machine grouping, we also need to convert the virtual machines to physical host mapping(V-P mapping) from current state(initial VM location) to the target state(final VM location).

Bin packing optimization algorithm for V-P grouping

Schedule algorithm For multiple VM migration

Information collection VM groups

VM migration steps

Fig. 1. The process of VM placement in IaaS cloud

The same VM group can locate on different hosts, therefore the target state is not unique. This process of V-P mapping convert involves the migration of multiple virtual machines, which could be scheduled to reduce the migration cost of VMs. Our study is focused on the optimization of the multiple virtual machines migration process. The purpose of this optimization is to minimize the overhead of CPU and network cost and avoid resource conflicts during the migration process(migration the number of virtual machines, choose the smaller virtual machine migration, adjust virtual machine migration steps to avoid conflicts). The optimization includes the choosing of VM for migration, the selecting of destination physical host, and accelerate the migration process of all VMs. For example, If several V-P mappings have same effect, we will choose the one that has minimum number of VM migration. If several V-P mapping have same VM migration steps, the one with minimal numbers of VM migration times will be chosen.

We need to develop a model to describe the scheduling problem of multiple virtual machines migration. In this model, the virtual machines which belong to same physical host are in the same group, and called a VM-cluster. At the initial moment, the VM-clusters of all virtual machines in IaaS cloud are the initial state of V-P mapping. Our schedule method is responsible for converting the V-P mapping from one type of VM-cluster to another VM-cluster. In this process, the proper physical host should be chosen for every VM-cluster, and the proper order of virtual machine migration determined, which is equivalent to create a new mapping of VM-clusters to physical hosts. Of course, this new mapping must meet the demand that the number of VM migration and the amount of traffic are as small as possible.

Formal Description of the VM schedule problem

We formalize the virtual machines to physical hosts mapping problem in this section. Firstly, we define some basic objects below:

 Host is denoted by H k (k=1,2...,N), and the set of hosts is H={H 1 ,H 2 ,...,H N },(N>=1).

V j denotes all the virtual machines that need to be migration. The set of virtual machine is V = {V 1 ,V 2 ,…,V n }(n>=1). The virtual machines that locate on the same physical host form a virtual machine set. We call this set the VM-cluster which is denoted by C i (i=1,2...,M). The set of VM-cluster is C={C 1 ,C 2 ,…,C M }. In order to simplify this model, we require M always be no more than N, that is the number of VM-clusters should be less than or equal to the number of hosts.  L(V j ) is the amount of network traffic that generated by the migration of virtual machine V j . Cost is the total amount of traffic generated by multiple virtual machines migration. In the initial state, each virtual machine running on a particular station host to form a set of virtual machine clusters.  At the initial state, each virtual machine running on a particular host to form a set of VM-cluster. And it will be converted to another set of VM-cluster by our schedule method. If the virtual machine V j belongs to a cluster C i , it is denoted as V j ∈C i .

The optimal mapping of virtual machines to physical hosts will be selected by our scheduling method.

3.3

The VM scheduling method

After management strategy at initial state, all the virtual machines in the system are re-divided into a set of VM-clusters(shown as V j ∈ C i , C i ∈C). The establishment of mapping of virtual machines to physical hosts is equivalent to choose the suitable of physical host H k for each VM-cluster C i . Our multiple virtual machine migration scheduling method need to create mapping of VM-cluster set(C) to physical host set(H) as f(M→N), and select the optimal one that meet our targets(minimum migrations, etc.). Each mapping establishes a relationship between VM-clusters to hosts, and determines the target hosts that each virtual machine will migrate to. Therefore migration path of the virtual machines is also determined. Because the mapping of VM-cluster(C, the number of C is M) to physical hosts(H, the number of H is N) will generate a large number of virtual machine migration paths( ). Our scheduling algorithm needs to search for the optimal solution in all migration paths, and we will use heuristic approaches to simplify the process. After the optimal migration path is obtained, our scheduling algorithm will further determine the optimal virtual machine migration steps based on the principle of minimum system cost.

Fig. 2. The migration path of f1 and f2

We show a simple examples here, to describe our method in detail. As a case that virtual machines V1-V9 run on three hosts(H1, H2, H3). After bin packing optimization, these virtual machines are divided into three clusters(C1:V1,V2,V4,V9; C2:V3,V6,V8;C3:V5,V7). Two different mappings are available, the mapping of f1 is (C1→H2,C2→H3,C3→H1), and the mapping of f2 is (C1→H1,C2→H2,C3→H3). F1 and f2 are shown in Figure 2.A and 2.B. These two mappings correspond to two multiple virtual machine migration paths. These two migration paths choose different physical hosts for VM-clusters, resulting in a different number of VM migrations. Obviously, the path of f2 needs to migrate 5 VMs, which is less than 7 VMs of f1.

When the two mappings have the same VM migration times, the different size and load of virtual machines will also lead to a larger difference of network traffic and CPU load. For example, the migration of virtual machine with large memory and higher workload needs to copy more data and consume more CPU resources. L(V j ) indicates the network traffic generated by virtual machine V j during migration. The total transfer data of fx is Cost(fx), which is the sum of all L(V j ). Like the first step, the cost of each migration paths are estimated and the one with minimum migration traffic would be chosen.

While the virtual machines starts migrate, the migrating virtual machines which have same source or destination host would migrate one by one. Because the node migration performance of host would decreased significantly due to simultaneous execution of multiple virtual machine migration. And of course, the virtual machines which their migration do not conflict with each other, could migrate at same time.

4

Design and implementation

Host Selection Algorithm for Virtual Machine

The host selection algorithm for virtual machine is used to find the optimal mapping from all possible V-P mapping, and to obtain the proper destination hosts for the VMs. Specifically, it needs to search all mappings of VM-cluster(C, the number is M) to physical hosts(H, the number is N), and selects the optimal mapping as the multiple virtual machine migration path. The optimal selection principle is minimum migration times of multiple migration process and minimum amount of migration network traffic(ie, the migration of VMs with smaller size will generate less network traffic). An improved genetic algorithm is be used to search the best mapping solution in this case. Due to limited space, the details of the genetic algorithm are not shown here. The pseudo-code of our based algorithm is shown in Figure 8. The algorithm traverses all mappings (lines 1-11) to obtain the minimum value of VM migration times and generates the set F which contains all the mappings with the minimum migration times (lines 8-9). Finally, it calculates the network traffic(Cost(f)) for each mapping in F, and select the mapping with minimum network as the return result of the algorithm (lines 12-15). In the algorithm, V j is the virtual machine with number j, Y j is the host where the virtual machine V j current locates, fs is a mapping of virtual machines to hosts, Y j ' is the host that V j will migrate to with the fs mapping, F is a set of mapping with minimum VM migration times, Cost(f) is the network traffic generate by VMs migration of mapping f and Min(F) is the mapping with minimum Cost(f) in set F.

The Migration Order and Parallelization of Multiple VMs Migration

After the selection of target hosts for multiple virtual machine hosts migration, the schedule algorithm next needs to determine the migration order of these virtual machines to be migrated. Our scheduling algorithm will generate a trituple < , > for each virtual machine that needs to be migrated. is the virtual machine need to be migrated, and are the source and destination hosts for migration of . The order of multiple virtual machine migration could be represented by this trituple sequence. Our algorithm is mainly based on the following two principles to arrange the order of multiple virtual machine migration, and execute the migration process.

Firstly, the scheduler give priority to migrates virtual machine on high-load host to the low-load host, and give priority to migrates virtual machines with higher workload and bigger size. The migration of virtual machine will cost much CPU resource both on source and destination hosts. While priority migrate virtual machine on high-load host to low-load host, we need only consider the impact of migration on the source host(high-load host). And on the other hand, if migrate VM to a high-load host, there may be no enough resource remained for this virtual machine. Meanwhile, the scheduler priority migrate virtual machine with higher workload on source host. This is mainly because the virtual machine with higher workload is more sensitive to resource competition. A bit more workload increase will cause the performance of the application decline. But for the application on low-load virtual machine, the workload increase is tolerable. And based on the queuing theory, the VM with bigger memory size has less priority to migrate. Therefore, according to the above aspects, the scheduler can minimize the impact of VM migration on application performance.

Secondly, the parallel migration can be used for the virtual machines whose migration do not interfere with each other. For performance and stability reasons, a physical host can only deal with one virtual machine migration, either as an source host or as a destination hosts. Therefore, we can refer to the realization of processor's instructionlevel parallelism to parallel processing the multiple virtual machines migration. In this case, the trituple sequence of migration VM is handled as the sequence of instructions of processor. When a VM migration is in processed, the source and destination hosts are marked busy, and reset free after VM migration. Therefore, while the source and destination hosts of the trituple being processed are not busy, the migration of this trituple could be executed immediately. Based on this strategy, our method can achieves parallel virtual machine migration, and avoid resource conflict.

Experiment And Evaluation

In this section, we validate and test the multiple virtual machine migration scheduling method, then analysis its performance. Using different test cases of multiple virtual machines migration to verify the effect of our schedule algorithm. The performance of our method is compared with default migration method, which migrate virtual machines one by one randomly.

For our experiment environment, we use a cluster composed by eight computer servers and one storage array. The configuration of server includes two AMD Opteron 2350 quad-core CPUs running at 2.0GHz and 12GB DDR RAM. They are all running XenServer 6.1 [START_REF]Xenserver[END_REF]. The storage array connects four hosts through optical fiber, as a shared storage. All the servers are connected by a Gigabit LAN. The virtual machine templates are configured with one VCPU, 1GB,2GB,4GB RAM and one virtual network card. The load generator program will randomly call some of the popular applications to generate the CPU, network and disk I/O workload, such as kernel compilation, file compression, and FTP, etc.

Verify the effectiveness of our algorithm

We select a test case to validate effectiveness of our scheduling algorithm. This test case uses 12 virtual machines and 8 physical hosts. The detail configuration of each virtual machine and physical host are shown in Table 1. These configurations of test case include input of algorithm, memory of VM and physical, the mapping of virtual machine to physical before and after migration, the workload of each virtual machine and physical host and the output of algorithm at stage 1 and 2. The output of our algorithm is listed in Table 1. Because our algorithm is divided into two stages, our validation also has two stages.

Firstly, the output of the first stage of our algorithm is a set of V-P mapping which has the minimum virtual machine migration times. For this test case, the minimum migration times is 5, and the mapping in the set is (f1: V10-->H1, V3-->H1, V11-->H2, V4-->H4, V7-->H4) and (f2: V10-->H1, V3-->H1, V11-->H2, V5-->H6, V6-->H6). Then the algorithm compares the migration traffic of each mapping, and chooses the V-P mapping with minimum migration traffic as the optimal migration path. In this test case, the Cost(f1) = L(V10)+L(V3)+L(V11)+L(V4)+L(V7) = 14GB, and Cost(f2) = L(V10)+L(V3)+L(V11)+L(V5)+ L(V6) = 13GB. Because Cost(f1) is greater than Cost(f2), our algorithm will select the f2 as the optimal migration path for multiple virtual machine migration. The second stage of the algorithm is to generate a virtual machine migration sequence based on the optimal mapping f2 which obtained by the first stage. The migra-tion sequence is shown as a trituple sequence in Table 2. According to our optimization strategy, the migration order output by the second stage of out algorithm is V5, V3, V6, V10, V11. This is because the virtual machine V5 has a higher workload, and the physical host V5 reside on has the highest workload in the physical hosts. The virtual machine V10 and V11 migrate at last, due to the large memory(4098MB).

The Table 3 shows the parallel migration process of multiple virtual machines based on the migration order. We divide virtual machine migration process to several periods. During each period, 1GB data could be transferred. As Table shows, the migrating VMs, waiting VMs and physical hosts which be occupied for each period during migration process. In Table 3, at T1 period, the migration of virtual machine V5 is executed. However, VM V3 and V6 are waiting due to resource confliction, and VM V10 and V11 can migrate at T1 period without interference with each other. At the beginning of T3 period, VM V5 finishes the migration. The next VM V3 could not start migration because of the destination host(H1) of V3 is busy. Thus, the VM V6 starts migration at T3 period. The VM V3 finishes migration at end of T5 period. The total time of the parallel migration are 5 periods. Compared with the 13 periods of serial migration, the parallel virtual machine migration greatly reduces migration time(160%), and avoids resource conflicts in multiple virtual machine migration.

Verify the versatility of our algorithm

We choose several test cases to validate the algorithm's versatility. The detailed configuration of these test cases are shown in Table 4. 30 virtual machines are running on three physical hosts, each VM has 1GB memory. The VM-cluster inputs of five test cases are shown in Table 5. The results of migration time for each test case are shown in Figure 9. We can see that, compared with default migration strategy, the average VM migration times of our algorithm is lower. The degree of optimization is different for each test case depending on the initial mapping state. This experiment shows that in most cases, our algorithm can optimize the process of multiple virtual machine migration.

CONCLUSION AND FUTURE WORK

This paper presents a schedule method for multiple virtual machine migration. The contributions of this paper include: [START_REF] Armbrust | A view of cloud computing[END_REF] We analyze and formal the problem of multiple virtual machine migration; [START_REF] Zhang | Cloud computing: state-of-the-art and research challenges[END_REF] We propose a schedule algorithm for multiple virtual machine migration. The algorithm contains two parts. The first is finding the minimum cost VM migration path from all mapping of virtual machine to physical hosts, and the second an algorithm generating the optimization virtual machine migration sequence, and accelerating multiple virtual machine migration process based on parallelize techniques; (3) We use some experiments to verify the effectiveness and versatility of the algorithm. In this paper, the algorithm proposed has high complexity, and it's performance is not good while dealing with large-scale multi-virtual machine migration case. Therefore, we need to improve the scalability of the our method.

1 . 12 .15. End for 16 .Fig. 3 .

 112163 Fig. 3. The algorithm for Optimal mapping selection

Fig. 4 .

 4 Fig. 4. Migration time of five time cases

  t C a s e D e fa u lt M Ig ra tio n O u r s c h e d u le M Ig ra tio n C a s e 2

Table 1 .

 1 The configuration of test case

	Input of VM-cluster	C1:v1,v2,v3,v10;C2:v4,v5,v6,v7;C3:v8,v9,v11,v12
	Information of VMs
	VM ID	Mem(MB)	Init reside host ID	Load(%)
	V1	1024	H1	30%
	V2	1024	H1	60%
	V3	1024	H4	50%
	V4	2048	H6	15%
	V5	2048	H4	80%
	V6	2048	H4	50%
	V7	3072	H6	40%
	V8	3072	H2	35%
	V9	3072	H2	45%
	V10	4096	H5	70%
	V11	4096	H7	50%
	V12	4096	H2	10%
	Information of physical hosts before VMs migration
	Host ID	Mem(GB)	VMs	Load(%)
	H1	12	V1,V2	15%
	H2	12	V8,V9,V12	15%
	H3	12	None	0%
	H4	12	V3,V5,V6	30%
	H5	16	V10	10%

Table 2 .

 2 The trituple Sequence for migration step

	Id	Trituple	Load(VM/Host)	Mem(MB)
	1	(V10,H5->H1)	70%/10%	4096
	2	(V3,H4->H1)	50%/30%	1024
	3	(V11,H7->H2)	50%/10%	4096
	4	(V5,H4->H6)	80%/30%	2048
	5	(V6,H4->H6)	50%/30%	2048
	Migration step: V5,V3,V6,V10,V11

Table 3 .

 3 The parallel migration process for multiple virtual machine migration

	Tim	Migrating VMs/ Mem(G)	Waiting VMs	Busy Hosts
	e
	T1	V5(2G),V10(4G),V11(4G)	V3(1G),V6(2G)	H4,H6,H5,H1,H7,H2
	T2	V5(2G),V10(4G),V11(4G)	V3(1G),V6(2G)	H4,H6,H5,H1,H7,H2
	T3	V10(4G),V11(4G),V6(2G)	V3(1G)	H5,H1,H7,H2,H4,H6
	T4	V10(4G),V11(4G),V6(2G)	V3(1G)	H5,H1,H7,H2,H4,H6
	T5	V3(1G)	None	H4,H6

Table 4 .

 4 The distribution state of virtual machines

	VM/Host	Host1	Host2	Host3
	VM ID	V1~V10	V11~V20	V21~V30

Table 5 .

 5 Five test cases

	ID/	C1	C2	C3
	VM-cluster
	Case 1	1,11,12,13,14,15,16,1 7,18,19	2,3,4,5,6,7,8,9,10,20,30	21,22,23,24,25,26,27,28, 29
	Case 2	1,2,3,5,11,12,14,17,2 1,24,25	4,13,15,16,18,19,20,22, 23,26,28	6,7,8,9,10,27,29,30
	Case 3	1,2,3,5,24,25	4,13,15,16,18,19, 26,28,11,12,14,17,21	6,7,8,9,10,27,29,30,20,2 2,23
	Case 4	1,14,17,21,24,25,16,1	4,13,15,	6,10,27,29,30,2,3,5,11,1
		8,19,20	22,23,26,28,7,8,9	2
	Case 5	1,12,14,17,21,24,19,2 0,22, 9,10,27,25	4,13,15,2,3,5,11,16,18, 23,26,28	6,7,8, 29,30

Acknowledgments: This work is supported by the National Natural Science Foundation of China(61232009); the State Key Laboratory of Software Development Environment (SKLSDE-2012ZX-07); the Doctoral Fund of Ministry of Education of China (20101102110018); the Hi-Tech Research and Development Program (863) of China (2011AA01A205); the Beijing Natural Science Foundation(4122042); Shanghai Science and Technology Innovation Action Plan(11511500400)


Chen Ding

Lei Liu

Access Annotation for Safe Program Parallelization

The safety of speculative parallelization depends on monitoring all program access to shared data. The problem is especially difficult in softwarebased solutions. Till now, automatic techniques use either program instrumentation, which can be costly, or virtual memory protection, which incurs false sharing. In addition, not all access requires monitoring. It is worth considering a manual approach in which programmers insert access annotations to reduce the cost and increase the precision of program monitoring. This paper presents an interface for access annotation and two techniques to check the correctness of user annotation, i.e. whether all parallel executions are properly monitored and guaranteed to produce the sequential result. It gives a quadratic-time algorithm to check the exponential number of parallel interleavings. The paper then uses the annotation interface to parallelize several programs with uncertain parallelism. It demonstrates the efficiency of program monitoring by a performance comparison with OpenMP, which does not monitor data access or guarantee safety.

Introduction

With the advent of multicore processors, existing applications written in Fortran/C/C++ are increasingly adapted to parallel execution using programming interfaces such as OpenMP, Cilkplus and TBB. They are efficient but do not guarantee correctness. The correctness problem is more serious when parallelizing large program code, mainly due to several issues of uncertainty:

-Complex code. A task may execute low-level or dynamic code not amenable to static analysis. Example problems include exceptions in control flow, indirections in data access, dynamic memory allocation and custom memory management. -Partial information. A programmer may read and understand only a part but not the whole program. The program may use separately compiled libraries. -Uncertain parallelism. Parallelism may exist in most but not all iterations of a loop or in some but not all inputs of a program. Important irregular computing tasks such as mesh refinement, clustering, image segmentation, and SAT approximation cannot be fully parallelized without speculation [START_REF] Kulkarni | Optimistic parallelism requires abstractions[END_REF].

Speculative parallelization is a technique to guard parallelism against uncertainty. To make it programmable, a number of systems provide primitives to mark a speculative task as a safe future [START_REF] Welc | Safe futures for Java[END_REF], an ordered transaction [START_REF] Von Praun | Implicit parallelism with ordered transactions[END_REF], or a possibly parallel region (PPR) [START_REF] Ding | Software behavior oriented parallelization[END_REF]. In this paper, we call a speculative task a PPR task and use the support system called BOP for speculation on commodity multicore machines [START_REF] Ding | Software behavior oriented parallelization[END_REF][START_REF] Ke | Safe parallel programming using dynamic dependence hints[END_REF].

Safe parallelization depends on monitoring data access, which in software is typically done in two ways. The first is program instrumentation. The cost is high if too many data accesses are instrumented. A compiler may remove unnecessary instrumentation but only for applications amenable to static analysis [START_REF] Rauchwerger | The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization[END_REF][START_REF] Tian | Supporting speculative parallelization in the presence of dynamic data structures[END_REF]. The other solution is virtual-memory support to monitor data at page granularity, which incurs false sharing [START_REF] Berger | Grace: Safe multithreaded programming for C/C++[END_REF][START_REF] Ding | Software behavior oriented parallelization[END_REF]. While these solutions are automatic and transparent to a user, they are not most efficient or precise especially when monitoring complex code.

The monitoring problem may be better solved with programmer control. In this paper, we define an interface for access annotation and integrate it into the BOP system. The new interface provides two primitives for marking data writes and data reads. The user annotation may be too much or too little, causing four possible problems:

-Insufficient annotation. Some reads and writes should be annotated but not. Incompleteness can lead to three types of errors:

• Incorrect output. Speculation does not generate sequential output.

• Nondeterministic output. Speculation generates different outputs depending on PPR task interleaving. • Partial correctness. The annotation is sufficient for some but not all inputs.

-Redundant annotation. The same access may be repeatedly annotated.

To check completeness, we describe two techniques, to be applied in order: 1. Semantic checking, which runs the PPR tasks in the sequential order and checks whether the output is the same as the sequential execution. The sequential PPR execution is the canonical execution, which is different from the sequential execution as we will explain later. 2. Determinism checking, which uses a quadratic number of tests to check whether all parallel interleavings produce the same result as the canonical execution, which means the sequential output if applied after the first step.

Semantic checking finds missing write annotations, while determinism checking looks for missing read annotations. The time cost is linear to the number of PPR tasks in the former and quadratic in the latter. If both checks are passed, the annotation is sufficient for the given test input. For this input, all parallel executions are guaranteed to produce the sequential result.

For the problem of redundant annotation, we view the new interface as a solution rather than a new cause. In the program examples shown throughout the paper, we will see how the interface enables a programmer to insert minimal annotation. Still, a user may over optimize. Then the problem becomes a completeness issue, which is the same as a user being too lazy or lacking knowledge. It will require annotation checking, which is the subject of this paper.

Annotation checking is a form of debugging. It is not guaranteed to find all errors. This is a familiar limitation to the programmer. If a program runs on an untested input and produces an error, the two-step checking can be re-applied to add overlooked annotations. With the checking support, parallel coding is similar to sequential coding. Systematic testing can be used to gain a high degree of certainty that the parallelized program has the right semantics and is safe.

The new model maintains and extends the benefits of speculative parallelization. Because of the sequential semantics, parallelized code is easier to write and understand. It can be composed with other sequential code or automatically parallelized code. There is no need for parallel debugging-the parallelized code produces the correct output if the sequential code does. A program may be fully annotated, so it no longer needs speculation. Finally, an BOP program can run on a cluster of machines without shared memory [START_REF] Jacobs | Distributive program parallelization using a suggestion language[END_REF].

Next, we describe in detail the need of access annotation and the two checking techniques, before we evaluate and discuss related work.

Access Annotation

To properly insert access annotation, a programmer needs to understand which tasks are parallel and how they share data. Since not all tasks are parallel, not all data access requires annotation.

The Execution Model

The parallelism hint is as follows:

bop ppr{X}Y. The bop ppr block suggests possible parallelism-X is likely parallel with the subsequent code Y. Y is also known as the continuation of X.

At run time, the PPR hints divide a sequential execution into a series of PPR tasks, numbered in an increasing order starting from 0. Any two tasks have a sequential order between them, so we can refer to them as the earlier task and the later task. We assume no nesting. 1A PPR task is dynamic. It has two parts. The link is the initial execution after the previous PPR and before the next PPR hint. It executes the code between two PPR hints. After the link, the body is the execution of the code inside the PPR hint. We call these two parts the link PPR and the body PPR. The parallelism happens between a body and all later links, and between all bodies. We call all links collectively as the backbone. The backbone is sequential, and the bodies are limbs hanging on the backbone. Next we show how PPR tasks share data and how BOP ensures correctness.

Data Copy and Merge

Logically, a BOP program is sequential, and all data is shared. In implementation, BOP uses a two-step strategy to share data correctly:

1. Data copy-on-write during parallel execution. BOP runs each task as a Unix process. For each page that the task modifies, the OS makes a private copy and hence removes all interference between PPR tasks.

2. Sequential merge after parallel execution. After a PPR task finishes, the changes are collected as a PPR patch. BOP merges the patches from multiple PPR tasks to ensure that the results be the same as the would-be sequential execution.

Figure 1 shows two PPR tasks. Although they both modify x, they do not conflict because each will do copy-on-write and then write to its private copy. After they finish, they will bundle the changes into two patches. At the merge, the x value from the later PPR task is kept to maintain sequential semantics. The two steps can be called copy-n-merge. The reason for using the strategy is compelling: copy-n-merge removes all false dependences in a parallel execution and all data races in a concurrent execution. A necessary condition for a dependence or a race is that two operations access the same memory location, and at least one is a write. By copy-on-write, no two tasks can access the same location unless it is read only. Removing this necessary condition removes any false dependence or data race, just as removing oxygen extinguishes the fire.

Access Annotation

There are two types of annotations:

ppr write( addr, size ) says that the PPR task produces a new value for data at memory addr for size bytes. ppr read( addr, size ) says that the PPR task needs the latest value produced before the PPR task for data at addr for size bytes.

Semantically, an annotation is a requirement on the information flow. The read annotation means that the reading PPR task must have the up-to-date value, the value from the last write before the PPR task (in the sequential execution). The write annotation means that the new value should be delivered to the remaining program execution for use by later reads of the data. These two requirements are intuitive, although not entirely precise.

Operationally, the annotations are used by BOP to create the PPR patch. After a task finishes, its patch includes the set of memory locations read and modified by the task and for each modified location, the last written value, i.e. the value it has at the end of the PPR execution. These patches are used at the merge time for conflict checking and data commit.

An annotation may be placed anywhere and can be executed more than once during the task execution. Because PPR tasks do not physically share data during the execution, the annotations specify only the values coming in and going out. As a result, the same data needs at most two annotations in a PPR task, one for the read, and one for the write, regardless how many times the task reads or writes the data. For the writes, only the last value will be copied into the PPR patch. For the reads, the task must read the correct value at the first time.

The read annotation is needed for the reads in both the link and the body of a PPR task, while the write annotation is needed only for the writes in the PPR body. To understand this slight asymmetry, we use Table 1 to enumerate all cases of true dependences between PPR link and body pairs. Of the four possible (source, sink) pairings, only the last two-(body i, body j) and (body i, link j), i < j -are parallel. Since both types of dependences begin at a PPR body, it is the only place we need to be annotate for writes. Access annotation is used to monitor dependences. It is indirect compared to annotating dependences explicitly. The indirect approach has several benefits. First, the number of dependence annotations may be quadratic to the length of the code, while the number of access annotations is at most linear. Second, access annotations are modular. They can be specified function by function and aggregated in larger modules without any extra effort. Finally, the source and sink locations of a dependence may be dynamic.

Correctness Checking

We use the following notations. PPR tasks are numbered from 0 to n -1. Each PPR task, ppr[i], has a link link[i] and a body body[i]. If a program ends in a link task, for symmetry we assume there is an empty body[n -1] after link[n -1]. For each task, we record two sets of memory locations, read, write, which are the memory locations annotated by ppr read and ppr write. Also recorded are the values, the value at the first read for each memory location in the read set and the value at the last write for each location in the write set.

Semantics Checking

The results of a PPR task are communicated in a patch. If a PPR task writes to x, and x is not annotated by a ppr write, the new value will not be included in the patch and will not be seen by computation outside the task. If the new value is only used inside the PPR task and not needed outside the task, the write annotation is extraneous. Omitting an extraneous annotation improves efficiency.

However, if the new value of the write is needed, directly or indirectly, to produce a program output later, then the write annotation is necessary. The absence of the annotation is an error. We call it a missing write annotation. The purpose of semantics checking is to examine the program execution for a given input and ensure that the program has no write annotation missing for this input.

The algorithm is given in Figure 2. Each PPR task is run twice, first in the sequential execution and second in the canonical execution. To distinguish their results, the algorithm refers to the first as seq ppr[i] and the second as cano ppr [i].

A missing write annotation may cause the canonical execution to generate a different output than the sequential execution. This is detected because some of the reads will be wrong. A user can examine the canonical execution in a debugger. Debugging is conventional since there is no concurrency or non-determinism. We note that if an error is detected at ppr[ j], the missing write annotation may be anywhere in ppr[0.. j -1]. Not detecting an error at ppr[i] does not mean ppr[0..i] has no missing annotation. Only when the algorithm finishes, will we know whether the program has all necessary write annotations for the test input.

Correctness proof . We prove by contradiction. Assume that semantics checking detects no error but there is an unannotated write in a PPR task that is actually necessary because its value is used to produce a later output. Since the write is not annotated, its value is not visible outside the PPR. If the value is needed to produce an output, the output in the canonical execution must be incorrect, which contradicts the assumption that the checking has succeeded.

Determinism Checking

If a task ppr[i] writes x, and ppr[ j] reads and prints x, i < j, the canonical execution will be correct since the ppr[ j].write is merged into the backbone before ppr[ j] starts. ppr[ j] does not need a read annotation. In a real run, however, ppr[ j] must exhibit a true dependence to ppr[i]. This can be done by adding to ppr[ j] a read annotation for x. Parallel semantics checking is to ensure that there are enough read annotations to mark all the true dependences between PPR tasks.

In a parallel execution, PPR bodies may finish in any order. In the absence of true dependences, their patches may be merged at different times. There are two restrictions.

-Merge time. A patch can only be merged at the juncture between the end of a PPR body and the start of the next PPR link. Any number of patches can be merged at the same juncture. -Merge order. The patches can only be added in the sequential order of the PPR tasks. For example, the patch for ppr[i], i.e. ppr[i].write, can be merged only after ppr[0..i -1].write have all been merged first.

Under these two restrictions, there is still much freedom in when patches are merged. For example, if ppr[0..i -1].write are merged before link[ j], then ppr[i].write may be merged before any link[k] for k ≥ j.

We can view each PPR body as a single unit, and the merge time as its execution time on the backbone. Then all link and body executions are serialized. The number of possible orders is the number of all legal interleavings subject to three constraints: an earlier link happens before a later link, an earlier body happens before a later body, and the link happens before the body for the same PPR.

The interleaving problem is similar to arranging parentheses correctly in a sequence. Let link[i] and body[i] be a pair of parentheses. A sequence of n open-close parentheses corresponds to the sequential execution of 2n link and body tasks. Any sequence of properly nested parentheses corresponds to a possible parallel interleaving. The number of different sequences is 2n! n!(n+1)! , known as the Catalan number. A read annotation is missing in a PPR task if its absence can cause one or more of its annotated writes to produce a value different from the canonical execution. Determinism checking detects missing read annotations inductively for each PPR in sequential order.

The algorithm for determinism checking is given in Figure 3. The checking is done in a nested loop. The iterations of the outer loop are the inductive steps. At step i, ppr[i] is checked to have sufficient read annotations such that its patch is always the same as its patch in the canonical execution, which is the same as its patch in the sequential execution. For the first PPR, there is nothing to check. For the second PPR, there are two cases. The body[0].write may be merged before or after link [START_REF] Allen | Optimizing Compilers for Modern Architectures: A Dependencebased Approach[END_REF]. The checking procedure would run both cases and check whether ppr [START_REF] Allen | Optimizing Compilers for Modern Architectures: A Dependencebased Approach[END_REF] produces the same result as it does in the canonical execution. Suppose there is a true dependence from ppr[0] to ppr [START_REF] Allen | Optimizing Compilers for Modern Architectures: A Dependencebased Approach[END_REF], but the absence of a read annotation in ppr [START_REF] Allen | Optimizing Compilers for Modern Architectures: A Dependencebased Approach[END_REF] causes this to be missed at the merge time. The checking procedure would detect an error and stop.

The inductive process checks link[i] and body[i] after checking all previous links and bodies. As in the canonical execution, the algorithm checks the PPRs sequentially in the outer loop and applies a different number of patches in each step of the inner loop. First, it runs body[i] with no prior patches. Then for j = 1, . . . , i -1, it includes the patches of PPR 0 through j. Correctness Proof . Prove by contradiction. If the determinism checking succeeds, but in one of the speculative executions, the output is incorrect. Since all the writes are annotated, there is a read missing. The missing read at ppr[y] and the matching write is in body[x] (x < y). Consider the inner loop at iteration i=y. For all iterations j < x, the execution of ppr[y] does not have the result of body[x]. There will be an error raised. Contradiction to the assumption that the determinism checking has succeeded.

Discussion

Composability of annotations Given the program, if we fix the hints and test for annotation correctness, we have the property that as new annotations are added for later tests, they preserve the correctness of earlier tests. New annotations do not break the correctness of previously passed tests. This property helps to bring down the cost of concurrency error testing to a level closer to sequential error testing.

Composability of annotated code Multiple BOP tasks can be grouped to form a single task the same way sequential tasks are stringed together. In addition, BOP tasks may run with auto-parallelized code, since both have sequential semantics. However, when new parallelism is introduced, e.g. by adding a task or removing a barrier, old access annotations need to be checked for completeness.

Automation Automatic techniques may be used to identify shared data accesses and annotate them using the annotation interface. Such analysis includes type inference as in Jade [START_REF] Rinard | The design, implementation, and evaluation of Jade[END_REF], compiler analysis as in CorD [START_REF] Tian | Supporting speculative parallelization in the presence of dynamic data structures[END_REF], and virtual memory support as in BOP [START_REF] Ding | Software behavior oriented parallelization[END_REF]. A user may use automatic analysis in most of the program and then manually annotate critical loops or functions. The hybrid solution lets a programmer lower the monitoring cost while letting a tool perform most of the annotation work.

Shared vs. private by default Most costs of speculation come from monitoring, checking, and copying shared data. BOP chooses to provide interface to specify shared data access because a user can minimize the monitoring cost by specifying only the data that has to be shared. Furthermore, the user can annotate data by regions rather than by elements, reducing both the number of annotation calls and the size of meta-data that the speculation system has to track and process.

Data access vs. data identity Data identity takes just one annotation per variable. Data access takes up to two annotations per datum per PPR (one per link task). A benefit, however, is the uniform treatment of global and heap data. A declaration-based method would have difficulties regarding dynamic data: heap data often has no static address, the access is often conditional, and the data location is often dynamically computed. Access annotation is also dynamic in that the role of data, whether shared or private, is allowed to change in different program phases. Finally, it is also more precise since the annotation can be inside arbitrary control flow to capture the condition of data access and avoid redundant annotation calls. Access annotation, however is harder to ensure completeness. 2 compares BOP with other annotation schemes: annotation of private data (the rest is shared) as in OpenMP, annotation of shared data as in Treadmarks [START_REF] Amza | Shared memory computing on networks of workstations[END_REF], annotation of shared data access as in DSTM [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], and annotation (registration) of files in distributed version control as in Mercurial. Like DSTM, BOP annotation is based on data access rather than data identity. Unlike DSTM, BOP uses copy-n-merge (Section 2.2), which requires annotation per PPR not per access. In fact, the annotation can be reduced to two per task pair as shown later in an example in Section 5. Because of copy-n-merge, annotations in BOP are entirely local operations. Synchronization happens at the end of a task. BOP is similar to checkin and check-out in distributed version control, which has one copy-in and one copy-out per datum per parallel execution. Unlike check-in/check-out, not all data sharing, i.e. link-link and link-body in Table 1, requires annotation. BOP is also distinct in its safety guarantee and the need for correctness checking as described in this paper.

A comparison Table

Evaluation

Access annotation was used in our earlier paper, which describes the interface (including the ordered block) and the safe implementation of dependence hints [START_REF] Ke | Safe parallel programming using dynamic dependence hints[END_REF]. As mentioned in a paragraph in Section 5.1 Experimental Setup, "BOP provides an annotation interface for recording data access at byte granularity." The interface described in this paper was necessary to parallel seven of the eight tests in that paper. The programs include string substitution (Section 5 of this paper), two clustering algorithms, and five SPEC benchmark programs: art, bzip2, hmmer, parser, and sjeng. The parallel speedup for these programs ranges from 5.8 to a factor of 14 when running on a 16-core machine.

Next we show performance for two of the tests. The first is string substitution, whose parallelization requires byte-granularity annotation. The second is k-means clustering, for which we compare the manual annotation with paging-based monitoring as used in the previous paper [START_REF] Ke | Safe parallel programming using dynamic dependence hints[END_REF]. We also compare with OpenMP, which has no access annotation. OpenMP (or any other non-speculative system) cannot parallelize string substitution.

For demonstration, we test two different multi-core machines: k-means on a machine with two 2.3GHz quad-core Intel Xeon (E5520) processors with 8MB secondlevel cache per processor, and string substitution on a machine with four 2.5GHz quadcore AMD Opteron (8380) processors with 512KB cache per core. Both are compiled by by GCC 4.4 with "-g3". The performance is measured by the speedup over the sequential version of the program and shown in Figure 4.

String substitution

The test program finds and replaces a pattern in 557MB of text, divided into 55,724 PPRs. The sequential run time is 4.4 seconds. Given the small size of each PPR, BOP uses a pool of processes rather than starting a process for each PPR. It uses a manager process to check correctness. When it has no checking work, the manager computes on the next PPR. At a conflict for safe recovery, BOP resumes from the last correct PPR and starts a new process pool.

We test the program with 5 different levels of conflicts: no conflict, 1%, 5%, 10%, and 50% conflicts. With no conflicts, the speed is improved by 94% to a factor of 5.5 with 2 to 9 processors, as shown in Figure 4. The execution time is reduced from 4.4 seconds to 0.8 second. The improvement decreases in the presence of conflicts, as the four other curves show. As expected, parallel performance is sensitive of the frequency of conflicts. The maximal speedup drops to 4.9 for 1% (551) conflicts, to 2.7 for 5% (2653) conflicts, and to 1.8 for 10% (5065) conflicts.

In the case of 50% conflicts, every other PPR fails the correctness check and requires a rollback. The parallel execution is slower by 6% to 19%. It shows the efficiency of understudy-based error recovery in BOP. The original BOP uses page protection for all global and heap data, which includes 640MB for coordinating data, 32MB for storing cluster assignments (both old and new assignments), and 2480 bytes for the centroids. It uses padding to separate the three arrays. To avoid false sharing, it blocks the loop so each PPR computes on 409,600 points and use different memory pages.

The coarse granularity limits the amount of parallelism-there are 190 PPRs, every 19 of them are parallel. As a result, the performance does not increase linearly with the number of processors. For example, a clustering iteration takes about the same amount of time using 8 and 9 processors.

Two access annotations are used, one for the centroid array, and the other for the (new) assignment. It monitors access to 16MB data, 2.3% of total data. The speedup, shown as A-BOP in the figure, is consistently better than BOP, although the difference is less than 10%. The OpenMP version has a higher sequential overhead (4%). It is about the same speed as A-BOP, although at finer granularity, the OpenMP version ran faster. Overall for k-means, the needed annotation is small (2 annotations), the performance is improved over automatic monitoring and comparable to OpenMP.

Related Work

Software speculative parallelization Software speculative parallelization was pioneered by Rauchwerger and Padua [START_REF] Rauchwerger | The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization[END_REF]. While most techniques automatically parallelized doall loops (with limited potential on full applications [START_REF] Kejariwal | On the performance potential of different types of speculative thread-level parallelism[END_REF]), several techniques provided a safe interface for expressing possible parallelism [START_REF] Von Praun | Implicit parallelism with ordered transactions[END_REF][START_REF] Welc | Safe futures for Java[END_REF] and likely dependence [START_REF] Zhai | Compiler and hardware support for reducing the synchronization of speculative threads[END_REF]. BOP used Unix processes to implement parallelism and dependence hints for sequential C/C++ programs [START_REF] Ding | Software behavior oriented parallelization[END_REF][START_REF] Jacobs | Distributive program parallelization using a suggestion language[END_REF]. Process-based systems use the virtual memory protection mechanism, which transparently provides strong isolation, on-demand data replication, and complete abortability. Similar benefits can be realized for threads using the Copy-or-Discard model with compiler and run-time support [START_REF] Tian | Supporting speculative parallelization in the presence of dynamic data structures[END_REF]. Raman et al. presented a software system called SMTX that supports pipelined execution of sequential loops [START_REF] Raman | Speculative parallelization using software multi-threaded transactions[END_REF]. Recently, Feng et al. generalized the model as SpiceC (scalable parallelism via implicit copying and explicit commit) to support either speculative parallelization by default or other types of commits defined by the user [START_REF] Feng | SpiceC: scalable parallelism via implicit copying and explicit commit[END_REF].

The original BOP divides program data into three categories -shared, checked, and likely private -for complete monitoring [START_REF] Ding | Software behavior oriented parallelization[END_REF]. Shared data is monitored at page granularity. Value-based checking is precise and has no false sharing. SMTX uses valuebased checking for all shared data to eliminate the false sharing (at the cost of per-access monitoring and logging) [START_REF] Raman | Speculative parallelization using software multi-threaded transactions[END_REF]. Instead of automatic monitoring, this paper describes an interface for a user to control access monitoring. It shows when annotations are necessary and how to ensure their correctness. A manual interface may leverage user knowledge and enable more efficient and precise monitoring than what is possible with automatic methods alone.

The framework of task isolation and ordered commit has been used to ensure deterministic semantics and eliminate concurrency errors in multi-threaded code. Grace used processes to implement threads to eliminate deadlocks and data races [START_REF] Berger | Grace: Safe multithreaded programming for C/C++[END_REF]. Burckhardt et al. defined isolation and revision types in C# to buffer and merge concurrent data changes in r-fork/r-join threads [START_REF] Burckhardt | Concurrent programming with revisions and isolation types[END_REF]. Determinator was developed as a new operating system that buffers processes and threads in private workspaces and terminates an execution if concurrent data writes are detected [START_REF] Aviram | Efficient system-enforced deterministic parallelism[END_REF]. CoreDet ensured determinism in threaded execution using versioned memory and a deterministic commit protocol [START_REF] Bergan | a compiler and runtime system for deterministic multithreaded execution[END_REF]. The access annotation of BOP may help to make program monitoring more precise and generally applicable in these systems. The concept of executable declaration is applicable, so is the use of error recovery and speculative synchronization.

Scott and Lu gave five definitions of determinism and showed their containment relationships [START_REF] Scott | Toward a formal semantic framework for deterministic parallel programming[END_REF]. A language-level definition is ExternalEvents, which requires that the observable events in two executions be the same. An implementation level definition is Data f low, which requires that two executions follow the same "reads-see-writes" relationship. BOP lets a programmer define external events and relies on speculation to preserve data flow. The combination enables user control over both the semantics and the cost of its enforcement.

Race detection in fork-join parallelism On-the-fly race detection can be done efficiently for perfectly nested fork-join parallelism [START_REF] Mellor-Crummey | On-the-fly detection of data races for programs with nested forkjoin parallelism[END_REF][START_REF] Raman | Scalable and precise dynamic datarace detection for structured parallelism[END_REF]. Callahan and others showed that at the program level, the problem of post-wait race checking is co-NP hard and gave an approximate solution based on dataflow analysis [START_REF] Callahan | Analysis of event synchronization in a parallel programming tool[END_REF]. They used the term canonical execution to mean the sequential execution of fork-join parallel constructs. The post-wait race checking can be done at run time in O(np) time, where n is the number of synchronization operations and p is the number of tasks [START_REF] Netzer | Efficient race condition detection for shared-memory programs with post/wait synchronization[END_REF]. These and other results are summarized in [START_REF] Helmbold | A taxonomy of race detection algorithms[END_REF]. The execution model of BOP is speculative, and the primitives of PPRs and ordered sections are hints and do not affect program semantics. The access annotation in BOP is used both at debugging time and at run time, so it needs the maximum efficiency. BOP gains efficiency from its data sharing model, which is copy-n-merge. As discussed in Section 4, BOP needs at most two annotations per datum per task and does not synchronize at every access. Race checkers, like DSTM mentioned in Section 4, use shared memory and have to monitor all accesses, and except for the recent Tardis system [START_REF] Ji | Tardis: Task-level access race detection by intersecting sets[END_REF], update a shared data structure at each shared-data access [START_REF] Raman | Scalable and precise dynamic datarace detection for structured parallelism[END_REF].

Fig. 1 :

 1 Fig. 1: Illustration of copy and merge: two PPR tasks shown in (a), data copy-on-write during and merge after the parallel execution shown in (b). After a PPR task, its changes are bundled into a patch and used by the merge step.

Fig. 2 :

 2 Fig. 2: The algorithm for semantics checking

Fig. 3 :

 3 Fig. 3: The algorithm for determinism checking

Fig. 4 :

 4 Fig.4: Demonstration of BOP performance. The test of string substitution shows that BOP exploits speculative parallelism in the presence of unknown conflicts. The test of k-means clustering shows that BOP, which monitors select data, reduces the overhead of BOP, which monitors all data, and performs similarly to OpenMP, which does not use speculation or guarantee sequential equivalence. OpenMP cannot parallelize the string substitution.K-means clusteringThe program clusters N points into k clusters iteratively. It starts with k centroids. In each step, it assigns each point to the closest centroid, and recomputes the center of each cluster as new centroids. In this test, we use 8 million points in 20 dimension space, 10 clusters, and 10 iterations. The sequential time is 110 seconds.The original BOP uses page protection for all global and heap data, which includes 640MB for coordinating data, 32MB for storing cluster assignments (both old and new assignments), and 2480 bytes for the centroids. It uses padding to separate the three arrays. To avoid false sharing, it blocks the loop so each PPR computes on 409,600 points and use different memory pages.The coarse granularity limits the amount of parallelism-there are 190 PPRs, every 19 of them are parallel. As a result, the performance does not increase linearly with the number of processors. For example, a clustering iteration takes about the same amount of time using 8 and 9 processors.Two access annotations are used, one for the centroid array, and the other for the (new) assignment. It monitors access to 16MB data, 2.3% of total data. The speedup, shown as A-BOP in the figure, is consistently better than BOP, although the difference is less than 10%. The OpenMP version has a higher sequential overhead (4%). It is about the same speed as A-BOP, although at finer granularity, the OpenMP version ran faster. Overall for k-means, the needed annotation is small (2 annotations), the performance is improved over automatic monitoring and comparable to OpenMP.

Table 1 :

 1 Annotation is needed only for true dependences between body-body and body-link pairs, i < j.

	source, sink	parallel?	data sharing	annotation
	link i, link j	no	direct	none
	link i, body j
	body i, body j	yes	patching	ppr write at i,
	body i, link j			ppr read at j

Table 2 :

 2 Comparison of five annotation schemes.

	data sharing	annotation unit	frequency	safety
	BOP copy-n-merge access annotation	≤ 2 per datum per task	sequential
	private by default	declaration, e.g. OpenMP	1 per variable	no
	shared by default	allocation, e.g. Treadmarks	1 per variable	no
		access, e.g. DSTM	1 per access	transaction
	version control	file, e.g. Mercurial	1 per file	no

In BOP, a bop ppr hint is ignored if encountered inside a PPR task. Nested hints can be supported by assigning a linear ordering of nested tasks[START_REF] Mellor-Crummey | On-the-fly detection of data races for programs with nested forkjoin parallelism[END_REF] and checking them in a way similar to checking non-nested tasks.

Summary

We have presented a new interface for access annotation. As access monitoring becomes programmable, it becomes part of program semantics. This paper provides two techniques to check correctness: canonical execution to ensure sequential semantics and check for missing write annotations, and a quadratic-time algorithm to ensure determinism and check for missing read annotations. In addition, the paper demonstrates efficient and safe parallelization of non-trivial programs. Some of them, string substitution and time skewing, cannot be parallelized by a conventional interface like OpenMP. Others, when parallelized safely, have a similar performance as OpenMP.

The new interface gives a programmer direct control over the cost and precision of access monitoring. Much of the cost can be saved by leveraging user knowledge. It enables a user to control both the semantics and its enforcement. Finally, the interface may be used by an automatic tool, allowing the mixed use of manual and automatic parallelization.


Liangwei Zhu

Jianhai Chen

Qinming He

Dawei Huang

Shuang Wu

ITC-LM: a Smart Iteration-Termination Criterion Based Live Virtual Machine Migration

Keywords: Virtualization, Live migration, Iteration-Termination Criterion, Terminating Conditions

Live migration of virtual machines (VMs) plays an important role in grids, clouds and datacenters, and has become the cornerstone of resource management in virtualized systems. The efficiency of live migration depends on the downtime, total migration time and total transferred data. However, while migrating a memory-intensive VM, XEN/KVM often do many useless iterations of memory copy in order to reach expected downtime which can never be reached, leading to a great deal of useless data transferring and insufferable total migration time. It consumes mass of network bandwidth and CPU resource when transferring memory from one to another node. Hence, a critical task is to determine the optimal time to terminate the copy iteration for live migration. In this paper, we propose a smart iteration-termination criterion based live migration which is termed as ITC-LM, to self adaptively control when to terminate iteration. We have implemented ITC-LM into KVM/QEMU. The improvement is significant, especially when migrate a memory-intensive VM. The experimental results show that, our approach can decrease 50.33% of total transferred data on average without impairing migration downtime.

Introduction

Virtualization technology plays an important role in cloud computing [START_REF] Armbrust | A view of cloud computing[END_REF][START_REF] Fox | Above the clouds: A Berkeley view of cloud computing[END_REF], in which a large number of virtual machines (VMs) are dynamically allocated to multiple physical machines (PMs). Virtualization enables live migration of VMs, which provides a flexible way to relocate VMs from one physical node to another, leading to efficient resource management [START_REF] Wang | Virtualization-based autonomic resource management for multi-tier Web applications in shared data center[END_REF], such as load balancing and power-saving etc.

Live migration of virtual machine is the essential mechanism of virtualization, which is included in all current mainstream virtualization platforms such as KVM [START_REF] Kivity | kvm: the Linux virtual machine monitor[END_REF], XEN [START_REF] Barham | Xen and the art of virtualization[END_REF], VMware [START_REF] Nelson | Fast transparent migration for virtual machines[END_REF], etc. Pre-copy as default live migration method of these platforms is the most popular algorithm of live migration, which first sends VM's memory to the destination host and then resumes VM in it. In order to improve migration performance, some research employs memory compression to reduce the transferred pages during live migration.

However, the efficiency of current live migration methods are not always satisfying, especially in a memory-intensive scenario. Now methods keeps the iterations of copying memory until the downtime is short enough, and if the expected downtime is always too high, it stops memory copy iterations after a fixed number of memory-copy iterations. As a result, these methods usually stop memory--copy iteration too late in memory-intensive scenarios and will consume a lot of network resource of a data center, even resulting in the performance degradation of data center.

Unfortunately, the existing live migration approaches commonly ignore the problem of determination about when to terminate the iterations. In pre-copy, memory is transferred from the source node to the destination node while VM is still running on source. Modified pages which are generated in the iteration are transferred in subsequent iteration. This process based on that the VM remaining dirty pages can converge to a small value. However, there are still lots of remaining dirty pages after multiple iterations when low-bandwidth or VM with a high workload. In other words, more iterations of copy memory cannot decrease the remaining dirty pages and no more benefit to the service downtime.

In this paper, we propose a smart iteration-termination criterion (ITC) based live migration method, termed as ITC-LM. We use ITC value to determine when to terminate the iteration in live migration. Actually, ITC value changes dynamically during the live migration process. In our method, we terminate the iteration when the ITC value is less than a given threshold.

The main contributions of this paper are as follows: First, we proposed a smart ITC-LM technique to decide when to stop iteration during live migration. To the best of our knowledge, our method is the first to consider both the iteration rounds and the convergence of remaining dirty pages.

Second, we have implemented our proposed algorithm in recent stable release of KVM/QEMU [START_REF]Kernel Based Virtual Machine[END_REF][START_REF] Qemu | [END_REF] and show that our methods can be conveniently deployed in virtualization platform.

Eventually, we demonstrate the effectiveness of ITC-LM method in our experiments by four different kinds of workloads. The results show that ITC-LM decreases 53.35% of total migration time and 50.33% of total transferred data on average.

Background and Motivation

There are various algorithms of live migration. Most of these studies are mainly based on the pre-copy live migration algorithm. It basically works [START_REF] Clark | Live migration of virtual machines[END_REF] as follows:

1) The resources of memory and VCPUs are reserved on the destination.

2) Memory of VM is sent to destination and using bitmap to log the dirty pages which rewrite during the memory copy.

3) The source continuously copies VM's memory dirty pages to the destination.

A number of iterations are performed to retransfer the pages which are dirtied in previous iteration. 4) Suspend the running VM at the source, and copy remaining pages to the destination.

5) The VM is resumed on the destination. In the best case, the approach of pre-copy can achieve an expected downtime by several iterative copy operations.

Terminating Conditions

There are some common conditions to decide the time to terminate the iterative copy operations.

Remaining Dirty Pages. Ideally, the default size of remaining dirty pages can be reached using iterative copy operations. However this is completely depending on the assumption of remaining dirty pages can converge expected size. Some application rewrite memory frequency that remaining dirty pages still very large over multiple rounds [START_REF] Jin | Live virtual machine migration with adaptive, memory compression[C]//Cluster Computing and Workshops[END_REF].

Maximum Number of Iterations. The terminative conditions of exact values for the maximum number of iteration are arguable, sometimes when the dirty rate is low compared to the transfer rate, the remaining pages will decrease quickly and down time will not have benefit from more iteration.

Hybrid Terminating Condition. Some of approaches use terminative conditions simultaneously of above two as shown in figure 1. Each iteration check the remaining pages whether below the expected remain pages, and check the number of iteration is more than the maximum number of iterations. This condition has been used in XEN, KVM/QEMU etc.

Fig. 1. A typical algorithm of use two terminative conditions simultaneously

The Problems of Common Terminating Conditions

The hybrid terminating condition can finish the live migration but the default remaining pages size and maximum number of iterations is hard to estimate. Beside, we can know that in order to minimize the size of remaining dirty pages the maximum iterations need to be set to a value that larger enough for most cases of live migration. However, a lot of useless iterations of pre-copy caused large amount of transferred data, especially when migrate a memory-intensive VM. From figure 2 we observe that the remaining pages converge from the fifth iteration. But the remaining dirty pages size still bigger than the default size 30MB (some approaches use remaining pages size divide transfer rate). So iterations of copy will continuous perform until the number of iterations exceeds the maximum number which is set as thirty-seven that larger enough for most cases of live migration in our experiments.

Algorithm Design

Although, the live migration complete after number of iteration exceeds the maximum number, the more iteration the more network bandwidth and CPU resource it consumes and it would prolong the total migration time. Moreover, it makes applications in migrated VM suffer longer time of performance degradation. The iterations of pre-copy are completely depending on the assumption of the remaining pages can converge to a small value. However iteration of pre-copy may never converge to a small value or even the convergence of iteration never happen when the VM's workload is high or bandwidth instability. So there should be some smart threshold to force the final iteration of a live migration which does not converge.

Terminating Condition Based on Remaining Dirty Pages

First, some notations are defined as follows:

i r M : The remaining dirty pages after ith iteration in the migrated virtual machine.

i t M : The data is transferred to destination of ith iteration. The average dirty page rate of ith iteration can be calculated as

i t r r page T M M M R i i i i ) ( 1     .
(

) 1
The average transferred rate of ith iteration can be presented as:

i t tran T M R i i  . ( 2
)
Only when

i tran R is greater than i page R
, the iteration can reduce the remaining pages. From formula (1) and ( 2) we can get:

1   i i r r M M . (3)
Different between two consecutive remaining pages is defined as:

1    i i i M D . ( 4
)
The above inequality indicates the remaining pages should be less than its previous round. Thus the iteration can reduce the remaining page size. Otherwise the rounds have no contribution to reach to the default value.

From formula (4), it is clear that when D i is not less zero is a good terminative condition. However, VM's dirty page rate and transfer rate are not stable in real virtualized system, thus once we find it unreliable that the remaining dirty pages is less than its previous one. The experiments choose benchmark of RUBiS as workload for each VM memory size. In order to see clear the trend of remaining dirty pages, the first iterations are taken off from the figures. The default remaining dirty pages set as 30MB and maximum iterations is thirty-seven (a number that larger enough for most cases of live migration).

Figure 3 illustrates the remaining dirty pages fluctuate during iterations and pages will continue to reduce after a shock. In detail, if only use the condition of difference between two successive remaining dirty pages will terminate the iteration at the first shock points (see the point of a and c in Figure 3). However the remaining dirty pages will continuously decrease after these points (see the point of b and d in Figure 3).

Iteration-termination Criterion

Based on the analysis of the iterative characteristics in the VM live migration, the key idea of the proposed method is to avoid directly terminating iterations when the remaining dirty pages do not decrease. So we give a smart iteration-termination criterion (ITC) based live migration method, termed as ITC-LM. In our method, we use ITC value to accumulative the variation tendency of remaining dirty pages and determine when to terminate the iteration in live migration. The value of ITC is relation to the difference of remaining pages between two consecutive iterations.

According to the variation of the remaining pages of iterations, if the remaining pages of current iteration are less than the previous one, then we add a trust value to ITC. The bigger ITC value means the more valuable to do iterations. On the contrary, if the remaining pages of current iteration are not less than the previous one, it means doing iterations has no benefit for reducing downtime, and then we cut down ITC value by dividing ITC value to a distrust coefficient which is used to constraint the rate of ITC descent.

We conclude ITC by formula (5) as follows.

distrust c ITC trust c ITC ITC _ / ) 1 ( ) _ (       , ( 5
)
Where

 is a 0-1 constant,       0 , 0 0 , 1 i i D D  , trust c _

Downtime.

In order to evaluate the influence of ITC-LM on downtime, experiments are performed with two memory size: 1GB and 2GB. Figure 5 (c) and(d) shows ITC-LM can get a good performance in total transferred data and total migration time while has slight influence on the downtime of live migration. This is because ITC-LM based on a smart threshold not a default remaining dirty pages or maximum iteration rounds.

Related Work

The technology of live migration is widely used in virtualization. At present, there are several types of live migration methods. The pre-copy approach is a main migration method in the mainstream virtualization platform such as KVM [START_REF] Kivity | kvm: the Linux virtual machine monitor[END_REF], XEN [START_REF] Barham | Xen and the art of virtualization[END_REF], VMware [START_REF] Nelson | Fast transparent migration for virtual machines[END_REF], etc. Some research has been done to improve the performance of live migration based on pre-copy in which the widespread used method is memory compression. Zhang et al. [START_REF] Zhang | Exploiting data deduplication to accelerate live virtual machine migration[END_REF] proposed a novel approach MMD to find identical and similar memory pages to redundant memory data. Delta compression technique [START_REF] Svä Rd | Evaluation of delta compression techniques for efficient live migration of large virtual machines[C]// Virtual Execution Environments (VEE)[END_REF] applied XOR on the current pages with kept previously sent pages in source host. Jin et al. [START_REF] Jin | Live virtual machine migration with adaptive, memory compression[C]//Cluster Computing and Workshops[END_REF] designed an adaptive memory compression based on memory page characteristics. ME2 [START_REF] Ma | ME2: Efficient Live Migration of Virtual Machine with Memory Exploration and Encoding[C]//Cluster Computing (CLUSTER)[END_REF] identified useful pages and then used RLE algorithm to compress data. Page rewriting frequency is related to dirty page rate. Microwiper [START_REF] Du | Microwiper: Efficient Memory Propagation in Live Migration of Virtual Machines[END_REF] ordered dirty memory pages according their rewriting rate. Petter et al. [START_REF] Svard | High performance live migration through dynamic page transfer reordering and compression[C]//Cloud Computing Technology and Science (CloudCom)[END_REF] designed a page priority map on top of the dirty page bitmap and proposed dynamic page transfer reordering based on it. CR/TR-Motion [START_REF] Liu | Live virtual machine migration via asynchronous replication and state synchronization[END_REF] log execution trace on source and replay it on target host. Chiang et al. [START_REF] Chiang | Introspection-based memory de-duplication and migration[C][END_REF] proposed a bootstrapping VM introspection technique to get the information of memory pool, and skips free memory pages during migration. Jo et al. [START_REF] Jo | Efficient live migration of virtual machines using shared storage[C][END_REF] first sent the memory-to-disk mapping to the host, and then fetch the contents directly from the shared storage.

Post-copy [START_REF] Hines M R, Deshpande | Post-copy live migration of virtual machines[END_REF] resumes running VM on the target host with only its CPU state before copying the VM's memory from source host to target. Adaptive pre-paging and dynamic self-ballooning [START_REF] Hines M R, Gopalan | Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning[END_REF] can improve the post-copy performance. Hirofuchi et al. [START_REF] Hirofuchi | Enabling instantaneous relocation of virtual machines with a lightweight vmm extension[END_REF] through a lightweight extension implement post-copy to KVM. Besides, some researches proposed hybrid live migration [START_REF] Sahni | A Hybrid Approach to Live Migration of Virtual Machines[C]//Cloud Computing in Emerging Markets (CCEM)[END_REF][START_REF] Shribman | Pre-Copy and post-copy VM live migration for memory intensive applications[END_REF][START_REF] Chen | Live migration of virtual machines based on hybrid memory copy approach[END_REF] approach that use pre-copy and post-copy methods simultaneously. They do some memory copy iteration of precopy before the stage of post-copy method.

7

Conclusions and Future Work

In this paper, we have presented the design and implementation of a smart ITC-LM technique for live migration of virtual machines. We choose four representative server applications in modern data center to verify our algorithm. The results show that ITC-LM has a good performance in different kinds of workload. In future work, we will study trust value and distrust coefficient of ITC-LM to make our approach more effective. Furthermore, we will implement our approach to other virtualization platforms.

Fig. 2 .

 2 Fig. 2. Number of remaining dirty pages and transferred data of each migration iteration rounds when migrate a VM which running workload of RUBiS webserver workload. VM size is 2GB.

iT:::

  The time of complete ith iteration used. The average dirty pages rate of ith iteration. The average transferred rate of ith iteration.

Fig. 3 .

 3 Fig.3. Remain dirty pages in successive iterations. The experiments choose benchmark of RUBiS as workload for each VM memory size. In order to see clear the trend of remaining dirty pages, the first iterations are taken off from the figures. The default remaining dirty pages set as 30MB and maximum iterations is thirty-seven (a number that larger enough for most cases of live migration).

  then we obtain a good performance of live migration in our experiments and we will do more research about values of

Fig. 4 .Fig. 5 .

 45 Fig. 4. Remaining dirty pages of each iteration compared with ITC-LM and Pre-default for each workload. (Memory 1GB) Total Transferred Data. Figure 4 respectively shows the each iteration remaining data of during live migration of VM running. The iteration rounds of ITC-LM far less than the pre-copy default algorithm in KVM/QEMU under the workload of kernelcompile, SPECjbb and RUBiS. As figure 4 (b) shows the benchmark of NPB-EP is a compute-intensive workload and VM produce less dirty pages, and iteration ending soon. Thus two approaches both in less iteration.Experimental results in figure5(a) show that compare with KMV/QEMU's default migration algorithm, ITC-LM can reduce total transferred data 50.73%, 7.74%,69.55%,73.29% respectively in diverse workload of above, an average of 50.33%. This will lighten greatly network loads of data center.Total Migration Time. The results in figure5(b) show that benefit from less iteration, ITC-LM can reduce total migration time 50.54%, 17.70%, 70.03%,75.14%, an average of 53.35%. For this, the service running in live migration VM can suffer less time of the decrease of quality.

Acknowledgments

This work was partly supported by the National Key Technologies R&D Program under Grants No. 2011BAD21B02

ITC-LM Algorithm

We have designed the ITC-LM Algorithm and implemented it in recent stable release of KVM/QEMU using ITC. QEMU is an open source machine emulator. KVM (for Kernel-based Virtual Machine) is a full virtualization solution for Linux on x86 hardware which containing virtualization extensions. When QEMU use KVM for its virtualization acceleration, can get a better performance. The major part of ITC-LM was implemented in QEMU. We use bitmap of memory to calculate the size of dirty pages. The pseudo code of ITC-LM algorithm is listed in follows:

Evaluation

In this section, we perform a series of live migration experiments with some various characteristic workloads on VM with varying working set sizes to evaluate the performance of ITC-LM algorithm by comparing with QEMU/KVM default pre-copy algorithm (Pre-default) which implemented hybrid terminating condition. In the following, we first introduce the experimental environment, and then we present the results of different benchmarks.

Experimental Environment

All live migration experiments are performed on two identical hosts as source and destination host respectively. Each host has dual Intel(R) Xeon(R) CPU E5606 @ 2.13GHZ with a total of eight cores. Each one has 16GB RAM. The host runs Ubuntu 12.04LTS with KVM module and QEMU-1.4.0. The source and destination hosts are connected via Gigabit switched Ethernet. The OS of Linux VM are all Ubuntu12.04LTS with Kernel-3.2.0 and all VM images are stored in a Network File System (NFS). We perform experiments VMs are configured with two virtual CPUs.

In each experiment the nodes of source and target only run the live migration VM. Besides, we use another identical host to deployment the client emulator of RUBiS.

Overview of Workload

We perform our experiments with the following VM workloads: 1. Kernel-complication. Linux kernel compilation is a balanced workload to use the source of VM. Two parallel threads were used to run Linux 3.8.5 kernel [START_REF]Linux-kernel[END_REF] compilation. 2. Parallel Benchmarks. The NAS parallel benchmarks (NPB) [START_REF]NAS Parallel Benchmarks[END_REF] are a set of programs which evaluate the performance parallel performance, available in commonly-used programing models like MPI and OpenMP. In our experiments, we use Embarrassingly Parallel (EP) of NPB (NPB-EP) to simulation the parallel computing workload. 3. SPEC jbb2005 [13]. It is a SPEC'S benchmark for evaluating the performance of server side java. It provides enhanced workload with a more object-oriented manner to reflect real-world applications. 4. Dynamic web Server. Rice University Bidding System (RUBiS) [START_REF]RUBiS[END_REF] which is a prototype modeled after eBay.com used to evaluate patterns and application servers performance. It contains a client-browser emulator, and we implement it in a third physical host.

Experiment Results

In this section, the results from the four workloads are present. The evaluation metric of experiments primarily includes total migration time, total transferred data and downtime during live migration of virtual machine. We run live migration five times for each workload and use the arithmetic mean for each metric.