检索结果-内蒙古大学图书馆

Oblivious routing for LC permutations on hypercubes

PARALLEL COMPUTING 1999年第4期25卷 445-460页

作者： Liu, ZY Cheung, DW Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong MIT Comp Sci Lab Cambridge MA 02139 USA

We propose an oblivious algorithm to route linear-complement (LC) permutations on hypercubes in circuit switched and wormhole routing. The algorithm guarantees that N independent paths can be set up simultaneously for any LC permutation with only a comparison of two bits in one routing step for any path. An LC permutation is determined by a transformation matrix T and a constant modifier C. For all the LC permutations with the same transformation matrix T (we call them a type of permutations), an algorithm is executed to find an ordered sequence of dimensions without knowing a particular permutation. When the sequence of dimensions is used in the routing process for all the packets of a permutation of this type, a comparison of two bits is carried out in each routing step in the packet transmission process. It is guaranteed that no contention will occur between any two paths on the use of the dimensional links, thus N independent paths can be set up simultaneously for the N packets of an LC permutation. Time complexity of the algorithm for finding an ordered sequence for the use of the n dimensions is O(n(3)) for any type of LC permutations (rather than one particular LC permutation), and it can be carried out off-line. The routing process itself is distributed, and oblivious. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： parallel processing hypercube linear-complement permutations routing algorithms circuit switched routing wormhole routing

来源：评论

学校读者我要写书评

暂无评论

Inter-domain routing for communication networks using Hierarchical Hopfield Neural Networks

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2018年 70卷 184-198页

作者： Silva, Hitalo O. Bastos-Filho, Carmelo J. A. Univ Pernambuco Polytech Sch Pernambuco Recife PE Brazil

This paper presents the Hierarchical Hopfield Neural Networks (HHNN). HHNN is a novel Hopfield Neural Network (HNN) approach. HHNN is composed of a hierarchy of self-sufficient HNNs, aiming to reduce the neural network structure and mitigate convergence problems. The HNNN composition depends on the applied problem. In this paper, the problem approached is the inter-domain routing for communication networks. Thus, the hierarchy of HNNs mimics the structure of communication networks (domains, nodes, and links). The proof of concept and the comparison between HNNN with the state-of-art HNN occurs using an implementation of them in the Java programming language. Besides, the performance analysis of the HHNN runs on a parallel hardware platform, using VHDL to develop it. The results have demonstrated a reduction of 93.75% and 99.98% in the number of neurons and connections to build the neural network, respectively. Furthermore, the mean time to achieve convergence of HHNN is rough 1.52% of the total time needed by the current state-of-art HNN approach. It is also less susceptible to early convergence problems when used in communications networks with a large number of nodes. Last, but not least, the VHDL implementation shows that convergence time of HHNN is comparable to routing algorithms used in practical applications.

关键词： Hopfield Neural Networks routing algorithms Communication networks Artificial neural networks

来源：评论

学校读者我要写书评

暂无评论

Heuristics in the routing algorithm for circuit layout design

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2000年第2期147卷 59-64页

作者： Mani, N Quach, NH Monash Univ Dept Elect & Comp Syst Engn Clayton Vic 3168 Australia

New heuristics in solving the maze routing problem are presented. The proposed MQ algorithm generates a shortest path based on the depth-first vertex traversal approach in the direction towards the target. A set of heuristics is formulated by assigning a directional priority sequence to each vertex while finding the path. This method will find a shortest path between two points, if one exists, on a rectangular grid-of vertices. Some vertices, named blocking vertices, are occupied by other circuitry or by paths already routed, and hence are not available for routing. Blocking vertices are introduced as a means of modelling obstacles during the path finding process. An implementation of the algorithm and its experimental results are also reported.

关键词： Heuristics routing algorithms circuit layout

来源：评论

学校读者我要写书评

暂无评论

A NEW routing ALGORITHM FOR CYCLIC SHIFTS ON BRGC HYPERCUBES

引用

INFORMATION PROCESSING LETTERS 1994年第4期49卷 165-169页

作者： WANG, CM ACAD SINICA INST INFORMAT SCITAIPEI 11529TAIWAN

The hypercube is one of the most efficient networks for parallel computation. It can efficiently simulate any other network of the same size. Arrays are natural structures for many applications. They can be embedded onto hypercubes either in natural order or in binary-reflected gray code (BRGC) order. The existing cyclic shift algorithms for the BRGC embedding usually route a message by correcting successive bits that differ in source and sink nodes from the less significant end to the more significant end or in the other order with some exceptions. However, all the algorithms have their drawbacks. A new routing algorithm for cyclic shifts on BRGC hypercubes is proposed. It is based on the divide-and-conquer approach. It uses, at most, n links to route a message from any node to its cyclic shifted sink node on an n-dimensional BRGC hypercube and is link-disjoint such that each link is used, at most, once in all routing paths. Therefore it is superior to other cyclic shift algorithms for BRGC hypercubes.

关键词： CYCLIC SHIFTS EMBEDDING HYPERCUBES PARALLEL PROCESSING routing algorithms

来源：评论

学校读者我要写书评

暂无评论

A practical network coding and routing scheme based on maximum flow combination

引用

INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT 2012年第5期22卷 373-396页

作者： Wu, Lianlong Curran, Kevin Univ Ulster Fac Comp & Engn Sch Comp & Intelligent Syst Londonderry BT48 7JL North Ireland

Network coding is a novel field of information theory and coding theory. It is a breakthrough over the traditional store-and-forward routing methods by allowing coding of two or more packets together. From an information flow aspect, multiple flows could be overlapped in a routing scheme. Hence the theoretical upper bound of multicast capacity could be achieved by network coding. In this project, a complete routing and coding scheme is constructed to realize the maximum multicast transportation task. In order to implement the scheme, the paths of multiple max-flows are determined. Edges are divided into overlapped and normal type based on the merged max-flows. The transmitting data are represented using packets in a specific format. Multicast, forward and coding operations are defined to transmit data at the nodes. The nodes are classified according to the type of operation. A dynamic coding and routing algorithm is proposed to route packets gradually from source node to destinations in topological sorting order by the three operations on the path of merged max-flows. We show that the use of simple XOR operations can satisfy most of the network topologies. The running time of the algorithm presented here is less than 1 second for most of the benchmark and random datasets. Copyright (C) 2012 John Wiley & Sons, Ltd.

关键词： Information Theory Network coding overlaps Surgery Network routing Runtime routing algorithms Packet Shannon\'s theory Maximum Flow

来源：评论

学校读者我要写书评

暂无评论

A Whale Swarm-Based Energy Efficient routing Algorithm for Wireless Sensor Networks

引用

IEEE SENSORS JOURNAL 2024年第12期24卷 19964-19981页

作者： Zeng, Bing Deng, Jiewen Dong, Yan Yang, Xuebing Huang, Lingxiang Xiao, Zhao Huazhong Univ Sci & Technol Sch Mech Sci & Engn State Key Lab Digital Mfg Equipment & Technol Wuhan Hubei Peoples R China Wind Power Co Ltd Harbin Elec Corp State Key Lab Offshore Wind Power Equipment & Eff Xiangtan 411102 Hunan Peoples R China Hunan Univ Sci & Technol Sch Mech Engn Xiangtan 411201 Hunan Peoples R China Huazhong Univ Sci & Technol Sch Elect Informat & Commun Wuhan 430074 Hubei Peoples R China

Developing energy-efficient routing algorithms is key to reducing energy consumption of wireless sensor networks (WSNs), and the WSNs energy-efficient routing is a combinatorial optimization problem. Many researchers try to optimize it with metaheuristics. However, most metaheuristics are inappropriate in designing routing algorithms for WSNs due to the individual coding and iteration rule for WSNs routing problem. To solve these problems, this article proposes a whale swarm algorithm with iterative counter-based routing (WSA-ICR) algorithm based on the WSA-IC algorithm. The WSA-ICR algorithm considers the energy consumption of each node and path length in the balanced network and designs a new energy efficiency objective function. Then, the WSA algorithm is improved from five aspects: individual coding, individual initialization, distance calculation between two individuals, individual movement rules, and local search. The WSA-ICR algorithm is compared with several energy efficiency optimization routing algorithms. The simulation results show that the WSA-ICR algorithm has excellent performance in balancing the energy consumption of the whole network, prolonging the network life cycle and convergence speed.

关键词： Wireless sensor networks routing Energy efficiency Metaheuristics Sensors routing protocols Quality of service Better and nearest energy-efficient metaheuristics routing algorithms whale swarm algorithm (WSA) wireless sensor networks (WSNs)

来源：评论

学校读者我要写书评

暂无评论

routing in wormhole-switched clustered networks with applications to fault tolerance

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1999年第10期10卷 1001-1011页

作者： Halwan, V Özgüner, F Dogan, A United Technol Res Ctr E Hartford CT 06108 USA Ohio State Univ Dept Elect Engn Columbus OH 43210 USA

This paper presents a novel technique for routing in wormhole-switched multiprocessor interconnection networks with clustered configuration. The network model used here consists of a set of clusters interfaced through a common central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A technique for deriving a global routing algorithm based on the local algorithms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free with two virtual channels. The clustered network model and the proposed routing technique can be used to enhance the fault tolerance capability of existing routing algorithms. In particular, we describe fault-tolerant routing methods for meshes, which can tolerate any arbitrary fault distribution without disabling connected healthy nodes.

关键词： wormhole-switching routing algorithms clustered networks scalable systems fault tolerance meshes

来源：评论

学校读者我要写书评

暂无评论

Process Variation Delay and Congestion Aware routing Algorithm for Asynchronous NoC Design

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2016年第3期24卷 909-919页

作者： Ezz-Eldin, Rabab El-Moursy, Magdy A. Hamed, Hesham F. A. Beni Suef Univ Dept Elect Engn Bani Suwayf 62511 Egypt Mentor Graph Corp Cairo 11361 Egypt Elect Res Inst Cairo Egypt Menia Univ Dept Elect Engn Al Minya 11432 Egypt

The effect of process variation (PV) on delay is a major reason to deteriorate the performance in advanced technologies. The performance of different routing algorithms is determined with/without PV for various traffic patterns. The saturation throughput and average message delay are used as performance metrics to evaluate the throughput. PV decreases the saturation throughput and increases the average message delay. PV increases the average message delay by up to 90% and decreases the saturation throughput by up to 29% compared with nominal characteristics of different routing algorithms. Adaptive routing algorithm should be manipulated with the PV. A novel PV delay and congestion aware routing (PDCR) algorithm is proposed for asynchronous network-on-chip design. PDCR is adaptive, low cost, and scalable. The novel routing algorithm outperforms different adaptive routing algorithms in the average delay and saturation throughput for various traffic patterns. PDCR can achieve up to 12%-32% average message delay lower than that of other routing algorithms. Moreover, the proposed scheme yields improvements in saturation throughput by up to 11%-82% compared with other adaptive routing algorithms.

关键词： Asynchronous design congestion network on chip (NoC) process variation (PV) routing algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint scheduling and routing algorithm with load balancing in wireless mesh network

引用

COMPUTERS & ELECTRICAL ENGINEERING 2012年第3期38卷 533-550页

作者： Ning, Zhaolong Guo, Lei Peng, Yuhuai Wang, Xiaojie Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Liaoning Peoples R China NEU SOFT Corp Shenyang 110819 Peoples R China

Wireless mesh network (WMN) is a promising solution for last mile broadband internet access. Mesh nodes or mesh routers are connected via wireless links to form a multi-hop backbone infrastructure and improving throughput is the primary goal. While previous works mainly focused on either link level protocol design or complex mathematical model, in this paper, we investigate the performance gains from jointly optimizing scheduling and routing in a multi-radio, multi-channel and multi-hop wireless mesh network. Then, two optimization objectives are addressed by considering wireless media contention and spatial multiplexing. The first objective is to maximize throughput by exploiting spatial reuse while the second one is to ensure fairness among different links. We design a cross-layer algorithm by considering both MAC layer and network layer. Simulation results show that our joint optimization algorithm can significantly increase throughput as well as fairness. (c) 2011 Elsevier Ltd. All rights reserved.

关键词： MAC layer Wireless mesh networks Load balancing Optimization algorithms wireless Throughput routing algorithms Spread spectrum communication

来源：评论

学校读者我要写书评

暂无评论

Scalable Deadlock-Free Deterministic Minimal-Path routing Engine for InfiniBand-Based Dragonfly Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2018年第1期29卷 183-197页

作者： Maglione-Mathey, German Yebenes, Pedro Escudero-Sahuquillo, Jesus Javier Garcia, Pedro Quiles, Francisco J. Zahavi, Eitan Univ Castilla La Mancha Comp Syst Dept Campus UnivAlbacete S-N Ciudad Real 02071 Spain Mellanox Technol IL-20692 Yokneam Israel

Dragonfly topologies are gathering great interest nowadays as one of the most promising interconnect options for High-Performance Computing (HPC) systems. However, Dragonflies contain physical cycles that may lead to traffic deadlocks unless the routing algorithm prevents them properly. In general, existing deadlock-free routing algorithms, either deterministic or adaptive, proposed for Dragonflies, use Virtual Channels (VCs) to prevent cyclic dependencies. However, these topology-aware algorithms are difficult to implement, or even unfeasible, in systems based on the InfiniBand (IB) architecture, which is nowadays the most widely used network technology in HPC systems. This is due to some limitations in the IB specification, specifically regarding the way Virtual Lanes (VLs), which are considered as similar to VCs, can be assigned to traffic flows. Indeed, none of the routing engines currently available in the official releases of the IB control software has been specifically proposed for Dragonflies. In this paper, we present a new deterministic, minimal-path routing for Dragonfly that prevents deadlocks using VLs according to the IB specification, so that it can be straightforwardly implemented in IB-based networks. We have called this proposal D3R (Deterministic Deadlock-free Dragonfly routing). Specifically, D3R maps each route to a single, specific VL depending on the destination group, and according to a specific order, so that cyclic dependencies (so deadlocks) are prevented. D3R is scalable as it requires only 2 VLs to prevent deadlocks regardless of network size, i.e., fewer VLs than the required by the deadlock-free routing engines available in IB that are suitable for Dragonflies. Alternatively, D3R achieves higher throughput if an additional VL is used to reduce internal contention in the Dragonfly groups. We have implemented D3R as a new routing engine in OpenSM, the control software including the subnet manager in IB. We have evaluated D3R by means of

关键词： High-performance interconnection networks InfiniBand Dragonfly topology routing algorithms deadlock-freedom

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：