An new representation for interconnection network structures

An important theoretic interest is to study the relations between different interconnection networks, and to compare the capability and performance of the network structures. The most popular way to do the investigation is network emulation. Based on the classical voltage graph theory, the authors develop a new representation scheme for interconnection network structures. The new approach is a combination of algebraic methods and combinatorial methods. The results demonstrate that the voltage graph theory is a powerful tool for representing well known interconnection networks and in implementing optimal network emulation algorithms, and in particular, show that all popular interconnection networks have very simple and intuitive representations under the new scheme. The new representation scheme also offers powerful tools for the study of network routings and emulations. For example, we present very simple constructions for optimal network emulations from the cube connected cycles networks to the butterfly networks, and from the butterfly networks to the hypercube networks. Compared with the most popular way of network emulation, this new scheme is intuitive and easy to realize, and easy to apply to other network structures.

All-To-All Personalized Communication in Wormhole-Routed 2D/3D Meshes and Multidimensional Interconnection Networks

All-to-all personalized communication,or complete exchange,is at the heart of numerous applications in paral-lel computing.It is one of the most dense communication patterns.In this paper,we consider this problem in a2D/3D mesh and a multidimensional interconnection network with the wormhole-routing capability.We propose complete ex-change algorithms for them respectively.We propose O(mn 2 )phase algorithm for2D mesh P m ×P n and O(mn 2 l 2 )phase algo-rithm for3D mesh P m ×P n ×P l ,where m,n,l are any positive integers.Also O(ph(G 1 )n 2 )phase algorithm is proposed for a multidimensional interconnection network G 1 ×G 2 ,where ph(G 1 )stands for complete exchange phases of G 1 and|G 2 |=n.

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2] +2, k + 5, [k/2] + 2, and k + 5 respectively. The RP(k) network and the routing algorithms can provide efficient communication means for parallel and distributed computer system.

Energy-efficient task allocation for reliable parallel computation of cluster-based wireless sensor network in edge computing

To efficiently complete a complex computation task,the complex task should be decomposed into subcomputation tasks that run parallel in edge computing.Wireless Sensor Network(WSN)is a typical application of parallel computation.To achieve highly reliable parallel computation for wireless sensor network,the network's lifetime needs to be extended.Therefore,a proper task allocation strategy is needed to reduce the energy consumption and balance the load of the network.This paper proposes a task model and a cluster-based WSN model in edge computing.In our model,different tasks require different types of resources and different sensors provide different types of resources,so our model is heterogeneous,which makes the model more practical.Then we propose a task allocation algorithm that combines the Genetic Algorithm(GA)and the Ant Colony Optimization(ACO)algorithm.The algorithm concentrates on energy conservation and load balancing so that the lifetime of the network can be extended.The experimental result shows the algorithm's effectiveness and advantages in energy conservation and load balancing.

A Routing Algorithm for Distributed Optimal Double Loop Computer Networks

A routing algorithm for distributed optimal double loop computer networks is proposed and analyzed. In this paper, the routing algorithm rule is described, and the procedures realizing the algorithm are given. The proposed algorithm is shown to be optimal and robust for optimal double loop. In the absence of failures,the algorithm can send a packet along the shortest path to destination; when there are failures,the packet can bypasss failed nodes and links.

BALANCE ROUTING TRAFFIC IN GENERALIZED SHUFFLE-EXCHANGE NETWORK

A methodology is proposed to handle problem that under equiproble address of packet traffic at the input port, Generalized Shuffle-Exchange Network (GSEN) routes traffic unevenly because of the unbalanced routing tags. The idea is to use routing tag according to probability, which can be evaluated by using Moore-Penrose inverse in matrix analysis. An instance is used to illustrate the idea, and the simulation is done to show the improvement in performance issues.

Fast and scalable routing protocols for data center networks

Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.

A Neurocomputing Model for Binary Coded Genetic Algorithm

A neurocomputing model for Genetic Algorithm (GA) to break the speed bottleneck of GA was proposed. With all genetic operations parallel implemented by NN-based sub-modules, the model integrates both the strongpoint of parallel GA (PGA) and those of hardware GA (HGA). Moreover a new crossover operator named universe crossover was also proposed to suit the NN-based realization. This model was tested with a benchmark function set, and the experimental results validated the potential of the neurocomputing model. The significance of this model means that HGA and PGA can be integrated and the inherent parallelism of GA can be explicitly and farthest realized, as a result, the optimization speed of GA will be accelerated by one or two magnitudes compered to the serial implementation with same speed hardware, and GA will be turned from an algorithm into a machine.

Wormhole Routing──大规模并行处理系统中的一项关键技术

本文详细介绍了基于直接网络的大规模并行计算机的ＷｏｒｍｈｏｌｅＲｏｕｔｉｎｇ的原理。Ｗｏｒｍｈｏｌｅ寻径算法以及其它与通信性能有关的技术问题。

Ferroelectric Liquid Crystal Gates and Optical Computing

The surface stabilized ferroelectric liquid crystal device configuration and ferroelectric liquid crystal gates are described.The liquid crystal electrooptical gates have numerous applications,including optical computation,optodigital circuits,and optical communication networks.

THE PN2I NETWORK: A SCALABLE BANYAN NETWORK

To design a Banyan network with an arbitrary even-sized port number, the PN2I network is proposed. The PN2I network can be divided into two classes: the complete and incomplete versions. A simple routing algorithm is given, but in the incomplete PN2I networks,this routing algorithm fails to make the traffic in links even, which deteriorates the performance badly. Thus a new routing algorithm is proposed, which makes the incomplete PN2I networks behave almost the same as the PN2I networks with respect to the performance issues.

增广立方体上边独立生成树的并行构造

近年来,围绕互连网络的研究工作越来越多。其中独立生成树(Independent Spanning Trees,ISTs)可以应用于信息的可靠传输、并行传输、安全分发以及故障服务器的并行诊断中,因此受到了许多研究者的关注。在一对多广播、可靠通信、多节点广播、容错广播、安全消息分发、IP快速重路由等网络通信中,边独立生成树(Edge-Independent Spanning Trees,EISTs)发挥着重要作用。n维增广立方体AQ_(n)是n维超立方体Q_(n)的节点对称变型,它具有超立方体及其变型所没有的一些可嵌入性质。然而,目前增广立方体上边独立生成树的构造方法都是串行构造的。文中首先提出了一种并行算法,用于构造以AQ_(n)中的任意节点为根的2n-1棵树。然后证明算法得到的2n-1棵树是高度为n的边独立生成树,算法的时间复杂度为O(N),其中N表示增广立方体中的节点数。最后通过模拟实验来验证了所提方法的准确性。

Optimum Tactics of Parallel Multi-Grid Algorithm with Virtual Boundary Forecast Method Running on a Local Network with the PVM Platform

In this paper, an optimum tactic of multi-grid parallel algorithmwith virtual boundary forecast method is disscussed, and a two-stage implementationis presented. The numerical results of solving a non-linear heat transfer equationshow that the optimum implementation is much better than the non-optimum one.

Virtual channel load-balanced routing algorithm for Torus networks

In order to improve the network performance furthermore, a routing algorithm for 2D-Torus is investigated from the standpoint of load balance for virtual channels. The 2D-Torus network is divided into two virtual networks and each physical channel is split into three virtual channels. A novel virtual channel allocation policy and a routing algorithm are proposed, in which traffic load is distributed to those three virtual channels in a more load-balanced manner by introducing a random parameter. Simulations of the proposed algorithm are developed with a SystemC-based test bench. The results show that compared with the negative first for Torus networks （NF-T） algorithm, the proposed algorithm can achieve better performance in terms of network latency and throughput under different traffic patterns. It also shows that a routing algorithm with load balance for virtual channels can significantly improve the network performance furthermore.

基于大数据的电力通信通道智能路由推荐策略研究

面对规模庞大、结构复杂的电力通信网,针对通信调度如何根据业务需求准确、合理、高效地安排通信通道,提出了一种基于分布式图并行计算的大数据智能路由推荐方法。该方法根据电力通信网特点构建电力通信网络拓扑模型、建立优选路由指标模型,并采用基于分布式图并行计算框架实现并行路由推荐算法。实验证明,该方法具有快速迭代与收敛的特性,在大型复杂的电力通信网络路由推荐与规划中具有良好的应用前景。

Topological properties and routing algorithm for semi-diagonal torus networks

To improve the scalability and reduce the implementation complexity of Mesh and Mesh-like networks, the semi-diagonal Torus （SD-Torus） network, a regular and symmetrical intercormection network is proposed. The SD-Torus network is a combination of a typical 2D-Torus network with two extra diagonal links from northwest to southeast direction for each node. The topological properties of SD-Torus networks are discussed, and a load balanced routing algorithm for SD-Torus is presented. System-C based simulation result shows that, compared with diagonal Mesh （DMesh）, diagonal Torus （DTorus） and XMesh networks, the SD-Torus network can achieve high performance with a lower network cost. It makes the SD-Torus network a powerful candidate for the high performance interconnection networks.

基于量子粒子群算法的计算机通信网络路由选择优化方法

针对当前计算机通信网络路由选择不合理,造成网络中最大链路利用率和平均链路利用率无法控制在规定要求的理想范围内的问题,引入量子粒子群算法,开展计算机通信网络路由选择优化方法设计研究。明确路由选择目标,建立计算机通信网络路由选择函数。利用量子粒子群算法,实现对路由的优化选择。通过对优化前后对比得出,优化方法的应用可以使计算机通信网络最大链路利用率和平均链路利用率控制在理想范围内,提高计算机通信网络通信质量。

智能搜索算法在计算机网络动态路由优化中的应用

阐述智能搜索算法在计算机网络中的应用、动态路由优化的特点。分析智能搜索算法的原理和类型,提出评价智能搜索算法性能的指标和方法,包括延迟、带宽利用率、负载均衡和鲁棒性。

基于DSP模式的计算机图像处理算法研究

基于DSP架构模式,提出了一种CNN卷积神经网络算法,并将其运用到计算机图像处理中。研究过程中,采用DSP技术进行计算机图像获取、算法处理、算例分析和结果优化,大大提高了计算机图像算法处理质量和效率。经过算法测试验证,结果表明,基于DSP数字信号处理器搭建多DSP并行处理架构模式,采用CNN卷积神经网络算法进行计算机图像处理,能够提高图像处理精度。该算法运行时的性能较高,功能低,CPU占用率不高,且DSP计算机处理系统在多DSP并行处理架构模式下进行算法分析,系统的稳健性和可靠性高,能够适应不同规模级别下的计算机图像处理数据集的处理速度、精度、资源消耗和功率要求,可为计算机图像算法处理提供准确、高效、经济的解决方案,对于计算机图像处理算法设计和优化以及应用具有较好的实用参考价值。

互联网络服务质量路由算法研究综述

如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1) 满足业务QoS需求;(2) 最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.