Leonard K M Poon
email: kmpoon@eduhk.hk

GPU-Accelerated Clique Tree Propagation for Pouch Latent Tree Models

Keywords: GPU acceleration, Clique tree propagation, Pouch latent tree models, Parallel computing, Probabilistic graphical models

Pouch latent tree models (PLTMs) are a class of probabilistic graphical models that generalizes the Gaussian mixture models (GMMs). PLTMs produce multiple clusterings simultaneously and have been shown better than GMMs for cluster analysis in previous studies. However, due to the considerably higher number of possible structures, the training of PLTMs is more time-demanding than GMMs. This thus has limited the application of PLTMs on only small data sets. In this paper, we consider using GPUs to exploit two parallelism opportunities, namely data parallelism and element-wise parallelism, for PTLMs. We focus on clique tree propagation, since this exact inference procedure is a strenuous task and is recurrently called for each data sample and each model structure during PLTM training. Our experiments with real-world data sets show that the GPU-accelerated implementation procedure can achieve up to 52x speedup over the sequential implementation running on CPUs. The experiment results signify promising potential for further improvement on the full training of PLTMs with GPUs.

Introduction

Clustering [START_REF] Bouveyrona | Model-based clustering of high-dimensional data: A review[END_REF][START_REF] Jain | Data clustering: A review[END_REF] is a fundamental problem in machine learning. For soft clustering, the Gaussian mixture models (GMMs) are often used [START_REF] Mclachlan | Finite Mixture Models[END_REF]. However, a GMM contains only one latent variable and can produce only a single clustering. This limitation may make GMMs not suitable for modern clustering applications, especially when the data sets contain many attributes and are multifaceted.

The pouch latent tree models (PLTMs) [START_REF] Poon | Variable selection in modelbased clustering: To do or to facilitate[END_REF][START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF] have been proposed as a generalization of GMMs to allow multiple latent variables. They can produce clusterings on multiple facets and are more versatile for data of higher dimensions. They have been evaluated on several real-world data sets and have been shown better than GMMs in terms of model quality and clustering performance [START_REF] Poon | Clustering with multidimensional mixture models: Analysis on World Development Indicators[END_REF][START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF]. However, the structure learning of PLTMs can be more time-demanding than GMMs due to the considerably larger number of possible model structures. For GMMs, the structure learning typically involves only the estimation of the number of the mixture components. In contrast, the structure learning of PLTMs involves determining the number of latent variables, the cardinalities of the latent variables, and the connections among the latent variables and the observed variables. The onerous structure training of PLTMs may pose a serious challenge for applying PTLMs on large data sets. Consequently, previous studies considered data with less than 100 attributes and 2000 samples [START_REF] Poon | Clustering with multidimensional mixture models: Analysis on World Development Indicators[END_REF][START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF]. Those sizes of data sets may be regarded as at most moderate in the Big Data Era.

In recent years, graphical processing units (GPUs) have become more prevalent in scientific computing. They have been demonstrated to achieve significant speedup in different artificial intelligence applications that involve high dimensional data, such as those in the fields of computer vision [START_REF] Grauer-Gray | GPU implementation of belief propagation using CUDA for cloud tracking and reconstruction[END_REF][START_REF] Xu | Belief propagation implementation using CUDA on an NVIDIA GTX 280[END_REF], constraint satisfaction [START_REF] Bistaffa | An efficient approach for accelerating Bucket Elimination on GPUs[END_REF][START_REF] Fioretto | Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs[END_REF], and clustering [START_REF] Al-Ayyoub | A GPUbased implementations of the fuzzy c-means algorithms for medical image segmentation[END_REF][START_REF] Arefin | kNN-MST-Agglomerative: A fast and scalable graph-based data clustering approach on GPU[END_REF][START_REF] Pangborn | Scalable data clustering using GPUs[END_REF][START_REF] Shalom | Graphics hardware based efficient and scalable fuzzy c-means clustering[END_REF].

In this paper, we consider the possibility of using GPUs to accelerate the training of PLTMs. We focus on the clique tree propagation algorithm for performing exact inference during the training process. The inference task is used for computing the likelihood and marginal probabilities on a data set during training. It is the most strenuous one and needs to be called recurrently for each data sample and each model structure. To evaluate the performance of the GPU-accelerated inference procedure, we use it to compute likelihood of a given PLTM on a given data set. This computation requires running inference on each data sample and exhibits resemblances to the other computationally intensive steps for PLTM training. Our study thus constitutes an important first step for using GPUs to accelerate the whole training process of PLTMs to make it feasible for application on larger data sets.

The rest of the paper is organized as follows. First, we review PLTMs and the inference procedure in Sections 2 and 3. Then, we describe the GPU-accelerated inference procedure in Section 4. Next, we evaluate the performance of the procedure in Section 5. After that, we discuss related work in Section 6 and conclude the paper in Section 7.

Pouch Latent Tree Models

A pouch latent tree model [START_REF] Poon | Variable selection in modelbased clustering: To do or to facilitate[END_REF][START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF] is a tree-structured probabilistic graphical model. In the model, each internal node represents a latent variable, and each leaf node represents a set of observed variables. All the latent variables are discrete, whereas all the observed variables are continuous. A leaf node, also called pouch node, may contain a single observed variable or several of them. An example is shown in Figure 1a. In the example model, X 1 -X 9 are continuous observed variables and Y 1 -Y 4 are discrete latent variables. For technical convenience, PLTMs are often treated as Bayesian networks [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF].

Consider a PLTM with observed variables X and latent variables Y . The dependency of a discrete latent variable Y on its parent Π(Y ) is characterized by a conditional discrete distribution P (y|π(y)). Let W ⊆ X be the variables of a pouch node with a parent node Y = Π(W ). The models assume that, given a value y of Y , W follows the conditional Gaussian distribution P (w|y) = N (w|µ y , Σ y ), with mean vector µ y and covariance matrix Σ y . Denote the sets of pouch nodes and latent nodes by W and Y, respsectively. The whole model defines a joint distribution over all observed variables X and latent variables Y

P (x, y) = W ∈W P (w|π(W )) Y ∈Y P (y|π(Y )). ( 1
)
Given a model structure m, the parameters can be estimated by the EMalgorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], which is well-known for estimating parameters of models with latent variables. When the model structure is unknown, a greedy search that aims to maximize a model selection score can be used [START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF].

The GMMs can be considered as a special case of the PLTMs. This is illustrated by the example GMM depicted in Figure 1b. In the figure, all the observed variables X 1 -X 9 in the GMM are drawn as a pouch node, which has a multivariate normal distribution conditional on its parent latent variable Y 1 .

Similar to GMMs, PLTMs can be used for clustering. After training PLTMs on a given data set, the data can be partitioned using each of the latent variables Y . Each data point d can be classified to one of the states of Y by computing the posterior probability P (y|d) based on the joint distribution defined by Eq. 1.

Clique Tree Propagation

Suppose the values of some variables E ⊆ X are observed in a data sample. Inference refers to the computation of the posterior probability P (q|e), where q are the values of some variables Q ⊆ X ∪ Y .

Inference is a core computation task for PLTMs. It is used in the E-step of the EM-algorithm to estimate the values of the unobserved variables. It is also used to compute the cluster assignments after training PLTMs for cluster analysis. The inference task is time-demanding. It is a strenuous task and is recurrently called for each data sample and each model structure during PLTM training. Therefore, it is the first target of optimization for streamlining PLTM training.

Inference can be done on PLTMs similarly as the clique tree propagation (also known as belief propagation or junction tree algorithm) on conditional Gaussian Bayesian networks [START_REF] Lauritzen | Stable local computation with conditional Gaussian distributions[END_REF]. We describe the main steps of the inference algorithm and the numerical operations below. Readers are referred to [START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF] for more details on inference on PLTMs and to [START_REF] Cowell | Probabilistic Networks and Expert Systems[END_REF][START_REF] Lauritzen | Stable local computation with conditional Gaussian distributions[END_REF][START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF] for the general clique tree algorithm.

Construction of Clique Trees. Clique tree propagation requires converting the original model to a structure called clique tree T to organize the computation. Construction of clique trees is simple due to the tree structure of PLTMs. To construct T , a clique C is added to T for each edge in M , such that C = V ∪ {Π(V )} contains the variable(s) V of the child node and variable Π(V ) of its parent node. A separator node is added for discrete node in the PLTM. It is used to connect the two clique nodes containing the separator variable. The resulting clique tree contains two types of cliques: discrete cliques with at most two discrete variables and mixed cliques with a discrete variable and multiple continuous variables.

Propagation. After a clique tree is constructed, propagation can be carried out on it. The clique tree propagation consists of four main steps: initialization of cliques, incorporation of evidence, message passing, and normalization.

Step 1 initializes the clique tree with the model parameters. The mean vectors and the covariance matrices of a pouch node are copied to its corresponding mixed clique. Similarly, the conditional probability table of a discrete node is copied to the corresponding discrete clique. Note that the root node does not have a corresponding clique. Its marginal probability is multiplied to one of the cliques corresponding to its child variables.

Step 2 incorporates the evidence (observed values) in the potentials. For brevity, here we consider only the case where there is no missing value in the data. Consider a pouch node with variables W and with observed values e. Furthermore, denote its parent variable by Y . This step involves computing the probability values P (y|W = e) = N e|µ y , Σ y , where N •|µ y , Σ y denote the normal distribution conditional on the value of Y .

Step 3 performs a series of computations, each on a small part of the clique tree, as represented by the process of message passing. Since the clique tree does not contain any loop, exact inference can be performed by message passing in two phases. In the first phase, messages are passed from the leaf clique nodes to the clique corresponding to the root node of the PLTM. We denote that clique as pivot. In the second phase, messages are passed from the pivot along the opposite direction back to the leaf nodes.

For the mixed cliques, the messages to be sent from the mixed cliques have already been computed in step 2. The message passing between discrete cliques requires performing multiplication and division between potential tables of two variable and message of one variable. It also requires marginalizing out a variable to compute the message of one variable from a potential table with two variables.

After message passing is completed, the likelihood for a data sample can be determined from the pivot clique. The likelihood is equal to the sum of the potential entries of the pivot clique.

Step 4 normalizes the clique potentials by multiplying each entry by a particular constant. It converts the potential values to proper probability values. This entails dividing each entry of the potential tables by the likelihood value.

Implementation for GPUs

In this section, we describe how to adapt the inference of PLTMs for running efficiently on GPUs. We refer to the CPU as host and the GPU as device below.

Data Representation. The original implementation of PLTMs1 used the objectoriented approach to represent the data units as objects. This poses a challenging for GPU programming. Instead, we represent the data units as arrays for easy access by the GPU kernel functions. The data units required for performing inference are shown in Table 1. Each node in a PLTM has a corresponding clique node and a separator node in the clique tree. 2 The third column describes the type of data associated with each clique node. The fourth column indicates the number of entries for each type of data.

Device Memory. The data units in Table 1 are used to store interim computation results during inference. Therefore, a clique tree (with cliques and separators) has to be allocated for each data sample. The data units are allocated at the beginning of likelihood computation so that they are available for the inference on multiple data samples in parallel. The memory is allocated in a single batch to minimize the number of API calls. We also allocate an array on the device for storing the likelihood results computed during inference.

Host-Device Memory Transfer. In the first step of inference, the clique tree needs to be initialized by the parameters of the model. We perform initialization on the host and then transfer the array data representing the initialized clique tree to the device. We transfer only the data corresponding to one instance of the clique tree. The data is then copied to the arrays representing the other instances of clique trees for all data samples on the device. This process saves the amount of data needed to be transferred between host and device. It also simplifies the way to transfer the model parameters to the device as the parameter values are now contained in an array rather than in objects. Besides, the data units representing the clique tree, the data matrix is also transferred to device in a single batch at the beginning to minimize the number of transfers.

Parallelism. Most computation of clique tree propagation for PLTMs is done during the two steps for incorporating evidence and message passing. Such computation involves the calculating multiple entries in a target potential or message. Those entries of a potential or message can be calculated in parallel. We refer to this parallelism as element-wise parallelism [START_REF] Zheng | Exploring multiple dimensions of parallelism in junction tree message passing[END_REF]. However, due to the tree structure of PLTMs, the number of entries of a potential or message is usually small compared to general Bayesian networks. The parallel computation of those entries may not be sufficient to utilize all GPU cores. For example, suppose the latent variables in a PLTM has at most 10 states. Then, the number of entries of a message is at most 10. This is much smaller than the number of cores on a GTX 1080 Ti GPU (3584).

To fully utilize the massive computation power in GPUs, we need to consider other parallelism opportunities. When the likelihood is being computed, the clique tree propagation is performed on each sample independently. Hence, they can be performed in parallel. This form of parallelism is referred to as data parallelism. As a comparison, the number of samples we used in the experiments can be at most 2310. With both data parallelism and element-wise parallelism, the GPU cores can be better utilized.

Host-Device Coordination. Compared with CPUs, GPUs can perform parallel computation very efficiently. However, they have fewer programming language support and programming on them can be tedious. Therefore, we program on the CPUs to mainly determine the sequence of computation and to delegate the highly parallelizable tasks to GPUs. For example, message passing is conducted one node at a time since the message computation needs to follow the aforementioned scheme of flow. We use the host to determine the sequence of the message passing and then invokes the kernel calls for computing the messages for each node. The kernel call is run with multiple threads on different data samples and different elements of messages in parallel.

Device-Host Memory Transfer. The computed likelihood values of the data samples are stored in an array on the device after the clique tree propagation. The array is transferred to the host and the values are then multiplied together on the host to obtain the final likelihood value on the whole data set. It is worthwhile to note that the data structure storing the interim results do not need to be transferred back and forth between the host and the device. This reduces the transfer cost. The same situation also applies for the EMalgorithm. Only the final parameter estimates need to be transferred back to the host. The intermediate values can be kept in the device memory during the different iterations of EM steps. This show one resemblance between the inference procedure and the full PLTM training.

Implementation. We implemented the inference method based on the CUDA framework [START_REF] Sanders | CUDA by Example: An Introduction to General-Purpose GPU Programming[END_REF]. We used the Scala language for host programming and the JCuda package 3 as Java bindings for CUDA. The Java ecosystem was used to reduce the coding effort since the original implementation was written in Java.

Experiments

To evaluate the performance of the GPU-accelerated inference method, we use it to compute likelihood of a given PLTM on a given data set. We ran it using real-world data sets in our experiments. We used the same models and data sets in [START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF] to estimate the actual improvement in practice. Table 2 show the properties of the data sets used. The EAST algorithm [START_REF] Poon | Model-Based Clustering of High-Dimensional Data: Variable Selection versus Facet Determination[END_REF] were used to train PLTMs on those data sets.

Three different implementations of the clique tree propagation were used in the experiments. The first implementation runs sequentially on CPUs. It serves as a baseline for comparison. The second one performs inference on different data samples in parallel on CPUs. The last one uses the GPUs for acceleration as described previously. The experiments were conducted on a Linux computer with a Xeon E3-1245 v5 CPU and a GeForce GTX 1080 Ti GPU. The CPU has fours cores (eight threads) running at a base frequency of 3.5GHz. The GPU has 28 streaming multiprocessors with 3584 CUDA cores running with a maximum clock rate of 1.6GHz. We measure the performance of the three implementations using the elapsed wall time for likelihood computation. We report the time averaged over 100 repetitions. The experiments first ran 20 repetitions at the beginning to allow the just-in-time compiler of the Java Runtime to come into force. Those repetitions were not included for time reporting.

Table 3 reports the average running time for one likelihood computation in milliseconds. The results show that the GPU acceleration could achieve 5x to 52x speedups over the baseline sequential version. It also attained 2x to 12x speedups over the parallel version running on CPUs. The higher speedups over the sequential version were obtained on data sets with larger number of samples (e.g. image, vehicle, wdbc, yeast, and zernike). This can be explained by the fact that the larger number of samples provide better opportunity for exploiting data parallelism by GPUs.

The considerable speedups shown above has demonstrated that the GPUs can be effective in accelerating the inference task. Since the other computationally intensive tasks in the PLTM training procedure show similar parallelism opportunities as the likelihood computation task, our results signify the promising potential for further improvement on the full training of PLTMs with GPUs.

To identify possible bottlenecks of the current GPU implementation, we used the tool nvprof provided in the CUDA Toolkits to profile different kernel calls. Table 4 lists the proportion of GPU activities and overall running time spent on the incorporation of evidence routine. We see that this task constituted most of the GPU activities except on the yeast data set. It even accounted for 86% and 94% of the overall running time on image and zernike, respectively. The two data sets happened to take the longest running time.

To understand this phenomenon, recall that the incorporation of evidence routine for a pouch node has a time complexity linear to the cardinality of its parent variable and cubic to the number of the variables in the pouch node. We compare the model properties on four data sets with similar number of attributes in Table 5. We see that the models for image and zernike both have a large pouch node with 10 and 16 variables, respectively. The problem is exacerbated by the high cardinality of the parent variables of those two pouch nodes. The PLTM for wdbc also has a large pouch node with 10 variables. However, that node has a smaller parent cardinality and the model has small pouch size on average. Hence, the incorporation of evidence routine was less significant on wdbc. Future study may consider how to tackle this bottleneck to make PLTMs more efficient on larger data sets.

Related Work

Several works used GPUs to speed up the EM-algorithm for parameter estimations [START_REF] Araújo | Parallel implementation of Expectation-Maximisation algorithm for the training of Gaussian mixture models[END_REF][START_REF] Kumar | Fast parallel expectation maximization for Gaussian mixture models on GPUs using CUDA[END_REF][START_REF] Machlica | Fast estimation of Gaussian mixture model parameters on GPU using CUDA[END_REF]. They exploited the innate data parallelism due to the independent computation for different data samples. However, they considered only GMMs. The inference procedure on GMMs is simpler than PLTMs. Some works used GPUs for belief propagation on Bayesian networks. Elementwise parallelism and arithmetic parallelism was exploited for inference [START_REF] Zheng | Exploring multiple dimensions of parallelism in junction tree message passing[END_REF] and a statistical model was further proposed for optimizing the GPU parameters [START_REF] Zheng | Optimizing parallel belief propagation in junction treesusing regression[END_REF]. Another work formulated the inference procedure in terms of operations on sparse matrices [START_REF] Bixler | Sparse Matrix Belief Propagation[END_REF]. Existing matrix packages utilizing GPU computation (e.g. PyTorch) were then used to run the inference. Some studies used better memory layout and better scheduling among memory transfers and works to improve the inference performance on GPUs [START_REF] Bistaffa | An efficient approach for accelerating Bucket Elimination on GPUs[END_REF][START_REF] Fioretto | Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs[END_REF]. Some works studied belief propagation on Markov Random Fields used for stereo processing on GPUs [START_REF] Eslami | A GPU implementation of tiled belief propagation on Markov Random Fields[END_REF][START_REF] Grauer-Gray | Optimizing and auto-tuning belief propagation on the gpu[END_REF][START_REF] Xu | Belief propagation implementation using CUDA on an NVIDIA GTX 280[END_REF]. They considered an approximate inference method that requires passing messages to the same nodes multiple times.

The above methods on inference usually achieve significant speedup only when the potential tables have a large number of entries. However, due to the tree structure in PLTMs, the parallelism exploited by those methods may not be as effective on PLTMs. Besides, our work considered data parallelism that were not available as those methods ran inference on only a single data sample.

PLTMs were proposed as a generalization of the latent tree models (LTMs). The LTMs [START_REF] Zhang | Hierarchical latent class models for cluster analysis[END_REF] have discrete observed variables, in contrast to the continuous observed variables in PLTMs. The LTMs have found numerous applications such as density estimation, multidimensional clustering, spectral clustering, and topic modeling [START_REF] Mourad | A survey on latent tree models and applications[END_REF][START_REF] Zhang | Latent tree analysis[END_REF]. Attempts have been made to speed up the training of LTMs. Spectral methods [START_REF] Anandkumar | Spectral methods for learning multivariate latent tree structure[END_REF] and Progressive EM [START_REF] Chen | Progressive EM for latent tree models and hierarchical topic detection[END_REF] have been proposed for faster parameter estimation. Heuristics were proposed to guide the structure learning [START_REF] Wang | Latent tree models and approximate inference in Bayesian networks[END_REF][START_REF] Choi | Learning latent tree graphical models[END_REF][START_REF] Liu | Greedy learning of latent tree models for multidimensional clustering[END_REF] and Stepwise EM was used to reduce the number of samples involved in computation [START_REF] Chen | Latent tree models for hierarchical topic detection[END_REF]. Those attempts did not utilize any parallelism for GPUs. On the other hand, their acceleration techniques can possibly be combined with our proposed method to achieve higher speedups.

Conclusion

In this paper, we show how to use GPUs to accelerate the clique tree propagation algorithm for PLTMs. We use the likelihood computation task to evaluate the performance of the inference procedure. The experiment results demonstrate that substantial speedups (up to 52x) can be achieved. As the other computationally intensive tasks in the PLTM training procedure show similar parallelism opportunities as the likelihood computation task, our results signify promising potential for further improvement on the full training of PLTMs with GPUs. The GPU acceleration techniques discussed in this paper can be crucial in applying PTLMs on massive data sets.

Fig. 1 :

 1 Fig. 1: (a) An example of PLTM. The observed variables are shown in shaded nodes. The numbers in parentheses show the cardinalities of the discrete variables. (b) A GMM depicted as a PLTM.

Table 1 :

 1 Data units for performing inference for each data sample. p denotes the number of variables in a pouch node. c and c denote the cardinalities of the variables of the node and its parent node, respectively, in the PLTM.Complexity. Let n be the number of nodes in a PLTM, c be the maximum cardinality of a discrete variable, and p be the maximum number of variables in a pouch node. The time complexity of the inference is dominated by the steps related to message passing and incorporation of evidence on continuous variables. The message passing step requires O(nc 2 ) time, since each clique has at most two discrete variables due to the tree structure. Incorporation of evidence requires O(ncp 3 ) time. Although the tree structure of PLTMs allows tractable inference, with time complexity linear to the number of nodes, the inference can still needs much time as it has to be performed many times during PLTM training.

	Node Type in	Node Type in	Data Type	Number of
	PLTM	Clique Tree		Entries
	Continuous node	Mixed clique	Mean vector	p × c
			Covariance matrix	p 2 × c
	Discrete node	Discrete clique	Potential table	c × c
	All node	Separator	Message to parent	c
			Message to children	c

Table 2 :

 2 Descriptions of real-world data sets from the UCI repository used in the experiments.

	Data Set	#Attributes	#Classes	#Samples
	glass	9	6	214
	image	18	7	2310
	ionosphere	33	2	351
	vehicle	18	4	846
	wdbc	30	2	569
	wine	13	3	178
	yeast	8	10	1484
	zernike	47	10	2000

Table 3 :

 3 Average elapsed wall time in milliseconds (ms) for computing the likelihood of PLTMs on real-world data sets using different implementations of clique tree propagation, including the sequential version running on CPUs, the parallel version running on CPUs, and the accelerated version running on GPUs. The speedups over the baseline sequential version are shown in parentheses.

		Average running time (ms)
		CPU-Sequential	CPU-Parallel	GPU
	glass	8.62	3.89 (2x)	1.42 (6x)
	ionosphere	48.37	14.67 (3x)	2.76 (18x)
	image	1421.30	290.14 (5x)	27.52 (52x)
	vehicle	169.90	41.54 (4x)	4.89 (35x)
	wdbc	143.04	37.77 (4x)	3.28 (44x)
	wine	7.54	2.94 (3x)	1.44 (5x)
	yeast	50.74	15.06 (3x)	2.07 (25x)
	zernike	2655.91	576.26 (5x)	97.75 (27x)

Table 4 :

 4 Proportion of GPU activities and overall running time used for the incorporation of evidence routine.

		% of GPU Activities	% of Overall Time
	glass	64.81%	3.02%
	ionosphere	82.46%	8.07%
	image	98.94%	86.13%
	vehicle	97.10%	46.26%
	wdbc	84.92%	15.74%
	wine	71.70%	3.32%
	yeast	32.71%	1.49%
	zernike	99.60%	94.25%

Table 5 :

 5 Properties of PLTMs on four data sets. The average and maximum number of variables in a pouch node are listed in the second and third columns, and the cardinality of the parent variable of the pouch node with maximum size in the fourth column.

		Average Pouch	Maximum Pouch	Parent
		Size	Size	Cardinality
	ionosphere	4.6	7	3
	image	3.6	10	11
	wdbc	3.0	10	5
	zernike	7.8	16	6

https://github.com/kmpoon/pltm-east

An exception is that the root node sometimes does not have a separate clique node.

http://www.jcuda.org

Acknowledgement

Research on this article was supported by the Education University of Hong Kong under grant RG70/2017-1018R, the Top-up Fund of Dean's Research Fund, and the Small Research Grant of the Department of Mathematics and Information Technology.


Peng Jiang

Ligang He
email: ligang.he@warwick.ac.uk

Shenyuan Ren

Junyu Li

Yuhua Cui

vGrouper: Optimizing the Performance of Parallel Jobs in Xen by Increasing Synchronous Execution of Virtual Machines

Keywords: Xen, Virtual Machine, Virtualization, Parallel Jobs, Scheduling

Xen is one of the most popular virtualization platforms nowadays, which has been broadly used by the industry. Credit scheduler, the default scheduler of Xen, was initially designed for serial jobs, which achieves good performance overall for serial jobs. Unfortunately, the parallel jobs are likely to co-exist with serial jobs in the same host in practice, the resource contention between virtual machines results in severe performance degradation of the parallel jobs. In this paper, we propose vGrouper, a progressive solution to enhance the performance of the parallel jobs. The vGrouper focuses on synchronizing the execution time of the parallel nodes in order to achieve the best performance of the parallel job. Moreover, the vGrouper guarantees that the parallel job nodes are able to run concurrently on pCPUs for the entire time slice, which maximizes the efficiency of communication between parallel nodes. A prototype of vGrouper is implemented, the experimental results demonstrate that the performance of the parallel job and resource utilization in Xen have been significantly improved.

Introduction

The Xen virtualization platform has been embraced by industry nowadays due to its impressive scalability and outstanding performance. However, the credit scheduler, which is the default scheduling strategy of Xen, has been identified to be less capable of scheduling parallel jobs. A parallel job usually relies on communication between nodes, which is a completely different working fashion from the serial job. Due to the lack of knowledge of the parallel job, the credit scheduler treats the nodes of each parallel job node as a normal serial job, where the particularity of the parallel job is completely disregarded. The shortcoming of credit scheduler has been discussed in several studies [START_REF] Shao | Analyzing and improving mpi communication performance in overcommitted virtualized systems[END_REF][4][2] [START_REF] Ye | Analyzing and modeling the performance in xen-based virtual cluster environment[END_REF].

In this paper, we propose vGrouper, a progressive solution to further enhance the performance of the parallel job to a new level. The vGrouper focuses on synchronizing the execution time of the parallel nodes in order to improve the performance of the parallel job. Moreover, the vGrouper guarantees that the parallel job nodes are able to run concurrently on pCPUs for the entire time slice, which maximizes the efficiency of communication between parallel nodes.

2 Background and Related Work

Credit Scheduler

The credit scheduler, which is a proportionally sharing scheduling strategy based on fair allocation of resource, was initially designed for scheduling serial jobs. Each VM will be given credits to consume during execution, which indicates that how many physical resources a VM can have. There two parameters weight and cap can be used for customizing the bias of resource allocation according to user's need, where the weight indicates the relative proportion of execution time and cap stands for the maximum amount time of execution time of a VM. In credit scheduler, two priorities are used to indicate the status of a VM. U N DER priority is given to those VMs which are remaining credits, while a VM running out of credits is given OV ER priority. Each vCPU of the VM is allowed to executed for a certain time, and the VMs with U N DER priority will be scheduled one by one.

Related Work

Several optimizations have been made to improve the performance of the parallel job in Xen. Chen and et al. found that overcommitted vCPUs brings performance degradations to concurrent jobs in [START_REF] Chen | Scheduling overcommitted vm: Behavior monitoring and dynamic switching-frequency scaling[END_REF], they mitigate the negative impact by adjusting the time length of execution of VMs according to the type of the workload. Shao and et al. also reveal the problem of overcommitted vCPUs in their research and indicate there is potential penalty on the performance of the parallel job in Xen [START_REF] Shao | Analyzing and improving mpi communication performance in overcommitted virtualized systems[END_REF], they choose to expose the workload types of VMs to Xen hypervisor to alleviate the decrease of the performance of the parallel job.

Problem Analysis

In the virtualized environment, a pCPU is proportionally shared among several vCPUs, and each vCPU in the local job queue is scheduled for a certain length of time periodically. We first make some assumptions on the environment of the virtual system based on the policies of credit scheduler and common experience of configuration. Firstly, the size of each parallel job is smaller than the number of pCPUs. Secondly, VMs of serial workloads are assumed to be in busy status. Thirdly, the VMs of the parallel job are Uniprocessor systems and only committed to execute the parallel jobs. Forthly, the total number of the VMs in system is much bigger than the number of the pCPUs of the host.

Let p be the number of pCPUs, s be the size of a parallel job and j be the total number of VMs. As the credit scheduler targets for global workload balanced, the VMs will be evenly and randomly allocated to the pCPUs. Therefore, we know the probability of the parallel nodes being allocated to different pCPUs is:

P A = i<s i=0 p -i p s (1)
Moreover, the nodes of the parallel job should be placed at the same positions of their run queues so that they can be scheduled simultaneously. We know the size of each run queue is:

q = j/p (2)
Thus, the probability of all parallel nodes being placed at the head of the run queues is:

P B = 1 q s-1 (3)
Therefore, the probability of a parallel job being simultaneously placed on the head of run queues by the credit scheduler is:

P C = i<s i=0 p -i p s • 1 q s-1 min (4)
We introduce execution efficiency E s to indicate the percentage of the parallel sub-tasks being simultaneous executed in a time slice. Additionally, as dom0 processes the I/O request in Xen, it is compulsory to schedule dom0 along with the parallel nodes. Thus, overall evaluation on the efficiency of scheduling a parallel job in Xens:

E overall = i<s+1 i=0 p -i p s+1 • 1 q s min • E s (5)
As can be seen, the probability of a parallel job being properly scheduled by credit scheduler is extremely low. Therefore, a co-scheduler is required to assist the credit scheduler to make the appropriate decision on scheduling the parallel job. The problem can be illustrated by Fig 1. The co-scheduling solution solve the problem using three steps. Firstly, it identifies the parallel job in Xen, which requires the VMs of parallel job to be labeled by the users so that co-scheduler is able to identify parallel workload. Secondly, the co-scheduler relocates the VMs of the parallel jobs to avoid overcommitted pCPUs. All VMs of the parallel jobs will be examined in this step, if multiple VMs of a parallel lie on the same job queue of pCPU, the vGrouper is expected to redistribute then to different job queues by migrating. Notably, this step is only taken one time when a parallel job is created. Thirdly, for each parallel job, we choose a flag VM which indicates the parallel job is encountered. When the flag VM is about to be scheduled online, the vGrouper schedule all related VMs of the same parallel job together with the flag VM as a group by boosting the parallel nodes. The boost mechanism of credit scheduler allows current running vCPUs to be preempted by others to accelerate the responding time, which can be used by vGrouper to simultaneously scheduled the VMs of a parallel job together.

Conclusion

In this paper, we investigate the reasons for performance degradation of the parallel job in Xen and analyze the importance of simultaneous scheduling to the execution of the parallel job in Xen. we present vGrouper to assist the credit scheduler in handling the parallel application by increasing the length of synchronous execution of a parallel job. The experiments show that vGrouper effectively optimizes the performance of the parallel job in Xen and increases the utilization of the system.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Problem of parallel job in Xen

Fig. 3 :Fig. 4 :

 34 Fig. 3: The overhead of co-scheduling process


Mingyi Zhu
email: my.zhu@siat.ac.cn

Kejiang Ye

Yang Wang
email: yang.wang1@siat.ac.cn

Cheng-Zhong Xu

A Deep Learning Approach for Network Anomaly Detection based on AMF-LSTM

The Internet and computer networks are currently suffering from different security threats. This paper presents a new method called AMF-LSTM for abnormal traffic detection by using deep learning model. We use the statistical features of multi-flows rather than a single flow or the features extracted from log as the input to obtain temporal correlation between flows, and add an attention mechanism to the original LSTM to help the model learn which traffic flow has more contributions to the final results. Experiments show AMF-LSTM method has high accuracy and recall in anomaly type identification.

Introduction

The Internet and computer networks are currently suffering from different security threats [START_REF] Garcia-Teodoro | Anomaly-based network intrusion detection: Techniques, systems and challenges[END_REF]. The Global State of Information Security Survey 2015 [START_REF] Ahmed | A survey of network anomaly detection techniques[END_REF] found there is a great increase in security incidents during the last several years. Network anomalies stand for a large fraction of the Internet traffic and compromise the performance of the network resources [START_REF] Garcia-Teodoro | Anomaly-based network intrusion detection: Techniques, systems and challenges[END_REF][START_REF] Benson | Network traffic characteristics of data centers in the wild[END_REF]. With the growing network scale, the traditional methods face two problems: i) the processing speed is too slow, unable to cope with the massive network traffic data in today's Internet environments; ii) it may invade the user's privacy. This situation can be alleviated by using machine learning methods, which are successfully used in many other areas. However, most of the traditional machine learning methods always focus on the traffic itself and extract their own characteristics to detect the potential anomalies.

As we know the data transmitted in network is in the form of flows. There is always a temporal correlation between flows, which is also true for abnormal traffic in the network. In previous work, researchers focus on the characteristics of traffic itself, but ignore that many network anomalies have potential temporal correlation. RNN (Recurrent Neural Networks) is widely used in the fields that are time series related. Recently, there are some works using RNN and LSTM (Long-Short Term Memory) to detect abnormal traffic [START_REF] Zhu | Network anomaly detection and identification based on deep learning methods[END_REF][START_REF] Yin | A deep learning approach for intrusion detection using recurrent neural networks[END_REF], but they only use a single flow to repeat multiple times, which can only learn the relationship between themselves and cannot learn the relationship between different flows. This paper presents an anomaly detection method using deep learning model based on AMF-LSTM. The proposed method has three important features: i) use the previous traffic flows as auxiliary features of the traffic to be detected; ii) use LSTM to find the hidden temporal correlation between these flows, and iii) use the attention mechanism to make model focus on the traffic and features that are useful for the results.

AMF-LSTM Model

We proposed an AMF-LSTM (Attention-base Multi-Flow LSTM) model for network anomaly detection. Attention means that our model is based on the attention mechanism [START_REF] Chorowski | Attentionbased models for speech recognition[END_REF]. Multi-Flow means that we not only use the characteristics of the current flow itself to detect the anomalies, but also use the previous traffic flows with temporal correlation to assist in detecting abnormal traffic. LSTM means the main body of our network is based on the long short-term memory networks [START_REF] Hochreiter | Long short-term memory[END_REF]. Fig. 1 shows the structure of AMF-LSTM model.

Experiment

We use CICIDS2017 [START_REF]Intrusion detection evaluation dataset (cicids2017)[END_REF] as the experimental dataset. The dataset contains benign and the most up-to-date common attacks, which resembles the true realworld data. The implemented attacks includes the most common attacks based on the 2016 McAfee report [START_REF]Mcafee labs threats report[END_REF].

Our experiment mainly has the following hyperparameters: n, the number of flows are selected to detect the traffic; the learning rate, which is the step size of neural network for each learning; and the number of LSTM hidden nodes, which is the number of nodes that LSTM uses to learn. We first study the effect of learning rate and hidden nodes on the model accuracy, and find the best value of hidden nodes is 256, and the optimal learning rate is 0.0001. Then, we perform two sets of experiments with n = 10 and n = 20. The experimental results are similar, probably because the attention can focus on where it is needed. We compare the performance of our model with several classic machine learning algorithms, such as Naive Bayes, SVM, AdaBoost, MLP, and the original LSTM. The results of accuracy and recall comparison are shown in the Fig. 2. We can see that our model is significantly better than other machine learning algorithms, both in accuracy or recall.

We further conduct a deeper study on model with n = 10, lr = 0.0001, node num = 256, which achieves the best performance. The evaluation metrics are shown in the Table 1. As we know, it is far more harmful for a system to judge abnormal traffic as normal traffic than to judge normal traffic as abnormal traffic. Therefore, we pay more attention to the value of recall. According to the table, our model can identify most of the anomalies correctly. In prior studies, a number of approaches have been proposed for network anomaly detection. Sun et al. [START_REF] Sun | Intrusion detection techniques in mobile ad hoc and wireless sensor networks[END_REF] present a survey of intrusion detection techniques for mobile ad-hoc networks (MANET) and wireless sensor networks (WSN). Sperotto et al. [START_REF] Sperotto | An overview of ip flow-based intrusion detection[END_REF] explain the concepts of flow and classified attacks, and provide a detailed discussion of detection techniques. Abbes et al. [START_REF] Abbes | Efficient decision tree for protocol analysis in intrusion detection[END_REF] introduce an approach that uses decision trees with protocol analysis for effective intrusion detection. Khan et al. [START_REF] Khan | Rule based network intrusion detection using genetic algorithm[END_REF] use genetic algorithms to develop rules for network intrusion detection. Tthere are also large number of methods using Neural Network. An example of ANN-based IDS is RT-UNNID [START_REF] Amini | Rt-unnid: A practical solution to realtime network-based intrusion detection using unsupervised neural networks[END_REF]. Thilina et al. [START_REF] Thilina | Intruder detection using deep learning and association rule mining[END_REF] propose a novel framework to perform intruder detection and analysis using deep learning nets association rule mining. Yuan et al. [START_REF] Yuan | Insider threat detection with deep neural network[END_REF] use the LSTM-CNN framework to find users anomalous behavior. Most recently, Zhu et al. [START_REF] Zhu | Network anomaly detection and identification based on deep learning methods[END_REF] use CNN model for network anomaly detection and identification and achieve better performance than traditional machine learning algorithms. Although RNN [START_REF] Yin | A deep learning approach for intrusion detection using recurrent neural networks[END_REF] and LSTM [START_REF] Kim | Long short term memory recurrent neural network classifier for intrusion detection[END_REF] have been used to detect abnormal traffic before, they only use a single flow as the input of RNN and recurrent itself multiple times. In our opinion, they can only learn the relation in the traffic itself, and can not fully utilize the characteristics of RNN, which can learn the potential relations between different traffic.

Conclusion

This paper presents a method for abnormal traffic detection in the Internet by using deep learning model based on AMF-LSTM. We use the statistical features of multi-flows rather than a single flow as the input to obtain temporal correlation between flows, and add an attention mechanism to the original LSTM to help the model learn which traffic flow has more contributions to the result. Compared with other classic machine learning algorithms, our model achieves about 10% improvement in accuracy and recall on the multi-classification problems.

Fig. 1 .

 1 Fig. 1. Structure of AMF-LSTM

Table 1 .

 1 The Results of Different Evaluation Metrics

		Precision	Recall F1-score Flows
	Normal	0.98	0.91	0.94	348631
	DDoS	0.83	0.98	0.90	25606
	PortScan	0.82	0.99	0.90	31786
	BOT	0.05	0.75	0.10	394
	Infiltration	0.00	0.75	0.01	8
	Web Attack	0.04	0.81	0.07	436
	Patator	0.38	0.53	0.44	2767
	DoS	0.87	0.88	0.87	50532

Acknowledgment

This work is supported by the National Key R&D Program of China (No. 2018YFB1004804), National Natural Science Foundation of China (No. 61702492, U1401258), and Shenzhen Basic Research Program (No. JCYJ20170818153016513, JCYJ20170307164747920).


Yi Liu

Yunchun Li

Honggang Zhou

Jingyi Zhang

Hailong Yang

Wei Li

A Fine-grained Performance Bottleneck Analysis Method for HDFS

Keywords: HDFS, Instrumentation, Bottleneck Analysis, Performance Optimization

The performance issue of HDFS has always been a great concern due to its widely adoption in both production and research environments. However, a fine-grained performance analysis tool is missing to effectively identify the bottlenecks as well as to provide useful guidance for performance optimization. In this paper, we propose a fine-grained performance bottleneck analysis tool, which extends HTrace with finegrained instrumentation points that are missing in Hadoop official distribution. In addition, we propose an effective trace merging method that improves the understandability of our analysis. We analyze the performance of HDFS under different kinds of workloads and get undiscovered insights.

Introduction

Distributed file systems are widely used in various computing domains such as supercomputing and big data analytics. However, diagnosing performance issues of distributed file systems is still a challenging task, because the performance bottleneck of a distributed file system may come from various components of the system, and even interaction between different components. Therefore, effective performance analysis tools for distributed file systems such as Hadoop are of vital importance. Currently, many researches focus on end-to-end performance analysis frameworks, which capture the information flow of each request of the distributed file system and then obtain the performance information of each component of the system and the interaction between the components such as Dapper [START_REF] Sigelman | Dapper, a large-scale distributed systems tracing infrastructure[END_REF], Magpie, Stardust [START_REF] Thereska | Stardust: tracking activity in a distributed storage system[END_REF], Xtrace [START_REF] Fonseca | X-trace: A pervasive network tracing framework[END_REF], HTrace [START_REF] Htrace | htrace[END_REF], etc.

Among the above performance analysis tools, HTrace has been merged into Hadoop release to provide useful performance data. However, the default HTrace instrumentation within Hadoop has the following limitations for fine-grained performance analysis. Firstly, the default Hadoop provides very limited instrumentation points without detailed information captured. For example, the major components of HDFS [START_REF] Shvachko | The hadoop distributed file system[END_REF] such as Namenode, Datanode and their interactions are not instrumented. For example, we can not conclude whether Namenode bookkeeping is the bottleneck because Hadoop's official implementation haven't instrumented Namenode. Secondly, the default instrumentation in Hadoop cannot obtain the detailed parameter information for the function calls instrumented. For better analyzing the performance of a distributed file system, not only the time series of each function call but also the size of bytes processed by each function need to be known in order to identify the potential performance bottlenecks. Lastly, instrumentation information provided in default Hadoop is difficult to retrieve and visualize. For example, in just a few minutes, hundreds of megabytes of trace files are generated, making it hard to locate and diagnose the performance issues.

Therefore, this paper focuses on the performance analysis of HDFS by extending HTrace to provide fine-grained instrumentation. In addition to solve the trace explosion problem, we propose a trace compression method that merges the traces of repeated function calls and only maintains the representative statistics during instrumentation. Finally, through experiments on representative big data workloads, we obtain some useful insights.

Methodology

Fine-grained Instrumentation

The instrumentation of Hadoop's official distribution mainly instrument client sensed delay or Datanode sensed delay. HDFS contains more complex interaction beyond Datanodes and the client node. What's more, we can not distinguish network delay from the local file I/O delay. Due to this reason, we instrument some new performance-related blocks. They mainly reside in Namenode, Datanodes. Our purpose is to get fine-grained Namenode performance, Datanode local I/O performance, Datanode network performance, Datanode and Datanode data exchange performance. Except for simply obtaining function call duration, our instrumentation also encodes important function arguments into traces such as data size processed, block id and filename so we can monitor data process rate, I/O error occurrence. One of the biggest challenges of our instrumentation is that Java has many polymorphous functions. In the case, we will instrument every function and merge them in the trace processing procedure.

Trace Compression

The running of HDFS will generate a huge volume of traces. In our experiments, after several minutes of Spark execution, a trace larger than 1 GB will generate. Traditional HDFS performance analysis tools neglect this fact and rely on human labor to find the bottleneck in a large amount of data.

We present an effective method for compressing traces. We observe that before compressing, there are many repeated function call. For example, the receiveBlock function usually contains hundreds of receivePacket functions. We merge repeated function call receivePacket in this circumstance and only extract several representative statistics from these merged function calls. The number of call trees will reduce by more than 90% after trace compression. Formally, we do a breadth-first traversal from bottom to top inside a call tree and merge the subtrees with the same structure. After compression inside every call tree, we compress these trees with the same structure.

Evaluation

Experiment Setup

Our experiments are conducted with a cluster with seven nodes with one master node (which is Namenode in HDFS), five slave nodes (which are Datanode in HDFS) and one client Node. The master node and slave nodes are equipped with Xeon E5-5620, 16GB memory. To achieve higher throughput, we use Intel Xeon Phi (Knights Landing) for workload generating. The many-core and high volume of memory enable Phi to start many HDFS clients simultaneously. The implementation is shown in Figure 1

Performance Bottleneck Analysis

Across Workloads -We choose the tiny sized workload input from Hibench.

For machine learning workloads, data will be iterated for many times generating large traces thus we use sampling (sample rate is 0.05) to reduce trace size. For Wordcount workload, the largest delay is caused by FileSystem#createFileSystem which spends total 90.21s. The second largest delay is caused by DFSOutput-Stream#close which spends total 10.54s. Local I/O plays an ignorable role here. The delay of Datanode flushing buffer into local file system is too small to measure. And also we can conclude that using faster storage medium won't speed up application greatly. We can see the bottleneck is in the client node. The process for initiating FileSystem object has a large potential to optimize. We have a similar conclusion for Sort, Terasort, Pagerank, LogisticRegression and Nweight workloads. Bayes workload is different from the above workloads. The largest delay is caused by BlockSender#sendBlock. Reading from local file system causes 3.10s delay and reading from remote Datanode causes 0.49s delay.

Impact of File Size -We use Wordcount workload to explore the impact of file size on HDFS performance. We use tiny, small, large, huge sized workloads which contains 32000, 320000000, 3200000000, 32000000000 respectively. Due to the trace size explosion, we use a sample rate of 1, 0.01, 0.001, 0.0001 respectively. With the increase of data size, the impact of FileSystem#createFileSystem is becoming weaker. In tiny sized workload, this operation causes total 91.92s delay compared with application time 28s(we add up delay from different Datanodes).

In small-sized workload, it takes 1.55s compared with application time 32s. And in larger sized workloads, it hasn't been sampled. So in small-sized workloads, the file system creation process is an import bottleneck.

Impact of Request Frequency -In [START_REF] Ren | Realistic and scalable benchmarking cloud file systems: Practices and lessons from alicloud[END_REF], the authors directly model real request patterns from the AliCloud on IOPS, Inter-arrival time, session size and read request size. However, Alicloud is a very large cluster contains tens of thousands of nodes. For our small cluster, we multiply IOPS with different factors α but retains the distribution the model. With request frequency increasing, we can explore which part of HDFS facing the request pressure as shown in Table 1.

The delay of request mainly caused by sendBlock operation. However, the average delay of this operation is decreasing. Although FileSystem#createFileSystem plays an important role in request delay, its duration has little to do with request frequency. We can find out that the delay of sendBlock first increase but then decrease with request frequency increasing. In small frequency, HDFS is in cold start state thus the delay is relatively large. And when request frequency is very large, the resource contention is more severe. The BlockSender#sendPacket, FS-Namesystem#getBlockLocations (Namenode searching for block locations for a given file) operation has the same conclusion. Contrary to common sense, the bottleneck under frequent request is neither in Namenode nor in Datanode. Thus optimization for the concurrent request in client node is more important.

Conclusion

In this paper, we propose an extension to HTrace in order to support fine-grained performance bottleneck analysis for HDFS. In addition, we propose a trace compression method to merge the repeated function calls for efficient performance analysis. We've also done a series of experiments to explore the bottleneck under different workloads and get useful insights.

Fig. 1 .

 1 Fig. 1. The implementation overview of our HDFS performance analysis tool.

Table 1 .

 1 The average delay (second) of some major functions under different request frequencies.

	Function	α = 0.001 α = 0.005 α = 0.01 α = 0.05 α = 0.1 α = 0.5
	FileSystem# create-	0.1567	0.1842	0.1827 0.2060 0.1887 0.1992
	FileSystem
	sendBlock	0.0054	0.0026	0.0020 0.0012 0.0009 0.0015
	BlockSender# send-	0.0005	0.0004	0.0002 0.0001 0.0001 0.0002
	Packet
	FSNamesystem#	0.0088	0.0006	0.0005 0.0003 0.0007 0.0014
	getBlockLocations
	total	0.0423	0.0439	0.0426 0.0648 0.0801 0.0674

Acknowledgment

The authors would like to thank all anonymous reviewers for their insightful comments and suggestions. This work is supported by National Key Research and Development Program of China (Grant No. 2016YFB1000304) and National Natural Science Foundation of China (Grant No. 61502019). Hailong Yang is the corresponding author.


Jinjing Zhao
email: misszhaojinjing@hotmail.com

Pang Ling
email: lingpang313@yahoo.com

Kuang Xiaohui

Jin Rong

Balancing the QOS and Security in Dijkstra Algorithm by SDN Technology

Dijkstra algorithm is widely used in a lot of common network routing protocols. We consider the problem of quality of service (QoS) and the Security features of the network routing area using software defined networks (SDN). The SDN framework enables an efficient decoupled implementation of dynamic routing protocols which could aware the communication network status. In this work we consider the varying delay status of the communication network along with other network security parameters. The routing problem is formulated as a multi-constrained shortest path problem. A new improved Dijkstra algorithm is presented named as QS-Dijkstra. The implement and experiment show that QS-Dijkstra algorithm is able to minimize traffic routing through vulnerable links while satisfying the QoS constraints of the network.

Introduction

Dijkstra algorithm is widely used in a lot of common network routing protocols, like OSPFand IS-IS. The main idea of Dijkstra algorithm is how to find a shortest path from a source node to a destination node in a network. So each network link has a cost value to present its status, and this cost is used to calculate the shortest path. In the practice, the link cost is defined as a static cost value in OSPF protocol, as the reference bandwidth divided by interface bandwidth or simply as 1 to reduce the shortest path weight to a hop count. The reason is that it's a very easy way in practice. But as the value of the link cost, it could not cover the feathers and status of the link.

In this work we present a practical way to calculate a more reasonable link cost in Dijkstra algorithm and consider the problem of QoS and the security features of the network routing procedure using SDN technology [START_REF] Nunes | A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF][START_REF]Software-defined networking[END_REF][START_REF]Software-defined networking: The new norm for networks[END_REF]. The SDN framework provides an approach to calculate the shortest path between source and destination based on dynamic link statuses through SDN's high network monitoring capability. A lot of useful link information, like link type, link ownership, interface bandwidth, transition delay and historical record, can be collected and computed by the SDN controller to enable more safe, reliable and efficient paths. In this way, we can consider the varying delay status of the communication network along with other network security parameters and get a presence of a passive/active adversary in the network routing area.

The remainder of this paper is organized as follows: double constrained shortest path problem is discussed and the derivation of QoS constraints and related cost metrics are presented in Section 2, the implementation details are provided in Section 3, Section 4 investigates the performance of the proposed framework. Conclusions and final remarks are discussed in Section 5.

System model

Consider a graph representation of the communication network. G(V,E, ω ) is a weighted undirected graph model and describes an N nodes and E links network. The node set is V = {v1, … , vN}, and the edge set is E ={eij |i, j = 1,2, …,N}. The weight 𝜔 𝑖𝑗 on the edge eij is defined as the cost of the link. In this article, the interplaying between QOS and security features is concerned in the network routing process. The security metrics of the link between nodes i and j could include these features as: 1) History LijH: a link that was previously targeted by an attacker in a particular time could be more likely to be attacked again. 2) Security installed measures LijS: a link with high encryption is typically hard to be listened or hijacked. So LijS values are dependent on the pre-installed and preconfigured security measures of nodes of the link. 3) Bandwidth LijB: A link with high bandwidth is more difficult to be congested by data flow. 4) Ownership LijO: a self-owned or in the same domain channel is more secure than a shared or leased channel by other domains. The vulnerability metric LijM should reflect the attributes that make a link more security.

LijM = LijH *(αLijS + βLijB + γLijO) (2) Where α, β, and γ are the weights of LijS, LijB and LijO depending on the impact importance of the considered security parameters.

Assume every link eij E has two weights cij>0 and dij>0 (cij is cost and dij means delay).For source and destination nodes (s,t), let Pst denote the set of paths from s to t. Further, for any path p define

c(p) = ∑ 𝐿 𝑖𝑗 𝑀 (𝑖,𝑗)∈𝑝 (3) d(p) = ∑ 𝑑 𝑖𝑗 (𝑖,𝑗)∈𝑝 (4)
The routing problem seeks to find the paths between s and t nodes with minimum link cost c(𝑝 𝑠𝑡 ), which satisfies 𝑑(𝑝 𝑠𝑡 ) ≤ 𝑇 𝑚𝑎𝑥 . This is a typical NP problem named constrained shortest path (CSP) [START_REF] Xiao | The constrained shortest path problem: algorithmic approaches and an algebraic study with generalization[END_REF][START_REF] Kuipers | An overview of constraint-based path selection algorithms for QOS routing[END_REF], which can be solved by the Lagrangian Relaxation Based Aggregated Cost (LARAC) algorithm [START_REF] Jüttner | Lagrange relaxation based method for the QOS routing problem[END_REF].

Implementation

The architecture of SDN network comprised of Floodlight controller and Mininet switches. In the floodlight controller, applications can be written in Java and can interact with the built-in controller modules via a JAVA API. Other applications can be written in different languages and interact with the controller modules via the REST API. And the controller allows the implementation of built-in modules that can communicate with their implementation of the OpenFlow controller (i.e OpenFlow Services). The controller, on the other hand, can communicate with the switches via the OpenFlow protocol through the abstraction layer present at the forwarding hardware. We propose a Vulnerable-Link Avoidance Dijkstra (QS-Dijkstra) algorithm to capture the problem of best-effort avoiding vulnerable links while maintaining the delay constraint. QS-Dijkstra algorithm uses the previously-defined vulnerability metric in equation ( 2) to arrive at a set of feasible paths between source node s and destination node t.

The flowchart of the QS-Dijkstra algorithm that is implemented is shown in Fig. 1. The algorithm is separated into two parts, the switch side and the controller side. The algorithm of the controller side performs the following tasks: 1) Listening to messages from switches and calculating link-delay value of each link, and then constructing the link-delay cost matrix. 2) Calculating the link-vulnerability cost matrix according to the metric developed in formula (2); this matrix can be modified and calibrated by network operators or managers. 3) Running a topology-update thread, and checking the link-vulnerability cost matrix updates every Ts; if a change is detected, the controller recalculates the routing paths. 4) Calculating the routing paths based on the link cost metrics of interest, and updating the flow table of each switch by advertise a PACKET OUT message to switches. The main function of the algorithm in the switches side is to collect the values of link-delays for the directly connected switches. This is done through an independent thread responsible for periodically testing the link between that switch and all connected switches with higher ID. The sampling time is parametric and is tuneable by the network managers; in our simulation environment, Tsd is set to 60 seconds. Link delay testing is done 3 times every Tsd and the average value is then compared with the last known value. If the new delay is significantly different from the previous value, the switch updates the controller accordingly.

Simulation and Results

We build two large scale network environment with the same topology and route information. One is running the Dijkstra routing protocol, the other is for QS-Dijkstra. In order to reach a high performance, in each environment, we use the highperformance workstation with 10 Intel Xeon Westmere EP six-core processors. Whose maximum process speed could reach 11.251Tflops. Thus, the whole network includes 260 routers and a controller. For every node, we pick a random number from [START_REF] Nunes | A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF]10] for its connection number. And the commercial network flow generator Spirent TestCentre is chosen to generate some popular network application data, like http, IP, TCP, UDP. And it sends the same packets to the two networks synchronously. In this test case, the link cost and link delay is randomized in the [0 -100]. The maximum path delay constraint T still set as 1000 seconds. After calculating the link vulnerability metric, there are 20 links which have very high vulnerable level. We sampled the packets number transmitted through these links every 200 seconds and calculate the average value on each links. The result is shown in Fig. 8, which shows that the packets transmitted on these un-safe links in QS-Dijkstra are much less than in Dijkstra. From the results shown in Figure 9, the conclusion could be proved that the network performance in QS-Dijstra does not lost much except for a few short intervals, and the maximum responds time in these intervals is still could be acceptable.

Conclusion

In this paper, we consider the varying delay status of the communication network along with other network security parameters. Our approach capitalizes on the SDN framework and technology. The implement and experiment show that QS-Dijkstra algorithm is able to minimize traffic routing through vulnerable links while satisfying the QoS constraints of the network.

In the future work, the algorithm could consider more security and performance features of links and routing nodes, to make a more effective routing protocol.

Fig. 1 .

 1 Fig. 1. QS-Dijkstra Algorithm Implementation. The algorithm is separated into two parts; a controller function which is implemented in Floodlight using Java, and a switch function implemented in Mininet using Python.

Fig. 8 .

 8 Fig. 8. The Number of Transmitted Packets on Un-Safe Links. There are 20 links which have very high vulnerable level.

Fig. 9 .

 9 Fig. 9. The Average Response Time of Routers. In order to evaluate the network performance in the two networks, the average response times are recorded every 15 seconds.


Junyu Li

Ligang He
email: liganghe@warwick.ac.uk

Shenyuan Ren
email: shenyuanren@warwick.ac.uk

Rui Mao
email: mao@szu.edu.cn

Data Fine-pruning: A Simple Way to Accelerate Neural Network Training

Keywords: Deep Neural Network, Data Pruning, SGD, Acceleration

The training process of a neural network is the most timeconsuming procedure before being deployed to applications. In this paper, we investigate the loss trend of the training data during the training process. We find that given a fixed set of hyper-parameters, pruning specific types of training data can reduce the time consumption of the training process while maintaining the accuracy of the neural network. We developed a data fine-pruning approach, which can monitor and analyse the loss trend of training instances at real-time, and based on the analysis results, temporarily pruned specific instances during the training process basing on the analysis. Furthermore, we formulate the time consumption reduced by applying our data fine-pruning approach. Extensive experiments with different neural networks are conducted to verify the effectiveness of our method. The experimental results show that applying the data fine-pruning approach can reduce the training time by around 14.29% while maintaining the accuracy of the neural network.

Introduction

Scaling up layers and parameters in modern neural networks improves the performance dramatically and enables the discovery of sophisticated high-level features. However, it also presents enormous challenges such as the training efficiency of Deep Neural Network (DNN).

Many novel training algorithms and deep neural networks have been designed and achieved good performance with benchmark datasets and even in industrial practices. For instance, Constitutional Neural Networks (CNN) demonstrates impressive performance in areas such as image recognition and classification; Very Deep Constitutional Networks (VGG) uses an architecture with tiny convolution filters and shows a significant improvement in network performance; Deep Residual Network (ResNet) is developed to ease the training of the networks that are substantially deeper than those used previously and gain the accuracy from considerably increased depth of the networks; Wide Residual Networks (WRN) that advances from ResNet contains a more complex architecture of network and outperforms regular deep ResNets in accuracy and efficiency.

Different configurations of DNN may lead to different level of accuracy and training efficiency (i.e., time consumption). Therefore, much research has been conducted to find the better configuration of the networks. Many endeavours have also been devoted to accelerating the training process by parallel computing. Our work does not focus on the optimization of the network configuration, but takes another approach. We assume that the configuration of the network has been optimized (or is fixed) with given settings of hyper-parameters such as the learning rate and the number of epochs. We propose to simplify the training process by reducing the training time of each epoch (regardless of the network configuration). In this approach, we dig into the training process, monitor and analyse the loss trend of each training instance. A novel method, named with Data Fine-pruning training, is developed to reduce the time consumption of training a model by sensibly and temporarily pruning a fraction of input training data in each training instance. The experimental results show that comparing to regular training, our approach is effective with majority nets and can reduce the training time by about 14.29% while maintaining the accuracy of the network.

The remainder of this paper is organized as follows. Section 2 introduces research backgrounds and motivations of our work. Section 3 reviews recent remarkable works that are related to our work. Section 4 detailed demonstrates our methods of analysing individual data, the way we run data pruning and formulations of time saved applying our approach. Section 5 illustrates the experiment results we did. Finally, a conclusion is addressed in Section 6.

Background and Motivation

DNNs have recently led to a series of breakthroughs in many fields such as speech recognition and image classification. Many novel learning algorithms are designed to build an effective model from a set of data and towards a prediction goal, where the model maps each input data to a prediction. Modern DNNs are typically powered by a vital training algorithm: Mini-batch Stochastic Gradient Descent (BSGD). However, there exists a heavy data dependence in the BSGD training which extremely limits the degree of parallelism.

Mini-batch Stochastic Gradient Descent

BSGD is the most widely used weight updating algorithm in recent notable neural networks. It takes a batch of data instead of using only one example each time as the input data for training. The weights of networks are same for all the instances in a batch during the forward propagation, and the changes in the weights depend on an average loss of a batch data. One core benefit of BSGD is that the changes in weights become much steadier than those in regular Stochastic Gradient Descent (SGD). Moreover, BSGD training can take the advantage of parallel computing by parallelising the calculations within a batch, so that the processing efficiency can further increase.

ω t+1 = ω t -γ 1 b b i=1 ∇ ωt (f ωt (x i ), y i ) ( 1
)
where b is the size of a batch data, ω is a weight vector, γ is a learning rate, and (f ω (x), y) is a loss function measuring how wrong the model is in terms of its ability to estimate the relationship between data x and corresponding label y.

Problem Setting

Figure 1 shows the loss trends when training a commonly used network -ResNet with the depth of 18 layers. The sub-figure on the top describes the trend of the values of the loss function over the testing data, which demonstrates that there are four main periods. Such different performance levels are closely related to the changes in the learning rate, where the changing points are at 60, 120, 160. The loss falls sharply from 1.5 to 0.67 in the first interval. However, from the second stage onwards, the decreasing rate slows down in each part. It can be observed from the figure that there exists a plateau in each training period with the corresponding learning rate. Such plateau always occurs in training no matter which network is used. On the contrary, the sub-figure at the bottom reflects the accuracy of the network with the test data. It can be seen that the accuracy increases as the loss decreases and the accuracy curve also contains the plateaus during the training.

In this paper, we aim to reduce the time spent on such training plateaus while achieving similar training results.

Related Work

DNNs can produce much better results than most of other techniques in many fields [START_REF] Lei | A novel scheme for speaker recognition using a phonetically-aware deep neural network[END_REF][START_REF] Richardson | Deep neural network approaches to speaker and language recognition[END_REF][START_REF] Dahl | Context-dependent pre-trained deep neural networks for large-vocabulary speech recognition[END_REF][START_REF] Cireşan | Multi-column deep neural networks for image classification[END_REF][START_REF] Taigman | Deepface: Closing the gap to humanlevel performance in face verification[END_REF] such as human face recognition. However, training the nets usually take quite a long time and the cost has a significant upward trend [START_REF] Lecun | Deep learning[END_REF]. An outstanding amount of effort has been put into extending deep learning models, improving prediction performance and reducing training time consumption [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF][START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF][START_REF] He | Deep residual learning for image recognition[END_REF][START_REF] Szegedy | Going deeper with convolutions[END_REF]. Regarding to the various latest acceleration mechanism for deep learning system, the technique of those could be sorted into two main cases: (i) utilize a set of GPUs to work for deep models and large training sets to take benefits from huge computing capacity facility so as to deal with large scale of models and data, (ii) optimize the training algorithms to enhance training efficiency so that directly reduce the time consumption of training.

Hardware Accelerating

GPUs are quite suitable for the computations in training a network since SGD and its variants carry high arithmetic density. It is known to all that GPU has advantages in computation capacity, thus applying a set of GPUs to train nets can deliver considerably efficient training of modestly sized Deep Neural Network practical [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF][START_REF] Cui | Geeps: Scalable deep learning on distributed gpus with a gpu-specialized parameter server[END_REF][START_REF] Chilimbi | Project adam: Building an efficient and scalable deep learning training system[END_REF][START_REF] Dean | Large scale distributed deep networks[END_REF]. A common limitation of such strategies is the size of GPU onboard memory. It restricts network model and training data to be small so that the model and data can be fitted into the GPU memory. As a result, the parameters of the network and the number of data used each time are usually reduced in order to utilise the GPU(s) computation. Apart from that, there exists a mismatch in speed between GPU compute and interconnects, which leads the system extremely hard to do data parallelism in real time via a parameter server.

Algorithm Accelerating

There are a number of works on optimising training algorithm have been done up to now. Momentum [START_REF] Qian | On the momentum term in gradient descent learning algorithms[END_REF] and Nesterov Accelerated Gradient [START_REF] Nesterov | A method for unconstrained convex minimization problem with the rate of convergence o (1/kˆ2)[END_REF] are the methods that help accelerate SGD in the relevant direction and dampens oscillations that always happen around local optima. The momentum term increases for dimensions whose gradients point in the same directions and reduces updates for dimensions whose gradients change directions. As a result, nets gain faster convergence and reduced oscillation. Adagrad [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF] and its extension (Adadelta) [START_REF] Zeiler | Adadelta: an adaptive learning rate method[END_REF] are the algorithms for gradient-based optimisation that mainly do: adapt the learning rate to the parameters, performing smaller updates for parameters associated with frequently occurring features, and more significant updates for parameters associated with infrequent features. Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] is another method that computes adaptive learning rates for each parameter. It considers the decaying averages of past and past squared gradients, and update the parameters in a similar way used in Adadelta. Besides, Asynchronous Stochastic Gradient Descent (ASGD) algorithms [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF][START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF][START_REF] Liu | An asynchronous parallel stochastic coordinate descent algorithm[END_REF][START_REF] Zheng | Asynchronous stochastic gradient descent with delay compensation[END_REF] represented by Hogwild [START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF] purposes to update the parameter by many workers where they are sharing a parameter server.

Data Accelerating

According to the studies on previous works on accelerating the training process, we find that there is no method that prunes the training data in a reasonable way so as to train the network with significant data that is a subset of original one. In this way, the time cost of training will be reduced by the number of data that is pruned. Our work is the first to propose an algorithm powered by such an idea. The method does not require making any changes to the original training settings, but real-time analyses performance on each data to make a choice on keeping or ignore. Please note that the decisions are not intended to be permanent, as such decisions are made based on a period of performances.

The Data Fine-pruning Approach

Our data fine-pruning approach reduces the training time of some specific epoch and therefore reduce the overall training time. We first investigate the loss trends of individual data in section 4.1. Second, we analyse the type of input data that should be selected for temporary pruing. Next, we introduce the data selection process and present the data fine-pruning approach in detail in subsection 4.2 and 4.3. Finally, section 4.4 formulates the time consumption reduced by our approach. At the end of the training, data 2 cannot be correctly allocated to the category that it is supposed to be due to the high loss produced in the first run. However, it still costs the time and computing power to make the model adjustments using data 2 in each epoch. Our approach makes use of the fact that some data consistently produce bad results but still cost the time and resources during the training process.

Loss trends of individual data

Based on the above analysis, we proposed a pruning method for the training data. It temporarily prunes some data that have poor performance evaluated at real-time during training. Our experiments show that temporarily pruning the data that performed poorly in recent training rounds makes little changes to the final model.

Loss Monitoring and pruning Selection

Algorithm 1 outlines the loss monitoring procedure and the selection method for data pruning. The loss of each data is monitored during the training process. The DroppingCount is defined for each data to measure its training performance and used to decide which data should be selected to prune. A larger DroppingCount of data x, denoted by DroppingCount[x] indicates a higher probability for this data item to be to pruned. At the end of training in each epoch, the algorithm examines each loss of the data, denoted by l(f ωt (x), y) (where y is the label of data x), within the current batch (line 4). Note that f ωt denotes the network with parameters of ω at the moment of t. Then the algorithm compares the loss of each data with the loss of the current batch, denoted by l(f ωt (Batch n )). The loss value of a batch is the average of all losses in the batch. The algorithm selects the data that perform poorly in this batch and increase their DroppingCount values (line 5-7).

Considering that a data item shows the varied behavior through the training stages, the DroppingCount of data is held for a window (i.e., a preset number of epochs) and reset at the end of the window (line 1-3). The algorithm judges the behavior of a data item according to the DroppingCount value of this data item in the latest window. The size of the window is initialized at the beginning and can be dynamically adjusted during the training. Note that e in the algorithm is the number of current epoch. In each window, the algorithm records the data losses and count their corresponding DroppingCount. The window size is set according to the changes in learning rate. The windows size is set to a factor of the duration (number of epochs) of the learning rate (e.g., if the duration of the learning rate is 60, the window size is set to be 60 or 30). The analysis is performed for the entire window. However, the data pruning is only performed for the later portion of the window starting from an epoch defined by StartingP oint. A fluctuation of the accuracy caused by the adjustment of the learning rate typically lasts for a period and the period becomes shorter as the training progresses. Thus we start to reduce the StartingP oint by Attenuation after the first window (line 2-4). This measure leads to more pruning rounds so as to further reduce time consumption.

Algorithm 1 Loss Monitoring and Pruning Selection

In the later part of each window (line 5), we select some of the epochs to train with the pruned data (line 6), while the original data is still used in other epochs. We only prune the data temporarily because the behaviour of a data varies in different stages of the training process. In the algorithm, P runingBlock defines the block of epochs in which the pruned data are used; P runingCount is the number of the epochs that performs the data pruning. In each data pruning epoch, the data are ranked in the decreasing order of DroppingCount and the first P runingN um number of data in the rank list are pruned in the current epoch (line 7-8). In another word, the data with higher DroppingCount values will has more chances to be pruned. KeepList stores the indexes of the data that are kept in the training; x is the data index while y is the label of the data. Then the weights of the network are adjusted by BSGD (line 11) at the end of each epoch.

Analysis of performance improvement

The time consumption of the regular training for a network can be formulated by Formula 2. The time of regular running is denoted by t regular , the number of epochs by n, the time of forward and backward propagation a batch of data by T , and the number of batches by b. The total time equals to all time consumed over a set of epochs.

t regular = n i=1 T * b (2)
The number of rounds that are trained with the pruned data is denoted by n prune , the size of pruning window by w, the pruning count by c, starting point of pruning by a, the number of iterations using the pruned data by r. According to Algorithm 2, the value of n prune can be obtained by either Formula 3 in the case where the total number of epochs can be divided by the size of the pruning window, or Formula 4 otherwise.

n prune = ( w -a r * c + (w -a) mod r) * n w (3)
n prune = ( w -a r * c + (w -a) mod r) * n w + n mod w -a r * c + (n mod w -a) mod r (4)
As the number of batches processed in each epoch changes after applying the data-pruning, the average batches over the entire training can be calculated basing on Formula 5.

b prune = 1 n ( nprune i=1 T + n-nprune i=1 T ) (5)
t prune denotes the training time with the data pruning approach, t 0 is the computing overhead of the approach, t save is the saved time, which can be obtained by Formula 6 and further by Formula 7.

t prune = n i=1 (T * b prune ) + nprune i=1 (t 0 ) (6)
t save = t regular -t prune (7)

Experiments

Our data pruning approach is deployed on several modern neural networks including LeCun network (LeNet), residual network (ResNet), wide residual network (WRN) as well as Vgg network (Vgg). Performance of our method is evaluated with different hyper-parameters and architectures of such networks. The aim of our data pruning approach is to reduce the training time while maintaining the accuracy. Table 2 compares the accuracy between our approach

Conclusions and Future Works

Training a deep neural network can be a very time-consuming process. In this paper, we present a data fine-pruning technique, which analyzes the loss of each data at real time and prunes a set of data that performs poorly in recent training epochs. It achieves the noticeable saving of training time while maintaining the accuracy of the results.

There is more work to be done in future. First, our experiments show that some data are commonly identified as bad data and are repeatedly selected for pruning. We would like to investigate whether the bad data contain the common features. If such common features do exist and can be identified, we can probably make use of the finding and further reduce the training time.

Second, the data that perform poorly may relate to the type of the networks. We would like to conduct more in-depth research regarding the relation between the bad data and the type of networks. If this could be established, we expect to further improve the performance in practice.

Fig. 1 .

 1 Fig. 1. A Motivation Example

Figure 2

 2 Figure2presents the changes in the value of of the loss function over two representative data in two separate training. The two trainings are carried out with the same network. The loss of data 1 manifests a trend of continuous dropping from the beginning to the end in the first training. In contrast, an increasing trend has been observed with data 2. However, things change in the second run, where both data 1 and data 2 experience the decrease in loss. These two data have similar trends as that of overall network performance in the second run. The results indicate that the individual input data may produce varied performance in different runs of training even on the same network.At the end of the training, data 2 cannot be correctly allocated to the category that it is supposed to be due to the high loss produced in the first run. However, it still costs the time and computing power to make the model adjustments using data 2 in each epoch. Our approach makes use of the fact that some data consistently produce bad results but still cost the time and resources during the training process.Based on the above analysis, we proposed a pruning method for the training data. It temporarily prunes some data that have poor performance evaluated at real-time during training. Our experiments show that temporarily pruning the data that performed poorly in recent training rounds makes little changes to the final model.

Fig. 2 .

 2 Fig. 2. Performance of Same Data in Same Network but Different Runs

Fig. 3 .

 3 Fig. 3. An example of network training with data fine-pruning method

Table 1

 1 presents the average value of the best three accuracies of both regular training and data-pruning training as well as the percentage of saved time (Speedup in the table). Our experiments are conducted on a workstation with a CPU Intel i7-7700K, a GPU Nvidia GTX 1080 Ti, a hard disk Samsung SSD 970 Pro, four 16GB DDR4 2400Hz memory, Ubuntu 18.04, Cuda 9.0 and cuDNN 7.0. Table1presents the average time consumption of regular training, data finepruned training and the percentage of save time (Speedup) on four networks: LeNet, VggNet, ResNet and WRN. The data we used in the experiments is a popular benchmark dataset Cifar-10. It can be seen from the table that our data pruning approach can effectively save the training time. Further, higher percentage of time can typically be saved with a larger network. In the best case when WRN-22 is used for training, 14.29% of time is saved. Besides, According to our experiments, the overhead of data pruning approach is very lightweight. It only adds around averaged 4.2 seconds over 200 epochs of the training.

Table 1 .

 1 Time consumption of pruning data training and regular training

		LeNet VggNet-13 VggNet-16 VggNet-19 ResNet-18
	Regular	1220s	2028s	2554s	3110s	1277s
	Pruned 1071.73s	1873.67s	2356.74s	2867.7s	1109.92s
	Overhead	4.27s	4.33s	4.26s	4.30s	4.08s
	Speedup 11.80%	7.40%	7.56%	7.65%	12.76%
		ResNet-34 ResNet-50 WRN-10 WRN-16 WRN-22
	Regular	2047s	3931s	3h24m	5h8m	6h53m
	Pruned 1767.79s	3379.82s	2h56m	4h26m	5h54m
	Overhead	4.21s	4.18s	4.12s	4.25s	4.32s
	Speedup 13.43%	13.92%	13.73%	13.81%	14.29%

Table 2 .

 2 Accuracy comparison between pruning data training and regular trainingLeNet VggNet-13 VggNet-16 VggNet-19 ResNet-18 It can be seen from the table that the difference in accuracy is typically less than 0.4% except LeNet with a difference of 0.43%. The reason why LeNet shows the worse accuracy is because of the limitation of the net itself. Comparing LeNet to others, LeNet has a quite small number of layers and parameters, which makes the network more uncertain and unstable. The smallest difference in accuracy observed in our experiments is 0.01% (with ResNet-34).

	Regular 75.15%	93.92%	93.79%	93.35%	91.25%
	Pruned 74.72%	93.56%	93.44%	93.30%	91.16%
	ResNet-34 ResNet-50 WRN-10 WRN-16 WRN-22
	Regular 92.86%	93.75%	92.13%	94.22%	95.08%
	Pruned 92.85%	93.46%	91.78%	94.20%	94.71%
	and regular training.

Acknowledgement

This work is partially supported by the National Key R&D Program of China 2018YFB1003201 and Guangdong Pre-national Project 2014GKXM054.