Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Non lock routing method for k-element N-dimension mesh

A deadlock-free and routing technology, applied to electrical components, data exchange networks, digital transmission systems, etc., can solve problems such as not being utilized

Inactive Publication Date: 2008-08-13
TSINGHUA UNIV
View PDF0 Cites 15 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, it can be found that the c in the z direction 1 and c 2 channel, c in the x direction 3 channel, has not been utilized

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Non lock routing method for k-element N-dimension mesh
  • Non lock routing method for k-element N-dimension mesh
  • Non lock routing method for k-element N-dimension mesh

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0098] The routing method in the x-y plane ascending subnet is given below. In this method, if the offset between the current point and the target point in the x direction is not zero and the corresponding c 1 If the channel is available, then the x direction is preferred for routing; if the channel in the x direction is not available, and the offset in the y direction is greater than zero, choose c in the y direction 1 + channel for routing. The routing method of the x-y descending subnet is basically the same as that of the ascending subnet, the only difference is that it uses c in the x direction 2 channel instead of c 1 aisle.

[0099] Method Deadlock-free-adaptive-routing-xy+():

[0100] The input is the current point curr, the target point dest, x off =x d -x c ,y off =y d -y c ;if x off >0 and y off >0, then Channel:=Select(x(c 1 +), y(c 1 +)); if x off off >0, then Channel:=Select(x(c 1 -), y(c 1 +)). if x off = 0 and y off >0, then Channel:=y(c 1 ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a deadlock-free routing method in K-ary N-dimension mesh network, belonging to the field of distributed high performance fault tolerant computing technology. Each physical channel between nodes is divided into two virtual channels which are two-way channels and distributed to rising subnet and falling subnet of each plane in N-dimension mesh network. The method avoids deadlock which may be formed between arbitrary adjacent planes by overlapping technology, and reaches highest adaptability by the highest dimension idle channel; the smallest connecting component created by planes on the basis further improves fault-tolerance performance. Compared with traditional PAR method and Gomez method, as standard input load and network fault node number increased, the invention can obviously improve network actual flow and reduce transmission delay, thus improving the transmission performance of the whole network.

Description

technical field [0001] A deadlock-free routing method in a k-element N-dimensional mesh network belongs to the technical field of distributed high-performance fault-tolerant computing. Background technique [0002] In today's experimental and commercial multi-computer systems, mesh network is a widely used topology. The k-element n-dimensional mesh network refers to an n-dimensional grid structure with k nodes in each dimension. The performance of a multicomputer system depends to the greatest extent on the performance of the point-to-point communication methods in the system. Therefore, it is necessary to propose some high-performance fault-tolerant routing methods applied to mesh networks. [0003] The turn model proposed by Glass and Ni is an important part adaptive routing method. Based on the turn model, the routing method can eliminate the ring correlation between channels by restricting some turns, so as to avoid deadlock without adding additional virtual channels....

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): H04L12/56H04L45/18
Inventor 向东张跃鲤
Owner TSINGHUA UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products