Parallel Processing Letters

We consider fundamental data manipulation operations such as broadcasting, prefix sum, data sum, data shift, data accumulation, consecutive sum, adjacent sum, sorting, and random access reads and writes, and show how these may be performed on the distributed memory bus computer (DMBC). In addition, we study two image processing applications: shrinking and expanding, and template matching. The DMBC algorithms are generally simpler than corresponding algorithms of the same time complexity developed for other reconfigurable bus computers.

We prove a separation between two models of the reconfigurable mesh (rmesh), the cross-over model and the non-cross-over model. Specifically, for any constant k ≥ 1, we show that in the non-cross-over model, a k × n rmesh requires Ω(log n) time to compute the parity of n bits stored one per column, while in the cross-over model, when k ≥ 3, a k × n rmesh can compute the parity in constant time. This is the first separation demonstrated between the cross-over and non-cross-over model. The lower bound does not rely on the bandwidth constraints of the mesh and does not restrict the instruction sets of the processors. Moreover, it is the first lower bound for the rmesh which requires only binary inputs.

This paper shows that the prefix-sums of n binary values can be computed in time on an n × m reconfigurable mesh of the word model. It also shows that prefix-sums of n binary values can be computed in time on an n × m reconfigurable mesh of the word model if the reconfigurable mesh has communication capability that allows simultaneous sending to the same bus.

We propose a design for, and investigate the computational power of a dynamically reconfigurable parallel computer that we call the Reconfigurable Ring of Processors (, for short). The is a ring of identical processing elements (PEs) that are interconnected via a flexible multi-line reconfigurable bus, each of whose lines has one-packet width and can be configured, independently of the other lines, to establish an arbitrary PE-to-PE connection. A novel aspect of our design is a communication protocol we call COMET — for Cooperative MEssage Transmission — which allows PEs of an to exchange one-packet messages with latency that is logarithmic in the number of PEs the message passes over in transit.

The main contribution of this paper is an algorithm that allows an N-PE, N-line to simulate an N-PE hypercube executing a normal algorithm, with slowdown less than 4 loglog N, provided that the local state of a hypercube PE can be encoded and transmitted using a single packet. This simulation provides a rich class of efficient algorithms for the , including algorithms for matrix multiplication, sorting, and the Fast Fourer Transform (often using fewer than N buslines). The resulting algorithms for the are often within a small constant factor of optimal.

Let A and B be two groups of up to n elements distributed on the first row of an n × n reconfigurable mesh, and C_A,B a subset of the cartesian product A × B satisfying some unknown condition C. Only one broadcasting step is needed in order to compute C_A,B's elements. However, the problem of moving C_A,B's elements to the first row in optimal time (so that they can be further processed) is not trivial. The conditional cartesian product (CCP) problem is to move C_A,B's elements to the first row in steps. This requires optimizing the cartesian product operation such that C_A,B's elements will be optimally scattered in the mesh, so that O(n) elements can be retrieved in a single step as opposed to elements needed if the cartesian product is not optimized). We give a deterministic algorithm that for any A, B, C solves this problem in steps, and an "adaptive" randomized algorithm whose optimality is verified by experimental results. Note that the CCP is a case where we overcome the inherent limitation of the reconfigurable mesh, namely, the inability to perform fast routing of packets located in a small area.

We also present the model of production systems, in which computation is realized by executing cartesian productions of subsets in a common element space. Production systems are useful for database applications, expert systems, and can even be used as a general parallel programming language. Solving the CCP problem allows us to devise an efficient implementation for production systems on the reconfigurable mesh. In this way the reconfigurable mesh is shown to be an attractive architecture for database machines and for parallel programming as well.

We study the problems of permutation routing and sorting on several models of meshes with fixed and reconfigurable row and column buses. We describe two fast and fairly simple deterministic algorithms for permutation routing on two-dimensional networks, and a more complicated algorithm for multi-dimensional networks. The algorithms are obtained by converting two known off-line routing schemes into deterministic routing algorithms, and they can be implemented on a variety of different models of meshes with buses. We also give a deterministic algorithm for 1–1 sorting whose running time matches that for permutation routing, and another algorithm that matches the bisection lower bound on reconfigurable networks of arbitrary constant dimension.

We consider routing and sorting problems on mesh connected processor arrays under a very weak model of reconfiguration: we allow only uni-directional row or column buses, point-to-point communication, one-port-at-the-time serve by each processor. We present a scheme which is asymptoticly optimal for k-k sorting, for any arbitrary k > 0. It works optimally on meshes of arbitrary dimensions d, from the linear array to hypercubic networks with d < n^1/3. The algorithm can also be used to perform k-k routing in the same time bound. We give an alternative scheme for permutation routing, which is asymptoticly slower, but has much better performance for realistic problem sizes.

This paper presents a new interconnection network for a massively parallel architecture based on the static model of communication. The principle of the model is to schedule at run time, on a circuit switching hardware, the off-line routed circuits computed at compile time. Designing a network especially for the compiled model can take full benefit of the current interconnection technology. The static network is intended to a synchronised MIMD distributed memory machine, based on high performance processing nodes including microprocessors. The application scope is numerical computation, where all communication patterns may occur. The hardware issues are the various synchronisations inside the network, which need a sophisticated switch design to keep pace with 1.33 Gbit/s links. The network is designed to reach a sustained aggregate bandwidth of more than 500GBytes/s, and provide an overall latency less than 270ns, up to 4K inputs. The network is fully pipelined and can be reconfigured each 60ns.

A dynamically reconfigurable architecture is a parallel computer architecture that supports a physical switching of communication patterns during a computation. Basically, the dynamically reconfigurable architecture consists of locally controllable switches, which enables flexible-connection patterns of the network. The bibliography attempts to classify published papers on dynamically reconfigurable architectures according to the problems that are dealt with.