Efficient embeddings of meshes and hypercubes on a group of future network architectures.

Abstract

Meshes and hypercubes are two most important communication and computation structures used in parallel computing. Network embedding problems for meshes and hypercubes on traditional network architectures have been intensively studied during the past years. With the emergence of new network architectures, the traditional network embedding results are not enough to solve the new requirements. The main objective of this thesis is to design efficient network embedding schemes for realizing meshes and hypercubes on a group of future network architectures. This thesis is organized into two parts. The first part focuses on embedding meshes/tori on a group of double-loop networks by evaluating the traditional embedding metrics, since double-loop networks have been intensively studied and proven to have many desirable properties for future network architecture. We propose a novel tessellation approach to partition the geometric plane of double-loop networks into a set of parallelogram tiles, called P-shape. Based on the characteristics of P-shape, we design a simple embedding scheme, namely P-shape embedding, that embeds arbitrary-shape meshes and tori on double-loop networks in a systematic way. A main merit of P-shape embedding is that a large fraction of embedded mesh/torus edges have edge dilation 1, resulting in a low average dilation. These are the first results, to our knowledge, on embedding meshes and tori on general doubleloop networks which is of great significance due to the popularity of these architectures. Our P-shape construction bridges between regular graphs and double-loop networks, and provides a powerful tool for studying the topological properties of double-loop networks. In the second part, we study efficient embedding schemes for realizing hypercubes on a group of array-basedWDMoptical networks by analyzing the new embedding metric of wavelength requirement, as WDM optical networking is becoming a promising technology for deployment in many applications in advanced telecommunication and parallel computing. We first design routing and wavelength assignments of both bidirectional and unidirectional hypercubes on WDM optical linear arrays, rings, meshes and tori with the consideration of communication directions. For each case, we identify a lower bound on the number of wavelengths required, and design the embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. To further reduce the wavelength requirement, we extend the results to WDM ring networks with additional links, namely WDM chordal rings. Based on our proposed embedding schemes, we provide the analysis of chord length with optimal number of wavelengths to realize hypercubes on 3-degree and 4-degree WDM chordal rings. Furthermore, we propose an embedding scheme for realizing dimensional hypercubes on WDM optical arrays by considering the hypercubes dimension by dimension, called lattice embedding, instead of embedding hypercubes with all dimensions. Based on lattice embedding, the number of wavelengths required to realize dimensional hypercube on WDM arrays can been significantly reduced compared to the previous results. By our embedding schemes, many communications and computations, originally designed based on hypercubes, can be directly implemented in WDM optical networks, and the wavelength requirements can be easily derived using our obtained results.