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

Current Issue

    • 论文
      Program interaction on multicore:Theory and applications       
      DING Chen1,YUAN Liang2
      2014, 36(01): 1-5. doi:
      Abstract ( 267 )   PDF (524KB) ( 385 )     

      On modern multicore systems, the interaction between corun programs largely depends on cache sharing, and cache sharing depends on the locality, i.e. the active data usage, in corun programs. The paper introduces a newly developed locality theory based on a concept called the footprint. The theory shows the composability of footprint and the conversion between footprint and other locality metrics including the miss rate and reuse distance. The new theory enables accurate analysis of performance and dynamic cache allocation in the shared cache on multicore processors.

      Positive handling of low criticality tasks in mixed criticality scheduling 
      HUANG Lida1,LI Long1,LI Renfa1,XIE Yong2
      2014, 36(01): 6-11. doi:
      Abstract ( 144 )   PDF (685KB) ( 194 )     

      When the computation demand of (some of) the higher critical tasks increase, current mixedcriticality scheduler discards less critical tasks in order to guarantee that the higher critical tasks can occupy enough processor time for normal execution. Considering the data consistency and integrity and the corresponding performance loss, the above method for discarding the lower critical tasks arbitrarily is very passive. On the other hand, the real computing time of tasks cannot always reach the execution time under their worst case, and the scheduling has enough time slacks in multiprocessors platform. Hence lowcritical tasks should and could be handled in a more positive way. On homogenous multiprocessors platform, two kinds of queues are built up. One stores the reclaimed time slacks, while the other stores tasks including the ready tasks and the discarded low critical tasks. According to the characteristics of the ready tasks and the discarded low critical tasks, two kinds of scheduling are adopted: mixedcriticality local scheduling for the ready tasks, and the allocated time slacks for the discarded low critical tasks. Simulation experimental results show that, our method can guarantee the deadline of the higher critical tasks and increase acceptable ratio of tasks obviously.

       

      Research and implementation of memory latency measurement model based on variable stride    
      MAO Xilong,YANG An,L Gaofeng,LIN Qi,CHENG Hui
      2014, 36(01): 12-18. doi:
      Abstract ( 200 )   PDF (969KB) ( 231 )     

      Evaluating the memory access latency has important significance for optimizing application patterns and data placement. However, cache, multithreading, data prefetching and other techniques have serious interference with the accuracy of measurement of memory access latency. A measurement model based on variable strides is designed and implemented. According to userspecified strides, we create a sequence ring in a space, and circularly access this ring to obtain the average time as the memory access latency.  Finally, we measure an Intel common processor and FT processor’s memory latency by different data size, stride and thread, and make the data contrast with each other. This model can display the memory hierarchy and display memory latency precisely.

      Research on a QEMU based processor fault simulation and injection method      
      LI Yi1,XU Ping1,WAN Han2
      2014, 36(01): 19-27. doi:
      Abstract ( 329 )   PDF (1540KB) ( 435 )     

      Fault injection technique is an effective means for BIT software testing. Addressing to the problems encountered in the boardlevel BIT software testing, this paper proposes a fault simulation and injection method based on the open source simulator QEMU. This method models and simulates a variety of processor class fault mode after the expansion and development of QEMU, which joins faulty behavior simulation and fault injection modules to achieve a system level simulator BitVaSim. Firstly, processor function failure mode analysis is given, keyvalue pair of faults are extracted, and XML Schema is used to define and model faults. Secondly, a second development is conducted on QEMU codes so as to simulate the fault behavior of processors. Thirdly, fault injection interfaces are configured to implement failure mode matching and fault conditions triggering to inject faults on demand in simulator runtime. Experimental results demonstrate the accuracy and potential of BitVaSim in the evaluation of the dependability properties of the complex computer systems and the BIT system.

      Research on verification techniques of  high-performance ESCA coprocessor         
      DENG Chengnuo,WU Dan,HUANG Wei,DAI Kui,ZOU Xuecheng
      2014, 36(01): 28-33. doi:
      Abstract ( 135 )   PDF (883KB) ( 185 )     

      The increasing complexity of processor structure makes the efficient verification on the performance of processor become increasingly important and critical. Based on the highperformance ESCA coprocessor, the concrete implementation of border value verification, equivalence verification, and decision table verification methods are discussed, and also an integrated verification method is proposed by considering the basic characteristics of different functional modules of ESCA processor. The experimental result shows that the functional verification on ESCA processor by adopting the integrated verification method can not only ensure the generation of verification case set, but also achieve the 100% functional coverage by using less verification work, and reduce the verification time of ESCA processor efficiently thus improving the verification efficiency.

      The automatic generation technology for distributed simulation framework based on HLA    
      LIANG Yangang,GAO Xiaosheng,ZHANG Yi,TANG Guojin
      2014, 36(01): 34-38. doi:
      Abstract ( 156 )   PDF (727KB) ( 255 )     

      The computation model codes are strongly coupled with RTI services codes commonly in HLAbased simulation application programs, which makes the simulation system development more difficult. To solve the above problem, an uncoupling method base on shared memory and interruptcallback is studied, and a HLAbased simulation adapter is proposed to pack RTI services program. The technology for automatically generating simulation adapter is studied according to the functional requirements of RTI services program in federate members. To improve the program development efficiency, a software is developed to generate code and executable file of each federate adapter automatically. And then the distributed simulation framework can be established after the federate adapters is combined with RTI.

      Speaker recognition method based on quantum model distance      
      LUO Hui,PAN Ping,WANG Yang
      2014, 36(01): 39-43. doi:
      Abstract ( 153 )   PDF (1110KB) ( 233 )     

      Probability measure and distance measure are the most basic measures in pattern recognition, and vector quantization is a typical pattern recognition algorithm based on distance measure. According to the theory of quantum model distance measure, on the basis of vector quantization method, the paper explores a speaker recognition method based on quantum model distance. In order to deal with the timevarying property, the randomness and the highdimensional characteristics of speaker’s voice, we see a frame of speech signal as a quantum state, and measure model distance between quantum states according to quantum measurement theory. Simulation results in classical computer demonstrate that this method has slightly better in terms of operating time and visibly better in terms of recognition rate than vector quantization. It can provide a new way for the theoretical investigation on speaker recognition.

      An optimization method for virtual machine scheduling in the environment of applications hosting         
      JIANG Yong1,FAN Qingtao2,ZHAO Zhuofeng1,DING Weilong1
      2014, 36(01): 44-50. doi:
      Abstract ( 116 )   PDF (689KB) ( 221 )     

      In the environment of applications hosting, the virtual machines of most current IaaS (Infrastructure as a Service) are scheduled in an applicationindependent way and cannot be adjusted for different dynamic requirements, which leads to load skew among virtual machines and inefficient resource utilization for the hosted applications. To solve these problems, an optimal scheduling method for virtual machines is proposed. Through the analysis and the monitoring on the physical resources for the hosted applications, virtual machines can be scheduled periodically in a greedy fashion. In the experiments from our application hosting environment, the method can reduce the number of physical servers and improve the utilization on those physical servers.

      System design of WSN identifier resolution      
      LUO Zhiyong,WANG Qingqing,WANG Qing
      2014, 36(01): 51-56. doi:
      Abstract ( 120 )   PDF (1248KB) ( 217 )     

      With the continuous development of Wireless Sensor Network (WSN) technology and its expanding range of applications, the limitations of datacentered WSN are exposed. Therefore, in order to meet the requirements of application and management, it is particularly important to uniquely identify the node on a global scale by assigning an identifier for the sensor node. Firstly, the paper proposes the integrated architecture of the WSN identifier resolution, based on the implementation of hardware gateway and the design of system software, completes the mapping between the identifier of sensor node and the communication address of the sensor node in WSN, and then achieves tracing and management of the sensor node’s application. Finally, the system is validated to be effective with being applied in the smart home.

      Supporting mechanism for applicationassisted
      memory management of processes group       
      CHEN Baozi,WU Qingbo,TAN Yusong
      2014, 36(01): 57-62. doi:
      Abstract ( 125 )   PDF (1272KB) ( 214 )     

      An important way to aggregate resources is to consolidating applications of different users with different features.While user space application garbage collector aims at memory management of specific service, operating system knows better about how to allocate memory resource through the entire system. However, current Linux kernel mechanism can only notify application to do garbage collection when the memory usage reaches the upper limit of either global system. The paper designs and implements the supporting mechanism for collaborative memory management in Linux Kernel by Cgroup and Eventfd subsystem, which can further increase the system’s ability to support application’s own memory management policy. The experiments show that the new mechanism does not bring significant performance regression to the original operating system.

      Analysis and assessment of network
      security situation based on cloud model       
      ZHANG Yongjun1,2,TANG Jun2
      2014, 36(01): 63-67. doi:
      Abstract ( 134 )   PDF (483KB) ( 202 )     

      In order to analyze and evaluate the risk of network security more reasonably, a cloudmodel based method for network security analysis was proposed. The main ideas, key technical and implementation steps of the method were given. The standard clouds were generated using improved backward cloud algorithm with unknown certainty. The improved algorithm with smaller deviation was also proved. Finally, Kddcup99 data set was used to simulate. The experimental results show that the proposed method retains the uncertainty of risk analysis. It provides a strong reference to adopt appropriate preventive measures.

      Research on USB security technology based on virtual volume         
      CHEN Yongfu,ZHOU Feng,WANG Qifu,CHEN Liping
      2014, 36(01): 68-72. doi:
      Abstract ( 111 )   PDF (623KB) ( 273 )     

      In response to the requirement that some information can be public in the USB but some private information should be protected, the paper proposes a security USB disk system based on virtual volume encryption technology on the basis of the analysis and research of the virtual volume technology. This system divides an USB disk into a regular volume and a virtual safety volume. The data in safety volume is encrypted using AES encryption algorithm, and the use of regular volume and normal USB disk is exactly the same. In this way, the leaking and pervasion of confident information is prevented,and the convenience, flexibility characteristics of the USB disk can be maintained.

      A new multitemplate selection algorithm for
      keystroke dynamic identity authentication         
      LI Fuxiang1,HUO Jianqiu2,LIN Muqing1,TANG Jing1,ZHOU Fucai2
      2014, 36(01): 73-82. doi:
      Abstract ( 125 )   PDF (1567KB) ( 224 )     

      Sample collection and the establishment of the template are crucial for keystroke dynamic identity authentication systems. So far, the single template systems cannot decrease the false reject/accept rate(FRR/FAR) into the reasonable range. The multitemplate method is introduced into the keystroke authentication, and then a new multitemplate selection algorithm is proposed to balance the FRR and FAR after the most/least authentication probability algorithm is presented. Experiments are done to compare the proposed algorithm with the GMMS, and the factors that can influence the authentication results are analyzed. At last, the advantage of multitemplate system is also shown, compared with the singletemplate authentication systems.

      Application of extended D-S evidence theory in intrusion detection      
      CHEN Ye1,2,LIU Yuan1
      2014, 36(01): 83-87. doi:
      Abstract ( 123 )   PDF (510KB) ( 219 )     

      Network anomaly behavior detection is the important section of the intrusion detection, and it is hard for single security measure to attain good detection result. According to the evidence combination problem of highly conflict evidences, the paper applies an improved combination method based on weight to network anomaly behavior detection, and builds an intrusion detection model with multiple SVM classifiers. The method uses average evidences and weight value to distinguish the importance among all evidences, and thus it can deal with the conflicting evidences. Simulation results show that, compared with the traditional DS theory, the proposed model can effectively improve the integration efficiency, thereby improving detection performance.

      Design and implementation of authentication system
      based on improved visual cryptography on ARM platform        
      LU Zhejun1,WEN Shameng1,ZHANG Xiang2
      2014, 36(01): 88-93. doi:
      Abstract ( 131 )   PDF (824KB) ( 200 )     

      The identity authentication for legal users is very important in information security. Authentication method based on traditional static password faces many security risks. This system is based on the features and advantages of visual cryptography. By using an improved algorithm from the practical safety, we achieve a complete set of onetime pad password authentication scheme and make the process of authentication safer and more reliable. The system adopts twofactor authentication method. By combining the fingerprint method and the visual cryptography method, the security is further improved. Finally, we realize an integrated system on the experimenter baseboard of AM3517. Experiment shows that the system is easy in operation and low cost in use, safe in identity authentication and can be extended easily. It will have broad applications in the near future.

      Implementation of an improved authentication method on IC cardFU Qingqin1,ANG Zhengquan2,XU Pingjiang1
      2014, 36(01): 94-98. doi:
      Abstract ( 89 )   PDF (564KB) ( 181 )     

      Analyzes disadvantages of traditional authentication on IC card, and proposes an improved IC card authentication method based on userdefined algorithm environment so as to avoid attacks. Cards can be authenticated by various algorithms according to userdefined algorithm environment. The supported algorithms can be categorized into DES algorithms and 16 byte packet length algorithms. Users can use the algorithm specified by command to complete the smart card authentication, thus achieving certain permissions and completing the certification authority of the required operation. Meanwhile, the paper proposes another method to avoid attacks, which can guarantee the safety of data transport by limiting the use times of external authentication key even if the system is under attack.

      Dendritic cell algorithm with adjustable
      false positives and false negatives
      YUAN Song
      2014, 36(01): 99-104. doi:
      Abstract ( 128 )   PDF (713KB) ( 213 )     

      In order to overcome the blindness of evaluation of the context in the classical Dendritic Cell Algorithm (DCA), how the weight matrix of DCA influences the detection results is analyzed, and two kinds of DCAs are proposed, which can adjust the false positives and false negatives. The first one is the improved voting DCA. The Tendency Factor (TF) is involved in the Dendritic Cell (DC) state transition to assess the context fairly, and through the fine adjustment of the TF the false positives and false negatives of the detection results are controlled. The other one is the scoring DCA. In DC state transition phase, the evaluation of the context is ignored, instead, the antigen is directly given a score, then according to the distribution of average scores of antigens the anomaly threshold value can be adjusted to control the false positives and false negatives. Experiments show that the two algorithms can both effectively realize controlling the results. Comparatively, the scoring DCA can realize more intuitive control.

      Complexity evaluation method for range electromagnetic environment         
      PENG Wu1,HE Yigang1,2,FANG Gefeng3,FAN Xiaoteng3
      2014, 36(01): 105-110. doi:
      Abstract ( 123 )   PDF (615KB) ( 237 )     

      The electromagnetic environment has become increasingly complex. In order to evaluate the complexity properly, a new method based on Back Propagation (BP) neural network is proposed. Firstly, the paper establishes range electromagnetic environment model, analyses the electromagnetic environment complexity evaluation index, in order to provide theoretical basis for quantitative evaluation. Secondly, we analyze the selection method of key parameters of BP neural network, and an example is used to verify the neural network function. Finally, the new method and the traditional evaluation methods are compared. Results show that the new method outperforms the traditional methods and realizes qualitative and quantitative classification of the electromagnetic environment in a realtime, fast and self adaptive way. It expands the application range of the traditional methods, and has practical value in studying the complex electromagnetic environment in real battlefield.

      Closed circle DNA algorithm of traveling salesman problem        
      XU Jinglei,ZHAO Hongchao,LIU Xiyu
      2014, 36(01): 111-114. doi:
      Abstract ( 159 )   PDF (373KB) ( 198 )     

      Traveling Salesman Problem (TSP) is a hard NPcomplete problem, which has wide applications in the engineering. It is very difficult to solve TSP problem in polynomial time by using regular algorithms. DNA computing is a new computing pattern; its inherent huge parallel computing power makes it show a huge advantage in solving many NP problems. We try to solve the TSP problem by the improved closed circle model. Firstly, the closed circle model and its improved version are introduced. Secondly, a closed circle DNA algorithm based on the improved model is proposed, which can solve the TSP problem. And the procedure is described in detail. Finally, a small case is solved by the algorithm. Experimental results show that the proposed algorithm can solve the TSP problem effectively in a lower time complexity.

      QuickSort algorithm for singly linked list       
      BAI Yu,GUO Xiane
      2014, 36(01): 115-120. doi:
      Abstract ( 188 )   PDF (515KB) ( 209 )     

      Singly linked list is widely used for the dynamic storage structure, the current singly linked list sorting algorithms generally have low efficiency, and the QuickSort algorithm with the highest average efficiency is inapplicable to singly linked list. Based on the divide and conquer strategy and the recursive method, through relinking the nodes of singly linked list, the paper proposes the QuickSort algorithm for singly linked list. Its average time complexity is O(nlog2n), its auxiliary space complexity is O(0), and its average space complexity of recursion stack is O(log2n). Algorithm analysis and experimental testing are conducted. The results show that its efficiency improves greatly over the other singly linked list sorting algorithms and more traditional QuickSort algorithm based on linear array. We can conclude that the proposed algorithm solves the inefficient problem on singly linked list sorting.