Journal of Interconnection Networks

In this paper, we introduce SPM (Software-built Parallel Machines), a model to create software based virtual parallel machines. With SPM, an application developer simply selects all the required virtual parallel machines from the repository and implements the intended parallel algorithms directly without any need of complex mappings, as if the required processor interconnections are readily available. In addition, we present an implementation of the SPM model, which provides a systematic way to design new virtual machines. Our experiments show that the applications developed using the SPM model and tools give excellent performance, as compared to the applications developed using a generic communication library, such as MPI.

The paper presents a closed form solution for an optimum scheduling of a divisible job on an optimum number of processor arranged in an optimum sequence in a multilevel tree networks. The solution has been derived for a single divisible job where there is no dependency among subtasks and the root processor can either perform communication and computation at the same time. The solution is carried out through three basic theorems. One of the theorems selects the optimum number of available processors that must participate in executing a divisible job. The other solves the sequencing problem in load distribution by which we are able to find the optimum sequence for load distribution in a generalized form. Having the optimum number of processors and their sequencing for load distribution, we have developed a closed form solution that determines the optimum share of each processor in the sequence such that the finish time is minimized. Any alteration of the number of processors, their sequences, or their shares that are determined by the three theorems will increase the finish time.

Combined input and output queued (CIOQ) architectures with a moderate fabric speedupS > 1 have come to play a major role in the design of high performance switches. In this paper we study CIOQ switches in two settings. The first is a setting of a single CIOQ switch with Priority Queuing (PQ) buffers, which provide better Quality of Service (QoS) guarantees by decreasing the delay experienced by mission-critical and real-time traffic. The second is a setting of a Multistage Interconnection Network (MIN), where each Switching Element (SE) is a CIOQ switch. In the first setting, we consider the case of traffic with packets having variable values. The goal of the switch policy is to maximize the total value of packets sent out of the switch. We present a switch policy that is 6-competitive for any speedup. In the second setting, we study a MIN architecture in which each internal buffer is further divided into virtual buffers, one per each MIN output port reachable from that buffer. We consider the case of traffic with unit value packets, and the goal of the policy managing the MIN is to maximize the total number of packets sent out of the MIN. We give a local memoryless switch policy that uses back pressure and achieves a competitive ratio of (4h + 1), where h is the number of stages of the MIN. The proposed policy is simple and can be efficiently implemented at high speeds. We also demonstrate a lower bound of h/2 on the competitive ratio of any local work-conserving deterministic memoryless switch policy. We further show that without back pressure, no online local work-conserving deterministic switch policy can break the competitive ratio of , where N is the size of the MIN and k is the size of an SE.

Let Γ be a finite group with a nonempty subset A. The Cayley graphCay(Γ, A) of Γ generated by A is defined as the digraph with vertex set Γ and edge set {(x,y) | x^-1 y ∈ A}. Cay(Γ, A) can be regarded as an undirected graph if x^-1 ∈ A for all x ∈ A. Let denote the largest integer M so that there exists a set of integers A = {±1, ±a₂;…, ±a_k} such that the average distance between all pairs of vertices of Cay(ℤ_M,A) is at most r, where ℤ_M is the additive group of residue classes modulo M. It is proved in this paper that

The diagnosis of faulty processors plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Zheng et al. showed that the diagnosability of the n-dimensional star graph S_n is n - 1. Lai et al. introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation when no faulty set can contain all the neighbors of any vertex in the system. In this paper, we study the conditional diagnosability of Cayley graphs generated by transposition trees (which include the star graphs) under the comparison model, and show that it is 3n - 8 for n ≥ 4, except for the n-dimensional star graph, for which it is 3n - 7. Hence the conditional diagnosability of these graphs is about three times larger than their classical diagnosability.

The susceptibility of ring networks to disconnection as a result of one or two node/link failures has led to a number of proposals to increase the robustness of such networks. One class of proposals, discussed primarily in the networking and communication communities, but also advocated for use in parallel and distributed systems, involves the provision of a second ring to improve system throughput during normal operation and to make alternate paths available in the event of node or link failures. With regard to the advantages just listed, chordal rings are quite similar to double-ring networks, and periodically regular chordal (PRC) rings offer the added benefit of smaller node degree compared with node-symmetric chordal rings of comparable diameters. In this paper, we note that certain double-ring networks are isomorphic to suitably constructed PRC rings, while other varieties correspond to PRC rings that closely approximate their static and dynamic attributes. These results, combined with greater flexibility and other advantages for the PRC-ring family of networks, demonstrate that PRC rings are preferable to double-ring networks in virtually all application contexts. A byproduct of our observations on the relationships among double-ring networks, generalized Petersen graphs, and PRC rings is that by amalgamating known results for these network classes, many more tools and techniques become applicable to the analysis and synthesis of robust ring networks for parallel and distributed computing. As examples of new results that can be developed with this viewpoint, we present near-optimal and fault-tolerant routing algorithms for our PRC ring networks.

As a network topology for a massively parallel computer system, Generalized Hierarchical Completely-Connected Networks (for short, HCC), which include conventional hierarchical networks, have been proposed. To apply the HCC to a parallel computer system effectively and to execute data processings on the HCC efficiently, the inherent fault-tolerant properties in HCC must be revealed. However, these properties have not been clarified enough. In this paper, node-connectivity is verified for HCC. Furthermore, the concept of block-connectivity related to node-connectivity of HCC is introduced, and fault-tolerance of HCC is discussed.

We consider a problem of cost-constrained minimum-delay multicasting in a network, which is to find a Steiner tree spanning the source and destination nodes such that the maximum total delay along a path from the source node to a destination node is minimized, while the sum of link costs in the tree is bounded by a constant. The problem is NP-hard even if the network is series-parallel. We present a fully polynomial time approximation scheme for the problem if the network is series-parallel.

A novel Interconnection Network Architecture is proposed for integrating tightly coupled Distributed Systems. It allows the implementation of Service Address Routing(SAR): network communications between components are based on the "name" of requested services. It is a client-server communications model, and optionally includes the traditional physical addressing schemes. This enhanced network architecture registers the capabilities of the components attached to its ports and directs service requests to appropriate server nodes. The Network can perform Resource Allocation by placing services in nodes that can support them. Load Distribution is achieved by binding requests to adequate servers with enough free resources. Furthermore, SAR effects a simple, yet efficient and transparent resource discovery mechanism by means of a distributed content-addressable search at each network port. A scalable implementation for computer clusters is proposed which uses the Least-Common-Ancestor Networks (LCANs) as the model for the hierarchical interconnect. At the end of this work, an analysis based on theoretical examination and experimental testing is carried out; scalability and cost-effectiveness of the proposed Service-Address-Routed Least-Common-Ancestor Networks are thus examined.