Embedding Of Exchanged Hypercubes And 3-Ary N-Cubes Into Grids And Tori

With the rapid development of integrated circuit techniques,the complexity of mod-ern System-on-Chip architecture increases steadily.Thousands of cores are integrated in one single chip.The interconnection architecture(interconnection network)between cores in System-on-Chip has become a critical problem that must be taken into account in high performance many-core processor design.Network-on-Chip has been proposed as a novel interconnection approach to overcome the limitation of traditional buses for chip design.Network-on-Chip draws on the interconnection network structure of traditional parallel processors.Grids and tori are the two most popular structures on chips.In the design and analysis of Network-on-Chip,its wiring and layout structure greatly affect the system per-formance.On-chip processors are constrained by space,cost and power consumption,and are mainly based on two-dimensional chip layout.Therefore,the communication mode of high-dimensional interconnection networks need to be realized by two-dimensional wiring and layout.Hypercube is one of the commonly used interconnection networks.It has the advan-tages of regularity,symmetry and high connectivity,but it also has the problem of larger diameter.Exchanged hypercube and 3-ary n-cube are important variants of hypercube,re-spectively.They not only retain the desirable properties of hypercubes,but also add some new features.The problem of wiring and layout of network-on-chip can be simulated by graph em-bedding.This thesis focuses on the embedding of exchanged hypercubes and 3-ary n-cubes into two kinds of popular structures-grids and tori.The main research contents are as fol-lows:1.Firstly,we gave an optimal set and an maximum induced subgraph of the exchanged hypercube.Secondly,we gave embeddings of exchanged hypercubes into grids,and proved that the embeddings have minimum bandwidth and wirelength.Thirdly,we gave a collinear layout of exchanged hypercubes into grids,and proved that the layout has minimum number of tracks and minimum area.2.Firstly,we gave embeddings of exchanged hypercubes into ring networks,and proved that the embeddings have minimum edge congestion and circular wirelength.Sec-ondly,we gave embeddings of exchanged hypercubes into tori,and proved that the embed-dings have minimum circular wirelength.3.Firstly,we studied the optimal set and the edge isoperimetric problem of 3-ary n-cube.Secondly,we gave embeddings of 3-ary n-cubes into grids,and prove that the embedding has minimum bandwidth and wirelength.Thirdly,we gave a layout of 3-ary n-cube into the square grid,and prove that the layout has minimum dilation,congestion and minimum number of tracks.Finally,we gave a communication balanced embedding algorithm with considering communication volume,and analysis its time complexity.4.Firstly,we gave embeddings of 3-ary n-cubes into tori,and prove that the embed-dings have the minimum edge congestion,circular wirelength and the minimum layout area.In the case of edges or nodes failure of 3-ary n-cubes,we gave a fault-tolerant embedding of 3-ary n-cubes into 2-dimensional tori,and proved that the embedding has the smallest circular wirelength.In summary,we study the embedding of exchanged hypercubes and 3-ary n-cubes into grids and tori,respectively.It can be used to estimate the chip area required for layout exchanged hypercubes and 3-ary n-cubes onto two-dimensional chips.The research results of this thesis provide a theoretical basis for their wiring and layout in chip design.