Loading...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Current Issue

    • 论文
      An analytical model and its applications for
      minimizing total makespan of multiple MapReduce jobs                 
      TIAN Wenhong1,2,CHEN Yu2,WANG Xinyang2,XUE Ruini2,ZHAO Yong2
      2014, 36(04): 571-578. doi:
      Abstract ( 137 )   PDF (666KB) ( 219 )     

      As large-scale MapReduce clusters become widely adapted to process huge amount of data, one of critical challenges is to improve the service quality of MapReduce clusters by minimizing their makespan. A scheduling model can be considered for multiple MapReduce jobs. It is observed that the order in which these jobs are executed can have a significant impact on their overall makespan. The goal of the paper is to design a framework of automatic job scheduler and propose an analytical model for minimizing the makespan of such a set of MapReduce jobs. By considering a better strategy and implementation, we can meet the conditions of the classical Johnson algorithm and use it to find the optimal solution. Under our proposed new strategy, solving the balanced pools problem becomes exact in linear time, better than existing simulating approaches. Our proposed analytical results can be applied to improve system response time, energyefficiency and load-balance in Hadoop cluster pools, while corresponding numerical examples validate our observations.

      Simulation driven package design for FT1500 DDR3 interface           
      LI Tiejun,SUN Yan,ZOU Jing,ZHANG Xiufeng
      2014, 36(04): 579-583. doi:
      Abstract ( 111 )   PDF (1572KB) ( 198 )     

      To solve the problems of signal integrity and power integrity in DDR3 interface of FT1500 CPU,a simulation driven package design method is proposed.At the early stage,simulation is used to make accurate design rules and objectives. Then the package design is optimized repeatedly according to the simulation results.After the package design is completed, it is verified by the simulation.The design method is applied to FT1500 chip,whose DDR3 interface can work steadily with 1400Mbps.  

      TM-CAM:An efficient soft error
      tolerant content addressable memory         
      SUN Yan,LI Tiejun,WANG Fayuan,ZHANG Minxuan
      2014, 36(04): 584-588. doi:
      Abstract ( 141 )   PDF (937KB) ( 205 )     

      In integrated circuits, Content Addressable Memory (CAM) is one of the most sensitive units to soft errors, but the traditional faulttolerant technique, such as errorcorrecting coding techniques, cannot be applied to it due to its special structure. To address the problem, the paper proposes a simple but efficient soft error tolerant structure: TMCAM, which is based on the triplevalue match line and can detect any one bit error in the CAM. Experimental results show that the proposed TMCAM can effectively mitigate the soft error problem at very low cost. 

      Improving delay estimation in logical
      effort under deep sub-micron technology           
      BI Zhuo1,CHEN Xiaojun2
      2014, 36(04): 589-595. doi:
      Abstract ( 114 )   PDF (544KB) ( 188 )     

      The logical effect delay estimation method, proposed by Sutherland I E,can quickly estimate the delay of the logic gates and logic circuits and reduce the difficulty of logical circuits design at the beginning of design.With CMOS technology entering deep submicron, however, short channel effect has begun to affect the correctness of the method of classical logic effort. In order to improve the accuracy of logical effort estimation, the paper proposes an improvement method of logical effort based on the velocity saturation. This method contains two main steps. Firstly, the width ratio of PMOS and NMOS in inverter is considered to precisely estimate the inverter delay, which is normalized. Secondly, logical gate delay is estimated based on inverter delay and velocity saturation. In hspice simulation,32nm、65nm、90nm and 130nm from Arizona State University PTM (Predictive Technology Model), and 45nm from North Carolina State University FreePDK are used. Comparative experiment demonstrates that our method improves the accuracy of the NAND gates delay estimation, approximately by 10%.

      An X-filling algorithm for EFDR code           
      GUO Dongsheng,TANG Min,WU Tiebin,LIU Hengzhu
      2014, 36(04): 596-600. doi:
      Abstract ( 95 )   PDF (367KB) ( 184 )     

      To address the problem of the shortcoming of the don’t case bits (Xs) filling algorithm in EFDR coding technique,a novel EFDRbased X-filling algorithm (ESA) is proposed. According to the coding characteristic of EFDR,the proposed X-filling algorithm fills the don’t care bits in all 0s,all 1s or blockpartitioned filling based on the properties of the runs of don’t care bits and the specified bits on both sides of don’t care bits. The proposed ESA algorithm can achieve higher test compression effect of EFDR and decrease the test application time. Simultaneously, it will not affect the test hardware overhead and test power dissipation of EFDR since the proposed X-filling algorithm only fills the don’t care bits in the test sets as other X-filling techniques.Experimental results demonstrate the effectiveness of the proposed technique.

      Adaptability analysis of data-intensive applications
      on on-chip storage structure of NVIDIA Fermi          
      SHU Bing,REN Xiujiang,ZHANG Qingbo,CHEN Fangyuan
      2014, 36(04): 601-606. doi:
      Abstract ( 111 )   PDF (617KB) ( 198 )     

      Data-intensive application is a class of application which mainly focuses on searching,analyzing,transporting and processing data.The paper simulates the NVIDIA Fermi architecture using GPGPU-SIM simulator,analyzes the adaptability of Fermi’s memory architecture with data-intensive applications,and gives some advices regarding optimization design on memory hierarchy.

      Security-constrained workflow scheduling
      in cloud computing environments         
      MA Junbo,YIN Jianping
      2014, 36(04): 607-614. doi:
      Abstract ( 104 )   PDF (816KB) ( 222 )     

      Workflow scheduling is one of the critical problems in cloud environment. Lots of strategies are presented to solve it. However, most of them only care about satisfying the time and cost QoS requirements of the users, such as the deadlines of the tasks, and cannot guarantee the security of scheduling. But the security is one of the most concerned issues for the cloud users. To solve this problem, a security constraint model for workflow scheduling problem is presented. Based on it, the Variable Neighborhood Particle Swarm Optimization(VNPSO) is adapted and implemented as the scheduling algorithm. Two representative metaheuristic based scheduling algorithms including MaxMin Ant Colony Optimization (MMACO) and Genetic algorithm (GA) are also implemented as the candidate scheduling algorithms. CloudSim is set up as the simulation platform, and the simulation experiments show that the variable neighborhood search heuristic provides a good balance between global exploration and local exploitation and makes VNPSO feasible and effective for scheduling workflow tasks.

      Application of GARCH model with wavelet
      transform in network traffic forecast             
      LIU Yuan,HUANG Shizhong
      2014, 36(04): 615-619. doi:
      Abstract ( 112 )   PDF (845KB) ( 223 )     

      Network traffic has characteristics of nonlinearity, heteroskedasticity, and volatility clustering in some network environments. Traditional models such as Auto Regressive Moving Average(ARMA) model with wavelet transform fail to describe these characteristics very well. Therefore, Generalized Auto Regressive Conditional Heteroskedasticity(GARCH) model with wavelet transform is studied for network traffic forecast. With wavelet transform, a network traffic series is divided into low frequency part and high frequency part, which are applied for GARCH modeling and forecasting respectively. Then, the forecast results of the subseries are reconstructed so as to implement the forecast of the original network traffic. The simulation shows that the accuracy of the forecast of GARCH model with wavelet transform is much better than that of ARMA model with wavelet transform.

      Measurement and performance analysis of
      CDNs in mainland China          
      WU Jinfu,TIAN Ye
      2014, 36(04): 620-626. doi:
      Abstract ( 182 )   PDF (821KB) ( 232 )     

      Content Delivery Networks(CDNs) are arranged for efficient delivery of the user's requests' according to the realtime environment of the network, avoiding network congestion effectively as well as optimizing the enduser experience. CDNs have become a critical part of today's Internet. Measurements of CDNs are required for understanding CDN performance and analyzing its architecture optimization, which aims to improve the quality of service. Due to the complexity of the network infrastructure in mainland China, researches on measurement and performance analysis of CDNs in mainland China are relatively few. We propose a novel CDNs measurement method based on the HTTP proxy that we use as vantage points. After extensively measuring the CDNs in mainland China, we obtain CDNs nodes distribution. Finally, we analyze the deployment strategy, load balancing, and node scheduling policies of different CDNs service providers.

      Far-end crosstalk cancellation algorithm
      in multi-user VDSL2 system         
      LIU Chao,LIN Jiming
      2014, 36(04): 627-633. doi:
      Abstract ( 138 )   PDF (915KB) ( 200 )     

      As broadband access network speed advances,VDSL2 technology has become the mainstream method of the last mile access.The dramatic increase in the number of user transmission makes the signal crosstalk an important factor between the transmissions lines, which restricts VDSL2 system performance. The crosstalk between the lines is divided into a nearend crosstalk (NEXT) and a farend crosstalk (FEXT).VDSL2 system uses DMT carrier modulation technique, and nearend crosstalk can be filtered out by the filter, but farend crosstalk cannot be eliminated. This paper mainly studies a method of farend crosstalk noise cancellation in VDSL2 system, proposes how farend crosstalk noise is evaluated and calculated, and derives the farend crosstalk offset formula.And it calculates the influence of crosstalk noise from other lines on each line.The receiver’s signal can eliminate the influence of crosstalk noise by the crosstalk noise preelimination algorithm at the transmitter.Therefore,SNR values of the receiver's signal and VDSL2 transmission rate are improved.

      On the algorithm of controlling of
      matching coefficient of complex networks         
      GUAN Shijie
      2014, 36(04): 634-638. doi:
      Abstract ( 109 )   PDF (611KB) ( 201 )     

      According to the analysis of the detection data provided by CAIDA, the AS level topology of the internet developed by the time is found. On the basis of the deep analysis of the matching coefficient, an algorithm, named Edges Rewiring, is proposed, which can monotonously change the coefficient of the matched network. This algorithm can construct a network set with continuous matching coefficient in two directions. It can construct the crescent continuous net of matching algorithm network when choosing the same direction of reconnection, and it can construct the decreasing continuous matching algorithm when choosing the opposite direction of reconnection. The network with the maximal matching coefficient or with the minimal matching coefficient can be constructed when the number of edges rewiring is enough.

      Quantitative security evaluation against
      timing attacks in cryptographic algorithm
      HE Zhangqing1,2,DAI Kui2,TONG Yuanman3,ZOU Xuecheng2
      2014, 36(04): 639-643. doi:
      Abstract ( 174 )   PDF (537KB) ( 197 )     

      Timing attack is one of the most threatening sidechannel attacks. In order to design efficient cryptosystems against timing attack, it is necessary to find the vulnerability at design time and quantitative analyze the resistibility to timing attack of the cryptographic algorithms. The paper proposes a unified method for identifying the feasible timing attack in various implementations of cryptographic algorithms, which are described by the Enhanced Data Dependence Graph (EDDG), and analyzes the timing attack vulnerabilities by finding some intermediary variable in the EDDG.The number of time samples required for a successful timing attack is used to characterize the resistibility, which is computed based on the signal-to-noise ratio of the corresponding timing attack.      

      Improved scheme for scalar multiplication against
      power analysis attacks in elliptic curve cryptography          
      ZHANG Youqiao1,ZHOU Wuneng1,SHEN Ye2,LIU Yujun2
      2014, 36(04): 644-648. doi:
      Abstract ( 114 )   PDF (458KB) ( 211 )     

      Elliptic curve scalar multiplication is the main computing process in Elliptic Curve Cryptography (ECC), and the efficiency and security of scalar multiplication is always the research hotspot. Aiming at the problem that elliptic curve scalar multiplication has a tremendous computation and is vulnerable to power analysis attacks, a fast sliding window algorithm against power analysis attacks is proposed. In Jacobian and Affine mixed coordinates, the signed sliding window algorithm strategy is used to perform elliptic curve scalar multiplication, and random keys method is applied against power analysis attacks. The analysis results show that, compared with binary expansion method and key assignment method, the improved signed sliding window scalar multiplication algorithm improves calculation efficiency and antiattack performance significantly.

      A novel handoff strategy based on multi-service
      in mobile communication systems           
      LIU Chenggang1,JIA Zhenhong1,QIN Xizhong1,SHENG Lei2,CHEN Li2
      2014, 36(04): 649-654. doi:
      Abstract ( 98 )   PDF (1113KB) ( 240 )     

      Aiming at the problem of high blocking probability in many handoff strategies, a novel handoff strategy is proposed to improve the performance of mobile communication systems by adopting some delay to the new calls over the handoff calls when there exists one idle channel. The time is shortened in the busy state. The opportunities of the new call and handoff call to occupy channel are increased. The strategy also takes into account the priority of different data types, and only when the data packet in high-priority data queue is empty, the data packets in general data queue can be transmitted. Expression for the dropping probability of handoff calls and the blocking probability of new calls and the dropping probability of data are derived. Through comparison with the channel reservation strategy and movable boundary strategy, it can be proved that the new handoff strategy provides much better performance improvement by reducing the dropping probability and the blocking probability.

      Software protection technique
      based on improved virtual machine           
      WU Weimin,XU Wenfeng,LIN Zhiyi,SI Si,RUAN Yibang
      2014, 36(04): 655-661. doi:
      Abstract ( 135 )   PDF (992KB) ( 211 )     

      For the increasingly serious software protection problem, the software protection technique based on virtual machine is analyzed, studied and improved, and thus a new software protection technique based on improved virtual machine is proposed. The proposal uses virtual junk code sequence and virtual instruction transformation technique, improves the virtual instruction system of original virtual machine, and hence increases complexity and confusion for virtual machine execution and has the advantages of high antireversing, tamperproof and anti cracking. Experimental analysis proves that the improved virtual machine protection technique outperforms other virtual machine protection techniques.

      Testing method for model driven architecture based on ASL             
      ZHANG Xiaoyan,WEN Hui
      2014, 36(04): 662-666. doi:
      Abstract ( 118 )   PDF (700KB) ( 191 )     

      Aiming at the issues of late test startup in software development methods with model driven architecture (MDA), difficulty in finding the flaws hidden in models,deficient precise semantemes in UML model description and others, proposes a model test method based on ASL:Starting from the UML model, Action Specification Language (ASL) is applied to platform independent model (PIM) in order to build a test model. Narrates the operation mode of ASL sentences in MDA process,creating process of PIM, steps for building test cases,implementation of tests,and finally applies ASL to build test environment on the basis of UML diagrams by combining examples and creates systematical test cases to test the model and business logic.Experimental results show that the proposed model test method based on ASL can not only simplify and abstract the complicated test cases by using model driven, but also disclose the flaws in the earlier part of software life cycle,preventing the flaws from being amplified as the software development process continues.

      A fusion algorithm of swarm intelligence and
      its application in emergency services facility location         
      XU Jun,XU Xiaodong
      2014, 36(04): 667-673. doi:
      Abstract ( 117 )   PDF (614KB) ( 207 )     

      In order to solve the problem of prematurity of swarm intelligence algorithm and slow speed of convergence of bacterial forging algorithm, an algorithm is proposed, which fuses quantum particle swarm together with bacteria foraging optimization. After considering the advantages of bacteria foraging optimization, quantum computing theory and particle swarm optimization, the proposed fusion algorithm takes the bacterial foraging algorithm as the main body and embedded quantum evolutionary algorithm and particle swarm optimization algorithm into it, thus improving the performance of the algorithm greatly. Through solving and validating the three criteria functions, the results show that the proposed fusion algorithm improves convergence precision and speed. Finally, the proposed algorithm is used to solve public health emergency service facility location problem and achieves good results, proving its effectiveness.

      Research overview of cooperative coevolutionary algorithms        
      ZHANG Kaibo,LI Bin
      2014, 36(04): 674-684. doi:
      Abstract ( 171 )   PDF (528KB) ( 426 )     

      Cooperative coevolution algorithm is a hot research topic in computational intelligence in recent years.Inspired by the principle of natural selection,cooperative coevolution algorithm constructs two or more groups and establishes the cooperative relationship among the groups.Two or more groups cooperates together to improve their performance,be adapted to dynamic evolutionary circumstance of complicated systems and largescale evolutionary circumstance,thus achieving the goal of population optimization.The research state and advances of cooperative coevolution algorithms in domestic and foreign are discussed and surveyed.The paper introduces the three main aspects of cooperative coevolution algorithm: basic structure and corresponding studies,basic and improved algorithms,and some applications in the real life.Finally,research prospects are indicated.

      Developing a health assessment system
      based on the fuzzy comprehensive evaluation       
      2014, 36(04): 685-689. doi:
      Abstract ( 122 )   PDF (613KB) ( 214 )     

      The basic principle of a health assessment system is expounded, the concept of membership and membership functions in the fuzzy set is introduced, and the principle and method of the fuzzy comprehensive evaluation system is proposed. MATLAB is used to construct evaluation matrix and algorithm programs, VB.net is used to design the friendly user interface, and Access is used to build knowledge base and expert advices. Besides, mixed programming technique is adopted to develop a health assessment system. Finally, the health assessment system is applied in hyperthyroidism risk assessment case.

      Adaptive fruit fly optimization algorithm#br# based on bacterial migration        
      LIU Chengzhong, HAN Junying
      2014, 36(04): 690-696. doi:
      Abstract ( 120 )   PDF (643KB) ( 196 )     

      Considering the premature convergence problem of Fruit Fly Optimization Algorithm (FOA), a new adaptive fruit fly optimization algorithm based on bacterial migration (AFOABM) is proposed. During the running time, according to the evolutionary stagnation step size, bacterial migration is adaptively introduced into FOA to improve its ability of jumping out of the local extreme; and according to the fitness values, each individual is assigned different adaptive migration probability in order to avoid the problem of possible solutions degradation resulting from migration. Experimental results show that the new algorithm has the advantages of better global searching ability, speeder convergence and more precise convergence.

      论文