A formal application model for code and test generation

The considered model is used in manual development of application specifications and is based on the Letichevsky theory of basic protocols and a respective symbolic verification tools. Means to limit the behavioral characteristics of the model still matching the source requirements are discussed. If the model is verified successfully, the executable code of the application and the respective test code are generated from the model. The technique of using the developed model is described.     

A new corner detection algorithm for chain code representation

A new algorithm is proposed to detect a corner of a thinned binary image that is represented by an eight-connected contour chain code. The algorithm is based on chain-coded image, deriving the slope between each code, analyze the series of chain code, and finally decide the existence of corner at the current pixel location. The work assumes that the pre-processing processes on the image, namely thinning and digitization, have been done. Two weighted parameters identified as significant factors in determining the accuracy of the corner detection algorithm are discussed. The parameters are the length of segment and threshold value. Computational phases to derive values of rows and columns given a series of chain code are also given in detail. The algorithm can be used to interpret line drawing that represents three-dimensional object.     

A simple algorithm for structured-grid generation with application to efficient Navier-Stokes computation

A grid generation procedure using a simple algorithm is presented. The present method is essentially based on the electro-static theory. By distributing electric charges at the boundary points, an electro-static vector field is produced inside the region between the inner and outer boundaries. The resulting electric force lines, which all emanate from grid points on the body, can be utilized as one family of grid lines. The other family of grid lines is easily constructed by plotting points at regular intervals along the electric force lines. The electric charge distribution is uniquely determined by an appropriate boundary condition, as long as the total amount of charges on each closed boundary is constant. The actual Navier-Stokes simulation using the block-structured grid generated by the present method was also carried out for a complex space vehicle configuration.     

Matrix generation algorithm for an M-stage closed tandem queue with blocking

This paper contains a discussion concerning state transition rate matrix generation for a closed tandem queue with a fixed number of pallets and with blocking due to there being intermediate queue between any pair of machines. The method is based on the blocal balance concept. 'with this matrix, one can obtain the limiting probability of each system state. Once the limiting probabilities are found, machine utilizations and average queue lengths are readily computed. The computational algorithm for a closed tandem queue with blocking is provided and the results are compared to the average values of a computer simulation model.     

A new unsupervised cube-based algorithm for iso-surface generation

This paper introduces a new algorithm which automatically produces polygonal representations of 3D structures within a volume data set built from a stack of parallel cross-sections. Several methods of 3D surface reconstruction have already been proposed ranging from heuristic approaches for constructing 3D surfaces from 2D contours to the Marching Cubes (MC) approach where the different configurations are checked systematically. Instead, we define a cube-to-cube connection based upon geometrical closeness provided by convex hulls computation. We further evaluate the precision of 3D models reconstructed from synthetic and real data obtained in confocal microscopy and compare it with the conventional MC algorithm. We also discuss improvements that allow to reduce the number of generated surface patches and the ability to be used in 3D quantitative tasks.     

A parallel sorting algorithm for a novel model of computation

The computational complexity of a parallel algorithm depends critically on the model of computation. We describe a simple and elegant rule-based model of computation in which processors apply rules asynchronously to pairs of objects from a global object space. Application of a rule to a pair of objects results in the creation of a new object if the objects satisfy the guard of the rule. The model can be efficiently implemented as a novel MIMD array processor architecture, the Intersecting Broadcast Machine. For this model of computation, we describe an efficient parallel sorting algorithm based on mergesort. The computational complexity of the sorting algorithm isO(nlog² n), comparable to that for specialized sorting networks and an improvement on theO(n ^1.5) complexity of conventional mesh-connected array processors.     

一种基于图元方向变形的人体模型生成新算法

提出了一种基于图元方向变形的人体模型生成算法。通过图元截线点以及图元方向变形的方式获得了不同部位的人体图元,从而很好地避免了模拟函数所产生的误差。同时,利用图元网格生成与平滑连接相结合的方式生成了不同人体体型。该方法既可以使生成的人体图元被重复使用,不同类型图元的组合又可以使模型的生成更有针对性。实验结果表明,与传统方法相比,本方法生成的模型更加逼真,与模板模型差异更小。另外,由于图元模型的可重用性,也可进一步提高模型生成的效率。     

A system for a new two-dimensional code: Secure 2D code

A new 2D code called Secure 2D code is designed in this paper, both encoder and decoder are also proposed. Secure 2D code can store any kind of data and provides high security. With regard to security, the input data is divided into two parts: general and secret. The general data is transformed into a 2D code pattern, then secret data is hidden in the 2D code pattern. To raise the reading speed and allow various reading environments, some features are added around the 2D code pattern boundary. As to the reliability, RS code is adopted to treat damaged patterns. Received: 9 September 1997 / Accepted: 2 March 1998     

A new algorithm for encoding and decoding the Hilbert order

An iterative algorithm is described, based on the replication process of the Hilbert matrix, for encoding and decoding the Hilbert order. The time complexity of the proposed algorithm is smaller than those published previously, and the space complexity is bounded by a constant. Moreover, the new algorithm has a wider applicability when compared with existing algorithms for certain machine‐word lengths. A new variant of the Hilbert curve is suggested to overcome a shortcoming of the traditional Hilbert curve for the mapping problem. The proposed coding algorithms for the traditional Hilbert curve are also applicable to the new variant without increasing the time and space complexities. Copyright © 2006 John Wiley & Sons, Ltd.     

MPI通信代码自动生成算法

对于高性能并行计算机而言，如何由给出的计算、数据划分信息及精确数组数据流分析信息自动生成并行化代码是实现串行程序并行化的一个重要问题。根据Saman P.Amarasinghe和Lam的定理，实现了一种并行化识别工具中MPI（Message Passing Interface）并行化代码自动生成技术的算法，并对该算法的性能进行分析。     

一种基于演化计算的在线手写签名验证算法实现

提出了基于演化计算的在线手写签名验证算法。该算法将参考签名分割成曲线段,以一定长度的搜索窗在测试签名曲线上进行动态搜索,实现与参考签名曲线段自适应的动态分割与匹配。在算法中引进了演化计算中的分级和加速技术,使算法的搜索速度和匹配效果有了一定程度的提高。实验结果表明了该算法的有效性。     

基于云模型的被动队列管理算法

为了解决因拥塞而带来的网络性能问题,基于“弃头”方式提出了一种新的被动队列管理算法DFCM。该算法首先结合业务流队长和到达速率给出了丢包策略和丢包概率,同时利用云模型对实际队长进行求解;最后,通过利用NS2和Matlab进行仿真实验,深入分析了影响算法性能的关键因素。与“弃尾”(Drop Tail)和DFSQ算法相比,DFCM在瞬时队长方差、有效传输数据包等方面显示了较好的适应性。     

A space-efficient code generation scheme for BCPL

This paper presents a methodology in generating space-efficient code for BCPL and BCPL-like programming languages. An intermediate language called ICE was designed which, while preserving those program features salient to translation, also tries to minimize the number of instructions generated. This internal representation is then realized as an actual machine. The encoding scheme (called ES0) is based on usage frequencies of instructions and other real world constraints on machines such as word size and addressing space. Using a large sample of BCPL programs, it is shown that BCODE, which is a realization of OCODE (the intermediate language currently used for BCPL program translation), takes up an average of 32 per cent more space as compared to ICE/ES0.     

A code generation interface for ANSI C

1cc is a retargetable, production compiler for ANSI C; it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000, and some versions have been in use for over a year and a half. It is smaller and faster than generally available alternatives, and its local code is comparable. This paper describes the interface between the target-independent front end and the target-dependent back ends. The interface consists of shared data structures, a few functions, and a dag language. While this approach couples the front and back ends tightly, it results in efficient, compact compilers. The interface is illustrated by detailing a code generator that emits naive VAX code.     

A toolkit for nonlinear model predictive control using gradient projection and code generation

Nonlinear model predictive control (NMPC) is a control strategy based on finding an optimal control trajectory that minimizes a given objective function. The optimization is recalculated at each control cycle and only the first control values are actually used. The dynamics of the system can be nonlinear and there can be constraints on states and controls. A new toolkit called VIATOC has been developed that can be used to automatically generate the code needed to implement NMPC. The generated code is self-contained ANSI C and the compiled program has a small footprint. In VIATOC, the gradient projection method is used to solve the nonlinear optimization problem. Barzilai–Borwein type step length selection for the gradient method has also been implemented. The performance of the controllers generated with the toolkit is compared with those solved with the ACADO toolkit and HQP. The performance of the optimization is compared with two different test cases with different numbers of controls and states. The first one is based on a model of a pendulum hanging freely on a movable platform. The second one is a more complex model of a chain of three masses connected by springs. Seven different prediction horizons between 10 and 100 steps are used. When the time to achieve a near optimum solution is measured, VIATOC is in most cases the fastest one when the length of the prediction horizon is shorter than 70 steps.     

A new algorithm for generation of different types of RNA

The structure of RNA is often the key to its function and there is a close relationship between structure and function in biology. In this paper, we present a new algorithm for generating the possible shapes of a single-stranded RNA molecule of length ?. We use a bijection between the secondary structure and specific ordered trees. Hence, generating different types of RNA becomes equivalent to the generation of these trees. The generated trees are encoded as integer sequences and are produced in A-order. The time complexity of the presented algorithm is O(??k) where ? is the number of bases and k, the number of pairings. Ranking and unranking algorithms with O(k??k ²) and O(?²+k ²) time complexity are also presented.     

A new method for the computation of all stabilizing controllers of a given order

A new method is given for computing the set of all stabilizing controllers of a given order for linear, time invariant, scalar plants. The method is based on a generalized Hermite–Biehler theorem and the successive application of a modified constant gain stabilizing algorithm to subsidiary plants. It is applicable to both continuous and discrete time systems.     

A queue based mutual exclusion algorithm

A new elegant and simple algorithm for mutual exclusion of N processes is proposed. It only requires shared variables in a memory model where shared variables need not be accessed atomically. We prove mutual exclusion by reformulating the algorithm as a transition system (automaton), and applying simulation of automata. The proof has been verified with the higher-order interactive theorem prover PVS. Under an additional atomicity assumption, the algorithm is starvation free, and we conjecture that no competing process is passed by any other process more than once. This conjecture was verified by model checking for systems with at most five processes.     

A parallel algorithm for 2-D DFT computation with no interprocessorcommunication

A parallel algorithm is proposed for the two-dimensional discrete Fourier transform (2-D DFT) computation which eliminates interprocessor communications and uses only O(N) processors. The mapping of the algorithm onto architectures with broadcast and report capabilities is discussed. Expressions are obtained for estimating the speed performance on these machines as a function of the size N×N of the 2-D DFT, the bandwidth of the communications channel, the time for an addition, the time T( F_N) for a single processing element to perform an N-point DFT, and the degree of parallelism. For single I/O channel machines that are capable of exploiting the full degree of parallelism of the algorithm, attainable execution times are as low as the time T(F_N) plus the I/O time for data upload and download. An implementation on a binary tree computer is discussed     

基于Ising模型的QR码加密算法

快速反应码(QR)二维条形码在通信时存在安全隐患,为此提出了一种加密算法。伊辛(Ising)模型具有矩阵形式,在形式上与QR码相同,且其状态变换过程支持并行计算。基于Ising模型的变换规则生成加密矩阵,然后结合QR码的编码原理计算出QR码的密文。实验结果证实该算法具有良好的随机性和密钥敏感性。该算法简单、安全、高效,可用于QR码的安全保密通信