Jiaquan Gao

Bo Li

Guixia He

Modified Incomplete Cholesky Preconditioned Conjugate Gradient Algorithm on GPU for the 3D Parabolic Equation

Keywords: conjugate gradient algorithm, modified incomplete Cholesky preconditioner, parabolic equation, GPU

In this study, for solving the three-dimensional partial differential equation ut = uxx + uyy + uzz, an efficient parallel method based on the modified incomplete Cholesky preconditioned conjugate gradient algorithm (MICPCGA) on the GPU is presented. In our proposed method, for this case, we overcome the drawbacks that the MIC preconditioner is generally difficult to be parallelized on the GPU due to the forward/backward substitutions, and thus present an efficient parallel implementation method on the GPU. Moreover, a vector kernel for the sparse matrix-vector multiplication, and optimization of vector operations by grouping several vector operations into a single kernel are adopted. Numerical results show that our proposed forward/backward substitutions and MICPCGA on the GPU both can achieve a significant speedup, and compared to an approximate inverse SSOR preconditioned conjugate gradient algorithm (SSORPCGA), our proposed MICPCGA obtains a bigger speedup, and outperforms it in solving the three-dimensional partial differential equation.

Introduction

The conjugate gradient (CG) algorithm is one of the best known iterative methods. With a suitable preconditioner, the performance of the CG algorithm can be dramatically improved. The preconditioned conjugate gradient (PCG) algorithm has proven its efficiency and robustness in a wide range of applications. Following the introduction of CUDA (Compute Unified Device Architecture) by NVIDIA in 2007 in rent years [1], Graphic Processing Units (GPUs) have drawn much attentions. Many researchers have attempted to develop the suitable and flexible PCG algorithm for the GPU architecture. Related work can be found in [START_REF] Buatois | Concurrent number cruncher: a GPU implementation of a general sparse linear solver[END_REF][3][START_REF] Gravvanis | Solving finite difference linear systems on GPUs: CUDA parallel explicit preconditioned biconjugate conjugate gradient type methods[END_REF][START_REF] Galiano | GPU-based parallel algorithms for sparse nonlinear systems[END_REF].

For a PCG algorithm, the key is how to parallel solve the equation M z = r (M is the preconditioned matrix) on GPUs when shifting it to the GPU platform. For the modified incomplete Cholesky factorization (MIC) preconditioning, M = LDL T , where L is a lower triangular matrix. As we know, for solving the equation LDL T z = r, the following two steps are required. First, LDv = r is solved for v by the forward substitution, and then DL T z = Dv is solved for z by the backward substitution. It is obviously observed that the forward/backward substitutions are not easy to implement on GPUs if L does not have especial characteristics.

Due to the forward/backward substitutions, the MIC preconditioning is difficult to be parallelized on GPUs. In this study, we present an efficient method for parallelizing the forward/backward substitutions on the GPU, which is the main contribution. The reminder of this paper is organized as follows. In the second section, the problem and the MIC PCG algorithm are described. In the third section, some GPU kernels for the MIC PCG algorithm are proposed. Numerical results are presented in the fourth section. The fifth section contains our conclusions and points to our future research direction.

Problem and MIC PCG Algorithm

Problem Description

In this study, we consider the following partial differential equation (PDE):

     u t = u xx + u yy + u zz , (x, y, z, t) ∈ Ω × [0, T ], u(x, y, z, 0) = φ(x, y, z), (x, y, z) ∈ Ω, u(x, y, z, t) = 0, (x, y, z, t) ∈ ∂Ω × [0, T ], (1)
where u is the solution, φ(x, y, z) is a function of variables x, y and z, Ω is a regular three-dimensional domain and ∂Ω denotes the boundary of Ω.

Here we utilize the discrete variational derivative method (DVDM) to discretize the PDE (1). As compared to the finite difference method (FDM), The DVDM can guarantee that the constructed numerical scheme retains the energy dissipation or conservation properties. According to the strategy of the DVDM to construct a dissipative scheme, we define an energy G(u, u x , u y , u z ) = (u x ) 2 /2+(u y ) 2 /2+(u z ) 2 /2 of the PDE (1) and then obtain the numerical scheme as follows.

u t i,j,k -u t-1 i,j,k ∆t =δ (2) i u t i,j,k + u t-1 i,j,k 2 + δ (2) j u t i,j,k + u t-1 i,j,k 2 + δ (2) k u t i,j,k + u t-1 i,j,k 2 , (2)
where

δ (2) i u i,j,k = u i+1,j,k -2u i,j,k + u i-1,j,k (∆x) 2 , δ (2)
j u i,j,k = u i,j+1,k -2u i,j,k + u i,j-1,k (∆y) 2 , δ (2)
k u i,j,k = u i,j,k+1 -2u i,j,k + u i,j,k-1 (∆z) 2 . Assume that a 4 × 2 × 2 three-dimensional grid, shown in Fig. 1, is defined, the scheme (2) can be written as the following linear system for a certain time t ∈ [0, T ].

Au = b, (3)
where the coefficient matrix A is denoted as follows:

             * * * *             
, a sparse, symmetric, positive definite, seven-diagonal, diagonally dominant 16 × 16 matrix of regular structure, b is a vector of size 16, and u is an unknown solution vector of size 16. Therefore, it can be obviously seen that the key is to solve the linear system (3) for solving the 3D PDE (1).

MIC PCG Algorithm

For solving the symmetric linear system similar to (3), the PCG algorithm has proven its efficiency and robustness in a wide range of applications. Its detailed procedure is shown in Algorithm 1.

Algorithm 1: PCG algorithm for the linear system Au = b Input: A, b; Output: u

01 k = 0 02 u = [1, 1, • • • , 1] T , r = b -Au, M z = r, p = z, ρ0 = z T r 03 Repeat 04 q = Ap, α = ρ0/p T q 05 u = u + αp 06 r = r -αq 07 M z = r 08 ρ1 = z T r, β = ρ1/ρ0, ρ0 = ρ1 08 p = r + βp 09 k = k + 1 10 Until (k < maxiter and r T r > tol)
For the above linear system (3), the preconditioned matrix M = LDL T , where L is a lower triangular matrix with nonzero values along the main diagonal and at off-diagonal locations only where A has nonzero entries. Generally, the forward/backward substitutions both need n (n is the element number of the solution vector) steps to finish calculations of elements. However, we observe that the forward/backward substitutions for this case both can be finished in 6 steps instead of 16 steps according to the progressions shown in Fig. 2.

Fig. 2. Progression of the forward substitution

The computational grid in Fig. 2 is the same as in Fig. 1, and arrows represent dependencies between elements of the grid. The calculation of an element in each step does not only depend on its adjacent row and column neighbors, but also depends on its adjacent layer neighbors. For example, the element 14 is dependent to its adjacent row and column elements 10 and 13 and its adjacent layer element 6. However, not all elements have these neighbor elements and the number of neighbors varies with the location of the element. Moreover, for any element, its dependent neighbors must be calculated earlier than it in order to start its calculation. Moreover, the elements of each step are independent each other and can be concurrently calculated. All these things are helpful for shifting the forward/backward substitutions to the GPU platform.

GPU Kernels and Optimization

The primary kernels used in the implementation of Algorithm 1 are explained in this section. The kernels represented here perform mathematical operations used in Algorithm 1. Following Algorithm 1, the basic operations are sparse matrix-vector multiplications, vector operations and the forward/backward substitutions.

Sparse Matrix-Vector Multiplication

Here the sparse matrix A is stored with the compressed sparse row (CSR) format:

(1) the array a contains all the nonzero elements of A; (2) the array colidx contains column indices of these nonzero elements; and (3) entries of array rowstr point to the first element of subsequent row of A in arrays a and colidx.

Sparse matrix-vector multiplications (SpMVs) represent the dominant cost in the PCG algorithm for solving large-scale linear systems. Fortunately, the SpMV for the CSR format is easy to be parallelized on the GPU. A straightforward CUDA implementation, which is referred to as the scalar kernel, uses one thread per row. However, its performance suffers from several drawbacks. The most significant among these problems is that threads with a warp (a bunch of 32 CUDA threads) can not access the arrays a and colidx in a coalesced manner. In [START_REF] Bell | Efficient sparse matrix-vector multiplication on CUDA[END_REF], An alternative to the scalar kernel, called the vector kernel, assigns one warp to each matrix row. For the vector kernel, it accesses the arrays a and colidx contiguously, and therefore overcomes the principal deficiency of the scalar kernel.

Thus, here we will utilize the vector kernel to compute the SpMV on the GPU, and refer the readers interested in the detailed GPU implementation of the vector kernel to the literature [START_REF] Bell | Efficient sparse matrix-vector multiplication on CUDA[END_REF].

Vector Operations

As we can see in Algorithm 1, the vector operations are the vector copy, the scalar vector product, the saxpy operation and the inner product of vector. In order to optimize these operations, we try to group several operations into a single kernel. For example, the saxpy operation as well as the vector copy are grouped in the same kernel. On the other hand, we perform the inner products needed for the computation of α and the inner products involved in the β computation in single kernels.

Forward/Backward Substitution

In this section, we will exhibit our proposed method of the forward/backward substitutions on the GPU. In order to better show our proposed method, the 4 × 2 × 2 grid in Fig. 1 are extended to a 64 × 48 × 3 grid.

Since the implementation technique of the forward substitution is also suitable for the backward substitution for this case, here we only discuss the forward substitution. Assume that each thread block is assigned with x × y solution elements, the number of required thread blocks can be calculated by the following formula:

N tb = N ROW x × N COL y × N LAY. (4)
By Eq.( 4), 36 thread blocks are required if each thread block is assigned with 16 × 16 (x = 16 and y = 16) solution elements for the 64 × 48 × 3 threedimensional grid. A way of possible grouping of 36 thread blocks on the GPU is illustrated in Fig. 3. According to the progression of the forward substitution in Fig. 2, it is obviously found that the amount of data must be almost transferred between two adjacent thread blocks from the same layer and from the neighboring layers. For example, consider calculations of elements in thread block 18. To start its execution, on one hand, the thread block 18 must wait for transmission from its adjacent thread blocks 14 and 17 to which it is independent in the same layer; on the other hand, it also waits for transmission from its adjacent thread block 6 on which it depends in the neighboring layer. The total amount of data to be received from the same layer is (x + y). However, the total amount of data to be received from the neighboring layers is (x × y). Since the data exchange between thread blocks must be performed on the GPU global memory, the transmissions will be the primary source of the overall communication latency.

Here in order to decrease the amount of exchanged data between thread blocks from the neighboring laryers, we utilize the share memory to store the values calculated by a thread block, and the thread blocks which are located in different layers and whose position are the same are mapped to a thread block. For example, thread block 1 in the first layer, thread block 13 in the second layer and thread block 25 in the third layer can be mapped to a thread block in Fig. 3. If so, the data exchange between thread blocks of the adjacent layers will be no longer required because they are located in the same thread block. Thus, the amount of exchanged data required is to decrease from (x × y + x + y) to (x + y) when the elements in a thread block are calculated. For example, when calculating elements in thread block 18 in Fig. 3, only the data transmissions from its adjacent thread blocks 14 and 17 in the same layer are required, and thus the total amount of exchanged data is 32 rather than 288. At the same time, the number of required thread blocks is also reduced and can be calculated as

N tbnew = N ROW x × N COL y . ( 5
)
Therefore, the number of required thread blocks for this case is decreased from 36 to 12. Figure 4 summarizes the progression of the forward substitution with 12 active thread blocks. Furthermore, in order to decrease the frequency of reading data from the GPU global memory, we allocate a two-dimensional (x+1)×(y+1) array in shard memory instead of (x × y) to store data for a x × y sized thread block. The extra row and column are allocated for dependent data from neighbor thread blocks in the same layer. Moreover, to manage the dependencies between adjacent thread blocks, we store a matrix in the GPU global memory where each thread block can check the status of adjacent thread blocks to which it is dependent. A thread block waits for a spinlock until the dependent thread blocks finish calculations and write results to the global memory. Then it reads these results and continues with its calculations.

Numerical Results

All experiments in this section are conducted on the environment which is based on GNU/Linux Ubuntu v10.04.1 with an Intel Xeon Quad-Core 2.66 GHz, 12GB RAM (CPU) and NVIDIA Tesla C2050, 448 CUDA Cores, 6GB RAM (GPU).

Firstly, the following seven three-dimensional grid models, 800 × 800 × 30, 480 × 480 × 80, 480 × 480 × 320, 128 × 128 × 480, 512 × 512 × 256, 128 × 128 × 1440, 1440 × 1440 × 80, are chosen to test the performance of our proposed forward substitution (GPUFBS). We respectively add up the computational time of GPUFBS and the CPU implementation of the forward/backward substitutions and then show them in Table 1. The time unit is microsecond denoted by ms. From Table 1, we can see that GPUFBS achieves a significant speedup for all seven three-dimensional grid models due to high utilization of GPU. As observed from Fig. 4, the thread blocks have high concurrency and the concurrency of thread blocks is improved as the number of layers increases.

By observing 480 × 480 × 80 and 480 × 480 × 320 grid models, it can be found that when the column and row sizes are given, GPUFBS with high number of layers has a bigger speedup than that of with low number of layers. Similarly, it can also seen that for a given number of layers, GPUFBS with a big size of column × row achieves a higher speedup than that with a small size of column × row by comparing the 480×480×80 grid model with the 1440×1440×80 model. Furthermore, as observed from the 128 × 128 × 1440 and 128 × 128 × 480 grid models, for the same size of column × row (128 × 128), the speedup obtained by GPUFBS with 1440 layers is nearly 2 times of the speedup obtained by GPUFBS with 480 layers. However, we compare the 480 × 480 × 80 grid model with the 1440 × 1440 × 80 grid model and find that for the same number of layers 80, the speedup obtained by GPUFBS with 1440 × 1440 (column × row) is only 1.02 times of the speedup obtained by GPUFBS with 480 × 480 (column × row). Therefore, we can conclude that the number of layers and the column and row sizes both have an impact on the performance of GPUFBS, but the number of layers for GPUFBS has a larger impact than the column and row sizes.

Secondly, we test the validity of our proposed MIC PCG method on GPU (MICPCGA) for solving the 3D PDE comparing with the PCG algorithm on the GPU (SSORPCGA) suggested in [3]. Let Ω = {(x, y, z)|0 ≤ x ≤ 1, 0 ≤ y ≤ 1, 0 ≤ z ≤ 1}, φ(x, y, z) = 3 sin πx sin πy sin πz for the PDE (1), and define the error (ER) = max |u i,j,k -ũi,j,k |, where u i,j,k and ũi,j,k respectively denote the exact solution and the approximate solution at the point (x i , y j , z k ). For this case, the exact solution is u(x, y, z, t) = 3e -3π 2 t sin πx sin πy sin πz, and the following five grid models, 100 × 100 × 100 (M21), 250 × 250 × 100 (M22), 250 × 250 × 250 (M23), 100 × 100 × 250 (M24), 100 × 100 × 1000 (M25), are chosen. In the following, taking x = 0.5, y = 0.5(z = 0.1, 0.3, 0.5, 0.7, 0.9) for example, Table 2 shows the errors of MICPCGA and SSORPCGA. The speedups of MICPCGA and SSORPCGA are summed in Table 3. From Table 3, we can see that for models M21 and M22, MICPCGA has a comparable speedup with SSORPCGA, and for models M23, M24 and M25, MICPCGA obtains a bigger speedup than SSORPCGA. Furthermore, it can be found that MICPCGA can obtain better approximate solutions than SSOR-PCGA for all cases. Therefore, we can conclude that MICPCGA outperforms SSORPCGA for this case.

Conclusion

In this study, we present an efficient parallel method for the forward/backward substitutions on the GPU, and thus propose a MIC PCG algorithm on the GPU. Numerical results show that our proposed MIC PCG algorithm has a good behavior, and outperforms the PCG algorithm suggested by Helfenstein and Koko.

For GPUFBS, its efficiency has been validated in this study. Next, we will extend the constructing idea of GPUFBS to other PCG algorithms with the following preconditioners, the incomplete-LU factorization (ILU), the modified incomplete-LU factorization (MILU) and their variants, and furthermore do research for the three-dimensional partial differential equation.

Fig. 1 .

 1 Fig. 1. A 4 × 2 × 2 three-dimensional grid

Fig. 3 .

 3 Fig. 3. 4 × 9 sized grid of GPU thread block

Fig. 4 .

 4 Fig. 4. Progression of the forward substitution with 12 active thread blocks

Table 1 .

 1 Speedups of GPUFBS

	Grid model	CPU (ms)	GPU (ms)	Speedup
	800 × 800 × 30 1020	125	8.16
	480 × 480 × 80 1058	101	10.47
	480 × 480 × 320 4784	278	17.20
	128 × 128 × 480 458	39	11.74
	512 × 512 × 256 3958	256	15.38
	128 × 128 × 1440 1463	67	21.83
	1440 × 1440 × 80 9560	893	10.70

Table 2 .

 2 Errors of MICPCGA and SSORPCGA (t = 0.1)

	Method	0.1	0.3	0.5	0.7	0.9
	Exact solution(10 -1 )	0.4799 1.2565 1.5531 1.2565 0.4799
	ER MICPCGA M21(10 -5 ) 1.1236 1.2342 1.4347 1.2358 1.2362
	ER MICPCGA M22(10 -5 ) 1.1192 1.1331 1.3019 1.1376 1.1164
	ER MICPCGA M23 (10 -5 ) 0.5786 0.8941 1.1893 0.8937 0.5734
	ER MICPCGA M24 (10 -5 ) 1.0304 1.1343 1.2184 1.1342 1.0328
	ER MICPCGA M25 (10 -5 ) 1.0122 1.1121 1.1834 1.0101 1.0152
	ER SSORPCGA M21 (10 -5 ) 5.5632 5.9822 6.2876 5.9896 5.5617
	ER SSORPCGA M22 (10 -5 ) 4.9127 5.3939 5.9918 5.3908 4.9103
	ER SSORPCGA M23 (10 -5 ) 2.3243 2.4232 3.1967 2.4234 2.3253
	ER SSORPCGA M24 (10 -5 ) 5.1342 5.1458 5.7633 5.1442 5.1354
	ER SSORPCGA M25 (10 -5 ) 4.7482 4.8294 5.2304 4.8261 4.7476

Table 3 .

 3 Speedups of MICPCGA and SSORPCGA

	Method and Model CPU (s)	GPU (s)	Speedup
	MICPCGA M21	3.71	0.40	9.27
	MICPCGA M22	23.91	2.43	9.83
	MICPCGA M23	63.58	5.21	12.20
	MICPCGA M24	9.62	0.93	10.34
	MICPCGA M25	39.36	3.51	11.21
	SSORPCGA M21	3.92	0.42	9.33
	SSORPCGA M22	25.40	2.60	9.76
	SSORPCGA M23	65.19	7.02	9.28
	SSORPCGA M24	10.13	1.03	9.83
	SSORPCGA M25	41.80	4.24	9.85

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

The research has been supported by the Chinese Natural Science Foundation under grant number 61202049 and the Natural Science Foundation of Zhejiang Province, China under grant number LY12A01027


Min Wang
email: wangxw@mail.neu.edu.cn

Huang
email: mhuang@mail.neu.edu.cn

Chengxi Gao

Xingwei Wang

Min Huang

A Cloud Resource Allocation Mechanism Based on Mean-Variance Optimization and Double Multi-Attribution Auction

Keywords: Cloud resource, Double multi-attribution auction, BP neural network, Support vector machine, Mean-variance optimization

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

Introduction

Cloud computing is the development of distributed computing, parallel computing, grid computing and many other technologies [START_REF] Dikaiakos | Cloud Computing: Distributed Internet Computing for IT and Scientific Research[END_REF]. It can integrate various types of resources in the network, so that they can be fully utilized. Therefore, a robust resource allocation mechanism has become the focus of researches about cloud computing which can specify the billing functionalities of the system and efficiently allocate the resources while bringing the most profits. Contemporarily, auction theory has been successfully used in solving the problem of resource allocation in many cases, which has shown good performance. Danak et al. presented a repeated auction-based allocation protocol and a utility-maximizing bidding algorithm to improve the long-term profits of the grid users [START_REF] Danak | Efficient bidding in dynamic grid markets[END_REF], but they didn't consider the fraud behavior in the market mechanism. Lan et al. proposed a multi-unit Continuous Double Auction (CDA) and got a reasonable resource allocation scheme to ensure fairness between users [START_REF] Lan | Multi-unit continuous double auction based resource allocation method[END_REF], but they didn't consider the fraud behavior of the users. Tan et al. proposed a novel Stable Continuous Double Auction (SCDA) mechanism which effectively reduced the instable factors of CDA and brought good economic returns [START_REF] Tan | Market-based grid resource allocation using a stable continuous double auction[END_REF], but the mechanism was weak in the consideration of the malicious bidding behavior of users. Prodan et al. determined the resource allocation model based on the CDA mechanism [START_REF] Prodan | Double auction-based scheduling of scientific applications in distributed grid and cloud environment[END_REF], but they didn't predict the market price.

Besides, game theory is also practical in the area of resource allocation. Teng et al. proposed a resource pricing and allocation policy through game theory which solved the equilibrium allocation problem among different users [START_REF] Teng | Resource pricing and equilibrium allocation policy in cloud computing[END_REF], but they didn't consider the malicious bidding behavior of users. Mutz et al. designed a resource pricing mechanism based on game theory and scheduled jobs and computed payments in pseudo-polynomial time [START_REF] Mutz | Efficient auction-based grid reservations using dynamic programming[END_REF], but they didn't consider the Quality of Service (QoS). Wang et al. determined the transaction price through the linear pricing strategy, and used the game-theoretic algorithm to get the optimized bandwidth resource allocation scheme [START_REF] Wang | A Game Theoretical Bandwidth Allocation Mechanism for Cloud Robotics[END_REF], but they didn't consider the information of historical transactions.

To sum up, the majorities of existing researches only care about the price attribution, but ignore the non-price attributions in transactions. Moreover, they lack the careful consideration about the fraud behaviors in the market mechanisms and don't forecast reasonably about the market price based on historical information.

In this paper, according to the Support Vector Machine (SVM) and Back Propagation (BP) neural network, we propose a cloud resource allocation mechanism based on Mean-Variance Optimization (MVO) algorithm and double multi-attribution auction (DMAA) mechanism. The prices of both traders are forecast based on SVM algorithm, and the non-price attributions of resource providers and resource consumers are converted into the quality indexes based on BP neural network algorithm. Combined with the DMAA mechanism, the cloud resource allocation scheme is obtained based on the MVO algorithm which aims to maximize the total satisfaction of both trades while increasing the resource utilization of providers and satisfying more consumers.

The rest of this paper is organized as follows. We introduce the system framework in Sect.2, and the auction model is discussed in Sect. 3. We talk about how to predict the price using SVM algorithm in Sect. 4 and multi-attribution processing is specified based on BP neural network algorithm in Sect. 5. We design a resource allocation scheme based on MVO algorithm in Sect. 6. The proposed mechanism is simulated and evaluated in Sect. 7 and we conclude the paper in Sect. 8.

System Framework

The cloud system mainly involves three roles including resource provider ( RP ), resource consumer ( RC ) and auction organizer ( AO ). The system framework is presented in Fig. 1. As is shown in Fig. 1, the process of the system is specified as follows:

AO

Step1: RP and RC submit their own information to AO to confirm the identity; Step2:

RP and RC use SVM algorithm to predict the prices and submit them to AO ; Step3: If there is a matching transaction, then go to Step4.Otherwise RP and RC are notified to confirm whether or not they are willing to stay in the auction. If they are, they need to re-determine the price according to SVM algorithm and then submit the new tenders to AO . Otherwise they will quit the auction or wait for the next auction considering their own situation;

Step4: According to the matching results of the transaction, AO uses BP neural network algorithm to transfer the non-price attributions to the quality index and adopts the MVO algorithm to solve the cloud resource allocation scheme;

Step5: AO notifies RP and RC to update the quote and bid respectively to participate in the new round of the auction until the end;

Step6: RC who receives the resources pays for the service to the corresponding RP , and they assess each other for his performance after the transaction. AO updates the corresponding information.

i i i i i i B B B B i i i BB i i i i i i B B B B ii BB DT TEFT TL or DT TLFT TL DT TLFT TL LoD TEFT TL DT TLFT TL TEFT TLFT                        (3)
Where ii BB TEFT TLFT  and  is constant which is used to adjust the value of i LoD . So S LoD is defined as in Eqn. ( 4).

1 1 M Si i LoD LoD M    (4)
Level of Spiteful Quote.

S

LoSQ is used to check whether or not RP has the behavior of spiteful quote or disrupting the auction market.

p is the price of the resources that RP provides, top and bottom represent the upper and lower limits of the resource price that AO sets, most and least devote the highest and lowest trading price of the resources. So S LoSQ is specified in Eqn. [START_REF] Prodan | Double auction-based scheduling of scientific applications in distributed grid and cloud environment[END_REF].

        2 2 2 2 1 , 0 , 0, , 1,
                                     (5)
Where  and  are constant which are used to adjust the value of S LoSQ .

Satisfaction of Resource

X X S iX i X i X X i X X S B S S X S i X X S DP EDP DP S IoQ RP DP EDP EDP DP RP                    (6) , , , 1, , 0, i
Where  and  are constant which are used to adjust the value of , iX S S . As is shown in Eqn. [START_REF] Teng | Resource pricing and equilibrium allocation policy in cloud computing[END_REF] S ,so we don't repeat the definition here.

Auction Organizer

When the auction starts, AO submits RP 's quote to the quote queue and RC 's bid to the bid queue respectively. The quote queue is sorted in ascending order and _ lowest quote represents the one at the head of the quote queue. The bid queue is sorted in descending order and _ highest bid represents the one at the head of the bid queue.

AO has to check whether or not there are transactions that satisfy the condition for matching which is specified as __ highest bid lowest quote  .

Price Prediction

SVM Algorithm

The goal of SVM algorithm [START_REF] Rajasegarar | Centered hyperspherical and hyperellipsoidal one-class support vector machines for anomaly detection in sensor networks[END_REF] is to select a function   In this paper, we adopt symmetric overrelaxation preprocessing technology [START_REF] Xing | On Issues and Applications for Least Squares Support Vector Machine[END_REF] to reduce the conditions of the coefficient matrix of the linear equations which can decrease the iteration time of the algorithm, thus speeding up the convergence rate and weakening the influence that rounding errors have on SVM.

Price Prediction Method Based on SVM Algorithm

In this paper, we use exponential smoothing method to predict the relationship between supply and demand. j sd represents the j-th relationship between supply and demand in previous transactions, 0 SA represents the initial predicted value and j SA represents the j-th predicted value which is defined in Eqn. [START_REF] Rajasegarar | Centered hyperspherical and hyperellipsoidal one-class support vector machines for anomaly detection in sensor networks[END_REF] .

    2 10 0 11 j ij j j i i SA sd SA               (9)
Where11 jn SD ,task urgency degree ( TUD ) and predicted buying price ( PBP ). The process of predicting the price based on SVM algorithm is as follows:

   , 
Step1: If there is a trained SVM, then go to Step 3. Otherwise, initialize the training sample set and determine the parameters of SVM algorithm such as the error threshold and maximum iteration time;

Step2: Train SVM using the training samples and update the weights. Then save the trained SVM;

Step3: Utilize the trained SVM to predict the price and generate the sample corresponding to this price prediction as the training sample which is then added to the training sample set;

Step4: If the maximum iteration time is not reached, then go to Step 2; otherwise, output the prices and the algorithm ends.

5

Multi-Attribution Processing

BP Neural Network Algorithm

The structure of BP neural network [START_REF] Zweiri | Stability analysis of a three-term backpropagation algorithm[END_REF] is consisted of input layer, hidden layer and output layer where input layer and output layer are single layers while hidden layer can be a single layer or multiple layers. The learning process of BP neural network [START_REF] Suresh | Parallel implementation of back-propagation algorithm in networks of workstations[END_REF][START_REF] Zhang | Employing BP Neural Networks to Alleviate the Sparsity Issue in Collaborative Filtering Recommendation Algorithms[END_REF][START_REF] Li | The Research of Intrusion Detection Technology Based on Artificial Neural Network[END_REF] includes the forward propagation and the error back propagation of the signal. These two processes are carried out circularly until the output error of BP neural network is less than the minimum error or the preset training time is reached.

In this paper, Sigmoid function [START_REF] Richard | Pattern Classification[END_REF] is utilized as the activation function to train the samples. The weights of the BP neural network are updated after training for W times where W is constant. Variable learning rate is adopted to adjust the decline rate of errors dynamically in the process of training. Inertia factor is used to measure the impact that the weight increments of previous trainings have on the weights of current training. Chaos noise [START_REF] Azamimi | Effect of chaos noise on the learning ability of back propagation algorithm in feed forward neural network[END_REF] is introduced into the process of weight updating so as to improve the error back-propagation process and the ability of jumping out of a local minimum point, thus enhancing the learning ability of BP neural network algorithm.

Multi-Attribution Processing Method Based on BP Neural Network Algorithm

The IoQ . The process of applying BP neural network algorithm to multi-attribution processing method is as follows:

Step1: If there is a trained BP neural network, then go to Step 3. Otherwise, initialize the training sample set and determine the parameters of BP neural network algorithm such as the error threshold and maximum iteration time;

Step2: Train the BP neural network using training samples and adjust the weights. Then save the trained BP neural network;

Step3: Utilize the trained BP neural network to transfer the non-price attributions to the quality index and generate the sample corresponding to this multi-attribution processing as the training sample which is then added to the training sample set;

Step4: If the maximum iteration time is not reached, then go to Step 2; otherwise, output the quality index and the algorithm ends.

Resource Allocation

In this paper, the total satisfaction of RC and RP is used as the fitness function in order to determine whether or not the allocation scheme is good.

MVO Algorithm

MVO algorithm [START_REF] Erlich | A Mean-Variance Optimization Algorithm[END_REF] is a kind of intelligent optimization algorithms. The basic idea is to use the mean and variance of the components of the solution vectors to evolve the solution set and find the optimal solution by iteration.

Resource Allocation Based on MVO Algorithm

Step1: Determine the amount of resources of this transaction namely TA and initialize the related parameters of MVO algorithm such as the maximum iteration time and the dimension of variation which is devoted by c . Generate a random initial solution X according to TA ;

Step2: Calculate the fitness function value. If the termination condition is satisfied, then go to Step 5;

Step3: Create the n best  population where n best  population represents the set of the top n best solutions when all of the solutions are sorted in descending order according to the fitness function value. Then calculate the mean and variance of the components of the solution vectors. Choose the solution with the largest fitness function value as the father solution father X ;

Step4: Randomly select c components from father X and evolve and update the selected components to get the child solutions, and then go to Step2;

Step5: Output the optimal resource allocation scheme and the algorithm ends.

Simulation and Evaluation

The resource allocation mechanism is implemented and evaluated based on JDK and Cloudsim on the Eclipse platform. There are 200 s RP and 150 s RC participating in the auction. The parameters of the proposed algorithms are detailed in Table 1, Table 2 and Table 3. A set of cloud resource prices is selected from Amazon as is shown in Table 4, which acts as the reference of RP 's quote and RC 's bid. In this paper, SCDA mechanism [START_REF] Tan | Market-based grid resource allocation using a stable continuous double auction[END_REF] is used as the benchmark double auction mechanism which acts as the reference of the performance compared with the proposed DMAA mechanism. SCDA adds a compulsory bidding adjustment layer (CBAL) based on the traditional CDA mechanism. When RP and RC submit the prices to AO , CBAL will delete the unreasonable prices according to the historical trading prices and the supply and demand of resources. Meanwhile, SCDA sets the task queue to save the tasks to be finished and the task queue is sorted in descending order according to the bids. All of the s RP calculate the price needed to complete the first task in the task queue. If there exists RP whose quote is less than the price, then the RP with the lowest quote can transact with the RC corresponding to the first task of the task queue.

The Comparison of Resource Utilization Rate of Resource Providers

We compare the resource utilization rate of RP between the two auction mechanisms in three cases when the supply exceeds the demand, the supply equals the demand and the supply is less than the demand. The results are presented in Fig. 2. As is shown in Fig. 2, at the beginning of the auction, the resource utilization rate of DMAA mechanism is slightly lower than that of SCDA mechanism. With the auction going on, the resource utilization rate of DMAA mechanism is higher than that of SCDA mechanism. This is because that the price prediction method used in the DMAA mechanism requires a process of collecting the training samples and learning, and at the beginning of the auction, the price prediction method is still in the process of learning, so the excellent performance of the method seems vague, thus the resource utilization rate of DMAA mechanism is lower than that of SCDA mechanism. With the auction going on, the performance of the price prediction method is gradually stabilized, so the resource utilization rate of DMAA mechanism is higher than that of SCDA mechanism.

7.2

The Comparison of the Amount of Resource Consumers Whose Demands

Are Satisfied

We compare the amount of resource consumers whose demands are satisfied between the two auction mechanisms in three cases when the supply exceeds the demand, the supply equals the demand and the supply is less than the demand. The results are presented in Fig. 3. As is shown in Fig. 3, at the beginning of the auction, the amount calculated from DMAA mechanism is slightly lower than that from SCDA mechanism. With the auction going on, the amount calculated from DMAA mechanism is higher than that from SCDA mechanism. The reason is similar to that in the previous section.

The Comparison of the Execution Time

We compare the execution time of the two mechanisms when the amount of s RC is 30,50,70,90,110,130 and 150 respectively, and the results are presented in Fig. 4. The amount of resource comsumers As is shown in Fig. 4, the execution time of the DMAA mechanism is higher than that of SCDA mechanism in all these seven conditions, and with the amount of s RC increasing, the gap of the execution time between the two mechanisms be-comes larger. This is because in DMAA mechanism, the multi-attribution processing method based on BP neural network algorithm, the price prediction method based on SVM algorithm and the resource allocation scheme based on MVO algorithm will take large amounts of time for learning and iteration, but the time consumed is less than 20s in most cases. If the hardware is greatly improved, the execution time of the proposed mechanism can be reduced to within the acceptable range.

Conclusion

Cloud computing can integrate the distributed resources in the network and provide service to users. So a resource allocation mechanism is needed to reasonably allocate the idle resources. In this paper, MVO algorithm and DMAA mechanism are adopted to design and simulate a cloud resource allocation mechanism. In the proposed mechanism, RP and RC use SVM algorithm to predict the price and submit the tenders to AO . AO comprehensively analyzes the price attribution and non-price attributions of both traders and uses the BP neural network algorithm to transfer the non-price attributions to the quality index. To effectively allocate the resources and maximize the total satisfaction of both traders, the problem of optimal cloud resource allocation is transformed into the optimization problem of maximizing the total satisfaction. And MVO algorithm is utilized to obtain the optimized cloud resource allocation scheme. Simulation results have shown that the proposed mechanism is feasible and effective for increasing the resource utilization rate and satisfying the demands of users. It constitutes our future work to implement and test the mechanism in the actual system so as to further improve the practicality of the model and the algorithm.

Fig. 1

 1 Fig. 1 System framework

,,

  fx  which can express the mapping relationship be- tween x and y . Then we can adopt   , fx  to predict y when given x .

Fig. 2

 2 Fig.2The comparison of resource utilization rate

Fig. 3

 3 Fig.[START_REF] Lan | Multi-unit continuous double auction based resource allocation method[END_REF] The comparison of the amount of resource consumers whose demands are satisfied

Fig. 4 .

 4 Fig. 4. The comparison of the execution time

3 Auction Model 3.1 Resource Provider Multi-Attributions of Resource Provider. When

  task expected finished time, task latest finished time, task length and deal time. RP 's level of delivery for

						analyzing	RP 's trading behavior,
	we put forward three non-price attributions including	RP 's quality of service (	QoS ),
						S
	level of delivery (	LoD ) and level of spiteful quote (
				S
	Quality of Service.	QoS is used to measure the quality of the resources that	RP pro-
					S
	vides.	 1,2,3, , gM  i		represents the grade that the i-th resource consumer (	i RC )
	gives to RP where M is the total amount of	RCs . RP 's quality of service in this trans-
	action (	this QoS ) is defined as in Eqn.(1) .
		S
						QoS	1 Si 1 M this i g   	(1)
						M
	Devote RP 's quality of service for the last	H transactions by	old QoS , so after this
						S
	transaction,
						QoS	S		1 SS old this QoS H H QoS  	(2)
	Level of Delivery.
						i TEFT ,	i TLFT , i TL and	i DT respectively repre-
						B	B	B
	sent

S LoSQ ).

S

QoS is defined as in Eqn.

[START_REF] Danak | Efficient bidding in dynamic grid markets[END_REF]

.

S

LoD is used to check whether or not RP delivers the usage rights of the resources to RC on time. i RC 's

Provider. i

			X EDP and	X RP are the ex-
			S	S
	pected deal price and reserve price of this kind of resource respectively that	RP wants to
	sell.	, iX DP is the deal price and	, iX IoQ represents the quality index which is calculated
			B
	in Sect.5. , iX S represents the satisfaction which is specified in Eqn.(6) .
		S

S

S is the satisfaction of RP when transacting with i RC .

X represents a kind of resources that RP sells. , , ,

  is the smoothing coefficient and 01   .

	The structure of	RP 's training samples is consisted of	RP 's quality index (	IoQ ),
					S
	reserve price (	RP ), the relationship between supply and demand (	SD ), remaining
		S
	sale amount (

S RSA ) and predicted sale price ( PSP ). The structure of RC 's training samples is consisted of RC 's quality index ( B IoQ ), reserve price ( B RP ),

Table 1 .

 1 Relative Parameters to BP Neural Network Algorithm

	Relative parameter	Value
	Input layer node number	1
	Hidden layer node number	20
	Output layer node number	1
	Error threshold	0.01
	Number of training samples	400
	Maximum iteration time	1000

Table 2 .

 2 Relative Parameters to SVM Algorithm

	Relative parameter	Value
	Error threshold	0.01
	Penalty coefficient	100
	Regularization parameter	100
	Maximum iteration time	1000

Table 3 .

 3 Relative Parameters to MVO Algorithm

	Relative parameter	Value
	Scale of n-best population	10
	Dimension of the solutions	4
	Dimension of variation	3
	Asymmetry factor	0.1
	Maximum iteration time

Table 4 .

 4 Prices of Cloud Servers

		Server Size			Linux		Windows
	RAM	Disk	Network Bandwidth	Hourly	Estimated Monthly	Hourly	Estimated Monthly
	256MB	10GB	10Mbps	$0.010	$7.30	-	-
	512MB	20GB	20Mbps	$0.020	$14.60	-	-
	1024MB	40GB	30Mbps	$0.040	$29.20	$0.053	$37.96
	2048MB	80GB	40Mbps	$0.080	$58.40	$0.106	$75.92
	4096MB	160GB	50Mbps	$0.160	$116.80	$0.212	$151.84
	8192MB	320GB	60Mbps	$0.320	$233.60	$0.424	$303.68
	15872MB	620GB	70Mbps	$0.640	$467.20	$0.848	$607.36
	30720MB	1200GB	80Mbps	$1.217	$876.00	$1.606	$1156.30

Acknowledgements

. This work is supported by the National Science Foundation for Distinguished Young Scholars of China under Grant No. 61225012; the National Natural Science Foundation of China under Grant No. 61070162, No. 71071028 and No. 70931001; the Specialized Research Fund of the Doctoral Program of Higher Education for the Priority Development Areas under Grant No. 20120042130003; the Specialized Research Fund for the Doctoral Program of Higher Education under Grant No. 20100042110025 and No. 20110042110024; the Specialized Development Fund for the Internet of Things from the ministry of industry and information technology of the P.R. China; the Fundamental Research Funds for the Central Universities under Grant No. N110204003 and No. N120104001.


K D A K S Perera

T Kishanthan

H A S Perera

D T H V Madola

Malaka Walpola
email: malaka.uom@gmail.com

Srinath Perera
email: srinath@wso2.com

Mahasen: Distributed Storage Resource Broker

Modern day systems are facing an avalanche of data, and they are being forced to handle more and more data intensive use cases. These data comes in many forms and shapes: Sensors (RFID, Near Field Communication, Weather Sensors), transaction logs, Web, social networks etc. As an example, weather sensors across the world generate a large amount of data throughout the year. Handling these and similar data require scalable, efficient, reliable and very large storages with support for efficient metadata based searching. This paper present Mahasen, a highly scalable storage for high volume data intensive applications built on top of a peer-to-peer layer. In addition to scalable storage, Mahasen also supports efficient searching, built on top of the Distributed Hash table (DHT)

Introduction

Currently United States collects weather data from many sources like Doppler readers deployed across the country, aircrafts, mobile towers and Balloons etc. These sensors keep generating a sizable amount of data. Processing them efficiently as needed is pushing our understanding about large-scale data processing to its limits. Among many challenges data poses, a prominent one is storing the data and indexing them so that scientist and researchers can come and ask for specific type of data collected at a given time and in a given region. For example, a scientist may want to search for all Automated Weather data items collected in Bloomington area in June 15 between 8am-12pm.

Although we have presented meteorology as an example, there are many similar use cases. For instance, Sky server [START_REF] Alexander | Designing and Mining Multi-Terabyte Astronomy Archives.: The Sloan Digital Sky Survey[END_REF] is one of the best examples that illustrate the use case of large data generation. This project expects to collect 40 terabytes of data in five years. In its data collection, the photometric catalog is expected to contain about 500 distinct attributes for each of one hundred million galaxies, one hundred million stars, and one million quasars. Similarly many sciences, analytic processing organizations, data mining use cases etc., would want to store large amount of data and process them later in a selective manner. These systems often store data as files and there have been several efforts to build large scale Metadata catalogs [START_REF] Baru | The SDSC Storage Resource Broker[END_REF][3] and storage solutions [START_REF] Decandia | Dynamo.: Amazon's Highly Available Key-value Store[END_REF] [START_REF] Ghemawat | The Google File System[END_REF] to support storing and searching those data items. One such example is AMGA metadata catalog [START_REF] Nuno | Distributed Metadata with the AMGA Metadata Catalog[END_REF] which was an effort to build replication and distribution mechanism for metadata catalogs.

As we discuss in the related work section, most of the metadata catalog implementations use centralized architectures and therefore have limited scalability unlike Mahasen. For example, Nirvana Storage [START_REF]Nirvana Storage -Home of the Storage Resource Broker (SRB®)[END_REF] has a centralized metadata catalog which only supports scalability through vendor's mechanism such as Oracle Real Application clusters. XML Metadata Concept catalog (XMC Cat) [START_REF]XML Metadata Concept Catalog (XMC Cat), Data to Insight Center[END_REF] is another centralized metadata catalog which stores hierarchical rich metadata. This paper presents Mahasen, a scalable metadata catalog and storage server built on top of a P2P technology. Further, it is built by distributing an open source centralized Data registry (WSO2 Registry).

Mahasen (Distributed Storage Resource Broker) is a Data Grid Management System (DGMS) that can manage a large volume of distributed data. It targets high volume data intensive applications. The architecture of Mahasen has been designed to present a single global logical namespace across all the stored data, and it maintains a metadata structure which can be used to search files based on its' attributes. It is a network of storage servers that plays the dual purpose of a metadata catalog and a storage server. Mahasen will solve the huge data storage problem and fault tolerance in data intensive computing through aggregating low cost hardware while having both metadata and actual resources distributed without single point of failure. Metadata management will ensure the capability of searching files based on attributes of the stored resources. Mahasen has a metadata catalog, which is highly distributed and well scalable. The metadata layer ensures fault tolerance by keeping replicas of metadata. The rest of the paper is organized as follows. The next section will discuss the related work in Metadata catalogs and Storage servers while comparing and contrasting them with Mahasen. The following section will discuss Mahasen architecture. The next section will present the performance evaluation of Mahasen. Finally the discussion section discusses limitations, other potential solutions and directions.

Related Work

Nirvana Storage

Nirvana SRB [START_REF]Nirvana Storage -Home of the Storage Resource Broker (SRB®)[END_REF] is a middleware system that federates large heterogeneous data resources distributed across a network. The ability to access, manage, search and organize data across the entire SRB Federation is provided via a Global Namespace. MCAT is the centralized metadata repository which maintains two types of recordssystem-and user-metadata. Scalability of MCAT is achieved using database vendor's mechanisms [START_REF]Nirvana Performance[END_REF], hence limited by Relational DB scalability Limits.

Storage/Replication. The stored resources are divided as Physical resources, Logical resources and Cluster resources. Replication of resources across multiple servers ensures the availability and recoverability of resources during failovers.

Retrieve. Data stream routing is handled by SRB and TCP/IP, making the data transfer process transparent to the users..

Search.

Searching is done based on metadata attributes which are extracted and managed by the SRB.

Add/Update. Data can be added in two ways: Registration and Ingestion. Registration does not transfer any data but only creates a pointer to the data in MCAT. Ingestion is similar to registration but also transfers the data to an SRB storage resource.

Delete. If a file shadow object is used as a data object to ingest a file resource to SRB then file will be removed from MCAT but not from the physical location.

Apache OODT

OODT [START_REF] Apachetm | [END_REF] is a middleware system for metadata that provides transparent access to the resources. It facilitates functionalities such as store, retrieve, search and analyze distributed data, objects and databases jointly. OODT provides a product service and profile service which manage data and metadata respectively. Storage/Replication. OODT stores data product in a file-based storage in a distributed manner. They classify storage into three categories: on-line, near-line or off-line storage.

Retrieve. When OODT receives a request for retrieving a file, it issues a profile query to a product server that helps in resolving resources that could provide data. The response will include the target product server address in the form of a URI. The OODT issues a product query based on the profile query results to get the data, and it will actually retrieve data from the product server in a MIME-compliant format.

Search. OODT uses the profile server and the product server for searching the metadata and retrieve the products, and it has multiple of each type of server. OODT is based on client server architecture and it promotes REST-style architectural pattern for search and retrieve data. The profile or a subset of profile is returned for retrieval.

Add/Update. OODT provide data management including manage files and folders with the implementation of javax.sql.datasource interface.

Delete. The file management component of a Catalog and Archive Service support the delete of resource files and metadata through the implementation of javax.sql.datasource interface.

WSO2 Governance Registry

WSO2 Governance Registry [START_REF]WSO2 Governance Registry -lean.enterprise.middleware -open source SOA[END_REF] is a repository that allows users to store resources in a tree-structured manner, just like with a file system. However, unlike a file system, users may annotate resources using their custom properties, and also WSO2 Registry has built in metadata management features like tagging, associating resources.

However, WSO2 registry is backed by a Relational Database system, and it uses database features to store data, metadata, to manage them, and to search. Hence it has a centralized architecture. Mahasen extends that architecture to a distributed architecture.

Replication.

There is no inbuilt mechanism to do the replication of resources in WSO2 registry.

Search. The WSO2 registry provides two types of searches. One is searching for a resource with their name, metadata etc., and it is implemented using underline relational database system. The second one is searching the content of resources, and implemented using Lucene [START_REF]Apache Lucene -Overview[END_REF]. The second search is only applicable to resources with textual content. Add/Update. Adding of resources to registry can be done in two ways. First one is adding via the web interface provided by the registry. When adding a new resource, it is also possible to add additional metadata such as tags, properties of name value pairs, which later will be useful to search for that resource. The other way to add resources is by writing your own way by extending the registry API and exposing it as a web service.

The major limitation with registry, when storing resources, is the amount of memory available. Since it uses the java heap memory to buffer the resources before storing them, large files cannot be stored as the available memory is only limited to few hundred of megabytes.

Hadoop Distributed File System

Apache Hadoop Distributed File System is (HDFS) [START_REF]HDFS Architecture Guide[END_REF] is a file system designed to run on commodity hardware. HDFS has a master slave architecture that consists of a single NameNode as master and number of DataNodes. The NameNode is responsible of regulating access to files by client and managing the namespace of the file system. Generally DataNodes are deployed one per node in the cluster, and is responsible of managing storage attached to that node.

Storage / Replication. Hadoop supports hierarchical file organization where user can create directories and store files. It splits the file in to chunks with the default size of 64MB and stores them as sequence of blocks, and those blocks are stored in underlying file system of DataNodes. Those blocks are replicated for fault tolerance and the block size and the replication factor of data are configurable.

Retrieve. Applications that run on HDFS need streaming access to their data sets. Data nodes will be responsible for the read requests that issued from a user to retrieve data from the system.

Search. Hadoop Distributed File System does not provide a comprehensive search for users or applications, and it just fulfill the requirement of a distributed file system by supporting to locate the physical location of the file using the system specific metadata.

Add/Update. Writing to HDFS should be done by creating a new file and writing data to it. Hadoop addresses a single writer multiple readers' model. Once the data is written and file is closed, one cannot remove or alter data. Data can be added to the file by reopening the file and appending new data.

Delete. When a file is deleted by a user or from an application, the particular resource is not immediately removed from HDFS. The resource will be renamed and copied in to /trash directory giving the possibility to restore as long as it remains in the trash.

Mahasen's main differentiation from above systems comes from its scalability. It can scale significantly than Nirvana Storage that depends on relational databases to scale the system, since the Mahasen metadata layer is natively distributed using a DHT.WSO2 Registry provides the clustering as the scalability option, but it is not optimized for large file transfers and storing as it uses an ATOM based resource transfers. Furthermore, Mahasen provides users a comprehensive metadata model for managing the distributed resources they stored with user-defined metadata, unlike the HDFS, which only focuses on creating a Distributed file system. Further Mahasen's metadata layer is natively distributed and fault tolerant while HDFS has a single name node which can make fault tolerant only with an active passive failover configuration.

High Level Architecture

Mahasen High Level Architecture

As shown by Figure 1, Mahasen consists of several storage nodes which are connected as peers to a logical ring via FreePastry. Each node consists of a registry to store metadata and a file system to store physical file parts. Once connected to the ring each node contributes to the metadata space as well as file storage capacity, scaling the system dynamically with new node additions. Nodes use underline DHT (FreePastry) routing protocol to communicate efficiently with each other.

Fig. 1. Mahasen High Level Architecture

Mahasen uses a WSO2 registry and the file system in each node and DHT based architecture is used to connect the nodes to a one unit.

Mahasen has a distributed metadata layer that stores data about the distributed files in Mahasen peer to peer network. The metadata catalog is used to broker the stored resources in the network and to assist the user to locate the files in Mahasen distributed environment abstracting the metadata management from the user.

Mahasen stores two main types of metadata, which are system-defined metadata and user-defined (descriptive) metadata. System defined metadata is mainly used for server side resource handling. File name, file size, stored node IPs of file are examples of the system-defined metadata. User defined metadata is used to provide users the searching capability on those metadata. User can add tags and properties (name, value pairs) to the files that are uploaded.

Fig. 2. Metadata Object Structure of Mahasen

When a file is uploaded connecting to a Mahasen node the file will be temporarily saved in that node. Then the node will act as the master node and split the file into pre-defined sized chunks and the split parts are stored in a selected set of the neighborhood nodes of master node through parallel transfer. Then the metadata object created by master node will be stored with replicas using PAST storage implementation of Free pastry. We have rewritten PAST node's persistent storage such that the data will be stored in the WSO registry in that node.

After storing the metadata, the nodes that received file parts act as worker nodes and replicate their file parts in parallel according to the replicate request issued by the master node. Each worker node will update the metadata object with stored locations of the file parts which were replicated after replicating their file parts using the capability of concurrent access to metadata objects, and Mahasen handles them using the locking system provided by the lock manager of DHT.

User can request to download a file from any Mahasen node and the node will first generate the resource ID for the requested and retrieve the metadata object. Then it extracts the locations of Mahasen nodes that contain the file parts from the metadata object and retrieve those parts to the local machine. The parts will be merged to create the original file after retrieving all the parts and the file will be streamed to the user.

Deletion can be performed with a single command across a heterogeneous storage system. When a delete request for a file is issued, by following the same method of retrieving the file, Mahasen finds nodes that store parts of the file and deletes them. Finally the metadata object will also be deleted with replicas When user needs to update the user-defined metadata, the node that receives the update request retrieves the metadata object for the file from the DHT, updates it, and stores it back in the DHT. . Using this model, Mahasen has built a complete decentralized metadata system that handles metadata management in a highly scalable and efficient manner.

Mahasen keeps replicas of both actual files and metadata objects. The main purpose of keeping replicas is for fault tolerance and failover recovery. We ensure the high availability of metadata while ensuring the scalability using free pastry's underlying DHT.

Mahasen Search

When the amount of data in the system grows, the complexity of the search increases. Mahasen builds a distributed data structure using the underlying DHT, which can improve the performance of different search options that Mahasen supports.

The resources in Mahasen are associated with metadata and for each tag or property in system, we maintain an index pointing to all resources which have that tag or property. This is implemented as a TreeMap [16] and the property trees are stored in the DHT which handles replicas of it.

Fig. 3. A Property Tree Stored in Mahasen Memory Storage

When a user sends a search request, Mahasen extracts the requested search and initiate the execution of relevant search method. Then the resource IDs of the files which match with the given input are retrieved from the relevant property tree. Extracting the relevant resource IDs are done as follow.

Users can send search requests to any Mahasen node, and when a node receives a search request, Mahasen takes the property name given by the client and generates the property tree ID for that property. If the current node has the index for the property, it receives matching resource IDs for that property and sends them to the client. If not, the node acts as a master node and gets the node handles of the nodes which are having the specific property tree and routs Mahasen search messages with the required parameters to the node handles. Then those node handles will get the relevant resource IDs from the property trees in their memory storage and send back to the master node.

The property values in the property tree are sorted, so that if the search is a range based search, we can simply take the sub map between the initial and final property values and retrieve the set of resource IDs mapped to each of the node in the sub tree. Since these resource IDs represents the files having the given property values, Mahasen can look up for the metadata objects with those resource IDs and extract the file names to present to for the user. The operation of extracting the file names for the resource IDs has a high cost than extracting the matching resource IDs for the given search query.

Complete Data Structure built for Mahasen can support property based search, range based search, tag based search and Boolean operations for the properties such as AND operation and OR operation. The advanced search provided by Mahasen is capable of providing the search based on set of different properties and tags.

Mahasen Search utilizes the continuation model support by FreePastry in results retrieving and transferring. Therefore when a search request is issued, the application sends requests to look up node handles, which contain the particular TreeMap object to request results. Then the application will collect the first result incoming and resume action from the previous execution point.

File Handling

File Transfer. Mahasen is a network of storage nodes and users will be given a client which is the Mahasen Client to access and transfer files to the network. The Mahasen Client that is built using the Apache HttpClient [START_REF]HttpClient -HttpComponents HttpClient Overview[END_REF] uses HTTP methods for transferring files to the network. First the client initiates a connection with one of the node in the network. An authenticated client is capable of uploading downloading, deleting, updating or searching for the files in the network. The File content will be added as an entity to the HTTP POST method and streamed to the target address. The receiving end will read the file stream and write it to the repository.

Replica Management. To achieve fault tolerance and failover recovery, the file will be split into a set of predefined chunks and each part will be replicated and stored in different nodes according to predefined replication factor. The placement of replicas is a critical part which affects the reliability and performance of the system. The purpose of having a policy for placement of replicas is for data reliability, availability, and network bandwidth utilization. The current policy of Mahasen is to store the replicated files in leaf nodes set to the initial node. The selection of nodes in the leaf set will be calculated using cost evaluation function which focus on the distance of the node.

After successfully transferring the file to the initial node, the client will be notified about the status of the file transfer and initial node will then replicate and transfer the file to other nodes. The number of copies kept for a file is called the replication factor of that file and will be decided by the Mahasen system.

File Splitting and Parallel transfer. Mahasen storage network is designed to store large files reliably across distributed nodes. When storing the file it will be split into blocks of fixed size and these blocks will be replicated across the network for fault tolerance. The transferring of replicated file blocks will be done in parallel to other nodes in order to utilize the bandwidth and to save time.

When focusing on the retrieval of a file by using the metadata object the system will then select a node which is closest to the reader node and download the blocks to the client. Downloading of file blocks will also be done in parallel and then the blocks will be merged to create the complete file.

Mahasen API

Mahasen provides a complete API to perform CRUD operations and search. Users can develop external clients apart from the default client Mahasen provides and integrate with existing systems to perform resource management and search operations.

Performance Analysis

The Mahasen System Scalability was tested by running a system with M nodes and N parallel clients. Here the value for M was 1, 6, 12, 18, 24 and N was 1, 5, 10, 15, 20. Each client carried out upload, download, delete and search operations for 10 times and the average was taken. The system configuration that was used in this test are, Two machines with Intel(R) Xeon(R) CPU E5-2403 1.80GHz 4 Core machines having 24GB RAM and One machine with Intel(R) Xeon(R) CPU E5-2470 2.30GHz 8 Core machines having 63GB RAM. Following Figures (from 4 to 7) depicts the results of this test. In the upload test, 500MB size files were used by each client. .

Fig. 4. Upload test results

In the results it is observed that when the number of client increases, the upload time is also increasing. We believe that this is due to the network congestion and background processes of data replication across nodes. When the number of nodes increased to 18 or 24, a reduction in upload time were observed. This was an expected behaviour, because the node which client selects to upload, distributes replica management task for other nodes in the p2p ring.

Fig. 5. Download test results

When download files using Mahasen client, it is observed that with the increase of number of client, the single node setup has a significant growth in the download time. In the performance test, a single node was chosen to send the client request while it coordinates the file transfer from other nodes in the setup. Therefore when there are multiple nodes in the system you can download file parts from other available nodes, which reduces the download time.

Fig. 6. Delete test results

When Mahasen performs a Delete on a resource, it involves 3 operations such as deleting metadata, deleting entries from search index, and deleting the physical file. When more nodes are in the system, each node can participate in deleting its own files in parallel, making the system more scalable and efficient.

Fig 7. Search test results

Search results illustrate that Mahasen can perform well even with more nodes added to the system. Usually single node should have the lowest possible time as it does not have to search across the p2p ring. But with multiple nodes, it has to aggregate results and present it to the client. This can be observed from the figure that, when more clients are in the system, results tend to converge into a lower value due to caching as we requested search operation through the same node.

Discussion and future work

Mahasen provides a highly scalable metadata structure with its peer-to-peer architecture in the metadata catalog. Unlike the existing metadata catalogs that use centralized architecture, Mahasen distributes metadata across the nodes in the system with the replication making the overall system scalable and fault tolerant.

Mahasen keeps replicas of both metadata objects and property trees as well. The DHT of FreePastry is used to store these objects in the system which provides easy access of them. Keeping replicas of metadata objects and property tree objects do not cost as much as keeping replicas of actual files which are very large in size compared to metadata and property tree objects. By having these objects with replicas in the system, Mahasen has been able to ensure the correct functioning of many of the Mahasen operations even in the conditions like node failures.

An important contribution of Mahasen is developing a distributed indexing structure on top of the DHT for searching data products using different properties associated with data products. Since Mahasen needed to support range based queries, we evaluated earlier effort to build such index structures. Skip Tree Graph [START_REF] Gonz´alez Beltr´an | Skip Tree Graph: a Distributed and Balanced Search Tree for Peer-to-Peer Networks[END_REF] was one of the best candidates we selected for search assisting data structure, which can efficiently support range based queries over a DHT. Since we had different properties and data structure had to grow in two dimensions, one in number of properties and the other one in number of entries for one property we were forced to create different DHTs for different properties. Therefore we needed to evaluate a much less complex solution since maintaining different DHTs could have been very expensive in terms of resources.

When the system scales up with the large number of nodes, it will be more costly to issue a search operation on the available raw metadata stored. Therefore Mahasen developed a combined data structure with DHT and TreeMap as explained earlier.

When a Mahasen node fails, and it is detected by the existing nodes in the network, Mahasen replicates all the metadata objects and the property tree objects which were in the failed node to the existing Mahasen node reading them from other replicas. Mahasen helps in preserving the availability of metadata objects and property tree objects by maintaining the replication factor of them a constant.

Current Mahasen design has several limitations, which we plan to handle as future works. Currently Mahasen stores each property indexes in one Mahasen node and assumes that it will fit within the memory of that node. This may not be major concern for simple cases, and even NoSQL storages like Cassandra makes similar assumptions. Dividing the property tree into parts and storing them in different nodes when it is larger than a given size can solve this problem. We can predefine the maximum size of a part that will be residing in one node.

Another challenge is that search based multiple properties where at least one is a common property would force Mahasen to join large data sets, and one potential solution is to negotiate the size of data sets before start the data merging.

To summarize, Mahasen project builds a scalable storage solution by making a group of existing open source registries work as a one unit. It provides a one logical global namespace, and users may talk to any node of the group and perform any operations.

Mahasen connects nodes (registries) using PAST, a storage overlay implemented on top of Pastry DHT algorithm. Furthermore, Mahasen builds a distributed indexing structure on top of DHT to support property-based search of data items.

A user can benefit from the Web Service API provided and effectively utilize for batch processing of file uploading task through a custom client or basic client provided by Mahasen.


Qiuming Luo

Yuanyuan Zhou

Chang Kong

Guoqiang Liu

Ye Cai
email: caiye@szu.edu.cn

Xiao-Hui Lin

Analyzing the Characteristics of Memory Subsystem on Two different 8-way NUMA Architectures

Keywords: Memory subsystem, NUMA, Global Queue, Crossbar switch

Two NUMA architectures with different memory subsystems are experimentally analyzed in this paper. By applying the benchmark with various access patterns, it shows much different characteristics of memory system between Xeon E5620 with Global Queue and LS 3A with typical crossbar switch. The experiment results reveal the fact that LS 3A and Xeon E5620 have some similar features. Our study also showed some other diverse features of these two platforms: due to the different contention locations and mechanisms, the memory access model for E5620 doesn't fit for LS 3A. Through comparing, we find that one advantage of LS 3A is that it can obtain steady bandwidth on both local and remote thread, and it is more fair for local and remote access under some circumstances. Another fact is that LS 3A is not such sensitive to remote access, compared with E5620, so there will be no obvious performance degradation caused by non-local memory access.

Introduction

With the increasing number of processor cores on one single machine, memory bandwidth has become the main bottleneck of computer system. Instead of using faster and bigger processor caches, NUMA has reduced the memory bandwidth issue by using asymmetric hierarchical memory model. A NUMA system contains some processors, caches, memory controllers and memory banks, using connection technologies provided by AMD's HT (HyperTransport) [START_REF]AMD HyperTransport Technology-based system architecture[END_REF] or Intel's QPI (Quick Path Inter connect) [START_REF] Maddox | A first look at the Intel QuickPath Interconnect[END_REF] to connect with each other. Due to the NUMA factor, when a process access local memory or remote memory, they have different access delay and bandwidth. To obtain the optimal performance, previous optimization work on NUMA platform often schedule the process, move data from remote to local to maximize the local accesses. Some of these are based on analysis after execution [START_REF] Li | Locality and loop scheduling on NUMA multiprocessors[END_REF][4] [START_REF] Mccurdy | Memphis: Finding and fixing NUMA-related performance problems on multi-core platforms[END_REF], while others can dynamic deal with it during execution [START_REF] Ogasawara | NUMA-aware memory manager with dominant-thread-based copying GC[END_REF][7] [START_REF] Tikir | Hardware monitors for dynamic page migration [J][END_REF][9] [START_REF] Wilson | Dynamic page placement to improve locality in CC-NUMA multiprocessors for TPC-C[END_REF]. Instead of just observing local or remote memory access, the studies have made deep analyze of the inner memory controller architecture in recent two years. And they found that under some circumstance decreasing data locality may procure better performance [11][12]. This kind of study involves the detail behaviors and architecture of memory controller and it is more applicable to real application environment. After all, entirely local or remote access is not common in real applications. When we study the memory bandwidth on NUMA platform we need to consider both memory layout and the contention of local and remote memory access. We need to understand its architecture features through experiments to take full advantage of these CPU's underlying hardware power.

In this paper, we test two NUMA platforms, consisted of LS 3A processors and Intel Xeon E5620 processors, to characterize their memory performance. Then we analyze their similarities and differences, merits and shortcoming based on their difference architectures. At last, we propose a guideline to obtain best performance when using NUMA system consisted of these two processors.

Experimental Setup

In this section we describe the architecture details of the evaluation systems, the benchmark programs, and the experimental methodology used.

Hardware

LS 3A used in our work is an experimental CPU made by Institute of Computing Technology (Chinese Academy of Sciences). The NUMA platform made by LS 3A is consisted of dual-processors and it use HT to connect with each other. As shown in Fig. 1(a), for each processor, the first level crossbar switch X1 connected with four 64bit superscalar GS464 high performance processor cores (P0-P3),four 1MB shared second level cache (we can also call it LLC, Last Level Cache), the two ports of HT used to connect with IO or other processors. The second level crossbar switch X2 used to connect LLC and 2 memory controllers MC0 and MC1, which also called IMC(Integrated Memory Controller). Each MC is connected with 2GB DDR2 memory, and the total memory of the system is 8GB. The frequency and width of the HT on this main board is about 200MHz and 8-bit (it can work on 800MHz and 16-bit). Two 64-bits 400MHz DDR2 controller can provide total bandwidth about 6.4GB/s. The 8 processor cores will share the L2 cache. When doing remote memory access, they go through the remote crossbar switch X1 and X2. Intel named LLC, local and remote arbitrate queue and IMC as uncore unit, and it corresponds to the part surrounded by dotted line square in Fig. 1.

(a) LS 3A (b) E5620

Fig. 1 NUMA system consisted of dual-processors In this architecture, a memory access may reach different components, such as local cache, remote LLC (L2), local memory or remote memory. And IMC also can deal with request from other nodes. So they need the support of request queuing and arbitrating mechanism. According to the official material, LS 3A use the HT port to send remote memory access request and it will contend the X1 switch network with native memory access request issued by the 4 local processor cores (include direct access to DDR and those access the LLC). And there is no detail explanation about how it arbitrates the request, so we need to figure out its inner mechanism through experiments. But from the architecture we can tell it is much different about remote memory access and local memory access path from Intel Xeon E5620. The later NUMA system is illustrated as Fig. 1(b), the QPI connection, processor core and LLC layout is different from LS 3A. In E5620, the processor cores shared the L3 cache, GQ (Global Queue) is used for dealing with request from L3 cache, IMC and QPI. IMC have 4 channels and is used to connect 4 DDR3-1066 (2GB each, the total memory is 8GB). It can provide 25.6GB/s peak bandwidth. Two QPIs separately used for connecting with I/O and processors, the unidirectional peak bandwidth is 11.72GB/s and the bidirectional peak bandwidth is 23.44GB/s

The uncore unit in Intel E5620 processor is shown in Fig. 2. It includes 3 components, LLC, IMC and QPI, and connected with each other with GQ. In GQ component (based on crossbar switch), there are 3 queues to deal with the miss request and update request from L2 cache and the remote access request from QPI. These queues' length is 32 items, 16 items and 12 items respectively [START_REF] Levinthal | Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors[END_REF]. Since every memory request goes through GQ, there are many contentions among local memory request and remote memory request on it. And GQ can reserve about 50% bandwidth for remote memory access request (This is the maximum bandwidth of remote memory access). Early version of E5500 reserves less than 50% of total bandwidth. PMU (Performance Monitoring Unit) can used for observing and analyzing performance issues in Intel E5620 [START_REF] Levinthal | Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors[END_REF]. This paper used Intel E5620 for comparison, the same tests will perform on both platform.

Cache plays an important role in memory tests. In order to measure the bandwidth, we need to take advantage of cache and reduce the interference of cache. The detail information of cache on LS 3A is described in [START_REF] Huandong | Interconnection of Godson-3 Multi-Core Processor[END_REF]. LS 3A have implement a nonblocking cache technology. It can support up to 24 misses in LS 3A's cache. The Westmere (Nehalem's successor) core of Intel E5620 has private L1 and L2 cache, four Westmere cores of E5620 shared the L3 cache (LLC). Its non-blocking technology can support up to 16 caches misses. Since LS and Intel have different cache levels, capacity and pre-fetch mechanism, we need to avoid their influence about measuring the bandwidth.

Software and Benchmarks

The Linux kernel on LS 3A platform is Linux 2.6.36, the compiler version is GCC 4.4.5 and the compile parameter is gcc -fopenmp -O3. The Intel platform use Linux 2.6.32 as its kernel and the compiler version is also GCC 4.4.5, the compile parameter is gcc -fopenmp -O3 -mcmodel=medium. This paper use STREAM [START_REF] Mccalpin | Memory bandwidth and machine balance in current high performance computers[END_REF] to test the memory access performance of each processor core, each processor and the whole system. Traid has an intensive memory access cycle. It accesses 3

arrays (a[], b[] and c[])

. Their sizes all exceed the size of LLC, so they can issue enough memory access requests. The kernel cycle of Triad is showed in Fig. 3.

Fig.3 kernel cycle of Triad

In fact, an instance or thread is not able to saturate the maximum bandwidth of IMC, so we can't just use one Triad program to study the memory access characteristic of Intel or LS NUMA systems. Besides, we need to study the memory contention of local request and remote request. We must use at least 2 Triad instances to fulfill our work. So we made some modification on Triad and made it can produce multiple processes or threads to execute concurrently. Through using OpenMP, we can use For direction and static schedule direction to parallelize it, the threads can share the 3 arrays and access their data set alone at the same time. The threads share the arrays, but the processes didn't share any data.

The advantage of Triad is described as below: The first one is that it is cachestarve-style [START_REF] Charles | Evaluation of the Intel Core i7 Turbo Boost feature[END_REF] application and the cache will have steady missing rate, each Triad thread will not influence the cache missing of LLC [START_REF]Intel 64 and IA-32 Architectures Optimization Reference Manual[END_REF]. The second advantage is that 94% to 99%'s read operation will reach the main memory [START_REF] Majo | Memory System Performance in a NUMA Multicore Multiprocessor[END_REF], it will not be impacted by confliction on cache line.

2.3

Measurement and Methodology

We use numactl [START_REF] Kleen | An NUMA API for Linux[END_REF] tool to control the data distribution on every node's memory and bind the threads to corresponding nodes.

To study the interference and contention on IMC and cross-process connection (HT/QPI), we defined three configurations, as fig. 4 shows, about the layout of threads and data. The first configuration put threads in both L(Local, on node0) site and R(Remote, on node1) site, and put all data in L site. The second configuration put threads and data on both nodes in a cross accessing style. The third configuration put threads on L site and issue memory access to both nodes.

Fig.4 threads and data layout configurations

When measuring the memory access bandwidth, it needs to obtain the total number of memory access that arrived IMC and the time elapsed. But we can't get the total amount of memory access direct for the program or source code. The Intel's processor hardware counter can give accurate cache line size, missing rate and processor frequency [START_REF] Majo | Memory System Performance in a NUMA Multicore Multiprocessor[END_REF]. But we haven't got the proper tools for LS 3A to do this, so we use the execution time of Triad as a reference. This is mainly due to Triad has a steady memory access workload, and every data only accessed once, this kind of application's execution time is decided by memory access operation [START_REF] Levinthal | Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors[END_REF]. In addition, both LS 3A and E5620 processor's L1 instruction cache have enough capacity to hold Triad's main cycle instructions, which means fetching instruction will not occupy the memory controller's bandwidth. So we can compute the bandwidth as below:

Bandwidth Bandwidth Bandwidth

Bandwidth Memory Access Size Exe Time MB/s

Due to local process and remote process need different time to finish the workload, the contention will not exist when one of them exit. We execute the processes repeatedly to keep the bandwidth contention. Therefore, the date we get is under contention. The Intel's Nehalem micro architecture use MESIF protocol to keep cache coherent, different access states in cache line will cause different access delay. The states of LS 3A are INV、SHD and EXC, L2 cache use directory to find cache stay in which processor core. Since the modified Triad code doesn't share data, cache line will only exist M, E and I state, we don't have to take the delay variation into account.

At last, Nehalem micro architecture' SpeedStep and Turbo Burst technology [START_REF] Levinthal | Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors[END_REF] can change the clock frequency according to power consumption and fever situation. Therefore we close this function in BIOS to exclude its influence and provide a steady easy measure system environment.

Experimental Data of Memory Performance

We divide the work into several parts. The first test, using Conf.1 configuration, is to measure the local or remote bandwidth from threads on one single node, on both LS and Intel platform. The second one (still using Conf.1) then combines the local and remote access together to show the contention on one IMC. The third test is based on Conf.3 which focus on the total bandwidth of whole system based on the same configuration as previous tests. The forth test is based on Conf.2 which setup a cross accessing scenery. The last one study the confliction of local and remote access issued from same node, using Conf.3. The details are described in following sections.

Local and Remote Bandwidth for One Single IMC

In order to study the behavior of IMC serving the local and remote requests, the first test using conf. 1. In this section (xL,yR) represents the threads binding, x represents the number of local threads (on node0) and y represents the number of remote threads (on node1). There will be x+y threads executing concurrently. The setup of (xL,0R), which means no remote access, is used to measure the local accessing. From Fig. 7(a) we can see the bandwidth of serving the local access on LS platform continues to increase till it reaches the maximum thread number on signal node. And the remote memory bandwidth (with setup of 0L,yR) is about 20% less than local access bandwidth. On Intel platform, it nearly reaches the maximum bandwidth with 2 threads, and the maximum bandwidth of remote memory is 20%~30% less than local memory bandwidth.

The data show that LS can obtain increasing bandwidth with more threads, but Intel can reach the maximum bandwidth with fewer threads. We also measure the remote bandwidth impact by local threads. The details are showed in Fig. 7, where remote thread number varies from 1 to 4 with local thread number varies from 0 to 4. It can say that this case is similar to previous case.

Total Memory Bandwidth

Table 1 is the total memory bandwidth with different (xL,yR) combination under configuration 1. The total memory bandwidth in this table is the normalized sum of local and remote bandwidth. These 2 tables show that on both platform the maximum bandwidth is not at (4L,4R). The maximum for LS platform is at (4L, 3R) and the Intel platform is at (3L,2R). If there are 6 threads, the maximum bandwidth for LS is not at (4L,2R) but at (3L,3R), it is similar on both platforms. From the data we can find that on both NUMA platforms, maximizing local access can't obtain the maximum bandwidth, and when move some threads to remote node may increase the total bandwidth.

Cross Pattern

We place the threads and the data they access on different nodes according to confi-guration2, which is defined by in Fig. 4(b), to check out how the remote access of node0 and node1 interfere with each other. The detail is showed in Fig. 8. On Intel's platform, when there is one opposite thread, the referenced threads' bandwidth will decrease about 30% (except for the case of 1 local threads), and there is not bandwidth lost when the remote thread number increase further. And when there is only one referenced thread, the bandwidth will decrease less than 5%. On LS Platform, the opposite thread impact is much less, with the maximum no more than 10%. This test shows that LS's remote access's influence is much smaller than that of Intel. 3.5

Split Pattern

The last test setup is according to configuration 3 in Fig. 4(c), and we want to check out how the local and remote access of the threads on the same node interferes with each other. We call this access pattern as split pattern. The result is showed in Fig. 9. The Fig. 9(a) and Fig. 9(b) showed that LS NUMA platform have little impact on each other. But Fig. 9 (c) and Fig. 9(d) shows that, on Intel NUMA platform, there is continually impact on local accesses when increasing the remote accesses. The result from split pattern apparently shows that the optimization on Intel's platform will not fit for LS platform.

Discussion and Conclusion

In this section, we first discuss the architectural differences between these NUMAs concerning the memory access, and then try to explain their diverse behavior.

Local threads in E5620 only need to go through GQ and IMC to access the memory, and the remote threads must go through GQ, QPI and IMC to access the memory, as illustrated in Fig. 10(b). The LS 3A local access need to go through X1, X2 and IMC, and the remote access must go through X1, HT, X2 and IMC, as shown in Fig. 10(a). When considering the rate to issue memory access, the individual LS core is not such powerful as E5620 core, because the later can saturate the IMC by only two threads/cores as Fig. 5 shown. The remote access is much slower than local access, on both platforms, due to the overhead of cross-processor interconnection.

When local and remote accesses compete for the same IMC, the LS demonstrates a equally free competition and Intel demonstrates a arbitrated behavior. As Fig. 6 and Fig. 7 shows, the local bandwidth on LS will decrease as more remote competitive threads and vice versa, but the Intel limit the tense of competition to some degree. The arbitrative action on Intel platform will reserve 50%~60% IMC bandwidth for local accessing and 40%~50% for remote accessing, not matter how many threads/cores take part in the competition.

The total bandwidth of two IMCs demonstrates the characteristics that previous study have point out [START_REF] Majo | Memory System Performance in a NUMA Multicore Multiprocessor[END_REF]. As Tab.1 shows, the best performance occurs at (3L,3R)for LS with 6 threads.

For the cross pattern case, there is little contention on LS platform because of the full duplex HT connections, but an obvious contention on GQ in Intel platform. That explain why there is a dramatic drop for Intel and a slightly decrease for LS in Fig. 8.

For the last case of split pattern, there is not variation on LS platform due to the crossbar switch routing, but there is a nearly linear decrease on Intel platform due to the queuing on GQ.

Because of the different philosophies of designing, these two NUMA systems demonstrate apparently diverse behavior of memory subsystem. With GQ might make Intel platform get a better bandwidth and a little longer delay. And the GQ's arbitrative action will contain the competition between local and remote threads. With barely crossbar switch LS allow the free competition and overcome the performance degradation of unnecessary arbitrating (as the cases of cross pattern and split pattern).

When optimizing the memory performance on these platforms, the thread amount, thread binding, and memory layout should be considered with the memory subsystem's characteristics together. The best mapping of thread and data can be found according to the measured data other than barely maximizing the memory locality. Basically speaking, it needs more threads to compete for a higher bandwidth on LS architecture.

Fig. 2

 2 Fig.2 Intel E5620 uncore unit

Fig. 5 2 Fig. 6 .Fig. 6

 5266 Fig.[START_REF] Mccurdy | Memphis: Finding and fixing NUMA-related performance problems on multi-core platforms[END_REF] The memory bandwidth of local and remote access with signal node

Fig. 7

 7 Fig.7 Remote bandwidth impact by local memory contention

Fig. 8

 8 Fig.8 Bandwidth for cross pattern

Fig. 9

 9 Fig.9 Bandwidth for split pattern

Fig. 10

 10 Fig.10 Local and remote access channels (2L,1R)

Table 1

 1 Normalized total bandwidth with different (xL, yR) combination

			(a) LS 3A NUMA
		0R	1R	2R	3R	4R
	0L	0	0.268604753	0.489641936	0.669026213	0.796305483
	1L	0.510155182	0.76435979	0.93206135	1.071639386	1.167414268
	2L	0.807668329	1.077136439	1.21477007	1.061157669	1.327363384
	3L	0.957279374	1.221851671	1.294655035	1.428549427	1.026310918
	4L	1	1.244672139	1.395384964	1.480886933	1.458042771
			(b) Intel E5620 NUMA
		0R	1R	2R	3R	4R
	0L	0	0.469004798	0.675381934	0.714149411	0.718478895
	1L	0.660250795	1.034590501	1.073531914	1.056589576	1.047122689
	2L	0.980231839	1.205814996	1.253073808	1.245351318	1.237903597
	3L	0.989410094	1.18881594	1.260403052	1.252844415	1.243145613
	4L	1	1.059521274	1.057766793	1.029016999	1.021363832

Acknowledgement

The research was jointly supported by project grant from Natural Science Foundation of China under the numbers NSFC61003272, NSFC61171071, grant from Foundation of Guangdong Province and Chinese Academy of Sciences (2011A090100037), and grants from Foundation of Shenzhen City under the numbers JCYJ20120613161137326, JCYJ2012061310222457.