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)

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