JOURNAL OF COMPUTERS (JCP)

ISSN : 1796-203X

Volume : 4 Issue : 3 Date : March 2009

**Topology and Routing Algorithm Based on the Combination Gray Code with Johnson Code**

Xiaoqiang Yang, Huimin Du, and Jungang Han

Page(s): 259-264

Full Text: PDF (141 KB)

**Abstract**

Hypercubes utilizing Gray Code are used widely as the interconnection networks of parallel

computer systems. But an n-dimensional hypercube has 2n nodes, when the size of a network have

been increases added nodes must be 2i times more than its nodes and increase the degree of

nodes , which affects scalable characteristic. The paper puts forward a scalable hypercube based

on the Combination Gray Code with Johnson Code(GJCode(s, t)). The GJCode(s, t) has flexible

scalable characteristics and the important properties of both Gray Code and Johnson Code which

is there exists a link between two nodes only if their binary addresses differ in a single bit. In the

GJCode(s, t), there are two adjustable parameters which offer a good tradeoff between the cost of

networks and their performance in terms of the demand of application systems. The paper

discusses the performance of several variations of the hypercube and proposes the routing

algorithm for the GJCode(s, t), which can make packets pass along the shortest distance path and

is very simple and easy to be implemented in hardware with low implementation cost. The

GJCode(s, t) can be applied in parallel computer systems and networks on chip.

**Index Terms**

Network Topology, Routing Algorithm, Node Encoding, Hypercube, parallel architecture, Network on

Chip

ISSN : 1796-203X

Volume : 4 Issue : 3 Date : March 2009

Page(s): 259-264

Full Text: PDF (141 KB)

computer systems. But an n-dimensional hypercube has 2n nodes, when the size of a network have

been increases added nodes must be 2i times more than its nodes and increase the degree of

nodes , which affects scalable characteristic. The paper puts forward a scalable hypercube based

on the Combination Gray Code with Johnson Code(GJCode(s, t)). The GJCode(s, t) has flexible

scalable characteristics and the important properties of both Gray Code and Johnson Code which

is there exists a link between two nodes only if their binary addresses differ in a single bit. In the

GJCode(s, t), there are two adjustable parameters which offer a good tradeoff between the cost of

networks and their performance in terms of the demand of application systems. The paper

discusses the performance of several variations of the hypercube and proposes the routing

algorithm for the GJCode(s, t), which can make packets pass along the shortest distance path and

is very simple and easy to be implemented in hardware with low implementation cost. The

GJCode(s, t) can be applied in parallel computer systems and networks on chip.

Chip