Volume 16, 1997, No. 2

Special Issue on Parallel and Distributed Computing

Guest Editor: Ondrej Sýkora

 

Matrix Transpose on Meshes: Theory and Practice

M. Kaufmann, U. Meyer, J.F. Sibeyn

Abstract. We consider the problem of matrix transpose on mesh-connected processor networks. On the theoretical side, we present the first optimal algorithm for matrix transpose on two-dimensional meshes.  Then we consider issues on implementations, show that the theoretical best bound cannot be achieved and present an alternative approach that really improves the practical performance. Finally, we introduce the concept of orthogonalizations, which are generalization of matrix transposes.  We show how to realize them efficiently and present interesting applications of this new technique.

 

Mesh Sorting and Selection Optimal to the Average

B.S. Chlebus

Abstract. We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time 2-n + o(n), and sorting in the average time 2 . n+o(n). Matching lower bounds are also proved.

 

On Partitioning Grids into Equal Parts

S.L. Bezrukov,  B. Rovan

Abstract. Let an edge cut partition the vertex set of an n-dimensional quadratic grid with the side length a into k subsets A1, … , Ak with || Ai| - |Aj|| £ 1. We consider the problem of determining the minimal size c (n,k,a) of such a cut and present its asymptotic c (n,k,a) ~ nan-1 as a, k ®  and k/an ® 0. The same asymptotic holds for partitioning of the n-dimensional torus. We present also some heuristics, which provide better partitioning for n = 2 and small k.

 

Graph Relabelling Systems: A General Overview

Y. Métivier, E. Sopena

Abstract. Graph relabelling systems have been introduced as a suitable model for expressing and studying distributed algorithms on a network of communicating processors. We recall the basic ideas underlying that model and we survey the main questions that have been considered and the main results that have been obtained in that framework.

 

Contextual Coordination for the Mapping of Distributed Systems on Object-Oriented Systems

M. Buffo, D. Buchs

Abstract. Components of object-oriented systems have strong similarities with components of distributed systems; objects can be viewed as loosely coupled computing entities similar to distributed processes, but objects granularity is generally different from process granularity. This prevents a direct mapping between objects and processes during the implementation process. This paper presents a suitable coordination model, based on hierarchical execution contexts, allowing to map object-oriented specifications into distributed systems. As a result, object-oriented systems can be mapped into distributed systems at the specification level, and we obtain a formal framework for understanding and implementing distributed systems.

 

Local Quartet Splits of a Binary Tree Infer All Quartet Splits Via One Dyadic Inference Rule

P.L. Erdös. M.A. Steel, L.A. Székely, T.J. Warnow

Abstract. A significant problem in phylogeny is to reconstruct a semilabelled binary tree from few valid quartet splits of it. It is well-known that every semilabelled binary tree is determined by its set of all valid quartet splits. Here we strengthen this result by showing that its local (i.e. small diameter) quartet splits infer by a dyadic inference rule all valid quartet splits, and hence determine the tree.  The results of the paper also present a polynomial time algorithm to recover the tree.

Go To Contents