随着集成电路技术的飞速发展,片上系统体系结构的复杂性不断增加,成千上万的核集成在一个芯片中。因此,带宽、可扩展性、端到端延迟和吞吐量的设计都面临着瓶颈。片上系统内核间的互连结构(即互连网络)已成为高性能多核处理器设计中必须考虑的关键问题。片上网络作为一种新的互连方式,克服了传统总线在芯片设计中的局限性。片上网络借鉴了传统并行处理机中的互连网络结构,其中网格和环绕是片上网络最流行的两种结构。在片上网络的设计与分析中,其布线与布局结构极大地影响着系统性能。片上处理器受到空间、成本和功耗的限制,内部以二维芯片布局为主,因此,高维互连网络的通信方式需要通过二维布局与布线来实现。超立方体是常用的互连网络之一,具有正则性、对称性、高连通性等优点,但也存在直径较大的问题。交换超立方体与3-元n-立方体分别是超立方体的重要变型,它们不仅保留了超立方体的优良性质,而且增加了一些新的特性。片上网络的布线与布局问题可以模拟为图嵌入问题。本文重点研究了交换超方体和3-元n-立方体在两类常用的芯片结构——网格与环绕中的嵌入,主要研究内容如下:1.首先给出了交换超立方体的一个最佳集与一个最大导出子图。然后给出了交换超立方体到网格中的嵌入,证明了该嵌入具有最小的连线长度。最后给出了交换超立方体到网格中的共线布局,证明了该布局具有最小轨道数以及最小的布线区域,给出了所提布局算法的网络开销与线长模拟实验。2.首先给出了交换超立方体到环网中的嵌入,证明了该嵌入具有最小的边拥塞度及循环连线长度。然后给出了交换超立方体到环绕中的嵌入,证明了该嵌入具有最小的循环连线长度。3.首先研究了3-元n-立方体的最佳集与边等周问题。其次给出了3-元n-立方体到网格中的嵌入,证明了该嵌入具有最小的带宽以及连线长度。然后给出了 3-元n-立方体在四方网格中的布局,证明了实现该布局具有最小的延展率、拥塞度,以及最小轨道数。最后给出了一种考虑通信量的通信平衡布局算法,分析了该算法的时间复杂度,并给出了布局算法的模拟实验。4.首先给出了3-元n-立方体到环绕中的嵌入,并证明了该嵌入具有最小的边拥塞度、循环连线长度以及最小的布局面积。其次在3-元n-立方体中的顶点或者边出现故障的条件下,给出了3-元n-立方体到环绕中的容错布局算法,以及相应的模拟实验。综上所述,本文研究了交换超立方体与3-元n-立方体分别在网格与环绕中的嵌入,由此可以估计在二维芯片上实现交换超立方体及3-元n-立方体所需的芯片面积。本文研究成果对于它们在芯片设计中的布线与布局提供了理论依据。