Transactional Memory (TM) is a synchronization model for parallel programming which provides optimistic concurrency control. Transactions can run in parallel and are only serialized in case of conflict. In this article we use hardware TM (HTM) to implement an optimisticspeculative barrier(SB) to replace the lock-based solution. SBs leverage HTM support to elide barriers speculatively. When a thread reaches an SB, a newSB transactionis started, keeping the updates private to the thread, and letting the HTM system detect potential conflicts. Once the last thread reaches the corresponding SB, the speculative threads can commit their changes. The main contributions of this work are: an API for SBs implemented with HTM extensions; a procedure to check the speculation state in between barriers to enable SBs with non-transactional codes; a HTM SB-aware conflict resolution enhancement where SB transactions stall on a conflict with a standard transaction; and a set of SB use guidelines derived from our experience on using SBs in a variety of applications. We evaluated our proposals in two different architectures with a full-system simulator and an IBM Power8 server. Results show an overall performance improvement of SBs over traditional barriers.

IBM and Intel now offer commercial systems with Transactional Memory (TM), a programming paradigm whose aim is to facilitate concurrent programming while maximizing parallelism. These TM systems are implemented in hardware and provide a software fallback path to overcome the hardware implementation limitations. They are known as best-effort hardware TM (BE-HTM) systems. The software fallback path must be provided by the user to ensure forward progress, which adds programming complexity to the TM paradigm. We propose a new type of irrevocability (a transactional mode that marks transactions as non-abortable) to deal with BE-HTM limitations in a more efficient manner, and to liberate the user from having to program a fallback path. It is based on the concept of lazy subscription used in the context of software fallback paths, where the fallback lock is checked at the end of the transaction instead of at the beginning. We propose a hardware lazy irrevocability mechanism that does not involve changes in the coherence protocol. It solves the unsafe execution problem of premature commits associated with lazy subscription fallbacks, and can be triggered by the user via an ISA extension, for the sake of versatility. It is compared with its software counterpart, which we propose as an enhanced lazy single global lock with escaped spinning at the end of the transaction. We also propose the lazy irrevocability with anticipation, a mechanism that cannot be implemented in software, which significantly improves the performance of codes with multiple cache evictions of transactional data. The evaluation of the proposals is carried out with the Simics/GEMS simulator along with the STAMP benchmark suite, and we obtain speedups from 14 to 28 percent over the fallback path approaches.

Signatures have been proposed in Hardware Transactional Memory (HTM) to represent read and write sets of transactions and decouple transaction conflict detection from private caches. Generally, signatures are implemented as Bloom filters that allow unbounded read/write sets to be summarized in bounded hardware, at the cost of address aliasing that causes false conflict detection. Such conflicts rises exponentially as signature fills so they can lead a parallel program to perform worse than its sequential counterpart (we say that signature saturates). In this work, irrevocability is proposed to address the signature saturation problem. When a transaction is near to saturate its signature, the transaction enters an irrevocable state that prevents it from being aborted. Then, such a transaction keeps running while the others are either stalled or allowed to run concurrently. Two variants of irrevocability are analyzed in this paper. Experimental evaluation on an HTM simulator shows the benefits in performance and power consumption of the proposed irrevocability mechanisms.

This article describes a transactional memory execution model intended to exploit maximum parallelism from sequential and multithreaded programs. A program code section is partitioned into chunks that will be mapped onto threads and executed transactionally. These transactions run concurrently and out of order, trying to exploit maximum parallelism but managed by a specific fully distributed commit control to meet data dependencies. To accomplish correct parallel execution, a partial precedence order relation is derived from the program code section and/or defined by the programmer. When a conflict between chunks is eagerly detected, the precedence order relation is used to determine the best policy to solve the conflict that preserves the precedence order while maximizing concurrency. The model defines a new transactional state called executed but not committed . This state allows exploiting concurrency on two levels: intrathread and interthread. Intrathread concurrency is improved by having pending uncommitted transactions while executing a new one in the same thread. The new state improves interthread concurrency because it permits out-of-order transaction commits regarding the precedence order. Our model has been implemented in a lightweight software transactional memory system, TinySTM, and has been evaluated on a set of benchmarks obtaining an important performance improvement over the baseline TM system.

We propose a floating-point representation to deal efficiently with arithmetic operations in codes with a balanced number of additions and multiplications for FPGA devices. The variable shift operation is very slow in these devices. We propose a format that reduces the variable shifter penalty. It is based on a radix-64 representation such that the number of the possible shifts is considerably reduced. Thus, the execution time of the floating-point addition is highly optimized when it is performed in an FPGA device, which compensates for the multiplication penalty when a high radix is used, as experimental results have shown. Consequently, the main problem of previous specific high-radix FPGA designs (no speedup for codes with a balanced number of multiplications and additions) is overcome with our proposal. The inherent architecture supporting the new format works with greater bit precision than the corresponding single precision (SP) IEEE-754 standard.

The knowledge of visibility information on a terrain is essential for a large number of current applications. There exist several algorithms in the literature for building visibility maps (VMs) but only for one single viewpoint or at most for a very small number of observers. This limitation is due to the high computational complexity of the used methods (which is greater than O , where N is the number of the terrain points) and also due to the fact that single-point algorithms cannot efficiently be scaled to all points. We present a novel fast algorithm able to compute the complete VM, also called total viewshed, where, given a terrain T represented by its regular digital elevation model (DEM), our method simultaneously produces a continuous VM for all the points of T. In particular, the proposed algorithm combines two algorithms, (i) a visible heights algorithm that divides the terrain into sectors and calculates the end of all the visible ring sectors and (ii) an algorithm that finds out the start of those visible ring sectors using a low-cost calculation. Theoretical and experimental comparisons were performed considering the VM of one single observer, because the most used GIS tools compute the viewshed by point. The results demonstrate that our algorithm is faster by many orders of magnitude than the widely used GIS visibility tools showing similar accuracy.

Although redundant addition is widely used to design parallel multioperand adders for ASIC implementations, the use of redundant adders on Field Programmable Gate Arrays (FPGAs) has generally been avoided. The main reasons are the efficient implementation of carry propagate adders (CPAs) on these devices (due to their specialized carry-chain resources) as well as the area overhead of the redundant adders when they are implemented on FPGAs. This paper presents different approaches to the efficient implementation of generic carry-save compressor trees on FPGAs. They present a fast critical path, independent of bit width, with practically no area overhead compared to CPA trees. Along with the classic carry-save compressor tree, we present a novel linear array structure, which efficiently uses the fast carry-chain resources. This approach is defined in a parameterizable HDL code based on CPAs, which makes it compatible with any FPGA family or vendor. A detailed study is provided for a wide range of bit widths and large number of operands. Compared to binary and ternary CPA trees, speedups of up to 2.29 and 2.14 are achieved for 16-bit width and up to 3.81 and 3.11 for 64-bit width.

Transactional Memory (TM) is an alternative to conventional multithreaded programming to ease the writing of concurrent programs. In the context of unbounded TM, concurrent threads may use hardware signatures to record all the memory addresses issued inside a transaction to detect conflicts. Signatures are usually implemented as per-thread fixed hardware Bloom filters that summarize a very large amount of read and write memory addresses at the cost of false conflicts (detection of nonexisting conflicts). In this paper, to reduce the probability of false conflicts, a novel signature design that exploits spatial locality is proposed. The design is based on new hash function mappings, so that nearby located addresses share some bits inserted in the filters. This is favorable particularly for large transactions that usually exhibit some amount of spatial locality. Besides, its implementation does not require extra hardware. The proposed signature was experimentally evaluated using the GEMS simulator and all the codes of the STAMP benchmark suite. In most cases, the results show significant improvement, particularly in the codes that involve long-running, large-data transactions.

Transactional Memory (TM) systems must track memory accesses made by concurrent transactions in order to detect conflicts. Many TM implementations use signatures for this purpose, which summarize reads and writes in fixed-size bit registers at the cost of false positives (detection of nonexisting conflicts). Signatures are commonly implemented as two separate same-sized Bloom filters, one for reads and other for writes. In contrast, transactions frequently exhibit read and write sets of uneven cardinality. This mismatch between data sets and filter storage introduces inefficiencies in the use of signatures that have some impact on performance. This paper presents different signature designs as alternatives to the common scheme to deal with the asymmetry in transactional data sets in an effective way. Basically, we analyze two classes of new signatures, called multiset and reconfigurable asymmetric signatures. The first class uses only one Bloom filter to track both read and write sets, while the second class uses Bloom filters of configurable size for reads and writes. The main focus of this paper is a thorough study of these alternative signature designs, including a statistical analysis of false positives and an experimental evaluation, providing performance results and hardware area, time and energy requirements.

In this paper we present the design of an on-line adder dealing with two RBCD numbers. This basic element is intended to be be used in any on-line system in which the addition is involved. We obtain the on-line adder by serialization of a recent parallel RBCD adder with minimum latency.To reduce the cycle time a pipelined version is proposed. To deal with data stream the throughput has been reduced to its theoretical minimum possible value by a negligible cost hardware modification. Finally, actual implementation results for 16 digits (i.e. decimal64 format) are presented.

In this work, we propose a new decimal redundant CORDIC algorithm to manage transcendental functions, using floating-point representation. The algorithms determine the direction of the elementary rotation using sign estimations. Unlike binary redundant CORDIC, repetition of iterations are not required to ensure convergence since novel decimal codes have been carefully selected with sufficient redundancy to prevent any repetition. The algorithms are mapped to a low-cost unit based on a decimal 3-2 carry-save adder which can also be used as a floating-point decimal division unit. Compared to current decimal floating-point units, the implementation of our algorithm involves minor modifications of the native hardware, while providing a huge set of elementary functions.

Given the arrival of multicore processors, it has become a matter of urgency to introduce parallel programming into mainstream computing. In emerging applications, a class of computational problem that poses a challenge to the programmers is the wavefront pattern. A particular characteristic of this pattern is multi-dimensional streaming of the computations that must follow a dependence pattern. The modern software stack for multicore systems offers task-based programming libraries like TBB (Threading Building Blocks), that allow an execution model based on lightweight asynchronous tasks. We suggest that TBB provides useful features to improve the scalability of these kinds of codes but at the cost of leaving some low-level task management details to the programmer. In this paper, we discuss such low-level task management issues and incorporate them into a high-level TBB-based template. The goal of the template is to improve the programmer's productivity such that a nonexpert user can easily code complex wavefront problems without having to deal with task creation, synchronization or scheduling mechanisms. With our template, the user only has to specify a definition file with the wavefront dependence pattern and the function that each task has to execute. In addition, we describe our experience with the TBB template when coding four complex real wavefront problems. In these experiments, we found that the template implementations reduced the programming effort from 25% to 50% at a cost of increasing the overhead up to 5% when compared to manual implementations of the same problem.

Spectral evolution simulations based on the observed Very Long Baseline Interferometry (VLBI) radio-maps are of paramount importance to understand the nature of extragalactic objects in astrophysics. This work analyzes the performance and scaling of a spectral evolution algorithm on three leading multi-socket, multi-core architectures. We evaluate three parallel models with different levels of data-sharing: a sharing approach, a privatizing approach and a hybrid approach. Our experiments show that the data-privatizing model is reasonably efficient on medium scale multi-socket, multi-core systems (up to 48 cores) while regardless algorithmic and scheduling optimizations, sharing approach is unable to reach acceptable scalability on more than one socket. However, the hybrid model with a specific level of data-sharing gives the best scalability over all the considered multi-socket, multi-core systems.

Transactional Memory (TM) systems must record the memory locations read and written (read and write sets) by concurrent transactions in order to detect conflicts. Some TM implementations use signatures for this purpose, which summarize read and write sets in bounded hardware at the cost of false positives (detection of non-existing conflicts).

This work presents a high-performance algorithm to compute the horizon in very large high-resolution DEMs. We used Stewart's algorithm as the core of our implementation and considered that the horizon has three components: the ground, near, and far horizons. To eliminate the edge-effect, we introduced a multi-resolution halo method. Moreover, we used a new data partition approach, to substantially increase the parallelism in the algorithm. In addition, several optimizations have been applied to considerably reduce the number of arithmetical operations in the core of the algorithm. The experimental results have demonstrated that by applying the above-described contributions, the proposed algorithm is more than twice faster than Stewart's algorithm while maintaining the same accuracy.

Range reduction is a crucial step for accuracy in trigonometric functions evaluation. This paper shows and compares a set of algorithms for additive range reduction computation and their corresponding application-specific integrated circuit implementations (ensuring an accuracy of one unit in the last place). A word-serial architecture implementation has been used as a reference for clearer comparisons. Besides, a new table-based pipelined architecture for range reduction has also been proposed.

This paper analyzes the applicability of the task programming model in the parallelization of generic wave front problems. Computations on this type of problems are characterized by a data dependency pattern across a data space, which can produce a variable number of independent tasks through the traversal of such space. Precisely, we think that it is better to formulate the parallelization of this wave front-based programs in terms of logical tasks, instead of threads for several reasons: more efficient matching of computations to available resources, faster start-up and creation task times, improved load balancing and higher level thinking. To implement the parallel wave front we have used two state-of-the art task libraries: TBB and OpenMP 3.0. In this work, we highlight the differences between both implementations, from a programmer standpoint and from the performance point of view. For it, we conduct several experiments to identify the factors that can limit the performance on each case. Besides, we present in the paper a wave front template based on tasks, template that makes easier the coding of parallel wave front codes. We have validated this template with three real dynamic programming algorithms, finding that the TBB-coded template always outperforms the OpenMP based-one.

Writing multithreaded programs is a fairly complex task that poses a major obstacle to exploit multicore processors. Transactional Memory (TM) emerges as an alternative to the conventional multithreaded programming to ease the writing of concurrent programs. Hardware Transactional Memory (HTM) implements most of the required mechanisms of TM at the core level, e.g. conflict detection. Signatures are designed to support the detection of conflicts amongst concurrent transactions, and are usually implemented as per-thread Bloom filters in HTM. Basically, signatures use fixed hardware to summarize an unbounded amount of read and write memory addresses at the cost of false conflicts (detection of non-existing conflicts). In this paper, a novel signature design that exploit locality is proposed to reduce the number of false conflicts. We show how that reduction translates into a performance improvement in the execution of concurrent transactions. Our signatures are based on address mappings of the hash functions that reduce the number of bits inserted in the filter for those addresses nearby located. This is specially favorable for large transactions, that usually exhibit some amount of spatial locality. Furthermore, the implementation do not require extra hardware. Our proposal was experimentally evaluated using the Wisconsin GEMS simulator and all codes from the STAMP benchmark suite. Results show a significant performance improvement in many cases, specially for those codes with long-running, large-data transactions.

Most field programmable gate array (FPGA) devices have a special fast carry propagation logic intended to optimize addition operations. The redundant adders do not easily fit into this specialized carry-logic and, consequently, they require double hardware resources than carry propagate adders, while showing a similar delay for small size operands. Therefore, carry-save adders are not usually implemented on FPGA devices, although they are very useful in ASIC implementations. In this paper we study efficient implementations of carry-save adders on FPGA devices, taking advantage of the specialized carry-logic. We show that it is possible to implement redundant adders with a hardware cost close to that of a carry propagate adder. Specifically, for 16 bits and bigger wordlengths, redundant adders are clearly faster and have an area requirement similar to carry propagate adders. Among all the redundant adders studied, the 4:2 compressor is the fastest one, presents the best exploitation of the logic resources within FPGA slices and the easiest way to adapt classical algorithms to efficiently fit FPGA resources.

Visual tracking is a key component in many computer vision applications. Linear subspace techniques (e.g. eigen-tracking) are one of the most popular approaches to align templates with appearance variations (e.g. illumination, iconic changes). A number of well known tracking algorithms have been proposed in the last years to accurately fit these models to images. Computational efficiency is an important limitation in object tracking algorithms and different efficient techniques, such as the “projected-out” optimization, have been proposed. They reduce the computational cost using an efficient formulation in which many of the involved operations can be precomputed. On the other hand, alternative “simultaneous” algorithms jointly optimize pose and appearance parameters, providing better performance but increasing the computational cost. In this paper, we propose an algorithm for efficient linear appearance model fitting based on the inverse compositional simultaneous optimization of pose and appearance. We introduce a novel formulation which reduces the required computational time while maintaining similar convergence properties of previous “simultaneous” approaches. Experimental results illustrate the capabilities of this algorithm in face tracking.

The Hough transform is a line detection algorithm widely used within image processing applications, showing several variations depending on the shape which is intended to be detected. This paper provides for some new SIMD instructions aided by a specialized look-up table specifically devised for an improved Hough transform algorithm implementation, although they may also be used within other algorithms implementation with a slight modification. The new approach has been tested and evaluated using SimpleScalar tool set.

Due to its inherent data parallelism, image processing applications benefit from multimedia extensions SIMD instructions within general purpose processors. However, current multimedia extensions do not allow to simultaneously address different memory positions using indirect addressing, i. e. the desired memory position address is located within a register. This restriction forces to sequential execution at some program points. This paper shows a new set of instructions providing parallel indirect addressing to a specialized table and intended to be added to existing multimedia extensions. In order to evaluate the new instructions usefulness and feasibility, we have used SimpleScalar for testing some image processing applications, getting in some cases a speed up of 3.5.

In the new multicore architecture arena, the problem of improving the performance of a code is more in the software side than in the hardware one. However, optimizing irregular dynamic data structure based codes for such architectures is not easy, either by hand or compiler assisted. Regarding this last approach, shape analysis is a static technique that achieves abstraction of dynamic memory and can help to disambiguate, quite accurately, memory references in programs that create and traverse recursive data structures. This kind of analysis has promising applicability for accurate data dependence tests in loops or recursive functions that traverse dynamic data structures. However, support for interprocedural programs in shape analysis is still a challenge, especially in the presence of recursive functions. In this work we present a novel fully context-sensitive interprocedural shape analysis algorithm that supports recursion and can be used to uncover parallelism. Our approach is based on three key ideas: i) intraprocedural support based on "coexistent links sets" to precisely describe the memory configurations during the abstract interpretation of the C code; ii) interprocedural support based on "recursive flow links" to trace the state of pointers in previous calls; and Hi) annotations of the read/written heap locations during the program analysis. We present preliminary experiments that reveal that our technique compares favorably with related work, and obtains precise memory abstractions in a variety of recursive programs that create and manipulate dynamic data structures. We have also implemented a data dependence test over our interprocedural shape analysis. With this test we have obtained promising results, automatically detecting parallelism in three C codes, which have been successfully parallelized.

The unfolded and pipelined CORDIC is a high-performance hardware element that produces a wide variety of one and two argument functions with high throughput. The reduction in delay, power, and area (cost) are of significant interest regarding this module due to its high demand for resources. The linear approximation to rotation has been proposed to achieve such reductions. However, the schemes for rotation (multiplication) and vectoring (division) complicate the implementation in a single unit. In this work, we improve the linear approximation scheme, leading to a unified implementation for rotation and vectoring, where fully parallel tree multipliers are used instead of the second half of CORDIC iterations. We also combine the linear approximation to rotation with the scale factor compensation so that the compensation is concurrently performed with the rotation process. We then extend the method to 3D CORDIC. Such an extension is not straightforward due to the lack of existing analytical expressions for the convergence of the algorithm. A comparison, using a rough area-time model and synthesis results, shows that our proposals may achieve significant reductions in delay, with no increase in area, in actual implementations.

Appearance Models have been applied to model the space of human faces over the last two decades. In particular, Active Appearance Models (AAMs) have been successfully used for face tracking, synthesis and recognition, and they are one of the state-of-the-art approaches due to its efficiency and representational power. Although widely employed, AAMs suffer from a few drawbacks, such as the inability to isolate pose, identity and expression changes. This paper proposes Bilinear Active Appearance Models (BAAMs), an extension of AAMs, that effectively decouple changes due to pose and expression/identity. We derive a gradient-descent algorithm to efficiently fit BAAMs to new images. Experimental results show how BAAMs improve generalization and convergence with respect to the linear model. In addition, we illustrate decoupling benefits of BAAMs in face recognition across pose. We show how the pose normalization provided by BAAMs increase the recognition performance of commercial systems.

This paper presents a new pipelined architecture to deal with range reduction for floating point representation. It is based on Horner's scheme and a look-up table. The overall design has been optimized for a module equal to 2π, which is the most widely used due to trigonometric functions requirements. To ensure an accuracy of one unit in the last place (ULP), a complete error propagation study has been carried out.

Block matching motion estimation takes a great part of the processing time for video encoding. To accelerate this process is must to reach real time video coding. The best motion vector is obtained by full-search block matching algorithm which has to be usually implemented by hardware. In recent years, several FPGA based designs have been proposed since these devices support high number of process elements in parallel mode. In this paper a survey of recent architectures to perform the full-search block matching algorithm in FPGAs is presented. A further comparison on terms of frames per second reached, hardware cost in CLB slices and system frequency is presented

In this paper a technique for video cataloging based on logo detection is shown. No a priori knowledge about shape or spatial-temporal location of logos is assumed. The method implements a new algorithm for online logo detection based on temporal and spatial segmentation of broadcasted videos. Temporal segmentation identifies constant luminance regions within video frames while spatial segmentation helps to refine previous segmented regions. In a final step, identified logos are searched in a database and classified into candidate or learnt logotypes. Learnt logos can be directly tracked through the video. Candidate logotypes are assigned to a cluster of similar logos. After a promotion process, all the candidate logos belonging to the same cluster are used to create a new learnt logotype.

In our research, we consider a distributed video-on-demand (VoD) system in which only the most popular videos are replicated in all the servers, whereas the rest of them are distributed through the system following some allocation scheme. In this paper, we present an algorithm to efficiently share the load in such a system and an analytical model that captures the performance of this algorithm, which we validate through simulations. One novelty in our work is that our analytical model lets us relate popularity and partial replication of some of the videos and to predict the user waiting time. We exploit such relationships to assist the system designer to select the size of the servers and network, the optimal number of servers to maintain short waiting time and to predict when the network encounters bottleneck

In this paper we deal with the online addition of multioperands for conventional, carry save (CS) and/or signed-digit (SD) numbers. We propose an online full adder (olFA) as the key element to design trees of adders to deal with multioperands. We also consider mixed inputs (e.g. SD and CS) and how to obtain the output in any of these representations. We show that for dealing with online multioperands it is more efficient to work with online CS trees based on olFAs than with online SD tree based on online SD adders. Finally a novel olFA-based architecture is proposed to directly deal with SD numbers.

The problem of data dependences in pointer-based codes is crucial to various compiler optimizations. The approach presented in this paper focus on detecting data dependences induced by heap-directed pointers on loops that access dynamic data structures. Knowledge about the shape of the data structure accessible from a heap-directed pointer provides critical information for disambiguating heap accesses originating from it. Our approach is based on a previously developed shape analysis that maintains topological information of the connections among the different nodes (memory locations) in the data structure. As a novelty, our approach carries out abstract interpretation of the statements being analyzed, annotating memory locations with read/write information. This information will be later used in a very accurate dependence test, which we describe in this paper. We also discuss its application to three different programs: the sparse matrix-vector product, mst from Olden and twolf from the SPEC CPU2000 suite.

Summary form only given. Most current computers include multimedia features. We use these extensions to compute elementary functions based on polynomial approximations. Hence, we present several alternatives taking advantage of the new attributes on multimedia processors, such as VLIW and SIMD architectures. Our algorithms support the polynomial evaluation in two different ways: the first one is only based in addition/shift operations; while the second uses MAC instructions. Both approximations are analyzed and tailored to subword parallelism units of the new processors. Potential instruction-level and machine-level parallelism are fully exploited through concurrent use of all functional units. A combined approximation using MAC units and addition and shifts is also presented as a third approximation. Two new instructions are also presented here to improve the execution of some of our algorithms.

Among many different multicast approaches, batching and patching are two commonly used policies. In this paper, we propose two hybrid multicast algorithms inspired by the maximum factored queue length (MFQL) batching scheme - used to decide which video queue will be serviced with a multicast session - and by a threshold-based patching scheme - applied to control the partial streams transmission before a threshold is reached during an ongoing multicast session. The novelty is that our algorithms have been designed to efficiently handle the requests in a distributed VoD system while optimizing the usage of the sever/network resources. Precisely, one key issue in the optimization of these resources is the computation of the threshold. We show in this paper how that threshold is derived to deliver a service. In addition, we conduct some simulation experiments that provides us some insightful information about the impact that our threshold based multicast algorithms have in the average waiting time in a distributed VoD system.

Abstract Different parallelization methods for irregular reductions on shared memory multiprocessors have been proposed in the literature in recent years. We have classified all these methods and analyzed them in terms of a set of properties: data locality, memory overhead, exploited parallelism, and workload balancing. In this paper we propose several techniques to increase the amount of exploited parallelism and to introduce load balancing into an important class of these methods. Regarding parallelism, the proposed solution is based on the partial expansion of the reduction array. Load balancing is discussed in terms of two techniques. The first technique is a generic one, as it deals with any kind of load imbalance present in the problem domain. The second technique handles a special case of load imbalance which occurs whenever a large number of write operations are concentrated on small regions of the reduction arrays. Efficient implementations of the proposed optimizing solutions for a particular method are presented, experimentally tested on static and dynamic kernel codes, and compared with other parallel reduction methods. Copyright © 2004 John Wiley & Sons, Ltd.

To successfully exploit all the possibilities of current computer/multicomputer architectures, optimization compiling techniques are a must. However, for codes based on pointers and dynamic data structures, these optimization techniques have to be necessarily carried out after identifying the characteristics and properties of the data structure used in the code. We describe the framework and the analyzer we have implemented to capture complex data structures generated, traversed, and modified in codes based on pointers. Our method assigns a reduced set of reference shape graph (RSRSG) to each statement to approximate the shape of the data structure after the execution of such a statement. With the properties and operations that define the behavior of our RSRSG, the method can accurately detect complex recursive data structures such as a doubly linked list of pointers to trees where the leaves point to additional lists. Several experiments are carried out with real codes to validate the capabilities of our analyzer.

The increasing gap between processor and main memory speeds makes the role of the memory hierarchy behavior in the system performance essential. Both hardware and software techniques to improve this behavior require good analysis tools that help predict and understand such behavior. Analytical modeling arises as a good choice in this field due to its high speed if its traditional limited precision is overcome. We present a modular analytical modeling strategy for arbitrary set-associative caches with LRU replacement policy. The model differs from all the previous related works in its probabilistic approach. Both perfectly and nonperfectly nested loops as well as reuse between different nests are considered by this model, so it makes the analysis of complete programs with regular computations feasible. Moreover, the model achieves good levels of accuracy while being extremely fast and flexible enough to allow its extension. Our approach has been extensively validated using well-known benchmarks. Finally, the model has also proven its ability to drive code optimizations even more successfully than current production compilers.

This paper presents a new method that can be applied by a parallelizing compiler to find, without user intervention, the iteration and data decompositions that minimize communication and load imbalance overheads in parallel programs targeted at NUMA architectures. One of the key ingredients in our approach is the representation of locality as a locality-communication graph (ICG) and the formulation of the compiler technique as a mixed integer nonlinear programming (MINLP) optimization problem on this graph. The objective function and constraints of the optimization problem model communication costs and load imbalance. The solution to this optimization problem is a decomposition that minimizes the parallel execution overhead. This paper summarizes the process of how the compiler extracts the locality information from a nonannotated code and focuses on how this compiler can derive the optimization problem, solve it, and generate the parallel code with the automatically selected iteration and data distributions. In addition, we include a discussion about our model and the solutions - the decompositions - that it provides. The approach presented in the paper is evaluated using several benchmarks. The experimental results demonstrate that the MINLP formulation does not increase compilation time significantly and that our framework generates very efficient iteration/data distributions for a variety of NUMA machines.

In this paper we deal with polynomial evaluation based on new processor architectures for multimedia applications. We introduce some algorithms to take advantage of the new attributes of multimedia processors, such as VLIW (very long instruction word) and SIMD (single instruction multiple data architecture) architectures. Algorithms to support polynomial evaluation based only in addition/shift operations and other different algorithms with MAC (multiply-and-add) instructions are analyzed and tailored to subword parallelism units of the new processors. Both potential instruction-level and machine-level parallelism are fully exploited through concurrent use of all functional units.

In recent years, there has been an increasing interest in video on demand (VoD) systems. We study a distributed VoD system in which the videos are replicated according to their popularity. We present an algorithm to share the load in such a system efficiently and an analytical model that captures the performance of this algorithm, which we validate through simulations. This research shows that popularity is an essential parameter which can save storage without reducing performance by just replicating a few popular videos in all the servers.

The Cray T3D and T3E are non-cache-coherent (NCC) computers with a NUMA structure. They have been shown to exhibit a very stable and scalable performance for a variety of application programs. Considerable evidence suggests that they are more stable and scalable than many other shared-memory multiprocessors. However, the principal drawback of these machines is a lack of programmability, caused by the absence of the global cache coherence that is necessary to provide a convenient shared view of memory in hardware. This forces the programmer to keep careful track of where each piece of data is stored, a complication that is unnecessary when a pure shared-memory view is presented to the user. We believe that a remedy for this problem is advanced compiler technology. In this paper, we present our experience with a compiler framework for automatic parallelization and communication generation that has the potential to reduce the time-consuming hand-tuning that would otherwise be necessary to achieve good performance with this type of machine. From our experiments, we learned that our compiler performs well for a variety of applications on the T3D and T3E and we found a few sophisticated techniques that could improve performance even more once they are fully implemented in the compiler.

Dynamic and pointer-based data structures are widely used in symbolic or irregular C codes. However there is still a lack of compiler techniques to deal with the automatic optimization of such codes. In this paper we take a first step towards this final objective: the automatic identification of the data structure used in the code. More precisely, we describe the framework and the compiler we have implemented to capture complex data structures generated, traversed, and modified in C codes. Our method assigns a reduced set of reference shape graphs (RSRSG) to each sentence to approximate the shape of the data structure after the execution of such a sentence. With the properties and operations that define the behavior of our RSRSG, the method can accurately detect complex recursive data structures. The compiler makes a progressive analysis in which the level of detail is increased during the analysis when needed. Several experiments are carried out with complex data structures to validate the capabilities of our compiler.

Complexity in real codes is sometimes due to the utilization of multi-vector data structures, but there are not many compile-time approaches dealing with this problem, Moreover current compilation techniques only analyze single vectors. This paper describes how the performance can be improved if semantical bindings are taken into account during the parallelization. Our approach is a first step to converge from the data-parallel paradigm to the automatic parallelization, by reducing the number of directives on code. We apply a multi-loop analysis and a sparse privatization to replace the owner computes rule. Additionally, our support will be able to parallelize loops with some of levels of indirections on a left-hand side. In this paper, we also present three alternatives to store the sending information, and two algorithms to calculate coordinates from pointers. Both issues have a critical importance when the parallelized algorithm requires a sparse communication.

Much effort has been devoted recently to efficiently parallelize irregular reductions. In this paper, parallelizing techniques for these computations are analyzed in terms of three performance aspects: parallelism, data locality and memory overhead. These aspects have a strong influence in the overall performance and scalability of the parallel code. We will discuss how the parallelization techniques usually try to optimize some of these aspects, while missing the other(s). We will show that by combining complementary techniques we can improve the overall performance/scalability of the parallel irregular reduction, obtaining an effective solution for large problems on large machines. Specifically, a combination of array expansion and a locality-oriented method (DWA-LIP), named partial array expansion, is introduced. An implementation of the proposed method is discussed, showing that the transformation that the compiler must apply to the irregular reduction code is not excessively complex. Finally, the method is analyzed and experimentally evaluated.

This paper presents a general data-parallel formulation for a class of problems based on the divide and conquer strategy. A combination of three techniques—mapping vectors, index-digit permutations and space-filling curves—are used to reorganize the algorithmic dataflow, providing great flexibility to efficiently exploit data locality and to reduce and optimize communications. In addition, these techniques allow the easy translation of the reorganized dataflows into HPF (High Performance Fortran) constructs. Finally, experimental results on the Cray T3E validate our method.

Wavelet Packet Transform (WPT) provides good spectral and temporal resolutions in arbitrary regions of the time-frequency plane. Given an additive cost function, a best-tree searching algorithm allows the selection of the best basis for a given signal according to this function. This adaptive choice of the time-frequency tiling benefits most of the applications where the standard Wavelet Transform (WT) has already shown to be useful. Though many specific architectures have been proposed in the literature for the WT, it is not the case for WPT. In this work we present a specific architecture for WPT which implements the best-tree searching algorithm.

Wavelet packets have been applied in order to compensate the speech signal to improve the intelligibility for a common hearing impairment known as recruitment of loudness, a sensorineural hearing loss of cochlear origin. We present an architecture that allows selection of the best decomposition tree for each patient, in order to apply this wavelet-packet based parametric compression algorithm.

A new approach to the detection of shapes under global deformations is presented. The algorithm is based in the combination of a generalized Hough transform (GHT) and an universal evolutionary global optimizer (UEGO). This method exploits the invariant characteristics to rotation, scale and displacement of the GHT to detect shapes deformed by a global deformation model, and without an initial positioning of the template. The GHT is used as an objective function for the UEGO, an optimizer that is able to find multiple optima with a low computational cost.

This paper presents a new parallelization method for reductions of arrays with subscripted subscripts on scalable shared memory multiprocessors. The mapping of computations is based on grouping reduction loop iterations into sets that are further assigned to the cooperating threads of computation. Iterations belonging to the same set are chosen in such a way that update different entries in the reduction array. That is, the loop distribution implies a conflict-free write distribution of the reduction array. The iteration sets are set up by building a loop-index prefetching data structure that allows to reorder properly the loop iterations. The proposed method is general, scalable, and easy to implement on a compiler. In addition it deals in a uniform way with one and multiple subscript arrays. In case of multiple indirection arrays, writes on the reduction array affecting different sets are solved by defining conflict-free supersets. A performance evaluation is presented. From the experimental results and performance analysis, the proposed method appears as a clear alternative to the array expansion and privatized buffer techniques, used on state-of-the-art parallelizing compilers, like Polaris or SUIF. The scalability problem that those techniques exhibit is missing in our method, as the memory overhead presented does not depend on the number of processors.

In this paper we design a CORDIC architecture for variable-precision, and a new algorithm is proposed to perform the interval sine and cosine functions. This system allows us to specify the precision to perform the sine and cosine functions, and control the accuracy of the result, in such a way that recomputation of inaccurate results can be carried out with higher precision. An important reduction in the number of iterations is obtained by taking advantage of the differential angle, and the number of cycles per iteration is reduced by avoiding the additions of the leading all zero words. As a consequence, the computation time of the interval function evaluation obtained is close to that of a point function evaluation. The problem of the large table of angles and the scale factor compensation involved in a high precision CORDIC has been solved efficiently.

Most of today's multiprocessors have a Distributed-Shared Memory (DSM) organization, which enables scalability while retaining the convenience of the shared-memory programming paradigm. Data locality is crucial for performance in DSM machines, due to the difference in access times between local and remote memories. In this paper, we present a compile-time representation that captures the memory locality exhibited by a program in the form of a graph known as Locality-Communication Graph (LCG). In the LCG, each node represents a DO loop nest which can have at most one level of parallelism. Not all loops need to be represented within a node and, therefore, the LCG may contain cycles. Our representation works whether the loops represented by the nodes are perfectly nested or not, and the subscript expressions and loop limits can be affine or non-affine expressions of the loop indices. The LCG provides essential information that a parallelizing compiler can use to automatically choose a good iteration/data distribution and to schedule the communication operations required during program execution.

Automaticparallelization of codes with complex data structures is becoming very important.These complex, and often, recursive data structures are widely used in scientific computing.Shape analysis is one of the key steps in the automatic parallelization of such codes.In this paper we extend the Static Shape Graph (SSG) method to enable the successful and accurate detection of complex doubly linked structures.In addition, these techniques have been implemented in a compiler, which has been validated for several C codes.In particular, we present the results the compiler achieves for the C sparse LU factorization algorithm.The output SSG for this case study perfectly describes the complex data structure used during the LU code.'This work was supported by the

Real time image processing uses SIMD engines to accelerate the computation of algorithms such as the DCT, FFT or DWT. So, a good skewing scheme becomes essential for avoiding memory bank conflicts. A memory system is introduced for the efficient in-place computation of such transforms. It consists of M=2/sup m/ memory modules, providing parallel access to M image points whose patterns are a row or a column, the interval in both cases being 2/sup l/, l/spl ges/0. The efficiency of our design is proved through the computation of the 2D DWT.

While much work has been devoted to the study of cache behavior during the execution of codes with regular access patterns, little attention has been paid to irregular codes. An important portion of these codes are scientific applications that handle compressed sparse matrices. In this work a probabilistic model for the prediction of the number of misses on a K-way associative cache memory considering sparse matrices with a uniform or banded distribution is presented. Two different irregular kernels are considered: the sparse matrix-vector product and the transposition of a sparse matrix. The model was validated with simulations on synthetic uniform matrices and banded matrices from the Harwell-Boeing collection. Keywords: Sparse matrix, irregular computation, cache performance, probabilistic model. 1 Introduction Sparse matrices are in the kernel of many numerical applications. Their compressed storage [2], which permits both operations and memory savings, generates irregular access ...

MOTIVATION: The explosive growth of the biological sequences databases stimulated by genome projects has modified the framework of several applications in the biological sequence analysis area. In most cases, this new scenario is characterized by studies on large sets of sequences, suggesting the need for effective and automatic methods for their clustering. A more effective clustering of the database could be followed by the application of common family analysis schemes to the groups so formed. RESULTS: In this work, we present a new strategy to reduce the computational cost associated with the clustering of large sets of sequences which are expected to contain several families. The strategy is based on the grouping of the sequences into families by using a dynamic threshold on a pairwise sequence similarity criterion. Routine clustering of large data sets can now be done very efficiently. The method developed here achieves a computational space reduction of about an order of magnitude over more traditional ones of all-versus-all comparisons. The outcome of this approach produces family groupings that reproduce closely already accepted biological results. Our work includes a parallel implementation for distributed memory multiprocessors with a dynamic scheduling strategy for performance optimization. AVAILABILITY: By anonymous ftp at ftp.ac.uma.es (/pub/ots/pCluster directory), or from our Web site http://www.cnb. uam.es/www/software/software_index.html CONTACT: [email protected]

This paper presents a new design for two operand normalization. The two operand normalization operation involves the normalization of at least one of two operands by left shifting both by the same amount. Our design performs the computation of the shift by making an OR of the bits of both operands in a tree network, encoding the position of the first nonzero bit. The encoded position is obtained most significant bit first, and then there is an overlapping with the shifting operation. The design we propose replaces two leading zero detector circuits and a comparator, that are present in the conventional approach. Our scheme demonstrates to be more area efficient than the conventional one. The circuit we propose is useful in floating point complex multiplication and COordinate Rotation DIgital Computer (CORDIC) processors.

The cosine transform (DCT) is in the core of image encoding and compression applications. We present a new architecture to efficiently compute the fast direct and inverse cosine transform which is based on reordering the butterflies after their computation. The designed architecture exploits locality, allowing pipelining between stages and saving memory (in place). The result is an efficient architecture for high speed computation of the DCT that reduces significantly the area required to VLSI implementation.

The Polaris restructurer transforms conventional Fortran programs into parallel form for various types of multiprocessor systems. This paper presents the results of a study on strategies to improve the effectiveness of Polaris' techniques for distributed-memory multiprocessors. Our study, which is based on the hand analysis of MDG and TRFD from the Perfect Benchmarks and TOYCATV and SWIM from SPEC benchmarks, identified three techniques that are important for improving communication optimization. Their application produces almost perfect speedups for the four programs on the Cray T3D.

In this paper, we consider the errors appearing in angle computations with the CORDIC algorithm (circular and hyperbolic coordinate systems) using fixed-point arithmetic. We include errors arising not only from the finite number of iterations and the finite width of the data path, but also from the finite number of bits of the input. We show that this last contribution is significant when both operands are small and that the error is acceptable only if an input normalization stage is included, making unsatisfactory other previous proposals to reduce the error. We propose a method based on the prescaling of the input operands and a modified CORDIC recurrence and show that it is a suitable alternative to the input normalization with a smaller hardware cost. This solution can also be used in pipelined architectures with redundant carry-save arithmetic.

Traditionally, CORDIC algorithms have employed radix-2 in the first n/2 microrotations (n is the precision in bits) in order to preserve a constant scale factor. The authors present a full radix-4 CORDIC algorithm in rotation mode and circular coordinates and its corresponding selection function, and propose an efficient technique for the compensation of the nonconstant scale factor. Three radix-4 CORDIC architectures are implemented: 1) a word serial architecture based on the zero skipping technique, 2) a pipelined architecture, and 3) an application specific architecture (the angles are known beforehand). The first two are general purpose implementations where redundant (carry-save) or nonredundant arithmetic can be used, whereas the last one is a simplification of the first two. The proposed architectures present a good trade-off between latency and hardware complexity when compared with existing CORDIC architectures.

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages.

Vienna Fortran, High Performance Fortran (HPF), and other data parallel languages have been introduced to allow the programming of massively parallel distributed-memory machines (DMMP) at a relatively high level of abstraction, based on the SPMD paradigm. Their main features include directives to express the distribution of data and computations across the processors of a machine. In this paper, we use Vienna-Fortran as a general framework for dealing with sparse data structures. We describe new methods for the representation and distribution of such data on DMMPs, and propose simple language features that permit the user to characterize a matrix as "sparse" and specify the associated representation. Together with the data distribution for the matrix, this enables the complier and runtime system to translate sequential sparse code into explicitly parallel message-passing code. We develop new compilation and runtime techniques, which focus on achieving storage economy and reducing communication overhead in the target program. The overall result is a powerful mechanism for dealing efficiently with sparse matrices in data parallel languages and their compilers for DMMPs.

The main part of the Viterbi algorithm is a nonlinear feedback loop which presents a bottleneck for high-speed implementations. We present a novel scheduling scheme that allows increasing the available speed of the system. This is done through the utilization of look-ahead techniques to compute non-sequential data and, in this way, break the recursivity of the algorithm. This permits introducing pipelining. As a result, we obtain a speed growth comparable to previous parallel solutions, but with less hardware cost.

In this paper we present a new CORDIC algorithm for the vectoring mode, based on the use of radix-4 preserving a complexity in the microrotations that is similar to that of the conventional radix-2 CORDIC. The use of this radix, together with the inclusion in the CORDIC algorithm of the zero skipping technique, reduces by more than half the number of iterations with respect to the conventional radix 2 CORDIC, with the consequent reduction of time in recursive architectures or area in pipelined architectures. In processes such as SVD or matrix triangularization in which the evaluation of the rotation angle is required, this algorithm is shown to be specially efficient.

Trellis coded quantization (TCQ) is an efficient technique for encoding memoryless sources. Furthermore TCQ can be incorporated into a transform coding structure (such as the discrete cosine transform) for encoding monochrome and color images with fixed rate or entropy-constrained schemes. In all these cases an expanded codebook is partitioned into subsets used to label the branches of an appropriate graph (trellis). For a given data sequence, the Viterbi algorithm is then used to find the minimum mean square error path through the trellis. We present a generic architecture scheme that can be easily adapted to the different TCQ image compression methods. We also present a formal model that permits a regular and modular design solution that is optimal for a particular set of area and/or speed constraints.

There are a series of very efficient sequential algorithms that generate irregular trees during the process of detecting shapes in images. These algorithms are based on the fast Hough transform and are used for solving the most complex stages of detection when the production of the parameters is uncoupled. However, the parallelization of these algorithms is complex, and the problem of load distribution is crucial. We present three parallel algorithms for solving this problem. One of the solutions employs static load balancing. The other two use dynamic balancing with two different control policies: distributed and centralized. These algorithms may also be used for solving other problems, such as the branch and bound, that generate irregular trees.

Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since non-zero elements are unevenly scattered and are accessed via multiple levels of indirection. Distributions that achieve good load balance and locality are hard to compute and also lead to further indirection in locating distributed data. This paper evaluates alternative distribution strategies which trade off the quality of load-balance and locality for lower decomposition costs and efficient lookup. The proposed techniques are compared with previous strategies for parallelizing sparse matrix problems and the relative merits of each method is outlined. 1 Introduction Sparse matrices are used in a large number of important scientific codes, such as molecular dynamics, CFD solvers, finite element methods and climate modelling. Unfortunately, these applications are hard to parallelize efficiently, particularly using automated compiler techniques. This is because sparse matrices are repre...

We present a unified mixed radix CORDIC algorithm with carry-save arithmetic with a constant scale factor. The pipelined architecture of the processor is determined by a unique sequence of microrotations for the two modes of operation (rotation and vectoring) in circular and hyperbolic coordinates. The combination of radix-2 and radix-4 microrotations allows us to reduce the latency and size of the pipeline significantly. The unified algorithm is based on the correcting microrotation method, which we have extended to the vectoring mode in hyperbolic coordinates. We have also generalized the use of radix-4 microrotations to the two operation modes and coordinate systems.

We present a Cordic rotator, using carry-save arithmetic, based on the prediction of all the coefficients into which the rotation angle is decomposed. The prediction algorithm is based on the use of radix-2 microrotations with multiple shifts in the first iterations and the use of a redundant radix-2 and radix-4 representation for the coefficients in the rest of the microrotations. The use of multiple shifts facilitates the prediction of the coefficients in the case of microrotations where i/spl les/n/4, being n the precision of the algorithm, and the use of radix-4 microrotations helps to reduce the total number of iterations. The prediction is carried out using the redundant representation of the z coordinate, without any need for conversions to a non-redundant representation. Finally, we present a VLSI architecture based on this algorithm. As the production of the coefficients is very fast, and they are known before starting each microrotation, the resulting architecture can be highly pipelined and consequently appropriate for applications where high speeds are required.>

Many applications figure the evaluation of rotations at high speeds. However there is a trade-off between the chip area and the latency. In this paper we develop a digit on-line pipelined array architecture based on the radix-4 CORDIC algorithm in rotation mode. The radix-4 CORDIC algorithm halves the number of microrotations with respect the traditionally radix-2 algorithm with the drawback of a non-constant scale factor. Seeking a good compromise between silicon area and latency we have used digit on-line processing. This way the data inputs the processor in blocks of bits (digits) in MSD-first mode of processing. We have used redundant carry-save arithmetic to allow carry-free additions and on-line processing. The designed processor demonstrates to have a better performance than previous digit on-line architectures.

The compensation of scale factor imposes significant computation overhead on the CORDIC algorithm. In this paper we will propose two algorithms and architectures in order to perform the compensation of the scale factor in parallel with the computation of the CORDIC iterations. This way it is not necessary to carry out the final multiplication or add scaling iterations in order to achieve the compensation. With the architectures we propose the dependence on n of the compensation of the scale factor disappears, and this considerably reduces the latency of the system. The architectures developed are optimized solutions for the different operating modes of the CORDIC both in conventional and in redundant arithmetic.

This paper describes new compiler and run-time techniques to handle array accesses involving several levels of indirection such as those arising in sparse and irregular problems. The lack of information at compile-time in such problems has typically required the insertion of expensive runtime support. We propose new data distributions which can be used with standard sparse matrix representations to achieve much more efficient resolution of indirections at runtime. Unlike previous methods, our techniques require only a single communication phase to access non-local data, even in the presence of multiple levels of indirections. Likewise, the methods presented here are novel in that they allow the compiler to use the semantic relations of the array elements involved in the indirect accesses to perform a number of optimizations.

We present an approach to the study of the relationships between biological sequences and structures applying image analysis methods to dotplots. We introduce a set of analytical tools based on different types of digital image-processing filters that are new within the context of dotplots. We have reformulated some of the usual approaches in dotplot analysis as mathematical operations on images within the framework of mathematical morphology. An X-Window-based implementation of this new approach has been developed and is available by anonymous FTP.

The authors describe a new algorithm for the fast Hough transform (FHT) that satisfactorily solves the problems other fast algorithms propose in the literature-erroneous solutions, point redundance, scaling, and detection of straight lines of different sizes-and needs less storage space. By using the information generated by the algorithm for the detection of straight lines, they manage to detect the segments of the image without appreciable computational overhead. They also discuss the performance and the parallelization of the algorithm and show its efficiency with some examples.

We present a new parallel computing approach to the case of exhaustive sequential sequence comparison algorithms on message-passing architectures. In this context a modification of guided self-scheduling as well as efficient buffering strategies are presented. We discuss two specific implementations, one on the Paramid parallel computer, and the other on a cluster of workstations running PVM. In both cases the parallel performance is higher than with any other method presented so far. The code is public domain and can be obtained by anonymous ftp at ftp.cnb.uam.es.

The solution of tridiagonal systems is a topic of great interest in many areas of numerical analysis. Several algorithms have recently been proposed for solving triadiagonal systems based on the Divide and Conquer (DC) strategy. In this work we propose a unified parallel architecture for DC algorithms which present the data flows of the Successive Doubling, Recursive Doubling and Parallel Cyclic Reduction methods. The architecture is based in the perfect unshuffle permutation, which transforms these data flows into a constant geometry one. The partition of the data arises in a natural manner, giving way to a systolic data flow with a wired control section. We conclude that the constant geometry Cyclic Reduction architecture is the most appropriate one for solving tridiagonal systems and, from the point of view of integration in VLSI technology, is the one which uses the least amount of area and the smallest number of pins.>

We present an unified parallel architecture for four of the most important fast orthogonal transforms with trigonometric kernel: Complex Valued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cosine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be transformed on a constant geometry flow using perfect unshuffle or shuffle permutations. The other three require some type of hardware modification to guarantee the constant geometry of the successive doubling method. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section permits the evaluation of the CFFT and FCT transforms in n data recirculations and the RFFT and FHT transforms in n-1 data recirculations, with n being the number of stages of a transform of length N=r/sup n/. Also, the efficiency of the partitioned parallel architecture is optimum because there is no cycle loss in the systolic computation of all the butterflies for each of the four transforms.>

An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N=2/sup n/ data items is considered as input. The system calculates the FHT and the FFT in n and n+1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (Nlog/sub 2/N)/4Q cycles for the FHT and N(1+log/sub 2/N)/4Q cycles for the FFT, where Q is the number of processors (Q= 2/sup q/, Q>

A semisystolic architecture is presented for the parallel calculation of the decimation in time and radix-2 fast Hartley transform (FHT) of a real sequence with N=2/sup n/ data items. The architecture is based on a constant geometry algorithm for computing the FHT which facilitates its mapping in VLSI technology and minimizes the communications among processors. The circuit proposed is characterized by its modular design and its interconnective regularity. It permits the computation of arbitrarily sized FHTs as a consequence of the partition of the data and the recirculation of partial results over the processing units in the successive stages of the transform. Each calculation stage requires N/4Q cycles where Q is the number of processors (Q=2/sup q/). The total calculation time is (Nlog/sub 2/N)/4Q cycles.>

This paper describes ACLE (Array C Language Emulator), a software package comprising an ACLAN-to-C translator and a library of simulation routines enabling the execution of programs written in ACLAN to be simulated on a conventional sequential computer. Array C LANguage (ACLAN) is a machine-independent programming language that extends C by endowing it with structures for programming array processors. ACLAN was successfully proven by developing many parallel algorithms for hypercube computers. An algorithmic solution for mapping algorithms onto these computers is explained.