Journal of Interconnection Networks

We propose a new network called the mixed chordal ring where the amount of hardware and its structure are very comparable to the (directed) double-loop network, and yet can achieve a better diameter. We also investigated other combinatorial properties such as connectivity and hamiltonian circuits in the mixed chordal ring.

Improved bounds for the crossing number of the mesh of trees graph, M_n, are derived. In particular, we derive a new lower bound of which improves on the previous bound of Leighton [11] by a constant factor, and an upper bound of . In addition, we construct drawings of M_n which achieve the upper bound number of crossings. We also prove that the crossing number of M₄ is 4.

In classical broadcast models, once a vertex receives the broadcast message, it sends the message out in such a way as to achieve the minimum possible broadcasting time. It is assumed either that there is a leader who coordinates the actions of all vertices during the broadcasting process, or that the vertices have a coordinated set of protocols which allow them to achieve minimum time broadcast for any originator. In the messy broadcast model, there is no leader, the vertices of the network do not know the starting time of the broadcast or the originator, the state of the whole scheme is unknown to any vertex, and the protocols are not coordinated. This model also describes a network with vertices that have small memories insufficient to store a set of coordinated protocols.

In this paper, we continue the study of messy broadcasting and present the first results for directed graphs. We obtain exact values for and bounds on the messy broadcast times of multidimensional directed tori.

For the Butterfly of N input/output vertices we present a layout on the rectilinear (square) grid of area ½N² + o(N²). A lower bound of the same order is proved. The encompassing rectangle which defines the area is 45° slanted w.r.t. the grid axes and the input/output vertices are not on the boundary of this rectangle.

The layout is component-scalable, i.e., if one allocates for each switch a square of a × a area, the layout remains of area ½N² + o(N²); that is, the value of a affects only the o(N²) term. The layout is also free of knock-knees.

Due to advances in fiber-optics and VLSI technology, interconnection networks which allow multiple simultaneous broadcasts are becoming feasible. This paper examines the performance of distributed-shared-memory (DSM) systems based on the Simultaneous Optical Multiprocessor Exchange Bus (SOME-Bus) using queuing network models and develops theoretical results which predict processor utilization, message latency and other useful measures. It also presents simulation results which compare the performance of the SOME-Bus, the mesh and the torus using queuing-network models. The SOME-Bus is a low-latency, high-bandwidth, fiber-optic interconnection network which directly links arbitrary pairs of processor nodes without contention, and can efficiently interconnect over one hundred nodes. It contains a dedicated channel for the data output of each node, eliminating the need for global arbitration and providing bandwidth that scales directly with the number of nodes in the system. Each of the N nodes has an array of receivers, with one receiver dedicated to each node output channel. No node is ever blocked from transmitting by another transmitter or due to contention for shared switching logic. The entire N-receiver array can be integrated on a single chip at a comparatively minor cost resulting in o(N) complexity. The SOME-Bus has much more functionality than a crossbar by supporting multiple simultaneous broadcasts of messages, allowing cache consistency protocols to complete much faster. The effect of collective communications due to cache coherence is examined. Results reveal that the performance of the SOME-Bus interconnection network is the least affected by large communication times, compared to the other two architectures considered here. Even in the presence of intense coherence traffic, processor utilization and message latency is much less affected than in the other architectures.

A novel and efficient neighbourhood broadcasting scheme is proposed for star interconnection networks, based on binomial trees and graph theoretic concepts. The optimal scheme has an upper bound of 1.33⌈log₂(n - 2)⌉ + O(1) time steps and it is applicable to both single-port and half-duplex modes of message passing communication.

We study the strong fault-tolerance for the star networks. Let G be a network in which all nodes have degree d. We say that G is strongly fault-tolerant if it has the following property: let G_f be a copy of G with at most d - 2 faulty nodes removed, then for any pair of non-faulty nodes u and v in G_f, there is a container of width t between u and v, where t is the minimum of degree of u and degree of v in G_f. We show that the star networks are strongly fault-tolerant and develop an algorithm that constructs a maximum width container of nearly optimal length in a star network with faults. Our algorithm requires no prior knowledge for the faulty nodes and runs in optimal time.