The aim of this paper is to present a novel reconfigurable architecture support which provides efficient access to noncontiguous locations in an array-like structure, whether it be memories or configurable logic blocks (Claw) in reconfigurable systems. This distribution tree (distTree) architecture serves as a mean of address resolution so that no addressing information is required externally or explicitly. It not only reduces the amount of information transferred but also reduces the time for address resolution significantly. A software and a hardware simulators were developed to test the correctness, performance, and hardware resources required for distTree. We found from our simulators that the run-time overhead for address resolution is close to none in most cases while occupying a reasonable amount of hardware area.

Reconfigurable computing devices such as FPGAs offer application developers the ability to create solutions with a performance comparable to that of a hardware solution, but with the flexibility of software. Development tools that attempt to support popular software development languages such as C and Java have been developed to reduce the need for the FPGA developer to be trained in hardware design practices, however the tools have not been successful in mirroring all of the languages functionality. In particular most tools do not support programming with recursive functions. Previous research on mapping recursive functions to reconfigurable hardware has built a stack on the device which does not take full advantage of the massive amount of parallel resources on the reconfigurable device. This paper describes a method for mapping recursive functions to reconfigurable hardware without the use of a stack. It does this by unrolling the function on the device as it is executing. The results presented in this paper show that using this method can result in a significant performance increase when compared to a stack based implementation.

Abstract — In the absence of a cost-effective technology for storing optical signals, emerging optical packet switched (OPS) networks are expected to have severely limited buffering capability. This paper investigates the resulting impact on end-to-end loss and throughput, and proposes that the optical edge switches “pace ” packets into the OPS core to improve performance without adversely affecting end-to-end delays. In this context, our contributions are three-fold. We first evaluate the impact of short buffers on the performance of real-time and TCP traffic. This helps us identify short-time-scale burstiness as the major contributor to performance degradation, so we propose that the optical edge switches pace the transmission of packets into the OPS core while respecting their delay-constraints. Our second contribution develops algorithms of poly-logarithmic complexity that can perform optimal real-time pacing of high data rate traffic. Lastly, we show via simulations of a realistic network carrying real-time traffic that pacing can significantly reduce losses at the expense of a bounded increase in end-to-end delay. The loss-delay trade-off mechanism provided by pacing can help achieve desired OPS network performance. I.

Recursive solutions are effective software techniques that are difficult to map into hardware due to their dependency on input size and data values. As a result, most high-level design tools do not allow for recursive calls. In this paper we present a technique for mapping the merge-sort algorithm, as a case study, into a reconfigurable system. Our mapping employs an on-line prediction method to reconfigure the necessary hardware only when the need arises, and to hide the reconfiguration delay. As a result, our implementation uses the smallest possible size hardware to sort an input data stream without prior knowledge of its length and eliminates the reconfiguration delay penalty. We outline a reconfigurable system with self-organizing multiple-buses as the communication subsystem. The processing elements and memory modules are connected to the multiple-buses as a linear array. We also demonstrate the effectiveness of adding simple LUTs to the multiple-buses in improving the throughput by allowing for pipelining at the word level.

Parallelized FTP (P-FTP) approach, attempts to solve the problem of slow downloads of large multimedia files while optimizing the utilization of mirror servers. The approach presented in this paper downloads a single file from multiple mirror servers simultaneously, where each mirror server transfers a portion of the file. P-FTP server calculates the optimum division of the file for efficient transfer. The dynamic monitoring ability of P-FTP maintains the file transfer process at the optimized level no matter how abruptly network and mirror server characteristics change.

In this paper we report on our experimentation with the use of FPGA-based system to solve the irregular computation problem of evaluating y = Ax when the matrix A is sparse. The main features of our matrix-vector multiplication algorithm are (i) an organization of the operations to suit the FPGA-based system ability in processing a stream of data, and (ii) the use of distributed arithmetic technique together with an efficient scheduling heuristic to exploit the inherent parallelism in the matrix-vector multiplication problem. The performance of our algorithm has been evaluated with an implementation on the Pamette FPGA-based system.

We propose to modify a type of ant algorithm called Population based Ant Colony Optimization (P-ACO) to allow implementation on an FPGA architecture. Ant algorithms are adapted from the natural behavior of ants and used to find good solutions to combinatorial optimization problems. General layout on the FPGA and algorithmic description are covered The most notable achievements featured in this paper are a runtime reduction and including the approximation of the heuristic function by a small set of favored decisions which changes over time.

No abstract available.

We introduce the unoriented $\Theta$-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented $\Theta$-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented $\Theta$-maximum of a set of planar points when $\Theta=\pi/2$.

In this paper, we introduce a simple and efficient algorithm for computing the Voronoi Diagram for n planar points on a reconfigurable mesh of size O(n)/spl times/O(n). The algorithm has a worst case running of O(log n log log n) time. The algorithm exploits the O(1) communication diameter of the reconfigurable mesh model to implement efficient load balancing.

The heart of a massively parallel computer is its interconnection network. In this article we present a reconfigurable multiple bas network to support circuit switching as means of communication between processors of a multiprocessor machine. The main contribution of the papers is in demonstrating the simplicity of the routing hardware whilst still providing modularity and full utilization of the multiple bus system. A comparison with major interconnection network is also presented.

A set P of points in Rd is called simplicial if it has dimension d and contains exactly d + 1 extreme points. We show that when P contains n interior points, there is always one point, called a splitter, that partitions P into d + 1 simplices, none of which contain more than dn /(d + 1) points. A splitter can be found in O (d4n) time. Using this result, we give a O (d4n log1+1/dn) algorithm for triangulating simplicial point sets that are in general position. In R3 we give an O (n logn + k) algorithm for triangulating arbitrary point sets, where k is the number of simplices produced. We exhibit sets of 2n + 1 points in R3 for which the number of simplices produced may vary between (n -1)2 + 1 and 2n -2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.

A new optimal algorithm for computing the convex hull of a simple polygon in the plane, along with a proof of correctness, is presented. The main novelty of the proposed algorithm is its use of existing concepts such as the unimodality of the area of a triangle inscribed in a convex polygon and Sldansky's scan. The combination of these concepts gives us new insight into the problem.

A new approach is presented to the classification problem of planar shapes represented by polygons. A shape is abstracted combinatorially by means of its visibility graph, and two shapes are deemed similar whenever their graphs are cyclically isomorphic. Efficient algorithms are presented for performing these operations.