We first argue that the spectrum of processor architectures from general-purpose processors (GPPs) to application-specific processors (ASPs) to FPGA coprocessors is narrowing (but not converging), due to some dominating physical and economic forces. We then suggest some research opportunities driven by these forces

Abstract Javelin 3 is a software system for developing large‐scale, fault‐tolerant, adaptively parallel applications. When all or part of their application can be cast as a master–worker or branch‐and‐bound computation, Javelin 3 frees application developers from concerns about inter‐processor communication and fault tolerance among networked hosts, allowing them to focus on the underlying application. The paper describes a fault‐tolerant task scheduler and its performance analysis. The task scheduler integrates work stealing with an advanced form of eager scheduling. It enables dynamic task decomposition, which improves host load‐balancing in the presence of tasks whose non‐uniform computational load is evident only at execution time. Speedup measurements are presented of actual performance on up to 1000 hosts. We analyze the expected performance degradation due to unresponsive hosts, and measure actual performance degradation due to unresponsive hosts. Copyright © 2005 John Wiley & Sons, Ltd.

Javelin is a Java-based infrastructure for global computing. This paper presents Javelin++, an extension of Javelin, intended to support a much larger set of computational hosts. Contributions to scalability and fault tolerance are presented. This is the focus of the paper. Two scheduling schemes are presented: probabilistic work stealing and deterministic work stealing. The distributed deterministic work stealing is integrated with a distributed deterministic eager scheduler, which is one of the paper's primary original contributions. An additional fault tolerance mechanism is implemented for replacing hosts that have failed or retreated. A Javelin++ API is sketched, then illustrated on a raytracing application. Performance results for the two schedulers are reported, indicating that Javelin++, with its broker network, scales better than the original Javelin. Copyright © 2000 John Wiley & Sons, Ltd.

Java offers the basic infrastructure needed to integrate computers connected to the Internet into a seamless distributed computational resource: an infrastructure for running coarse-grained parallel applications on numerous, anonymous machines. First, we sketch such a resource's essential technical properties. Then, we present Javelin, an infrastructure for global computing. The system is based on Internet software that is interoperable, increasingly secure and ubiquitous: Java-enabled Web technology. Ease of participation is seen as a key property for such a resource to realize the vision of a multiprocessing environment comprising thousands of computers. Javelin's architecture and implementation require participants to have access to only a Java-enabled Web browser. The security constraints implied by this, the resulting architecture and the current implementation are presented. The Javelin architecture is intended to be a substrate on which various programming models may be implemented. Different computation servers, each corresponding to a different programming model, are supported by Javelin's architecture. Several are presented briefly. Experimental results are given in the form of micro-benchmarks, a Mersenne Prime application and a ray-tracing application that run on a heterogeneous network of several parallel machines, workstations and PCs. © 1997 John Wiley & Sons, Ltd.

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n/sub x//spl times/n/sub y//spl times/n/sub z/ directed rectilinear mesh. Its completion requires at least n/sub x/+n/sub y/+n/sub z/-2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. Lower bounds are shown for the n/sub x//spl times/n/sub y//spl times/n/sub z/ directed mesh, and these bounds are shown to be exact by constructing a processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is either a two dimensional mesh or skewed cylinder. The contribution of this paper is two-fold: It generalizes the previous work on cubical mesh algorithms, and it presents a more elegant mathematical method for deriving processor-time lower bounds for such problems.

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n/spl times/n/spl times/n/spl times/n directed mesh. Its completion requires at least 4n-3 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the 4D mesh, such a schedule requires at least (2/3)n/sup 3/+n/3 processors. This lower bound is shown to be exact by constructing a processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a 3-dimensional twisted torus.>

Using a directed acyclic graph (dag) model of algorithms, we investigate precedence-constrained multiprocessor schedules for the n/spl times/n/spl times/n directed mesh. This cubical mesh is fundamental, representing the standard algorithm for square matrix product, as well as many other algorithms. Its completion requires at least 3/sup n/spl minus/2/ multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the cubical mesh, such a schedule requires at least /spl lsqb/3n/sup 2//4/spl rsqb/ processors. Among such schedules, one with the minimum period (i.e., maximum throughput) is referred to as a period-processor-time-minimal schedule. The period of any processor-time-minimal schedule for the cubical mesh is at least 3/sup n/2/ steps. This lower bound is shown to be exact by constructing, for n a multiple of 6, a period-processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a toroidally connected n/2/spl times/n/2/spl times/3 mesh.>

The paper, using a direct acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n /spl times/ n /spl times/ n directed mesh. This cubical mesh is fundamental, representing the standard algorithm for square matrix product, as well as many other algorithms. Its completion requires at least 3n - 2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. For the cubical mesh, such a schedule requires at least [3n/sup 2//4] processors. Among such schedules, one with the minimum period (i.e., maximum throughput) is referred to as a period-processor-time-minimal schedule. The period of any processor-time-minimal schedule for the cubical mesh is at least 3n/2 steps. This lower bound is shown to be exact by by constructing, for n a multiple of 6, a period-processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is a toroidally-connected n/2 /spl times/ n/2 /spl times/ 3 mesh.>

A systolic super summer is a cellular apparatus for summing floating-point numbers. The apparatus receives floating-point summands, converting them to fixed-point within a sieve-like cellular array. The emerging fixed-point numbers are summed in a pipelined array of long accumulators. An improved design is presented for the summer's sieve. Although the new sieve is structurally simpler and uses less hardware, the throughput per unit area is the same as that for the previously designed sieve. The new sieve's architectural regularity makes it ideal for implementation in VLSI circuit technology.>

Using a directed acyclic graph (DAG) model of algorithms, the paper focuses on time-minimal multiprocessor schedules that use as few processors as possible. Such a processor-time-minimal scheduling of an algorithm's DAG first is illustrated using a triangular shaped 2-D directed mesh (representing, for example, an algorithm for solving a triangular system of linear equations). Then, algorithms represented by an n*n*n directed mesh are investigated. This cubical directed mesh is fundamental; it represents the standard algorithm for computing matrix product as well as many other algorithms. Completion of the cubical mesh required 3n-2 steps. It is shown that the number of processing elements needed to achieve this time bound is at least (3n/sup 2/4/). A systolic array for the cubical directed mesh is then presented. It completes the mesh using the minimum number of steps and exactly (3n/sup 2/4/) processing elements it is processor-time-minimal. The systolic array's topology is that of a hexagonally shaped, cylindrically connected, 2-D directed mesh.>

Using a directed acyclic graph (DAG) model of algorithms, the authors focus on processor-time-minimal multiprocessor schedules: time-minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo, and Lewis (KLL) algorithm for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 parallel steps. As originally reported. their systolic array comprises n/sup 2/ processing elements. It is shown that any time-minimal multiprocessor schedule of the KLL algorithm's dag needs at least n/sup 2//3 processing elements. Then a processor-time-minimal systolic array realizing the KLL dag is constructed. Its processing elements are organized as a cylindrically connected 2-D mesh, when n=0 mod 3. When n not=0 mod 3, the 2-D mesh is connected as a torus.>

A directed acyclic graph (DAG) model of algorithms is used. For a given DAG the authors focus on processor-time minimal multiprocessor schedules: time minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo and Lewis (KLL) algorithm (S.-Y. Kung et al., 1987) for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 steps. Their systolic array comprises n/sup 2/ processing elements. Here, it first is shown that any multiprocessor that achieves this 5n-4 time bound needs at least (n/sup 2//3) processing elements. Then, a processor-time minimal systolic array realizing the KLL algorithm's DAG is constructed. Its (n/sup 2//3) processing elements are organized as a cylindrically connected 2-D mesh, when n identical to 0 mod 3. When n is not identical to 0 mod 3, the 2-D mesh is connected as a twisted torus.>

Iterative logic arrays (ILAs) are studied with respect to two testing problems. First, a variety of conditions is presented. Meeting these conditions guarantees an upper bound on the size of the test set for the ILA under consideration. Second, techniques for designing optimally testable ILAs are presented. The arrays treated are, in some cases, more general than those that have been reported by other researchers: they include multidimensional and inhomogeneous arrays. Octagonally connected arrays and bilateral arrays are also discussed. The results indicate that the characteristics of the individual cell functions (e.g. whether they are bijective) are a good guide to the test complexity of the overall array. Matrix multiplication, as an example, is shown to have several different optimally testable implementations. The results are useful for combinational and pipelined arrays and for certain systolic arrays.>

The authors present several time-optimal and space-time-optimal systolic arrays for computing a process dependence graph corresponding to the mixed-radix conversion algorithm. The arrays are particularly suitable for software implementations of algorithms from the applications of residue number systems on a programmable systolic/wavefront array. Examples of such applications are the exact solution of linear systems and matrix problems over integral domains. The authors also describe a decomposition strategy for treating a mixed-radix conversion problem whose size exceeds the array size.>

A principal limitation in accuracy for scientific computation performed with floating-point arithmetic is due to the computation of repeated sums, such as those that arise in inner products. A systolic super summer of cellular design is proposed for the high-throughput performance of repeated sums of floating-point numbers. The apparatus receives pipelined inputs of streams of summands from one or many sources. The floating-point summands are converted into a fixed-point form by a sieve-like pipelined cellular packet-switching device with signal combining. The emerging fixed-point numbers are then summed in a corresponding network of extremely long accumulators (i.e., super accumulators). At the cell level, the design uses a synchronous model of VLSI. The amount of time the apparatus needs to compute an entire sum depends on the values of summands; at this architectural level, the design is asynchronous. The throughput per unit area of hardware approaches that of a tree network, but without the long wire and signal propagation delay that are intrinsic to tree networks.>

A CAD tool is presented for producing very high throughput IIR filters. The architecture is a cascade of word-parallel, blocked, second-order sections. Because it is application-specific, it is a very high level CAD tool. An engineer only needs to specify 1) the word size W, 2) the block size B; and 3) each second-order section's coefficients. Using this information, the CAD tool will generate CIF files for a filter system that, operating at 10MHz, can process 5B/W million samples per second. Our purpose is to illustrate the benefits of applying both bit-level array architecture and application-specific CAD to the problem of IIR filtering. The resulting CAD system reduces the costs of very high throughput IIR filters with respect to design, fabrication, and operation.

A CAD tool is presented for producing very high-throughput FIR filters. Because the CAD tool is application-specific, it is a very high-level tool. An engineer only needs to specify 1) the filter order, N; 2) the input word size; and 3) the output word size. Using this information, the CAD tool generates CIF files for a filter system that can process 10N million samples per second. The purpose of the paper is to illustrate the benefits of applying both bit-level systolic array architecture and application-specific CAD to the problem of FIR filtering. The resulting CAD system reduces the costs of very high-throughput FIR filters with respect to design, fabrication, and operation.

The architecture and implementation of a novel VLSI bit-level systolic Vector Quantization processor is described. This architecture offers very high data throughput for real-time processing applications. Given a codebook of sizeNand dimensionk, an input vector can be quantized everyNclock cycles, compared to O(kN) cycles for a Single-Instruction, Single-Data (SISD) machine. Any distortion measure which can be expressed as a Euclidean vector inner product can be computed with this array.

Given a tissue of suitable size one may program the tissues cells so that it implements any FIR filter. The parameters of such a tissue program are: the number of taps, the tap values, the word sizes (input, ou tput, and internal), and the type of arithmetic (twos complement, one's complement, or sign-magnitude). The FIR tissue thus is versatile. With respect to performance, the tissue supports high-throughput applications; the filter implementation is blocked and pipelined, with a cycle time that depends on neither the word size nor the number of taps. The FIR filter tissue has many desireable anatomic features. It is homogeneous, that is the tissue is an array of structurally identical cells. Each cell is simple - roughly on the order of a latc lied one-hit full adder. The intercellular structure the orthogonal mesh is also simple. It is extensible, that is, the extent of the tissue can be increased (e.g., by adding a new row of cells) without redesigning ally of the parts. Homogeneous simple cells, cellular communication and extensibility all contribute to making this tissue especially well-suited to VLSI implementation.

We describe the design, layout, and simulation of a recursively defined VLSI chip, using a constraint-based, procedural layout language. We use as an example the problem of counting the number of 1's in a set of (B - 1) input bits, where B is a power of 2. A regular, recursive structure, called a unary-to-binary converter (UBC(B)), tally circuit, or parallel counter, is described, based on the original design of Swartzlander. Area from the CIF plots and worst-case delay from simulations are given for 5 instantiations of the circuit, for B = 4, 8, 16, 32, and 64. The results verify the expected asymptotic behavior of the implementation as a function of B. The high-level, procedural approach leads to a succinct and parameterized description of the circuit. Verification and simulation of different versions of the circuit is much easier than with the conventional, hand-layout approach.

This paper investigates the optimal tradeoff between the degree of intermediate latching and cost in special-purpose VLSI chips, using the measure AP, where A is the chip area and P is the period (the reciprocal of throughput). The results show that significant reductions in AP-product (reciprocal of throughput per unit area) can be achieved by-intermediate latching in many typical signal processing applications, for a wide range of circuit parameters.

Parallel counters (unary-to-binary converters) are the principal component of a Dadda multiplier.We specify a design first for a pipelined parallel counter, and then for a complete multiplier.As a result of its structural regularity, the layout is suitable for use in a VLSI implementation.We analyze the complexity of the resulting design using a VLSI model of computation, showing that it is optimal with respect to both its period and latency.In this sense the design compares favorably with other recent VLSI multiplier designs.

Over the past decade a large class of problems, called NP-complete[1], have been shown to be equivalent in the sense that if a fast algorithm can be found for one, fast algorithms can be found for all. At the same time, despite much effort, no fast algorithms have been found for any, and these problems are widely regarded as intractable. This class includes such notoriously difficult problems as the traveling salesman problem, graph coloring, and satisfiability of Boolean expressions. This paper describes some problems in digital signal processing which are NP-complete. These include: (1) Minimize the number of registers required to implement a signal flow graph; (2) Minimize the time to perform the additions (multiplications) of a signal flow graph using P adders (multipliers); (3) Minimize the computational cost for multiplication by a fixed matrix. Large-scale instances of such problems may become important with the use of VLSI technology to implement signal processing.