In this paper, we update our previous research for Mel-Frequency Cepstral Coefficient (MFCC) feature extraction [1] and describe the optimizations required for improving throughput on the Graphics Processing Units (GPU). We not only demonstrate that the feature extraction process is suitable for GPUs and a substantial reduction in computation time can be obtained by performing feature extraction on these platforms, but also discus about the optimized algorithm. Using one GTX580 GPU our approach is shown to be approximately 97x faster than a sequential CPU implementation, enabling feature extraction to be performed at under 0.01% real-time. This is significantly faster than prior reported results implemented on GPUs, DSPs and FPGAs. Furthermore we demonstrate that multiple MFCC features can be generated for a set of predefined Vocal Tract Length Normalization (VTLN) alpha parameters with little degradation in throughput, along with the optimization for filter bank and reductions.

The latest FPGA devices provide the headroom to implement large-scale and complex systems. A key requirement is the integration of modules from diverse sources to promote modular design and reuse. A contrary factor is that using dynamic partial reconfiguration typically requires low-level planning of the system implementation. In this article, we introduce ReShape: a high-level approach for designing reconfigurable systems by interconnecting modules, which gives a “plug and play” look and feel, is supported by tools that carry out implementation functions, and is carried through to support system reconfiguration during operation. The emphasis is on the inter-module connections and abstracting the communication patterns that are typical between modules: for example, the streaming of data, or the reading and writing of data to and from memory modules. The details of wiring and signaling are hidden from view, via metadata associated with individual modules. This setting allows system reconfiguration at the module level, both by supporting type checking of replacement modules and by managing the overall system implementation, via metadata associated with its FPGA floorplan. The methodology and tools have been implemented in a prototype targeted to a domain-specific setting---high-speed networking---and have been validated on real telecommunications design projects.

Loop unrolling is a loop transformation where a few loop iterations are grouped as a super iteration for exploring more independent instructions and to decrease the total loop overhead. This paper characterizes loop unrolling by the unrolling factor, the number of iterations in a super iteration and the unrolling direction, the choice of iterations to be grouped to form the super iteration. We use loop unrolling for maximizing instruction-level parallelism in the longest common subsequence problem. To increase the number of independent instructions in the super iteration, we use a linear schedule to group iterations on the same wave front, a hyper plane in the loop iteration space. Then, the loop is unrolled along the wave front which guarantees all iterations in the same super iteration are independent. The selection of the optimal unrolling factor is based on the assumption that if all the pipelines are saturated, the performance should not be bad. Two necessary conditions and a sufficient condition for optimality are presented and used to find the optimal unrolling factor. The total execution time is expressed as a function of algorithm parameters, architecture parameters and the unrolling factor. A benchmark of the technique scores a 1.475 speed-up over traditional methods.

The latest generation of FPGA devices offers huge resource counts that provide the headroom to implement large-scale and complex systems. However, this poses increasing challenges for the designer, not just because of pure size and complexity, but also to harness effectively the flexibility and programmability of the FPGA. A central issue is the need to integrate modules (IP blocks) from diverse sources to promote modular design and reuse. In this paper, we introduce ShapeUp: a high-level approach for designing systems by interconnecting modules, which gives a `plug and play' look and feel to the designer and is supported by tools that carry out implementation and verification functions. The emphasis is on the inter-module connections and abstracting the communication patterns that are typical between modules - for example, the streaming of data that is common in many FPGA based DSP or networking systems, or the reading and writing of data to and from memory modules. The details of wiring and signaling are hidden from view, via metadata associated with individual modules. The ShapeUp tool suite includes an implementation capability that automatically generates wiring between blocks, possibly including additional bridging blocks, and a simulation capability that allows multi-level verification of systems of interconnected modules. The methodology and tools have been validated on Xilinx customer design projects.

Field programmable logic is increasingly used to provide the high performance and flexible acceleration needed for network processing functions at multiple gigabit/second rates. Almost all such functions feature the use of clocks and timers in control and/or data roles, and these are typically implemented in an ad hoc manner. This paper introduces a set of three configurable timing modules that are based on abstractions of the prevalent timing paradigms observed in network protocols. The modules fit within the experimental ShapeUp methodology for modular FPGA-based system design, and so can be easily integrated with other modules that are tailored for specific networking functions. The use and benefits of the new modular approach are demonstrated by an example of a flexible FPGA reference design that has been made available for real-life use by telecommunication equipment providers.

In this paper, we propose an efficient and practical algorithm to dynamically adapt the Lagrange multipliers for each macroblock based on the context of the neighboring or upper layer blocks to improve rate-distortion performance. Our method improves the accuracy for the detection of true motion vectors as well as the most efficient encoding modes for luma, which are used for deriving the motion vectors, and modes for chroma. Simulation results for H.264/advanced video coding video demonstrate that our method reduces bit rate significantly and achieves peak signal-to-noise ratio gain over those of the joint model (JM) software for all sequences tested, with negligible extra computational cost. The improvement is particularly significant for high motion high-resolution videos. This paper describes our work that led to our Joint Video Team adopted contribution (included in software JM 12.0 onward), collectively known as context adaptive Lagrange multiplier (CALM).

For memory constrained environments like embedded systems, optimization for size is often as important as, if not more important than, optimization for execution speed. A common technique for compacting code is procedural abstraction. Equivalent code fragments are identified and abstracted into a procedure. The standard algorithm for identifying these fragments is based on suffix trees. We propose in this paper the calculation of suffix trees over the program text not in the common top-down fashion, but reversed, i.e. bottom-up. With this simple modification, not only equivalent fragments can be identified, but also fragments equivalent to (possibly often differently long) suffixes of the longest fragments. A longest fragment is then abstracted, and all fragments are replaced by procedure calls to their corresponding start instruction somewhere in the abstracted procedure. This allows us to harvest more and longer fragments than with standard suffix trees, improving code size reductions on average by 8.277% over standard suffix trees.

The emerging scalable video coding extension in H.264/AVC standard will enable the deployment of video streaming and distribution applications in heterogeneous environments, with different user bandwidth resources and display capacities. In this paper, we study the problem of how to distribute scalable coded media objects from a media distribution server in peer-to-peer based IPTV applications. All the media layers are divided in segments to be exchanged by peers in every playback interval. We formulate the media distribution scheme as an optimization problem, so that the time for the system to distribute all media layers to its subscribed end users is minimized. We compared the optimal distribution algorithm with an alternative heuristic algorithm through simulations. The experimental results have demonstrated the excellent performance of the proposed optimal distribution algorithm.

There is an active research community concentrating on visualizations of algorithms taught in CS1 and CS2 courses. These visualizations can help students to create concrete visual images of the algorithms and their underlying concepts. Not only fundamental algorithms can be visualized, but also algorithms used in compilers. Visualizations that exist for use in compiler courses are mostly for the frontend , though. In this article we propose the use of visualizations for understanding optimization passes. Optimization passes are complex algorithms that operate on large amounts of code and it is not obvious when, where and how often each optimization is applied to the code. We show in this article how visualizations for a procedural abstraction optimization pass can capture the effect of all instances of this optimization over an entire program to make it easier for students to comprehend procedural abstraction.

For memory constrained environments like embedded systems, optimization for program size is often as important, if not more important, as optimization for execution speed. Commonly, compilers try to reduce the code segment and neglect the stack segment, although the stack can significantly grow during the execution of recursive functions as a separate activation record is required for each recursive call. An activation record holds administrative data like the return address and the frame pointer but also the function's formal parameter list and local variables.

The increasing interest in higher fidelity video initiated the need of higher efficient coding. Color pictures are usually compressed in a luma-chroma coordinate space. One of the important components in H.264 encoding is to find optimal motion vectors and modes to minimize both luma and chroma coefficients bits. This paper proposes a new simple and efficient method to adjust Lagrange multipliers based on the context (context adaptive Lagrange multiplier or CALM), which improves the accuracy for the detection of true motion vectors as well as the most efficient encoding modes for luma which are used for deriving the motion vectors and modes for chroma. Simulation results show that the chroma bit rates can be reduced by 4.36% and 4.80% for U and V components respectively when compared with that of the JM reference software (version 10.2). In addition, the coding efficiency improvement is comparable to the more complicated rate-distortion optimized (RDO) mode decision techniques.

Distributed Arithmetic (DA) is an important technique to implement digital signal processing (DSP) functions in FPGAs. However, traditional lookup table (LUT) based DA architectures contain one or more carry propagation chains in the critical path that dictates the fastest time at which an entire design can run. In this paper, we describe a novel technique that can reduce or eliminate the carry-propagate chain from the critical path in LUT based DA architectures on FPGAs. In the proposed scheme, the individual bits of a word do not have to be processed as a unit. Instead, the current iteration can start as soon as the least significant bit (LSB) of the previous iteration is available, without waiting for the entire word from the previous iteration to be fully computed. This technique has great potential in speeding up DSP applications based on DA. Designs are described for serial and parallel DALUT and accumulator structures in which an n-bit carry chain, where n is the word length, is broken into smaller r-bit chains, 1 r n ≤ <. A cost-performance analysis of the designs is presented. The analysis shows that the designs proposed in this paper have a lower cost-performance ratio (indicating better performance) than traditional DA designs. We also show that the 8-bit (r = 8) designs offer a good compromise between cost and performance. The implementation is on a Xilinx chip XC4028XL-3-BG256 using Xilinx Foundation tools v 3.1i. The results show that the proposed designs can achieve speedup by a factor of at least 1.5 over traditional DA designs in some cases.

With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses the selection of an optimal supernode shape of a supernode transformation (also known as tiling). We identify three parameters of a supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For supernode transformations on algorithms with perfectly nested loops and uniform dependencies, we prove the optimality of a constant linear schedule vector and give a necessary and sufficient condition for optimal relative side lengths. We also prove that the total running time is minimized by a cutting hyperplane direction matrix from a particular subset of all valid directions and we discuss the cases where this subset is unique. The results are derived in continuous space and should be considered approximate. Our model does not include cache effects and assumes an unbounded number of available processors, the communication cost approximated by a constant, uniform dependences, and loop bounds known at compile time. A comprehensive example is discussed with an application of the results to the Jacobi algorithm.

With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses how to find an optimal supernode size and optimal supernode relative side lengths of a supernode transformation (also known as tiling). We identify three parameters of supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For algorithms with perfectly nested loops and uniform dependencies, for sufficiently large supernodes and number of processors, and for the case where multiple supernodes are mapped to a single processor, we give an order n polynomial whose real positive roots include the optimal supernode size. For two special cases, 1) two-dimensional algorithm problems and 2) n-dimensional algorithm problems, where the communication cost is dominated by the startup penalty and, therefore, can be approximated by a constant, we give a closed form expression for the optimal supernode size, which is independent of the supernode relative side lengths and cutting hyperplanes. For the case where the algorithm iteration index space and the supernodes are hyperrectangular, we give closed form expressions for the optimal supernode relative side lengths. Our experiment shows a good match of the closed form expressions with experimental data.

Supernode transformation has been proposed to reduce the communication startup cost by grouping a number of iterations in a loop as a supernode which is assigned to a processor as a single unit. A supernode transformation is specified by n families of hyperplanes which slice the iteration space into parallelepiped supernodes, the grain size of a supernode, and the relative side lengths of the parallelepiped supernode. The total running time is affected by the three factors mentioned above. In this paper, how to find an optimal grain size and an optimal relative side length vector, with the goal of minimizing total running time, is addressed. Two communication cost models are considered. In the first one, communication cost is approximated by a constant startup penalty and in the second, communication cost is a function of the startup penalty and the message size. We derive closed form analytical expressions for the optimal supernode size for the one parameter model and the two parameter model with doubly nested loops. A closed form expression for the optimal relative length vector is also provided for the one parameter model with constant bounded loop iteration space.

The paper deals with the problem of transforming irregular data dependence structures of algorithms with nested loops into more regular ones. Algorithms under consideration are n-dimensional algorithms (algorithms with n nested loops) with affine dependences where dependences are affine functions of index variables of the loop. Methods are proposed to uniformize affine dependence algorithms, i.e., to transform affine dependence algorithms into uniform dependence algorithms where dependences are independent of the index variables (constant). Objectives are considered to guide the selection of feasible uniformizations. The first one is to reduce the number of dependences after uniformization. The second one is to maximize parallelism preserved by the uniformization. Some parallelism might be lost due to the uniformization. The parallelism preserved by the uniformization is measured by: the total execution time by the optimal linear schedule which assigns each computation in the algorithm an execution time according to a linear function of the index of the computation; and the size of the cone spanned by the dependence vectors after uniformization.

In this paper, how to distribute data to different memory modules and how to distribute computations to different processors for execution in a distributed memory parallel computer without nonlocal communications or with minimum nonlocal communications are addressed. Nonlocal communications are much more expensive compared to local communications, e.g., nearest neighbor shifts of data. Algorithms are classified to uniform communication algorithms where communication patterns are regular and affine communication algorithms where communication patterns are affine functions of loop index variables. Necessary and sufficient conditions on the existence of mappings without nonlocal communications are presented. If such mappings exist, constraints posed by the mapping without nonlocal communications are constructed and used to guide the selection of mappings with minimum local communications.>

We consider a connected set of workstations as a “pool of processors” and develop a queueing model to analyze the performance of optimal co-scheduling algorithms. The pool of processors model was originally developed for the Amoeba operating system. It was also used in the design of the recent IBM supercomputer model 9076 SP1. Recently, co-scheduling has been suggested as an approach for scheduling computationally intensive tasks in the pool of processors model. Co-scheduling algorithms select the best possible subset of workstations for a task to minimize its completion time.

This paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes.>

To test if there is a dependence between different iterations in a loop can be converted to checking if there exist integral points in a polyhedron described by a set of linear equations and inequalities. In this paper, a method for accurate data dependence test is proposed. In this method, first, data dependence test problems with any number of linear equations are transformed equivalently to test problems with only one linear equation and constant inequality bounds. Then, a sequence of efficient test methods applicable to test problems with one equation are used in order of their time complexities. If one of those methods succeeds, then stop, if not, a more expensive method is tried. If all those methods do not work, then the tent function method is applied which always gives accurate results. In the proposed tent function method, which is also applicable to any test problems, a nonnegative and piecewise linear function called tent function, is defined on the polyhedron whose minimum value is zero if the polyhedron contains integers. Thus, an integer checking problem is converted to an optimization problem. A piecewise linear program is used to find the minimum value of this tent function.>

In designing application-specific bit-level architectures and in programming existing bit-level processor arrays, it is necessary to expand a word-level algorithm into its bit-level form before dependence analysis can be performed. In this paper, we consider dependence structures of bit-level algorithms as functions of three components dependence structures of word-level algorithms, dependence structures of the arithmetic algorithms implementing word-wise operations, and algorithm expansions. Based on these components, we can derive dependence structures of bit-level algorithms without using time consuming general dependence analysis methods. To illustrate our approach, we derive two dependence structures for bit-level matrix multiplication and apply a method developed earlier [5,6,10] to design two bit-level architectures. One of these architectures is O{p) times faster than the best word-level architecture, where p is the word length. The speedup we found here is true in general because a bit in a bit-level architecture goes to the next processor for processing as soon as it is available.

Uniform dependence algorithms with arbitrary index sets are considered, and two computationally inexpensive methods to find their independent partitions are proposed. Each method has advantages over the other one for certain kinds of applications, and they both outperform previously proposed approaches in terms of computational complexity and/or optimality. Also, lower and upper bounds are given for the cardinality of maximal independent partitions. In multiple instruction multiple data (MIMD) systems, if different blocks of an independent partition are assigned to different processors, communications between processors will be minimized to zero. This is significant because the communications usually dominate the overhead in MIMD machines.>

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k>

The authors address the problem of identifying optimal linear schedules for uniform dependence algorithms so that their execution time is minimized. Procedures are proposed to solve this problem based on the mathematical solution of a nonlinear optimization problem. The complexity of these procedures is independent of the size of the algorithm. Actually, the complexity is exponential in the dimension of the index set of the algorithm, and for all practical purposes, very small due to the limited dimension of the index set of algorithms of practical interest. A particular class of algorithms for which the proposed solution is greatly simplified is considered, and the corresponding simpler organization procedure is provided.>