2020 Vol. 57 No. 12
2020, 57(12): 2479-2480.
DOI: 10.7544/issn1000-1239.2020.qy1201
2020, 57(12): 2481-2489.
DOI: 10.7544/issn1000-1239.2020.20200723
Abstract：
Brain-computer Interface (BCI) technology based on motor imagery (MI) can establish communication between the human brain and outside world. It has been widely used in medical rehabilitation and other fields. Owing to the characteristics of the motor imagery EEG signals，such as non-linear, non-stationary, and low signal-noise ratio, it is a huge challenge to classify motor imagery EEG signals accurately. Hence, we propose a novel multiscale feature extraction and squeeze-excitation model which is applied for the classification of motor imagery EEG signals. Firstly, the proposed deep learning module, which is based on multiscale structure, automatically extracts time domain features, frequency domain features and time-frequency domain features. Then, the residual module and squeeze-excitation module are applied for feature fusion and selection, respectively. Finally, fully connected network layers are used to classify motor imagery EEG signals. The proposed model is evaluated on two public BCI competition datasets. The results show that the proposed model can effectively improve the recognition performance of motor imagery EEG signals compared with the existing several state-of-the-art models. The average accuracy on the two datasets is 78.0% and 82.5%, respectively. Moreover, the proposed model has higher application value because it classifies motor imagery EEG signals efficiently without manual feature extraction when spatial information is insufficient.
Brain-computer Interface (BCI) technology based on motor imagery (MI) can establish communication between the human brain and outside world. It has been widely used in medical rehabilitation and other fields. Owing to the characteristics of the motor imagery EEG signals，such as non-linear, non-stationary, and low signal-noise ratio, it is a huge challenge to classify motor imagery EEG signals accurately. Hence, we propose a novel multiscale feature extraction and squeeze-excitation model which is applied for the classification of motor imagery EEG signals. Firstly, the proposed deep learning module, which is based on multiscale structure, automatically extracts time domain features, frequency domain features and time-frequency domain features. Then, the residual module and squeeze-excitation module are applied for feature fusion and selection, respectively. Finally, fully connected network layers are used to classify motor imagery EEG signals. The proposed model is evaluated on two public BCI competition datasets. The results show that the proposed model can effectively improve the recognition performance of motor imagery EEG signals compared with the existing several state-of-the-art models. The average accuracy on the two datasets is 78.0% and 82.5%, respectively. Moreover, the proposed model has higher application value because it classifies motor imagery EEG signals efficiently without manual feature extraction when spatial information is insufficient.
2020, 57(12): 2490-2500.
DOI: 10.7544/issn1000-1239.2020.20200725
Abstract：
Public opinion events in social networks have a bearing on social harmony and stability. Analyzing the evolution trend of events so as to manage and control them is able to reduce the impact of malignant online public opinion. However, the lack of labelled data and the limited relevant resources makes the effective management of online public opinion challenging and complicated. To solve those difficulties, we propose a learning-to-rank algorithm for the events evolution trend evaluation, which makes full use of the expert knowledge in the labelled data and the correlation between labelled and unlabelled data to select important public opinion for management, in turn, improves the management efficiency. Firstly, based on the experiences and demands of public opinion management, we design a measurable, accessible and meaningful hierarchical index system, which is derived from the three most important factors of events, for evolution trend evaluation. Secondly, we build an evaluation model for evolution trend evaluation based on the graph convolutional network. Specifically, our model uses the local sensitive Hash algorithm to mine the structural information from the data node’s neighborhood and generates the mixed feature of the data node and its neighbor. Finally, we design different loss functions for the labelled and unlabelled data respectively, in order to realize the comprehensive utilization of the expert knowledge in the labelled data and the spatial structure information in the unlabelled data. We verify the efficiency of the proposed model on public datasets MQ 2007-semi and MQ 2008-semi. We also build a real-world public opinion event dataset to verify the practicability and generalization of the proposed algorithm. The experimental results show that the proposed model can evaluate the public opinion event evolution trend with limited expert knowledge, and provide decision support for public opinion event management with limited resources.
Public opinion events in social networks have a bearing on social harmony and stability. Analyzing the evolution trend of events so as to manage and control them is able to reduce the impact of malignant online public opinion. However, the lack of labelled data and the limited relevant resources makes the effective management of online public opinion challenging and complicated. To solve those difficulties, we propose a learning-to-rank algorithm for the events evolution trend evaluation, which makes full use of the expert knowledge in the labelled data and the correlation between labelled and unlabelled data to select important public opinion for management, in turn, improves the management efficiency. Firstly, based on the experiences and demands of public opinion management, we design a measurable, accessible and meaningful hierarchical index system, which is derived from the three most important factors of events, for evolution trend evaluation. Secondly, we build an evaluation model for evolution trend evaluation based on the graph convolutional network. Specifically, our model uses the local sensitive Hash algorithm to mine the structural information from the data node’s neighborhood and generates the mixed feature of the data node and its neighbor. Finally, we design different loss functions for the labelled and unlabelled data respectively, in order to realize the comprehensive utilization of the expert knowledge in the labelled data and the spatial structure information in the unlabelled data. We verify the efficiency of the proposed model on public datasets MQ 2007-semi and MQ 2008-semi. We also build a real-world public opinion event dataset to verify the practicability and generalization of the proposed algorithm. The experimental results show that the proposed model can evaluate the public opinion event evolution trend with limited expert knowledge, and provide decision support for public opinion event management with limited resources.
2020, 57(12): 2501-2513.
DOI: 10.7544/issn1000-1239.2020.20200750
Abstract：
Effective search over knowledge graphs can provide support for applications such as question answering and semantic search. However, when the user cannot give a clear query, accurately capturing the user’s interest and finding the answer are difficult for machines. Hybrid human-machine active search provides a pathway to bridge the gap between users and machines. Hybrid human-machine active search is a kind of interactive search, and it is originated from the thought of active learning in machine learning field. The core idea is to let the machine issue questions to the user, to obtain information from the user feedback, and then based on this information to eventually capture user intent and return answers. In this paper, we stand on recent advances in knowledge graph representation learning techniques and propose a hybrid human-machine active search in the vector space of a knowledge graph. Specifically, the knowledge graph is first embedded into the low-dimensional vector space, which quantizes the characteristics of entities and relationships, and at the same time, the user’s interests and preferences are embedded into the same space. Then, the machine actively proposes questions to the user, and gets the feedback information by asking the user to rate the specific entity, thus updating the user preference positioning in the vector space. We design an evaluation method to measure the user’s interest in a specific entity based on the Euclidean distance between the preference point and other entities, and finally find the final target entity to return to the user after multiple turns of human-machine interaction. In the experiment part, we conduct experiments on the knowledge graph embedding and the active search respectively, and the experimental results show that the proposed method is effective.
Effective search over knowledge graphs can provide support for applications such as question answering and semantic search. However, when the user cannot give a clear query, accurately capturing the user’s interest and finding the answer are difficult for machines. Hybrid human-machine active search provides a pathway to bridge the gap between users and machines. Hybrid human-machine active search is a kind of interactive search, and it is originated from the thought of active learning in machine learning field. The core idea is to let the machine issue questions to the user, to obtain information from the user feedback, and then based on this information to eventually capture user intent and return answers. In this paper, we stand on recent advances in knowledge graph representation learning techniques and propose a hybrid human-machine active search in the vector space of a knowledge graph. Specifically, the knowledge graph is first embedded into the low-dimensional vector space, which quantizes the characteristics of entities and relationships, and at the same time, the user’s interests and preferences are embedded into the same space. Then, the machine actively proposes questions to the user, and gets the feedback information by asking the user to rate the specific entity, thus updating the user preference positioning in the vector space. We design an evaluation method to measure the user’s interest in a specific entity based on the Euclidean distance between the preference point and other entities, and finally find the final target entity to return to the user after multiple turns of human-machine interaction. In the experiment part, we conduct experiments on the knowledge graph embedding and the active search respectively, and the experimental results show that the proposed method is effective.
2020, 57(12): 2514-2522.
DOI: 10.7544/issn1000-1239.2020.20200741
Abstract：
In recent years, numerous research works have been devoted to knowledge graph embedding learning which aims to encode entities and relations of the knowledge graph in continuous low-dimensional vector spaces. And the learned embedding representations have been successfully utilized to alleviate the computational inefficiency problem of large-scale knowledge graphs. However, most existing embedding models only consider the structural information of the knowledge graph. The contextual information and literal information are also abundantly contained in knowledge graphs and could be exploited to learn better embedding representations. In this paper, we focus on this problem and propose a rule-guided joint embedding learning model which integrates the contextual information and literal information into the embedding representations of entities and relations based on graph convolutional networks. Especially for the convolutional encoding of the contextual information, we measure the importance of a piece of contextual information by computing its confidence and relatedness metrics. For the confidence metric, we define a simple and effective rule and propose a rule-guided computing method. For the relatedness metric, we propose a computing method based on the representations of the literal information. We conduct extensive experiments on two benchmark datasets, and the experimental results demonstrate the effectiveness of the proposed model.
In recent years, numerous research works have been devoted to knowledge graph embedding learning which aims to encode entities and relations of the knowledge graph in continuous low-dimensional vector spaces. And the learned embedding representations have been successfully utilized to alleviate the computational inefficiency problem of large-scale knowledge graphs. However, most existing embedding models only consider the structural information of the knowledge graph. The contextual information and literal information are also abundantly contained in knowledge graphs and could be exploited to learn better embedding representations. In this paper, we focus on this problem and propose a rule-guided joint embedding learning model which integrates the contextual information and literal information into the embedding representations of entities and relations based on graph convolutional networks. Especially for the convolutional encoding of the contextual information, we measure the importance of a piece of contextual information by computing its confidence and relatedness metrics. For the confidence metric, we define a simple and effective rule and propose a rule-guided computing method. For the relatedness metric, we propose a computing method based on the representations of the literal information. We conduct extensive experiments on two benchmark datasets, and the experimental results demonstrate the effectiveness of the proposed model.
2020, 57(12): 2523-2546.
DOI: 10.7544/issn1000-1239.2020.20190767
Abstract：
With the in-depth advancement of informational education and the rapid development of online education, a large amount of fragmented educational data are generated during the learning process of students. How to mine and analyze these educational big data has become an urgent problem in the education and the knowledge engineering with big data fields. As for the dynamic education data, knowledge tracing models trace the cognitive status of students over time by analyzing the students’ exercising data generated in the learning process, so as to predict the exercising performance of students in the future time. In this paper, knowledge tracing models in educational big data are reviewed, analyzed, and discussed. Firstly, knowledge tracing models are introduced in detail from the perspective of their principles, steps, and model variants, including two mainstream knowledge tracing models based on Bayesian methods and deep learning methods. Then, the application scenarios of knowledge tracing models are explained from five aspects: student performance prediction, cognitive state assessment, psychological factor analysis, exercise sequence, and programming practice. The strengths and weaknesses in Bayesian knowledge tracing models and Deep Knowledge Tracing models are discussed through the two classic models BKT and DKT. Finally, some future directions of knowledge tracing models are given.
With the in-depth advancement of informational education and the rapid development of online education, a large amount of fragmented educational data are generated during the learning process of students. How to mine and analyze these educational big data has become an urgent problem in the education and the knowledge engineering with big data fields. As for the dynamic education data, knowledge tracing models trace the cognitive status of students over time by analyzing the students’ exercising data generated in the learning process, so as to predict the exercising performance of students in the future time. In this paper, knowledge tracing models in educational big data are reviewed, analyzed, and discussed. Firstly, knowledge tracing models are introduced in detail from the perspective of their principles, steps, and model variants, including two mainstream knowledge tracing models based on Bayesian methods and deep learning methods. Then, the application scenarios of knowledge tracing models are explained from five aspects: student performance prediction, cognitive state assessment, psychological factor analysis, exercise sequence, and programming practice. The strengths and weaknesses in Bayesian knowledge tracing models and Deep Knowledge Tracing models are discussed through the two classic models BKT and DKT. Finally, some future directions of knowledge tracing models are given.
2020, 57(12): 2547-2555.
DOI: 10.7544/issn1000-1239.2020.20190583
Abstract：
Obstructive sleep apnea (OSA) is the most common sleep respiratory disorder, and it is a potential threat to many physiological systems, especially the cardiovascular system. Most of the previous methods for OSA detection extracted the shallow features from electrocardiograph (ECG) which would be used in classifiers, and they failed to achieve excellent performances on the ECG signal with high noise and large datasets. To solve this kind of problem, this paper proposes a long short-term memory recurrent neural network (LSTM-RNN) based on combination of multiple kinds of feature signals. The method fuses multiple kinds of shallow feature signals that are extracted from ECG signals and learns the deep feature from the fused signals. The accuracy of OSA detection model in long ECG segments is increased and the generalization ability on large datasets is improved. An effective preprocessing method is propesed for shallow feature signals to highlight the variation of OSA time sequences. The preprocessing method may improve the convergence of training neural networks, reduce the impact of outlier noise, and further improve the detection accuracy of the model for the ECG segments with high noise. The experimental results indicate that our method is superior to the existing methods in the accuracy of per-segment OSA detection.
Obstructive sleep apnea (OSA) is the most common sleep respiratory disorder, and it is a potential threat to many physiological systems, especially the cardiovascular system. Most of the previous methods for OSA detection extracted the shallow features from electrocardiograph (ECG) which would be used in classifiers, and they failed to achieve excellent performances on the ECG signal with high noise and large datasets. To solve this kind of problem, this paper proposes a long short-term memory recurrent neural network (LSTM-RNN) based on combination of multiple kinds of feature signals. The method fuses multiple kinds of shallow feature signals that are extracted from ECG signals and learns the deep feature from the fused signals. The accuracy of OSA detection model in long ECG segments is increased and the generalization ability on large datasets is improved. An effective preprocessing method is propesed for shallow feature signals to highlight the variation of OSA time sequences. The preprocessing method may improve the convergence of training neural networks, reduce the impact of outlier noise, and further improve the detection accuracy of the model for the ECG segments with high noise. The experimental results indicate that our method is superior to the existing methods in the accuracy of per-segment OSA detection.
2020, 57(12): 2556-2570.
DOI: 10.7544/issn1000-1239.2020.20190275
Abstract：
The service of personalized recommendations in event-based social networks (EBSN) is a very significant and valuable issue. Most of existing research work are mainly based on the ordinary graph to model relationships in EBSN. However, EBSN is a heterogeneous and complex network with many different types of entities. Because of that, modeling EBSN with ordinary graphs has the problem of high-dimensional information loss, resulting in reduced recommendation quality. Based on this background, in this paper, we first propose a hypergraph-based personalized recommendation (PRH) algorithm in EBSN. The basic idea is to make use of the characteristics of hypergraphs without losing high-dimensional data information to model high-dimensional complex social relationship data in EBSN more accurately, and to use regularized calculation of manifold ordering to obtain preliminary recommendation results. Next, this paper proposes an optimized PRH (oPRH) algorithm from the perspective of improving the query vector setting method and applying diverse weights to all sorts of different types of super edges to further optimize the recommendation results obtained by the PRH algorithm, so as to achieve accurate recommendation. The extended experiments show that the hypergraph-based personalized recommendation algorithm in EBSN and its optimization algorithm have higher accuracy than the previous ordinary graph-based recommendation algorithms.
The service of personalized recommendations in event-based social networks (EBSN) is a very significant and valuable issue. Most of existing research work are mainly based on the ordinary graph to model relationships in EBSN. However, EBSN is a heterogeneous and complex network with many different types of entities. Because of that, modeling EBSN with ordinary graphs has the problem of high-dimensional information loss, resulting in reduced recommendation quality. Based on this background, in this paper, we first propose a hypergraph-based personalized recommendation (PRH) algorithm in EBSN. The basic idea is to make use of the characteristics of hypergraphs without losing high-dimensional data information to model high-dimensional complex social relationship data in EBSN more accurately, and to use regularized calculation of manifold ordering to obtain preliminary recommendation results. Next, this paper proposes an optimized PRH (oPRH) algorithm from the perspective of improving the query vector setting method and applying diverse weights to all sorts of different types of super edges to further optimize the recommendation results obtained by the PRH algorithm, so as to achieve accurate recommendation. The extended experiments show that the hypergraph-based personalized recommendation algorithm in EBSN and its optimization algorithm have higher accuracy than the previous ordinary graph-based recommendation algorithms.
2020, 57(12): 2571-2582.
DOI: 10.7544/issn1000-1239.2020.20190754
Abstract：
With the continuous improvement of the performance of the IoT and mobile devices, a new type of computing architecture, edge computing, came into being. The emergence of edge computing has changed the situation where data needs to be uploaded to the cloud for data processing, fully utilizing the computing and storage capabilities of edge IoT devices. Edge nodes process private data locally and no longer need upload a large amount of data to the cloud for processing, reducing the transmission delay. The demand for implementing artificial intelligence frameworks on edge nodes is also increasing day by day. Because the federated learning mechanism does not require centralized data for model training, it is more suitable for edge network machine learning scenarios where the average amount of data of nodes is limited. This paper proposes an efficient asynchronous federated learning mechanism for edge network computing (EAFLM), which compresses the redundant communication between the nodes and the parameter server during the training process according to the self-adaptive threshold. The gradient update algorithm based on dual-weight correction allows nodes to join or withdraw from federated learning during any process of learning. Experimental results show that when the gradient communication is compressed to 8.77% of the original communication times, the accuracy of the test set is only reduced by 0.03%.
With the continuous improvement of the performance of the IoT and mobile devices, a new type of computing architecture, edge computing, came into being. The emergence of edge computing has changed the situation where data needs to be uploaded to the cloud for data processing, fully utilizing the computing and storage capabilities of edge IoT devices. Edge nodes process private data locally and no longer need upload a large amount of data to the cloud for processing, reducing the transmission delay. The demand for implementing artificial intelligence frameworks on edge nodes is also increasing day by day. Because the federated learning mechanism does not require centralized data for model training, it is more suitable for edge network machine learning scenarios where the average amount of data of nodes is limited. This paper proposes an efficient asynchronous federated learning mechanism for edge network computing (EAFLM), which compresses the redundant communication between the nodes and the parameter server during the training process according to the self-adaptive threshold. The gradient update algorithm based on dual-weight correction allows nodes to join or withdraw from federated learning during any process of learning. Experimental results show that when the gradient communication is compressed to 8.77% of the original communication times, the accuracy of the test set is only reduced by 0.03%.
2020, 57(12): 2583-2595.
DOI: 10.7544/issn1000-1239.2020.20190854
Abstract：
CNN(convolutional neural network) and RNN(recurrent neural network) have been widely used in the field of text sentiment analysis and have achieved good results in recent years. However, there is a problem of contextual dependency between texts, although CNN can extract local features between consecutive words of a sentence, it ignores the contextual semantic information between words. BiGRU(bidirectional gated recurrent unit) network can not only solve the problem of gradient disappearance or gradient explosion in traditional RNN model, but also make up for the shortcomings that CNN can’t effectively extract contextual semantic information of long text, while it can’t extract local features as well as CNN. Therefore, this paper proposes a MC-AttCNN-AttBiGRU(multi-channels CNN and BiGRU network based on attention mechanism) model. The model can notice the important words for sentiment classification in the sentence. It combines the advantages of CNN to extract local features of text and BiGRU network to extract contextual semantic information of long text, which improves the text feature extraction ability of the model. The experimental results on the Tan Songbo Hotel Review dataset and IMDB dataset show that the proposed model can extract richer text features than other baseline models, and can achieve better classification results than other baseline models.
CNN(convolutional neural network) and RNN(recurrent neural network) have been widely used in the field of text sentiment analysis and have achieved good results in recent years. However, there is a problem of contextual dependency between texts, although CNN can extract local features between consecutive words of a sentence, it ignores the contextual semantic information between words. BiGRU(bidirectional gated recurrent unit) network can not only solve the problem of gradient disappearance or gradient explosion in traditional RNN model, but also make up for the shortcomings that CNN can’t effectively extract contextual semantic information of long text, while it can’t extract local features as well as CNN. Therefore, this paper proposes a MC-AttCNN-AttBiGRU(multi-channels CNN and BiGRU network based on attention mechanism) model. The model can notice the important words for sentiment classification in the sentence. It combines the advantages of CNN to extract local features of text and BiGRU network to extract contextual semantic information of long text, which improves the text feature extraction ability of the model. The experimental results on the Tan Songbo Hotel Review dataset and IMDB dataset show that the proposed model can extract richer text features than other baseline models, and can achieve better classification results than other baseline models.
2020, 57(12): 2596-2609.
DOI: 10.7544/issn1000-1239.2020.20190670
Abstract：
Current machine learning models require numbers of hyperparameters. Adjusting those hyperparameters is an exhausting job. Thus, hyperparameters optimization algorithms play important roles in machine learning application. In hyperparameters optimization algorithms, sequential model-based optimization algorithms (SMBO) and parallel SMBO algorithms are state-of-the-art hyperpara-meter optimization methods. However, (parallel) SMBO algorithms do not take the best hyperpara-meters high possibility range and gradients into considerasion. It is obvious that best hyperparameters high possibility range and hyperparameter gradients can accelerate traditional hyperparameters optimization algorithms. In this paper, we accelerate the traditional SMBO method and name our method as AccSMBO. In AccSMBO, we build a novel gradient-based multikernel Gaussian process. Our multikernel Gaussian process has a good generalization ability which reduces the gradient noise influence on SMBO algorithm. And we also design meta-acquisition function and parallel resource allocation plan which encourage that (parallel) SMBO puts more attention on the best hyperpara-meters high possibility range. In theory, our method ensures that all hyperparameter gradient information and the best hyperparameters high possibility range information are fully used. In L2 norm regularised logistic loss function experiments, on different scales datasets: small-scale dataset Pc4, middle-scale dataset Rcv1, large-scale dataset Real-sim, compared with state-of-the-art gradient based algorithm: HOAG and state-of-the-art SMBO algorithm: SMAC, our method exhibits the best performance.
Current machine learning models require numbers of hyperparameters. Adjusting those hyperparameters is an exhausting job. Thus, hyperparameters optimization algorithms play important roles in machine learning application. In hyperparameters optimization algorithms, sequential model-based optimization algorithms (SMBO) and parallel SMBO algorithms are state-of-the-art hyperpara-meter optimization methods. However, (parallel) SMBO algorithms do not take the best hyperpara-meters high possibility range and gradients into considerasion. It is obvious that best hyperparameters high possibility range and hyperparameter gradients can accelerate traditional hyperparameters optimization algorithms. In this paper, we accelerate the traditional SMBO method and name our method as AccSMBO. In AccSMBO, we build a novel gradient-based multikernel Gaussian process. Our multikernel Gaussian process has a good generalization ability which reduces the gradient noise influence on SMBO algorithm. And we also design meta-acquisition function and parallel resource allocation plan which encourage that (parallel) SMBO puts more attention on the best hyperpara-meters high possibility range. In theory, our method ensures that all hyperparameter gradient information and the best hyperparameters high possibility range information are fully used. In L2 norm regularised logistic loss function experiments, on different scales datasets: small-scale dataset Pc4, middle-scale dataset Rcv1, large-scale dataset Real-sim, compared with state-of-the-art gradient based algorithm: HOAG and state-of-the-art SMBO algorithm: SMAC, our method exhibits the best performance.
2020, 57(12): 2610-2620.
DOI: 10.7544/issn1000-1239.2020.20190721
Abstract：
Benefitting from SIMD (single instruction multiple data) vectorization, processors’ floating-point compute capability has been increased largely. However, the current SIMD units and SIMD instruction sets only support basic operations like arithmetic operations (addition, subtraction, multiplication, and division) and logical operations, and do not provide direct support for floating-point transcendental functions. Since transcendental functions are the most time-consuming functions in floating-point computing, improving these functions’ performance has become a key point in math library optimization. In this paper, we design and propose a new method that utilizes SIMD units to vectorize and optimize trigonometric functions (which are one class of transcendental functions). While most vector implementations use a unified algorithm to process all floating-point numbers, we select and import several optimizable branches from the scalar implementations to process different ranges of floating-point numbers. We further utilize a series of optimization techniques to accelerate the vectorized scalar code. By combining the piecewise computing of the scalar implementations and the vectorization advantage of the vector implementations, our method optimizes branch processing in vector trigonometric functions, reduces redundant computation, and increases the utilization of SIMD units. Experimental results show that our method meets accuracy requirement, and effectively improves trigonometric functions’ performance. Compared with original vector trigonometric functions, the average performance speedup of optimized functions is 2.04x.
Benefitting from SIMD (single instruction multiple data) vectorization, processors’ floating-point compute capability has been increased largely. However, the current SIMD units and SIMD instruction sets only support basic operations like arithmetic operations (addition, subtraction, multiplication, and division) and logical operations, and do not provide direct support for floating-point transcendental functions. Since transcendental functions are the most time-consuming functions in floating-point computing, improving these functions’ performance has become a key point in math library optimization. In this paper, we design and propose a new method that utilizes SIMD units to vectorize and optimize trigonometric functions (which are one class of transcendental functions). While most vector implementations use a unified algorithm to process all floating-point numbers, we select and import several optimizable branches from the scalar implementations to process different ranges of floating-point numbers. We further utilize a series of optimization techniques to accelerate the vectorized scalar code. By combining the piecewise computing of the scalar implementations and the vectorization advantage of the vector implementations, our method optimizes branch processing in vector trigonometric functions, reduces redundant computation, and increases the utilization of SIMD units. Experimental results show that our method meets accuracy requirement, and effectively improves trigonometric functions’ performance. Compared with original vector trigonometric functions, the average performance speedup of optimized functions is 2.04x.
2020, 57(12): 2621-2634.
DOI: 10.7544/issn1000-1239.2020.20190734
Abstract：
The Stencil computation, i.e. the structured grid computing, is a very common kind of loop nesting algorithm in scientific and engineering applications. The exhaustively studied tiling method is of great effectiveness as one of the transformation techniques to exploit the data locality and parallelism of Stencil computations. However, the state-of-the-art work of tiling often uniformly handles different Stencil shapes. We first present a concept called natural block to identify the difference between the star and box Stencils. Then we propose a new two-level tessellation scheme for star Stencils, where the natural block, as well as its successive blocks can tessellate the spatial space and their extensions along the time dimension are able to form a tessellation of the iteration space. Furthermore, a novel implementation technique called double updating is developed for star Stencils specifically, which updates each element twice continuously and improves the in-core data reuse pattern. In addition, we adopt coarsening and block reuse to enhance the parallelization performance. Theoretical analysis shows that our scheme achieves a better cache complexity than existing methods such as Girih and Pluto. The experiments on performance and bandwidth are conducted on a multicore system. The results demonstrate the effectiveness of our approach.
The Stencil computation, i.e. the structured grid computing, is a very common kind of loop nesting algorithm in scientific and engineering applications. The exhaustively studied tiling method is of great effectiveness as one of the transformation techniques to exploit the data locality and parallelism of Stencil computations. However, the state-of-the-art work of tiling often uniformly handles different Stencil shapes. We first present a concept called natural block to identify the difference between the star and box Stencils. Then we propose a new two-level tessellation scheme for star Stencils, where the natural block, as well as its successive blocks can tessellate the spatial space and their extensions along the time dimension are able to form a tessellation of the iteration space. Furthermore, a novel implementation technique called double updating is developed for star Stencils specifically, which updates each element twice continuously and improves the in-core data reuse pattern. In addition, we adopt coarsening and block reuse to enhance the parallelization performance. Theoretical analysis shows that our scheme achieves a better cache complexity than existing methods such as Girih and Pluto. The experiments on performance and bandwidth are conducted on a multicore system. The results demonstrate the effectiveness of our approach.
2020, 57(12): 2635-2647.
DOI: 10.7544/issn1000-1239.2020.20190731
Abstract：
The symmetric matrix tridiagonalization is the key computational process for solving dense eigenproblems. This paper presents the implementation of the dense symmetric matrix tridiagonal hybrid parallel blocked algorithm based on MPI(message passing interface)+CUDA(compute unified device architecture) for GPU cluster. The parallel algorithm design uses a two-level parallel method of MPI cluster level and GPU level. In the MPI-level parallelism, the communication performance of the tridiagonal MPI parallel algorithm is improved by designing the global data communication between the row-column communication domains in the two-dimensional communication domain as a completely parallel point-to-point data communication method. Moreover, by improving the original matrix tridiagonalized MPI parallel algorithm, the use of irregular matrix-vector operation in GPU-level parallelism is avoided, and the parallel performance of this part is improved by about 1 time. What’s more, the small-grained computing existing in the GPU parallel is merged into a larger granularity calculation, which fully utilize the computing power of the GPU by increasing the computational intensity, thereby increasing the utilization of the GPU and improving the performance of the algorithm. In addition, multiple CUDA streams can be used to enable independent CUDA operations in the algorithm to be concurrently executed in different streams. Furthermore, in the parallel algorithm, the asynchronous data transmission between the CPU and the GPU is utilized, so that the data transmission and the kernel function in different streams are simultaneously executed, which hides the time of data transmission and improves the performance of the algorithm. On the supercomputer system Era of the Computer Network Center of the Chinese Academy of Sciences, each compute node is configured with 2 Nvidia Tesla K20 GPGPU cards and 2 Intel E5-2680 V2 processors, we tested the performance of the implementation of the tridiagonalization blocked algorithm with GPGPU cards. It has achieved better acceleration, performance and scalability.
The symmetric matrix tridiagonalization is the key computational process for solving dense eigenproblems. This paper presents the implementation of the dense symmetric matrix tridiagonal hybrid parallel blocked algorithm based on MPI(message passing interface)+CUDA(compute unified device architecture) for GPU cluster. The parallel algorithm design uses a two-level parallel method of MPI cluster level and GPU level. In the MPI-level parallelism, the communication performance of the tridiagonal MPI parallel algorithm is improved by designing the global data communication between the row-column communication domains in the two-dimensional communication domain as a completely parallel point-to-point data communication method. Moreover, by improving the original matrix tridiagonalized MPI parallel algorithm, the use of irregular matrix-vector operation in GPU-level parallelism is avoided, and the parallel performance of this part is improved by about 1 time. What’s more, the small-grained computing existing in the GPU parallel is merged into a larger granularity calculation, which fully utilize the computing power of the GPU by increasing the computational intensity, thereby increasing the utilization of the GPU and improving the performance of the algorithm. In addition, multiple CUDA streams can be used to enable independent CUDA operations in the algorithm to be concurrently executed in different streams. Furthermore, in the parallel algorithm, the asynchronous data transmission between the CPU and the GPU is utilized, so that the data transmission and the kernel function in different streams are simultaneously executed, which hides the time of data transmission and improves the performance of the algorithm. On the supercomputer system Era of the Computer Network Center of the Chinese Academy of Sciences, each compute node is configured with 2 Nvidia Tesla K20 GPGPU cards and 2 Intel E5-2680 V2 processors, we tested the performance of the implementation of the tridiagonalization blocked algorithm with GPGPU cards. It has achieved better acceleration, performance and scalability.
2020, 57(12): 2648-2661.
DOI: 10.7544/issn1000-1239.2020.20190704
Abstract：
A content-centrality-based probabilistic caching content placement method (CCPCP) is proposed to reduce cache redundancy as well as achieve better performance in terms of cache hits and utilization in information-centric networking (ICN). Different from those metrics that focus only on the centrality based on topology in the traditional network, the content centrality metric is developed in this paper. The content centrality metric not only describes the location centrality of cache nodes, but also describes the attribute of the content. In CCPCP method, each cache node individually makes a cache decision with a certain caching probability. In particular, each cache node adaptively calculates the caching probability by jointly considering the content centrality and the delay savings, which is proportional to the location centrality, the content popularity and the access delay savings. That is, the larger location centrality of cache node, the higher popularity of content, the more access delay savings, and the larger the caching probability of cache node caching the passing content. Simulation results show that CCPCP outperforms the state-of-art probabilistic methods in terms of cache hit ratio, caching content utilization ratio, access delay and cache redundancy under the less number of content replicas, even in the case that the reduction of number of content replicas is up to 32%.
A content-centrality-based probabilistic caching content placement method (CCPCP) is proposed to reduce cache redundancy as well as achieve better performance in terms of cache hits and utilization in information-centric networking (ICN). Different from those metrics that focus only on the centrality based on topology in the traditional network, the content centrality metric is developed in this paper. The content centrality metric not only describes the location centrality of cache nodes, but also describes the attribute of the content. In CCPCP method, each cache node individually makes a cache decision with a certain caching probability. In particular, each cache node adaptively calculates the caching probability by jointly considering the content centrality and the delay savings, which is proportional to the location centrality, the content popularity and the access delay savings. That is, the larger location centrality of cache node, the higher popularity of content, the more access delay savings, and the larger the caching probability of cache node caching the passing content. Simulation results show that CCPCP outperforms the state-of-art probabilistic methods in terms of cache hit ratio, caching content utilization ratio, access delay and cache redundancy under the less number of content replicas, even in the case that the reduction of number of content replicas is up to 32%.
2020, 57(12): 2662-2672.
DOI: 10.7544/issn1000-1239.2020.20190592
Abstract：
How to appropriately select link quality metrics and build a link quality estimation model with better performance, generalization capability, and lower time complexity is one of the key challenges in wireless sensor networks. We select M\-{CS}={μ,r,σ\+2}, where μ={μ\-{lqi}, μ\-{rssi},μ\-{snr}},r={r\-{lqi},r\-{rssi},r\-{snr}},σ\+2={σ\+2\-{lqi},σ\+2\-{rssi},σ\+2\-{snr}}, as link quality metric candidate set. A link quality metric selection algorithm based on wrapper is proposed, which employs adaptive general regression neural network (AGRNN) to evaluate the importance of link quality metric candidate subsets so as to select link quality metrics. Taking advantages of general regression neural network (GRNN) in classification and time complexity, this paper proposes a link quality estimation model based on AGRNN which assigns different smoothing factors to each link quality metric and adaptively modifies them by using back propagation. Indexes, such as accuracy, recall, generalization error and computing time, are used to evaluate the link quality estimation models. In scenarios of the indoor scenario, the park scenario and the motorway scenario, the experimental results show that the proposed link quality estimation model can achieve better performance, generalization capability, and lower time complexity, compared with link quality estimation models based on polynomial, support vector classifier and random forest respectively.
How to appropriately select link quality metrics and build a link quality estimation model with better performance, generalization capability, and lower time complexity is one of the key challenges in wireless sensor networks. We select M\-{CS}={μ,r,σ\+2}, where μ={μ\-{lqi}, μ\-{rssi},μ\-{snr}},r={r\-{lqi},r\-{rssi},r\-{snr}},σ\+2={σ\+2\-{lqi},σ\+2\-{rssi},σ\+2\-{snr}}, as link quality metric candidate set. A link quality metric selection algorithm based on wrapper is proposed, which employs adaptive general regression neural network (AGRNN) to evaluate the importance of link quality metric candidate subsets so as to select link quality metrics. Taking advantages of general regression neural network (GRNN) in classification and time complexity, this paper proposes a link quality estimation model based on AGRNN which assigns different smoothing factors to each link quality metric and adaptively modifies them by using back propagation. Indexes, such as accuracy, recall, generalization error and computing time, are used to evaluate the link quality estimation models. In scenarios of the indoor scenario, the park scenario and the motorway scenario, the experimental results show that the proposed link quality estimation model can achieve better performance, generalization capability, and lower time complexity, compared with link quality estimation models based on polynomial, support vector classifier and random forest respectively.
2020, 57(12): 2673-2682.
DOI: 10.7544/issn1000-1239.2020.20190691
Abstract：
Due to the high dynamic variability, suddenness and irreversibility of network traffic, the statistical characteristics and distribution of traffic may change dynamically, resulting in a concept drift problem based on the flow-based machine learning method. The problem of concept drift makes the classification model based on the original data set worse on the new sample, which causes the classification accuracy to decrease. Based on this, a classification approach based on divergence for network traffic in presence of concept drift, named ECDD (ensemble classification based on divergence detection) is proposed. The method uses a double-layer window mechanism to track the concept drift. From the perspective of information entropy, the Jensen-Shannon divergence is used to measure the difference of data distribution between old and new windows, so as to effectively detect the concept drift. This paper draws on the idea of incremental ensemble learning, trains a new classifier on the concept drift traffic based on the pre-retention classifier, and replaces the classifier with the original performance degradation according to the classifier weight, so that the ensemble classifier is effectively updated. For common network application traffic, this paper constructs a concept drift data set according to different application feature distributions. This paper compares the method with common concept drift detection methods and the experimental results show that the method can effectively detect concept drift and update the classifier, showing better classification performance.
Due to the high dynamic variability, suddenness and irreversibility of network traffic, the statistical characteristics and distribution of traffic may change dynamically, resulting in a concept drift problem based on the flow-based machine learning method. The problem of concept drift makes the classification model based on the original data set worse on the new sample, which causes the classification accuracy to decrease. Based on this, a classification approach based on divergence for network traffic in presence of concept drift, named ECDD (ensemble classification based on divergence detection) is proposed. The method uses a double-layer window mechanism to track the concept drift. From the perspective of information entropy, the Jensen-Shannon divergence is used to measure the difference of data distribution between old and new windows, so as to effectively detect the concept drift. This paper draws on the idea of incremental ensemble learning, trains a new classifier on the concept drift traffic based on the pre-retention classifier, and replaces the classifier with the original performance degradation according to the classifier weight, so that the ensemble classifier is effectively updated. For common network application traffic, this paper constructs a concept drift data set according to different application feature distributions. This paper compares the method with common concept drift detection methods and the experimental results show that the method can effectively detect concept drift and update the classifier, showing better classification performance.
2020, 57(12): 2683-2693.
DOI: 10.7544/issn1000-1239.2020.20190683
Abstract：
A large quantity of data is transmitted through the network during the process in distributed big data processing framework, resulting in the time consumption for data transmission between each node becomes one of the main costs of the operation. However, in the case of heterogeneous bandwidth of nodes, traditional data partitioning methods such as Hash partitioning or range partitioning will be inefficient, due to the existence of bandwidth bottleneck nodes. Data partitioning is necessary for big data processing and inefficient data partitioning methods would significantly increase the running time of jobs. We therefore propose a data transmission model between nodes to reduce time consumption in distributed heterogeneous bandwidth networks. The model calculates each node’s optimal data distribution ratio to minimize the data transfer time, according to its uplink and downlink bandwidth as well as the initial data size. Besides, a bandwidth-based data partitioning method is designed based on the proposed model, enabling each node to allocate data under the optimal data distribution ratio. We demonstrate the effectiveness of our bandwidth-based data partitioning method through the implementation in the Apache Flink framework and have significantly improved efficiency. Extensive experimental results show that the bandwidth-based data partitioning method can effectively reduce the time consumption of data partitioning in distributed heterogeneous bandwidth conditions.
A large quantity of data is transmitted through the network during the process in distributed big data processing framework, resulting in the time consumption for data transmission between each node becomes one of the main costs of the operation. However, in the case of heterogeneous bandwidth of nodes, traditional data partitioning methods such as Hash partitioning or range partitioning will be inefficient, due to the existence of bandwidth bottleneck nodes. Data partitioning is necessary for big data processing and inefficient data partitioning methods would significantly increase the running time of jobs. We therefore propose a data transmission model between nodes to reduce time consumption in distributed heterogeneous bandwidth networks. The model calculates each node’s optimal data distribution ratio to minimize the data transfer time, according to its uplink and downlink bandwidth as well as the initial data size. Besides, a bandwidth-based data partitioning method is designed based on the proposed model, enabling each node to allocate data under the optimal data distribution ratio. We demonstrate the effectiveness of our bandwidth-based data partitioning method through the implementation in the Apache Flink framework and have significantly improved efficiency. Extensive experimental results show that the bandwidth-based data partitioning method can effectively reduce the time consumption of data partitioning in distributed heterogeneous bandwidth conditions.
2020, 57(12): 2694-2702.
DOI: 10.7544/issn1000-1239.2020.20190718
Abstract：
During the development of the processor, it is necessary to fully verify the instructions datapaths. The existing simulation verification methods have insufficient functional coverage in terms of instruction result operands constraints, relationship constraints between operands, and internal constraints of instructions, etc. This paper proposes an instruction constraint solving method based on satisfiability modulo theory (SMT) solver. The SMT solver is introduced to convert the instruction function verification tasks into constraint satisfaction problems. Constraint satisfaction problem techniques are used to generate validation tuple data, which can be used to verify the functional correctness of the instructions set. The modeling processes and examples are given in four aspects: the instruction result operand constraints, the instruction operand constraints, the instruction internal constraints, and float-pointing instructions operand constraints. In order to improve the modeling efficiency, we propose two strategies. First, once the time threshold is reached, the current process is terminated; second, using process management and thread management technology, a parallel solution framework for instruction function constraints is implemented, and a series of serial solving tasks are assigned to multiple threads that can be executed in parallel, and the speed of solution is accelerated under the conditions of the same constraints coverage. Our experiences show that under the right circumstances, instruction constraint solving technology based on SMT provides technical support for system-level functional verification to achieve test coverage of complex scenarios.
During the development of the processor, it is necessary to fully verify the instructions datapaths. The existing simulation verification methods have insufficient functional coverage in terms of instruction result operands constraints, relationship constraints between operands, and internal constraints of instructions, etc. This paper proposes an instruction constraint solving method based on satisfiability modulo theory (SMT) solver. The SMT solver is introduced to convert the instruction function verification tasks into constraint satisfaction problems. Constraint satisfaction problem techniques are used to generate validation tuple data, which can be used to verify the functional correctness of the instructions set. The modeling processes and examples are given in four aspects: the instruction result operand constraints, the instruction operand constraints, the instruction internal constraints, and float-pointing instructions operand constraints. In order to improve the modeling efficiency, we propose two strategies. First, once the time threshold is reached, the current process is terminated; second, using process management and thread management technology, a parallel solution framework for instruction function constraints is implemented, and a series of serial solving tasks are assigned to multiple threads that can be executed in parallel, and the speed of solution is accelerated under the conditions of the same constraints coverage. Our experiences show that under the right circumstances, instruction constraint solving technology based on SMT provides technical support for system-level functional verification to achieve test coverage of complex scenarios.
2020, 57(12): 2703-2716.
DOI: 10.7544/issn1000-1239.2020.20190686
Abstract：
The causal consistency of data in a distributed environment means that when data with causal dependence is updated, the dependency metadata in other distributed copies must be updated simultaneously, while meeting higher availability and performance requirements. To solve the problem of users put latency and updating visible latency in existing results, based on the data center stable vectors, combined with the principle of hybrid logical clocks and the HashGraph, we propose the Causal-Pdh model. To reduce the communication overhead caused by exchanging data between replicates, partial stabel vectors required by synchronizing data and Hash value as the message signatures are used instead of the whole data center stable vectors. The principle of virtual voting in HashGraph is used to improve the process of synchronizing the latest entries in each data center. Just like Gossip about Gossip: each parent node also randomly exchanges the latest status, and updates the clock regularly. This progress reduces the time of virtual voting between the replicates. Finally, it is verified by experiments that the Causal-Pdh model not only doesnt affect the throughput of the client query, but also reduces the wait latency of users put operation by 20.85% when the clock skew is severe. When the query is amplified in the system, the response time of request is reduced by 23.37%.
The causal consistency of data in a distributed environment means that when data with causal dependence is updated, the dependency metadata in other distributed copies must be updated simultaneously, while meeting higher availability and performance requirements. To solve the problem of users put latency and updating visible latency in existing results, based on the data center stable vectors, combined with the principle of hybrid logical clocks and the HashGraph, we propose the Causal-Pdh model. To reduce the communication overhead caused by exchanging data between replicates, partial stabel vectors required by synchronizing data and Hash value as the message signatures are used instead of the whole data center stable vectors. The principle of virtual voting in HashGraph is used to improve the process of synchronizing the latest entries in each data center. Just like Gossip about Gossip: each parent node also randomly exchanges the latest status, and updates the clock regularly. This progress reduces the time of virtual voting between the replicates. Finally, it is verified by experiments that the Causal-Pdh model not only doesnt affect the throughput of the client query, but also reduces the wait latency of users put operation by 20.85% when the clock skew is severe. When the query is amplified in the system, the response time of request is reduced by 23.37%.
