Research On Properties Of2D-Mesh And Its Variants

The significant parameters for evaluating a topology are symmetry, diameter, degree, bisection width, routing algorithm, hamiltonian properties, metric dimension, broadcasting, etc.2D-Mesh is a most widely used topology in Network-on-Chip. It is simple and easy to be implemented. Honeycomb mesh and HDN network are two important variants of2D-Mesh. In this paper, we study some properties of2D-Mesh, Honeycomb mesh, and HDN network. Precisely speaking, we study the fault tolerant routing algorithm of2D-Mesh, the Hamiltonian properties of Honeycomb mesh, and the metric dimension of HDN network.(1) Routing algorithm determines the path selected by a packet to reach its destination. A fault-tolerant routing algorithm for2D-Mesh that uses only two virtual channels is pre-sented, while previously, Boppana et al. needs4virtual channels and Duan et al. needs3virtual channels. Our algorithm is based on the block fault model. The fault region can be f-ring and f-chain at the same time. Shortest paths are used for routing if there are no faults, while detour paths are used for blocked messages. We have proved that our algorithm is deadlock-free under both the non-overlapping and overlapping situations.(2) A Hamiltonian path (cycle) is a path (cycle) contains every vertex exactly once in G. There is, so far, no work reported about the Hamiltonian properties of Honeycomb mesh. In this paper, we address the Hamiltonian properties of Honeycomb mesh (HM). Our major contributions are as follows:(a) we give a necessary and sufficient condition for any two vertices such that there is a Hamiltonian path between them in HM;(b) we study the Hamiltonian properties with one faulty vertex in HM;(c) the proof in our paper is constructive, thus if the Hamiltonian path exists, we can build it according to our proof.(3) Let W (?) V(G). Suppose that for any pair of vertices u, v∈V(G), there is another vertex w such that d(u, w)≠d(v, w). Then, we call W is a locating set of G. If the cardinality of W less than all other locating sets, then W is the metric basis of G and its cardinality is called the metric dimension of G. The concept of metric dimension is widely used in network discovery and verification, strategies for the Mastermind game, image processing, and etc. We have solved the open problem proposed by Manuel et al. that the metric dimension of HDN1(n) and HDN2(n) are between3and5. Moreover, we give a more tight bound that the metric dimension of HDN1(n) and HDN2(n) are between3and4.