Tao Zhang
email: tao.zhang@sjtu.edu.cn

Xiaohui Pan
email: panxiaohui@shupl.edu.cn

Wei Shu
email: shu@sjtu.edu.cn

Min-You Wu

Asymmetry-Aware Scheduling in Heterogeneous Multi-core Architectures

Keywords: Scheduling, Heterogeneous, Asymmetric, Multi-core

As threads of execution in a multi-programmed computing environment have different characteristics and hardware resource requirements, heterogeneous multi-core processors can achieve higher performance as well as power efficiency than homogeneous multi-core processors. To fully tap into that potential, OS schedulers need to be heterogeneity-aware, so they can match threads to cores according to characteristics of both. We propose two heterogeneity-aware thread schedulers, PBS and LCSS. PBS makes scheduling based on applications' sensitivity on large cores, and assigns large cores to applications that can achieve better performance gains. LCSS balances the large core resource among all applications. We have implemented these two schedulers in Linux and evaluated their performance with the PARSEC benchmark on different heterogeneous architectures. Overall, PBS outperforms Linux scheduler by 13.3% on average and up to 18%. LCSS achieves a speedup of 5.3% on average and up to 6% over Linux scheduler. Besides, PBS brings good performance with both asymmetric and symmetric workloads, while LCSS is more suitable for scheduling symmetric workloads. In summary, PBS and LCSS provide repeatability of performance measurement and better performance than the Linux OS scheduler.

Introduction

Multi-core processors have become mainstream since they have better performance per watt and larger computational capacity than complex single-core processors. To efficiently utilize on-chip resource, recent research [13] [15] [17] advocates heterogeneous (or asymmetric) multi-core architectures consisting of a combination of cores with different computational capabilities. These processors are attractive because they have the potential to improve system performance, to reduce power consumption [START_REF] Kumar | Single-isa heterogeneous multi-core architectures for multithreaded workload performance[END_REF], and to mitigate Amdahl's law [START_REF] Hill | Amdahl's law in the multicore era[END_REF]. Since a heterogeneous multi-core architecture consists of a mix of different cores, it can better cater for heterogeneous workloads [START_REF] Balakrishnan | The impact of performance asymmetry in emerging multicore architectures[END_REF]. People could execute cpu-intensive threads on fast cores and memory-intensive threads on slow cores to achieve better energy efficiency.

The heterogeneity of such architectures can be classified into three levels: high, medium and low. A high-heterogeneity processor consists of cores of different instruction set architectures. A typical example is AMD FUSION APU [20] which incorporates CPU cores and GPU(Graphics Processing Unit) cores. A medium-heterogeneity processor integrates cores of overlapping instruction set architectures, such as IBM CELL [21]. A Cell processor contains a power processor element (PPE) with several synergistic processor elements (SPEs). Finally, a low-heterogeneity processor contains cores of same instruction set architectures but different performances. Such cores are called fast and slow cores [16], or big and small cores [17] in previous study.

Despite their benefits in energy and performance, heterogeneous architectures pose significant challenges on the design of operating systems or programming environments, which has traditionally assumed homogeneous hardware [17]. A key challenges is scheduling [7]. Current parallel programming environments such as MIT Cilk [START_REF] Blumofe | Cilk: An efficient multithreaded runtime system[END_REF], Cilk++ [START_REF] Leiserson | The Cilk++ concurrency platform[END_REF], OpenMP [START_REF] Ayguade | The design of openmp tasks[END_REF], and the default Linux OS scheduler [7] still assume all cores provide equal performance (Asymmetry-unaware). As a result, the default linux scheduler will schedule these threads in a random fashion, resulting in non-optimal performance [7] [16] [22]. In general, there are two issues: the scheduling is not optimal; system repeatability is low. Different run of the same application(s) has different performance. This phenomenon is called completion time jitter [22].

This paper presents Preference Based Scheduling (PBS) and Large Core Splitting Scheduling (LCSS) for arranging multiple multi-threaded applications on heterogeneous multi-core systems. LCSS is simpler and requires no scheduling hints, but less effective. On the contrary, PBS needs application preference to make scheduling decisions, and improves application performance more significantly than LCSS. Overall, the two proposed scheduling schemes improve performance and repeatability of application performance measurement over the Linux scheduler.

Preference Based Scheduling (PBS)

Application Preference

We define application preference as the degree of performance improvement as it receives more large cores. In general, asymmetry-aware schedulers should allocate more large cores to high-preference applications, and more small cores to lowpreference applications. More specifically, we define the speedup of running an application (all its threads) on large cores compared to half large, half slow cores as α, and define the speedup of running an application (all its threads) on half large, half slow cores compared to slow cores as β, then:

-An application has a high-preference if α and β are big and almost identical.

-An application has a low-preference if α is much larger than β.

-An application has a medium-preference if it falls between high-preference and low-preference.

Correlation between Application Preference and Fork-join

From the applications in PARSEC benchmark, we observed correlation between application preference and its fork-join structures. Applications in highpreference category and low-preference have only one fork-join structure. However, they distinguish from each other by the execution time of the sequential part versus the parallel part. For high-preference applications, the sum of sequential part takes longer time than the parallel part. Given more large fast cores, the performance of high-preference applications increases proportionally. On the contrary, for low-preference applications, the parallel part dominates the total execution time of each application. Therefore, application performance is limited by the slowest thread in the parallel phase. Applications in this category can not benefit significantly when receiving more large cores. On the other hand, the medium-preference applications have multiple fork-join structures. Therefore, their performance is limited not only by the slowest thread in each parallel phase, but also by the sequential phase. In general, their performance sensitivity for number of large cores is between high-preference and low-preference category. Let α be the summed time of all sequential parts of an application, and β be the summed time of all parallel parts, then we have an alternative definition of application preference:

-An application has a high-preference if it has only one fork-join structure, and α ≥ β. -An application has a low-preference if it has only one fork-join structure, and α < β. -An application has a medium-preference if it has multiple fork-join structures.

Preference Based Scheduling

Preference Based Scheduling(PBS) allocates processor core resource to application threads according to their preference. Application threads with higher preference have higher priority for large cores. A complete scheduling scheme should contain a policy for initial assignment, a policy for wake up assignment and a policy for load balancing [16]. In this work, we consider the case that the total number of application threads (in contrast to system threads) does not exceed the number of cores. High performance computing is such a case that there is at most 1 application thread running on each core.

Input:

The set of all large cores in a system: C = {l 1 , l 2 , ..., l k1 } Input: The set of all small cores in a system: S = {s Preference Based Assignment(PBA) Policy : The policy assigns cores to threads based on the application's preference. Threads within an application inherit its preference. Large cores are assigned to threads with the highest preference, one to each thread. In case there are large cores available, but the remaining applications all have the same preference, then this policy works in First Come First Serve(FCFS) fashion. That is, the first application in task queue receives large cores, then the second application, and so on. The detailed process is described in Algorithm 1.

if Q > 0 then 20 for each a i ∈ A do 21 X = U T hreads(a i ); 22 assign X small cores U to a i ; 23 S = S -U ; 24 A = A -{a i };

Wake up on Previous Core (WPC) Policy

: When a thread is woken up, it is assigned to the core on which it was previously running. In case that core is occupied by a new thread, then the new thread is migrated to another core following the load balancing rule explained in Algorithm 2.

Input:

The set of idle large cores in a system: C Input: The set of idle small cores in a system: S Input: The set of applications to schedule: A = {a 1 , a 2 , ..., a N }. Input: A vector recording current core occupation status: which core is used by which thread of which application 1 Func. UThreads(a i ): return the number of unscheduled threads of a i ; 2 Func. SThreads(a i ): return the number of threads of a i that running on small cores; 3 Func. LThreads(a i ): return the number of threads of a i that running on large cores; Preference Based Balancing (PBB) Policy : When performing load balancing, large cores will be assigned to threads with the highest preference. In case remaining applications have a same preference, PBB assigns large cores in First Come First Serve manner, just like the preference based assignment(PBA) policy. This policy ensures: large cores are always busy as long as there are applications; high preference application receives priority in getting large cores. Load balancing with the PBB policy is made in two steps. The first step constructs a new thread to core mapping according to Algorithm 2. The second step is to migrate old threads or assign new threads onto cores to reach that mapping.

Q = U T hreads(a i ) + ST hreads(a i ); 10 if Q > 0 then 11 if |C| > Q then 12 allocate Q large cores U to a i ; 13 C = C -U ;

Large Core Splitting Scheduling (LCSS)

Large Core Splitting Scheduling (LCSS) tries to distribute large cores among multi-thread applications equally. It is designed to be simple and provide a modest performance.

Thread Assignment Policy

Large Core Splitting Assignment (LCSA): Given K large cores in a system, then N applications will get K/N large cores each unless an application has less than K/N threads. In that case, spare large cores will be distributed equally among the rest applications. The scheduling algorithm will allocate one core for each thread.

Wake up Assignment Policy

Wake up on Previous Core (WPC) Policy : When a thread is woken up, it is assigned to the core on which it was previously running. In case that core is occupied by a new thread, then the new thread is migrated to another core.

Load Balancing Policy

Large Core Splitting Balancing (LCSB) Policy : This policy maintains the evenly distribution of large cores among applications through adjusting the number of large cores of each application. The load balancing is done in two steps. The first step is to construct a new thread to core mapping. The second step is to migrate old threads or assign new thread onto cores to reach that mapping.

Experimental Methodology

Simulation Methodology

We use the Gem5 simulator to construct various heterogeneous systems of desired heterogenity. The Gem5 simulator is an event-driven architecture simulator with proved accuracy [9]. We simulate two types of cores, large and small. A large core (L) is an Out-of-Order, 7-stage pipeline core while a small core (S) is a simple In-order core. Each core has a 32KB i-cache and a 64KB d-cache, both 2-way associative. All cores share an 8-way associative 2MB L2 cache. All caches use 64 byte lines. There is 4GB external memory. The performance of a large core is roughly twice of a small core. The area of a large core is around 2.5× that of a small core. And we use three heterogeneous multi-core architectures of roughly the same area: 8 large cores and 8 small cores (8L8S), 6 large cores and 13 small cores (6L13S), and 4 large cores and 18 small cores (4L18S).

Gem5 simulator supports full-system simulation which runs a commodity OS and user applications on the simulator. We ran Linux 2.6.27 on the simulator. Besides, we modified and integrated the Clavis tool [14] to control the Linux scheduler to follow our scheduling schemes.

Workload

We use combinations of applications from the PARSEC benchmark [8] to test our system. The workloads are described in Table 1.There are applications of high, low and medium preference with or without the supplement data. Canneal, Freqming, and Dedup are memory intensive, computation intensive, and communication intensive, respectively. We assign explicit value 3, 6, 9 to low, medium, and high preference, respectively. In addition, we assign value +1, -1, -1 to computation intensive, communication intensive, and memory intensive, respectively. The initial value of application preference and the supplement data are then summed to get a final preference value. In summary, the BF and BB are asymmetric workloads since the two applications in BF or BB have an difference of 3 in preference value. However, the BS and DC are symmetric workloads because applications in BS or DC have identical preference value. Finally, the CF is a weakly asymmetric workload since Canneal and Freqmine have an difference of 2 in overall preference value. All applications are 8 threaded, and their order in the "description" column indicates their order in task queue. For example blackscholes sits before freqmine in task queue.

Performance Comparison Metric

We use the makespan of all applications as the performance metric. We also perform repeatability test to ensure the correctness of our results. Since application performance with LIN varies from one run to another, we use the average performance of at least 5 runs with LIN in comparison. The performance of PBS, LCSS and Linux OS scheduler (LIN) will be compared.

Results

Evaluation on Repeatability

To evaluate the repeatability of application performance with PBS and LCSS, we ran the BF and BS workloads for multiple times with PBS and LCSS scheduler respectively, and recorded their execution time. Figure 1 shows the results.

For both schedulers, all the execution time is generally within {97%, 103%} of the average execution time. There are many reasons that could cause this variation of execution time. For example, the difference in scheduling activity, the stochastic interaction between threads, and the interference of system threads (in OS) to application threads. Considering the relative small percent (6%) of time variation, we think that PBS and LCSS provide acceptable repeatability for application performance.

Performance Comparison of schedulers

The performance of PBS, LCSS and LIN scheduling schemes on three heterogeneous architectures are presented in Figure 2, Figure 3, and Figure 4, respectively. Overall, PBS outperforms LIN by 13.3% on average and up to 18%. LCSS has a speedup of 5.3% on average and up to 6% over LIN. LIN lead together in another 2 cases. Finally, LCSS win the remaining 1 case. For asymmetric workloads BF, BB and weakly asymmetric workload CF, PBS always achieves the best performance. PBS still works best on the asymmetric workload BS. However, LCSS Outperforms PBS on the asymmetric workload DC.

In summary, PBS is more efficient for asymmetric and weakly asymmetric workloads, while LCSS and LIN are more suitable for symmetric workloads. In some cases, PBS performs better or equally with LCSS on symmetric workloads. As the number of large cores decreases, the platform becomes more and more homogeneous, thus the performance difference among schedulers becomes less prominent.

Effectiveness of the Load Balancing Policies

To evaluate the effectiveness of the load balancing policies, we compared the performance of PBS and LCSS with and without load balancing, as shown in Figure 5 and Figure 6 respectively. The execution time is the average on three architectures(8L8S, 6L13S, 4L18S). Without load balancing, threads generally run to completion on initially allocated cores, possibly leaving large cores idle and lowering system performance. In Figure 6, not surprisingly, performance of all workloads gets better with load balancing. The essentially balanced resource assignment of the LCSS is non-optimal for asymmetric workloads, and load balancing is a remedy. This is illustrated by the substantial improvement with load balancing on the BF and BB workload. On average, employing load balancing improves the performance by 9.2%, which includes the thread migration cost. For the BF workload, the performance of LCSS was improved by 14.4% with core reallocation.

In Figure 5, on average, core reallocation improves the performance by 9.9%, including the thread migration cost. For the DC workload, the performance was improved by 26.3%. Although the average improved performance is close to LCSS's, there are some differences. For LCSS, all five workloads were improved by around 9%. However, for PBS, the DC workload was improved by 26.3% while the other four workloads were improved by less than 7%. This means that LCSS has a larger space to improve after the initial thread assignment. Since the average performance of the PBS algorithm is better than LCSS (see Figure 2, Figure 3, and Figure 4), we can conclude that the initial thread assignment of PBS is better than LCSS on the BF, BB, and CF workloads.

Effective task scheduling algorithms are essential for multi-thread applications to make good use of heterogeneous multi-core architectures. Many previous work use DVFS to emulate heterogeneous multi-core systems [7] [10] [15] [16]. They tune the frequencies of cores to get different numbers of large/fast and small/slow cores, and they keep a constant total number of cores in a system. On the contrary, our simulated system consists of large Out-of-Order cores and small In-Order cores, thus having larger micro-architecture differences (eg. heterogeneity). Besides, our system keeps a constant area while the number of cores varies. Our heterogeneous system is similar to that in [17] [18].

Many studies on scheduling in heterogeneous multi-core systems focus on achieving high system throughput by balancing the hardware resources (e.g., cores, caches) among different applications [START_REF] Kumar | Single-isa heterogeneous multi-core architectures for multithreaded workload performance[END_REF] [16] [17] [18] [19]. They make scheduling decision based on runtime profiling/monitoring. Becchi's IPC driven algorithm [18] periodically samples threads' instructions per cycle (IPC) on cores of both types and gives threads that have a higher fast-to-slow IPC ratio priorities in running on the fast cores. Kumar et al. [START_REF] Kumar | Single-isa heterogeneous multi-core architectures for multithreaded workload performance[END_REF] proposes a similar technique, except that he uses more than one sample per core type per thread to improve accuracy. Lakshminarayana et al. [16] proposes age-based scheduling to schedule the threads with larger remaining time to fast cores. The remaining time of threads is predicted at runtime. Koufaty et al. [17] proposes a bias scheduling which matches threads to the right type of cores through dynamically monitoring the bias of the threads in order to maximize the system throughput.

There are some existing scheduling schemes that make no runtime profiling/sampling. Li et al. [7] designed a heterogeneity-aware scheduler for Linux, AMPS, that makes sure the load on each core is proportional to its power and that fast cores are never under-utilized. AMPS needs no scheduling hints, just as our LCSS. However, AMPS does not guarantee optimal performance. For example, it may run a memory-intensive thread on a fast core and lose efficiency. Shelepov et al. [10] proposed HASS that also puts more load on faster cores, but makes this decision based on the offline architectural signature of threads. The architectural signature includes thread information such as cpu-intensive versus memory-intensive, cache miss-rate and so on. This information is generated offline and provided to the scheduler as a hint before scheduling. Similarly, our PBS scheme requires estimated or offline profiled information as scheduling hints, named application preference. Application preference reflects its ability to boost performance through more and more large, fast cores. Our experiment results show that PBS has better performance over LCSS and Linux scheduler.

Conclusion

We proposed the PBS and LCSS scheduling schemes to map symmetric and asymmetric workloads efficiently onto heterogeneous architectures. LCSS employs the Large Core Splitting (LCS) idea and aims to balance the large core resource among applications. In contrast, PBS adopts the Preference Based Scheduling policy and aims to assign large cores to applications that can achieve greater performance improvement. LCSS is simpler, and needs no scheduling hints. PBS requires scheduling hints, and provides more significant performance improvements over the Linux OS scheduler. Both scheme ensure that the large cores are always busy unless there are insufficient tasks. Besides, LCSS and PBS guarantee repeatability that the Linux OS scheduler can not provide.

The experiment results show that PBS and LCSS provide better performance than Linux OS scheduler with asymmetric and symmetric workloads on different heterogeneous architectures. Overall, PBS outperforms Linux scheduler by 13.3% on average and up to 18%. LCSS has a speedup of 5.3% on average and up to 6% over Linux scheduler. The results also manifest that PBS can work with both asymmetric, weakly asymmetric and symmetric workloads, although the speedup with asymmetric or weakly asymmetric workloads is bigger. On the contrary, LCSS is more suitable for symmetric workloads. Although we presented only the results for two applications running together, our algorithms are applicable to more than two applications.

1 :

 1 Preference Based Assignment (PBA) policy

2 :

 2 0 and j > i do 20 P = LT hreads(a j );21 if P > 0 then 22 X = P > Q?Q : P ; 23 give a j 's X large cores to a i ; 24 Q = Q -X; each a i ∈ A do 32 X = U T hreads(a i );33 assign X small cores U to a i ; 34 S = S -U ; 35 A = A -{a i }; Preference Based Balancing (PBB) Policy

Fig. 1 .Fig. 2 .

 12 Fig. 1. Evaluation of Repeatability

Fig. 3 .SchedulerFig. 4 .

 34 Fig. 3. Execution Time on 6L13S

Fig. 6 .

 6 Fig. 5. PBS Load Balancing

13 else 14

  1 , s 2 , ..., s k2 } Input: The set of applications to schedule: A = {a 1 , a 2 , ..., a N }

	1 Func. UThreads(a i ): return the number of unscheduled threads of a i ;
	2 if a 1 .pref erence = a 2 .pref erence = ... = a N .pref erence then
	3	Assign large cores to threads in first come first serve manner
	4 else 5 Q = 6 while C ̸ = ϕ and Q > 0 do ∑ N i=1 U T hreads(a i );
	7	find a j ∈ A with the highest preference;
	8	X = U T hreads(a j );
	9	if |C| ≥ X then
	10	assign X large cores U to a j ;
	11	C = C -U ;
	12	A = A -{a j };

assign C to a j ; 15 C = ϕ; 16 end 17 update Q; 18 end 19

  Sort A in descending order of a i .pref erence;

	8	for i=1,..,N do
	9

4 if a 1 .pref erence = a 2 .pref erence = ... = a N .pref erence then 5 Assign large cores to threads in first come first serve manner; 6 else 7

Table 1 .

 1 Experiment Workloads

	Workloads Description	Preference	Supp. Data	Symmetry
	BF	Blackscholes and Freqmine Low + high	N.A.	Asymmetric
	BB	Bodytrack and Blackscholes Medium + Low N.A.	Asymmetric
	CF	Canneal and Freqmine	High + High	Mem. + Commp. Weakly Asymmetric
	BS	Blackscholes and Swaptions Low + Low	N.A.	Symmetric
	DC	Dedup and Canneal	High + High	Commu. + Mem. Symmetric

  7. Li, T., Baumberger, D., Koufaty, D. A., Hahn, S.: Efficient Operating System Scheduling for Performance-Asymmetric Multi-Core Architectures. Zhuravlev, S., Blagodurov, S., Fedorova, A.: Addressing shared resource contention in multicore processors via scheduling. In: Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (2010) 12. Luk, C. K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V. J., Hazelwood, K.: Pin: Building customized program analysis tools with dynamic instrumentation. In: Programming Language Design and Implementation(PLDI)(2005) 13. Saez, J.C., Shelepov, D., Fedorova, A., Prieto, M.: Leveraging workload diversity through OS scheduling to maximize performance on single-ISA heterogeneous multicore systems. Journal of Parallel and Distributed Computing(JPDC)(2011) 14. Blagodurov, S., Fedorova, A.: A. User-level scheduling on NUMA multicore systems under Linux. In: Linux Symposium (2011) 15. Chen, Q., Cheny, Y., Huangy, Z., Guo, M.: WATS:Workload-Aware Task Scheduling in Asymmetric Multi-core Architectures. In: EEE 26th International Parallel &Distributed Processing Symposium(IPDPS), IEEE (2012) 16. Lakshminarayana, N., Lee, J., Kim, H.: Age based scheduling for asymmetric multiprocessors. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (2009) 25-36 17. Koufaty, D., Reddy, D., Hahn, S.: Bias scheduling in heterogeneous multi-core architectures. In: Proceedings of the 5th European conference on Computer systems(EuroSys'10), ACM (2010) 125-138 18. Becchi, M., Crowley, P.: Dynamic Thread Assignment on Heterogeneous Multiprocessor Architectures. In: Proceedings of the 3rd Conference on Computing Frontiers, ACM (2006) 19. De Vuyst, M., Kumar, R., Tullsen, D.: Exploiting unbalanced thread scheduling for energy and performance on a cmp of smt processors. In: IEEE International /www.amd.com/us/Documents/48423 fusion whitepaper WEB.pdf 21. Kahle, J.A., Day, M. N., Hofstee, H. P., Johns, C. R., Maeurer, T. R., Shippy, D.: Introduction to the Cell Multiprocessor. IBM J. Research and Development 49(4/5) (2005) 589-604 22. Fedorova, A., Vengerov, D., Doucette, D. : Operating System Scheduling On Heterogeneous Core Systems. In: First Workshop on Operating System Support for Heterogeneous Multicore Architectures (2007)

									In: Proceedings
	of the 2007 ACM/IEEE Conference on Supercomputing(SC'07). ACM (2007)
	8. Bienia, C.: Benchmarking Modern Multiprocessors. Ph.D. Thesis, Princeton Uni-
	versity (2011)
	9. Binkert, N., Beckmann, B., Black, G., Reinhardt, S. K., Saidi, A., Basu, A., H-
	estness, J., Hower, D. R., Krishna, T., Sardashti, S., Sen, R., Sewell, K., Shoaib,
	M., Vaish, N., Hill, M. D., Wood, D. A.: The gem5 simulator. SIGARCH,Computer
	Architecture News 39 (2011) 1-7
	10. Shelepov, D., Saez, J. C., Jeffery, S.: HASS: a Scheduler for Heterogeneous Multi-
	core Systems. ACM Operating System Review 43(2) (2009)
	11. Parallel and Distributed Processing Symposium(IPDPS'06), IEEE (2006) 10-20
	20. Brookwood,	N.:	Amd	fusion	family	of	apus	C	enabling
	a	superior,	immersive	pc	experience.		AMD	white	paper,
	http:/

Acknowledgment

The authors would like to thank Linghe Kong, Sandy Harris and anonymous reviewers for their fruitful feedback and comments that have helped us improve the quality of this work. This work is supported by Program for Changjiang Scholars and Innovative Research Team in University (IRT1158, PCSIRT), China.


Yan Yao
email: yaoyan@sjtu.edu.cn

Jian Cao
email: bcao-jian@cs.sjtu.edu.cn

Minglu Li

A Network-aware Virtual Machine Allocation in Cloud Datacenter

Keywords: VM allocation, cloud datacenter, Two dimensional knapsack algorithm

In a cloud computing environment, virtual machine allocation is an important task for providing infrastructure services. Generally, the datacenters, on which a cloud computing platform runs, are distributed over a wide area network. Therefore, communication cost should be taken into consideration when allocating VMs across servers of multiple datacenters. A network-aware VM allocation algorithm for cloud is developed. It tries to minimize the communication cost and latency between servers, with the number of VMs, VM configurations and communication bandwidths are satisfied to users. Specifically, a two-dimensional knapsack algorithm is applied to solve this problem. The algorithm is evaluated and compared with other ones through experiments, which shows satisfying results.

Introduction

Cloud computing has emerged as a new paradigm for hosting and delivering services over the Internet [START_REF] Armbrust | A View of Cloud Computin[END_REF]. There are three service models in cloud computing: Infrastructure as a Service (IaaS), Platform as a Service (PaaS), and Software as a Service (SaaS) which deliver the infrastructure, platform, and software (application) as services respectively. These services are made available to consumers in an on-demand way. In order to provide users with various cloud services, many cloud providers (e.g. Amazon, Google) have built their cloud datacenters around the world.

Resource allocation is a core process in a datacenter. Recently, an increasing number of cloud providers take advantage of virtualization technologies, such as VMware [START_REF] Waldspurger | Memory resource management in VMware ESX server[END_REF], Xen [START_REF] Barham | Xen and the art of virtualization[END_REF], KVM [START_REF] Kivity | kvm: the Linux virtual machine monitor[END_REF] and OpenVZ [START_REF]Openvz: Server virtualization open source project[END_REF], to implement a cloud datacenter. Typically, a user submit his requests, including the number of Virtual Machines (VMs for short) and their configurations through a portal of the provider. The provider will allocate the VMs in the cloud datacenters to satisfy the requirements of the user. Thus VM allocation is becoming a new problem to be solved.

There already exist many algorithms for VM allocations with different aims and assumptions [START_REF] Ye | Virtual machine based energy-efficient data center architecture for cloud computing: a performance perspective[END_REF]. Some of them try to allocate VMs in an energy efficient way [START_REF] Cao | Energy efficient allocation of virtual machines in cloud computing environments based on demand forecast[END_REF][START_REF] Beloglazov | Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[END_REF][START_REF] Buyya | Energy-efficient management of data center resources for cloud computing: a vision, architectural elements, and open challenges[END_REF][START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF]. Energy consumption is a big concern for cloud providers. But other factors should be considered in VM allocation as well, such as network. Some works have been done on VMs allocation in a network-aware way [START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF][START_REF] Wang | Consolidating virtual machines with dynamic bandwidth demand in data centers[END_REF][START_REF] Biran | A stable network-aware vm placement for cloud systems[END_REF][START_REF] Alicherry | Network aware resource allocation in distributed clouds[END_REF]. However, there still exists several open issues to be solved. Firstly, the existing allocation algorithms considering the consumptions of network resources are designed for traditional datacenters whose network architectures are often centralized, not distribute over a wide area. In a cloud data center, the distances between different sub-datacenters greatly affect the performance of applications. In addition, the VMs requested by users have various configurations, such as different number of processors or amount of memory. Thus the issue of the heterogeneity should be considered.

In this paper, we focus on the two open issues mentioned above. As it is well known that the resource allocation problem is NP-hard, here we developed a heuristic algorithm, a Network-aware VM allocation algorithm based on Maximum Clique (MCNVMA for short), with the goal of minimizing the maximum latency in communication between the sub-datacenters. MCNVMA considers constraints on local physical resources, such as CPU and memory, as well as the network. In order to make it more practical, the VMs and the datacenters both are heterogeneous in MCNVMA.

The rest of this paper is organized as follows: Section 2 discusses related work and Section 3 introduces the problem in details. Section 4 illustrates detail steps of the MCNVMA we developed. Experimental results are illustrated in Section 5 to show performance evaluation of MCNVMA. Section 6 concludes the paper.

Related Work

Existing work on the allocation of VMs can be categorized into three offering models: reservation model, spot markets model and on-demand access model [START_REF] Shang | An Intelligent Capacity Planning Model for Cloud Market[END_REF]. In the reservation model, a user purchase a bundle of resources for a period (e.g., a whole year) , during which the specified VMs can get great discount for payment in advance. Spot market model is a one-side auction market, consuming resources at a lower and flexible cost. In on-demand access model, users simply requests a specified number of the VMs, and pays for it according to a fixed schedule of fees. Here we restrict our study to on-demand access model. There are two types of VM allocation decisions to be made: initial placement [START_REF] Machida | Redundant Virtual Machine Placement for Fault tolerant Consolidated Server Clusters[END_REF] and optimizing (or migration) of VMs allocations over time [START_REF] Lee | Validating Heuristics for Virtual Machine Consolidation[END_REF].

In the current research, initial placement and VM migration as considered as separate topics, though in some cases similar algorithms may be employed. We limit our study to initial VM placement. Cluster and node are two levels considered in initial VM placement. In general, we consider physical machines are put in an unstructured resource pool so that the default is a shared cluster. Some constraints should be satisfied when VMs are allocated to physical machines,.. Usually, the constraints are put on some specific attributes such as CPU usage, memory usage, and network usage. These constraints can be summarized into a weighted criteria used to order physical machines. If the criteria is about energy, then the algorithm tends to save energy [START_REF] Cao | Energy efficient allocation of virtual machines in cloud computing environments based on demand forecast[END_REF][START_REF] Beloglazov | Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[END_REF][START_REF] Buyya | Energy-efficient management of data center resources for cloud computing: a vision, architectural elements, and open challenges[END_REF][START_REF] Beloglazov | Energy efficient resource management in virtualized cloud data centers[END_REF]. If the criteria is about network, the algorithm tends to reduce the network traffic [START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF][START_REF] Wang | Consolidating virtual machines with dynamic bandwidth demand in data centers[END_REF][START_REF] Biran | A stable network-aware vm placement for cloud systems[END_REF][START_REF] Alicherry | Network aware resource allocation in distributed clouds[END_REF]. We briefly introduce some of them related to our work. In [START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF], the authors introduce a Traffic-aware VM Placement Problem (TVMPP), trying to reduce the aggregate traffic. As TVMPP is NP-hard , the authors introduce a heuristic approach to solve it. In [START_REF] Wang | Consolidating virtual machines with dynamic bandwidth demand in data centers[END_REF], a Min Cut Ratio-aware VM Placement (MCRVMP) is proposed. It considers both constraints on local physical resources and network resources evolving from complex network topologies and dynamic routing schemas. They achieve them by exploiting the notion of network graph cuts. While both TVMPP and MCRVMP assume static and well-defined traffic demands, in [START_REF] Biran | A stable network-aware vm placement for cloud systems[END_REF] the authors focus on the equivalent capacity notion to consolidate VMs with uncorrelated traffic demands. Traffic demands are modeled as stochastic variables, and the optimization problem strives to place VMs while ensuring that the maximum network capacity is not violated with a particular user-defined probability. Hence, the final VM placement problem is a stochastic bin packing problem, and authors introduce a new heuristic approach to solve it. However, all the above network-aware VM allocation strategy ( [START_REF] Meng | Improving the scalability of data center networks with traffic-aware virtual machine placement[END_REF][13] [START_REF] Biran | A stable network-aware vm placement for cloud systems[END_REF]) are designed for traditional datacenters whose network architectures are often centralized and do not distribute over a wide area. Mansoor Alicherry et. al in [START_REF] Alicherry | Network aware resource allocation in distributed clouds[END_REF] proposed a network aware resource allocation algorithm based on distributed datacenter. They also take it make a compare with traditional datacenter and they regard the VMs as homogeny, which means all the VMs requested by users have the same number of processors and the same amount of memory. It is not applicable to real world. In this paper, we view datacenter are geographical distribution and VM requested by users are unique. The number of processors and the amount of memory of the VMs requested can be arbitrary realistic value.

VM Allocation Problem in Cloud Datacenters

What exactly is the VM allocation? In brief, a user requests for a service hosted in the cloud, requiring the allocation of VMs in the cloud datacenters, to meet the requested service's computational needs. The datacenter should identify the suitable physical resources for each requested VMs and allocate them. A user's request can be specified in terms of the number of VMs, their configurations and the communication requirements. Sometimes a user may not have a priori knowledge of the communication requirements among the VMs. However we can get it by statistic analysis approach. In this paper, we assume that knowledge of the communication requirements among the VMs is already known.

We use a small dataset for ease of illustrating. In reality, it can be much larger sets of VMs and cloud datacenters. Suppose a user applies for ten VMs to run an application over a cloud infrastructure. Each VMs has fixed processor and memory (See Table 1) and the communication requirements(bandwidth) between VMs is collected (See Table 2). In Table 2, if the entry value is 0,it indicates there is no communication between two virtual machines, otherwise, it represents the necessary communication bandwidth needed. Suppose there are only five sub-datacenters to run these VMs. Each sub datacenter has some free CPU and memory capacities (see Table 3), and the distance between them are known as well(Table 4). Now, we need to find an VM allocation meeting the following requirements:  Processor and memory requirements of VMs allocated on a sub-datacenter should not exceed its available free capacity.  The communication requirements among VMs can be satisfied.  The communication between VMs which belonging to different sub-datacenters (or servers) is minimized.

In this paper, each VM can be placed on arbitrary datacenters and servers. We propose a heuristic approach which consists of two consequent steps: datacenter selection and server selection. Datacenter selection is to select sub datacenters , which are geographically distributed, to place the VMs. And then assign individual VMs to the selected sub datacenters. Server selection is to determine the servers in the selected sub-datacenters and place the individual VMs to the servers. The two steps are very similar in algorithm. And here we just provide an example of selecting sub datacenters.

VM Allocation Algorithm

Problem Formulation

Our problem statement can be briefly described as follows:

1. m cloud datacenters are available and their resource capacities given along processor and memory dimensions. Noted as the set = { , , … , } . For each ∈ , with the capacity = ( , ); 2. There are n VMs to be placed. The requirements of these VMs are given in terms of processors and memories needed, denoted as = { , , … , } and for each ∈ , the capacity requirement is = ( , );

The communication cost between n VMs is denoted by a matrix = (

) × ; 4. The communication distance between any two sub datacenters is given, denoted as = ( ) × . We regard the network resource as sufficiently enough, however in server selection phase, the constrains on communication distance is changed to the network resource (like bandwidth). 5. We need to find a mapping between VMs and sub datacenters that satisfies the VMs' resource requirements while minimizing inter-datacenter traffic and intra-datacenter traffic between VMs.

While finding such a mapping, we have to take care that the total resource requirement of the VMs placed on the same sub datacenter should not exceed the datacenter's capacity.

MCNVMA Algorithm

The basic idea of our MCNVMA algorithm is: First of all, we identify a subset of the datacenters with minimizing length of the paths between the datacenters. Additionally we need to determine the datacenter assignment for each individual VM. For this assignment, our objective is to minimize the inter datacenters traffic between the VMs. Firstly, we select a set of datacenters to place the VMs. We view this problem as a sub-graph selection problem, which is finding a maximum sub-graph with a given diameter. For general graphs, it is an NP-hard problem and cannot be approximated within 2-ε for any ε>0) [START_REF] Alicherry | Network aware resource allocation in distributed clouds[END_REF].

Given a complete graph G = (V, E, c, l). The vertices V represent the datacenters, and weights = ( , ) on them denote the number of processors and the amount of memory of the datacenter respectively. The edges E represent the path between the datacenters and length l on them denotes the communication distance between the sub datacenters (in server selection phase denotes bandwidth). Let s be the number of VMs requested by the user. Then we should find a sub graph of G, denoted as G', with m' vertices. G' meeting the flowing conditions<1, 2>, with minimum maximal distance. For ∀ ∈ {1,2, … , ′},

( ) ≤ (1) ( ) ≤ (2)
where ( ) equals to (represent the number of processors VM j required) if VM j is deployed on data center i, otherwise is zero; and

( ) equals to (represent the amount of memory VM j required) if VM j is deployed on datacenter i , otherwise also is zero.

Since the original graph is a complete graph, the subgraph induced by the selected vertices is also complete. And all of the complete graphs are their self-clique. Hence, our goal is to find such a clique whose length of the longest edge is minimum. Once a datacenter is selected, we will assign individual VMs to it. This assignment is done during the process of datacenter selection. This problem can be regarded as a variant of two dimensional knapsack problem. We regard each datacenters as a knapsack and each VM as an item. The capacity of knapsack consists of available processors and memory. As mentioned in the problem statement, each item has two different kinds of cost (processors and memory). The value of each VM is the sum of the bandwidth, which is needed while communicating with others. The value is dynamic change along with the implementation of the algorithm. Our goal is to find the allocation of VMs with the maximum value under the conditions of limited capacity and minimum communication.

Algorithm: MCNVMA(G, N, W[][],Value[]) Input: G =(V,
The algorithm finds a sub-clique satisfying the constraints that include vertex v and places VMs by invoking two dimensional knapsack algorithm which is implemented by the dynamic programming method. After completing the two dimensional knapsack algorithm, the VMs with lager communication requirement are placed on the same datacenter, then the communication cost between different datacenter is least. The algorithm finds maximum clique including vertex v by adding nodes in an increasing order of length to v, until the weight of the clique meeting the constraints. The algorithm computes the diameter of the resulting sub-clique as well. This is done by maintaining the diameter as the nodes are added. When a node is added, the diameter of the sub-graph change only if the length of the edges induced by that node is greater than the current diameter.

The algorithm finds a sub-clique meeting the constraints through the while loop for each of the vertices, and selecting the one with the smallest diameter.

Example and Analysis

Now let's illustrate how to solve the problem introduced in Section 3.2 using MCNVMA algorithm. First of all, we need to map datacenters onto the nodes of a graph(Fig 3). The weights of nodes correspond to the capacity of datacenters (Table 3), and the weights of edges correspond to distances between sub-datacenters (Table 4).

Firstly, we select a arbitrarily node, such as n 0 as the start node. We use two dimensional knapsack algorithm to assign VMs set on it. The sum of each row of Table 2 is the VM's value (Table 5), which changing dynamically. Now we place {VM 3 , VM 6 , VM 7 , VM 8 } on n 0 . As n 1 to shortest among n 0 's neighbors. Next, we select and place VMs on n 1 from the remaining VMs list ({VM 0 , VM 1 , VM 2 , VM 3 , VM 4 , VM 5 , VM 9 } ). This procedure repeats until all of the VMs have been allocated. We record the nodes and the diameter of the sub graph, which is induced by the nodes (Table 6). Then we select the clique with minimum diameter C={n 0 , n 1 , n 2 }, that is datacenter DC 0 , DC 1 , DC 2 .

Fig. 1. Graph G=(V,E)

Analysis: In the while loop needs to sort the lengths of edges incident on a node, which takes nlogn time, where n is number of datacenters. While loop in the algorithm may be executed once per node. Computing diameter takes O(n 2 ) as there are n 2 edges. And the dynamic programming based two dimension knapsack algorithm takes O(mn) time as there are m VMs and n data centers. Hence, in the worst case, the running time of while loop is O(n 2 ). Algorithm MCNVMA executes the while loop times, one for each node so that the worst case complexity is O(n 3 ). weight of vertices : w={(60,15),(22,18),(40,12),(20,13),(80,21)} weight of edges : <0,1>=2,<0,2>=7,<0,3>=11,<0,4>=10 <1,2>=5,<1,3>=7,<1,4>=1 <2,3>=9,<2,4>=20 <3,4>=15 0 1 2 3 4

Evaluation

Experiment Settings

We compare MCNVMA algorithm with Random algorithm and Greedy algorithm. Random algorithm selects a random datacenter and places VMs as many as possible on it randomly. If there are more VMs in the request than available in the datacenter, then the algorithm chooses the next datacenter randomly to place the remaining VMs. This process is repeated until all the VMs are placed. Greedy algorithm selects the datacenter with maximum capacity. It places as many VMs from the request as possible on that datacenter. If there are remaining VMs in the request to be placed, then the algorithm selects the next datacenter with the largest free capacity. This process continues until all the VMs are placed.

To measure the performance of the algorithms, we create random topologies and user requests, and measure the maximum distance between any two VMs in the placement output by these algorithms. The locations of datacenters are randomly selected from 500x500 grid. In each of the experiments below, we report the results as average of 100 runs.

Experiment Results

Firstly, we measure the maximum distance of the placement for a request of 100 VMs. By varying the number of datacenters, we compare the maximum distance between any two VMs, see Figure 2 and3. MCNVMA algorithm has much smaller distance than random algorithm. The communication cost between datacenters in MCNVMA is lower than other two. Now, we set the number of datacenter to 50. We vary the number of VMs to evaluate the maximum distance and the stability of the algorithm. From figure 5 we can see that the maximum distance computed by MCNVMA algorithm is much lower than random algorithm and greedy algorithm. And the stability of MCNVMA is similar to the other two algorithms (Fig. 6). In this work we provide a allocation algorithm (MCNVMA) for VMs in cloud datacenter. Each VM can has its own configuration requirements in MCNVMA. The communication cost among VMs, which can be collected, are also defined as requirements as well. This algorithm try to find solutions with short communication path among VMs while user's requirements can be satisfied. From experimental results, the MNCRA algorithm reduces the communication cost between the VMs especially in large scale datacenters. In this paper, only network factors are considered. However, energy saving, load balancing and other factors should also be considered in real applications. We are going to explore other market models, such as spot market model as well.

Fig. 2 .

 2 Fig. 2. Max distance for 100 VMs

Fig. 3 .Fig. 4 .Fig. 5 . 6 .

 3456 Fig. 3. Communication Cost for 100 VMs

Table 1 .

 1 VM Requirements(processor number, memory amount)

	VM	Processor Requirement	Memory Requirement
	VM 0	4	2
	VM 1	8	8
	VM 2	2	4
	VM 3	8	2
	VM 4	4	4
	VM 5	4	6
	VM 6	2	1
	VM 7	9	10
	VM 8	8	2
	VM 9	6	4

Table 2 .

 2 Communication cost between VMs(Mbps)

Table 3 .

 3 Datacenters Free Capacities

	DC	Processor Capacity	Memory Capacity

Table 4 .

 4 Distance between DCs (mile)

		DC 0	DC 1	DC 2	DC 3	DC 4
	DC 0	0	2	7	11	10
	DC 1	2	0	5	7	1
	DC 2	7	5	0	9	20
	DC 3	11	7	9	0	15
	DC 4	10	1	20	15	0

Table 5 .

 5 VM value list

	VM	Value(Mbps)
	VM 0	1.9
	VM 1	2.1
	VM 2	1.35
	VM 3	2.71
	VM 4	1.6
	VM 5	1.7
	VM 6	2.61
	VM 7	2.76
	VM 8	3.22
	VM 9	2.03

Table 6 .

 6 Result

	Start node	Clique	Diame-
		ter
	n 0	{ n 0 , n 1 , n 2 }	7
	n 1	{ n 1 , n 4 , n 0 }	10
	n 2	{ n 2 , n 1 , n 0 }	7
	n 3	{ n 3 , n 1 , n 2 }	9
	n 4	{ n 4 , n 1 , n 0 }	10

Acknowledgements

This work is partially supported by China National Science Foundation (Granted Number 61073021, 61272438), Research Funds of Science and Technology Commission of Shanghai Municipality (Granted Number 11511500102, 12511502704), Cross Research Fund of Biomedical Engineering of Shanghai Jiaotong University (YG2011MS38). The work described in this paper was supported by Morgan Stanley. Morgan Stanley and Shanghai Jiao Tong University Innovation Center of Computing in Financial Services have entered into Collaboration Agreement No. CIP-A20110324-2.


Youhui Zhang

Peng Qu

Ziqiang Qian

Hongwei Wang

Weimin Zheng

Peng Qu

Software/Hardware Hybrid Network-on-Chip Simulation on FPGA

Keywords: Network on chip, FPGA, Simulation

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Networks-on-Chip (NoC) [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF][2] is an approach to designing the communication subsystem between IP cores in a chip, which separates the on-chip communication from computing and storage to improve scalability. For multi-core architectures, NoC has been regarded as one of the crucial and common components. NoC interacts with other functions on-chip, like the cache-coherency (CC) mechanism, the cache-line distribution and so on, to affect the whole system efficiency. It means system architects and researchers must include detailed NoC simulation as part of any complete system simulation. Detailed NoC simulation is a time-consuming process [3] [4]. Thus quite a few existing projects [START_REF] Genko | A complete network-on-chip emulation framework[END_REF][6] [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF] [START_REF] Wolkotte | Fast, Accurate and Detailed NoC Simulations[END_REF] have used FPGA resource to emulate NoC for high speed, and the reconfigurable feature of FPGA provides a certain degree of flexibility. Fur-thermore, to simulate the system rather than the NoC itself is the final destination. Thus, NoC simulation should interact with other simulation modules efficiently.

This paper presents a software/hardware hybrid design for such requirements. The design principle is: the detailed and time-consuming NoC simulation is totally accomplished by the hardware resource (FPGA) and a simple but general purpose interface between the software and hardware simulations has been provided. To reduce the roundtrip transfer latency between SW and HW, we use the on-chip soft processor to execute simulation software to drive the NoC.

This paper gives the following contributions:

1. A general SW/HW hybrid simulation framework of CMP has been designed and implemented. The kernel is a configurable NoC simulator on the FPGA and some parameters such as data width, network topology, channel FIFO depth, virtual channel options, and packet length and so on can be assigned without recompiling / resynthesizing. Now in a Xilinx Virtex 5 FPGA chip, a NoC to scale to 16 nodes can be simulated with one MicroBlaze CPU on-chip and the work frequency is 100Mhz. A simple interface between SW and HW is also designed that the simulation software running on the on-chip soft core can cooperate with the NoC.

Performance analysis is given to show under what circumstance such a design is

preferred. There are two ways to run the simulation software, on the on-chip soft CPU or on the host general-purpose CPU. The former usually works on a much lower frequency (1/10 ~ 1/30 of the latter) but its interaction speed with the hardware module is very high because they co-exist on the same chip. For the latter, the transfer trip between the FPGA and the host application is fairly long. We present a sequential and quantitative performance model for such situations 3. The running efficiency is compared with its software counterpart. Result shows that, the NoC speed is 3000 times faster than the 100% software method for the simulation of a 4X4 NoC. Moreover, two usage examples are presented: For the first, two directory-based CC protocols for the multi-core architecture design have been simulated on this framework. In this case, all parts other than the NoC are simulated on the on-chip soft core. Compared with the counterpart that executes the software part on the host CPU, its speed is much higher because the HW/SW transfer latency has been reduced remarkably. The second is a trace-driven case.

Compared with the counterpart that executes all parts (including the equivalent NoC simulation implemented by software) on the host CPU, our method is much faster, too.

Related Work

Many NoC simulators are achieved by software. Some are standalone tools, like BookSim [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF] and DARSIM [START_REF] Lis | DARSIM: a Parallel Cycle-Level NoC Simulator[END_REF] while others are used as the interconnection module of full-system simulators (GEMS [START_REF] Milo | Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset[END_REF], SimFlex [START_REF] Hardavellas | SimFlex: a fast, accurate, flexible full-system simulation framework for performance evaluation of server architecture[END_REF], etc.). Software implementations are very easy for reconfiguration, fast to compile and deterministic. However they are quite slow, so that users often have to maintain reasonable running speed at the expenses of simulation accuracy.

Several FPGA-based NoC simulators have been designed [START_REF] Genko | A complete network-on-chip emulation framework[END_REF], [START_REF] Krasteva | A Fast Emulation-Based NoC Prototyping Framework[END_REF], [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF], [START_REF] Wolkotte | Fast, Accurate and Detailed NoC Simulations[END_REF], [START_REF] Wang | DART: a programmable architecture for NoC simulation on FPGAs[END_REF] that increase simulation performance by 10 times and more. [START_REF] Genko | A complete network-on-chip emulation framework[END_REF] presents an emulation environment implemented on an FPGA that is suitable to explore a wide range of NoC design-space. It gets a speed-up of 4 orders of magnitude with respect to a SystemC simulation of the same network. But re-generating is required when changing the configuration of the network.

DRNoC [START_REF] Krasteva | A Fast Emulation-Based NoC Prototyping Framework[END_REF] solves this problem based on the re-configurability of FPGAs. Speedups of hundreds of time have been achieved in the presented use case compared with a non-reconfigurable approach (synthesis based). However, partial reconfiguration requires a special design flow and incurs area overheads; and only a few select devices are available. NoCem [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF] improves emulation density over [START_REF] Lis | DARSIM: a Parallel Cycle-Level NoC Simulator[END_REF] and implements a 9-node mesh network on a single FPGA. Moreover, an example memory architecture exploration platform based on this tool has been provided. [START_REF] Wolkotte | Fast, Accurate and Detailed NoC Simulations[END_REF] virtualizes a single router on an FPGA, allowing the simulation of a NoC with multiple routers. An off-chip ARM processor stores N contexts for the router model and orchestrates the emulation of the N-node network. However, the off-chip ARM/FPGA communication is a performance bottleneck.

Further, DART [START_REF] Wang | DART: a programmable architecture for NoC simulation on FPGAs[END_REF] virtualizes NoC totally on the chip while no help of any offchip CPU is needed. It provides a flexible FPGA-based NoC simulator platform by decoupling the simulator architecture from the architecture of the simulated system. This technology has been also used in some multi-core CPU simulations, like Protoflex [START_REF] Chung | ProtoFlex: Towards Scalable, Full-System Multiprocessor Simulations Using FPGAs[END_REF], RAMPGold [START_REF] Asanović | RAMP Gold: An FPGA-based Architecture Simulator for Multiprocessors[END_REF] and so on.

Our work can be regarded as an extension of the above-mentioned projects. We design a straight and efficient HW/SW interface to control and stimulate the FGPA NoC module, and give a performance model of such a hybrid design to judge in what case it is beneficial in terms of performance.

A similar hybrid work is [START_REF] Liu | Cycle-Accurate 64+Core FPGA-Based Hybrid Simulator[END_REF]. It is focused on how to design the FPGA platform efficiently, which is used as an emulation platform for the cache and NoC designers to verify their designs in cooperation with the full-system software simulator. In contrast, our work provides a flexible NoC simulator on FPGA and all other modules, including the cache system, are implemented by software on-chip. Then, researchers can explore the design space more flexibly as less RTL (Register Transfer Level) codes are needed, and the SW/HW interaction is more efficient owing to the compact on-chip design. From the viewpoint of the system architects or researchers, a chip multi-core processor (CMP) contains the following levels (Fig. 1).

• Network on Chip: Most NoCs are packet-switched. The router usually implements wormhole routing with virtual channel (VC) flow control. Each packet in the network consists of the header flit to setup a route, an arbitrary number of data flits that contain the packet's information and one tail flit that will free the router's resources. All communications, including explicit accesses issued from CPU cores or the others (like control messages used by the CC protocol), are transferred in this level. • Memory hierarchy: It includes all of cores' local caches and / or on-chip memories.

Access requests from CPU cores will be handled by this level before entering into the NoC. If CC is maintained by hardware (which is true for most CMP designs today), the corresponding components (for example, the CC directory) are also regarded as part of this level.

• CPU cores and upper-level components.

In our design, the whole NoC is emulated by FPGA and quite a few of parameters can be configured without recompiling. Detailed descriptions of parameters are listed in Table 1. Of course, the simulation scale is limited by the available on-chip resources.

Further, we wrap the hardware kernel to provide control signals for the simulation software. From the viewpoint of software, the NoC module works like a function call: when all of the upper level's architecture-states in one simulated cycle have been updated, the software simulator invokes the SW/HW interface to promote the NoC simulation a cycle. Because the HW running frequency is much higher than the software simulation 1 , this sequential design does not affect the simulation speed. The first sends and receives data-flits to and from the node through those points; the second consists of arbitration blocks used to judge what is transmitted and when. The traffic generator connects to the Local Access Point to inject data flits into NoC. Each node has parameters that can be configured to match the properties of the component they simulate, without modifying the RTL codes (using VHDL generics).

• Traffic Model

Each data-flit in the NoC is described by a 32-bit value. It contains the metadata such as the source / destination addresses, the packet length, a timestamp that indicates when the flit should be forwarded, and the injection time to compute latency at the destination. The bit-width is dependent on the range of configuration parameters: For a NoC containing 16 nodes, 8 bits are used to represent the source and destination IDs, and we reserve extra 4 bits for expansion. Now the maximum of packet length is 16, so that 4 bits are used here. In addition, the timestamp occupies 6 bits and 10 bits for the latency computation.

For flow control, the credit-based mechanism is used: The upstream router keeps a count of the number of free flit buffers in each virtual channel downstream. Then, each time the upstream router forwards a flit, thus consuming a downstream buffer, it decrements the appropriate count. If the count reaches zero, no further flits can be forwarded until a buffer becomes available. Once the downstream router forwards a flit and frees the associated buffer, it sends a credit to the upstream router, causing a buffer count to be incremented. The 12-bit credit descriptor contains a timestamp (6 bits) and a virtual channel identifier.

• Timing Model

The channel FIFO models the timing information of latency of a wire link; each FIFO contains multiple virtual channels (VCs) and a RTL parameter controls the number of VCs to incorporate (up to 4 for this design). For each incoming flit, it will be queued into its VC and the internal timing logic can compute the corresponding de-queue timestamp.

The router models a four-stage wormhole VC router with credit-based flow control. Each router connects to four channel FIFOs and a traffic generator. The deterministic routing (X-Y routing) is supported because this simulator is mainly used to simulate the mesh (or mesh-like) topologies now. Router latency is modeled by incrementing the flit timestamp (it is also configurable) when it leaves. Contention in VC and switch allocation is also modeled by adjusting the timestamp appropriately.

The Configuration and Result-collection Interface

The interface contains the following types of signals or modules:

• Packet Injection: Packet control is written to the channel FIFO for the local access point. It will contain the metadata of packet such as source / destination addresses, packet length, and so on, which will be used to route the packet. • Statistics Export: There are three counters per traffic generator to record the number of injected and received packets and the cumulative packet latency.

• Router Metadata: These lines are used to collect running status of each router, which can be used to locate and analyze the hot spot(s). Now they mainly consist of various VC status signals (empty or full).

• Clock Signal:The clock signal of NoC is connected to a special strobe register.

Once this register has been written, a clock signal of high frequency will be issued to promote the NoC simulation a cycle.

• Reset Signal: It is a synchronous signal and the configuration is lost during the reset.

• Simulation configurations: As mentioned earlier, each node has configurable parameters (packet length, VC Number, FIFO length, etc.). These parameters are chained in a 16-bit shift register. A software tool sends the configuration bits over an RS232 serial interface.

From the system point of view, the NoC is a device attached to the processor bus. Thus software can access the above-mentioned signals through the memory-address mapping mechanism.

Performance Model

A sequential simulation model is presented here. In another word, the simulation software works with the hardware NoC sequentially. It is also a common case for quite a few widely-used full-system simulators, like SIMICS+GEMS and so on. Therefore, the elapsed time for one simulated cycle, E, can be represented by Equation 1.

E = Tsw + Thw + Tinteraction (1)

Tsw denotes the elapsed time of software execution and Thw is the hardware time. The last one represents the roundtrip latency of HW/SW interaction.

There are two modes of sequential simulation.

• Both software and hardware simulations are completed in the same chip.

In this case, both of Tinteraction and Thw are of the order of magnitude of 10 ns, while Tsw is much larger. For example, the test of this design shows that MicroBlaze and NoC both work at 100Mhz and a machine instruction on the MicroBlaze will take averagely 3 cycles to complete. It means the software simulation will consume tens or hundreds of instructions to finish a simulated cycle. Then, in this case E mainly depends on Tsw.

• The software is running on the host.

Here Thw is still of the order of magnitude of 10 ns and Tinteraction is much larger. Tests show that, in our design the average roundtrip latency between the host software and the NoC is about 0.3ms (through the GB Ethernet cable). On the other hand the software execution time is smaller: for an n-core CPU to simulate m target cores (m >= n), it is about 1/(30*n) of the previous version2 if we assume the frequency of the host CPU is 3Ghz.

In this case, E equals with (300000ns + Tsw / (30*n)). The conclusion is straightforward: if the operation in one simulated cycle is too complex, for example, it takes the core on-chip more than 30000 cycles (10ns per cycle) to complete, using the host CPU is preferred (just like [START_REF] Liu | Cycle-Accurate 64+Core FPGA-Based Hybrid Simulator[END_REF] did); otherwise, the on-chip mode is better.

4

Implementation and Evaluation

Implementation

We use the open source implementation of NoC emulator [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF] as the foundation, which is a body of VHDL code configurable by a top-level package file that can create a variety of Network on Chips on parameters of data-width, virtual channel implementations, topology, and in-network buffering lengths. We wrap this emulator as described in Section 3.1 to provide the SW/HW interface. As mentioned in Section 3.2, because the NoC simulation is actually used as a timing model, the original design of in-network buffers has been simplified. In detail, the packet header is necessary to be stored and forwarded node by node; for data flits, only the corresponding arbitration and flow control behaviors should be simulated while no real data-transfer is needed.

The FPGA platform used is BEE3. One BEE3 module consists of four large Virtex-5 155T FPGA chips. In addition, up to 4 Gigabit Ethernet interfaces allow a fullduplex data communication between each BEE3 module and a host server.

This NoC simulator is created by Xilinx ISE 12.4. For a 4X4 mesh, about 60% of FPGA slices have been used and its running frequency is 100Mhz. The remaining resources are used to occupy the MicroBlaze CPU.

BEEcube Platform Studio (BPS) is employed, too, which is a system-level IDE specially designed for BEE3. We use soft registers provided by BPS to connect the software simulation to the NoC. Such a register works like a normal hardware register; the difference lies in that it is used as a bus device that software can access. In order to improve the HW/SW interaction performance, several 128-bit-wide soft registers are used to supply data as much as possible once.

Moreover, external DRAM has been mapped into the MicroBlaze's address space so that the simulation software on-chip can access enough memory space. Thus, the work flow of one simulated cycle is described as follows:

Step 1) Software reads all output signals of the hardware NoC;

Step 2) Software completes all simulated events (of the memory hierarchy and / or the above level) in the current cycle.

Step 3) Software updates all input signals of the SW/HW interface accordingly.

Step 4) Trigger the reg_clk_strobe register.

Usage Examples and Tests

Table 2. Configurations of the comparison

• Running Performance Comparison

We use a well-known software NoC simulator, BookSim [START_REF] Jiang | BookSim 2.0 User's Guide[END_REF], as the counterpart and compare its performance with the FPGA version under different flit-injectionrates (configuration time is excluded). The flit-injection-rate defines the rate at which packets are injected into the simulator; for example, setting flit-injection-rate = 0.25 means that each node injects a new packet in one out of every four simulator cycles.

The configurations used by these two simulators are listed in Table .2.

One Linux server with a 3.2GHz Intel Xeon processor is used to run BookSim; multiple flit-injection-rates, from 0.05 to 0.5, are configured respectively to show the simulation performance under different loads.

The speedup (in the right part of Fig. 2) is the ratio of the number of cycles simulated per second in FPGA to that in software. We observe that the software's simulation speed decreases with increasing injection rate (in the left part of Fig. 4) while the hardware speed is constant. As a result, our simulator achieves greater speed-up at higher packet injection rates: The least is more than 3000 as the scale is 4X4 and the flit-injection-rate is 0.05; when the flit-injection-rate is set as 0.5, the ratio is about 6000. In addition, as the NoC scale increases, the speed gap will expand further.

• Comparison with other FPGA-based solutions

We have collected some information of existing FPGA-based NoC simulators, including the running performance, the consumed on-chip resources and the NoC scale that can be simulated, and presented them in Table 3. Because the FPGA chips used by these works are different, the comparison is for reference only. Fig. 2. Performance of the FPGA NoC simulator. In both figures, the X-axis stands for the NoC scale and flit-injection-rates. For example, 4X4(0.5) means there 16 nodes and each node injects a new packet in one out of every two simulator cycles. In the left part, the y-axis stands for the simulation speed measured in cycles per second. In the right part, the y-axis indicates the ratio of the number of cycles simulated per second in FPGA to that in software. Now, two variants of the MESI protocol have been implemented: Case 1: When one cache-line is to be modified, its owner directory will invalidate all copies in L1 caches.

Case 2: When one cache-line has been modified, its owner directory will replace all copies in caches with the new content as well as the copy in the memory.

A fixed sequence of 10000 memory accesses has been simulated in these two cases; the results are presented in Table 4. We can see that the number of elapsed cycles of Case 2 is about 164.5% of that of Case 1, although its L1 cache hit-ratio is 160.9% of Case 1. The reason lies in that, for Case 2, the communication times is much larger, about 229.5% of the other; and the average transfer-latency of a message through the NoC is increased from 3.8 cycles to 4.1. For Case 1, the whole simulation time is about 2.5s. According to the performance model in Section 3.2, if running the CC simulation on the host CPU that interacts with the FPGA, the time spent on the roundtrip communications will be more than 25.1s (83627 *0.3ms ), which is much more than the on-chip version. Therefore, this mode is preferred for such relatively simple simulations.

In addition, if both simulations (CC and the NoC) are completed by software on the host, the estimated running-time is also longer although we take the fastest simulation speed of BookSim (about 31000 cycles per second in Fig. 4).

• Trace-driven Example

This is a real usage. To compare NoC designs with different configurations, we have to simulate a few NoC architectures and use the real running trace as the input to judge the better design. The trace is collected through the following way: We use the Pin [START_REF] Berkowits | Pin -A Dynamic Binary Instrumentation Tool[END_REF] to instrument the real target process; in the corresponding callback code, we simulate a 16-core CMP's memory hierarchy with the given configurations but no NoC-communication has been simulated. Till now we can get the access-trace for NoC and the collected trace contains about 3,200,000 records.

Then, we use the GB Ethernet cable to transfer records into the chip when a proxy program is running on the soft core to receive data to drive the NoC. Although the transfer latency of the Ethernet is relatively high, its throughout is enough so that the transfer is not the bottleneck.

It has consumed 29,000,000 cycles or so to complete all records, in 127s. In contrast, we use the 100% software solution and the running time is about 710s.

Conclusions

We have presented a method that allows multi-core system designers to simulate NoC and other layers with flexibility and fast enough speed. By providing common SW/HW interfaces, the time-consuming and relatively-fixed part, NoC, is implemented by hardware while others are implemented by software. We synthesize this design on the Xilinx's Virtex 5 155T FPGA and some example has been completed to show its availability. In addition, performance analysis is given to show under what circumstance such a design is preferred: if the operation in one simulated cycle is too complex, using the host CPU for software simulation is preferred although the slow HW/SW interaction exists; otherwise, the on-chip mode is better.

Fig. 1 .

 1 Fig. 1. Levels of the micro-architecture of CMPs.

Table 1 .

 1 Parameters of the NoC simulatorFrom the physical view, the NoC simulator contains multiple nodes connected by a crossbar, which allows all-to-all communication mode. Because it can restrict the communication pattern through this interconnect, this design is able to model the connectivity of the target topology. Then from the viewpoint of simulation, arbitrary topologies can be simulated. In the current design, we only introduce 5 entry points into one NoC node (North, South, West, East and Local Access Point), which limits the number of types that can be simulated.Each node is a timing model, including the channel FIFOs, a router and a traffic generator:

	Configurations	Valid Options
	Topology	Mesh,Torus,2D-Torus
	Data width	1-256 bits
	Packet Length	2,4,8,16 words
	Pipeline latency of the router	Arbitrary (> 3)
	VC Number	0/2/4
	FIFO Length	2,4,8,16

Table 3 .

 3 Comparison with other FPGA-based simulators The whole memory space is shared by all cores. The CC feature is kept by the distributed-directory-based hardware, which is the main simulated subject by software. ─ No real CPU core is simulated. Instead, read / write memory accesses from the upper-level are created randomly. ─ On the memory-hierarchy level, a distributed and shared L2 cache including 16 banks and 16 L1 private caches have been simulated; all connect with each other through the 4X4 mesh. From the system point of view, each core has a L2 bank and a L1 private cache; the former is also the home directory of the corresponding memory-address range assigned to it. All distributed directories construct a global table that keeps track of what memory is held and where.

			[5]	[7]	[8]	[11]	Ours
	Running	Fre-	50	70	6.6	50	100
	quency(Mhz)
	On-chip resources	7387	16394	N/A	13050	11005
	(slices)		(Virtex II	(Virtex II Pro	(Virtex-II	(Virtex II Pro
			Pro V20)	(XC2VP30))	8000)	(XC2VP30))
	NoC Scale		6	9	N/A 3	9 4	16

Table 4 .

 4 Results of CC Examples

	Case 1	Case 2

In our design, MicroBlaze and NoC both work at 100Mhz and a machine instruction on the MicroBlaze will take at least 3 cycles to complete. Therefore, during a whole NoC cycle, there is almost no progress for software.

Because the detailed simulation of one core is usually implemented as a large and tightlycoupled state machine, it is difficult to be parallelized. On the other side, more than one target core can be simulated in parallel on several host CPU cores as they only interact with each other through the NoC.

It supports the time-division multiplexing technology, so that one physical node can simulate multiple target nodes (while the simulation speed will be degraded). For example, if a

4X4 network is simulated, the maximum simulation frequency is 206 kHz.

DART supports the time-division multiplexing technology, too. Here only the number of physical nodes are given.

Acknowledgement

The work is supported by the High Technology Research and Development Program of China under Grant No. 2013AA01A215. The authors wish to thank Mo Tao, Li Xiaoxiao and Jiang Linhao for their tireless support of the simulation environment.


Bingyi Liu

Libing Wu

Ping Dang

Lei Nei

Jianqun Cui

Research on the RRB+ tree for Resource Reservation

Keywords: Data structure, Advance resource reservation, RRB+ tree, Loop time slot array

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In high-performance distributed computing environments, some applications require access to distributed heterogeneous resources. These resources are often located in different zones and subject to different management strategies, which make it difficult to co-allocate them. In order to solve this problem, a method of resource reservation is used. It can ensure that all required resources are available at the same time in a specific period of the future time, and it can guarantee the QOS of services [START_REF] Gao Zhan | Dynamic grid resource reservation mechanism based on resource-reservation graph[END_REF]. Accord-ing to the use time of reserved resources, the resource reservation can be divided into two types -the immediate resource reservation and the advance resource reservation.

The latter is more widely used because of its flexibility, and this study focus on it.

The optimization of the data structure's performance plays a pivotal role in improving the overall performance of the advance resource reservation. Data structures are mainly used to store the real-time resource reservation information, involving operations of queries, insertions, and deletions. Among the processing time of the resource reservation, 60% is for the processing of the data structure, 8% is for the selection of suitable resources, and the remaining 32% is for the management of the resource reservation mechanism [START_REF] Burchard | Analysis of data structures for admission control of advance reservation requests[END_REF]. The key problem of building a data structure suitable for resource reservation is how to speed up the query rate and reduce the data redundancy. To this end, this paper studies the B+ tree for resource reservation -the RRB+ tree. By comparison with the loop time slot array, it is of better precision of expression, and higher utilization of storage space for the complex and changing network environment.

Related Works

The existing data structures can be divided into two categories: slot data structures, and non-slot data structures. The time slot array [START_REF] Burchard | Performance evaluation of data structures for admission control in bandwidth brokers[END_REF][START_REF] Ionuţ | Time slot groups -a data structure for QoS-constrained advance bandwidth reservation and admission control[END_REF] is a typical example of slot data structures. Each array element represents a time slot, and the value of it represents the amount of reserved resources. The time slot array is simple and easy for the admission control of reservation requests. However, there are also many inadequacies. First, if the duration of a request is too long, a considerable number of array elements will need to store the information, which is a waste of memory. Second, its precision of expression is very low, which means that if the unit of the array is a second, you can not describe the precise time in milliseconds. Third, the size of the array is affected by the parameters of reservation requests. The slot-based segment tree [START_REF] Brodnik | An efficient data structure for advance bandwidth reservations on the Internet[END_REF] is another time slot data structure. With the flexible resource reservation, Mugurel et al. improves the segment tree so that it can be better applied to actual environments [START_REF] Ionuţ | Efficient data structures for online QoS-constrained data transfer scheduling[END_REF].

In the studies of non-slot data structures, Qing Xiong et al. propose a data structure based on the single linked list [START_REF] Xiong | A linked-list data structure for advance reservation admission control[END_REF]. The experimental results show that its memory consumption is far less than the time slot array, and greatly superior to it in time consumption when the volume of requests is not very large. Libing Wu et al. propose an improved single linked list structure -the indexed list [START_REF] Wu | A index linked list suited for resource reservation[END_REF]. The experiments show that its memory consumption is lower than the single linked list, and its query time is shorter than the time slot array.

The tree structures are another widely studied non-slot data structures. Tao Wang et al. propose a bandwidth reservation resource tree [START_REF] Wang | Bandwidth tree -a data structure for routing in networks with advance reservation[END_REF]. All leaf nodes in the tree have the same depth. Each node represents a non-empty time interval. Each leaf node occupies a time interval, and the amount of remaining resources within this interval is the same. The interval that the parent node describes is the sum of the intervals occupied by all its children. However, the experimental results [START_REF] Xiong | A linked-list data structure for advance reservation admission control[END_REF] show that the bandwidth reservation resource tree is not as good as the slot array in both the processing ability and the memory consumption. Other tree structures include the binary search tree [START_REF] Schelbn | Performance of QoS agents for provisioning network resources[END_REF] and the resource binary tree.

The RRB+ tree

The B+ tree is typically used in the database and the operating system's file system.

Data in the B+ tree can be kept stable and in order. The insertion and update algorithms of the B+ tree are of logarithmic time complexity, which means that the insertion and update operations can be done efficiently. Therefore, according to the characteristics of resource reservation, we improve the B+ tree's node structure and related algorithms to obtain better performance, and that is the RRB+ tree.

The reservation requests are defined as follows:

Request = (bw, ts, td);

The parameter bw indicates the reserving bandwidth within each unit time, the parameter ts indicates the beginning time of the reservation, and the parameter td represents the reserving duration. Different from the B+ tree that insert a keyword each time, the RRB+ tree insert a reservation request, which means that the RRB+ tree consider the time values as keywords and the bandwidth of that time as a record.

Tree Node Structure

The non-leaf node of an m order RRB+ tree contains only the largest keywords of its sub trees. There are two head pointers: the pointer root to the root node and the pointer first to the leftmost leaf node. The nodes of the tree are defined as follows: (1) Empty tree;

(2) The tree is not empty, and the keyword ts is greater than all keywords in the current tree;

(3) The tree is not empty, ts is not greater than the largest keyword but it is not a keyword in the tree;

(4) The tree is not empty, and ts is one of the keywords.

The first two cases can be directly judged. For the first case, if the pointer root is null, the tree is empty. For the second case, the rightmost keyword of the node root is the biggest one in the tree. For the latter two cases, the query operation is similar to that of the binary sort tree. Traverse the tree from top to down since the node root -in every internal node, if ts is not bigger than a keyword of it from left to right, then enter the corresponding child node of that keyword until the traversal comes to leaf nodes. The structure of the query result is as follows:

struct Result { BNode * ptr; int i; int tag; };

The parameter ptr points to the leaf node where the insertion should begin for the latter two cases. For the first two cases, it will be NULL because it has to create a tree in the first case and the insertion place is clear in the second case (the rightmost leaf node). The parameter i indicates that the keyword ts should be the i-th keyword of the node ptr for the third case, and is originally the i-th keyword of the node ptr for the fourth case. For the first two cases, it will be zero. The parameter tag describes which one of the four cases is true for that result.

Insertion

On the basis of the query results above, the admission control will be done first. If it is of the first two cases, the server can directly decide the current reservation request to be admitted. For the latter two cases, the sever needs to read the resource reservation information during the time period of [ts, ts + td), and thus judges whether the request can be accepted. If it is able to accept the request, the corresponding insertion operation will be done.

If the tree is empty, establish a tree and insert the request. If the tree is not empty, the insertion operation will be divided into two steps: the insertion of the starting keyword ts and the insertion of the end keyword (ts+td For the insertion of the starting time ts, there will be no operation if the current tree contains the keyword ts(in case 4). If ts is greater than all the keywords in the current tree (in case 2), update the biggest keywords of each internal layer with the value of ts from top to down. And insert ts into the rightmost leaf node, setting its record value as equal as that of its previous keyword. If the tree doesn't contain the keyword ts and it is not greater than the largest keyword of the current tree (in case 3), insert it into the leaf node that the pointer ptr points to and set its record value the same as the previous keyword. Keywords' insertion may lead to leaf node's splitting and it is slightly different with the splitting algorithm of internal nodes (shown in the above algorithm) -the keyword may fall into the node tmp or t (the variables tmp and t are in the above algorithm), so the query result needs to be updated according to the real situation. The parent nodes will contain one more keyword, which may lead to the split operations upward. The insertion algorithm of ts is shown as follows: Take the 3 order RRB+ tree shown in Figure 1 as an example, insert the request (30, 108, 20) into it, and that leads to the calling of the insertion algorithm of ts at first.

void DealWithTs(Result r) if(r.tag == 2) //
Insert the keyword 108 to the third leaf node on the left and set its record value equal to that of the previous keyword 100 (that is 70). Then the number of keywords in that leaf node becomes 4, greater than 3, so it must be split. After the splitting, the number of keywords in its parent node becomes 4, so it needs to split, too. The new tree is shown in Figure 2. done to the tree in the Figure 2, it changes and its new state is illustrated in Figure 3.

to ensure the accuracy of experimental results, reservation requests of these four settings are the same (that means the random seed to generate the parameters of reservation requests is unchanged), and the value of the parameter BWMAX is also the same, so they get the same resource reservation results. which means that the deletions will be done probably every 10 requests received in set 1 and 600 in set 3. So the memory consumption before the deletion of RRB+ tree in set 3 is much larger than that in set 1.

The only difference between set 3 and 4 is that the value of λ in set 4 is ten times as large as that in set 3. So it probably receives 10 reservation requests in set 3 and one in set 4 per second. And the memory consumption of the RRB+ tree in set 4 has been significantly improved compared to that in set 3.

It can be seen that the memory consumption of the RRB+ tree is far less than that of the loop time slot array, when its deletion interval is appropriate. For different kinds of reservation requests, the RRB+ tree can achieve better performance through appropriately adjusting its parameters. The memory consumption of the loop slot array only associates with the largest reserved time and the current time. And if requests reserve resources far earlier than the time they use them or the durations are too long, its memory consumption will greatly increase. Also it is hard to set the size of the loop slot array. Therefore, the storage space utilization of the RRB+ tree will be much higher than that of the loop time slot array for the complex and changing network environment.

Conclusions

The performance optimization of the data structure plays a pivotal role in improving the overall performance of resource reservation. Data structure is mainly used to store the real-time resource reservation information, involving the operations of query, insertion and deletion. The query and update operations of the B+ tree are of high efficiency, so this paper propose a B+ tree structure suitable for resource reservation -the RRB+ tree, and design the corresponding algorithms for it. The results of experiments compared with the loop time slot array show that the storage space utilization of the RRB+ tree will be much higher than that of the loop time slot array for the complex and changing network environments.

  The parameter keynum represents the number of keywords in the node, and its range is [ ⎡ ⎤ 2 / m , m]. (key, record, ptr) describes a keyword: the parameter key represents the value of the keyword and it used to store the time in this article; the parameter record shows the resource reservation information of key, and its initial value is 0; and the parameter ptr is a pointer to the sub tree associated with that keyword key. The parameter parent points to the parent node of this node, the parameter seq indicates that it is the seq-th children of the parent node, and the parameter next is a pointer to the next node of the same level. Each node consumes the memory of 4 * (4 + 3 * (m +1)) bytes.

Figure 1

 1 Figure 1 shows a third order RRB+ tree. From the figure, we can get the current bandwidth reservation information stored in this tree: the amounts of reserved resources is 10 during the 0-14 time period, 90 during the 15-26 time period, 50 during the 27-35 time period, and so on.

Fig. 1 . 2 Algorithms 3 . 2 . 1

 12321 Fig. 1. Third Order RRB+ Tree

Fig. 2 .

 2 Fig. 2. after the Insertion of the ts (108)

Fig. 5 .

 5 Fig. 5. Comparison of Memory Consumption

  update the biggest keywords of internal layers with the value of ts

	top-down
	ReplaceDown(ts);
	end if
	if(r.ptr->keynum > m)
	//if the leaf node splits after the insertion, update r
	SplitUpdate(r.ptr);
	if(r.ptr->parent > m)
	Split(r.ptr->parent);
	end if
	end if

//r.ptr is the rightmost leaf node,insert ts to r.ptr Update(r.ptr); else if(r.tag == 3) //insert ts to r.ptr as the i-th member Insert(r.ptr, i);

Acknowledgment

This work is supported by National Science Foundation of China(No. 61070010, 61170017, 61272212)and Science & Technology Plan of Wuhan city.

After the insertion of ts, the parameter ptr points to the node where the keyword ts has been inserted and the parameter i indicates the position of ts in the node ptr pointing to for all these four search results, which makes the subsequent insertion algorithm of (ts + td) transparent to the four different insertion cases and simplifies this algorithm implementation. In the (ts + td) insertion algorithm, firstly all record values of keywords during the time period [ts, ts + td) are updated, and then the keyword (ts + td) is inserted.

4

Comparative Experiments

The Loop Time Slot Array

As time goes on, resources that have been reserved will be used, and there are new BWMAX, the maximum bandwidth that the system can provide per unit time.

Interval, the interval between two deletions of the RRB+ tree.

Results and Analysis

The fixed reservation admission control algorithm is used to decide whether to accept a reservation request or not. In the simulation experiments, the admission control rate will be about 98% by adjusting the value of the variable BWMAX after the values of other parameters are set. So the performance evaluation of the two data structures will be more objective. The settings of the relevant parameters are as shown in Table 1. The memory consumption of the RRB+ tree and the loop time slot array is shown in figure 5 below. "BD" represents the memory consumption of the RRB+ tree before deletions, "AD" represents the memory consumption of the RRB+ tree after deletions, and "Array" represents the memory consumption of the loop time slot array. In order