Started in January,1974(Monthly)
Supervised and Sponsored by Chongqing Southwest Information Co., Ltd.
ISSN 1002-137X
CN 50-1075/TP

Featured ArticlesMore...

  • Volume 47 Issue 8, 15 August 2020
      Development of Parallel Computing Subject
      CHEN Guo-liang, ZHANG Yu-jie,
      Computer Science. 2020, 47 (8): 1-4.  doi:10.11896/jsjkx.200600027
      Abstract ( 11 )   PDF(1062KB) ( 14 )   
      References | Related Articles | Metrics
      Computational science has become the third science in parallel with traditional theoretical science and experimentalscien-ce.They complement each other and promote the development of human science and technology and the progress of social civilization.The research frontiers of key scientific and economic problems in the 21st century may be solved by computing techniques and computing science.High-performance computing is a manifestation of a country’s comprehensive national strength, and it is one of the key technologies supporting the continuous development of national strength.It has an important strategic position in national defense security, high-tech development and national economic construction.Through more than 40 years of development, we have focused on parallel computers, parallel algorithms and parallel programming, integrating parallel computer architecture, numerical and non-numerical parallel algorithm design and parallel program design, forming parallel computing “architecture-algorithm-programming-application” disciplinary system and system curriculum framework.This article reviews the work we have done in the development of parallel computing, and introduces the calculation methods in non-numerical computing and the research of new non-von Neumann structured computer architecture.
      Survey of Heterogeneous Hybrid Parallel Computing
      YANG Wang-dong, WANG Hao-tian, ZHANG Yu-feng, LIN Sheng-le, CAI Qin-yun
      Computer Science. 2020, 47 (8): 5-16.  doi:10.11896/jsjkx.200600045
      Abstract ( 5 )   PDF(3592KB) ( 8 )   
      References | Related Articles | Metrics
      With the rapid increase in computing power demand of computer applications such as artificial intelligence and big data and the diversification of application scenarios, the research of heterogeneous hybrid parallel computing has become the focus of research.This paper introduces the current main heterogeneous computer architecture, including CPU/coprocessor, CPU/many-core processor, CPU/ASCI and CPU/FPGA heterogeneous architectures.The changes made by the heterogeneous hybrid parallel programming model with the development of various heterogeneous hybrid structures are briefly described, which is a transformation and re-implementation of an existing language, or an extension of an existing heterogeneous programming language, or heterogeneous programming using instructional statements, or container pattern collaborative programming.The analysis shows that the heterogeneous hybrid parallel computing architecture will further strengthen the support for AI, and will also enhance the versatility of the software.This paper reviewes the key technologies in heterogeneous hybrid parallel computing, including parallel task partitioning, task mapping, data communication, data access between heterogeneous processors, parallel synchronization of heterogeneous collaboration, and pipeline parallelism of heterogeneous resources.Based on these key technologies, this paper points out the challenges faced by heterogeneous hybrid parallel computing, such as programming difficulties, portability difficulties, large data communication overhead, complex data access, complex parallel control, and uneven resource load.The challenges faced by heterogeneous hybrid parallel computing are analyzed, and this paper concludes that the current key core technologies need to be integrated from general-purpose and AI-specific heterogeneous computing, seamless migration of heterogeneous architectures, unified programming model, integration of storage and computing, and intelligence breakthroughs in task division and allocation
      Communication Optimization Method of Heterogeneous Cluster Application Based on New Language Mechanism
      CUI Xiang, LI Xiao-wen, CHEN Yi-feng
      Computer Science. 2020, 47 (8): 17-15.  doi:10.11896/jsjkx.200100124
      Abstract ( 8 )   PDF(1901KB) ( 12 )   
      References | Related Articles | Metrics
      Compared with traditional cluster, heterogeneous cluster has obvious advantage in cost performance.However, compared with the rapidly developing hardware technology, the current software technology is still backward and cannot adapt to the constantly updated heterogeneous hardware and the super-large scale parallel computing environment.Currently, the common solution is to directly use parallel programming tools for different hardware.The disadvantages of this combination solution are that the programming level is low and it is difficult to develop, modify and debug.This paper introduces a new language mechanism to describe the multi-dimensional rule structure, arrangement and communication mode of data and threads.A new method of software migration and optimization between heterogeneous systems based on new language mechanism is proposed.Taking the direct normal turbulence simulation as an example, the communication optimization and fast migration for different heterogeneous systems are realized.
      Joint Optimization Algorithm for Partition-Scheduling of Dynamic Partial Reconfigurable Systems Based on Simulated Annealing
      WANG Zhe, TANG Qi, WANG Ling, WEI Ji-bo
      Computer Science. 2020, 47 (8): 26-31.  doi:10.11896/jsjkx.200500110
      Abstract ( 2 )   PDF(1476KB) ( 3 )   
      References | Related Articles | Metrics
      Dynamically partially reconfigurable (DPR) technology based on FPGA has many applications in the field of high-performance computing because of its advantages in processing efficiency and power consumption.In the DPR system, the partition of the reconfigurable region and task scheduling determine the performance of the entire system.Therefore, how to model the lo-gic resource partition and scheduling of the DPR system and devising an efficient solution algorithm are the keys to ensure the performance of the system.Based on the establishment of the partition and scheduling model, a joint optimization algorithm of DPR system partition-scheduling based on simulated annealing (SA) is designed to optimize the reconfigurable region partitioning and task scheduling.A new method is proposed for skip infeasible solutions and poor solutions effectively which accelerates the search of solution space and increases the convergence speed of the SA algorithm.Experimental results show that, compared with mixed integer linear programming (MILP) and IS-k, the proposed algorithm based on SA has lower time complexity, and for the large-scale applications, it can solve better partition and scheduling results in a short time.
      Parallelizing Multigrid Application Using Data-driven Programming Model
      GUO Jie, GAO Xi-ran, CHEN Li, FU You, LIU Ying
      Computer Science. 2020, 47 (8): 32-40.  doi:10.11896/jsjkx.200500093
      Abstract ( 2 )   PDF(3157KB) ( 1 )   
      References | Related Articles | Metrics
      Multigrid is an important family of algorithms to accelerate the convergence of iterative solvers for linear systems, and it plays an important role in large-scale scientific computing.At present, distributed-memory systems have evolved to large scale systems based on multi-core nodes or heterogeneous nodes with accelerators.Legacy applications face the urgent need to be ported to modern supercomputers with diverse node-level architectures.In this paper, a data-driven programming language, AceMesh is introduced, and using this directive language, NAS MG is ported to two home-made supercomputers which are Tianhe-2 and Sunway TaihuLight supercomputer.This paper shows how to taskify computation loops and communication-related codes in AceMesh, and analyzes the characteristics on its task graph and on its computation-communication overlapping.Experimental results show that compared with traditional programming models, the AceMesh versions achieve relative speedup up to 1.19X and 1.85X on Sunway TaihuLight and Tianhe-2 respectively.Analyses show that performance improvements come from two main reasons, memory-related optimization and communication overlapping optimization.At last, future directions are put forward to further optimize inter-process communications for the AceMesh version.
      Computing Resources Allocation with Load Balance in Modern Processor
      WANG Guo-peng, YANG Jian-xin, YIN Fei, JIANG Sheng-jian
      Computer Science. 2020, 47 (8): 41-48.  doi:10.11896/jsjkx.191000148
      Abstract ( 2 )   PDF(1828KB) ( 2 )   
      References | Related Articles | Metrics
      To improve the efficiency of program, it is used to arrange multiple function units in modern superscalar processor, supporting to execute instructions in parallel.The allocation policy of computing resources plays an important role in taking full advantage of multiple function units.Although the policy of how to allocate computing resources and schedule instruction has been well studied in literature, the proposed solutions almost concentrate on optimization methods at compile time, which is mostlystatic, inflexible and inefficient because of lack of computing pipeline information at run time.To mitigate the negative impacts of improper computing resource allocation and maximize the power of multiple function units, this paper abstracts the mathematical model of resource allocation problem at run time and makes a study of hardware fine-grained automatic method based on symmetric and asymmetric configuration of function units, in order to make dynamic and wise computing resource allocating decision when instructions are issued in general situation.As a result, a load-balanced greedy resource allocation strategy is proposed and evaluated.The experimental results show that our policy is efficient to minimize blocking time caused by unfair allocation of computing resources.Furthermore, the more computing resources are provided, the better performance our policy can yield.
      Parallel Algorithm of Deep Transductive Non-negative Matrix Factorization for Speech Separation
      LI Yu-rong, LIU Jie, LIU Ya-lin, GONG Chun-ye, WANG Yong
      Computer Science. 2020, 47 (8): 49-55.  doi:10.11896/jsjkx.190900202
      Abstract ( 2 )   PDF(2394KB) ( 5 )   
      References | Related Articles | Metrics
      Non-negative matrix factorization can preserve the non-negative features of the speech signal.It is an important method for speech separation.However, this method has the problems of complicated data operation and computation, it is necessary to propose a parallel method to reduce computation time.Aiming at the calculation problem of speech separation pre-training and separation process, this paper proposes a deep transductive non-negative matrix factorization multi-level parallel algorithm, which considers the data correlation of the iterative update process, and designs a multi-level parallel algorithm between tasks and within tasks.The parallel algorithm at the task level decomposes the training speech to obtain the corresponding base matrix as two independent tasks in parallel calculation.The matrix is divided into rows and columns at the internal process level of the task.The master process distributes the matrix blocks to the slave process, and the slave process receives the current sub-matrix, then the matrix block calculates the result matrix sub-block, and then sends the current process matrix block to the next process to achieve the traversal of each matrix block of the second matrix in all processes, calculating the product of the corresponding sub-block of the result matrix, and finally the sub-block is collected by the main process from the slave process.During the thread-level sub-matrix multiplication operation, an acceleration strategy of generating multiple threads and exchanging data through shared me-mory for sub-matrix block calculation is adopted.This algorithm is the first one to implement deep transduction non-negative matrix factorization algorithm.The experimentis performed on the Tianhe II platform.The test results show that when separating multi-speaker mixed speech signals without changing the separation effect, in the pre-training process, the proposed parallel algorithm performs well using 64 processes at a speed ratio of 18, and in the separation process, the corresponding speedup is 24.Compared to serial and MPI model separation, hybrid model separation time is greatly shortened, which proves that for the speech separation process, the parallel algorithm proposed in this paper can effectively improve the separation efficiency.
      Design and Optimization of Two-level Particle-mesh Algorithm Based on Fixed-point Compression
      CHENG Sheng-gan, YU Hao-ran, WEI Jian-wen, James LIN
      Computer Science. 2020, 47 (8): 56-61.  doi:10.11896/jsjkx.200200112
      Abstract ( 1 )   PDF(1841KB) ( 1 )   
      References | Related Articles | Metrics
      Large-scale N-body simulation is of great significance for the study of modern physical cosmology.One of the most popular N-body simulation algorithms is particle-mesh(PM).However, the PM-based algorithms cost considerable amounts of memory, which becomes the bottleneck to scale the N-body simulations in the modern supercomputer.Therefore, this paper pro-poses to use fixed-point compression to reduce memory footprints per N-body particle to only 6 bytes, nearly an order of magnitude lower than the traditional PM-based algorithms.This paper implements the two-level particle-mesh algorithm with fixed-point compression and optimizes it with mixed-precision computation and communication optimizations.These optimizations significantly reduce the performance loss caused by fixed-point compression.The proportion of compression and decompression in the total time of the program reduces from 21% to 8% and achieves up to 2.3 times speedup on computing hotspots which make the algorithm maintain high efficiency and scalability with low memory consumption.
      Prediction of Loop Tiling Size Based on Neural Network
      CHI Hao-yu, CHEN Chang-bo
      Computer Science. 2020, 47 (8): 62-70.  doi:10.11896/jsjkx.191200180
      Abstract ( 1 )   PDF(2981KB) ( 2 )   
      References | Related Articles | Metrics
      Optimization of loop programs is an important topic in program optimization.As a typical technique of loop optimization, loop tiling has been widely studied and applied.The selection of tile size, which is complex and highly dependent on program and hardware, has a great impact on the performance of loops.Traditional approaches based on static analysis and heuristic experience search have high cost of labor and time, and lack generality and portability.Therefore, the neural network method, which is good at representing high-dimensional information, is considered to learn the hidden correlation between tiling size and program performance, which is a result of complex interaction between program and hardware.A new group of features with 29 dimensions are extracted based on size of the problem, structure of the loop, locality of the operations within the loop.The experiments are carried out on hundreds of thousands of lines of six kinds of kernel programs (3D loop, 2D data) with random sizes in the range of 1024 to 2048.The sequential model (TSS-T6) achieves an average speedup of 6.64 compared with GCC-O2, 98.5% of the average maximum available performancecompared with the exhaustive search, and an average 9.9% performance improvement compared with Pluto.The parallel model (TSSP-T6-Search) achieves an average speedup of 2.41 compared with the OpenMP default optimization, 91.7% of the average maximum available performance compared with the exhaustive search, and an average 9% performance improvement compared with Pluto default parallel tiling optimization.
      Algorithm Design of Variable Precision Transcendental Functions
      HAO Jiang-wei, GUO Shao-zhong, XIA Yuan-yuan, XU Jin-chen
      Computer Science. 2020, 47 (8): 71-79.  doi:10.11896/jsjkx.200200013
      Abstract ( 2 )   PDF(3052KB) ( 1 )   
      References | Related Articles | Metrics
      Transcendental functions are the main part of fundamental mathematical software library.Their accuracy and perfor-mance greatly determine those of the upper-layer applications.Aiming at the problems of tedious and error-prone implementation of transcendental functions as well as accuracy requirements of different applications, a variable precision transcendental function algorithm is proposed, which considers both generality and mathematical characteristics of functions.Based on the similarity of transcendental functions, a transformation-reduction-approximation-reconstruction algorithm template is constructed to unify common transcendental function algorithm implementations, and the algorithm template parameters are adjusted to handle errors to generate different precision versions of function codes.Experiment results show that the algorithm is able to generate function codes of different precision versions of common transcendental functions and has performance advantages over the corresponding functions in the standard mathematical software library.
      Cuckoo Hash Table Based on Smart Placement Strategy
      JIN Qi, WANG Jun-chang, FU Xiong
      Computer Science. 2020, 47 (8): 80-86.  doi:10.11896/jsjkx.191200109
      Abstract ( 0 )   PDF(2074KB) ( 0 )   
      References | Related Articles | Metrics
      Because time overhead of query is O (1), Cuckoo hash table has been widely used in big data, cloud computing and other fields.However, insertion of the existing Cuckoo hash tables generally uses random replacement strategy to replace existing entries when encountering conflicts.On the one hand, writers are prone to high-latency insertion and infinite loops, especially when the load rate of hash table is relatively high, and even have the risk of reconstructing entire hash table;on the other hand, due to existing random replacement strategies, entries are scattered as much as possible in the buckets of hash table.The lack of good spatial locality among entries reduces the efficiency of positive query.To solve the above problems, this paper proposes a Cuckoo hash table based on smart placement strategy.Specifically, in order to improve efficiency of insertion, a load-balance Cuc-koo hash table (LBCHT) is proposed, which limits the load of each bucket in real time, using breadth-first search to find the best Cuckoo path to ensures load balancing among buckets.Experimental results show that LBCHT can effectively reduce long tail effect of insertion under high load rate.And in order to improve efficiency of lookup, a Cuckoo hash table that makes full use of the locality principle is proposed (LPCHT).By fully exploring the spatial Locality among entries, CPU cache miss rate caused by lookup is reduced and efficiency of positive query is improved.Experiments show that in a high load rate stress test environment, compared with libcuckoo, LBCHT throughput of insertion can be increased by 50%, and LPCHT improves positive query efficiency by 7%.
      Large Scalability Method of 2D Computation on Shenwei Many-core
      ZHUANG Yuan, GUO Qiang, ZHANG Jie, ZENG Yun-hui
      Computer Science. 2020, 47 (8): 87-92.  doi:10.11896/jsjkx.191000011
      Abstract ( 0 )   PDF(1963KB) ( 1 )   
      References | Related Articles | Metrics
      With the development of supercomputer and its programming environment, multilevel parallelism under heterogeneous system infrastructure is a promising trend.Applications ported to Sunway TaihuLight are typical.Since the Sunway TaihuLight was open to public in 2016, many scholars focus on the method study and application verification, so much experience on Shenwei many-core programming method is accumulated.However, when the CESM model is ported to Shenwei many-core infrastructure, some two dimensional computations in the ported POP model show quite good results under 1024 processes.On the contrary, they perform much worse than the original version, and false acceleration ratios appeared under 16800 processes.Upon this problem, a new parallel method based on slave-core partitions was proposed.Under the new parallel method, the 64 slave-cores in a core-group are divided into some disjoint small partitions, which make that different and independent computing kernels can run at different slave-core partitions simultaneously.In the method, the computing kernels can be loaded to different slave-core partitions with the suitable data size and computational load, where the amount and number of the slave-cores in each partition can be pro-perly set according to the computing scale, so the slave-core’s calculation ability can be fully utilized.Based on the new parallel method, also with the loops combination and function expansion, the slave-cores are fully applied and some computing time among several parallel running codes is hidden.Furthermore, it is effective to extend the parallel granularity of the kernels to be athrea-ded.Applied the above methods, the simulation speed of POP model in high-resolution CESM G-compset is improved by 0.8 si-mulation year per day under 1.1 million cores.
      Large-scale Quantum Fourier Transform Simulation Based on SW26010
      LIU Xiao-nan, JING Li-na, WANG Li-xin, WANG Mei-ling
      Computer Science. 2020, 47 (8): 93-97.  doi:10.11896/jsjkx.200300015
      Abstract ( 0 )   PDF(2381KB) ( 1 )   
      References | Related Articles | Metrics
      Quantum computing has a natural parallel advantage due to its entanglement and superposition.However, current quantum computing equipment is limited to the technological level of physical realization.It takes a certain amount of time to accumulate and break through to achieve huge computing power and solve practical problems with practical significance.Therefore, using classical computers to simulate quantum computing has become an effective way to verify quantum algorithms.Quantum Fourier Transform is a key part of many quantum algorithms.It involves phase estimation, order finding, factors, etc.Research on Quantum Fourier Transform and large-scale simulation implementation can effectively promote the research, verification and optimization of related quantum algorithms.In this paper, a large-scale Quantum Fourier Transform is simulated using the supercomputer, “Sunway TaihuLight”, independently developed by our country.According to the heterogeneous parallel characteristics of SW26010 processor, MPI, accelerated thread library, and communication and computing hiding technology are adopted to optimize the system.The correctness of the Quantum Fourier Transform simulation is verified by seeking the period in the Shor algorithm, and the simulation and optimization of the Quantum Fourier Transform of 46-Qubits are realized, which provides reference for the verification and optimization of other quantum algorithms on the supercomputing platform and the proposal of new quantum algorithms.
      Optimization of BFS on Domestic Heterogeneous Many-core Processor SW26010
      YUAN Xin-hui, LIN Rong-fen, WEI Di, YIN Wan-wang, XU Jin-xiu
      Computer Science. 2020, 47 (8): 98-104.  doi:10.11896/jsjkx.191000013
      Abstract ( 0 )   PDF(3058KB) ( 2 )   
      References | Related Articles | Metrics
      In recent years, there is growing concern for the processing capabilities of data-intensive task.Breadth-first search(BFS) is a typical data-intensive problem, which is widely used in a variety of graph algorithms.Graph 500 Benchmark, taking BFS algorithm as the core, has become the benchmark for the evaluation of processing capabilities of data-intensive tasks.Sunway TaihuLight supercomputer topped the Top 500 list for four consecutive times from June 2016 to November 2017, the processor of which, named SW26010, is the first Chinese homegrown heterogeneous many-core processor.This paper studies how to use the architecture characteristics of SW26010 to accelerate BFS algorithm.A direction-optimizing hybrid BFS algorithm based on a single core group(CG) is implemented on SW26010, using bytemap to release the data dependencies in inner loops, hiding overhead of calculation and SPM access by using asynchronous DMA, taking advantage of heterogeneous architecture to compute collaboratively and carrying out graph preprocessing.Eventually, with Graph 500 as the benchmark processing a scale 22 graph, a single CG of SW26010 processor achieves a performance of 457.54MTEPS.
      Real-time SIFT Algorithm Based on GPU
      WANG Liang, ZHOU Xin-zhi, YNA Hua
      Computer Science. 2020, 47 (8): 105-111.  doi:10.11896/jsjkx.190700036
      Abstract ( 1 )   PDF(4602KB) ( 3 )   
      References | Related Articles | Metrics
      Aiming at the complex and low real-time defects of the SIFT feature extraction algorithm, a real-time SIFT algorithm based on GPU is proposed, called CoSift (CUDA Optimized SIFT).Firstly, the algorithm uses the CUDA stream concurrency mechanism to construct the SIFT scale space.In this process, the high-speed memory in the CUDA memory model is fully utilized to improve data access speed, and the two-dimensional Gaussian convolution kernel is optimized to reduce the amount of computation.Then, the warp-based histogram policy is designed to rebalance the workload during the characterization process.Compared with the traditional algorithm of the CPU version and the improved algorithm of the GPU version, the proposed algorithm greatly improves the real-time performance of the SIFT algorithm without reducing the accuracy of feature extraction, and has a relatively higher optimization effect on large-size images.CoSift can extract features within 7.7~8.8ms (116.28~129.87fps) on the GTX1080Ti.The algorithm effectively reduces the complexity of the traditional SIFT algorithm process, improves the real-time performance, and is convenient to be applied in scenarios where the real-time requirement of SIFT algorithm is higher.
      Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems
      ZHANG Long-xin, ZHOU Li-qian, WEN Hong, XIAO Man-sheng, DENG Xiao-jun
      Computer Science. 2020, 47 (8): 112-118.  doi:10.11896/jsjkx.200300038
      Abstract ( 0 )   PDF(1843KB) ( 1 )   
      References | Related Articles | Metrics
      Cloud computing has become a very important computing service mode in various industries.Traditional studies on cloud computing mainly focus on the research of service quality such as the pricing mode, profit maximization and execution efficiency of cloud services.Green computing is the development trend of distributed computing.Aiming at the scheduling problem of workflow task set that meets the computing cost constraint of cloud users in heterogeneous cloud environment, an energy-aware based on budget level scheduling algorithm(EABL) with low time complexity is proposed.The EABL algorithm consists of three main stages:task priority establishment, task budget cost allocation, optimal execution virtual machine and energy efficiency frequency selection of the parallel task set, so as to minimize the energy consumption during task set execution under the constraint of budget cost.A large-scale workflow task sets in the real world are used to conduct a large number of tests on the algorithm for the experiment in this paper.Compared with famous algorithms EA_HBCS and MECABP, EABL algorithm can effectively reduce the energy consumption in the computing process of cloud data centers by making full use of the budget cost.
      ENLHS:Sampling Approach to Auto Tuning Kafka Configurations
      XIE Wen-kang, FAN Wei-bei, ZHANG Yu-jie, XU He, LI Peng
      Computer Science. 2020, 47 (8): 119-126.  doi:10.11896/jsjkx.200300010
      Abstract ( 0 )   PDF(2357KB) ( 1 )   
      References | Related Articles | Metrics
      When Kafka is applied in a production environment, its performance is not only limited by the machine’s hardware environment and system platform.Its own configuration items are the key element to judge whether it can achieve the desired performance under the condition of limited hardware resources, but it is manually configured.The efficiency of item modification and tuning is extremely poor.If the actual resource environment is not optimized, Kafka cannot guarantee its performance in each production environment using default configuration parameters.Because Kafka’s configuration bound is extremely large, the perfor-mance of traditional adaptive algorithms in large-scale production systems is poor.Therefore, in order to improve Kafka’s adaptive ability, eliminate complexity in the system, and obtain better operating performance, an adaptive performance tuning method for Kafka is proposed, which fully considers the influence weights of Kafka’s characteristic parameters and performance.It uses the principle of sampling to improve the efficiency of data sets generation and optimize the range of data selection, improve the efficiency of modeling and reduce the complexity of optimization methods.Experiments show that the algorithm optimizes the throughput rate and latency of the open source version Kafka, improves Kafka’s throughputs under a given system resource, and reduces latency.
      High-performance FPGA Implementation of Elliptic Curve ECC on Binary Domain
      YOU Wen-zhu, GE Hai-bo
      Computer Science. 2020, 47 (8): 127-131.  doi:10.11896/jsjkx.200600112
      Abstract ( 1 )   PDF(2308KB) ( 3 )   
      References | Related Articles | Metrics
      In recent years, the communications field has achieved tremendous development.Applications such as online banking and mobile communications have increased the security requirements in resource-constrained environments.Compared with traditional cryptographic algorithms, elliptic curve cryptosystem(ECC) provides better security standards and more space for optimizing performance parameters.Therefore, an efficient elliptic curve cipher hardware design scheme is proposed.Based on the exis-ting research, the proposed scheme uses the projected coordinate system LD Montgomery ladder algorithm to study the core scalar multiplication operation in ECC, and uses parallel scheduling to reduce delay in the group operation layer.For finite field ope-rations, the bit-parallel multiplication algorithm and improved Euclidean inverse algorithm are adopted.Based on Xilinx Virtex-5 and Virtex-7 FPGA device, the architecture is implemented on the binary domains with lengths of 163, 233 and 283 respectively.The experimental results show that the proposed scheme requires less FPGA resource consumption and faster calculation speed.Compared with other methods, the hardware resource consumption is reduced by 52.9% and the scalar multiplication operation speed is increased by 3.7times, so it is better suitable for the application of resource-constrained devices.
      Label Distribution Learning Based on Natural Neighbors
      YAO Cheng-liang, ZHU Qing-sheng
      Computer Science. 2020, 47 (8): 132-136.  doi:10.11896/jsjkx.190700012
      Abstract ( 0 )   PDF(2100KB) ( 1 )   
      References | Related Articles | Metrics
      Label distribution is a new machine learning paradigm which can solve some markup ambiguity problems well.Label distribution can be seen as the generalization of multi-label.Traditional single-label learning and multi-label learning can be seen as special cases of label distribution learning.AA-KNN based on algorithm adaptive is an effective algorithm, but it is diffcult to choose an appropriate parameter K which affects the perfomence when KNN is used.So, Natural neighbors is introduced into LDL and a new label distribution learning algorithm is proposed.It finds natural neighbors of each object by searching algorithm, and then gets the average of labels of these neighbours as the predicted result.The natural neighbours searching algorithm does not need any parameter and is passive so that neighbors of each object is decided automatically.Experiments was conducted on 6 data sets and 6 evaluation indexes.The experiments show that the proposed algorithm not only solves the problem of choosing parameter K, but also improves the performance compared with AA-KNN.
      Incremental Attribute Reduction Algorithm in Dominance-based Rough Set
      SANG Bin-bin, YANG Liu-zhong, CHEN Hong-mei, WANG Sheng-wu
      Computer Science. 2020, 47 (8): 137-143.  doi:10.11896/jsjkx.190700188
      Abstract ( 0 )   PDF(2637KB) ( null )   
      References | Related Articles | Metrics
      In real life, as the data increase continuously, the relation between the original criteria and the decision making changes dynamically.How to effectively calculate the attribute reduction becomes an urgent problem to be solved in the dynamic decision making.Incremental updating method can effectively complete the dynamic learning task, because it can acquire new knowledge based on previous knowledge.This paper exploited the dominance-based rough set approach to study the incremental attribute reduction method when adding a single object to the data with dominant relation.Firstly, the dominant set matrix is defined as the target of the update to calculate the new dominant conditional entropy.Then, an incremental learning mechanism of the dominant conditional entropy is proposed by analyzing the three different situations of the adding object.After that, an incremental attribute reduction algorithm is designed based on the dominant set matrix.Finally, experiments on six different UCI data set are conducted to compare the effectiveness and efficiency of the incremental and non-incremental algorithms.The experimental results show that the incremental attribute reduction algorithm proposed in this paper is not only consistent with the non-incremental attribute reduction algorithm in term of effectiveness, but also far superior to the non-incremental attribute reduction algorithm in term of efficiency.Therefore, the proposed incremental algorithm can effectively and efficiently accomplish the task of attribute reduction in dynamical data with dominant relation.
      Three-way Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications
      CHEN Yu-jin, XU Ji-hui, SHI Jia-hui, LIU Yu
      Computer Science. 2020, 47 (8): 144-150.  doi:10.11896/jsjkx.190800041
      Abstract ( 0 )   PDF(1504KB) ( 1 )   
      References | Related Articles | Metrics
      Due to the ability limitations of decision makers and the uncertainty of the objects being evaluated, the three-way decision models have insufficient expressive power in dealing with hesitant and fuzzy decision problems caused by fuzzy information and subjective cognitive concepts.In order to solve the above shortcomings, the intuitionistic fuzzy set is introduced to establish the corresponding three-way decision models.Firstly, considering that intuitionistic hesitant fuzzy set contains the characteristics of multiple membership degrees, the three-way decision method based on single intuitionistic fuzzy number is established in the case of determining the risk cost matrix.On this basis, three-way decision models based on intuitionistic hesitation fuzzy sets are established by using intuitionistic hesitation fuzzy sets as the domain.Then, taking into account the semantic interpretation of particular environment, decision-making rules based on optimism, pessimism, and minority obedience are formed.Finally, combining with the safety risk assessment methods in the aviation field, three-way decision methods of aviation safety risk based on double evaluation function are presented, and the concrete application process of the model is illustrated by an example.
      Deep Domain Adaptation Algorithm Based on PE Divergence Instance Filtering
      YUAN Chen-hui, CHENG Chun-ling
      Computer Science. 2020, 47 (8): 151-156.  doi:10.11896/jsjkx.190600175
      Abstract ( 1 )   PDF(1555KB) ( 2 )   
      References | Related Articles | Metrics
      Deep domain adaptation, one of the most common problems in transfer learning, has achieved excellent performance in many machine learning applications.However, the existing deep domain adaptation just adapts the fully connected layer while reduce domain shift, which ignores the spatial information and semantic context information of the convolutional layer, resulting in the loss of important information during the process of knowledge transfer.To this end, this paper combines instance-based domain adaptation with feature-based domain adaptation and proposes a deep domain adaptation algorithm based on PE divergence instance filtering (DAPEIF).Firstly, the relative importance weight of the source samples is calculated by PE divergence, and the source samples that are likely to cause negative transfer are deleted.Then the maximum mean discrepancy metric is included as a regularization term in the training of the neural network based on AlexNet, and the marginal probability distribution of the convolutional layer and the fully connected layer are jointly adapted to reduce the difference between the new source domain and the target domain.At the same time, the weight regularization term is introduced, and the network parameters are learned by the gradient descent to further improve the generalization performance of the model in the process of domain adaptation.The proposed algorithm can simultaneously assign domain adaptative ability to the parameters of the convolutional layer and the fully connected layer of the neural network.The experimental results on the public dataset Office-Caltech in domain adaptation demonstrate that compared with the state of the art domain adaptation algorithms, the proposed algorithm has better performance in accuracy and the average accuracy reaches 84.46%.
      Algorithm for Detecting Overlapping Communities Based on Centered Cliques
      XUE Lei, TANG Xu-qing
      Computer Science. 2020, 47 (8): 157-163.  doi:10.11896/jsjkx.200300034
      Abstract ( 1 )   PDF(1985KB) ( 4 )   
      References | Related Articles | Metrics
      Community detection in complex network has become a vital way to understand its structure and dynamic characteristics.However, there are two inherent shortcomings that the parameter dependency and instability of using the traditional node clustering and link clustering to detect overlapping communities.This paper proposes an improving algorithm, that is, the local expansion method based on the centered clique(CLEM), for detecting overlapping communities.Firstly, in CLEM algorithm, the centered cliques is selected as the core seed and the nodes deleted by multiple times in the process of seed expansion are punished, so its stability of results is improved.Then, by selecting the fitness function with parameter-independent and improving its iterative calculation process, the parameter limitation of the fitness function is avoided and the computational complexity is quickly reduced.Finally, the test results on synthetic networks and real-world networks show that CLEM is good both in computing time and accuracy compared with some existing algorithms.
      Opinion Word-pairs Collaborative Extraction Based on Dependency Relation Analysis
      ZHAO Wei, LIN Yu-ming, WANG Chao-qiang, CAI Guo-yong
      Computer Science. 2020, 47 (8): 164-170.  doi:10.11896/jsjkx.190600153
      Abstract ( 2 )   PDF(1695KB) ( 5 )   
      References | Related Articles | Metrics
      In the same category of commodities, opinion word-pairs usually have strong opinion dependence relation to the opinion targets and the opinion words contained in them.Therefore, in the extraction process of opinion word-pairs, they can be extracted by analyzing the opinion dependence relations among the words in the review sentences.Firstly, a dependency relation analysis model is constructed to obtain the dependency relation information of each word in a review sentence, and the basic model is defined as LSTM neural network.Secondly, it is assumed that one of the item that opinion word-pairs contained in review sentence is known, and the known item is used as the model’s attention information, so that the model can focus on extracting the words of phrases associated with the known item with strong opinion dependence from the review sentence as another unknown item in the opinion word-pairs.Finally, the word-pairs with the highest score of the opinion dependence relation are output as the opinion word-pairs.Then a compound model is designed to realize the mining of opinion word pairs without knowing the known items in advance by combining the two models which contain the information of different known items in the opinion word-pairs.
      Incremental Classification Model Based on Q-learning Algorithm
      LIU Ling-yun, QIAN Hui, XING Hong-jie, DONG Chun-ru, ZHANG Feng
      Computer Science. 2020, 47 (8): 171-177.  doi:10.11896/jsjkx.190600150
      Abstract ( 1 )   PDF(1369KB) ( 1 )   
      References | Related Articles | Metrics
      The traditional classification models are insufficient to take full advantage of the sequential data with their continuous and explosive growth due to the imprecision of the data.Therefore, the incremental learning is provided to handle this problem.However, the difference sequence of the training samples may have strong impact on performance of a classifier.Especially when the classifier is undertrained, traditional incremental learning method takes the risk of utilizing the noise samples with wrong labels to train the classifier.To overcome this problem, this paper proposes an incremental classification model based on Q-learning algorithm.The model employs the classical Q-learning algorithm in reinforcement learning to select the sequence samples incrementally, which is capable of softening the negative impact of the noise data and labels samples automatically as well.To overcome the problem of computational complexity along with the increasing of state space and action space of Q-learning, an improved batch incremental classification model based on Q-learning algorithm is proposed.Compared with the traditionally trained classifiers, the proposed model combines the ideas of online incremental learning and reinforcement learning, which is able to achieve high accuracy and can be updated online.Finally, the validity of the model is verified on three UCI datasets.The experimental results show that choosing training sets incrementally is helpful to improve the performance of the classifier and the precision of the classifier trained by different incremental training sequences varies greatly as well.The proposed incremental classification model based on Q-learning algorithm can make use of the limited available dataset for supervised initial training, and then construct new-added self-supervised training set based on the Q value of each unlabeled sample to improve the accuracy of the classifier.Therefore, the incremental classification model based on Q-learning algorithm can be used to solve the problem of lack of supervisory information, and has a potential application.
      K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection
      DONG Ming-gang, HUANG Yu-yang, JING Chao
      Computer Science. 2020, 47 (8): 178-184.  doi:10.11896/jsjkx.190700089
      Abstract ( 0 )   PDF(2327KB) ( null )   
      References | Related Articles | Metrics
      The classification performance of K-Nearest Neighbor depends on the quality of training set.It is significant to design an efficient training set optimization algorithm.Two major drawbacks of traditional evolutionary training set optimization algorithm are low efficiency and removing the non-noise samples and features by mistake.To address these issues, this paper proposes a genetic training set optimization algorithm.The algorithm uses the efficient genetic algorithm based on the maximum Hamming distance.Each cross preserves the parent and generates two new children with the largest Hamming distance, which not only improves the efficiency but also ensures the population diversity.In the proposed algorithm, the local noise sample deletion strategy is combined with the feature selection strategy.Firstly, the decision tree is used to determine the range of noise samples.Then the genetic algorithm is used to remove the noise samples in this range and select the features simultaneously.It reduces the risk of mistaken and improves the efficiency.At last, the 1NN-based selection strategy of validation set is used to improve the instance and feature selection accuracy of the genetic algorithm.Compared with co-evolutionary instance feature selection algorithm ( IFS-CoCo), weighted co-evolutionary instance feature selection algorithm (CIW-NN), evolutionary feature selection algorithm (EIS-RFS, evolutionary instance selection algorithm (PS-NN) and traditional KNN, the average improvement of the proposed algorithm in classification accuracy is 2.18% , 2.06%, 5.61%, 4.06%, 4.00%, respectively.The experiments results suggest that the proposed method has higher classification accuracy and optimization efficiency.
      FS-CRF:Outlier Detection Model Based on Feature Segmentation and Cascaded Random Forest
      LIU Zhen-peng, SU Nan, QIN Yi-wen, LU Jia-huan, LI Xiao-fei
      Computer Science. 2020, 47 (8): 185-188.  doi:10.11896/jsjkx.190600162
      Abstract ( 0 )   PDF(1697KB) ( 1 )   
      References | Related Articles | Metrics
      In the era of big data, there are many abnormal values hidden in massive data due to attack tampering, equipment fai-lure, artificial fraud and other reasons.Accurately detect outliers in data is critical to data cleaning.Therefore, an outlier detection model combining feature segmentation and multi-level cascaded random forest (FS-CRF) is proposed.Using the sliding window and the random forest to segment the original features, the generated class probability vector is used to train the multi-level cascaded random forest.Finally, the category of the sample is determined by the vote of the last layer.Simulation experiment results show that the new method can effectively detect outlier in classification tasks on UCI data sets, with high F1-measure scores obtained on both high and low dimensional data sets.The cascade structure further improves the generalization ability of the model compared to the classical random forest.Compared with the GBDT and XGBoost, the proposed method has performance advantages on high-dimensional data sets, and has fewer hyper-parameters that easy to tune and has better comprehensive performance.
      Analysis of China’s Patent Application Concern Based on Visibility Graph Network
      ZHANG Meng-yue, HU Jun, YAN Guan, LI Hui-jia
      Computer Science. 2020, 47 (8): 189-194.  doi:10.11896/jsjkx.200300001
      Abstract ( 0 )   PDF(2149KB) ( 2 )   
      References | Related Articles | Metrics
      Patent is an important embodiment of innovation.Many people will inquire about the process of patent application on the Internet and learn the application steps before patent application.In fact, the online searching is also a way to know whether innovative enterprises or individuals attach importance to innovation.This paper analyzes the dynamic characteristics of Baidu search index time series with the keywords of “patent application” from the perspective of a new time series analysis, namely from the perspective of network.The time series of Baidu search index is transformed into a complex network by using the principle of visibility graph algorithm, and its parameters are calculated to analyze the topological structure of the network.Firstly, by calculating the complex network, it can be found that the patent attention of each province has certain differences.Secondly, the study shows that most of the networks are scale-free networks and the original time series have fractal characteristics.Finally, by clustering, 31 provinces can be divided into 3 categories according to the characteristics of complex networks.This paper analyzes the data of Baidu search index from 2011 to 2018.By dividing the community structure, the time series period and the central node’s influence on the search index can be found.
      Video Saliency Detection Based on 3D Full ConvLSTM Neural Network
      WANG Jiao-jin, JIAN Mu-wei, LIU Xiang-yu, LIN Pei-guang, GEN Lei-lei, CUI Chao-ran, YIN Yi-long
      Computer Science. 2020, 47 (8): 195-201.  doi:10.11896/jsjkx.190600148
      Abstract ( 1 )   PDF(3008KB) ( null )   
      References | Related Articles | Metrics
      Video saliency detection aims to mimic human’s visual attention mechanism of perceiving the world via extracting the most attractive regions or objects in the input video.At present, it is still a challenge for video saliency detection.Traditional video saliency-detection models have reached a certain level, but exploiting the consistency of spatio-temporal information is unsatisfactory.In order to solve this issue, this paper proposes a video saliency-detection model based on 3D full ConvLSTM neural network.Firstly, the full-time convolution is utilized to extract spatio-temporal features from the input video, and then the 3D pooling layer is explored for dimensionality reduction.Secondly, the extracted features are decoded by 3D deconvolution in the decoding layer, and the interpolation algorithm is applied to restore the saliency map to the original size of the original image.The proposed method extracts the time and space information jointly so as to effectively enhance the completeness of the saliency map.Experimental results show that the performance of the proposed algorithm is superior to state-of-the-art video saliency detection methods based on three widely used data sets (DAVIS, FBMS, SegTrack) for video saliency detection.
      Dense Convolution Generative Adversarial Networks Based Image Inpainting
      MENG Li-sha, REN Kun, FAN Chun-qi, HUANG Long
      Computer Science. 2020, 47 (8): 202-207.  doi:10.11896/jsjkx.190700017
      Abstract ( 0 )   PDF(3379KB) ( 1 )   
      References | Related Articles | Metrics
      Image inpainting is one technique of reconstruction defect areas by inferring information from the known context of defect images.For semantic image inpainting of large areas, there are still many problems in inpainting algorithms based on generation models, such as blur, artifacts, and poor visual similarity, especially for the complex background images and small datasets.To solve this problem, an image inpainting algorithm based on dense convolution generative adversarial networks is proposed.The generated adversarial network is the basic framework.Firstly, dense convolutional blocks are used to enhance image feature extraction, improve image repair capability, and avoid the problem of gradient disappearance caused by the network depth increa-sing in the generator network.Secondly, skip connection between the encoding and decoding structures is involved to avoid information transmission lost problems between network layers.After that, a total loss function, composed of the reconstruction loss, adversarial loss and TV loss, is used to optimize the network and enhance network stability.Finally, the proposed algorithm is validated on the CelebA dataset and Car dataset respectively, compared with three typical image inpainting algorithms.The effectiveness of the algorithm is proved in visual perception, peak signal-to-noise ratio (PSNR) and structural similarity (SSIM).
      Highway Abnormal Event Detection Algorithm Based on Video Analysis
      YAO Lan, ZHAO Yong-heng, SHI Yu-qing, YU Ming-he
      Computer Science. 2020, 47 (8): 208-212.  doi:10.11896/jsjkx.191000165
      Abstract ( 1 )   PDF(1787KB) ( 1 )   
      References | Related Articles | Metrics
      Abnormal event detection in a traffic scenario is significant for accident prevention, on-call solution and other applications.While currently, the detection approaches are neither labor efficient, nor real-timing.A multi-target tracking algorithm combining motion characteristics and apparent characteristic for vehicle trace in highway traffic scenario is derived by introducing target detection in deep learning and extracting targets in a video.An abnormal event detection method which is based on vehicle trajectory feature is proposed.The proposed tracking algorithm declines the dependent on background during the procedure of trajectory extraction.The abnormal event detection algorithm is designated adequately for highway scenario with an additional strategy of sliding window to improve the performance on abnormal detection for remote and complex scenes.Through the experiments on practical video repository, the proposed method is compared with existing methods and shows a highlighted performance in the terms of Precision, Recall rate and F-value index.This method turns out to be solid and efficient in abnormal event detection in highway traffic scenario.
      GNNI U-net:Precise Segmentation Neural Network of Left Ventricular Contours for MRI Images Based on Group Normalization and Nearest Interpolation
      GAO Qiang, GAO Jing-yang, ZHAO Di
      Computer Science. 2020, 47 (8): 213-220.  doi:10.11896/jsjkx.190600026
      Abstract ( 0 )   PDF(3633KB) ( 2 )   
      References | Related Articles | Metrics
      Cardiovascular disease has become the No.1 killer of human health.At present, doctors manually label the left ventricle contour by left ventricular MRI imaging technology to calculate various functional parameters of the heart to prevent cardiovascular disease, which is not difficult but time consuming and cumbersome.Deep learning has achieved remarkable success in many areas of medical image segmentation, but there is still room for improvement in the field of left ventricular contour segmentation.We proposes a convolutional neural network based on group normalization and nearest interpolation up-sampling which is called GNNI U-net (U-net with Group normalization and Nearest interpolation) for MRI left ventricular contour precise segmentation.We constructe a convolution module with group normalization operation based on group normalization method for fast and accurately feature extraction.Based on nearest neighbor interpolation method, we constructe an up-sampling module for feature restoring.We conducte a pre-processing method for Center cropping ROI extraction and a detailed controlled experiment of GNNI U-net on the Sunnybrook left ventricular segmentation dataset and the LVSC left ventricular segmentation dataset.The experimental results show that the GNNI U-net obtains the accuracy of Dice coefficient of 0.937 and the accuracy of Jaccard coefficient of 0.893 on the Sunnybrook dataset, and it obtains the accuracy of the Dice coefficient of 0.957 and the accuracy of the Jaccard coefficient of 0.921 on the LVSC dataset.The GNNI U-net network achieves higher Dice coefficient accuracy than other convolutional network segmentation methods in the field of left ventricular contour segmentation.Finally, according to the experimental results, we discusse and verifie that the convolutional module of the normalization operation can accelerate the convergence of the network and improve the accuracy, and the up-sampling module using the nearest neighbor interpolation method is more friendly to the smaller target segmentation such as the left ventricle contour, and our model can accelerate network convergence to a certain extent.
      End-to-end Network Structure Optimization of Scene Text Recognition Based on Residual Connection
      HUANG Jin-xing, PAN Xiang, ZHENG He-rong
      Computer Science. 2020, 47 (8): 221-226.  doi:10.11896/jsjkx.190500017
      Abstract ( 0 )   PDF(1897KB) ( null )   
      References | Related Articles | Metrics
      The existing text recognition methods will cause decreased recognition accuracy due to not enough network depth.The paper addresses this issue and proposes an improved end-to-end text recognition network structure.Firstly, the algorithm takes the text as a sequence, and uses the residual module to divide the text into columns for the recurrent layer.This residual structureincreases network depth, to maintain the network’s best representation of the text image.It can capture the best feature representation of text images.Meanwhile, the residual module uses the stacked layer to learn the residual mapping to improve the convergence of the network though the number of layers is obviously increased.Secondly, we use the recurrent layer to model the context of these text features, and the modeling results will be taken into the softmax layer to predict corresponding labels, which achieve the recognition of arbitrary length of texts.The recurrent layer uses the Long Short-Term Memory to learn the dependencies between texts and solve the gradient vanishing problem in long sequence training.Finally, text label transcription and decoding are performed by the optimal path method.The method finds a path to maximize its probability, and outputs the sequence corresponding to the path as the optimal sequence.The improved text recognition network structure increases network depth, improves the feature description of text images and the stability under noises.In the experimental part, this paper compares with existing typical algorithms over the multiple test datasets (ICDAR2003, ICDAR2013, SVT and IIIT5K).The experiments show that the network structure can obtain better text recognition accuracy and verify the effectiveness of the proposed network structure.
      Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition
      LIANG Zheng-you, HE Jing-lin, SUN Yu
      Computer Science. 2020, 47 (8): 227-232.  doi:10.11896/jsjkx.190700009
      Abstract ( 3 )   PDF(1955KB) ( 1 )   
      References | Related Articles | Metrics
      Due to the short duration of micro-expressions and the small amplitude of motion, the automatic recognition of micro-expressions is still a challenging problem.Aiming at the problems, this paper proposes a Three-Dimensional Convolutional Neural Network Evolution (C3DEvol) method for micro-expression recognition.In the C3DEvol, three-dimensional Convolutional Neural Network (C3D) which can extract dynamic information effectively is used to extract micro-expression features in time domain and space domain.At the same time, the genetic algorithm with the capabilities of global search and optimization is used to optimize the network structure of C3D in order to obtain the optimal network structure and avoid local optimization.Experiments are performed on a workstation with two NVIDIA Titan X GPUs using the CASME2 dataset.Experiments show that the accuracy of C3DEvol micro-expression automatic recognition reaches 63.71%, which is better than the existing micro-expression automatic recognition method.
      Image Caption of Safety Helmets Wearing in Construction Scene Based on YOLOv3
      XU Shou-kun, NI Chu-han, JI Chen-chen, LI Ning
      Computer Science. 2020, 47 (8): 233-240.  doi:10.11896/jsjkx.190600109
      Abstract ( 3 )   PDF(4631KB) ( 3 )   
      References | Related Articles | Metrics
      In recent years, construction accidents caused by workers not wearing safety helmets occur frequently.In order to reduce the accident rate, this paper studies the image caption of workers wearing safety helmets.Existing image caption methods based on neural network are short of explanatory and detailed descriptions, and the research on the image caption of construction scene is relatively scarce.To solve this problem, this paper proposes YOLOv3 algorithm with the method based on the combination of semantic rules and sentence templates to gradually generate the description of wearing safety helmets.Firstly, images are collected, and the safety helmets wearing detection dataset and the image caption dataset are made.Secondly, the K-means algorithm is used to determine anchor boxes parameters, which are applicable to the dataset for the training and detection of YOLOv3 network.Thirdly, a semantic rule is predefined to combine the target detection results to extract visual concepts.Finally, the extracted visual concepts are filled into the sentence template generated by the image caption annotation, which is used to generate the image description statement about the workers wearing safety helmets or not in the construction scene.The Ubuntu16.04 system and the Keras deep learning framework are used to build the experimental environment, and different algorithmsare compared on the self-made datasets of helmet wearing.The experimental results show that the proposed method can not only effectively define the number of safety helmet wearers and non-wearers, but also achieve 0.722 and 0.957 respectively on BLEU-1 and CIDEr evaluation metrics, which are 6.9% and 14.8% higher than other methods, demonstrating the effectiveness and superiority of the proposed method.
      Single Image Defogging Method Based on Weighted Near-InFrared Image Fusion
      ZHU Zhen, HUANG Rui, ZANG Tie-gang, LU Shi-jun
      Computer Science. 2020, 47 (8): 241-244.  doi:10.11896/jsjkx.200300068
      Abstract ( 0 )   PDF(1702KB) ( 1 )   
      References | Related Articles | Metrics
      The traditional image defogging method has the problem that the image contrast in the fog-free area is too high, which causes the generated image visual effect is unnatural in some cases.In order to obtain natural and clear defogging images, a new single image defogging method based on weighted near-infrared(NIR) image fusion is proposed.Image contrast is restored by fusing the detail components of NIR images into visible images of the same scene.The NIR image is weighted using the transmission map to prevent excessive enhancement in the fog-free region.The experimental results show that compared with the traditional single image defogging methods, the proposed method can effectively restore the image contrast, does not excessively strengthen the fog-free area, and has higher PSNR and SSIM values.
      Research Status and Development Trend of Vehicle Following Control System
      ZHANG Jun-hui, CHEN Da-peng, LI Qing
      Computer Science. 2020, 47 (8): 245-254.  doi:10.11896/jsjkx.190700058
      Abstract ( 2 )   PDF(2670KB) ( 3 )   
      References | Related Articles | Metrics
      It has strongly been showed that intelligent vehicle following and vehicle platooning will be an effective way to deal with daily road traffic problems such as traffic congestion, traffic safety and environmental pollution.In this article, the development stages of vehicle following control system are explicated, and the latest research achievements of vehicle following control system in recent years are objectively and comprehensively discussed from the aspects of environmental perception technology, desired inter-vehicle clearance strategy, longitudinal and lateral vehicle dynamic modeling, as well as cooperative decision and control algorithms.Furthermore, the common problems of vehicle following control system are summarized, and some viewpoints concerning the future trend of such research are also suggested.
      Word Embedding Optimization for Low-frequency Words with Applications in Short-text Classification
      CHENG Jing, LIU Na-na, MIN Ke-rui, KANG Yu, WANG Xin, ZHOU Yang-fan
      Computer Science. 2020, 47 (8): 255-260.  doi:10.11896/jsjkx.191000163
      Abstract ( 2 )   PDF(2059KB) ( 1 )   
      References | Related Articles | Metrics
      Many Natural Language Processing (NLP) tasks have benefitted from the public availability of general-purpose vector representations of words trained with large-scale datasets.Since pre-trained word embeddings only have general semantic features from large corpus, it is often necessary to fine-tune these embeddings to make them more suitable for target tasks when it is applied to certain downstream tasks.But, the words with low occurrence frequencies can hardly receive stable gradient information when fine-tuning.However, low-frequency terms are likely to convey important class-specific information in tasks for short text classification.Therefore, it is necessary to obtain a better low-frequency word embedding on the specific task.To address the problem, this paper proposes a model-agnostic algorithm, which optimizes the vector representations of these words according to the task specifics.This approach leverages the update information from common words to guide the embedding updating on rare words.It helps achieve more effective embeddings for the low-frequency words.Our evaluation on three public short-text classification tasks shows that the proposed algorithm produces better task-specific embeddings for rarely occurring words, as a result, the model performance is improved from 0.4% to 1.4% on these tasks.It proves the positive influence of low frequency words on short-text classification tasks, which can shed light on short text classification tasks.
      Convolutional Neural Networks Compression Based on Pruning and Quantization
      SUN Yan-li, YE Jiong-yao
      Computer Science. 2020, 47 (8): 261-266.  doi:10.11896/jsjkx.190700062
      Abstract ( 1 )   PDF(2523KB) ( null )   
      References | Related Articles | Metrics
      With the development of deep learning, Convolutional Neural Networks(CNN), as one of its important algorithms, is widely applied in a variety of fields such as target detection, natural language processing, speech recognition and image identification, and achieves better results than the traditional algorithm.The number of parameters and calculation are increasing with the depth of network structure, resulting in many algorithms must be implemented on GPU.So it is difficult to apply the CNN model to mobile terminals which has limited resources and high real-time request.To solve this problem, this paper presents a method of optimizing network structure and parameters simultaneously.Firstly, the algorithms prunes weight according to its influence on the results of network, and ensure that the redundant information is removed while retaining the important connection of the mo-del.Then, this paper quantizes the float-point weight and activation of CNN.This changes float-point operation to fixed-point ope-ration.It not only reduces the computational complexity of the network model, but also reduces the size of the network model.To verify the algorithm, deep learning framework tensorflow is selected, and Spyder compiler is used in Ubuntu 16.04 operating system.The experimental results show that this method reduces size of LeNet model with simple structure from 1.64M to 0.36M.Compression ratio reaches 78%, but the accuracy drops only 0.016.And it also reduces the size of MobileNet with Lightweight network from 16.9M to 3.1M.Compression ratio reaches 81% with the accuracy dropping only 0.03.The data show that combining the weight pruning and parameter quantification of convolution neural network can effectively compress the convolution neural network within the acceptable range of accuracy loss.So, this method solve the difficulty of deploying the convolution neural network to the mobile terminal.
      Intelligent 3D Printing Path Planning Algorithm
      YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu
      Computer Science. 2020, 47 (8): 267-271.  doi:10.11896/jsjkx.190700184
      Abstract ( 1 )   PDF(2628KB) ( 1 )   
      References | Related Articles | Metrics
      The path planning of large industrial parts in additive manufacturing directly affects manufacturing quality and efficiency.At present, the commonly used traditional path planning methods have many problems, such as turning and stacking of print head and the number of rise and fall of print head, so they are not suitable for large industrial parts.Therefore, an intelligent path planning algorithm is proposed.Firstly, the two-dimensional plane obtained after slicing is concavely convexly decomposed into printing sub-areas, and then the internal long-axis scanning along the partition is performed on each sub-area to reduce the number and length of printing paths.Then, the sub-partition connection is treated as a traveling salesman problem (TSP) using gene-tic algorithms to complete the path planning between the sub-areas.Meanwhile, an intelligent 3D printing path planning system is designed and developed with C# language, which has the functions of slice input and display, print width setting, intelligent path planning and G-code code output.By comparing with the two traditional path planning algorithms, the proposed method significantly reduces the number of paths, the idle travel distance, and the number of print head lifts.The sub-partition-based intelligent path planning method provides a new idea for the additive manufacturing process of large industrial parts.
      Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm
      JIANG Chen-kai, LI Zhi, PAN Shu-bao, WANG Yong-jun
      Computer Science. 2020, 47 (8): 272-277.  doi:10.11896/jsjkx.190700138
      Abstract ( 2 )   PDF(2282KB) ( 6 )   
      References | Related Articles | Metrics
      Aiming at the path planning and conflict problems of automatic guided vehicle (AGV) in flexible manufacturing systems, an improved Dijkstra algorithm based on time window is proposed to realize dynamic path planning of multiple AGVs.Firstly, the traditional Dijkstra algorithm is used to calculate the path of the multi-AGV for the scheduled task, and the degree of use of the planned path is calculated and the weighting coefficient is calculated, and then the weighted path length is updated to the database.Secondly, calculate the time for the AGV to pass through each station node, and avoid collision conflicts through the arrangement of time windows.In the end, when the conflict occurs, the path of the lower priority AGV is re-planned by calcula-ting and setting the priority of the AGV.The simulation results show that the proposed algorithm can effectively avoid conflicts and deadlocks under the optimal path, which not only improves the system efficiency, but also makes the system more robust.
      Study on Optimal Scheduling of Gate Based on Mixed Integer Programming
      ZHANG Hong-ying, SHEN Rong-miao, LUO Qian
      Computer Science. 2020, 47 (8): 278-283.  doi:10.11896/jsjkx.190400154
      Abstract ( 1 )   PDF(1792KB) ( 1 )   
      References | Related Articles | Metrics
      In order to alleviate effectively the current situation of airport aircraft delay, the optimal scheduling of airport gate is studied.By deeply analyzing the characteristics of airport ground operation, considering the constraint restrictions such as aircraft model matching, buffer time and aircraft conflict, scientifically and reasonably weighing the various interest needs of the airport, this paper proposes a mixed integer programming model to optimize the gate scheduling problem, the main goal is to ensure the safe operation of the aircraft under the premise, so that the total flight delay time is the shortest.The probability distribution function is introduced to avoid the occurrence of aircraft conflict.Combining with the basic theory of multi-objective optimization and branching definition algorithm, the optimal assignment schemeis sought.The simulation results show that the model optimizes the timing of the expected inbound aircraft in the airport, adjusts the position allocation conflict by optimizing the scheduling scheme, and gets the optimal allocation scheme.The algorithm can reduce the search space, improve the efficiency of the solution, significantly reduce the total delay time, and improve the utilization rate of airport gate resources.Compared with heuristic algorithm, the aircraft delay is reduced by 2.4%, and the proposed method caneffectively reduce the delay rate of airport ground flight.
      Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery
      ZHANG Qing-qi, LIU Man-dan
      Computer Science. 2020, 47 (8): 284-290.  doi:10.11896/jsjkx.190700082
      Abstract ( 1 )   PDF(2556KB) ( null )   
      References | Related Articles | Metrics
      As an important property of complex networks, community structure is of great significance for understanding the function and organization of networks.In order to solve the community discovery problem of complex networks, a multi-objective five-elements cycle optimization algorithm (MOFECO) is proposed.Firstly, the task of the community discovery is modelled as a multi-objective optimization problem, and two opposite targets, inverse ratio vssociation (IRA) and ratio cut (RC) are selected as the objective function.Then, based on five-elements cycle model (FECM), individual updating is implemented through local optimal individuals and global optimal individuals, and crossover and mutation operators are introduced to improve the update strategy.Finally, the fast non-dominated sorting method is used to obtain the Pareto optimal community partitioning set, which is helpful to reveal the hierarchical structure of complex networks.Experiments are conducted on LFR benchmark networks and real social networks, compared with single-objective algorithms(GA-Net, Meme-Net) and multi-objective algorithms, such as MOGA-Net, MOCD, MOEA/D-Net, DMOPSO, DIM-MOEA/D and MOCD-ACO, MOFECO overcomes the shortcomings of traditional single-objective optimization of community structure division, and improves the accuracy of community discovery.
      Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy
      LI Yang, LI Wei-gang, ZHAO Yun-tao, LIU Ao
      Computer Science. 2020, 47 (8): 291-296.  doi:10.11896/jsjkx.190600107
      Abstract ( 4 )   PDF(2443KB) ( 1 )   
      References | Related Articles | Metrics
      The individuals in the grey wolf group tend to approach to the area where the leadership grey wolf is located because of the reduction of attenuation factor in the middle and late stage of the optimization process for the standard grey wolf optimization algorithm, which results in poor global optimization ability and reduces the optimization accuracy of the algorithm.Aiming at this problem, an improved grey wolf optimization algorithm (IGWO) is proposed.Firstly, by analyzing the influence of the decay factor, an adjustable segmentation decay factor is presented to focus on proper balance between exploration ability and exploitation ability.The appropriate parameter is searched to achieve more precise optimization.And it ensures that the algorithm has a certain global search ability in the middle and later stages of the optimization process.The numerical simulation experiments show that increasing the exploration ratio is beneficial to improve the convergence accuracy of the algorithm.Meanwhile, leadership wolves are selected by probability to carry out levy flight operation or random walk operation respectively in the process of optimization.The global optimization ability of the algorithm is improved by the levy flight with the feature of short-range flight search and occasional long-distance walk.While the local optimization ability is improved by random walk with relatively centralized search range.Simulation experiments are conducted on optimization problems.The results show that compared with other algorithms, the improved algorithm has great performance in optimization precision, algorithm stability and convergence speed.
      Salp Swarm Algorithm with Random Inertia Weight and Differential Mutation Operator
      ZHANG Zhi-qiang, LU Xiao-feng, SUI Lian-sheng, LI Jun-huai
      Computer Science. 2020, 47 (8): 297-301.  doi:10.11896/jsjkx.190700063
      Abstract ( 11 )   PDF(1316KB) ( 1 )   
      References | Related Articles | Metrics
      After analyzing and summarizing the related research achievements of particle swarm optimization (PSO) and differential evolution (DE) algorithms, this paper proposes an improved salp swarm algorithm (iSSA) with random inertia weight and differential mutation operator for enhancing the convergence rate, computational accuracy and global optimization of SSA algorithm.Firstly, the random inertia weight of particle swarm optimization is introduced in the followers’ position update equation of SSA algorithm in order to enhance and balance the exploration and exploitation ability of SSA algorithm.Secondly, the leader position update of SSA algorithm is replaced with the mutation operator of differential evolution algorithm DE, which is used to improve the convergence rate and computational accuracy of SSA algorithm.For the purpose of checking the improvement effect on SSA algorithm by the random inertia weight and differential mutation operator, simulation experiments on some high-dimension benchmark functions are performed and comparisons between the proposed iSSA and two typical improved SSA algorithms named by enhanced salp swarm algorithm (ESSA) and crazy and adaptive salp swarm algorithm (CASSA) are performed.The experimental results and analysis show that, the proposed iSSA with random inertia weight and differential mutation operator obviously improves the convergence rate, computational accuracy and global optimization when compared with two typical improved ESSA and CASSA algorithms in the case of no any increase in the time complexity of SSA algorithm.
      Review of Link Prediction Methods Based on Feature Classification
      WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao
      Computer Science. 2020, 47 (8): 302-312.  doi:10.11896/jsjkx.190700136
      Abstract ( 0 )   PDF(2715KB) ( 1 )   
      References | Related Articles | Metrics
      As an important research direction of network science research, link prediction of complex network has been more and more attention from experts from various disciplines, and it can make use of existing network information, such as the features of the nodes and edges, to predict possible future relationships, missing information in the network, and new or disappearing information, identify the false interactions, evaluate network evolution mechanism and conduct network reconfiguration, etc.Current articles on link prediction mainly come from the expert in engineering, computer science and physics.They are independent and lack cooperation, and there are few review articles combining multidisciplinary link prediction.The goal of this article is from the perspective of computer science and physics comprehensive to review, analyze, and discusse the research progress of link prediction algorithm based on feature classification, introduces a variety of feature extraction techniques in this field.This paper firstly introduces the idea of layering into the classification of link prediction algorithm, which divides the classification model into three layers, the metadata layer, features classification layer and feature extraction layer.The classification model includes two parts and seven aspects, that is, the prediction algorithm is divided into two parts, features extraction method and features learning method.The seven aspects are the similarity based methods, probabilistic methods, likelihood based methods, matrix factorization based method, random walk based method, neural network based method and custom loss function based method.This classification method covers many classical and latest link prediction techniques in various disciplines, including GNN, GCN, RNN and RL, which are the most popular link prediction techniques in graph neural networks.The differences of these algorithms in model complexity and prediction performance are studied, and the challenges of current link prediction technology in the future are discussed.
      Unknown Binary Protocol Format Inference Method Based on Longest Continuous Interval
      CHEN Qing-chao, WANG Tao, FENG Wen-bo, YIN Shi-zhuang, LIU Li-jun
      Computer Science. 2020, 47 (8): 313-318.  doi:10.11896/jsjkx.190700031
      Abstract ( 0 )   PDF(2057KB) ( null )   
      References | Related Articles | Metrics
      In the process of format inference of unknown binary protocols, a large amount of prior knowledge is often introduced, the experimental operation is complex and the accuracy of the results is low.For this reason, a method that requires less artificial setting of parameters, simple operation and higher accuracy is proposed to infer the unknown binary protocol format.The preprocessed protocol data is clustered hierarchically, and the optimal clustering is obtained by using CH (Calinski-Harabasz) coefficient as the evaluation criteria.Through the improved sequence comparison of the clustering results, the protocol data sequence with interval is obtained, continuous intervals are counted and merged to analyze protocol formats.The experimental results show that the binary protocol format inference method proposed in this paper can infer more than 80% of the field intervals in the unknown binary protocol.Compared with the format inference method in AutoReEngine algorithm, the F1-Measure value of the proposed method is improved by about 30% as a whole.
      Prediction of Wireless Network Traffic Based on Clustering Analysis and Optimized Support Vector Machine
      CAO Su-e, YANG Ze-min
      Computer Science. 2020, 47 (8): 319-322.  doi:10.11896/jsjkx.190800075
      Abstract ( 1 )   PDF(1748KB) ( 2 )   
      References | Related Articles | Metrics
      In order to solve the problems existing in the current wireless network traffic prediction process and improve the accuracy of wireless network traffic prediction, a wireless network traffic prediction model based on clustering analysis algorithm and optimized support vector machine is proposed.Firstly, data sets of wireless network traffic are collected and clustering analysis algorithm is used to construct the training sample set.And then, support vector machine is used to learn the training samples of wireless network traffic, and cuckoo search algorithms is introduced to optimize the parameters of support vector.Thus, the prediction model of wireless network traffic is established.Finally, the effectiveness of the model is analyzed through a specific example of wireless network traffic prediction.The results show that the proposed model has high prediction accuracy, improves the efficiency of wireless network traffic modeling, and the prediction effect of wireless network traffic is better than the current classical wireless network traffic prediction models, which has more significant advantages.
      Multi-source Sensor Body Area Network Data Fusion Model Based on Manifold Learning
      ZHANG Jun, WANG Yang, LI Kun-hao, LI Chang, ZHAO Chuan-xin
      Computer Science. 2020, 47 (8): 323-328.  doi:10.11896/jsjkx.191000012
      Abstract ( 0 )   PDF(2573KB) ( 3 )   
      References | Related Articles | Metrics
      Due to the problem of large amount of data collected by multi-sensors in wireless body area networks and redundant data types, it is difficult to effectively perform multi-dimensional data fusion.Although traditional manifold and decomposition data fusion methods (Isomap, MDS, PCA, etc.) have the ability to generate a reasonable rejection gradient at a small distance and are less affected by anomalies, the data dimension reduction effect for wireless multi-sensor volume domain networks is notideal.Therefore, this paper proposed the T-SNE algorithm based on manifold learning to fuse multi-sensor body area network data.The T-SNE algorithm first converts the Euclidean distance between a high-dimensional data point and its corresponding low-dimensional data point into a conditional probability matrix, then iterates the processed low-dimensional probability set a finite number of times, and finally updates the low-dimensional probability matrix to make the distance more reasonable exclusion gradient be generated between the small points, and a multi-dimensional body area network data fusion model is constructed.Experimental results show that compared with the traditional manifold reduction algorithm and traditional decomposition dimensionality reduction algorithm under a specific body area network data set, the T-SNE algorithm has a precision of 1.11 times that of Isomap, 1.33 times that of MDS, and 1.21 times that of PCA, achieves a better data dimensionality reduction effect.
  • Computer Science
    NCTCS2017 (0)
    Network & Communication (159)
    Information Security (261)
    Software & Database Technology (3)
    Artificial Intelligence (247)
    Surveys (52)
    Graphics, Image & Pattern Recognition (58)
    WISA2017 (1)
    WISA2018 (1)
    NASAC 2017 (13)
    CGCKD 2018 (12)
    Netword & Communication (4)
    Graphics, Image & Pattern Recognition (7)
    CCF Big Data 2017 (7)
    NCIS 2017 (5)
    Graphics, Image & Pattem Recognition (10)
    Interdiscipline & Frontier (74)
    Review (33)
    Intelligent Computing (87)
    Pattern Recognition & Image Processing (82)
    Big Date & Date Mining (21)
    Interdiscipline & Application (107)
    ChinaMM 2017 (12)
    CCDM2018 (14)
    Graphics ,Image & Pattern Recognition (45)
    Pattem Recognition & Image Processing (25)
    Big Data & Data Mining (42)
    Surverys (5)
    NDBC 2018 (8)
    Graphics,Image & Pattern Recognition (11)
    Database & Big Data & Data Science (56)
    Computer Graphics & Multimedia (94)
    Intelligent Software Engineering (17)
    Databωe & Big Data & Data Science (14)
    Survys (0)
    Network & Communication (0)
    Graphics, Image & Patten Recognition (0)
    Interdiscipline & Frontier (0)
    HPC China 2018 (6)
    Data Science (18)
    Software & Database Technology (48)
    ChinaMM2018 (14)
    ChinaMM2019 (0)
    Big Data & Data Science (61)
    Network & Cornmunication (4)
    Theoretical Computer Science (10)
    Software Engineering & Database Technology (8)
    Computer Architecture (12)
    Discipline Construction (2)
    Computer Science Theory (10)
    Computer Network (57)
    Contents (5)
  • [an error occurred while processing this directive]
  • Polynomial Time Algorithm for Hamilton Circuit Problem (4182)
    JIANG Xin-wen
    Computer Science. 2020, No.7:8-20
    Abstract (4182) PDF (1760KB) (6828)
    Detecting Community from Bipartite Network Based on Spectral Clustering (208)
    ZHANG Xiao-qin, AN Xiao-dan, CAO Fu-yuan
    Computer Science. 2019, No.4:216-221
    Abstract (208) PDF (1772KB) (2493)
    Review of Time Series Prediction Methods (414)
    YANG Hai-min, PAN Zhi-song, BAI Wei
    Computer Science. 2019, No.1:21-28
    Abstract (414) PDF (1294KB) (2316)
    Survey of Distributed Machine Learning Platforms and Algorithms (656)
    SHU Na,LIU Bo,LIN Wei-wei,LI Peng-fei
    Computer Science. 2019, No.3:9-18
    Abstract (656) PDF (1744KB) (2184)
    State-of-the-art and Development Trend of Artificial Intelligence Combined with Law (1167)
    HUANG Qiao-juan, LUO Xu-dong
    Computer Science. 2018, No.12:1-11
    Abstract (1167) PDF (1447KB) (2169)
  • » Diagnosability of Discrete-event Systems Based on Temporal
      Computer Science. 2012 Vol. 39 (8): 210-214,251
      Cited by: Baidu(626)
    » Key Technologies and Applications of Internet of Things
      LIU Qiang,CUI Li,CHEN Hai-ming
      Computer Science. 2010 Vol. 37 (6): 1-4
      Cited by: Baidu(444)
    » Research Survey of Cloud Computing
      LI Qiao,ZHENG Xiao
      Computer Science. 2011 Vol. 38 (4): 32-37
      Cited by: Baidu(194)
    » P-sets and its Applied Characteristics
      SHI Kai-quan
      Computer Science. 2010 Vol. 37 (8): 1-8
      Cited by: Baidu(135)