Reliable broadcasting in wormhole-routed hypercube-connected networks using local safety information

This paper presents a method to cope with reliable broadcasting in faulty hypercubes using local safety information. A new definition, broadcast subcube, is introduced, with which various techniques are proposed to improve performance of the broadcast algorithm. Local safety information is well used in the fault-tolerant broadcast algorithm by considering only safety of the broadcast subcube. An unsafe hypercube can be split into a set of maximal safe subcubes. If these maximal safe subcubes meet certain requirements (listed in this paper), then broadcasting can still be done successfully and, in some cases, optimal broadcast is still possible. The sufficient condition for optimal broadcast of a message is presented in an unsafe hypercube. Extensive simulation results show that the proposed method outperforms previous methods, in all cases.     

超立方体网络中基于局部安全信息的广播容错路由研究

针对具有错误节点和故障链路的超立方体网络,改进了一种算法实现可靠的容错广播路由。在没有安全结点的不安全的超立方体网络中,将网络分成一系列最大安全子立方体,根据提出的故障链路处理方法和选择广播路由的准则,改进了基于局部安全信息的广播路由算法。证明了根据文中算法,这些最大安全子立方体在满足文中要求的情况下,仍有可能实现可靠的广播路由,有效地提高了信息路由的可靠性。提供了实例介绍文中算法的原理和优点。     

交换超立方体的拓扑性质与嵌入问题研究

 交换超立方体(Exchanged hypercube)作为超立方体的一种变型网络,降低了网络规模增大时所需要的拓扑连接的开销.本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS(s,t)和EHT(s,t)的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}.为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Q_n-1能够同胚地嵌入到交换超立方体EH(s,t)中.     

Reliability analysis of hypercube multicomputers

This paper proposes a topology-based general algorithm to generate all Markov states of an n-dimensional hypercube. Considering the system to be degradable, we define task-based reliability (TBR) measures for the hypercubes. Using the proposed algorithm, Markov models for two and three-dimensional hypercubes are developed and solved to obtain various task-based reliability measures. Markov states for hypercubes of higher dimensions are generated using the proposed method. Results are validated through extensive simulation.     

Reliability evaluation of hypercube multicomputers

An analytic model for the reliability evaluation of hypercube multicomputers is presented. The model is based on the decomposition principle, where a hypercube of a higher dimension is recursively decomposed into smaller hypercubes, until the reliability of the smallest cube is modeled exactly. The reliability of the large n-cube is then obtained from this smallest base model using a recursive equation. The reliability model used is task-based, i.e., it is assumed that the system is operational if a task can be executed on the system. Analytic results are given for n-dimensional hypercubes with up to 75% system degradation. The model is validated by comparison of analytic results with simulation results     

Partitionable multistage interconnection networks. Part 2: Task migration schemes

A new subcube migration scheme for maximally utilizing system resources is proposed for multiprocessor systems based on multistage interconnection networks (MINs). The objective is to migrate tasks to create larger free subcubes; this is referred to as subcube migration. After the migration, we can then apply the more conventional subcube compaction schemes. First, the problem formulation is presented and the goals are set for the solution. It is shown that the migration problem is, in fact, not just a one subcube to one subcube migration problem (as treated in the previous work), but rather a many subcubes to many subcubes migration problem. This problem analysis and formulation lead us to a sophisticated subcube migration scheme. This scheme, thus, successfully handles many‐to‐many subcube migrations. It is not only near‐optimal but also scalable for different sizes of the multiprocessors. Extensive experiments were performed over a wide range of load distributions and problem sizes; the results show that for problems sizes of all practical purposes, the proposed scheme achieves very high system utilization, while requiring little computing time. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performability of the hypercube [reliability]

The authors address the problem of modeling and evaluating the composite performance and reliability measures (performability) of a hypercube architecture running a specific application. A generalized stochastic Petri net (GSPN) is used to model the component failures and repairs in the hypercube. The GSPN model defines the dimension and number of subcubes available for the application. This model generalizes previously proposed models for hypercube reliability and automatically generates the underlying Markov chain needed for performability analysis. A novel performability analysis algorithm is presented that computes both the moments and the distribution of performability in O( N³). The algorithm is conceptually simpler than those previously reported. An example is given to illustrate the modeling process and demonstrate the importance of performability analysis for mission-critical systems     

An optical multi-mesh hypercube: a scalable optical interconnectionnetwork for massively parallel computing

A new interconnection network for massively parallel computing is introduced. This network is called an optical multi-mesh hypercube (OMMH) network. The OMMH integrates positive features of both hypercube (small diameter, high connectivity, symmetry, simple control and routing, fault tolerance, etc.) and mesh (constant node degree and scalability) topologies and at the same time circumvents their limitations (e.g., the lack of scalability of hypercubes, and the large diameter of meshes). The OMMH can maintain a constant node degree regardless of the increase in the network size. In addition, the flexibility of the OMMH network makes it well suited for optical implementations. This paper presents the OMMH topology, analyzes its architectural properties and potentials for massively parallel computing, and compares it to the hypercube. Moreover, it also presents a three-dimensional optical design methodology based on free-space optics. The proposed optical implementation has totally space-invariant connection patterns at every node, which enables the OMMH to be highly amenable to optical implementation using simple and efficient large space-bandwidth product space-invariant optical elements     

A general scheme for constructing optimal bus based architectures for hypercubes

We present a general methodology for constructing optimal bus based hypercubes. The methodology encompasses previously proposed bus based hypercubes. If m _n is the total number of different unidirectional Multiple Bus Systems (MBSs) that can optimally emulate the n‐dimensional hypercube, then σ_n≤ m _n ≤σ_n, where σ _n denotes the number of unlabeled trees on n edges. Each such MBS is symmetric with respect to the buses and processors, and has n + 1 ports per processor, whereas the hypercube has 2n ports per processor. We choose one specific MBS from those optimal MBSs and demonstrate its other attractive properties. It can simultaneously perform data transfers across as many as n dimensions. It is fault tolerant with respect to a bus, a processor, or an interface failure. We also show how to construct optimal bidirectional MBSs emulating hypercubes. The new architecture is very similar to the unidirectional one; yet it has half the number of buses and half the number of interfaces. It can simultaneously transfer data across as many as n dimensions. Its fault tolerance is similar to that of the unidirectional MBS. This revised version was published online in June 2006 with corrections to the Cover Date.     

Reliability modeling and assessment of the Star-Graph networks

The reliability of the Star Graph architecture is discussed. The robustness of the Star Graph network under node failures, link failures, and combined node and link failures is shown. The degradation of the Star Graph into Substar Graphs is used as the measure of system effectiveness in the face of failures. Models are provided for each of the failure and re-mapping modes evaluated herein, and the resilience of the Star Graph to failures is emphasized. This paper defines failure of a Star Graph as being when no fault-free (n - 1)-substars remain operational and the intermediate states are defined by the number of (n - 1)-substars that remain operational. A powerful tool (re-mapping) is introduced in which the number of operational (n 1)-substars can be maintained for longer periods, thus improving the overall MTTF (mean time to failure). For comparison the results of a similar reliability analysis of the hypercube is shown. The comparisons are considered conservative due to the failure model used herein for the star graph. One might apply re-mapping to hypercubes; while it would improve the overall MTTF of hypercubes, the hypercubes would still have an appreciably poorer performance than star graphs     

Content‐Based Image Retrieval Based on Relevance Feedback and Reinforcement Learning for Medical Images

To enable a relevance feedback paradigm to evolve itself by users’ feedback, a reinforcement learning method is proposed. The feature space of the medical images is partitioned into positive and negative hypercubes by the system. Each hypercube constitutes an individual in a genetic algorithm infrastructure. The rules take recombination and mutation operators to make new rules for better exploring the feature space. The effectiveness of the rules is checked by a scoring method by which the ineffective rules will be omitted gradually and the effective ones survive. Our experiments on a set of 10,004 images from the IRMA database show that the proposed approach can better describe the semantic content of images for image retrieval with respect to other existing approaches in the literature.     

A concurrent implementation of the prime factor algorithm onhypercube

The prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm in which a one-dimensional DFT is tuned into a multidimensional DFT, consisting of a few short DFTs whose lengths are mutually prime, and then an efficient algorithm is used for the short DFTs. The PFA was implemented on a hypercube using CrOS III communication routines, taking 120 ms to compute the DFT of 5040 complex points using 32 nodes of the Caltech-JPL MARK III Hypercube. It took 105 ms to do a DFT of 4096 complex points using the Cooley-Tukey algorithm with the same hardware configuration. The performance of hypercubes MARK III, NCUBE, and iPSC and the relative importance of communication and calculation are analyzed. With the current communication speed the Cooley-Tukey algorithm performs fast on a massively concurrent processor and the PFA is advantageous when the number of processors is less than 64 or so. The experience with using the PFA also serves as a useful guide to a multidimensional fast Fourier transform implementation using any algorithm     

基于时空混合图卷积网络的机器人定位误差预测及补偿方法

工业机器人作为智能制造的重要载体,在大范围复杂任务中具有巨大潜力。但是,定位精度低且难以控制的问题阻碍了机器人在高精度任务的进一步推广。为了提升机器人作业精度,该文提出一种基于时空混合图卷积网络的机器人定位误差预测及补偿方法。首先通过设计图关系编码模块、时空混合特征解码模块,构建基于图卷积网络的机器人位姿误差预测模型;然后,针对传统迭代补偿方法中机器人逆解次数多导致效率低的问题,该文将定位误差补偿问题转化为优化问题,并利用遗传算法同时对位置和姿态进行误差补偿;最后,通过拉丁超立方抽样方法获得训练集,实现机器人定位误差预测模型的训练,并通过实验验证了定位误差预测的准确性以及补偿的效果。     

Analysis of scheduling parallel tasks on hypercube systems

The problem of scheduling independent parallel tasks with the consideration of setup time on a d-dimensional hypercube system is investigated. The objective of this problem is to find a schedule with minimum finish time; such a scheduling problem is NP-hard. Therefore, a heuristic algorithm is proposed and its performance bound derived     

Modelling fully‐adaptive routing in hypercubes

Analytical models for wormhole‐routed hypercubes with deterministic routing have been widely reported in the literature. A model for the hypercube with fully‐adaptive routing has recently been proposed in [1]. It uses M/M/1 queues, and computes a different probability of blocking at each intermediate router along the message path. As a result, the number of equations, and thus the computation steps, to evaluate latency increases with the network size. This paper proposes an alternative model that uses M/G/1 queues, and requires a constant number of computation steps irrespective of the network size. It achieves this by computing only once the mean probability of blocking across the entire path, and using it to determine the blocking time at a given router. Simulation experiments reveal that the model yields accurate latency results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fault tolerance in the Block-Shift Network

The Block Shift Network (BSN) is a new topology for interconnection networks in multiprocessor systems. BSN is a class of networks defined by several parameters, and has a constant number of links/node for some given parameters. Many popular networks such as the hypercube, the shuffle-exchange, and the complete networks, are instances of the BSN for different parameters. Performance of BSN has been evaluated through analysis, simulation, and design of typical parallel algorithms on it. The results indicate that BSN surpasses the hypercube in several respects while retaining most of the hypercube advantages, especially when the traffic has the locality property. As the size and complexity of a system increase, however, the reliability aspects become equally important and should be included in the system-performance study. This paper discusses the reliability issue of BSN. Several reliability measures, including network connectivity, network diagnosability, and 2-terminal reliability, are obtained through analysis. This paper shows that the BSN not only surpasses the hypercube in performance as confirmed before, but also has comparable reliability to the hypercube under similar conditions. BSN is also very flexible in balancing its cost and performance. One can increase two parameters to enhance the performance and reliability of the BSN, while it is impossible to do so in the hypercube once its size is fixed. The BSN can be an effective interconnection network for future parallel computer systems     

Sphere-packing upper bounds on the free distance of trellis codes

Sphere-packing arguments are used to develop upper bounds on the free distance of trellis codes. A general bounding procedure is presented. Sphere packing bounds, including bounds on the density of infinite regions, packings for hypercubes, and packings on the surface of a unit sphere, are then used to produce bounds for a wide variety of trellis codes. Among the applications are convolutional codes, Ungerboeck codes for phase-shift keying and quadrature amplitude modulation, coset codes, and continuous phase modulation codes. The new bounds are significantly tighter than existing bounds in many cases of practical interest     

A spanning bus connected hypercube: a new scalable opticalinterconnection network for multiprocessors and massively parallelsystems

A new scalable interconnection topology suitable for massively parallel systems called the spanning bus connected hypercube (SBCH) is proposed. The SBCH uses the hypercube topology as a basic building block and connects such building blocks using multidimensional spanning buses. In doing so, the SBCH combines positive features of both the hypercube (small diameter, high connectivity, symmetry, simple routing, and fault tolerance) and the spanning bus hypercube (SBH) (constant node degree, scalability, and ease of physical implementation), while at the same time circumventing their disadvantages. The SBCH topology permits the efficient support of many communication patterns found in different classes of computation such as bus-based, mesh-based, tree-based problems as well as hypercube-based problems. A very attractive feature of the SBCH network is its ability to support a large number of processors while maintaining a constant degree and constant diameter. Other positive features include symmetry, incremental scalability, and fault-tolerance. An optical implementation methodology is proposed for SBCH. The implementation methodology combines both the advantages of free space optics with those of wavelength division multiplexing techniques. A detailed analysis of the feasibility of the proposed network is also presented     

On the cyclostationary statistics of ultra-wideband signals in the presence of timing and frequency jitter

Cyclostationarity is an inherent characteristic of many man-made communication signals, which, if properly recognized, can be exploited for performing various signal-processing tasks. Determining the cyclostationary characteristics of a signal of interest is the first step in the design of signal processing systems exploiting this cyclostationary behaviour. This paper investigates the cyclostationary statistics of various signalling schemes employed in ultra-wideband (UWB) communication systems. Analytical expressions are derived for the cyclic autocorrelation and spectral correlation density functions in the presence of random timing and frequency jitter, which are characterized by discrete-time stationary random processes with known distribution functions.     

Hypercube-based architecture for high speed communication systems

An implementation is presented of digital demultiplexing and demodulation algorithms for an advanced satellite communication system on a hypercube. The mapping on a hypercube provides the high speed necessary for processing hundreds of single channel per carrier/frequency division multiple access (SCPC/FDMA) voice/data channels. Data demultiplexing and demodulation are parts of the recovery of the transmitted digital data in a MODEM. A demultiplexer comprises a filter bank followed by the computation of FFT. A demodulator primarily consists of circuits to recovery carrier signal, clock frequency and data. The computation of FFT on a hypercube is well established (Hwang and Briggs 1984). Therefore, this paper analyses the filter bank and carrier and data recovery algorithms to find an efficient mapping in a multiprocessor environment connected in a hypercubic configuration. A few models to implement these algorithms on a hypercube are provided. Comparison of the speed-up achieved on a hypercube vrsus that on a sequential computer is provided for the three models.