Parallel Processing Letters

This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let T_f be the total time needed to execute all computations using the free (greedy) schedule and let T_l be the total time needed to execute all computations using the optimal linear schedule. Our main result is to bound T_l/T_f and T_l − T_f for sufficiently "fat" domains.

Starting with a system of uniform recurrence equations (source UREs) for a systolic design, we provide a method that allows a specification of control signals by another system of UREs (control UREs), which has no notion of time and space. Necessary and sufficient conditions for the correctness of the control UREs are stated. The standard space-time mapping technique is extended so that systolic arrays with a description of both data and control flow are directly synthesised from the source and control UREs. Optimisations of control signals are discussed. An example is provided.

Address transformation schemes, such as skewing and linear transformations, have been proposed to achieve conflict-free access to one family of strides in vector processors with matched memories.

In this paper, we extend these schemes to achieve this conflict-free access for several families. The basic idea is to perform an out-of-order access to vectors of fixed length, equal to that of the vector registers of the processor. The hardware rcquired is similar to that for the access in order.

We propose new models of SIMD distributed memory parallel computers. We define concurrent read/write access also for machines other than PRAM. Our goal is to unify the description of abstract models of parallel machines with the aim of building a complexity theory where all models can be soundly compared. As an example, we introduce the Hypercube Random Access Machine with concurrent read/write capabilities, and show that it can solve some problems faster than the PRAM.

In this paper we present upper and lower bounds for the problems of sorting and routing n items using p processors on the hypercube, the shuffle, the butterfly and the Cube-Connected-Cycles. We consider problems where n is large; more precisely we assume that n = Ω (p²). The main results of this paper are an algorithm for routing n packets in O((n/p) log p) time, and an algorithm for sorting n integers in the range 0, 1, …, R – 1 in time.

In this paper we derive a lower bound for the total communication volume when mapping arbitrary task graphs onto a distributed processor system. For a K processor system this lower bound can be computed with only the K (possibly) largest eigen values of the adjacency matrix of the task graph and the eigen values of the adjacency matrix of the processor graph. We also derive the eigen values of the adjacency matrix of the processor graph for a hypercube multiprocessor and illustrate the concept with a simple example for the two processor case.

In this paper we present a randomized parallel maximal matching algorithm that requires only O(n) processors on an. EREW PRAM, where n is the number of vertices in an undirected graph G = (V, E). Our algorithm outputs a matching in O(log² m) expected time, where m is the number of edges in G. The probability that the output of our algorithm is maximal is at least 1 − e^−k, where k is a constant.

We present a cost-optimal parallel algorithm for generating variations of m elements out of {0, 1, …, n - 1} in lexicographic order. It uses a linear array of m processors, each having constant size memory and each being responsible for producing one part of a given variation. Binary and decimal counters are special cases of the algorithm, when n = 2 and n = 10, respectively. To our knowledge, the algorithm presented here is the first to be published with the property that the delay between any two variations generated is constant.

We show a relation in the performance of three of the most important and frequently performed parallel operations on dynamically reconfiguring machines, namely, the data reduction, the ranking and the sorting operations. In particular we consider the reconfigurable mesh, for which we show the applicability of the method by giving an asymptotically optimal ranking algorithm. The latter result also uses an optimal packing algorithm.

In parallel systems, a number of joins from one or more queries can be executed either serially or in parallel. While serial execution assigns all processors to execute each join one after another, parallel execution distributes the joins to clusters formed by certain numbers of processors and executes them concurrently. However, data skew may result in load imbalance among processors executing the same join and some clusters may be overloaded with more expensive joins. As a result, the completion time will be much longer than what is expected. In this paper, we propose an algorithm to further minimize the completion time of concurrently executed multiple joins. For this algorithm, all the joins to be executed concurrently are decomposed into a set of tasks that are ordered according to decreasing task size. These tasks are dynamically acquired by available processors during execution. Our performance study shows that the proposed algorithm outperforms previously proposed approaches, especially when the number of processors increases, the relations are highly skewed and relation sizes are large.