FLUX interconnection networks on demand

In this paper, we introduce the FLUX interconnection networks, a scheme where the interconnections of a parallel system are established on demand before or during program execution. We present a programming paradigm which can be utilized to make the proposed solution feasible. We perform several experiments to show the viability of our approach and the potential performance gain of using the most suitable network configuration for a given parallel program. We experiment on several case studies, evaluate different algorithms, developed for meshes or trees, and map them on “grid”-like or reconfigurable physical interconnection networks. Our results clearly show that, based on the underlying network, different mappings are suitable for different algorithms. Even for a single algorithm different mappings are more appropriate, when the processing data size, the number of utilized nodes or the hardware cost of the processing elements changes. The implication of the above is that changing interconnection topologies/mappings (dynamically) on demand depending on the program needs can be beneficial.     

Tighter error bounds and weighted error metrics for hierarchical radiosity

In this paper we first derive a tighter error bound on form factors as a subdivision criterion for the hierarchical radiosity algorithm. Such an error bound can reduce more unnecessary links and improve the performance of the hierarchical radiosity algorithm to meet a user-specified error tolerance. We then propose a weighted error metric in form factor computation such that more effort is automatically applied to shadow boundaries. Evaluating form factors along shadow boundaries with a higher degree of precision should enhance the quality of human perception. Using the proposed tighter error bound on the weighted error metric, we not only improve the performance but also increase the accuracy of the hierarchical radiosity algorithm. © 1998 John Wiley & Sons, Ltd.     

Announced dynamic access probability protocol for next generation wireless networks

A multiple access protocol that is particularly suitable for cellular Internet access and satellite-based networks with on-board processing is developed in this paper. The basic idea is that when a user wishes to send a message, it transmits with probability p_access that depends on the load on the channel. Under conditions of low load, the probability p_access approaches 1, while at high load p_access is relatively low. This media access control protocol guarantees high channel utilization at high load, as well as low delay at low load periods. Using the statistical usage of the shared channel, the load is estimated with certain uncertainty. Our analysis shows that using the statistical usage of the shared channel, the optimal access probability can be well estimated for a broad class of load distribution patterns. In addition, we propose to use a central station to broadcast the value of p_access in networks with poor collision detection capability, or long feedback delay. The proposed method is particularly suitable for shared channels with poor collision detection capability, under conditions of bursty traffic and a large number of users. Examples for such channels are the reservation channel in satellite-based networks with on-board processing, and the control channel in cellular networks. Hence, the proposed method can be used for cellular Internet access and for accessing public satellite-based networks. The broadcast mechanism that already exists in such networks can be used to inform the users the dynamic access probability.     

Testing the dynamic full access property of a class of multistageinterconnection networks

The banyan network, and networks topologically equivalent to it, have recently been adopted as interconnection networks in multiprocessor systems. Often, a multiprocessor system is reconfigured when the banyan network becomes faulty. It is possible to avoid a complicated reconfiguration process as long as the faulty banyan network still possesses the dynamic full access (DFA) property. In this paper, we determine a necessary and sufficient condition for a faulty banyan network to possess the DFA property and design a test procedure based on the condition. The test procedure can be used to decompose a faulty banyan network into subsystems possessing the DFA property. We also evaluate the probability that a banyan network loses the DFA property, given the number of faulty switching elements. It is found that as long as faults do not occur in switching elements located in the first and last stages, this probability is very small, even when there are quite a few faulty switching elements     

Analysis of multiple-bus interconnection networks

The performance of multiple-bus interconnection networks for multiprocessor systems is analyzed, taking into account conflict arising from memory and bus interference. A discrete stochastic model of bandwidth is presented for systems in which each memory is connected either to all the buses or to a subset of the available buses. The effects of the assumptions made concerning independence among requests for different memories (spatial independence) and resubmission of blocked requests (temporal independence) are investigated systematically. The basic bandwidth model is extended to account for spatial dependence, and compared to previously proposed models. Finally, the various analytic models are shown to be in close agreement with simulation results.     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

Topology optimization of interconnection networks

This paper describes an automatic optimization tool that searches a family of network topologies to select the topology that best achieves a specified set of design goals while satisfying specified packaging constraints. Our tool uses a model of signaling technology that relates bandwidth, cost and distance of links. This model captures the distance-dependent bandwidth of modern high-speed electrical links and the cost differential between electrical and optical links. Using our optimization tool, we explore the design space of hybrid Clos-torus (C-T) networks. For a representative set of packaging constraints we determine the optimal hybrid C-T topology to minimize cost and the optimal C-T topology to minimize latency for various packet lengths. We then use the tool to measure the sensitivity of the optimal topology to several important packaging constraints such as pin count and critical distance.     

Performance of multiprocessor interconnection networks

A tutorial is provided on the performance evaluation of multiprocessor interconnection networks, to guide system designers in their design process. A classification of parallel/distributed systems is followed by a classification of multiprocessor interconnection networks. Basic terminology for performance evaluation is presented. The performance of crossbar interconnection networks, multistage interconnection networks, and multiple-bus systems is then addressed, and a comparison is made along them     

Equivalence of multistage interconnection networks

In recent years, many multistage interconnection networks using 2 × 2 switching cells have been proposed for parallel architecture. Here we state a correct and easy graph characterization of all the networks topologically equivalent to the Omega, Flip, Baseline, Reverse Baseline, Indirect Binary Cube, and Modified Data Manipulator networks.     

Equivalence relations among interconnection networks

The interconnection network equivalence notions reported in the literature are formalized via conjugation maps over the sets of interconnections of such networks. Various forms of relations including group isomorphisms among interconnection networks are introduced. Equivalence relations express the degrees of freedom in “making one network behave like another.” Examples of these relations for commutative cube-connected networks with individual stage control are also included. In addition, an algorithm is provided to construct equivalence maps among such networks.     

一种高阶混合互连网络拓扑结构

随着对高性能计算机性能需求的不断提升,高性能计算机的系统规模在逐渐扩大,系统内的互连网络已经成为影响性能的关键因素。如何基于高阶路由器构建更大规模、更低网络延迟以及成本、更高网络吞吐率的互连网络,是目前的主要研究方向。针对目前广泛应用的高阶网络进行特性分析,并对其中的环网以及树网进行综合,提出了一种新型层次化混合互连网络拓扑结构。该结构具有良好的可扩展性以及通信能力,并在网络模拟器NetSim上对其性能进行了仿真和分析。     

Adaptive flow control in high-performance interconnection networks

The flow-control mechanism determinates the manner in which the communicational resources are allocated. Well-designed flow-control mechanism should provide efficient allocation of the communicational resources in wide variety of interconnection networks. The goal of this paper is to suggest a highly effective “Step-Back-on-Blocking” buffered flow control. The proposed flow-control mechanism combines the advantages of the Wormhole and Virtual-Cut Through flow controls, whilst adds a means for adaptive allocation of the communicational resources. The “Step-Back-on-Blocking” flow control provides low message latency and achieves high fraction of the channel bandwidth by performing conditional evasion of temporary blocked network resources. The effectiveness of the proposed flow control has been evaluated on the basis of numerous experiments conducted in OMNet++ discrete event simulation environment.     

Alternate resolution strategy in multistage interconnection networks

Multistage interconnection networks have been proposed by many research groups to provide communication between processor and memory module in multiprocessor systems. However, two different processor requests may result in a conflict on the path establishment. For multistage interconnection networks operated in circuit switching mode, the drop approach and the hold approach are often employed to solve the conflict problem in path establishment. In this paper, we propose another resolution, the preemptive hold approach, to solve the conflict problem in path establishment. The proposed approach requires a minor modification in the design of the switching element in multistage interconnection networks. From simulation results, we find that the bandwidth of our proposed resolution approach is higher than those of the other two approaches. Meanwhile, we also propose an analytical model to analyze the bandwidth of the drop approach in multistage interconnection networks.     

Reducing complexity in tree-like computer interconnection networks

Interconnection networks based on the k-ary n-tree topology are widely used in high-performance parallel computers. However, this topology is expensive and complex to build. In this paper we evaluate an alternative tree-like topology that is cheaper in terms of cost and complexity because it uses fewer switches and links. This alternative topology leaves unused upward ports on switches, which can be rearranged to be used as downward ports. The increase of locality might be efficiently exploited by applications. We test the performance of these thin-trees, and compare it with that of regular trees. Evaluation is carried out using a collection of synthetic traffic patterns that emulate the behavior of scientific applications and functions within message passing libraries, not only in terms of sources and destinations of messages, but also considering the causal relationships among them. We also propose a methodology to perform cost and performance analysis of different networks. Our main conclusion is that, for the set of studied workloads, the performance drop in thin-trees is less noticeable than the cost savings.     

SLA-controlled interconnection charging in next generation networks

Next generation network (NGN) should facilitate a single party to establish quality of service (QoS) enabled path between the two IP providers mutually interconnected by one or more transit providers. For that purpose, an end-to-end service level agreement (SLA) should be negotiated and maintained. In this article, we propose interconnection charging, which is controlled by the end-to-end SLA. Relationships between the required, offered, and actually achieved inter-provider QoS are quantified through the degrees of offering and provisioning, at both end-to-end and per-domain levels. Nominal retail price offered to end users and interconnection costs related with particular SLA are then corrected if needed, depending on the offered and provisioned QoS levels. We further propose five policies for interconnection charging and compare them under different QoS provisioning scenarios. Results of the analysis indicate that a properly selected SLA-controlled interconnection charging policy should encourage providers: (1) to offer services with different QoS levels; (2) to offer service that perfectly or most approximately matches the required QoS and (3) to achieve the contracted QoS level.     

The cross product of interconnection networks

We study the cross product as a method for generating and analyzing interconnection network topologies for multiprocessor systems. Consider two interconnection graphs G₁ and G₂ each with some established properties such as symmetry, low degree and diameter, scalability, simple optimal routing, recursive structure (partitionability), fault tolerance, existence of node-disjoint paths, low cost embedding, and efficient broadcasting. We investigate and evaluate the corresponding properties for the cross product of G₁ and G₂ based on the properties of G₁ and those of G₂. We also give a mathematical characterization of product families of graphs which are closed under the cross product operation. This investigation is useful in two ways. On one hand, it gives a new tool for further studying some of the known interconnection topologies, such as the hypercube and the mesh, which can be defined using the cross product operation. On the other hand, it can be used in defining and evaluating new interconnection graphs using the cross product operation on known topologies     

Analytic models for multistage interconnection networks

Central to all parallel architectures is a switching network which facilitates the communication between a machine's components necessary to support their cooperation. Multistage interconnection networks (MINs) are classified and analytic models are described for both packet-switched and circuit-switched MINs with asynchronous transmission mode. Under strong enough assumptions, packet switching can be modeled by standard queuing methods, hence providing a standard against which to assess approximate models. We describe one such approximate model with much weaker assumptions which is more widely applicable and can be implemented more efficiently. To model circuit switching requires a different approach because of the presence of passive resources, namely multiple links through the MIN which must be held before a message can be transmitted and throughout its transmission. An approximate analysis based upon the recursive structure of a particular MIN topology which yields accurate predictions when compared with simulation is described.     

实现无线传感器网络与IPv6网络互联的一种方案

提出并设计了无线传感器网络与IPv6网络无缝互联的通信模型。此模型提出了一种传感器地址自动配置方案,并在此方案之上实现了传感器节点的自动寻址路由。此外,给出了一种适用于无线传感器网络（WSN）的IPv6协议裁剪方案,以节省传感器节点的功耗。在实验平台及仿真环境中,实现了模型并且分析了模型的性能,实验结果证明了此模型的有效性和正确性。