Current Issue

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

• 论文

  A New Analysis Technique on the Internet Topology:The dMSeries Analysis Method

  YANG Guoqiang,DOU Wenhua

  2011, 33(3): 1-6. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 377 )   PDF (665KB) ( 395 )   　　

  It is an important task for the network topology research to analyze the properties of topologies and generate topologies that share the same properties with the original topologies. The dKseries analysis is an efficient technique to analyze the properties of the Internet topology. Increasing the values of the d capture progressively more properties of the original topology are at the cost of more complex states. The drawback of the dKseries is that the states increase fast when d increasess, and also the generation algorithm is too complicate. We present a new series analysis technique based on the neighbor graph distribution, called the dMseries analysis technique. The dMseries analysis technique has less states and easier algorithm generation compared with the dKseries analysis technique, so it is more practical when analyzing large scale networks like the Internet ASlevel topology.

  Differential Fault Analysis of Salsa20

  SHEN Yancheng1,XIE Duanqiang1,LI Chao1,2

  2011, 33(3): 7-12. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 381 )   PDF (397KB) ( 268 )   　　

  Salsa20 is one of the finalists of the eSTREAM project. Its main feature is using the ARX operations (i.e. addition, rotation, and xor on 32bit words) to achieve good confusion and diffusion effects. At present, many cryptanalytic results on it are statistical cryptanalysis and differential cryptanalysis. In this paper, we further investigate a differential fault analysis of Salsa20/256. By adopting a random fault word model, when inducing 96 faults,the 186 bit key can be recovered with a probability close to 1,accordingly the complexity of recovering the full key bits of Salsa20/256 can be reduced to 270, which implies that Salsa20/256 is sensitive to the differential fault analasis.

  Evaluating the Vital Network Nodes Based on Node Estranging

  LIU Jianqiang,LAN Julong,WU Jiangxing

  2011, 33(3): 13-17. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 368 )   PDF (488KB) ( 419 )   　　

  The Internet is essentially a heterogeneous network, and is robust and fragile .Evaluating the importance of the nodes is a critical foundation for the ability of antiattacks. The paper analyzes the shortcomings of the existing methods and proposes a method known as the node estranging method, through estranging the link weight .A new metric is proposed which reflects the node location information in the whole network and the local connectivity. And the computing complexity is reduced with the characteristics that the total of the varieties of network efficiency is equal to the sum of the varieties of path efficiency through the node. Simulation results show that the node estranging method can better evaluate the importance of the node with finer granularity to other methods.

  The Linear Complexity of a Family of p-ary d-form Sequences

  REN Bo,XIE Duanqiang

  2011, 33(3): 18-22. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 416 )   PDF (397KB) ( 306 )   　　

  Pseudorandom sequences are widely used in secret communications, spread spectrum communications and code division multiple address communications. They are usually used as the key sequences, spread spectrum sequences and address sequences. In the design theory of stream ciphers, complexity is introduced to evaluate the unpredictability of the cipher stream, that is, its level of safety. Linear complexity of sequences is an important measure for security in these applications, and this paper investigates the linear complexity of a family of p-ary d-form sequences under certain conditions, and the upper bound is given. There exists a family of p-ary d-form sequences whose linear complexity can reach the upper bound , which suggests that our upper bound is tight.

  An Advanced Congestion Control Algorithm G-Vega Based on Game Theory

  ZHANG Hua，LIAO Minghua

  2011, 33(3): 23-27. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 407 )   PDF (546KB) ( 344 )   　　

  With the development of the Internet, congestion has become more and more serious, and good congestion control algorithms are needed. Vegas is a good algorithm for its active avoidance of congestion, however, it can not work well with the mainstream algorithm Reno because its bandwidth can be stolen by Reno. This paper  analyzes the problem between Vegas and Reno, with a method of game theory, and proposes an advanced congestion control algorithm GVegas. According to the results of emulation on NS2, the algorithm is effective.

  An I/O Restricted Parallel Speedup Model  and the Scalable I/O Architecture

  LI Qiong,DU Yunfei,YANG Xuejun

  2011, 33(3): 28-33. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 385 )   PDF (577KB) ( 345 )   　　

  The effective solutions for the I/O bottleneck can be found from the following six levels, including applications, algorithms, languages and compilers, runtime libraries, operating systems, and I/O architecture. Among all the levels mentioned above, the I/O architecture is the most fundamental. In order to meet the I/O requirements and challenges, along with our research task of a high performance parallel computing system, this paper presents a theoretical study of I/O architectures, from which we can make it possible the high performance and scalability in terms of I/O architecture level. The current parallel I/O performance analysis lacks scientific theoretical models to support the I/O architecture design. The paper studies the impact of I/O workload on the scalability of parallel computing systems and proposes an I/O restricted parallel speedup model. Based on this model, which can be used to guide I/O architecture design, a scalable parallel I/O architecture for high performance computing is presented. Moreover, the paper analyzes several strategies for improving the system scalability, which serves as the basis for further study.

  Communication Performance Analysis of the NoCs in 2D and 3D Architectures

  QIAN Yue1,LU Zhonghai2,DOU Qiang1,DOU Wenhua1

  2011, 33(3): 34-40. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 613 )   PDF (1047KB) ( 246 )   　　

  Advanced integration technologies enable the construction of NetworkonChip (NoC) from two dimensions to three dimensions. Studies have shown that 3D NoCs can improve the average communication performance because of the possibility of using the additional dimension to shorten the communication distance. In this paper, we present a comparative analysis on the worstcase communication performance in the regular kary2mesh networks and their 3D forms. We show that, though 3D networks achieve better average latency, this may not be the case for the worstcase performance mainly due to the constraints on vertical channels. Our analysis is based on network calculus, which allows to calculate the theoretical delay bounds for constrained flows traversing network elements.

  Implementation and Optimization of  Stencil Applications on GPUs

  FANG Xudong,TANG Yuhua,WANG Guibin,TANG Tao

  2011, 33(3): 41-45. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 402 )   PDF (528KB) ( 343 )   　　

  With the fast development of GPUs, using them to accelerate scientific computing applications is becoming an inevitable trend. In this paper, we port two typical subroutines Rprj3 and Interp from Mgrid which contains rich stencil operations in SPEC2000 to run on an AMD GPU using Brook+. Using a thread granularity tuning mechanism provided by Brook+, we implement different ported program versions and analyze their performances. We also conclude how to utilize thread granularity tuning to optimize stencil program transplantation. Our experimental results show that under the largest problem size, Rprj3 obtains a speedup of 5.37 over its CPU version while Interp gains a speedup of 12.8 over its CPU version.

  FreeBSD Kernel Based Virtual Server Research and Implementation

  WANG Li,YANG Xuejun,ZHANG Wensong

  2011, 33(3): 46-50. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 336 )   PDF (569KB) ( 293 )   　　

  Server cluster is an efficient architecture for providing high performance networkservices, and the packet forwarding technique plays an important role in exploiting theperformance of server clusters. Efficient packet forwarding techniques incur low schedulingoverhead, and have high scalability. IP Tunneling/Direct Routing are novel and efficientpacket forwarding techniques. FreeBSD is an ideal network server operating system. However,the packet forwarding technique adopted in the current FreeBSD based server cluster schedulersare all network address translation, which has a limited scalability. This paper describes themotivation, design, and implementation of FVS (FreeBSD Virtual Server), which works inside theFreeBSD kernel and adopts the IP Tunneling/Direct Routing techniques. The discussion focuseson the system architecture and the key implementation techniques. We have implemented FVS on

  the FreeBSD5.3 release, and the experimental results show that the system incurs very low

  overload, thus achieves high scalability.

  FaultTolerance Techniques for OnBoard Parallel  Computer System Based on Distributed Architecture

  WANG Weicheng,LUO Yu

  2011, 33(3): 51-56. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 416 )   PDF (732KB) ( 409 )   　　

  Faulttolerant techniques can provide high reliability for onboard computers

  running in the outer space, the current multinode onboard systems are designed as a master

  slave structure, which focuses on the strategy of faulttolerance  in the master node and

  hereby contains a hidden danger. A parallel faulttolerant computer system with a distributed

  framework is proposed in this paper. Based on the framework, the computing nodes and fault

  tolerant units are designed and some novel faulttolerant strategies are introduced. Our work

  can serve as an important guideline for the development of the related projects.

  Texture_Based Volume Rendering Using Full Binary Tree Partitioning for Large Datasets

  SUN Anyu,JIANG Guiping

  2011, 33(3): 57-61. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 525 )   PDF (620KB) ( 363 )   　　

  In order to break through the limitation of GPU memory for the traditional

  texture_based volume rendering, an effective technique utilizing 3D texture partitioning based

  on full binary tree is presented for rendering largescale volume datasets interactively on

  general purpose GPU . Using the Fragment Programming capability of commodity graphics cards,

  the texture data is transferred to a 1D color lookup table and a working set of dynamic

  texture datasets equivalent to the volume dataset size. The working set manages the boundaries

  between blocks with the help of abstract partitioning and inherited attributes.The

  experimental results show that this method is efficient for rendering largescale volume

  datasets at an interactive rate on general purpose PCs．

  Design and Implementation of a Texture Image Retrieval System Based on Curvelets

  LI Jian,NIU Zhenshan

  2011, 33(3): 62-66. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 381 )   PDF (664KB) ( 367 )   　　

  In order to manage and query massive images, there is an urgent need for a content

  based image retrieval system with high retrieval rates. This paper proposes an image retrieval

  method based on curvelet transform and integrated Shannon entropy and frequency subband

  energy features. This method uses the Shannon entropy to preclassify data, adopts the energy

  subband features to measure image similarity, and joins the feedback information of

  searchers  to achieve accurate image retrieval. The retrieval experimental results conducted

  on the Brodatz texture image database show that the system has a high retrieval rate and a

  certain practical value.

  A Mixed Noise Linear Filtering Algorithm Based on the Neighborhood Structure Similarity

  LUO Xiaojun1,2,WANG Shixiu3,LI Bing4,XU Junling 2

  2011, 33(3): 67-72. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 458 )   PDF (617KB) ( 247 )   　　

  A mixed noise linear filtering algorithm based on the neighborhood structure

  information’s similarity (GLMF) is proposed, which is also a good improvement of the linear

  filter algorithm(LMF). This algorithm makes full use of the image of redundant information to

  restore the mixed noise pollution of pixels. In judging the similarity of neighborhood pixels,

  we consider the pixel values, and consider the similarity of a pixel neighborhood structure,

  while using the gradient of pixel values to express neighborhood information. Simulation

  experiments show, comparing with the existing similar filter, GLMF is better on both visual

  effect and PSNR. This algorithm is applicable to restore the Gaussian noise and random pulse

  noise mixed pollution digital images.

  A Detection Method of  Directional Texture Fabric Defects

  GUAN Shengqi

  2011, 33(3): 73-76. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 370 )   PDF (502KB) ( 458 )   　　

  By analyzing the characteristics of directional fabric textures, a new method for

  defect detection is presented. Firstly, the main lines of texture fabric texture are detected

  by the normal fabric texture Hough transform. Then, fabric texture images are decomposed by

  the directional wavelet. On this basis, the subwindows of characteristics are extracted from

  the detailed subimages. Finally, the fabric defects are identified by the BP neural network.

  The experimental results show that this method is effective.

  A Class of QuasiQuartic Trigonometric Polynomial Bézier Curves with a Shape Parameter

  YANG Lian,LI Juncheng

  2011, 33(3): 77-81. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 491 )   PDF (591KB) ( 308 )   　　

  A class of quasiquartic trigonometric polynomial Bézier curves  with a shape

  parameter is presented. The curve is controlled by five points, and it has a lot of similar

  characteristics with the traditional quartic Bézier curve, and its shape can be adjusted by a

  parameter, which makes the curve feature  more powerful expression ability. The shape

  parameter affects the property of geometry, the larger is the parameter, and the more of the

  curve approaches the control polygon, therefore, the trigonometric polynomial curve with the

  shape parameter can be close to the given control polygon than the quartic Bézier curve. The

  new curve can represent exactly the arc of circle, arc of ellipse, arc of parabola and other

  quadratic curves without using a rational form. For designing free curves, the G2 and C3

  continuity condition of twopiece curves are also discussed. The modeling examples illustrate

  that the new curve has a high application value for computer aided geometric design.

  Automatic Generation of Test Cases for Statechart Specification Based on the Conformance Testing Theory

  MIAO Chunyu1,CHEN Lina2,ZHAO Jianmin2

  2011, 33(3): 82-89. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 526 )   PDF (535KB) ( 287 )   　　

  This paper studies testing semantics and automatic test case generation for

  Statechart specification. Applying Tretmans’ approach to generate test cases for I/O automata

  from labeled transition systems, we provide a solid mathematical basis for conformance testing

  and automatic test case generation for Statechart specification. We introduce formal testing

  semantics of Statechart specification that go beyond the semantics presented for formal

  verification. These observable testing semantics can be used for general application, critical

  application and realtime application. We also propose a formal conformance testing relation

  based on presenting formal semantics and test hypothesis, and provide an algorithm which, for

  a Statechart specification, generates a test suites. For finiteruns semantics the algorithm

  can generate complete test suites, and for infiniteruns semantics only sound test suite can

  be generated.

  A Way of Defect Management Process Inprovement  and Practice Based on Matrix Measure

  CHENG Quanliang1，ZENG Yi1，GUO Yingjun1，LI Juan1，FENG Wei2

  2011, 33(3): 90-93. doi:

  Abstract ( 453 )   PDF (585KB) ( 352 )   　　

  This paper analyzes the type of software defects, defect injection, defect identification ,makes some improvement for the traditional defect management processes and adds defect removal effectiveness of the metrics, and then puts forward a practical software defect management process, establishes a software defect measurement model based on software lifecycle,and gives the corresponding matrix measurement methods. Finally, two software projects in the various stages of the defects measured by this defect management metric process in one company.Through this practice ,it proves that this defect management processes and the measurement method can provide the data basis for the development team to set goals and plans, for process control, process evaluation, continuous improvement of the management to provide a quantitative basis,indicating that the defect management processes and the measurement method of the model are effective.

  A Static Analyzer for Numerical Programs in C and Fortran

  HOU Suning,CHEN Liqian,WANG Zhaofei,WANG Ji

  2011, 33(3): 94-102. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 523 )   PDF (735KB) ( 276 )   　　

  The validation of program correctness is a challenge problem in computer science. The theory of abstract interpretation provides a general framework for static analysis which can deduce programs’ dynamic property automatically. A value range analysis based on abstract interpretation can give the invariant relationship of variables at every program point, which is very important to compilation optimization and error examination. We propose an interprocedural framework that analyses the value range information of numerical programs, which can process C and Fortran programs. The C or Fortran source program is first preprocessed to an uniform representation, and then we draw the semantic equation which is equivalent to the source semantics. Finally, the iterative computation is done on this syntax equation to get the program invariant. Besides, we model some complex syntax structures such as array. The experiment indicates that our framework is very extensive and precise, and can process most problems brought by the usage of array.

  Research of  Handling the Parameter Constraints in Pairwise Testing

  GAO Jianhua,LIU Hui

  2011, 33(3): 103-107. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 396 )   PDF (441KB) ( 276 )   　　

  This paper proposes a way of parameter constraint classification and defines them.It summarizes the changes of test set size when there is 2ways constraints and concludes that although the number of pairs are reduced, the size of the  test set is not always reduced in pairwise testing with 2ways constraints. It proposes the least size of the test set, when there is 2ways constraints,and proves the conclusion. Finally, it proposes the HPC_IPO algorithm which can handle constraints effectively.

  Detection Techniques of Program Invariants

  LIU Shukun 1,YANG Xiaohua2

  2011, 33(3): 108-112. doi: 10.3969/j.issn.1007130X.2011.

  Abstract ( 410 )   PDF (468KB) ( 564 )   　　

  Design by contract is an important technology which can be used to improve software quality. Contract can express the basic properties which are  invisible to the users and the conditions used to guarantee the correct results of programs. Program invariant is a kind of contract including class invariants, preconditions invariants and postconditions invariants. The program invariants can be applied to the range of program verification and software test. In this paper, the current mainstream research technology of detecting program invariants is described and the main process and key methods of discovering the invariants are shown.