Parallel Processing Letters

The tree interconnection network lends itself to several suitably structured applications. However, the low connectivity at each node, traffic congestion and single point of failure at the root node reduce reliability and availability. Both the hypertree and X-tree are fault-tolerant variants of the basic tree network and have been the focus of more recent implementation and research interest. In this paper, we consider a recently proposed family of interconnection networks known as the Josephus Cubes and show how hypertrees, X-trees and ringed X-trees of arbitrary height can be near-optimally embedded in this novel interconnection network.

We consider a broadcasting problem in the n-dimensional k-ary even torus in the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time step a number of links of the network can be faulty. Moreover the faults are dynamic. The problem is to determine the minimum broadcasting time if at most 2n - 1 faults are allowed in any step. In [4], it was shown that the broadcasting time is at most diameter+O(1), provided that k is limited by a polynomial of n. In our paper we drop this additional assumption and prove that the broadcasting can be always done in time diameter +2. The bound is the best possible.

We study the wavelength problem and arc (edge) congestion problem for communicating permutation instances on a ring. We prove the best possible upper bounds on the number of wavelengths and arc (edge) congestion in both directed and undirected cases.

We consider a communication model in which the intermediate nodes cannot store in-transit messages. Under this communication model we study the all-node multicast operation on multidimensional grids and tori. We derive optimal algorithms that are compactly described using a short sequence of node identities. This characteristic contributes to the simplicity of the router, the unit that resides at each processor and is dedicated to handle communication.

Free-space optical interconnection is used to fashion a reconfigurable network. Since network reconfiguration is expensive compared to message transmission in such networks, latency hiding techniques can be used to increase the performance of collective communications operations. Berthome and Ferreira have recently proposed a broadcasting algorithm for their loosely-coupled optically reconfigurable parallel computer where they have shown that the total number of nodes, N(S), informed up to step S follows a recurrence relation. We have adapted their algorithm to our reconfigurable optical network, RON (K, N), which has slightly different modeling. We present a new analysis of this broadcasting algorithm on our network. This paper contributes by providing closed formulations for the N(S) that yield the termination time for both single-port and k-port modeling. The derived closed formulate are easier to computer than the recurrence relations.

In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O(log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O(log² n) time using O(mn) processors on the CRCW PRAM model and O(log² n) time using O(m) processors on the CREW PRAM model, respectively.

Virtual Interface Architecture(VIA) is a light-weight protocol for protected user-level zero-copy communication. In spite of the promised high performance of VIA, previous MPI implementations for GigaNet's cLAN revealed low communication performance. Two main sources of such low performance are the discrepancy in the communication model between MPI and VIA and the multi-threading overhead. In this paper, we propose a new implementation of the Bulk Synchronous Parallel(BSP) programming library for VIA called xBSP to overcome such problems. To the best of our knowledge, xBSP is the first implementation of the BSP library for VIA. xBSP demonstrates that the selection of a proper library is important to exploit the features of light-weight protocols. Intensive use of Remote Direct Memory Access(RDMA) operations leads to high performance close to the native VIA performance with respect to round trip delay and bandwidth. Considering the effects of multi-threading, memory registration, and completion policy on performance, we could obtain an efficient BSP implementation for cLAN, which was confirmed by experimental results.

We present new communication-efficient parallel dense linear solvers: a solver for triangular linear systems with multiple right-hand sides and an LU factorization algorithm. These solvers are highly parallel and they perform a factor of 0.4P^1/6 less communication than existing algorithms, where P is number of processors. The new solvers reduce communication at the expense of using more temporary storage. Previously, algorithms that reduce communication by using more memory were only known for matrix multiplication. Our algorithms are recursive, elegant, and relatively simple to implement. We have implemented them using MPI, a message-passing libray, and tested them on a cluster of workstations.

Static performance prediction of implicitly parallel functional programs can be facilitated by restricting the source language to be shapely [7]. The resulting analyses should provide valuable support for the calculational style of program derivation. We build upon previous work in the area by extending the range of admissible programs, allowing us to demonstrate the first automated analysis of a complete program derivation, that of the well known maximum segment sum algorithm of Skillicorn and Cai [11]. We examine the accuracy of our predictions against the run time of real parallel programs.

The motivation for the research presented here is to develop an approach for scheduling I/O operations in distributed/parallel computer systems. First, a general model for specifying the parallel I/O scheduling problem is developed. The model defines the I/O bandwidth for different parallel/distributed architectures. Then the model is used to establish an algorithm for scheduling I/O operations on these architectures.

We study the parallel approximability of computing the number of true gates and false gates for circuits with only NOR gates, we refer to these problems as Nor-False Gates and Nor-True Gates Problems, respectively. We show that the parallel approximability of these problems depends on restrictions on the topology of the circuit. More precisely, for circuits with fan-in and fan-out bounded by a constant and having a constant number of output gates both problems exhibit a threshold behavior in their parllel approximability. Bounding only the number of outputs gives threshold results for the Nor-False Gates Problem but non-approximability (for any constant) for the Nor-True Gates Problem. For the case of unbounded number of outputs we show that none of the two problems can be approximated in parallel within any constant. We use the threshold result of False Gates Problem to identify a subclass of linear programming that also presents a threshold behavior in its parallel approximability.