Parallel Processing Letters

We outline constructions of packet radio networks (with time division multiplexing) that achieve much better parameters than those previously proposed. Given the desired diameter and number of slots per time frame, our networks seek to maximize the possible number of users. We model this as a problem of constructing large graphs or digraphs with given diameter and chromatic index, and relate it to extant work on large graphs with given diameter and maximum degree.

We prove the following results:

(a) The Cube-Connected Cycles network of dimension n is a subgraph of the Butterfly network of dimension n.

(b) The Shuffle-Exchange network of dimension n is a subgraph of the DeBruijn network of dimension n.

A distributed system consists of a set of loosely connected state machines which do not share a global memory. The global state of the system depends on the state of each process in the system. The set of global states can be split up into two categories, legal and illegal. This paper deals with methods of detecting deadlocks in distributed systems. One way that has been used to detect deadlocks is by sending probes around the system. If a process thinks that it may be deadlocked, it initiates a probe. If the probe is received by the initiator, the initiator declares deadlock. This paper uses the idea of states of processes In order to detect the deadlock. The algorithm runs continually and does not have to be initiated. This paper presents deadlock detection algorithms for single and multiple outstanding requests. A method for deadlock resolution is also discussed. The algorithms detect all deadlocks and do not detect false deadlocks.

This paper places the optimal tree ranking problem in . A ranking is a labeling of the nodes with natural numbers such that if nodes u and v have the same label then there exists another node with a greater label on the path between them. An optimal ranking is a ranking in which the largest label assigned to any node is as small as possible among all rankings. An O(n) sequential algorithm is known. Researchers have speculated that this problem is P-complete. We show that for an n-node tree, one can compute an optimal ranking in O(log n) time using n²/log n CREW PRAM processors. In fact, our ranking is super critical in that the label assigned to each node is absolutely as small as possible. We achieve these results by showing that a more general problem, which we call the super critical numbering problem, is in . No algorithm for the super critical tree ranking problem, approximate or otherwise, was previously known; the only known algorithm for optimal tree ranking was an approximate one.

We propose that a new measure of performance be applied in the analysis of PRAM algorithms, called discriminating analysis. Discriminating analysis charges Θ (log M) time for access to a memory of size M. As well, a read is split into two primitives, a request and a receipt, with a receipt completing Ω (log M) time units after the corresponding request is issued. A facility for pipelining of access requests is assumed. A new adaptive and optimal algorithm for matrix by vector multiplication is presented.

The paper proposes an analytical model for estimating the performance of Pipelined Ring algorithm for LU factorisation on any distributed memory message passing multiprocessor. Expressions for parallel execution time and speedup are derived from the computation-communication characteristics of the algorithm. Earlier methods on performance estimation of LU factorisation have been based on determining the number of floating point operations in the best and worst cases. The methodology proposed in this paper follows a different approach and estimates the performance of LU factorisation from a measurement of the execution time of the algorithm on a single processor and from a knowledge of the number of bytes communicated in different steps of the algorithm. The expression for parallel execution time of LU factorisation derived from the analytical model has been validated with experimental values obtained 011 a sixty-four transputer based multiprocessor. Results indicate that the methodology proposed in this paper can be used for estimating the execution time of Pipelined Ring algorithm for LU factorisation on any distributed memory message passing multiprocessor with high accuracy.

We present a new method for the solution of partial differential equations. In contrast to the usual approach which needs in the 2-D case grid points, our combination technique works with only grid points, where h_n denotes the employed grid size. The accuracy of the obtained solution deteriorates only slightly from to for a sufficiently smooth solution. Additionally, the new method is perfectly suited for parallelization. On a machine with processors we get in practice an overall parallel complexity of only . The method can be generalized to higher dimensions. Then, the gain is expected to be even more dramatic. For the two-dimensional case, we report the results of numerical experiments obtained on a Transputer system and on the CRAY Y-MP.

Recently Conery proposed a backward execution algorithm for AND-parallel execution of logic programs, and Ng and Leung extended it. They adopt the same data structure called mark(s) set to store information about failure history during AND-parallel evaluation of clauses. Both of the two algorithms essentially have the same rationale with minor differences and have been considered correct, largely due to their intuitive persuasiveness. We closely re-examine those algorithms and find out that they are incorrect. Their incorrectness comes from oversimplification of failure situations. Our analyses focused on the mark(s)-set-based backtrack literal selection are presented. We also propose another backtrack literal selection method based on the mark(s) set, and prove its correctness.

This paper addresses the problem of mapping the modules of a task precedence graph to the processing elements of a parallel computer. The goal of the mapping is to minimize the total execution time of the task, sum of the computation and communications time, within a processor network of limited size. We consider the special instance where the precedence graph is a binary precedence tree. We present a linear time procedure for mapping an almost full binary precedence tree of n nodes to any p processor hypercube, with unit dilation cost and optimal execution time. The computation time under the mapping is seen to be O(n/p) and the communications time is seen to be log p.

This paper formulates and discusses a processor assignment problem arising in partitionable parallel architectures. A partitionable hypercube multiprocessor can simultaneously execute multiple tasks where each task is independently executed on a subcube. Given a p processor hypercube and n independent tasks, where a task can be assigned a subcube of any size, an assignment determines the size of the subcube — i.e., the number of processors — to be assigned to each task. The objective of our problem is to find the optimal assignment which minimizes the maximum execution time among all tasks. We present an O(n log p max{log log p, log n}) algorithm that determines an optimal assignment. This algorithm can be efficiently parallelized, on the p processor hypercube, to obtain an O((n/p)log p log²(n log p)) parallel assignment algorithm.

In this paper we design modular linear systolic arrays for the solutions of dynamic programming problems using geometric considerations. Our results show that solving a dynamic programming problem of size n requires (n - 1) ⌈( n/α)⌉ + 1 cells and (n - 1) ((α + 3) ⌈(n/α)⌉ + 2) + 1 time steps, where each cell has a local memory of constant size α and the time delay between two consecutive cells of the array is assumed to be constant.