（计算机软件与理论专业论文）torus网络中处理机分配策略的研究.pdf

t o m s 网络中处理机分配策略的研究 摘要 网络技术与并行技术的高速发展，使得人们对计算能力的要求随之增 加，而并行计算机是实现高性能计算的最有效的技术途径。2 0 世纪8 0 年代 末以来，高性能商用微处理器技术取得了迅猛的发展，使高性能大规模并 行计算机的实现成为可能。随着并行计算系统的应用和推广，人们不断增 长的需求为科研工作者提出了一系列新的挑战课题。 本文就t o m s 结构的多处理机系统中处理机的搜索与分配算法进行了较 为深入的研究，在已有工作的基础上进行了探索和创新，并取得了一定的 成果。具体内容体现在如下几个方面： 1 、系统阐述了网络技术与并行计算技术的发展，对并行计算中的任务 调度和处理机分配的联系与区别进行了探讨。 2 、在系统分析已有的子网搜索与分配算法的基础上，以二维t o m s 结构 的多处理机系统为例，提出了一种相对快速、高效的子网搜索分配算法， 该算法通过简单的坐标运算和空间运算能够显著地缩小搜索范围，从而快 速地找到满足要求的子网。 3 、随着系统中处理机数目的增加，处理机出现故障的情况是难以避免 的，一旦出现故障结点，原有的搜索算法将受到限制，从而影响系统的性 能；针对这种情况，本文对具有故障结点的t o m s 网络进行研究，给出了搜 索由正常结点组成的最大子网的算法，并用实例验证了算法的可行性。 t 4 、在连续分配策略的基础上提出一种非连续分配策略，该策略能够进 一步提高处理机的利用率，降低任务的等待时间，提高整个系统的效率。 5 、最后，提出需要进一步开展的研究工作。 关键词：t o r u s 网络并行计算机子网搜索故障结点 处理机分配 r e s e a r c ho np r o c e s s o ra i l o c a t i o ns c h e m ef o r t o r u s c o n n e c t e dm u l t i c o m p u t e r s a b s t r a c t a st h e d e v e l o p m e n to fn e t w o r kt e c h n o l o g y a n d p a r a l l e l t e c h n o l o g y , t h e r e q u i r e m e n t sf o rc o m p u t i n gp o w e ri sa l s oi n c r e a s e d 。a n dt h ep a r a l l e lc o m p u t e r i st h em o s te f f e c t i v et e c h n i c a lm e a n st oa c h i e v eh i 曲一p e r f o r m a n c ec o m p u t i n g p o w e r a t t h ee n do ft h e2 0 t hc e n t u r y , h i g h p e r f o r m a n c ec o m m e r c i a l m i c r o p r o c e s s o rt e c h n o l o g yh a sm a d er a p i dd e v e l o p m e n t ，s ot h e r e a l i z a t i o no f h i g h p e r f o r m a n c em a s s i v e l yp a r a l l e lc o m p u t e ri sp o s s i b l e w i t ht h ea p p l i c a t i o n a n dp o p u l a r i z a t i o no fp a r a l l e lc o m p u t i n gs y s t e m s ，as e r i e so fc h a l l e n g e sh a s b e e nr a is e df o rp e o p l ei nt h ef i e l d t h i sp a p e rh a sm a d et h er e s e a r c ht h o r o u g h l yo nt h ep r o c e s s o ra l l o c t a i o ns c h e m e f o rt o r u s c o n n e c t e dm u l t i c o m p u t e r s b a s e do nt h ep r e v o i u sw o r k s ，t h ep a p e rh a s m a d es o m ee x p l o r a t i o na n di n n o v a t i o n ，a n dd e v e l o p e ds o m en e wr e s u l t s t h e i n n o v a t i v ew o r k so ft h ep a p e rh a v eb e e nl a i dd o w n ： 1 t h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dp a r a l l e lc o m p u t i n gt e c h n o l o g y a r ee x p o u n d e d t h ed i s t i n c t i o n a n dc o n t a c tb e t w e e nt a s ks c h e d u l i n ga n d p r o c e s s o ra l l o c a t i o na r ed i s c u s s e d 2 b a s e do np r e v i o u sr e s e a r c h ，w ep r o p o s e af a s ta n de f f i c i e n tp r o c e s s o r a l l o c a t i o ns c h e m ef o r2 d t o r u s ，c o n n e c t e dm u l t i c o m p u t e r s b yu s i n gs i m p l e i i i c o o r d i n a t ec a l c u l a t i o na n ds p a t i a ls u b t r a c t i o n ，t h ep r o p o s e ds c h e m ec a nr e d u c e t h es e a r c hs p a c ed r a s t i c a l l y , h e n c eaf l e es u b m e s hc a nb el o c a t e dq u i c k l y 3 f o ral a r g es y s t e m ，t h ep r o b a b i l i t yo ff a u l to c c u r r e n c em a yb el a r g e ，o n c e s o m ep r o c e s s o r sa r ef a i l u r e ，t h eo r i g i n a la l g o r i t h mw i l lb el i m i t e d ，t h u st h e p e r f o r m a n c eo ft h es y s t e mi s a f f e c t e d s ot h i sp a p e rp r o p o s e sa ne f f i c i e n t a p p r o a c hf o ri d e n t i f y i n ga l lt h em a x i m u mh e a l t h ys u b m e s h e sp r e s e n ti naf a u l t t o m s a n dt h ef e a s i b i l i t yo ft h ea l g o r i t h mi sv e r i f i e db ye x a m p l e 4 b a s e do n c o n t i g u o u s a l l o c a t i o n s t r a t e g i e s ，an o n c o n s e c u t i v ea l l o c a t i o n s t r a t e g yi sp r o p o s e d t h es t r a t e g yc a ni m p r o v et h eu t i l i z a t i o no fp r o c e s s o r s ，a n d r e d u c et h ew a i t i n gt i m ef o rt a s k s ，t oi m p r o v et h ee f f i c i e n c yo ft h ee n t i r es y s t e m 5 f i n a l l y , t h ep a p e ri n d i c a t e st h a tt h ew o r k n e e dt ob ef u r t h e rs t u d i e d k e y w o r d s ：t o m s ；p a r a l l e lc o m p u t i n g ；s u b t o m ss e a r c h i n g ；f a u l t y p r o c e s s o r ；p r o c e s s o ra l l o c a t i o n i v 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：獭 学位论文使用授权说明 聊年 月髟日 | 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的e p $ 1 j 本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务： 学校可以采用影印、缩印、数字化或其它复制手段保存论文： 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：徐琢 导师签名： p 多年么月竹 广西大学硕士学位论文t o r u s 网络中处理机分配策略的研究 1 1 选题背景和意义 第一章绪论 目前，计算技术正成为与理论研究和实验分析相提并论的第三种科学研究手段。例 如，科研人员常使用计算机来模拟那些非常复杂以致不能由理论可靠地预测的现象，以 及那些非常危险或昂贵的试验【lj 。反过来，在计算科学上所取得的成功，又往往在计算 精度和速度上对计算机的性能提出更高的要求。最近的三十多年罩，在微电子技术发展 的推动之下，单处理机的性能几乎以几何级数增长的方式提高。在今后的一段时期内， 这种发展趋势还会持续下去。除此之外，另外一种较为经济且能有效地提高计算机性能 的途径便是并行处理。所谓的并行处理，便是将, 台处理机及相应的存储模块以某种拓 扑结构经网络互连起来，所有 1 台处理机同时工作共同求解某个大型应用。而多处理机 系统( 例如大规模并行处理机，机群等) 则被认为是构造高性能并行计算环境最有潜力的 方法。 影响多处理机系统性能的主要因素是网络的互连结构和操作系统1 2 j 。在网络互连方 面，多种静态网络互连拓扑结构已经在实际中得到应用，例如环、二叉树、网格、超立 方体、环网等。在操作系统方面要求能够支持多用户、多任务环境，通过有效地系统资 源管理使大量的任务能够同时执行。操作系统中实现这一功能的主要是资源管理系统， 它主要由任务调度和处理机分配两部分组成。任务调度主要负责任务队列中每个任务执 行的顺序；处理机分配主要负责为将要执行的任务选择合适的处理机p 巧j 。 国内外对多处理机中的任务调度进行了大量的研究，相比之下，对处理机分配的研 究相对较少。然而随着系统中处理机规模的增大，如何设计有效的处理机分配算法，使 其能够最大化处理机的利用率，同时具有最小分配时间开销，已成为提高系统性能所必 须考虑的一个问题。而网格( m e s h ) 、环网( t o r u s ) 等规则的互连网络结构已在新一代的实 验及商用的分布存储并行计算机中得到了广泛应用。2 d m e s h 陬 连接简单，每个节点伸 出上下左右四个通道与相邻节点相连，伸缩性好，便于扩展，便于组装。2 d - m e s h 网的 互连代价是2 州n 1 陀) ，延迟是2 n 汜，对分带宽为n 2 。二维环形网2 d t o m s 的互连代价( 2 n ) 略高于2 d m e s h ，但延迟洲) 和对分带宽( 2 n 1 2 ) 的性能都较2 d m e s h 改盖了一倍，同时 2 d t o r u s 网络负载的均衡性优于2 d m e s h 6 1 ，而目前专门针对t o m s 网络中的处理机分配 的研究相对较少。 基于以上分析，本文密切跟踪国际科技前沿，对传统的处理机分配算法进行改进， 提出新的适用于t o m s 网络的子网搜索与分配算法，并针对具有故障结点的网络进行了专 门研究提出相关的算法。这不仅丰富了并行计算的内容，也为t o m s 网络的广泛应用与发 展提供了理论基础。 广西大掌硕士学位论文t o r u s 网络中处理机分配策略的研究 1 2 国内外研究概况 近十几年来，国内外对多计算机中处理机分配策略的研究主要基于m e s h 结构，对 t o r u s 结构的研究很少。其方法大致可以分为两类：连续分配策略的研究和非连续分配策 略的研究。 在连续分配中，分配给同一任务的处理机在物理上要求是相邻的，除此之外有些系 统还要求所分配的所有处理机必须仍保持原网络的拓扑结构。连续分配最突出的缺点是 容易导致大量的内片断和外片断，其中内片断是指给一个任务分配了一个超过它所需要 的节点机数的大的空闲子网，从而造成资源的浪费；外片断是指系统中有足够的节点机 可以被分配，但由于各节点机在物理上不是相邻的，从而不能找到满足需要大小的一个 空闲子网。这样的一些片断严重降低了处理机的利用率。此外，现有的一些算法还不具 备子网的完全搜索能力( 所谓子网的完全搜索能力是指只要网络中存在符合要求的子 网，搜索算法就一定能够找到) 。文【5 】首先提出了2 d b ( t w od i m e n s i o n a lb u d d y ) 算法， 该算法只适用于长度为2 的幂的方形网格结构，对请求任意节点机数的任务，它将分配 可容纳该请求的最d , 2 的幂的方形子网，因此该算法存在着严重的内片断问题。为了解 决算法2 d b 的限制，文 7 提出了f s ( f r a m es l i d i n g ) 算法，该算法适用于任意规模的m e s h 网络，可以避免内片断的产生，但它不具备完全子网搜索能力，从而又导致外片断的产 生。为了提高算法f s 的性能，文【8 】中提出了f f ( f i r s t f i t ) 矛n b f ( b e s t f i t ) 算法，与原来 的算法相比，该算法简单、高效并且能够提供相对较好的性能，但它同样不具备完全子 网搜索能力。最近有人提出基于空闲子网列表( 或b u s y 子网) 的方法，这些方法主要 是为了降低处理机的分配与回收时间。后来 9 1 5 】等文献中提出了各种连续分配算法， 但外片断的问题始终没能得到很好的解决。 为了解决外片断的问题，近年来随着虫孔路由技术的发展，一些学者又提出了不连 续分配方澍1 6 。2 0 1 。虫孔路由与之前的其它交换技术相比最主要的特点就是结点机之间的 距离对消息延迟的影响降低了 2 1 - 2 2 1 。在非连续分配中，一个分配请求可以分成几个小部 分，每个小部分分配一个满足要求的子网，而这几个子网可以是不相邻的。非连续分配 策略主要存在两个问题：第一，执行同一个并行任务且处在不同子网的处理机之间进行 消息交换时，可能会与其它的任务竞争通信资源；第二，执行同一个任务的不同处理机 之间的距离明显增大，而距离的增大会导致通信时间以及消息竞争的可能性随之增加。 文f 1 8 1 中首先提出了随机算法，该算法为将要执行的任务随机选择指定数目的处理机， 由于它没有考虑处理机之间的邻接性，从而导致通信延迟的增加。文 1 8 中的分块算法 ( p a g i n g ) 将整个m e s h 网络分成规模相等的一些子网，从而在一定程度上实现了邻接性， 但是它又可能会导致内片断的产生。文【2 3 】中的m b s ( m u l t i p l eb u d d ys y s t e m ) 算法是 2 d b 算法的扩展；文 2 4 】中的a n c a ( a d a p t i v en o n c o n t i g u o u sa l l o c a t i o n ) 第一次尝试 连续地分配一个任务，该算法存在的一个问题就是当达到一定条件时会产生外片断。文 2 广西大掌硕士掌位论文t o r u s 网络中处理机分配策略的研究 【2 5 - 2 6 先后对已有的算法进行改进，实现更大程度的邻接性。 目前针对t o r u s 结构的多处理机中的子网搜索与分配算法的研究的文献较少，仍有许 多空白领域有待研究。 1 3 主要工作介绍 本文首先对网络技术与并行计算技术进行理论研究，并将多处理机中的任务调度与 处理机调度进行比较分析，完善t o r u s 结构的多处理机系统中处理机的搜索与分配算法。 本文丌展并完成了以下方面的工作： 1 、系统阐述了网络技术与并行计算技术的发展，对并行计算中的任务调度和处理 机分配的联系与区别进行了探讨。 2 、在系统分析已有的子网搜索与分配算法的基础上，以二维t o m s 结构的多处理机 系统为例，提出了一种相对快速、高效的子网搜索分配算法，该算法通过简单的坐标运 算和空间减法能够显著地缩小搜索范围，从而快速地找到满足要求的子网。 3 、随着系统中处理机数目的增加，处理机出现故障的情况是难以避免的，一旦出 现故障结点，原有的搜索算法将受到限制，从而影响系统的性能；针对这种情况，本文 对具有故障结点的t o m s 网络进行研究，给出了搜索由正常结点组成的最大子网的算法。 4 、在连续分配策略的基础上提出一种非连续分配策略，该策略能够进一步提高处 理机的利用率，降低任务的等待时间，提高整个系统的效率。 5 、最后提出需要进一步开展的研究工作。 1 4 论文的组织结构 论文共分六章，各章的主要内容如下： 第一章简要介绍论文的选题背景、意义及国内外研究现状，在此基础上提出了论 文的主要研究工作。 第二章对并行计算机的体系结构，常用的互连网络的类型进行了简要的介绍；详 细介绍了多处理机系统中的两种调度：任务调度和处理机调度( 即处理机的搜索与分 配) ，给出了两种调度的研究内容、研究现状及存在的问题。这些都是本文后续内容的 理论基础。 第三章首先系统分析已有的子网搜索与分配算法，并提出其中的不足之处，然后 以t o r u s 结构的多处理机系统为例，提出了一种相对快速、高效的子网搜索分配算法，该 算法通过简单的坐标运算和空间减法能够显著地缩小搜索范围，从而快速地找到满足要 求的子网。 第四章对具有故障结点的t o m s 网络进行研究，给出了搜索由正常结点组成的最大 子网的算法，用实验仿真该方案并对实验结果进行分析。 第五章在连续分配策略的基础上提出种非连续分配策略，该策略能够进一步提 3 广西大掌硕士掌位论文t o r u s 网络中处理机分配策略的研究 高处理机的利用率，降低任务的等待时间，提高整个系统的效率。 第六章总结全文，对未来的工作进行展望。 4 广西大掌硕士掌位论文t o r us 网络中处理机分配策略的研究 2 1 并行计算与互连网络 第二章预备知识 当前科学技术迅猛发展，人类对高性能计算技术的需求越来越大。自上世纪8 0 年代 以来，计算机处理器的性能每1 8 个月翻一番【27 1 ，但仍不能满足国防、航空航天、石油勘 探与开发、材料设计和生命科学等应用领域对高性能计算的需求。目前出现了许多具有 重大挑战性的应用问题，如全球天气预报、分子动力学实验、核试验的模拟和生物遗产 密码破译等。这些应用问题都要求计算机具有万亿次( t e r a f l o p s ) 甚至千万亿次( p e t a f l o p s ) 以上的计算能力，而单个处理器即使集成度达到极限也是远远不够的，唯一的途径就是 把成千上万个处理器连接起来，组成并行计算机。例如，在最新公布( 2 0 0 5 年1 1 月) 的全 世界速度最快的超级计算机5 0 0 强【2 8 】排名中，排名第一的是i b m 的b l u eg e n e l ，其峰值 速度超过每秒2 8 0 6 t e r a ( 1 0 1 2 ) 次浮点运算，所用的处理器数多达6 5 ，5 3 6 个。为了连接这 么多的处理结点，获得如此之高的计算速度，就必须设计高性能的互连网络和提供高效 的通信系统。 2 2 并行计算机体系结构 使用商品化部件来设计并行计算机的思想，推动t 2 0 世纪8 0 年代初分布内存多处理 器系统和多计算机的发展。这些并行计算机包括一组处理器，每个处理器都连接自己本 地存储器，处理器这间通过互连网络传递消息来完成通信。图2 1 给出了这种结构的示 意图【2 9 】。 多计算机系统的编程不是一件容易的事情，程序员必须小心地处理分布在各处理器 之间的代码和数据，当其它处理器需要某些数据时将产生消息传递调用。而共享主存多 处理器系统对所有的处理器提供单一的存储器空间，这简化了处理器之间的数据交换。 处理器通过互连网络访问主存( 参见图2 1 ) ，这种结构称为一致性存储器访问体系结构。 互连网 络 f i g 2 - 1d i s t r i b u t e dm e m o r ym u l t i p r o c e s s o r 图2 1 分布式存储多处理机 5 互连网络 f i g 2 - 2s h a r e dm e m o r ym u l t i p r o c e s s o r 图2 - 2 共享存储多处理机 广西大学硕士学位论文 t o r u s 网络中处理机分配策略的研究 f i g 2 3d i s t r i b u t e d s h a r e dm e m o r ym u l t i p r o c e s s o r 图2 - 3 分布式共享存储多处理机 随后，共享主存多处理器系统采用了先前为多计算机建立的模式，将共享存储器物 理地分布在多个处理器之间，这样就减少了本地存储器的访问时间，从而提高了系统的 可伸缩性。这种并行计算机称做分布共享主存多处理器系统( 参见图2 3 ) 。访问远地存 储器是通过互连网络实现的，这与多计算机非常类似。分布共享主存多处理器系统和多 计算机的主要区别在于消息的启动方式，分布共享主存多处理器系统利用存储器访问， 而多计算机系统通过系统功能调用来完成。为了减少存储器延迟，每个处理器都设有若 干级c a c h e 存储器，以匹配处理器和存储器之间的速度差异。这种体系结构提供了非一致 性存储器访问。实际上，非一致性主要归因于c a c h e 和主存访问时间的差异，而不仅仅是 本地和远地存储器访问时间的差异。分布共享主存多处理器系统出现的主要问题是c a c h e 一致性。目前已经提出了许多硬件和软件的c a c h e 一致性协议，这些协议的实现无疑在互 连网络中又增加了额外的通信量。 由于使用了全定制的互连网络，这使得多计算机和分布共享主存多处理器系统非常 昂贵，所以又提出了用工作站集群( n o w ) 来构造并行计算机的廉价方法。工作站集 群利用了l a n 中发展的新技术，有人提议使用a t m 交换来实现n o w ，但是a t m 交换机 成本仍然很贵，所以有必要专门为工作站和个人计算机互连设计高性能的交换机，以便 降低系统成本。 尽管多计算机和分布共享主存多处理器系统的互连网络有很多相似之处，但是它们 的性能要求却差别很大，这一点值得注意。使用分布共享主存多处理器系统时，消息通 常都很短。除此之外，网络延迟也很重要，因为存储器访问时间依赖于网络延迟。但是， 在使用多计算机时消息一般都较长而且不经常使用，多计算机中消息通信的粒度通常由 程序员调整。另一方面，多计算机币 i n o w 的互连网络主要用于消息传递。但是工作站 地理分布的特点又影响了处理器连接的方式，而且单个的处理器可能在任何时候接入网 络或从网络断开，这也给设计带来了较大的影响。 2 3 互连网络分类啪3 传统的互连网络是根据操作模式( 同步或异步) 和网络控制( 集中式、分散式或分 布式) 来分类的。现在，多计算机、多处理器系统和n o w 占领了并行计算机市场，所有的 6 广西大学硕士掌位论文t o r u s 网络中处理机分配策略的研究 这些体系结构都实现了分布式控制的异步网络。因此，我们将根据另外一个标准进行分 类，该标准更符合当前的实际情况。该方案主要根据网络拓扑将现有的互连网络分为4 大判3 1j ：共享介质网络、直接网络、间接网络和混合网络。 在共享介质网络中，所有的通信设备共享传输介质。另一种是使用点到点的链路， 把各个通信设备直接连接到网络中其它通信设备的子集。在这种情况下，任何非相邻设 备之间的通信都要经过多个中间设备进行信息传输，这种网络就是间接网络。问接网络 不是直接把通信设备连接起来，而是使用一个或多个交换机来连接设备。如果有多个交 换机，它们之间使用点到点链路连接。在这种情况下，任何非相邻设备之间的通信都要 经过一个或多个交换机传输。 2 3 1 共享介质网络 在共享介质网络结构中，所有的通信设备共享传输介质，同一时刻只允许一个设备 使用网络，如图2 4 所示。每个连接到网络的设备都包括请求电路、驱动电路和接收电路， 它们用来处理传输的地址和数据。网络本身通常是被动的，其本身并不产生任何消息。 f i g 2 - 4s h a r e d 。m e d i u mn e t w o r k 图2 4 共享介质网络 共享介质互连网络的一个重要问题是仲裁策略问题，为了分解网络访问冲突，必须 确定共享介质网络的主设备。共享介质的一个特点是它具有支持原子广播的能力，网络 上所有的设备都可以监听网络活动，接受共享介质上传输的信息。这一特性对那些要求 一对全或一对多广播服务的应用特别重要，比如栅栏同步和侦听c a c h e 致性协议。由 于网络带宽的限制，单个共享介质只能支持有限数量的设备，否则介质会成为瓶颈。 2 3 2 直接网络 直接网络是指网络中的每个结点都与其它一些结点直接相连的网络。由于这类网络 在运行过程中不能改变网络的连接方式，因此也被称为静态网络。在直接网络中，结点 之间的连接方式决定了互连网络的拓扑结构。网孑l ( m e s h ) 、环网( t o m s ) 和超立方体 ( h y p e r c u b e ) 都是典型的直接网络。其它如树( t r e e ) 、带环立方( c u b e c o n n e c t e dc y c l e ) 、星 图( s t a rg r a p h ) 等也都是经常被研究的直接网络。图2 5 和图2 6 分别描述了一个6 6 的网 孔和一个6 6 的环网。 7 广西大掌硕士掌位论文t o r u s 网络中处理机分配策略的研究 f i g 2 - 56 x 6m e s h 图2 56 x 6 网孔 2 3 2 1 结点的结构 护b b b u审 4 -扛扛扛4 -厶 扛长扛扛岳厶 扯扛扯扛扛厶 扛厶仁之卜 卜4 - 3 一出卜出卜出出占 f i g 2 66 x 6t o r u s 图2 - 6 6 x 6 环网 在直接网络中，每个结点由处理器、存储器、路由器( r o u t e r ) 和其它功能单元组成， 如图2 7 所示。路由器的主要功能是完成结点之间的消息传递。由于路由器在直接网络 中占有重要的地位，因此直接网络也称为基于路由器的网络。 f i g 2 - 7n o d es t r u c t u r eo fd i r e c t - n e t w o r k 图2 - 7 直接网络中结点的结构 虽然本地处理器就可以实现路由的功能，但在高性能计算机系统中一般都采用专用 的路由器，以便每个结点的计算和通信操作可以同时进行。路由器的一般结构如图2 8 所示，主要包括五个部分：接口通道、链路控制器、缓冲区、开关、路由及仲裁单元。 接口通道每个路由器都有几对外部通道与相邻结点的路由器相连接。每对外部通道 中的一个用作输入，另个用作输出。每个路由器还通过一对( 或多对) 内部通道与本地 的处理器相连接。每对内部通道中，输入通道通常被称为注射通道，用于将本地处理器 发出的消息注射到网络中去；输出通道则通常被称为消费通道、排除通道或递送通道， 用于将从网络中接收到的消息传送到本地处理器。 链路控制器( l c ) 用来提供相邻路由器之间的握手信号，以实现消息在物理通道上的 传输。 缓冲区用来暂时存储传输中的消息，通常吐i f i f o 存储器构成。在图2 8 所示的模型中， 每个输入通道和每个输出通道都有缓冲区。具体实现时可以只设立输入通道缓冲区或只 设立输出通道缓冲区。 8 广西大掌硕士掌位论文t o r u s 网络中处理机分配策略的研究 开关负责连接路由器的输入缓冲区和输出缓冲区。高速路由器通常采用全连接的交 叉开关，而低速路由器中的丌关不一定都是全连接的。 路由及仲裁单元用来实现路由算法，为输入通道中的消息选择一条输出通道并设置 开关。如果多个消息同时申请同一个输出通道，该部件对它们进行仲裁。 f i g 2 - 8t h es t r u c t u r eo fr o u t e 图2 8 路由器的一般结构 从路由器的性能角度来说，有两个参数是必须考虑的：路由时延( r o u t i n gd e l a y ) 和 流控制时延( f l o wc o n t r o ld e l a y ) p 2 i 。前者指的是当消息第一次到达路由器时，用来检查和 确定消息前进的输出通道所需的时间，后者指的是在路由路径建立以后，消息通过该路 由器到达相邻路由器所需的时间。流控制时延又包括两部分，即内部流控制时延和外部 流控制时延。 直接网络有很好的扩展性，而且点对点的直接通道传输速率高且易于实现，因而是 构造大规模并行计算机最流行的互连网络。从图论的角度来看，直接网络具有良好的数 学特性，因而成为人们研究的重点。 2 3 2 1 直接网络的属性【3 2 i 在设计和分析直接网络之前，先定义几个常用于描述直接网络拓扑特定的参数，这 些参数常用来估计网络复杂性、通信效率和成本。 节点度：一个节点与其相邻节点连接通道的数目。 直径：网络中两个节点之间的最大距离。 规整性：如果所有节点度都相等，那么该网络是规整的。 对称性：如果网络从每个结点看上去拓扑结构都是都一样的，则称此网络是对 称的。 直接网络主要由三个要素来描述：拓扑、路由和交换。拓扑定义各节点可以通过通 道互连。直接网络最理想的拓扑结构是全相连结构，即网络中每个节点都与其它任何节 结相连。这样在消息传递时就不需要经过中间节点，直接到达目的节点。如果网络有n 个节点，这种全相连的拓扑要求每个路由器有n 条通道( 包括一条内部通道) 。因此成本 限制了网络的规模。另外，一个节点的物理连接数目受限于硬件条件，例如可用引脚数 目和可能的连线面积等。由于这些工程和成本方面的限制，妨碍了全相连网络的应用， 即使在小型网络中也很少使用。于是人们提出了许多其它的拓扑结构，以达到更好的性 9 广西大掌硕士掌位论文t o r u s 网络中处理机分配策略的研究 能价格比。在这些拓扑结构中，消息到达目的节点之前必须经过一个或多个中间节点。 2 3 2 1 流行的直接网络拓扑 各种网络结构各有特点和优势，当在系统高性能和适当的价格之间作权衡时，具有 较好的拓扑特性( 如低结点度、小直径等) 、算法实现容易及容错特性好的网络是较合适 的选择。目前，环网和网孔等直接网络受到了广泛青睐。例如，i b mb l u e e e n e 和 e r a y t 3 d t 3 e 都使用了具有双向通道的三维环网作为数据通信网络。本文的研究工作就是 围绕以环网为代表的直接网络而展开的。 2 3 3 间接网络 l 、目j 接网络或基于开关的网络是另一类主要的互连网络。它没有提供节点间的直接连 接，任何两个节点间的通信必须通过某些交换机进行。每个节点都有一个网络适配器连 接在网络丌关上。每个开关都有一组端口，每个端口包括一条输入和一条输出链路。每 个开关的端口或者连接到处理器，或者悬空，或者连接到其它开关的端口上，以实现处 理器间的连接( 如图2 9 所示) 。这些丌关的互连方式决定了不同的网络拓扑。 通道 f i g 2 - 9t h es t r u c t u r eo f d i r e c t n e t w o r ka n dn o d eb a s e do ns w i t c h 图2 - 9 基于开关的间接网络及结点结构 与直接网络相似，间接网络的主要属性由三个要素来描述：拓扑、路由和交换。拓 扑定义了开关是如何通过通道互连的。对于具有n 个节点的网络，理想的拓扑是使用一 个n n 的开关连接它们，这种开关就是交叉开关。使用一个n n 的交叉开关比使用全连 接的直接网络拓扑要便宜，但是交叉开关的成本仍然限制了它在大型网络中的使用。与 直接网络相似，一个开关的物理连接数目受硬件条件的限制，比如引脚数目和可用的连 线面积。于是，又提出了很多其它的拓扑结构。在这些拓扑中，消息到达目的节点之前 要经过多个开关。规整网络中的开关通常都是相同的，传统上采用多级结构。除了输入 输出级既连接节点，又连接了网络中的其它级，这种网络称为多级互连网络。 2 3 4 混合网络 顾名思义，混合网络是综合了前面三种网络的优点构成的一种网络。与共享介质网 络相比，混合网络有更高的带宽和更好的扩展性；与直接网络或间接网络相比，混合网 1 0 广西大掌硕士学位论文 t o r u s 网络中处理机分配策略的研究 络结点之间的距离更短。正因为有这些优点，有许多并行机就采用了混合网络的互连模 式，例如大型机d a s h 的结点采用二维网孔结构，每个结点内部是由开关总线连接而成的 机群，这样既保持了直接互连网络的良好扩展性，同时在结点内部可以利用总线实现快 速通信。其它典型的混合网络还有多总线1 3 3 1 、超网格( h y p e r m e s h ) 3 4 1 等。在超网格中， 结点按网孔结构排列，但每一维上的结点用总线而不是通道相连。这种结构最初由 w i t t i e l 3 5 1 提出，其优点是网络直径很小，结点问的平均距离在网络规模增大时仅有q n d , 的增加，缺点是网络带宽的可扩展性差。 2 4 任务调度 2 4 1 任务调度的类型1 3 6 j 任务调度是多处理机系统中的关键问题之一，它直接影响着系统的高性能计算和用 户响应速度，因此受到国内外学者的广泛关注。 调度s 可以定义为任务空间，到处理机的运行空间p x t 的映射( p 为处理机集合，7 1 为时间) ，即： s ：， p x t 调度问题一般可以分为两大步：第一步就是在空间上对计算和数据进行分配，包括 选取给定任务所需要的资源组合，将任务交给这些资源去执行，并分配相关的数据和计 算等；第二步就是在时间上为计算和通信进行排序，包括在计算资源上为不同的任务进 行排序，同时为不同任务之间的通信进行排序。 任务的指派要求将系统中所有任务均匀地分配到处理机上以获得最大程度的并行， 从而使得运行于同一个处理机上的每个进程都能达到整个程序的最小执行时间。然而随 着进程在处理机上的分布，进程问的通信也相应增加，这就要求具有较大通信量的任务 被分配到同一个处理机或邻近处理机上。任务的指派问题通常用图嵌入或图划分的方法 近似解决【3 7 1 ，即将所有任务模型化为一个无向有权图，顶点表示任务计算量，边表示任 务之间的通信量然后考虑与处理机图的匹配。 2 4 2 多处理机任务调度 假定系统含有m 个处理机p l ，p 2 ，以，对于疗个待调度执行的多处理机任务 ，以，以， 每个任务具有一系列处理机组合的选择。对于每一可选择的处理机组合，任务还指明处 理本任务所需占用这组处理机的时间。即每一任务可用一组处理机模式一时间表来表 示：z = ( m ，t ) ，( m ：，：) ，( m 和o ) 其中每一心称为处理机模式( 它是处理机集合 p 。，p 2 ，e r a 的一个子集) ，而0 是这组处理机集合执行任务z 所花的执行时间3 8 4 引。 问题：给出一个调度，使得系统处理这些任务的时间跨度( 最后完成的时间) 最小。 广西大掌硕士学位论文t o r u s 网络中处理机分配策略的研究 根据g r a h a m 、l a w l e r 、l e n s t r a 等人使用的标准表示，这种典型调度问题记为 巴ls e t l c 一。这种记法包含了调度问题的三个部分( 用竖线隔开) ： ( i ) 系统处理机模型。处理机环境定义了处理机的数目、类型、性能等特征参数。m 个处理机的集合为p = a ，p 2 ，办 。处理机性能包括处理速度、并行加速比等。处理机 类型有单处理机、多处理机等，如果是多处理机，那么还可以描述处理机互连网络类型， 如线性( 或称数组型) 、星型、超立方体和簇型等拓扑结构。一般来说，任何处理机在任 一时刻都至多只能执行一个任务，但在执行过程中，有的处理机是可剥夺的，而有的不 是。如己表示系统有m 个独立的处理机，k 表示系统中m 个处理机以总线方式连接，m ， 则表示以网格方式互连的m 个处理机，等等。 ( i i ) 调度实例的约束，是对任务集合和处理机集合的约束条件。对于任务集合来说， 任务之间可能是相互约束的，如优先权约束、时间延迟约束等。若任务以优先于任务，：， 则引入偏序关系 2 ，。- 2 。网络中的每一个结点代表一个处 理机，每个结点用坐标( w ) 表示，o s x ( z ，u )( 3 ，u f i g 3 - 1 r ( 5 ，5 1 图3 - 1 t ( 5 ，5 ) 定义2 酬如果一个任务所需要的处理机的规模为p 。9 ，则该任务可表示为j ( 舢) ；一个子 网s 可表示为以( 叫) 玑( 州) ，其中o _ ， 埘，o s 蹦 p 一1 ，j 叮一1 ； 当f ，s 满足i p - 1 ，j g i ； 当f ，j 满足f p i ，j g i ； ( f + 珊一p + 1 ：j ) d y ( s + n - g +