（计算机应用技术专业论文）容错处理器阵列的高效重构技术.pdf

学位论文的主要创新点 一在前人研究的基础上，对最新研究的的重构算法给予了改进， 并提出新算法。新算法在最好的情况下只需要进行1 次赋值操作，在 最坏情况下只需进行1 次加法和1 次比较操作，比原算法了有了较大 的改进和提高。实验结果表明，原算法的运行时间改进了2 8 。 二提出了温控子阵列的构造算法。构造了最大的温控子阵列， 对这个最大温控子阵列进行优化，并提出了温控子阵列的温度的下 界，以此来衡量算法的优劣。实验分别对故障单元随机分布和聚集分 布的情况进行讨论。软件模拟结果显示，在故障单元随机分布的情况 下，当故障率很大时，优化后的温控子阵列的平均温度逐渐接近其下 界，因而说明，温控子阵列的优化算法具有渐近最优性。在故障单元 聚集分布时，温控子阵列的优化算法也能达到类似的效果。 摘要 随着超大规模集成电路( v l s i ) 设计技术和集成工艺的不断发展，芯片上 的处理单元的集成度越来越高。这些被集成的处理单元以网状连接形式形成阵 列。对于数量众多的处理单元来说，如果芯片使用时间过长，或者外界环境比较 恶劣，那么，芯片中就可能出现故障单元。因此，v l s i 阵列的容错技术就显得 尤为重要。 v l s i 阵列的容错技术主要包括两种：冗余方法和可降阶的方法。其中，可 降阶的方法是当出现故障单元时，使用现有的无故障单元重新构造一个满足特定 条件的子阵列的方法，用这种方法构造的子阵列是一个只包含无故障单元的子阵 列，这种子阵列被称为目标阵列( 或者逻辑阵列) 。因此，这种方法的目标就是 在某些限制条件下( 例如开关机制等) ，在一个含有故障单元的主阵列上重新构 造一个无故障的目标阵列。 在加速高性能子阵列的构造算法中，对现有的重构算法予以改进。新算法在 最好的情况下只需要进行1 次赋值操作，在最坏情况下只需进行1 次加法和1 次 比较操作，而原算法则需5 次操作( 1 次赋值，2 次加法和2 次比较) 。实验结果 表明，与原算法相比，运行时间缩短了2 8 ，并且重构后的子阵列的内部连接长 度的误差被控制在可以接受的范围内。 在构造温控子阵列部分，提出了构造温控子阵列的方法。构造了最大的温控 子阵列，对这个最大温控子阵列进行优化，并提出了温控子阵列的温度的下界， 以此来衡量算法的优劣。实验分别对故障单元随机分布和聚集分布的情况进行讨 论。软件模拟结果显示，在故障单元随机分布的情况下，当故障率很大时，优化 后的温控子阵列的平均温度逐渐接近其下界，因而说明，温控子阵列的优化算法 具有渐近最优性。在故障单元聚集分布时，温控子阵列的优化算法也能达到类似 的效果。 关键字：超大规模集成电路( v l s i ) ；重构算法；容错技术；高性能子阵列； 温控子阵列； a b s t r a c t a d v a n c ei nv l s ia n dw s it e c h n o l o g i e sa l l o wi n c r e a s i n g l yl a r g e rp r o c e s s o r a r r a y st ob ef a b r i c a t e do nas i n g l ec h i p o rw a f e r t h e s ep r o c e s s i n ge l e m e n t sa r e m e s h c o n n e c t e d i ft h ec h i pi su s e df o ral o n gt i m eo rt h ee n v i r o n m e n ti ss e v e r e ，t h e n t h en u m b e ro ft h ef a u l t yp r o c e s s i n ge l e m e n t sw i l la r i s e t h u s ，t h ef a u l t - t o l e r a n t t e c h n i q u e so fv l s ia r r a y sb e c o m ei n c r e a s i n g l yi m p o r t a n t g e n e r a l l y , t w om e t h o d sf o rr e c o n f i g u r a t i o n ，n a m e l y , r e d u n d a n c ya p p r o a c ha n d d e g r a d a t i o na p p r o a c h ，a r ee m p l o y e di nf a u l t t o l e r a n tt e c h n i q u e s i nt h ed e g r a d a t i o n a p p r o a c ho fp r o v i d i n gf a u l tt o l e r a n c ei np r o c e s s o ra r r a y si st ou s e a sm u c hf a u l t - f r e e c i r c u i t sa sp o s s i b l et oc o n s t r u c tat a r g e tf a u l t - f r e ea r r a yu n d e rc e r t a i nl i m i t a t i o n s ，s u c h a ss w i t c h i n gc a p a b i l i t i e sa n dm i n i m u md i m e n s i o n so ft h et a r g e ta r r a y i nt h i s a p p r o a c h af a u l t f r e es u b - a r r a y c a i lb ec a l l e dt a r g e ta r r a yo rl o g i c a la r r a y 1 n h u s ，g i v e n ad e f e c t i v ea r r a y , t h eg o a li st od r i v eaf a u l t - f r e et a r g e ta r r a yu n d e rc e r t a i nl i m i t a t i o n s af a s tr e c o n f i g u r a t i o na l g o r i t h mi sp r o p o s e dt os i m p l i r yad y n a m i cp r o g r a m m i n g a p p r o a c ht oc o n s t r u c tl o g i c a lc o l u m n si nt h i st h e s i s f o re a c hp r o c e s s i n g e l e m e n t l y i n gi nt h el o g i c a lc o l u m n s ，t h ec a l c u l a t i o n i sr e d u c e df r o mf i v eo p e r a t i o n s ( o n e a s s i g n m e n t , t w oa d d i t i o n sa n dt w oc o m p a r i s o n s ) t h a ta r et a k e ni nt h es t a t e - o f - t h e a r t t os i n g l ea s s i g n m e n to p e r a t i o ni nm o s tc a s e s ，o rt h r e eo p e r a t i o n s ( o n ea s s i g n m e n t , o n e c o m p a r i s o na n do n ea d d i t i o n ) i nw o r s tc a s e s i m u l a t i o n r e s u l t sb a s e do ns a m e b e n c h m a r k su t i l i z e di nt h es t a t e o f - t h e a r ts h o wt h a t ，t h es i m p l i f i e da l g o r i t h mr u n s f a s t e rb y2 8 w i t h o u tl o s so fh a r v e s t m o r e o v e r , t h ei n c r e a s e o ft h et o t a l i n t e r c o n n e c t i o nl e n g t ho ft h et a r g e ta r r a yi sa c c e p t a b l e am e t h o df o rt e m p e r a t u r e a w a r es u b a r r a yr e c o n f i g u r a t i o ni sp r o p o s e di n t h i s t h e s i s am a x i m u mt e m p e r a t u r e - a w a r es u b a r r a yi sc o n s t r u c t e da n do p t i m i z e d ，a n dt h e t e m p e r a t u r el o w e rb o u n do ft h i ss u b - a r r a yi sp r o p o s e d 1 1 1 el o w e rb o u n di su s e dt o m e a s u r et h ep e r f o r m a n c eo fa l g o r i t h m m e a n w h i l e ，r a n d o md i s t r i b u t i o na n dc l u s t e r d i s t r i b u t i o nf o rt h ef a u l t ye l e m e n t sa r ea l s oc o n s i d e r e di na l g o r i t h ms i m u l a t i o n s s i m u l a t i o nr e s u l t ss h o wt h a t ，t h ea v e r a g et e m p e r a t u r e o ft h er e s u l t a n t t e m p e r a t u r e a w a r es u b - a r r a ya p p r o a c h e si t s l o w e rb o u n df o rt h ec a s e so fr a n d o m d i s t r i b u t i o no ff a u l t ye l e m e n t so nt h eh o s ta r r a yw i t hl a r g e rf a u l td e n s i t y t l l i sr e f l e c t s t h a tt h et e m p e r a t u r e a w a r es u b - a r r a yg e n e r a t e db yp r o p o s e da l g o r i t h mi sn e a r l y o p t i m a l s i m i l a rr e s u l t sa let r u ef o rt h ec a s eo fc l u s t e rd i s t r i b u t i o n o ft h ef a u l t y e l e m e n t s k e y w o r d s ：v l s i ；r e c o n f i g u r a t i o na l g o r i t h m s ；f a u l t - t o l e r a n tt e c h n i q u e s ；h i g h p e r f o r m a n c es u b a r r a y s ；t e m p e r a t u r e - b a s e ds u b a r r a y s ； 目录 第一章引言 1 1 研究背景 1 2 研究目标及主要贡献。 1 3 论文组织结构 第二章基本定义与相关术语 2 1 基本定义和相关术语 2 2 问题的一般性描述 第三章相关算法回顾 3 1 基于列选路的贪心算法 3 1 1 算法概述 3 1 2g c r 算法的时间复杂度 3 1 3g c r 算法的形式化描述 3 2 目标阵列的优化算法 3 2 1 算法介绍 3 2 2l d p 算法的时间复杂度 3 2 2l d p 算法的形式化描述 3 3 本章小结 第四章高性能子阵列的快速重构算法 4 1 算法基本设计思想 4 2 算法描述 4 3 实验结果分析 4 4 本章小结一 第五章温控目标阵列的构造算法 5 1 研究的问题 5 2 算法基本设计思想及形式化描述 5 2 1 贪心的列选路温控算法 5 2 2 温控子阵列的优化算法 5 2 3 子阵列温度的下界 5 3 实验结果及分析 5 3 1 故障单元随机分布时的实验结果及分析 5 3 2 故障单元聚集分布时的实验结果及分析 5 4 本章小结 第六章总结与展望 6 1 回顾与总结 6 2 未来工作展望4 7 参考文献4 9 研究生期间发表论文及参加科研情况说明51 致 射5 3 第章引言 1 1 研究背景 第章引言 网状( m e s h ) 连接的处理器阵列拥有一个规整的结构，它可以快速的执行绝 大多数信号与图像处理的算法。随着超大规模集成电路( v e r yl a r g es c a l e i n t e g r a t e dc i r c u i t e s ，v l s o 和晶片规模集成电路( w a f e rs c a l ei n t e g r a t i o n ，w s i ) 的集 成技术与集成工艺的不断发展与成熟，使得集成更大的处理单元阵列成为可能， 并且随着v l s i 和w s i 阵列密度的不断增加，单一芯片上的处理单元数量呈指数 倍增长，从而导致在芯片的制造或者实时运行过程中处理单元发生故障的概率也 随之增大。另外，当芯片装载在空间飞行器中时，因为受到维护难的条件限制， 故障处理单元可能会出现，并不断地增多。因此，使用有效的容错技术对含有故 障处理器的v l s i 阵列进行重构从而充分发挥剩余的处理器的功效，提高芯片的 可靠性，就日益成为一个亟待解决的实际的问题。 到目前为止主要有两种方法解决阵列重组问题：冗余方法和重构方法。所谓 冗余方法就是在制造芯片时预留一定数量的备用处理单元，当有工作处理单元出 现故障时，使用备用处理单元来取代不能正常工作的处理器。针对冗余方法有不 同的策略，很多文献【1 】- 【7 1 详细陈述了这些策略，还有的学者8 】【1 1 】提出了带有备用 行和列的处理器体系。这种方法的最大特点是，重构后阵列的大小是固定不变的， 但是，如果备用处理器不能完全取代发生故障的处理器，冗余重构策略就失效， 导致整个系统停止工作。 不同于冗余方法，重构方法把阵列中的所有元素都同等对待，不提前预留备 用处理单元。这种方法采用的是在故障发生后通过尽可能多的使用剩余的无故障 处理单元来构建目标阵列的策略。重构后的v l s i 阵列的阶数比原v l s i 阵列的 要小，因此，这种方法又被称为降阶重构方法。 对于v l s i 阵列上的降阶重构方法的研究开始于8 0 年代，一些学者【1 2 1 1 3 1 “1 4 】 开始了对降阶重构问题模型分析、解决策略的探讨。9 0 年代后，降阶重构方 法的研究发展迅速，s y k u o 和i y c h e n 【l ”【1 7 】针对本问题在三种不同的选路 约束条件下进行了研究：1 ) 行、列穿越方式( r o wa n dc o l u m nb y p a s s ) ，2 ) 行穿 越、列选路方式( r o wb y p a s sa n dc o l u m nr e r o u t i n g ) ，3 ) 行、列选路方式( r o wa n d c o l u m nr e r o u t i n g ) 。通过研究，他们证明了大多数基于这三种约束条件下而产生 的问题都是n p 完全问题，同时他们针对这类问题提出了启发式的解决算法。 天津工业大学硕士学位论文 c pl o wa n dh w l e o n g 1 8 】、【9 】提出了在第二及第三种约束条件下的通用启 发式解决算法，可以在多项式时间内找到近似最优解，并且指出在第二种约束条 件下阵列重组问题的一个特例可以在线性时间内得到最优解，并给出了算法的详 细描述和证明过程。这是一种新的基于贪心策略的启发式算法。由于第二种选路 约束在重构时具有更大的灵活性，后续的很多研究都偏向于以此为模型。 在相关的前期研究中，文献【2 0 】提出了一种新的选择物理行的算法，这是对 文献 1 9 1 的一种改进。文献【2 1 】设计出了目标阵列的上界，并在没有降低处理器 的利用率( h a r v e s t ) 的情况下，利用这个上界减少了算法得到目标阵列的运行时 间。文献【2 2 提出了一些新的技术，这些技术是基于启发式策略和动态规划思想 被提出的，对文献 1 9 】中的算法构造的目标子阵列进行优化从而减少了目标子阵 列中处理单元连结的长度。 需要说明的是，降阶重构方法中的行( 列) 选路过程要基于v l s i 阵列上的 开关体系机制，因为不同的开关体系机制的重构策略会有所不同，效率性能也会 不同，文献 2 3 1 和【2 2 】分别针对6 口开关和41 2 1 开关机制提出了相应的解决方法。 2 0 0 6 年，王晓东【2 4 】在综合前人研究成果的基础上，提出了一种综合考虑行、 列混合选路机制的方案，并提出了一种新的补偿策略进行重构，提高了算法的性 能，使重构后的v l s i 子阵列的阶有明显增加。 2 0 0 7 年，韩d , n t 2 5 】在已有工作的基础上，通过改进，组合，创新，构造一 个高效的算法来加速重构问题。不仅改进了部分逻辑列的扫描算法，同时，设计 了新的算法，然后把这两种方法组合成一个新的算法来重构v l s i 阵列，缩短了 重构时间。 2 0 0 8 年，王凯【2 6 】分别针对重构给定大小的子阵列和最大子阵列两个问题设计 了新的算法，对于重构给定大小的子阵列的算法，他采用先定位，后局部重构的 方法，针对重构最大子阵列的问题，他提出了一种新的动态规划方法。这两种算 法都取得到了比较好的结果。 本文中提出的新算法是在第二种约束条件下考虑二维阵列的重构问题。 1 2 研究目标及主要贡献 本文主要做了两部分工作：加速文献 2 2 】中的动态规划算法和提出温控子阵 列的构造算法。 文献 2 2 】中提出了高性能重构算法的核心部分是动态规划过程。本文中提出 了一种对该动态规划过程的加速算法。在动态规划算法的计算过程中，采用新算 法对每个处理器单元进行计算，在最好情况下只需要1 次赋值操作，在最坏情况 下也只需要3 次操作( 1 次赋值，1 次加法和1 次比较) 。而文献 2 2 1 中的动态规 第一章引言 划过程则需要5 次操作( 1 次赋值，2 次加法和2 次比较) 。在相同的假设条件下， 算法的模拟结果显示，新算法在执行时间方面相对于文献 2 2 1 改进了2 8 ，并且 重构后的阵列的内部连接长度的误差保持在可以接受的范围内。 在第二部分中，提出了构造温控子阵列的方法。首先，提出了构造最大温控 子阵列的算法。然后，在这个算法的基础上提出了对最大温控子阵列进行优化的 算法。最后，本文又给出了温控子阵列的温度的下界构造算法，并给出了温控子 阵列的相关算法的模拟结果及分析。在这一部分，分别对故障单元随机分布情况 和聚集分布的情况进行实验和分析。其中，在故障单元随机分布情况的讨论中， 分别给出了算法在小阵列( 3 2 3 2 ) ，中等阵列( 1 2 8 1 2 8 ) 和大阵列( 5 1 2 x 5 1 2 ) 上的模拟结果，并着重分析了大阵列上的曲线趋势，剖析了呈现这些变化的原因。 在故障单元聚集分布情况的讨论中，着重分析了大小为2 5 6 2 5 6 的主阵列的模拟 结果。 1 3 论文组织结构 本文共分为六章，余下章节的内容如下： 第二章，介绍重构问题的相关解决方法和方法中涉及到的术语、定义、选路 方案以及本文要研究的问题的一般性描述； 第三章，对已有的算法进行介绍，主要针对文献【1 9 】和 2 2 1 中提出的贪心列选 路算法和动态规划求局部最优列的算法； 第四章，提出一个新的算法对文献 2 2 】中的动态规划过程进行加速。首先， 给出新算法的算法思想：通过直接赋值代替文献 2 2 】中的求最小值再赋值的过 程。然后，给出了算法的模拟结果，证实了新算法是有效的； 第五章，提出了温控子阵列的构造算法，以及对这一算法的优化，并且提出 了温控子阵列的温度的下界。并分别对故障单元随机分布和聚集分布的情况进行 模拟及结果分析。 第六章，对本文的工作进行总结，并对以后的研究方向进行说明，对未来的 工作进行展望。 天津工业大学硕士学位论文 第二章基本定义与相关术语 第二章基本定义与相关术语 2 1 基本定义和相关术语 在一个v l s i a v s i 阵列中，生产出来的原始阵列称为主阵列( h o s ta r r a y ) 。阵 列中的每个处理器也被称作单元或元素。能够正常工作的处理器被称为正常单元 ( 或无故障单元) ，不能正常工作的处理单元被称为故障单元，能够正常工作并 且没有故障单元的阵列被称为无故障阵列。由主阵列的正常单元重组得到的子阵 列被称为目标阵列或者逻辑阵列。主阵列中的行( 列) 被称为物理行( 物理列) ， 把目标阵列中的行( 列) 称为逻辑行( 逻辑列) 。本文的目标是在主阵列一卜构造 出大小符合要求的逻辑子阵列。 需要指出的是，本文沿用文献 1 7 】- 2 1 】中提出的假设：故障单元指的只是运 算单元，如处理器，而内部连接线路都被看作是可以正常运行的。这是因为，芯 片的大部分区域都被处理器占据，而连接线路只是占据了很少的部分。同样，控 制器和开关在阵列重组过程中也被看作是可以正常运行的。 在本文中，h 表示主阵列，t 表示目标逻辑阵列，而“，f 表示主阵列的故障密 度( 故障处理器的数量主阵列的处理器数量1 0 0 ) 。p ( f ，力表示主阵列中瓴力处 的处理器，其中i 表示单元的行坐标，表示单元的列坐标。r o w ( e ) 表示元素p ( f ，力 的物理行坐标，c o l ( e ) 表示p ( 力的物理列坐标。r f 表示第i 个逻辑行。e ( i - 1 ，力和p ( 件1 ， ，) 分别被称为元素p ( ，) 的上邻居元素和下邻居元素。物理行扣l 和升1 分别被称为 物理行i 的上邻居行和下邻居行。同理可定义元素p ( ，) 的左邻居元素和右邻居元 素，以及左邻居列和右邻居列。 图2 1 ( a ) 是一个4e l 开关连接的4 x 4 阶v l s i 阵列。此v l s i 阵列展示了本 文将要用到的体系结构。其中白色方块代表能正常工作的处理器，灰色方块代表 有故障的处理器，白色的圆代表用于行连接的4 口开关，黑色的圆代表用于列连 接的4 口开关。 定义1 ：物理行( 物理列) 相同、物理列( 物理行) 相差l 的两个处理器被 直接相连的方式被称为行( 列) 穿越方式( r o w c o l u m nb y p a s ss c h e m e ) 。 在4 口开关连接的v l s i 阵列中，每一个处理器拥有两个内部“穿越 ( b y p a s s ) 链接线路，即行穿越和列穿越线路。因此，当需要时，每个处理器元素( 不管是 否故障) 都可以被“穿越”成为连通的电路。 同一行的处理器元素p ( ，力和p ( _ ，+ 2 ) 能够“穿越”它们之间的处理器元素p g ，+ 1 ) 而直接相连，如图2 - l ( b ) 所示。 天津工业大学硕士学位论文 定义2 ：假设甜和v 是主阵列中的两个不同的无故障处理器：当“和v 满足 i r o w ( u ) - r o w ( v ) l _ d ( i c o l ( u ) - c o l ( v ) l _ d ) 时，u 和v 才能相连，这种重构连接方式被称 为行( 列) 选路方式。 行选路链路 列选路链路 群q 渊 ( b ) e ( f + 1 ，- 1 ) e ( f + l ，力e ( f + 1 ，+ 1 ) ( c ) 故障单元0 行选路开关 口 无故障单元 列选路开关 ( a ) 基于4 口开关机制的4 x 4 处理器阵列 ( b ) 行穿越( r o wb y p a s s )( c ) 列选路( c o l 硼mr 踟u t i i l 曲 图2 1 v l s i 重构连接方式【2 2 1 行( 列) 穿越方式和行( 列) 选路方式经过行列的不同组合就构成了前面所 提到过的降阶重构算法下的三种不同的约束条件：1 ) 行、穿越，2 ) 行穿越、列 选路( 列传越、行选路) ，3 ) 行、列选路。当行选路方式和列选路方式同时被考 虑时，问题将会非常复杂。 定义3 ：行( 列) 选路方式中的约束条件d 被称为行( 列) 补偿距离，也就是 能够直接相连的处理器单元所在的行( 列) 的最大差值。 定义4 ：只有条件i 户fl 纠成立时，物理行( 物理列) f 中的无故障的处理器 与物理行( 物理列) j 中的无故障的处理器才能相连接。这个对于补偿距离的约 束条件叫做补偿约束。 在行( 列) 选路方式下，为了和文献【1 5 】 2 2 】中的定义保持一致，限定补偿 距离为l ，即：当且仅当i - 枢l 时，第确勿理行( 列) 的无故障处理器单元才能 和第物理行( 列) 的无故障处理器单元直接相连。如图2 1 ( c ) 所示列选路方案： 处理器元素p ( f ，力可以选择和p ( 计1 ，户1 ) ，p ( 件l ，力或p ( 件l ，p 1 ) 相连。 首先，参考图2 2 来观察一下在一个重构后的目标逻辑子阵列中可能存在的 第_ 章基本定义与相关术语 6 种内部连接方式。图中的6 种连接方式根据使用的开关数日可以分为两大类： 第一类如图中( a ) 和( d ) 所示，连接两个相邻的处理器元素时，只使用了一个开关； 另一类如图中( b ) 、( c ) 、( e ) 和( f ) 所示，连接相邻的两个处理器元素时，需要使用 两个开关，第一类连接被称为为“短连接”，与之对应的第二种连接被称为“长 连接”。在图2 2 中，( a ) 、( b ) 和( c ) 所使用的连接方式为行选路方式，而( d ) 、( e ) 和( f ) 所使用的则为列选路方式。 ( f ) 图2 - 2 重构v l s i 后的6 种内部连接方式【捌 2 2 问题的一般性描述 本文主要研究二维网状连接的v l s i 阵列的降阶重构问题，问题的一般性描 述如下： 给定一个大小为m x r 的网状连接的主阵列h ，在行穿越、列选路方式下找到 包含主阵列h 中的某些特定行的最大目标子阵列。 文献 i s l 和 1 9 1 对文献 1 7 】提出的算法进行了改进，提出贪心列选路算法 ( g r e e d yc o l u m nr e r o u t i n g ，g c r ) ，使算法运行时间从多项式量级降低到线性量 级。文献【2 2 】对贪心的列选路算法的运行结果进行了优化，减少了重构后的v l s i 目标子阵列的长连接数量，提高了性能。第三章将详细介绍文献 1 9 】和文献 2 2 】 中的这两种算法。 一 天津工业大学硕士学位论文 第三章相关算法回顾 第三章相关算法回顾 3 1 基于列选路的贪心算法 3 1 1 算法概述 假设尺l ，r 2 ，尺m 表示主阵y l j h 中所有的m 个物理行，而r ，r ，r 。是被选 定的用来重构新的逻辑子阵n t 的若干特定物理行。逻辑阵列t 中的任意一个逻 辑列的重构都是从足，足，足。的每一行获得一个无故障元素，并且只能获得一 个无故障元素。文献【1 8 】和【1 9 】中给出了解决此问题的算法，被称之为贪心的列 选路算法( g r e e d yc o l u m nr e r o u t i n g ，g c r ) ，并且g c r 算法的时间复杂度是线性级 的。 本文使用c o l ( u ) 和c o t ( v ) 分别表示处理器u 和处理器，的物理列标号。 定义5 ：对于尾行中的一个无故障处理器材： l 、对于任意2 s 亡抑，彳( “) = 1 ，：v e r i n ，无故障且i c o l ( u ) - c o l ( v ) l 1 ) ； 2 、对于任意1 9 霸一1 ，彳矿( 炉 ，：1 ，尺什l ，无故障且l c o l ( u ) 一c o l ( v ) l ； 3 、对于任意v a d f ( u ) 或者v e a 矿( “) ，当且仅当c o l ( v ) - c o l ( v ) = - l ，0 或者l 时，这个处理器 ，分别被称为处理器u 的左相邻、中间相邻和右相邻元素。 其中，a a ( u ) 被称为处理器u 的相邻集合。算法g c r 中的核心实现部分是通 过对特定行中的每一个无故障处理器u 的相邻集合进行运算来实现的。 对于r ，( 产1 ，2 ，加) 行的每一个处理器元素u ，a 矿( 甜) 中的处理器按照物理 列号从小到大的顺序为选路时的优先考虑顺序。在存储时，为了计算方便，彳矿( “) 中的处理器可以按照物理列号的递增顺利来存放。 g c r 算法根据从左到有的顺序选择后继元素来组成逻辑列，从而构建目标阵 列。每一次的迭代过程总是考虑如何形成当前最左边的逻辑列。 g c r 算法的过程如下： 首先，在物理行r l 中选择当前最左边的无故障处理器作为当前逻辑列的头节 点，把它称为处理器u ，并把u 标记成“已检测过”的状态。 然后，枷矿( 甜) 中选择当前最左边的处理器( 即物理列号最小的处理器) ， 称之为处理器，再把v 连接n u ，1 ，也被标记成“已检测过”的状态。 g c r 算法其实是一个迭代过程：在g c r 算法运行的每一步里，都试图把，与 集合彳矿( v ) 中的物理列号较小、并且状态不是“已检测过的处理器相连接。如 果没有找到满足上述条件的处理器，也就是说v 不能按照算法需要和它的后继单 元顺利连接，那么可以得出这样的结论，即在这次迭代中无法生成一个包含1 ，的 天津工业大学硕士学位论文 逻辑列。如果发生这样的情况，需要回溯n v 的前驱w 。下面需要做的就是在集合 彳矿( w ) e e 再次找一个当前物理列号最小的且状态不是“已检测过”的处理器与 w 相连接。这种过程需要不断的迭代，直到遇到下面两种情况停止：( 1 ) 处理 器，在最后一个物理行r m 上，且【已经将尺m 中的某个处理器与物理行尺聃1 中的处理 器进行了连接； ( 2 ) 算法回溯到第一个物理行r l 中的某个处理器u ，且a d j + ( u ) 中的后继单元都已经被标记为“已检测过”或彳矿( “) 本来就是空集。如果是第二 种迭代终止情况，算法再次循环，从第一行尺l 中寻找当前物理列号最小的，且未 被标记成“已检测过”的无故障处理器u ，重复上述过程，直到第一行r l 中所有 可用的处理器都已经被检测过，则整个算法完成。g c r 算法就是这样一个接一个 地找出当前最左边的逻辑列，直到从主阵列中无法再生成新的逻辑列，从而找到 目标阵列。 尺l 尼 尺3 尺4 e ( 9 ，1 ) 图3 1 g c r 算法具体实例 如图3 - l 的实例所示：在这个例子中，首先选择t r ! 行中的无故障单元p ( 1 ，1 ) 作为第一个逻辑列的头节点，并把e ( 1 ，1 ) 标记为“已检测过”的状态。然后，根 据定义5 可以计算出p ( 1 ，1 ) 的相邻集合彳矿( p ( 1 ，1 ) ) = p ( 2 ，1 ) ，p ( 2 ，2 ) 。显然，单元 e ( 2 ，1 ) 的物理列号较小，连接e ( 2 ，1 ) n e ( 1 ，1 ) ，并把e ( 2 ，1 ) 的状态标记为“已检测 口 口 口 口 曩 口 口 口 口 尼 凡 尼 q 菅 凡 第三章相关算法回顾 过”。接着计算e ( 2 ，1 ) 的相邻后继集合彳矿( ( p ( 2 ，1 ) ) ，如此迭代下去，直到把单元 e ( 9 ，1 ) 连接至l j e ( 8 ，1 ) ，并把e ( 9 ，1 ) 的状态标记成“己检测过”为止，第一个逻辑列 就构造完成了。 在构造第二个逻辑列的过程中，当把e ( 2 ，2 ) 连接至l j e ( 1 ，2 ) ，并把p ( 2 ，2 ) 标记成 “已检测过”的状态以后，开始计算e ( 2 ，2 ) 的相邻后继集合彳矿( ( p ( 2 ，2 ) ) 。可以发 现，在补偿距离d = - i 的限制条件下，a d j + ( e ( 2 ，2 ) ) 为空集，也就是说没有后继节点 能与e ( 2 ，2 ) 相连，这时采用的策略是回溯。重新回至t j e ( 2 ，2 ) 的前一个节点p ( 1 ，2 ) ， 选择e ( 2 ，2 ) 右边的无故障单元e ( 2 ，3 ) 与p ( 1 ，2 ) 相连，并把e ( 2 ，3 ) 标记成“已检测 过”的状态。 在构造第六个逻辑列的过程中，当把e ( 2 ，7 ) 连接至t j e ( 1 ，6 ) 以后，同样产生了 回溯，但是彳矿( p ( 1 ，6 ) ) 中已经不存在状态末被标记的节点了。按照算法规定，迭 代终止。接着寻找r l 行中e ( 1 ，6 ) 右边的可用节点作为头节点构造第六个逻辑列。 当回到r l 行，并且尺l 行中已经不存在无故障且状态未被标记的处理单元时， 整个算法终止，最大的逻辑目标子阵列构造完毕。 3 1 2g c r 算法的时间复杂度 g c r 算法的时间复杂度为o ( 加，即线性时间复杂度。其中为h 中的无故 障元素的个数。 在文献 1 9 】中，l o w 给出了g c r 算法的时间复杂度是线性级的证明过程：假 设，是主阵列h 中的两个无故障的处理器单元。如果，彳矿( 甜) ，那么就在”， ， 之间存在一个有效的内部连接。对于f 行r f ( i = 1 ，2 ，m 1 ) 的任意无故障元素甜， 都有i a , f ( “) l s 3 ，所以，甜的有效内部连接最多为3 个。因此，在无故障元素共有 个的主阵列h 中，最多的有效内部连接数为3 n 。g c r 算法的实施过程中，每一 个有效的内部连接( 甜，叻( ，彳矿( 掰) ) 被检测的次数最多为2 。所以，可以得到结 论，g c r 算法的时间复杂度为d i ，也即线性时间复杂度。 另外在文献【l8 】、 1 9 中l o w 已经采用反证法证明了g c r 算法找到的子阵 列是包含选定行的最大逻辑子阵列。 3 1 3g c r 算法的形式化描述 g c r 算法的形式化描述如图3 2 所示。 天津工业大学硕士学位论文 图3 - 2 g c r 算法的形式化描述 第三章相关算法同顾 3 2 目标阵列的优化算法 3 2 1 算法介绍 目标阵列的优化算法( l o c a lo p t i m a lc o l u m nb yd y n a m i cp r o g r a m m i n g ，l d p ) 是在2 0 0 6 年发表的文献 2 2 1 中提出的，该算法是在文献 1 9 1 中提出的g c r 算法 的基础上，对g c r 的结果进行再优化，通过减少v l s i 子阵列中的长连接个数 来提高子阵列性能指标的方法。 下面，用一个实例来说明两者的区别。如图3 - 3 所示，( a ) 、( b ) 都是由4 x 4 阶的原始主阵列构造的4 3 阶的最大目标逻辑子阵列。左边的目标阵列是用 g c r 算法构造的，其中包含了6 个“长连接”；右边则是用l d p 算法优化后的 结果，只包含2 个“长连接”。 图3 3 中g c r 算法得到的子阵列和l d p 算法优化后的子阵列的内部连接情 况的对比直观上说明，l d p 重构后的子阵列中的逻辑列变“直”了，故称之为 “取直方法 。 显而易见，在目标阵列的阶数不变的前提下，如果能够尽可能的地减少其内 部所使用的“长连接”数，这样内部处理器之问的通信总长度就能降低，同时， 也有利于减少能耗。 问题的一般描述：给定一个大小为m x n 的网状连接的主阵y u h ，其中有个 无故障元素，r l ，尺2 ，凡是主阵列h 中被选出的某些特定行，在行穿越和列选 路方式下构造包含这些特定行的“取直”逻辑子阵列。 卜卜一1 2 h呻扣j 甲 上 t 1 卜卜荡b 、 ， f 一 一 、 t t 一，卜_ 陆b 吨 订土南 丫 g 弋附 j k t 工 州h tt ，卜_ 陆k 廿 丫i t t j，j 1r - j l l ( a ) g c r 算法构造的目标阵列 ( b ) l d p 算法优化后的目标阵列 图3 3 不同目标阵列的内部连型2 2 l 设r l ，尺2 ，尺卅表示主阵列h 中所有的m 个物理行，r l ，r 2 ，凡表示其中的 某些物理行，t 为逻辑阵列，嘞逻辑阵列中的逻辑列的集合。逻辑阵? u t 包含了 天津工业大学硕士学位论文 行尺l ，尺2 ，凡，也就是说，逻辑列集合u 中的任意一个逻辑列的重构都是从尺1 到凤的每一行中获得一个无故障元素，并且每一行只能获得一个无故障元素。 定义6 1 2 2 1 ：对于u 中的任意两个逻辑列g 和o ，并腑则： l 、任意l s 斟，如果c p 中的第f 个元素( 即位于第f 个特定行的元素) 都在c 口 中第f 个元素的左边，那么称之为c 口 c q ； 2 、任意l i k ，如果g 中的第f 个元素( 即位于第f 个特定行的元素) 都在g 中第f 个元素的左边或者相同位置，那么称之为c p 5 g ： 3 、如果g c q ，那么称。和c 。是相互独立的。 假设对某一主阵列h ，通过它的某些特定物理行能够生成七个逻辑列，那么， 这k 个逻辑列一定是相互独立的。这是因为每次都检查后继集合中未被标记为 “己检测过 的单元，不会出现相邻的两个逻辑列共用一个单元的情况。通过上 面的叙述可知，g c r 算法能够产生包含阶相互独立的逻辑列的最大目标逻辑子 阵列。并且，从左到右的第，个逻辑列就是g c r 算法第，次循环产生的。这是因为 g c r 在生成逻辑列时是按照从左到右的顺序搜索主阵列的，并且彳矿( 甜) 中的 处理器是按照物理列号从小到大排列的。假设g c r 产生的目标阵列为t ，哟逻 辑阵列中的逻辑列的集合，帅包含阶相互独立的逻辑列c l ，c 2 ，c i 。l d p 就 是对这后个逻辑列进行“取直”的算法。 任意无故障处理器u 的彳矿( 功中的后继处理单元的优先级计算函数： 一正 如屎c o z ( 访一c o l ( u ) = - 1 ； 如果z 一c o l ( u ) = o ； 如呆c o l c v ) 一z ( 妨= l ； 其中，甜尺f ，y e a 矿( “) ， l ，2 ，m - 1 ) 。 假设曰，b ，u 并助t b ，那么用彳陴，b r 】来表示那些以b 卜研为闭边界( 即 包含这两个逻辑列上的处理器) ，内郭只包含无故障处理器的区域；同理，用a 8 ， 曰，) 来表示以b ，为闭边界，以研为开边界，内部包含无故障处理器的区域，其中， 召，和研分别被称为左、右边界。 对于r f ( t = - i ，2 ，m 1 ) 行的任意无故障处理器u ，如果处理器v 是它的后继 节点，即1 ，4 矿( 甜) ，那么，一定存在一个有效边e d ( u ，v ) 表示u 能连接到v 。对于 每一个有效边e d ( u ，们，给出它的“长连接数”的定义。 定义7 1 2 2 ：用c ( 甜，v ) 表示任意有效边e d ( u ，v ) 的“长连接数”，贝u c ( u ，v ) 的计算 公式为c ( u ，v ) = l c o l ( u ) 一c o t ( v ) i 。 在l d p 的计算过程中，逻辑列的优劣是用“长连接数来衡量的。例如，当 构造逻辑列c f 时所用的“长连