Current Issue

• 2013, No. 3　Published:25 March 2013 Last issue    Next issue
  Columns in this issue: 论文

• 论文

  Universal homogeneous spiking neural P systems without delays

  PENG Xianwu1,2,FAN Xiaoping1,3,LIU Jianxun2,WEN Hong1,2

  2013, 35(3): 1-7. doi:

  Abstract ( 144 )   PDF (463KB) ( 266 )   　　

  Spiking neural P systems are a new class of bioinspired computing devices incorporating the ideas of spiking neural networks into P systems, and have powerful computational capability. Homogeneous spiking neural P systems are a restricted variant of spiking neural P systems, where each neuron has the same set of rules. The universality of two kinds of homogeneous spiking neural P systems without delays is investigated, including homogeneous spiking neural P systems with weighted synapses and without weight on synapses. We proved that these two kinds of homogeneous spiking neural P systems are universal in both the generating mode and the accepting mode. This paper provides an answer to an open issue about whether there is a universal homogeneous spiking neural P system without delays proposed by Zeng Xiangxiang,Zhang Xingyi and Pan Linqiang.

  Endpoint dynamic faulttolerant
  approach in sourcerouting fat trees

  CAO Jijun,LIU Lu,WANG Yongqing

  2013, 35(3): 8-14. doi:

  Abstract ( 152 )   PDF (992KB) ( 275 )   　　

  Fault tolerant routing is an important approach to improve the usability of interconnection networks.Aiming at the sourcerouting fat tree,this paper proposes an endpoint dynamic fault tolerant routing approach.In the approach,a three level hierarchy is adopted for the routing storage,in which the RT (Routing Table) is stored in NIC (Network Interface Card) of the endpoint,the ERT (Extended RT) is stored in the memory of the endpoint, and the SERT (System ERT) is stored in the hard disk of the management server. Meanwhile, the path management process running in the endpoint is responsible for managing the state of multipath maintained in the ERT of this endpoint,and replaces the current failed path with a chosen available path when a link fault occurs in the network.The primary analysis results show that our proposed fault tolerant routing method has a low implementation cost and high scalability and cannot lead to deadlock problems.

  VLSI systemlevel soft error reliability evaluation:A survey

  ZHU Dan,LI Tun,LI Sikun

  2013, 35(3): 15-24. doi:

  Abstract ( 136 )   PDF (575KB) ( 215 )   　　

  The soft error induced by various environment problems,such as radiation and random noise,has emerged as a critical challenge in VLSI designs.Since most of the methods for soft error protection are based on redundancy,the cost of full soft error protection is unacceptable.Thus,the designs can only be selectively protected.The soft error reliability evaluation is the key of selective protection.In order to make costeffective tradeoff between reliability and various overhead from hardening,the soft error reliability evaluation at system level is crucial.The paper firstly classifies the existing systemlevel soft error reliability evaluation approaches by their core techniques;secondly discusses their development and features;finally proposes their remained difficult issues and challenges and predicts their future trends.

  Performance evaluation methodology for
  massively parallel computer systems

  LIU Jie，CHI Lihua，JIANG Jie，XU Han，YAN Yihui,HU Qingfeng

  2013, 35(3): 25-30. doi:

  Abstract ( 145 )   PDF (635KB) ( 242 )   　　

  The complexity of modern massively parallel computer systems requires sophisticated method to facilitate the evaluation of system performance, and it is difficult to measure all the characteristics of systems using a single metric. The concept of applicability is given from the demand of users for supercomputers. Based on the applicability concept, we present a performance evaluation methodology for massively parallel computer systems. The methodology, including total applicability, subentry applicability, the concepts of subentry, metrics and benchmarks, can avoid the personal factors and obtains the impersonality results for systems performance. After collecting data using performance analysis tools, the data can be used to get the subentry applicability. Then the total applicability can be calculated by the weight equation. Based on the total applicability, one can evaluate whether the massively parallel computer systems satisfy the demand of user or not.

  Largescale electromagnetic parallel computing
  software based on parallel MLFMA

  DONG Jian,PANG Chen,WEN Shameng,ZHU Jianqing

  2013, 35(3): 31-37. doi:

  Abstract ( 188 )   PDF (1482KB) ( 254 )   　　

  In this paper,a largescale electromagnetic parallel computing software package based on multilevel fast multipole algorithm (MLFMA) is introduced.This software package includes a complete pre/post process module and a parallel electromagnetic computing module,which can be used to finish objects modeling, mesh generation,mesh preprocess,parallel computing,2D/3D result viewing on largescale parallel computing systems.The accuracy and efficiency of this software package are proved on the TianHe supercomputer.

  Research of the Astarbased workflow scheduling
  advanced algorithm for distributed computing

  LI Kun1，JIANG Lili2

  2013, 35(3): 38-42. doi:

  Abstract ( 132 )   PDF (870KB) ( 237 )   　　

  The workflow scheduling problem in heterogeneous distributed systems is hard to solve due to both the intermediate data transfer time and the computation time for each task being considered.The paper has a study of the dataaware workflow scheduling algorithm based on Astar,to achieve optimal scheduling which is through the overlapping of task execution and data deployment on computing sites.The simulation results show that, in most cases,the improved algorithm is superior to the existing work in performance and efficiency,and significantly reduces the turnaround time.In addition,we also extend the algorithm to solve the process coscheduling problem.

  Parallel electromagnetic calculation solver
  based on Tianhe1A supercomputer

  LIU Liguo，MO Jinjun,YUAN Naichang

  2013, 35(3): 43-47. doi:

  Abstract ( 151 )   PDF (974KB) ( 939 )   　　

  The paper presents a parallel electromagnetic solver in Tianhe1A supercomputer. The solver adopts the parallel FDTD algorithm, which is a powerful tool for solving large electrical objects for its parallel nature. As one of the fastest supercomputers in the world, Tianhe1A can provide very high computational capability. An efficient parallel electromagnetic solver running on Tianhe1A is urgent for actual applications. We have developed a parallel Finite Difference Time Domain (FDTD) algorithm with high performance based on the Tianhe1A supercomputer. Our goal is to effectively solve the problems of complex structures and large electrical object. By using parallel computation, we are able to complete a calculation on 7200 processors in less than 48 hours, where a serial version would have taken over several decades. Accurateness, scalability and efficiency of the parallel simulator is examined in this paper.

  Research of cloud computing resource scheduling model

  LIU Sai,LI Xurong,WAN Linrui,CHEN Tao

  2013, 35(3): 48-51. doi:

  Abstract ( 128 )   PDF (532KB) ( 278 )   　　

  In the cloud computing environment, resource scheduling management is one of the key technologies. This paper describes a cloud computing resource scheduling model and explains the relationship between entities in the resource scheduling process of cloud computing and cloud computing environments. According to the physical server resource properties, a scheduling model that comprehensively considers the cloud computing resources loads is established, and the artificial and automatic virtual machine migration technology is used to balance the load of the physical servers in the cloud computing environment. The experimental results show that this resource scheduling model not only supports balancing the resource load but also improves the virtualization degree and flexibility degree of the resource pool. Finally, the future research directions are discussed.

  MapReduce oriented selfadaptive delay scheduling algorithm

  NING Wenyu,WU Qingbo,TAN Yusong

  2013, 35(3): 52-57. doi:

  Abstract ( 115 )   PDF (663KB) ( 234 )   　　

  MapReduce has become a mainstream mass data processing mode,As its crucial part, the scheduler has received extensive concerns of the industry.But existing scheduling algorithms cannothavea good balance between fairness and data locality.Therefore,in this paper, a selfadaptive delay scheduling algorithm is proposed in order to make up the shortage of statically setting waiting time in configuration file.It dynamically adjust waiting time according to the speed of free nodes,so it can reduce job response time.Based on the algorithm,a prototype is developed and experiments testing the algorithm's performance are carried out.The results show that the selfadaptive delay schedulingalgorithm outperforms previous delay scheduling ones in term of the job response time about 5%~8%.

  An efficient  twoparty secure computation
  protocol under the malicious model  

  YANG Yong

  2013, 35(3): 58-65. doi:

  Abstract ( 168 )   PDF (490KB) ( 270 )   　　

  For the sake of improving the efficiency of the secure twoparty computation protocol under the malicious model, this protocol uses the simple permutation projection. Therefore, it can not only check the input consistency of the malicious party , but also avoid the complexity of full connectivity when checking the input consistency. Compared with the classic protocol, it improves the efficiency by nearly 50%. Besides, in order to better guarantee the protocol security, under the ideal/real model, based on simulation of  OT12  protocol and the knowledge proof, the paper uses the rollback method to give a rigid formal proof and failure proof of the protocol.

  Epidemic routing with backoff mechanism  

  SUN Jianzhi,ZHANG Yingxin,CHEN Dan,HAN Zhongming

  2013, 35(3): 66-71. doi:

  Abstract ( 127 )   PDF (856KB) ( 230 )   　　

  In some scenarios, Epidemic algorithm has high delivery ratio, small delivery delay, but poor adaptabilityd. Moreover, the performance of the algorithm will significantly degrade in other scenarios. On the basis of analysis of the factors affecting the algorithm performance, CrowdingOut effect is considered as the main reason leading to negative performance. In this paper, the performance of Epidemic algorithm with immune mechanism is analyzed and some defects of the immune mechanism are indicated. Therefore, an improved algorithm is formulated with a kind of Backoff mechanism, so that the node will no longer receive packets from meeting nodes when its buffer is close to saturation. The promising results on the ONE simulation platform show that the proposed algorithm can effectively suppress CrowdingOut effect and greatly improve the delivery ratio and  reduce the routing overhead to some extend under various scenarios.  

  HS-streamCube:Realtime multidimensional
  analysis system on network security event stream  

  GAN Liang1,2,LI Runheng1,JIA Yan1,LIU Jian3

  2013, 35(3): 72-79. doi:

  Abstract ( 130 )   PDF (1172KB) ( 206 )   　　

  In the applications of largescale network security monitoring,data stream of security events is analysised realtimely to acquire the characteristic of current security in the network and to assess dynamically the current security situation with Stream OLAP by building Stream Cube.Because of the limited memory capacity, Stream Cube only concerned about the current data within the time window,but expired data is stored approximately or simply discarded,so it do not support the query with time beyond the scope of current time window.We propose a realtime StreamCubebased multidimensional and multilevel analysis framework on security event stream, Hybrid StorageStreamCube,which is implemented by a twotier (memory and disk) storage model.On the basis of characteristics of data stream,we focus on the modeling,building,storing and querying of HSStreamCube within the twotier storage model.Efficient experiments verify the availability and efficiency of the system.   

  Design of AES Core Based on FPGA  

  HAN Jinsheng1,LIN Jiajun1,ZHOU Wenjin2,YE Jianwu3

  2013, 35(3): 80-84. doi:

  Abstract ( 113 )   PDF (666KB) ( 207 )   　　

  AES has its remarkable advantages in security, high performance, high efficiency, ease of use, flexibility, etc. As the demand of computation performance increases, researches on AES's FPGA implementation are paid more attention to. Based on the analysis of AES algorithm, a FPGA based fully pipelined AES model is proposed. In this model, the structure of the ae data block and wheel computation are modified in order to improve the performance of the AES hardcore. The implementation results on Altera EP4CE40F23C6 FPGA show that the proposed AES hardcore can run at 310 MHz with the computation throughput of 9.92 Gbps at the cost of 6413 LE and 80 M9K.       

  Research on trust mechanism of BitTorrent model   

  ZHANG Xinyou,FAN Huibo

  2013, 35(3): 85-91. doi:

  Abstract ( 107 )   PDF (649KB) ( 187 )   　　

  With the wide application of the BitTorrent download model,the problems of lacking peers control measures and existing fake resources arise seriously.The characteristics,security problems and existing security mechanisms of BitTorrent model are analysed.Combining with the idea about the trust model in P2P technology,this paper improve the security mechanism of BitTorrent,optimize the file splitting and integrating algorithms.The simulation results show that the proposed model can find fake resources rapidly and increase the probability of downloading files successfully.

  Provably secure identitybased threshold
  ring signature in the standard model  

  SUN Hua1,ZHONG Luo2,WANG Aimin1

  2013, 35(3): 92-96. doi:

  Abstract ( 133 )   PDF (415KB) ( 224 )   　　

  The (t,n) threshold ring signature can be generated by any t entities of n entities group on behalf of the whole group, while the actual signers remain anonymous. At present, the security of the identity based threshold ring signature schemes are almost proven under the random oracle model, while it may be not secure for those schemes under the random oracle model. There, it is meaningful to design threshold ring signature scheme in the standard model. This paper proposes a secure and efficient identitybased threshold ring signature scheme by using bilinear pairing technique, and proves that this scheme satisfies the existential unforgeability against adaptive chosen message and identity attacks in terms of the hardness of CDH problem in the standard model. Meanwhile, it is proved that the scheme satisfies the unconditional signer ambiguity.   

  Matrixbased approach for calculating knowledge
  granulation and its application in attribute reduction    

  WANG Lei,YE Jun

  2013, 35(3): 97-102. doi:

  Abstract ( 131 )   PDF (424KB) ( 255 )   　　

  In this paper, a novel computational approach for knowledge granulation and its meaning are investigated from a new point of view of matrix. Firstly, two computational approaches for knowledge granulation, discernibility degree and attribute importance are proposed based on the equivalent relation matrix. Secondly, the relationship between the equivalent relation matrix and the knowledge granulation is analyzed, and hence the relevance between the equivalent relation matrix and the uncertainty of an information system is revealed. Furthermore, the meaning and the inherent essence of the matrix expression of knowledge granulation are analyzed. Finally, the matrixbased computational method for attribute importance is applied to calculate the core and the minimum reduction of attribute combined with the update of equivalent relation matrix while one attribute added to or removed from the attribute set, the numerical examples demonstrates the effectiveness of matrixbased computational method of attribute importance.  

  An ant colony algorithm based on
  penalty function and new pheromone updating  

  ZHAO Wei1,CAI Xingsheng1,2,QU Huiyan1

  2013, 35(3): 103-107. doi:

  Abstract ( 142 )   PDF (624KB) ( 218 )   　　

  An fast ant colony algorithm solving traveling salesman problem is presented. Firstly, this paper gives a new pheromone updating model. It reduces the complexity of the search process, improves the accuracy of the route searching. Secondly, by setting penalty function, to exclude irrelevant path so that the narrow scope of the search process. Experiments show that, this algorithm can get better optimal solution, and improve the convergence speed significantly.   

  Minor component analysis neural network method  

  KONG Xiangyu,HU Changhua,HU Youtao,HE Chuan,WANG Zhaoqiang

  2013, 35(3): 108-114. doi:

  Abstract ( 160 )   PDF (451KB) ( 211 )   　　

  The minor component analysis neural network is a method for adaptively extract the minor component of the autocorrelation matrix of the input data,which has been researched in the last decade.This paper analyzes and summarizes the minor component analysis learning algorithm as general divergence,sudden divergence,dynamic divergence,numerical divergence and selfstabilizing property,and points out the existing problems and the future development trend of this fields,and this work lays sound theoretical foundations for the neural MCA theory.

  Research on domain ontology semiautomatic
  construction based on FCA and Jena  

  TIAN Wei1，GUO Jianyi1,2，YU Zhengtao1,2，XIAN Yantuan1,2，WANG Yanbing1

  2013, 35(3): 115-120. doi:

  Abstract ( 129 )   PDF (797KB) ( 224 )   　　

  To aim at solving the difficult problems of discovering the implicit knowledge and coding for ontology inefficiently in ontology construction, this paper proposes a semiautomatic approach to construct the domain ontology based on FCA and Jena. At first, formal context is built up by clustering the instance sets and the attribute sets of the domain concept repeatedly and then the concept lattice is built up. Secondly, the domain ontology needs to be visualized. Furthermore, the potential concepts and relations among concepts are found to form the ontology trunk. At last, the ontology trunk is enriched by adding the corresponding attribute values. After that, the OWL is selected to code and formalize the above original ontology based on Jena in order to complete the construction of domain ontology. Taking the Yunnan tourism domain as background, the tourism ontology prototype system is constructed, which demonstrates the validity of the domain ontology semiautomatic construction approach proposed in this paper, and some evaluations on field portability, ontology building efficiency and degree of automation have good results. Compared with artificial construct results, it shows the construction validity.

  Schedulability validation of embedded
  software model based on time automaton   

  BAI Haiyang,LI Jing,ZHAO Na

  2013, 35(3): 121-127. doi:

  Abstract ( 113 )   PDF (746KB) ( 256 )   　　

  The Architecture Analysis and Design Language (AADL) is a popular language for embedded system development in industrial control, automotive, aerospace and other mission critical and realtime fields. In order to validate the schedulability of the established model at early stage, we propose a new method which can translate the AADL model into time automaton model. The scheduling strategy of the AADL model is mapped to the template of time automaton model, and we define the specific rules of translating the AADL execution model and behavior model. The generated model can be simulated and checked through the tool UPPAAL, to analyze the schedulability of the original model. Finally, the project describes the whole process of AADL modeling, model transformation and model verification, and proves the validation of the method.