交换超立方体和3-元n-立方体在网格与环绕中的嵌入
发布时间：2021-07-05 14:53
随着集成电路技术的飞速发展,片上系统体系结构的复杂性不断增加,成千上万的核集成在一个芯片中。因此,带宽、可扩展性、端到端延迟和吞吐量的设计都面临着瓶颈。片上系统内核间的互连结构（即互连网络）已成为高性能多核处理器设计中必须考虑的关键问题。片上网络作为一种新的互连方式,克服了传统总线在芯片设计中的局限性。片上网络借鉴了传统并行处理机中的互连网络结构,其中网格和环绕是片上网络最流行的两种结构。在片上网络的设计与分析中,其布线与布局结构极大地影响着系统性能。片上处理器受到空间、成本和功耗的限制,内部以二维芯片布局为主,因此,高维互连网络的通信方式需要通过二维布局与布线来实现。超立方体是常用的互连网络之一,具有正则性、对称性、高连通性等优点,但也存在直径较大的问题。交换超立方体与3-元n-立方体分别是超立方体的重要变型,它们不仅保留了超立方体的优良性质,而且增加了一些新的特性。片上网络的布线与布局问题可以模拟为图嵌入问题。本文重点研究了交换超方体和3-元n-立方体在两类常用的芯片结构——网格与环绕中的嵌入,主要研究内容如下:1.首先给出了交换超立方体的一个最佳集与一个最大导出子图。然后给出了交...
【文章来源】：苏州大学江苏省
【文章页数】：115 页
【学位级别】：博士
【部分图文】：
图１－１?ＮｏＣ体系结构??２??
交换超立方体和３－元心立方体在网格与环绕中的嵌入?第二章相关知识??点上，可以得到嵌入的延展率为２，拥塞度为４，膨胀率和负载均为１。在图２－ｌ（ｂ）中，??将３－超立方体的顶点都映射到顶点数为８的环形网络中，可以得到嵌入的延展率为３，??拥塞度为３，膨胀率和负载均为１。??１?２?３??？?ｆ?ｆ??（ｂ?ＨＩ?＾＾￣￣＾＾＾?？？参??１?２３?４５６７８９??７?８?９??？?４?４??（４网格到线性阵列中的嵌入??——／??（ｂ）?３－维超立方体到环网中的嵌入??图２－丨网格和超立方体到线性阵列和环网中的嵌入??将互连网络嵌入到线性阵列（或者环网）也叫作线性布局（循环线性布局）或??者线性布置（循环线性布置）ｍｗｉ。线性布局是图Ｇ到／／之间一个单射函数釦该函??数０：１／—丨１，２，．．．，《丨将图６中的每个顶点分配不同的整数（从１到《），使得图〇中的??每个顶点和每条边与图／／形成一个特定的对应关系，其中／／表示一条水平的线性阵??列，其顶点按照其对应关系进行标号为１，２，．．．，《（如图２－１（３））。循环布局是存在一个??函数广：＼／４｛１，２，．．．，《｝，同样是对具有《个顶点的图分配不同的整数（从１到《），而??是将图的顶点布局到一个圈中，其中最后一个顶点（标号为ｎ的顶点）与第一个顶点??（标号为１的顶点）相邻（如图２－ｌ（ｂ））。这两种情形下，负载度均为１。关于布局的优??化问题，主要有以下几个优化目标。??割宽最小化问题（Ｃｕｔｗｉｄｔｈ?Ｍｉｎｉｍｉｚａｔｉｏｎ?Ｐｒｏｂｌｅｍ，?ＣＭＰ）是一个ＮＰ－难的最小??极大线性布局问题［９４］。它是在线性阵列上
１０?１１０１０??／?１￣￣Ｊｘ＇?ｊｌ￣￣ｉ?＼??＼?／?／?ｏｏｑｏｏ?ｏｉｏｏｏ卜、一ｏｏｏｉｏ?ｏｉｂｉｏ?．??＼?ｏｑ＾ｐｏ?ｏｏｏｏｉ?０乂ｏｏｏ；?赢?／、邊一＇??〇〇ｉｊｒ?卜Ｈ?ｗ。＂?＇丨??ｕｏ〇（ｉ／?ｊ１００１?＂ｊ＇Ａ?＼?１?〇〇ｉ＾ｆ〇〇＂／＼＂〇（Ｓｒ＾ｎ〇?！??＾?＇Ｑ＾??ｕｖｒｏｏ＂?ｉｎ?）ｉ?ｍ丨丨一?Ｉ＇ｏｒｒｏ?ｉｏｏｏｉ?１００１１?ｎ〇〇ｉ?ｎｏｎ??ＥＨ（＼，３）?ＥＨ?（２，２）??图２－３?￡州．，与￡／／２．２，其中虚线表示＆边集，实线表示￡：边集，黑线表示￡，边集??总之，￡／／、．，中的顶点数目与込＋，＋?１中顶点数目相同，而边的数目大约为２ｗ＋ｉ的??一羊。维边，或者叫，的（Ｓ?＋?／＋１）－边，是指ｗ与ｖ仅在第ｄ位不相同。这种??情况下，｝叫做ｘ的心邻居，表示为ｖ?＝?ｙＶｒｆ（ｘ）。令表示￡／／ｗ的所有维边，那??么，￡（￡／／，．，）?＝?构，可以更准确的表示为旧⑷仏．，）丨＝（．ｓ’?＋?＾?＋?２）２Ｈ?＝??（卜丄輕册丨）丨＿。??交换超立方体的几个性质如下：??（１）?￡／／、．，同构于￡／／，／９１。??（２）?—个￡７７、．，能够被分成两个或者两个一个￡／／、，也能够被分解??成Ｙ个不相交的ｇｊｌ２ｓ个不相交的（２／１９１。??（３）?￡／／，，，的连通度／＜（五／／，，，）?＝?Ｓ＋?１，其中１?幺?ｊ?幺?ｆ＿〇??交换超立方体比超立方体具有更低的链路复杂度，它可以直接影响系统的硬件??成本和ＶＬＳＩ实现１ｍ１。??２．２．２?３？元立方体及其基本性质??３－元立方体定义如下：??
【参考文献】：
期刊论文
[1]异构三维片上网络布局优化的超图划分算法[J]. 宋国治,张大坤,马杰超,涂遥,刘畅. 计算机科学与探索. 2016(06)
[2]一种考虑拥挤度的布线模型及其算法[J]. 陈秀华. 福州大学学报(自然科学版). 2015(01)
[3]一个同时考虑时延约束和拥挤度优化的总体布线新方法[J]. 吕丽华,马琪,谢满得. 微电子学与计算机. 2006(04)
博士论文
[1]交换交叉立方体上若干性质的研究[D]. 周东仿.苏州大学 2017
[2]若干互连网络的圈嵌入和路嵌入[D]. 程冬琴.北京交通大学 2015
[3]基于智能算法的片上网络布局优化研究[D]. 乐千桤.电子科技大学 2014
[4]并行计算机故障诊断及WDM网络路由与波长分配问题研究[D]. 余翠.重庆大学 2014
[5]k-元n-立方体的路和圈[D]. 李晶.山西大学 2011
[6]几类规则互连网络的嵌入与容错嵌入研究[D]. 董强.重庆大学 2010
本文编号：3266283
【文章来源】：苏州大学江苏省
【文章页数】：115 页
【学位级别】：博士
【部分图文】：
图１－１?ＮｏＣ体系结构??２??
交换超立方体和３－元心立方体在网格与环绕中的嵌入?第二章相关知识??点上，可以得到嵌入的延展率为２，拥塞度为４，膨胀率和负载均为１。在图２－ｌ（ｂ）中，??将３－超立方体的顶点都映射到顶点数为８的环形网络中，可以得到嵌入的延展率为３，??拥塞度为３，膨胀率和负载均为１。??１?２?３??？?ｆ?ｆ??（ｂ?ＨＩ?＾＾￣￣＾＾＾?？？参??１?２３?４５６７８９??７?８?９??？?４?４??（４网格到线性阵列中的嵌入??——／??（ｂ）?３－维超立方体到环网中的嵌入??图２－丨网格和超立方体到线性阵列和环网中的嵌入??将互连网络嵌入到线性阵列（或者环网）也叫作线性布局（循环线性布局）或??者线性布置（循环线性布置）ｍｗｉ。线性布局是图Ｇ到／／之间一个单射函数釦该函??数０：１／—丨１，２，．．．，《丨将图６中的每个顶点分配不同的整数（从１到《），使得图〇中的??每个顶点和每条边与图／／形成一个特定的对应关系，其中／／表示一条水平的线性阵??列，其顶点按照其对应关系进行标号为１，２，．．．，《（如图２－１（３））。循环布局是存在一个??函数广：＼／４｛１，２，．．．，《｝，同样是对具有《个顶点的图分配不同的整数（从１到《），而??是将图的顶点布局到一个圈中，其中最后一个顶点（标号为ｎ的顶点）与第一个顶点??（标号为１的顶点）相邻（如图２－ｌ（ｂ））。这两种情形下，负载度均为１。关于布局的优??化问题，主要有以下几个优化目标。??割宽最小化问题（Ｃｕｔｗｉｄｔｈ?Ｍｉｎｉｍｉｚａｔｉｏｎ?Ｐｒｏｂｌｅｍ，?ＣＭＰ）是一个ＮＰ－难的最小??极大线性布局问题［９４］。它是在线性阵列上
１０?１１０１０??／?１￣￣Ｊｘ＇?ｊｌ￣￣ｉ?＼??＼?／?／?ｏｏｑｏｏ?ｏｉｏｏｏ卜、一ｏｏｏｉｏ?ｏｉｂｉｏ?．??＼?ｏｑ＾ｐｏ?ｏｏｏｏｉ?０乂ｏｏｏ；?赢?／、邊一＇??〇〇ｉｊｒ?卜Ｈ?ｗ。＂?＇丨??ｕｏ〇（ｉ／?ｊ１００１?＂ｊ＇Ａ?＼?１?〇〇ｉ＾ｆ〇〇＂／＼＂〇（Ｓｒ＾ｎ〇?！??＾?＇Ｑ＾??ｕｖｒｏｏ＂?ｉｎ?）ｉ?ｍ丨丨一?Ｉ＇ｏｒｒｏ?ｉｏｏｏｉ?１００１１?ｎ〇〇ｉ?ｎｏｎ??ＥＨ（＼，３）?ＥＨ?（２，２）??图２－３?￡州．，与￡／／２．２，其中虚线表示＆边集，实线表示￡：边集，黑线表示￡，边集??总之，￡／／、．，中的顶点数目与込＋，＋?１中顶点数目相同，而边的数目大约为２ｗ＋ｉ的??一羊。维边，或者叫，的（Ｓ?＋?／＋１）－边，是指ｗ与ｖ仅在第ｄ位不相同。这种??情况下，｝叫做ｘ的心邻居，表示为ｖ?＝?ｙＶｒｆ（ｘ）。令表示￡／／ｗ的所有维边，那??么，￡（￡／／，．，）?＝?构，可以更准确的表示为旧⑷仏．，）丨＝（．ｓ’?＋?＾?＋?２）２Ｈ?＝??（卜丄輕册丨）丨＿。??交换超立方体的几个性质如下：??（１）?￡／／、．，同构于￡／／，／９１。??（２）?—个￡７７、．，能够被分成两个或者两个一个￡／／、，也能够被分解??成Ｙ个不相交的ｇｊｌ２ｓ个不相交的（２／１９１。??（３）?￡／／，，，的连通度／＜（五／／，，，）?＝?Ｓ＋?１，其中１?幺?ｊ?幺?ｆ＿〇??交换超立方体比超立方体具有更低的链路复杂度，它可以直接影响系统的硬件??成本和ＶＬＳＩ实现１ｍ１。??２．２．２?３？元立方体及其基本性质??３－元立方体定义如下：??
【参考文献】：
期刊论文
[1]异构三维片上网络布局优化的超图划分算法[J]. 宋国治,张大坤,马杰超,涂遥,刘畅. 计算机科学与探索. 2016(06)
[2]一种考虑拥挤度的布线模型及其算法[J]. 陈秀华. 福州大学学报(自然科学版). 2015(01)
[3]一个同时考虑时延约束和拥挤度优化的总体布线新方法[J]. 吕丽华,马琪,谢满得. 微电子学与计算机. 2006(04)
博士论文
[1]交换交叉立方体上若干性质的研究[D]. 周东仿.苏州大学 2017
[2]若干互连网络的圈嵌入和路嵌入[D]. 程冬琴.北京交通大学 2015
[3]基于智能算法的片上网络布局优化研究[D]. 乐千桤.电子科技大学 2014
[4]并行计算机故障诊断及WDM网络路由与波长分配问题研究[D]. 余翠.重庆大学 2014
[5]k-元n-立方体的路和圈[D]. 李晶.山西大学 2011
[6]几类规则互连网络的嵌入与容错嵌入研究[D]. 董强.重庆大学 2010
本文编号：3266283
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/3266283.html
