Parallel Processing Letters

We show the NP-Completeness of two processor scheduling with tasks of execution time 1 or 2 units and unit interprocessor communication latency. We develop a model of scheduling in the presence of communication contention, and show the NP-Completeness of two processor scheduling with unit execution time tasks in our model.

Job scheduling on multiprocessor systems is studied here as a special case of oriented two-dimensional orthogonal bin packing. Each job has subtasks which can be processed in parallel, requiring multiple processors to be allocated to each job. Then each job corresponds to a rectangle with sides equal to the processor requirement and the processing time. We study two classes of algorithms: (i) Longest processing time first (LPT) algorithms, and (ii) Largest processor requirement first (LPR) algorithms. We obtain improved asymptotic upper bounds for these algorithms compared to the bounds of the corresponding algorithms for the general two-dimensional packing problem. This is due to the discrete nature of the processor requirement (dimension) of jobs. We find that the LPR algorithms have better asymptotic upper bound on the makespan compared to the LPT algorithms. Specifically, the bound is 7/4 for the LPR algorithms whereas it is 2 for the LPT algorithms. Moreover, LPR algorithms are found to be more suited for dynamic job scheduling.

This article proposes an election algorithm for the hypercube; it exchanges less than messages and uses O(log² N) time (where N is the size of the cube). A randomized version of the algorithm achieves the same (expected) asymptotic message and time bounds, but uses messages of only O(log log N) bits and can be used in anonymous hypercubes.

Given a sequence Q of n numbers (positive and negative), the maximum subsequence of Q is the contiguous subsequence that has the maximum sum among all contiguous subsequences of Q. Given a two-dimensional array A of n × n numbers (positive and negative), the maximum subarray of A is the contiguous subarray that has the maximum sum among all contiguous subarrays of A. We present two O(log n)-time parallel algorithms — one for finding the maximum subsequence sum of a given sequence, and the other for finding the maximum subarray sum of a given array. The former is optimal on an EREW PRAM. The latter is optimal on a CREW PRAM, in the sense that the time-processor product matches the current sequential upperbound of O(n³).

We theoretically compare the efficiency of two versions, sequential and parallel (synchronous), of the method called branch-and-bound used for searching for an optimal solution in the scope of combinatorial optimization. The sequential version consists of successive decompositions of the original problem in smaller disjoint subproblems and its parallel version consists of a high level parallelization that assumes a shared memory model of parallel computation. Its principle consists of decomposing several subproblems in parallel at each iteration in a synchronous way, and its efficiency is usually defined with respect to its sequential counterpart. In this paper, we redefine the notion of efficiency in such a way that the usefulness of the work done by each processor will be taken into account. The knapsack problem is used as an application and some simulation results are presented to validate and illustrate the use of the new efficiency measures.

The track model for fault tolerant 2D processor arrays is extended to 3D mesh architectures. Non-intersecting, continuous, straight and non-near miss compensation paths are considered. It is shown that when six directions in the 3D mesh are allowed for compensation paths, then switches with 13 states are needed to preserve the 3D mesh topology after faults. The number of switch states reduces to 7 if only 3 directions are allowed for compensation paths. It is also shown that switch reconfiguration after faults is local in the sense that the state of each switch is uniquely determined by the states of the 2 processors connected to it.

Sorting techniques have numerous applications in computer science. Current real number and integer sorting techniques for the reconfigurable mesh operate in constant time using a reconfigurable mesh of size n × n to sort n numbers. This paper presents a constant time algorithm to sort n items on a reconfigurable network with switches and processors. Also, new constant time selection and compression algorithms are given. All results may also be implemented on the 3-D reconfigurable mesh.

A work-efficient deterministic algorithm is presented for finding a maximum matching in a bipartite expander graph with any expansion factor β > 1. This improves upon a recently presented deterministic maximum matching algorithm which is restricted to those bipartite expanders with large expansion factors (β ≥ Δ^∊, ∊ > 0), and is not work-efficient [1].

Most parallelization techniques for loop nests are based on reindexation. Reindexation yields a new iteration space, which is a convex integer polyhedron defined by a set of affine constraints. Parallel code generation thus needs to scan all the integer points of this convex, thereby requiring the construction of a new loop nest. We detail an algorithm to this purpose, which relies on a parametrized version of the Dual Simplex. We show how the resulting loop nest and especially the loop bounds can be kept simple, thus reducing the control overhead of parallelization to a minimum.

Proper distribution of operations among parallel processors in a large scientific computation executed on a distributed-memory machine can significantly reduce the total computation time. In this paper, we propose an operation called simultaneous parallel reduction(SPR), that is amenable to such optimization. SPR performs reduction operations in parallel, each operation reducing a one-dimensional consecutive section of a distributed array. Each element of the distributed array is used as an operand to many reductions executed concurrently over the overlapping array's sections. SPR is distinct from a more commonly considered parallel reduction which concurrently evaluates a single reduction. In this paper we consider SPR on Single Instruction Multiple Data (SIMD) machines with different interconnection networks. We focus on SPR over sections whose size is not a power of 2 with the result shifted relative to the arguments. Several algorithms achieving some of the lower bounds on SPR complexity are presented under various assumptions about the properties of the binary operator of the reduction and of the communication cost of the target architectures.

We present a simple systolic algorithm for implementing dictionary machine based on the VLSI technology. Our design makes use of a dynamic. global tree rebalancing scheme to attain high system throughput. Our scheme is simple to implement and requires low sophistication in the design of processing nodes. Results from analysis and simulation show that our algorithm has optimal response time and achieves an average latency close to 1. This represents a significant improvement over many of the previous designs. Unlike most parallel dictionary machines reported in the literature, our approach requires no compression operations.

In this paper, two linear systolic arrays for the solution of general, strongly regular Toeplitz system of equations are presented. They arise from systolization of the efficient serial Schur-like algorithm. Both arrays are time-minimal and they complete the solution in 3n – 4 time cycles (without the initialization and the retrieval of results). The first array requires 2n – 2 processors, and the second one uses only n – 1 processors.

Sizes of on-chip caches on current commercial microprocessors range from 16 Kbytes to 36 Kbytes. These microprocessors can be directly used in the design of a low cost single-bus shared memory multiprocessors without using any second-level cache.

In this paper, we explore the viability of such a multi-microprocessor. Simulations results clearly establish that performance of such a system will be quite poor if on-chip caches are direct-mapped. On the other hand, when the on-chip caches are partially associative, the achieved level of performance is quite promising. In particular, two recently proposed innovative cache structures, the skewed-associative cache organization and the semi-unified cache organization are shown to work fine.

We consider the Byzantine Agreement problem by assuming that nodes of a network fail independently with fixed probability 0 < p < 1. The goal is to construct almost-safe agreement protocols working for classes of sparse n-node networks. For such protocols, the probability of reaching consensus, under any behavior of faulty nodes, must converge to 1 as n grows. For p < 1/3 and every function L: N → N growing faster than linear, we show n-node networks with L (n) links and an almost-safe Byzantine Agreement protocol working for these networks. We also construct such a protocol working for a large class of n-node networks of maximum degree O(log n). We show, further, that these networks are asymptotically sparsest possible to support almost-safe Byzantine Agreement.

The Reconfigurable Array with Spanning Optical Buses (or RASOB) architecture provides flexible reconfiguration and strong connectivities with low hardware and control complexities. We use a parallel implementation of the matrix transposition as well as multiplication algorithms as an example to show how the architectural capabilities can be taken advantage of in designing efficient parallel algorithms.

The original DIOGENES design methodology produces fault-tolerant layouts of VLSI processor arrays by designing an array's interconnection network as a (possibly large) number of (re)configurable bundles of wires, each bundle being organized as either a stack or a queue. The benefits of DIOGENES often come only at high cost, in terms of both configuration hardware and algorithmic cost of configuration. In this paper, we improve the original methodology in a way that simultaneously: streamlines the design process; produces more cost-effective layouts; can be augmented to allow efficient dynamic reconfigurability.

Our new version of DIOGENES replaces the wire-stacks and/or -queues of the original methodology by a single generalized deletion stack (GDS for short), independent of the topology of the array. The new methodology has three major benefits:

1. A GDS-network can be configured in time linear in the size of the graph being realized. (Optimal network configuration is superlinear for the queue-based version and NPcomplete for the stack-based version of the original methodology.)

2. A GDS-network can realize any linearization of any graph, subject only to the constraints of the implemented node-degree and cutwidth. (The original methodology demands a priori commitment to a fixed number of stacks or queues of fixed sizes, hence limits one to a restricted set of array topologies.)

3. A GDS-network usually requires dramatically less configuration hardware than a stack- or queue-based network would (albeit with larger switches).

We end with suggested enhancements to this new, flexible, version of DIOGENES.