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

Current Issue

    • 论文
      Contextbounded analysis of concurrent programs with Fork/Join parallelism
      QIAN Junyan1,2,JIA Shugui1,CAI Guoyong1,ZHAO Lingzhong1
      2013, 35(2): 1-6. doi:
      Abstract ( 186 )   PDF (542KB) ( 281 )     

      As multicore technique has been well developed, in order to utilize the computing power provided by multicore processor, concurrent programs bring in Fork/Join parallelism to decompose a task into finegrained subtasks. But interaction among concurrent threads results in insidious programming errors, it is necessary to analyze the correctness of these concurrent programs. Contextbounded analysis is an efficient method for finding insidious errors in concurrent programs by computing reachable states in a run within a bounded number of context switches, it determines whether an error state is reachable or not. In this paper, we perform reachablility analysis for concurrent programs with Fork/Join parallelism. The main idea is as follows: dynamic concurrent programs is modeled as an abstract modeldynamic concurrent pushdown system P, the abstract model can simulate the Fork/Join operation, then a concurrent pushdown system P can be abstracted from dynamic pushdown system that simulate the kbounded execution of P, and the kreachability problems of abstracted Pk can be solved by existing contextbounded reachability algorithm.


      Research on peertopeer information sharing system based on semantic overlay network
      ZHOU Guangxin1,TANG Jiuyang2,ZHANG Yang3
      2013, 35(2): 7-12. doi:
      Abstract ( 122 )   PDF (942KB) ( 191 )     

      Existing P2P information sharing systems can only support semanticsfree sharing of large granularity and inefficiently utilize their own resources, limiting their largescale, higherlevel applications. To address these challenges, the resources were clustered to form topics and the peers which include relevant topics were linked to form semantic overlay network. According to the principle, a fourlayer based architecture was proposed, which is made up of resource layer, information service center layer, semantic overlay network layer and applicationlayer. The corresponding analysis shows that the P2P information sharing system based on semantic overlay network effectively optimizes network performance and is scalable.

      An adaptive deadlockfree routing algorithm in the exchanged hypercube
      CAO Ruhui,LIANG Jiarong,WANG Xinyang,DOU Qiuli
      2013, 35(2): 13-17. doi:
      Abstract ( 163 )   PDF (869KB) ( 243 )     

      The exchanged hypercube is a novel interconnection network. Firstly, the method of graph theory is employed to analyze the topological property of the exchanged hypercube, the concept of similar subnet is defined and the result that the hypercube and the similar subnet are isomorphic is obtained. Secondly, an adaptive routing algorithm is proposed by using the technique of dividing a physical channel into two virtual channels. Finally, the theoretical analysis shows that the algorithm is deadlockfree.

      Design of network interface in Tianhe1A interconnection system
      LIU Lu,ZHANG Lei,XIE Min,WANG Yongqing
      2013, 35(2): 18-25. doi:
      Abstract ( 170 )   PDF (705KB) ( 232 )     

      NIC is the network interface chip of the high performance interconnection network THNet. Based on proprietary protocol, it supports nonconnection oriented, zerocopy, Userlevel communication RDMA mechanism which provides high system scalability on MPI implementation. The proposed handle method of descriptor queue which can be triggered by incoming control packet supports offload collective communication such as broadcast and barrier. In tests, the network interface using the NIC chip obtained the lowest oneway latency 1.57μs and 6.34GB/s peak bandwidth. NIC has been applied in Tianhe1A supercomputer which was ranked NO.1 in World’s TOP500 Supercomputers 2010.

      Implementation and optimization of shortrange molecular dynamics simulation on Hadoop
      JIAO Shanfei1,2,HE Chen2,DOU Yusheng2,TANG Hong1,2
      2013, 35(2): 26-31. doi:
      Abstract ( 138 )   PDF (962KB) ( 305 )     

      Running molecular dynamics simulation programs on Hadoop has many research meanings such as saving hardware and software investment and shortening simulation time. However, Hadoop is not good at implementing the quick iteration and communication between subtasks in these scientific computing applications. Base on atomdecomposition method, the paper proposes three solutions and implements the parallel algorithm of molecular dynamics simulation by using "HDFS read/write synchronization method". We tested it on a Hadoop cluster and analyzed expansibility, speedup ratio and costtime of various parts, and then obtained good results as high as 28x speedup in largescale system simulations. The experiment results show molecular dynamics simulation on Hadoop is more economical and practical.

       


      Research and implementation of power supply for highperformance computer system
      YAO Xinan1,2,SONG Fei2,HU Shiping2
      2013, 35(2): 32-37. doi:
      Abstract ( 129 )   PDF (1105KB) ( 231 )     

      To meet the power supply requirement of highperformance computer system, 12V DC bus distributed power system is adopted in this paper, and the power supply schemes of computing cabinet and motherboard are described. The power supply for processor in computing motherboard is analyzed in detail, and the parameters of loop gain, compensation network and output filter are presented. The application results show that this power supply can fully meet the requirement of highperformance computer system.

      Research on workflow time management of collaborative virtual prototype
      TIAN Fengchun
      2013, 35(2): 38-42. doi:
      Abstract ( 173 )   PDF (435KB) ( 217 )     

      Workflow management of collaborative virtual prototype supports and controls the dynamic and collaborative process of designs by many integrated productdeveloping teams distributed here and there, thus to achieve effective management of the collaborative design process, which plays an important role in improving work efficiency and quality of the virtual prototype. This paper mainly studies the workflow time management of the virtual prototype. By analyzing the routing structures, adopting workflow relaxation time distribution method, and adjusting some weak and demanding time constraints to their satisfactory state, more workflow instances can be enabled to meet deadlines, thus reducing the abnormal triggering frequency, saving the processing cost, and improving operation efficiency.

      A PMTU discovery mechanism based on routing protocol in IPv6 network
      CHENG Youqing,YU Shaohua
      2013, 35(2): 43-48. doi:
      Abstract ( 193 )   PDF (535KB) ( 147 )     

      This paper proposes an IPv6 PMTU discovery mechanism based on the routing protocol. By extending the routing protocol, the MTU value can be carried in the route information domain of the routing protocol and be transmitted in the IPv6 network. Therefore, a host sends only one packet to the first hop routers to discover the PMTU. The new mechanism was implemented and used on actual devices. Experimental results show that the mechanism is feasible, and brings great improvement on PMTU discovery time and connection delay.

      Study on the deployment of sink nodes in wireless sensor networks with random distribution
      LIU Qiang,MAO Yuming,LENG Supeng,LI Longjiang
      2013, 35(2): 49-55. doi:
      Abstract ( 153 )   PDF (797KB) ( 262 )     

      The reasonable deployment of the quantity and location of multisink in Wireless Sensor Networks (WSNs) is efficient to prolong the network lifetime and control the network cost. This paper establishes network lifetime and cost model based on the WSNs with random distribution. Furthermore, the expression of the optimal number of sink nodes is deduced by using the ratio of network lifetime to cost (RLC), which makes a tradeoff between the network lifetime and the deployment cost. A placement algorithm named RDF (Region Density First) is also proposed which makes us to determine the place of the sink nodes easily. These methods are validated by a simulation test and the results show that they are effective to prolong the network lifetime and decrease the deployment cost.

      A serverside software authorization model based on hardware feature and dynamic license
      GAO Bo1,LI Yan2
      2013, 35(2): 56-61. doi:
      Abstract ( 161 )   PDF (534KB) ( 276 )     

      Software copyright protection is an important part of the intellectual property protection system. Because the traditional serverside software license can not fully meet the requirements of the EULA issue, based on hardware characteristics and management of server architecture with independent authority, the paper proposes a distributed serverside software authorization model to support dynamic license. Through the "mandatory feature authentication and atomic authorization " mechanism, this model solves the issues such as the software copyright protection and the reauthentication of software migration.  It reaches the EULA requirements in terms of feasibility, safety and completeness.

      Signature generation model for botnet command and control channel
      WANG Hailong1,2,TANG Yong2,GONG Zhenghu2
      2013, 35(2): 62-67. doi:
      Abstract ( 167 )   PDF (729KB) ( 290 )     

      The malicious activities such as distributed denial of service attack, spam sending, and sensitive information theft launched by botnet have been the serious threats to Internet security. Command and control channel is the only way for botnet to manipulate these malicious activities. With the features of relatively fixed command format and string in the command and control channel, a novel signature generation model is proposed based on the existing techniques of signature generation, which focuses on the edge network’s suspect traffics. Experiment results show that the proposed model can generate accurate signatures conforming to the command format. Furthermore, the intrusion detection rules generated from these signatures can be used to identify the zombies effectively.

      A static analysis method of antiSQL injection attack
      QIN Guangzan,GUO Fan,XU Fang,YU Min
      2013, 35(2): 68-73. doi:
      Abstract ( 181 )   PDF (652KB) ( 221 )     

      This paper proposes a detection method of SQL injection attack based on static analysis. It statically analyzes the source pages of Web application, extracts taint to execution parameters’ constructed path and forms detection rules. The input parameters in rules are replaced by user input values during dynamic enforcement. By comparing the resulting SQL statements with the original SQL statements in the semantic and structural similarities and discrepancies, the method will determine whether SQL injection attack exists in the Web application. Experiments results show its effectiveness and feasibility since it has little effect on system performance after increasing the filtering module.

      Deriving algebraic specification of composite web service from BPMN model
      YU Bo
      2013, 35(2): 74-80. doi:
      Abstract ( 137 )   PDF (519KB) ( 181 )     

      Aiming at the problem of deriving specifications from composite Web service defined by BPEL when testing the service automatically based on specification, an approach is presented for the sake of deriving algebraic specification defined by algebraic specification language CASOCCWS of composite Web service defined by BPEL from BPMN model. Firstly, the rules for translating BPMN model into signature and translating BPMN structure into regular expressions are presented. Secondly, the algorithm for deriving the terms of axiom equation from the regular expression is proposed, and the heuristic rules for constructing axioms from the terms manually are proposed. At last, a prototype tool is implemented for deriving signature of composite web service from BPMN model. A case study shows that the presented approach is suitable to writing algebraic specification from the definition of BPEL service.

      Determination and conformation of full symmetric function sets in partial Kvalued logic
      GONG Zhiwei1,LIU Renren2
      2013, 35(2): 81-84. doi:
      Abstract ( 130 )   PDF (332KB) ( 156 )     

      According to the completeness theory in partial kvalued logic, firstly, the number of preserving binary full symmetric function sets is determined for general K, and the method of constructing these function sets is given out; secondly, the number of all full symmetric function sets is determined for general K, and the method of constructing these function sets is given out.

      A novel Lie group classifier and its application on handwritten digits
      WANG Xiaoqian,ZHANG Li,HE Shuping,YANG Jiwen,LI Fanzhang
      2013, 35(2): 85-90. doi:
      Abstract ( 133 )   PDF (693KB) ( 230 )     

      Lie group theory is the fundamental representation theory of the transformation space. Presently, there are only a few classifiers for Lie group matrix data and they do not work well for multiclass classification tasks. Taking handwritten digits as application background, the paper introduces the support vector machine (SVM) to handle Lie group matrix data. Since the Lie group data has their matrix form, we design a matrix Gaussian kernel function, making the SVM to handle Lie group matrix data. Experimental results show that the SVM performs well on the Lie group matrix data.

      An improved algorithm of local support vector machine
      ZHU Yingying1,YIN Chuanhuan1,MU Shaomin2
      2013, 35(2): 91-95. doi:
      Abstract ( 127 )   PDF (444KB) ( 157 )     

      Local support vector machine is a widely used classifier. It has been attracting more and more attention both on its theoretical research and practical applications. Nowadays, there exists a problem in many traditional local support vector machine algorithms: the imbalance of the number of the samples leads to the difficulty in improving the classification accuracy. In this paper, firstly, under the inspiration of weighted support vector machine, the algorithm named WFalkSVM is proposed, which uses weight in FalkSVM. Secondly, the experiments demonstrates the feasibility and effectiveness. At last, we conclude the weighted FalkSVM.

      New promoter recognition method based on manifold reconstruction
      ZHANG Youxin,WANG Lihong
      2013, 35(2): 96-102. doi:
      Abstract ( 140 )   PDF (634KB) ( 308 )     

      Promoter recognition is one of the important research directions in bioinformatics. Due to the characteristics of the promoters, there have been many kinds of identification algorithms based on the signal, the content and the CpG islands. Gene sequences are large scale nonlinear data with high dimensionality, so a new promoter recognition method based on manifold reconstruction is proposed, using nonlinear dimensionality reduction method to compress the data before promoter recognition. The experimental results show that this method can obain better results.

      An efficient algorithm for Chinese text clustering
      MA Jialin,LIU Jinling,YU Changhui
      2013, 35(2): 103-108. doi:
      Abstract ( 142 )   PDF (517KB) ( 254 )     

      Text clustering algorithm faces the extremely sparse highdimensional vector problem, the traditional dimension reduction methods statistically extract text features by assuming that the key words are independent. They often ignore the text semantic relations in the context, leading to considerable loss of text semantics. In this paper, using “HowNet”, by computing the similarity of the semantic class, a weighted value of the lexical chain is constructed. Depending on the size of the weights, the two lexical chains with two largest weights are chosen to be composed of representative text keyword sequence. Then, a text clustering algorithm based on the theme of lexical chain (TCABTLC) is proposed. It can solve the issue that the text vector with high dimension and sparse leads to the operating efficiency of the clustering algorithm, and obtain better clustering results. The experiments show that, to maintain good accuracy, the time efficiency of the clustering algorithm has been greatly improved.

      Friend recommendation algorithm based on association rules and tags
      HU Wenjiang,HU Dawei,GAO Yongbing,HAO Bin
      2013, 35(2): 109-113. doi:
      Abstract ( 164 )   PDF (612KB) ( 448 )     

      The paper proposes an improved friend recommendation algorithm in social networks. It combines the relationship recommendation among friends and the similarity recommendation of tags. Firstly, through the friend relationship, the TopN common friends among the target users are recommended. Secondly, the tag similarity among the target users and the recommended TopN friends is used to recommend the friends with the highest similarity score, and they are given corresponding weights and scored.  Finally, the TopN uses with the highest scores are recommended. The results show that the proposed improved algorithm is efficient and its precision and recall rates are better than the common friend recommendation algorithms.

      Research on qualitative relationship among temporal elements with temporal granularities constraints
      ZUO Yayao1,SHU Zhongmei2,TANG Yong3
      2013, 35(2): 114-120. doi:
      Abstract ( 120 )   PDF (963KB) ( 211 )     

      Qualitative relationship among temporal elements with the constraints of temporal granularity, is one of the most fundamental issues. The vector space is introduced to solve the complexity of the temporal relationship with the constraints of temporal granularity. Thus, the relationship between two temporal points can be converted to the operation in the vector space. Furthermore, the granularity scaling operators are used to analyze the relationship between different temporal elements, such as temporal point, temporal interval. The proposed method has a fundamental support to the temporal research and applications such as temporal database, temporal knowledge reasoning and temporal data mining.