An integrated automatic test data generation system

The Godzilla automatic test data generator is an integrated collection of tools that implements a relatively new test data generation method—constraint-based testing—that is based on mutation analysis. Constraint-based testing integrates mutation analysis with several other testing techniques, including statement coverage, branch coverage, domain perturbation, and symbolic evaluation. Because Godzilla uses a rule-based approach to generate test data, it is easily extendible to allow new testing techniques to be integrated into the current system. This article describes the system that has been built to implement constraint-based testing. Godzilla's design emphasizes orthogonality and modularity, allowing relatively easy extensions. Godzilla's internal structure and algorithms are described with emphasis on internal structures of the system and the engineering problems that were solved during the implementation.Parts of this research were supported by Contract F30602-85-C-0255 through Rome Air Development Center while the author was a graduate student at the Georgia Institute of Technology.     

Top-down designs of instruction systolic arrays for polynomial interpolation and evaluation

This paper describes the application of a new parallel architecture—Instruction systolic array (ISA)-for the interpolation and evaluation of polynomials using a linear array of processors. It also demonstrates a systematic top-down design of instruction systolic arrays. The periods of the resulting algorithms are O(n) for interpolation and O(1) for evaluation, where n is the degree of the polynomial.     

Optimal floating point multiplication processor for signal processing

The design of a floating point matrix- vector multiplication processor array for VLSI, which has an optimal area-time complexity product, is presented. This processor array is capable of performing the function (where n = 1,…, N) and can be applied in many digital signal processing applications, by simply changing the matrix coefficients stored in that array. Each N-bit mantissa, M-bit exponent (N, M) processor element of the array comprises a mantissa multiplier/adder circuit and hardware to handle the floating point control. The multiplier/adder circuit is implemented by a new optimal algorithm, which is regular, recursive and fast. Secondly, the algorithm offers a highly local and regular interconnection network, which is a fundamental requirement in VLSI circuit design methodology.     

Flexible rerouting schemes for reconfiguration of multiprocessor arrays

In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration reorganizes fault-free PEs to a new regular topology by changing the interconnection among PEs. This paper investigates the problem of constructing as large as possible logical array with short interconnects from a physical array with faults. A flexible rerouting scheme is developed to improve the efficiency of utilizing fault-free PEs. Under the scheme, two efficient reconfiguration algorithms are proposed. The first algorithm is able to generate the maximum logical array (MLA) in linear time. The second algorithm reduces the interconnect length of the MLA, and it is capable of producing nearly optimal logical arrays in comparison to the lower bound of the interconnect length, that is also proposed in this paper. Experimental results validate the efficiency of the flexible rerouting schemes and the proposed algorithms. For 128×128 host arrays with 30% unavailable PEs, the proposed approaches improve existing algorithm up to 44% in terms of logical array size, while reducing the interconnection redundancy by 49.6%. In addition, the proposed algorithms are more scalable than existing approaches. On host arrays with 50% unavailable PEs, our algorithms can produce logical arrays with harvest over 56% while existing approaches fail to construct a feasible logical array.     

A conceptual approach for the die structure design

A large number of decisions are made during the conceptual design stage which is characterized by a lack of complete geometric information. While existing CAD systems supporting the geometric aspects of design have had little impact at the conceptual design stage. To support the conceptual die design and the top–down design process, a new concept called conceptual assembly modeling framework (CAMF) is presented in this paper. Firstly, the framework employs the zigzag function-symbol mapping to implement the function design of the die. From the easily understood analytical results of the function-symbol mapping matrix, the designer can evaluate the quality of a proposed die concept. Secondly, a new method—logic assembly modeling is proposed using logic components in this framework to satisfy the characteristic of the conceptual die design. Representing shapes and spatial relations in logic can provide a natural, intuitive method of developing complete computer systems for reasoning about die construction design at the conceptual stage. The logic assembly which consists of logic components is an innovative representation that provides a natural link between the function design of the die and the detailed geometric design.     

Transforming engineering knowledge through graph representations: transferring the Willis method to linkages and trusses

The paper introduces an approach for transforming methods and knowledge between different engineering fields through general discrete mathematical models, called graph representations, which carry engineering knowledge of specific systems. The idea is demonstrated by showing the transformation of the known method in planetary gear trains—the Willis method—to two other engineering systems: linkages and trusses. In doing so, two efficient methods were derived: one for analysing compound linkages, such as those containing tetrads, and another for compound trusses. These new methods were derived from two relations characterising graph representations: a representation that is common to two engineering fields and the duality relation between representations. The new approach underlying these transformations is shown to open new ways of conducting engineering research by enabling a systematic derivation of engineering knowledge through knowledge transformations between the graph representations.     

Towards an RCC-Based Accelerator for Computational Fluid Dynamics Applications

Computational Fluid Dynamics (CFD) applications are a critical tool in designing sophisticated mechanical systems such as jet engines and gas turbines. CFD applications use intensive floating-point calculations and are typically run on High-Performance Computing (HPC) systems. We analyze three of the most compute intensive functions (Euler, Viscous, and Smoothing algorithms) and develop a baseline system architecture for accelerating these functions in RCC hardware. We then present detailed design data for the most compute intensive (Euler) function. Based on this analysis, we show that an RCC-based CFD accelerator—compared to conventional processors—promises dramatic improvement in sustained compute speed at better price-performance ratios coupled with much lower overall power consumption.     

Functional programming on a dataflow architecture: Applications in real-time image processing

This paper presents a dataflow functional computer (DFFC) developed at the Etablissement Technique Central de l'Armement (ETCA) and dedicated to real-time image processing. Two types of data-driven processing elements, dedicated respectively to low-level and mid-level processings are integrated in a regular 3D array. The design of the DFFC relies on a close integration of the dataflow-architecture principles and the functional programming concept. An image processing algorithm, expressed with a syntax similar to that of functional programming (FP) is first converted into a dataflow graph. The nodes of this graph are real-time operators that can be implemented on the physical processors of the dataflow machine. This dataflow graph is then mapped directly onto the processor array. The programming environment includes a complete compilation stream from the FP specification to hardware implementation, along with a global operator database. Apart from being a research tool for real-time image processing, the DFFC may also be used to perform the automatic synthesis of autonomous vision automata from a high-level functional specification. An experimental system, including 1024 lowlevel custom dataflow processors and 12 T800 transputers, was built and can perform up to 50 billion operations/s. Several image processing algorithms were implemented on this system and run in real-time at digital video speed.     

Window memoization: an efficient hardware architecture for high-performance image processing

This work presents a new performance improvement technique, window memoization, for hardware implementations of local image processing algorithms. Window memoization combines the memoization techniques proposed in software and hardware with data redundancy in image processing to improve the efficiency of local image processing algorithms implemented in hardware. It minimizes the number of redundant computations performed on an image by identifying similar neighborhoods of pixels in the image and skipping the redundant computations. We have developed an optimized architecture in hardware that embodies the window memoization technique. Our hardware design for window memoization achieves high speedups with an overhead in hardware area that is significantly less than that of the conventional performance improvement techniques. As case studies in hardware, we have applied window memoization to the Kirsch edge detector and median filter. The typical speedup factor in hardware is 1.58 with 40% less hardware in comparison to conventional optimization techniques.     

短波宽带阵列信号源的设计与实现

为了在实验室给宽带阵列信号处理设备的研制、维护提供一个较好的仿真环境,介绍了一种基于多片DSP芯片ADSP-TS201S和数字上变频器AD9857构成的宽带阵列信号源,模拟实现了最大带宽为4MHz的短波宽带阵列信号。主要包括系统设计方案、系统硬件设计和DSP软件设计等。     

Variable structure exponential stabilization of chained systems based on the extended nonholonomic integrator

In this paper, a new variable structure control strategy for exponentially stabilizing chained systems is presented based on the extended nonholonomic integrator model, the discontinuous coordinate transformation and the “reaching law method” in variable structure control design. The proposed approach converts the stabilization problem of an n-dimensional chained system into the pole-assignment problem of an (n−3)-dimensional linear time-invariant system and consequently simplifies the stabilization controller design of nonholonomic chained systems.     

正交阵并行图象处理的研究和实现

文中提出了具有良好性能的正交阵并行图象处理机系统的硬件构造，并详细分析了快速Ｆｏｕｒｉｅｒ变换，图象矩运算，直方图统计等图像处理中常用算法在并行机上的执行情况，时间复杂度和相对单机而言的加速比。     

Parallelization of sorting algorithms

The paper considers parallel (synchronous) array sorting algorithms obtained by parallelizing the corresponding sequential sorting algorithms. A classification of synchronous sorting algorithms, based on the sequential scheme, is proposed. A number of new efficient synchronous array sorting algorithms are developed.Translated from Kibernetika, No. 6, pp. 67–74, November–December, 1989.     

Synthesis of linear antenna array using flower pollination algorithm

Linear antenna array (LAA) design is a classical electromagnetic problem. It has been extensively dealt by number of researchers in the past, and different optimization algorithms have been applied for the synthesis of LAA. This paper presents a relatively new optimization technique, namely flower pollination algorithm (FPA) for the design of LAA for reducing the maximum side lobe level (SLL) and null control. The desired antenna is achieved by controlling only amplitudes or positions of the array elements. FPA is a novel meta-heuristic optimization method based on the process of pollination of flowers. The effectiveness and capability of FPA have been proved by taking difficult instances of antenna array design with single and multiple objectives. It is found that FPA is able to provide SLL reduction and steering the nulls in the undesired interference directions. Numerical results of FPA are also compared with the available results in the literature of state-of-the-art algorithms like genetic algorithm, particle swarm optimization, cuckoo search, tabu search, biogeography based optimization (BBO) and others which also proves the better performance of the proposed method. Moreover, FPA is more consistent in giving optimum results as compared to BBO method reported recently in the literature.

     

Scalable and Modular Algorithms for Floating-Point Matrix Multiplication on Reconfigurable Computing Systems

The abundant hardware resources on current reconfigurable computing systems provide new opportunities for high-performance parallel implementations of scientific computations. In this paper, we study designs for floating-point matrix multiplication, a fundamental kernel in a number of scientific applications, on reconfigurable computing systems. We first analyze design trade-offs in implementing this kernel. These trade-offs are caused by the inherent parallelism of matrix multiplication and the resource constraints, including the number of configurable slices, the size of on-chip memory, and the available memory bandwidth. We propose three parameterized algorithms which can be tuned according to the problem size and the available hardware resources. Our algorithms employ linear array architecture with simple control logic. This architecture effectively utilizes the available resources and reduces routing complexity. The processing elements (PEs) used in our algorithms are modular so that it is easy to embed floating-point units into them. Experimental results on a Xilinx Virtex-ll Pro XC2VP100 show that our algorithms achieve good scalability and high sustained GFLOPS performance. We also implement our algorithms on Cray XD1. XD1 is a high-end reconfigurable computing system that employs both general-purpose processors and reconfigurable devices. Our algorithms achieve a sustained performance of 2.06 GFLOPS on a single node of XD1     

Scalarization Using Loop Alignment and Loop Skewing

Array syntax, which is supported in many technical programming languages, adds expressive power by allowing operations on and assignments to whole arrays and array sections. To compile an array assignment statement to a uniprocessor, the language processor must convert the statement into a loop that has the same meaning. This process is called scalarization.Scalarization presents a significant technical problem because an array assignment needs to be implemented as if all inputs are fetched before any outputs are stored. Since a loop intermixes loads and stores, the compiler typically allocates a temporary array to hold the intermediate result. Because these extra temporary arrays can cause performance problems in cache, many techniques have been developed to avoid their use or minimize their size.In this paper, we present a novel application of two compiler strategies—loop alignment and loop skewing—to address this problem. We show that these strategies can achieve the asymptotically minimal memory allocation for stencil computations. Our experiments with loop alignment and loop skewing demonstrate that it is extremely effective in improving memory hierarchy performance of Fortran 90 array code on standard uniprocessors. The result should be applicable to other array languages, such as MATLAB.     

On Randomization in On-Line Computation

This paper concerns two fundamental but somewhat neglected issues, both related to the design and analysis of randomized on-line algorithms. Motivated by early results in game theory we define several types of randomized on-line algorithms, discuss known conditions for their equivalence, and give a natural example distinguishing between two kinds of randomizations. In particular, we show thatmixedrandomized memoryless paging algorithms can achieve strictly better competitive performance thanbehavioralrandomized algorithms. Next we summarize known—and derive new—“Yao principle” theorems for lower bounding competitive ratios of randomized on-line algorithms. This leads to four different theorems for bounded/unbounded and minimization/maximization problems.     

A new algorithm based on Givens rotations for solving linearequations on fault-tolerant mesh-connected processors

In this paper, we propose a new I/O overhead free Givens rotations based parallel algorithm for solving a system of linear equations. The algorithm uses a new technique called two-sided elimination and requires an N×(N+1) mesh-connected processor array to solve N linear equations in (5N-log N-4) time steps. The array is well suited for VLSI implementation as identical processors with simple and regular interconnection pattern are required. We also describe a fault-tolerant scheme based on an algorithm based fault tolerance (ABFT) approach. This scheme has small hardware and time overhead and can tolerate up to N processor failures     

Hardware Coprocessor Synthesis from an ANSI C Specification

Editor's note:This article shows how design space exploration can be realized through high-level synthesis. It presents a case study of a hardware implementation of the Advanced Encryption Standard (AES) Rijndael algorithm. Starting from the algorithmic specification, the authors generate various architectures by using the C2R compiler.—Philippe Coussy, Université de Bretagne-Sud