InfiniBand高速网络互连技术45625PPT课件

.,1,InfiniBand高速网络互连技术,清风明月2012年5月,.,2,内容提要,超级计算机系统及其互连结构Infiniband互连网络的体系结构在HPC中的典型互连架构及应用IB网络优化技术未来展望,Lecture1,Lecture2,.,3,内容提要,超级计算机系统及其互连结构Infiniband互连网络的体系结构在HPC中的典型互连架构及应用IB网络优化技术未来展望,.,4,国际超级计算机500强排名(TOP500),是美国田纳西大学、伯克利NERSC实验室和德国曼海姆大学一些专家为评价世界超级计算机性能而搞的民间学术活动，每年2次排出世界上实际运行速度最快的前500台计算机。(6月、11月)排名的依据是线性代数软件包Linpack的实际测试数据，而峰值浮点运算速度作为参考值列出。Linpack基准测试程序是一个可以分解和解答线性方程和线性最小平方问题的Fortran子程序集.于20世纪70年代到80年代初为超级计算机而设计测试出的最高性能指标作为衡量机器性能的标准,.,5,TOP500分析,中国TOP100总Linpack性能达到11.85Pflops(2010年6.3PFlops)，是2010年的1.88倍;跟全球TOP500相比，2011年6月全球TOP500排行榜第一名被日本的K-Computer夺得，2010年11月TOP500第一名的天河1A降为世界第二，但中国的机器份额首次取得第二名,仅次于美国;国家超级计算天津中心以国防科大天河1A再次蝉联中国TOP100第一名，Linpack性能2.57PFlops，峰值4.7PFlops;国家超级计算济南中心以国家并行计算机工程技术研究中心全国产神威蓝光力夺得中国TOP100第二名，Linpack性能795.9TFlops，峰值1.07PFlops，神威蓝光是我国历史上首台全国产的千万亿次超级计算机;国家超级计算长沙中心以国防科大天河1A-HN力夺中国TOP100第三名，Linpack性能771.7TFlops，峰值1.34PFlops。全部机器的Linpack性能超过22.1Tflops是2010年9.6TFlops的2.3倍,比去年的1.41倍大幅提升。全部系统的峰值超过25.6TFlops，是2010年11TFlops的2.33倍，比去年的1.36倍大幅提升;排名前三的机器两套是CPU+GPU异构MPP;97个(2010年98个)系统都是机群架构，机群继续占据主导地位，在前10名里4台是CPU+GPU体系架构，在TOP100中共有13套CPU+GPU异构机群。,.,6,近3年来的TOP5超级计算机系统,.,7,No1:KComputer,日本理化研究所(RIKEN)高级计算科学研究院(AICS)和富士通共同研制每秒运算速度超越1亿亿次大关。Linpack测试的最大计算性能达到了10.51PFlops，也就是每秒钟1.051亿亿次浮点计算，这也是人类首次跨越1亿亿次计算大关。采用的处理器是富士通制造的SPARC64VIIIfx，八核心，主频2.0GHz，二级缓存6MB，热设计功耗58W，峰值浮点性能128GFlops。为了获得更高性能，富士通还在其中加入了一系列高性能集群计算扩展，可以有效管理其共享二级缓存，并支持SIMD、每核心256位浮点寄存器、高级核心间硬件同步等等。处理器数量是88128颗，核心数量为705024个，占据864个机柜。这些处理器通过名为“豆腐”(Tofu)的特殊6-Dmesh/torus网络连接在一起，带宽5GB/s。同时，“京”的峰值计算性能也达到了11.28PFlops，执行效率为惊人的93.2%,ASCISpringschool2012,.,8,KComputer:10.51Petaflop/sonLinpack705024SPARC64cores(8perdie;45nm)(Fujitsudesign)Tofuinterconnect(6-Dtorus)12.7MegaWatt,.,9,KComputer的互连架构,6D-mesh/Tours,.,10,.,11,No2：天河-1A，国防科技大学,这是超过美国橡树岭国家实验室产品高达40的系统。达到每秒万亿次的峰值性能和每秒万亿次的实测性能。14336颗英特尔六核至强X56702.93GHzCPU、7168颗NvidiaTeslaM2050GPU，以及2048颗自主研发的八核飞腾FT-1000处理器天河一号A将大规模并行GPU与多核CPU相结合，在性能、尺寸以及功耗等方面均取得了巨大进步，是当代异构计算的典型代表。该系统采用了7168颗英伟达（NVIDIA）TeslaM2050GPU以及14,336颗CPU。如果单纯只使用CPU的话，要实现同等性能则需要50,000颗以上的CPU以及两倍的占地面积。更重要的是，如果完全采用CPU打造，可实现2.507Petaflops（千万亿次）性能的系统将消耗1200万瓦特的电力。多亏在异构计算环境中运用了GPU，天河一号A仅消耗404万瓦特的电力，节能效果高达3倍。二者之间的功耗之差足够满足5000多户居民一年的电力所需。,.,12,.,13,三大突破,“天河一号”除了使用了英特尔处理器，还首次在超级计算机中使用了2048个我国自主设计的处理器。这款名为“飞腾-1000”的64位CPU。它利用65纳米技术设计生产，共有8个核心。中国首创了CPU和GPU融合并行的体系结构。制造了先进的通信芯片，设计了先进的互联结构。160Gb/s，是国际上的商用IB的两倍。,.,14,TH-1A互连架构,超级胖树结构,.,15,NO.3Jaguar美洲虎,2.331PflopsCrayXT5-HEOpteronSixCore2.6GHz,近25万个内核,.,16,美洲虎的3D-Torus,.,17,.,18,CRAY超级计算机的Roadmap,CrayXT5:1+PFLeadership-classsystemforscience,DARPAHPCS:20PFLeadership-classsystem,FY2009,FY2011,FY2015,FY2018,Futuresystem:1EF,100250PF,美洲虎,.,19,NO.4曙光“星云”,2.9843Pflops,Infiniband互连,.,20,No14:神威蓝光：全国产化的超级计算机问世,该机器获得科技部863计划支持，由国家并行计算机工程技术研究中心制造，于2011年9月安装于国家超算济南中心，全部采用自主设计生产的CPU(ShenWeiprocessorSW1600)，系统共8704个CPU，峰值1.07016PFlops，持续性能795.9TFlops，Linpack效率74.37%，总功耗1074KW。国家超级计算济南中心是科技部批准成立的全国3个千万亿次超级计算中心之一，由山东省科学院计算中心负责建设、管理和运营。是国内首台全部采用国产中央处理器（CPU）和系统软件构建的千万亿次计算机系统，标志着我国成为继美国、日本之后第三个能够采用自主CPU构建千万亿次计算机的国家。,.,21,.,22,.,23,神威蓝光拥有四大特点：,全部采用国产的CPULinpack效率高达74.4%，而一般的千万亿次机都在50%左右采用液冷技术，节能高密度，在一个机仓（机柜）里可以装入1024颗CPU，千万亿次规模仅需要9个这样的机仓。,.,24,计算机节点，在1U高的机箱中可以放入4个CPU板，每个板上可以装两颗16核的CPU。,这就是神威蓝光的“心脏”：申威1600实物照,在计算节点中采用液冷（据说是使用500元1吨的纯净水）设计也是神威蓝光的一大技术特色，中间是铝制液冷散热板。,.,25,国内三大系统比较,.,26,Opteronsocket,Roadrunner（走鹃）Part1:OpteronBlades,Opteroncore,Opteroncore,1.8GHz3.6Gflop/s64+64KBL1cache2MBL2cache,.,27,LS21Blade,Roadrunner（走鹃）Part1:OpteronBlades,8GBDDR2memory,8GBDDR2memory,.,28,Roadrunner（走鹃）Part1:OpteronBlades,.,29,RoadrunnerArchitecturePart2:CellBlades,.,30,RoadrunnerArchitecturePart2:CellBlades,.,31,RoadrunnerArchitecturePart3:Nodes（Triblade=1*Opteron+2*cell）,.,32,RoadrunnerArchitecturePart4:ScalingOut,BladeCenter,BladeCenter,BladeCenter,BladeCenter,.,33,ComputeUnit(CU),RoadrunnerArchitecturePart4:ScalingOut,.,34,RoadrunnerArchitecturePart4:ScalingOut,.,35,RoadrunnerArchitecture,.,36,IBM计划10万万亿次HPC12倍于世界最快！,今年预计BlueGene/Q“Sequoia”其峰值性能可达到20petaflops，而其升级版将是首个超过10万万亿次浮点计算的超级计算机，达到107petaflops，是目前世界最快KComputer的12倍。,.,37,Sequoia（红杉）,Sequoia超级计算机是IBM正在为LawrenceLivermore国家实验室研制的一种超级计算机，而这种计算机中使用的BlueGene/Q处理器就将采用IBM在HotChips大会上发表的论文中披露的这种新部件。Sequoia将在2012年完工，有望提供20petaFLOPs（peta1015）的强大性能。当Sequoia完工时，这台超级计算机可能成为世界上功能最强大的系统之一。,.,38,计算机技术的发展,自1946年以来，计算机近70年有了惊人的发展性能：（加法）速度提高了5个数量级计算机性能以大约每年35%的速度提高价格：今天$1000的机器相当于60年代中$106的机器，这里同性能计算机的价格比，改善了个数量级。,.,39,处理器速度持续提高（广度）,从1971年第一颗微处理器Intel4004问世以来，40年间处理器芯片集成的晶体管数目从2300个发展到今天的数十亿个，处理器频率从不到1MHz发展到今天最高接近5GHz，与英特尔4004相比，如今下一代英特尔酷睿处理器的性能是其35万倍，每个晶体管的能耗却降低了5千倍。同期，晶体管的价格下降了约5万倍。,.,40,.,41,在30年间计算机系统的速度提高了6个数量级,.,42,对计算能力的需求持续增长,.,43,.,44,.,45,超级计算机的性能趋势,CAGR=1.9,1stPasadenaPetaflopsWorkshop,GFlops,ExaFlops,PetaFlops,TeraFlops,FigurecourtesyofPeterKogge,.,46,.,47,超级计算机发展路线图,2010,2020,2030,2050,.,48,.,49,.,50,TOP500中的互连网络统计,TOP500Nov2011，IB占42%TOP10中有5家采用IB(4/5/7/9/10)TOP20中有8家TOP100中有55%采用IB基于GPU混合系统中有92%采用IB,.,51,TOP100中的IO互连架构统计,在TOP100机器的IO互连中55%采用IB,.,52,Top500中各种互连的趋势图,.,53,典型商业互连网络的性价比,.,54,Top500中IB互连的趋势图,.,55,内容提要,超级计算机系统及其互连结构Infiniband互连网络的体系结构在HPC中的典型互连架构及应用IB网络优化技术未来展望,.,56,为什么TOP500中有42%机器采用IB互连？,高带宽目前主流的单链路传输能力40Gbps，10GB以太网不可比拟超低延时应用程序之间通信延时小于1us高可靠性、低误码率、自管理的网络链路级流控拥塞控制,.,57,IB网络组成,HostChannelAdapters(HCA)TargetChannelAdapters(TCA)SwitchesRouters,.,58,IB网络组成,多个子网，每个子网是一个独立的路由域子网之间通过交换机互连，一般的HPC只使用一个子网。,.,59,IB网络硬件实体,.,60,IB网络硬件实体,Blade/RackServers,Storage,Switch,SWITCH,.,61,基于IB网络构建的Cluster系统,.,62,CA（端结点-主机适配卡）,两种类型的CAHCA，通过IBverbs为用户提供操作TCA，IBA未定义TCA接口语义CA是一个具备一定保护功能的可编程DMA引擎,VirtualLane(VL),LocalID(LID),独立的发送和接收缓冲区,内存翻译和保护,子网管理代理,GUID,.,63,IB交换机（多端口交换）,子网内部路由设备交换机端口具备LID，具有HCA特性。子网内部的每个端口分配一个或多个唯一的LID通过报文LocalRouteHeader标识目标端口LID，交换机根据该地址信息交换到目标端口提供单播和多播路由支持多路径（负载均衡，链路容错）,.,64,IB传输分层（对比TCP/IP）,.,65,.,66,PhysicalLayerLinkRate,InfiniBand使用串行差分链路传输链路宽度1xOnedifferentialpairperTx/Rx4xFourdifferentialpairsperTx/Rx8xEightdifferentialpairsperTx/Rx12x-TwelvedifferentialpairsperTxandperRx链路速度SingleDataRate(SDR)-2.5Gb/sperlane(10Gb/sfor4x)DoubleDataRate(DDR)-5Gb/sperlane(20Gb/sfor4x)QuadDataRate(QDR)-10Gb/sperlane(40Gb/sfor4x)FourteenDataRate(FDR)-14Gb/sperlane(56Gb/sfor4x)EnhancedDatarate(EDR)-25Gb/sperlane(100Gb/sfor4x)目前多采用4X链路,.,67,PhysicalLayerlinkwidth,Lane的概念，1x即1lane，类似于PCIElane,1xLink,4xLink,12xLink,.,68,IB物理链路速率历程,串行高带宽链路SDR:10Gb/sHCAlinksDDR:20Gb/sHCAlinksQDR:40Gb/sHCAlinksFDR:56Gb/sHCAlinksEDR:100Gb/sHCAlinks,.,69,PhysicalLayerCables&Connectors,.,70,单个物理信道上复用多个虚拟链路信道,.,71,LinkLayerProtocol,Message长度最大2GbyteMTU尺寸从256byte到最大4Kbyte,.,72,LinkLayerAddressing,每个节点（HCA端节点和交换机）必须拥有一个全局唯一的64位ID（GUID），类似于以太网MAC地址。同时，为了方便路由，在每个子网内为节点分配一个本地ID(LID)-16bits，子网内线性编号,GUID,GUID,GUID,GUID,GUID,GUID,GUID,GUID,LID=1,LID=2,LID=3,LID=4,LID=5,LID=6,LID=7,LID=8,.,73,IB通信协议的硬件实现原理,.,74,TransportLayerUsingQueuePairs,发送和接收队列是成对出现的。,.,75,TransportLayer队列模型,.,76,IB通信传输示例,.,77,LinkLayerFlowControl,基于信用（Credit）的链路级流控反压原理,.,78,TransportLayerServicesProperties,可靠与不可靠面向连接与数据报（非面向连接）,.,79,服务分类,.,80,.,81,如何管理子网？,IB网络维持一个子网管理器SubnetManager(SM)是一个独立软件通过与每个节点上的子网管理代理通信的方式来管理子网,.,82,子网管理和路由,每个子网必须有一个子网管理器子网管理器的作用：管理IB网络中的所有节点，包括端节点HCA和交换机SW子网网络拓扑发现为每个节点分配一个本地ID（LID），用于路由为交换机分配转发表，用于网络路由监控子网状态，当网络发生改变时负责重新分配路由表。维护网络正常运转,.,83,子网管理器SM,SM是IB网络中一个重要元素负责配置和管理交换机、路由器、HCA。SM可以被实现在HCA或者交换机等设备上。一个子网内可以有多个SM，其中一个SM为主，其余为备份SM功能进行子网拓扑发现产生子网前缀，为端口分配LID配置每个交换的LID，配置转发表提供节点和服务的数据库服务,.,84,.,85,.,86,子网管理基础子网管理器（1）,相对于以太网的分布式管理，在Infiniband网络中，SM通过SMA对子网进行集中管理。这种方式结构简单易于管理。为了防止单点失效问题，在Infiniband中可存在多个SM，一个主SM，多个备份SM。备份SM检测到主SM死亡时，会选择一个备份SM成为主SM，接管子网管理权。,.,87,子网管理基础子网管理器（2）,.,88,主SM是IB子网初始化和配置的关键因素。主SM的选择也是初始化过程的一部分。主SM的主要作用是：发现子网的物理拓扑结构。为每个端节点，交换机和路由器分配本地标识符LID。确定各端节点之间的合理路径。扫描子网，发现拓扑改变处理节点加入和节点删除。,子网管理基础子网管理器（3）,.,89,子网探测主要是指在Infiniband子网初始化时，SM通过SMA获得子网内各节点信息。主要的信息就是各个节点的GUID，节点类型，端口信息以及各节点之间的连接关系。在子网初始化完毕后，SM还会定时的检查网络拓扑是否发生变化（某个交换机端口的状态发生改变）。交换机检测到自己的某个端口状态发生改变，可以通过Trap机制主动向SM报告拓扑改变。,子网探测,.,90,子网发现的过程：子网启动时，SM发送包含Get方法的直接路由SMP，SMA收到后会响应一个SMP，从而找到一个新的节点，然后SM通过这个新节点向外辐射只到找到所有的设备。,子网探测子网发现,.,91,对于一个已经初始化的子网，如果SM发现某一个交换机的一个端口的状态从DOWN变为UP，则说明有设备加入到子网中。,子网探测增加设备,.,92,对于一个已经初始化的子网，如果SM发现某一个交换机的一个端口的状态从UP变为DOWN，则说明有设备从子网中移除。,子网探测删除设备,.,93,在规范中，并没有规定LID的分配规则，只要满足上述的性质即可。具体实现时，LID的分配与特定的路由算法有关。最简单的分配方式是按照设备的发现顺序，从1开始连续分配。,LID分配,.,94,路由计算主要是指SM在得到子网拓扑以后，确定每两个节点之间的路径的过程。SM将这个计算结果以转发表的形式发布给交换机，使数据包沿着计算好的路径传递。转发表是一个LID,PORT组成的表，交换机接收到一个LID路由的数据包时，通过查找目的LID对应的表项，从而确定应该从那个端口转发这个数据包。,路由计算,.,95,网络拓扑发现过程,由子网管理器（SM）发起从SM软件驻留的节点开始，按照宽度优先（BFS）、或深度优先（DFS）方法逐个发现，将发现好的节点加入拓扑链表中在进行子网发现的过程中，为每个已发现的节点分配一个本地ID（LID），为后继的路由做准备,.,96,网络拓扑发现过程,LID=1,LID=2,LID=3,LID=4,LID=5,LID=6,LID=7,LID=8,.,97,IB网络路由过程交换机内部转发机制,LFT：LineralForwardTable（线性转发表）首先，根据报文头的SL查找SL-to-VL-Table（服务等级映射表），获得该报文的转发的VL通道。而后，根据目的DLID查找LFT线性转发表，获取下一跳的端口号。,.,98,IB网络路由过程寻径过程,SW2,cn0,cn1,cn2,cn3,LID=2,LID=3,LID=4,LID=5,LID=6,1,2,3,4,1,2,3,4,SW1线性转发表,SW2线性转发表,LID=1,SW1,查表,查表,SM,.,99,路由节点的添加和删除,子网管理器SM发现拓扑变化主动发现，通过子网扫描被动发现，节点的代理软件主动上报自己的故障端口当拓扑发生改变时，更新路由表,.,100,IB网络路由更新过程（1）,SW2,cn0,cn1,cn2,cn3,LID=2,LID=3,LID=4,LID=5,LID=6,1,2,3,4,1,2,3,4,SW1线性转发表,SW2线性转发表,LID=1,SW1,SM,链路故障报告,.,101,IB网络路由更新过程（2）,SW2,cn0,cn1,cn2,cn3,LID=2,LID=3,LID=4,LID=5,LID=6,1,2,3,4,1,2,3,4,SW1线性转发表,SW2线性转发表,LID=1,SW1,SM,更新转发表,.,102,IB分层协议栈,由OpenFabric组织制定IB规范,Common,InfiniBand,iWARP,Key,InfiniBandHCA,iWARPR-NIC,HardwareSpecificDriver,HardwareSpecificDriver,ConnectionManager,MAD,InfiniBandVerbs/API,SAClient,ConnectionManager,ConnectionManagerAbstraction(CMA),UserLevelVerbs/API,SDP,IPoIB,SRP,iSER,RDS,UDAPL,SDPLibrary,UserLevelMADAPI,OpenSM,DiagTools,Hardware,Provider,Mid-Layer,UpperLayerProtocol,UserAPIs,KernelSpace,UserSpace,NFS-RDMARPC,ClusterFileSys,ApplicationLevel,SMA,R-NICDriverAPI,ClusteredDBAccess(Oracle10gRAC),SocketsBasedAccess(IBMDB2),VariousMPIs,AccesstoFileSystems,BlockStorageAccess,IPBasedAppAccess,Apps&AccessMethodsforusingOFStack,.,103,IB分层协议栈,Applications,User,Kernel,WSDSANProvider,ManagementTools,VNIC*,.,104,SocketsDirectProtocol(SDP)&ReliableDatagramSockets(RDS),HostChannelAdapter,OpenIBAccessLayer,IPoIB,IP,Oracle10g,SocketApplications,TCP,UDP,SDP,RDS,Kernel,User,UDPApplications,.,105,IPoIB,.,106,IPoIBPacketFormat,.,107,IPoIB子网视图,每个端结点HCA的每个IB端口都分配一个独立的IP地址，支持IPv4/v6地址格式结点间通信，可使用IP地址标识,.,108,FCoIB,IB网到FC网之间采用透明网桥,.,109,FCoverIBGatewayModel,PhysicalView:,HandlinginitiatorsloginsActsasanNPIVN_PortReflectsF_LOGIasF_DISC,.,110,FCoIBGatewayStatelessPacketRelay,IBtoFCStripIBheadersPayloadcontainsentireFCframe,FCtoIBD_IDlookuptoretrieveaddressingLID,QPN,etc.EncapsulateFCframeasUDpayload,FCFrame,.,111,内容提要,超级计算机系统及其互连结构Infiniband互连网络的体系结构在HPC中的典型互连架构及应用IB网络优化技术未来展望,.,112,典型的IB交换机实现结构（1）,9xFabricBoards(singleanddoubledense),2xFanUnits,6xPowerSupplies,2xManagementBoards,18xLineBoards,.,113,典型的IB交换机实现结构（2）,两级胖树结构或者“折叠的clos网络”,.,114,IB网络拓扑,TopologiesthataremainlyinuseforlargeclustersFat-Tree3DTorusMash,.,115,IB网络拓扑,3DTorusAnoversubscribednetwork,easiertoscaleFitmoreapplicationswithlocality,.,116,IB网络拓扑,Fat-tree(alsoknownasCBB)Flatnetwork,canbesetasoversubscribednetworkornotInotherwords,blockingornonblockingTypicallythelowestlatencynetwork,.,117,胖树结构是互连已知硬件数量的一种通用方法。胖树相对传统树，越靠近根部带宽越大。如果要使网络是非阻塞的，每层的总带宽都要相同。,胖树结构,.,118,常用的IB网络拓扑结构,利用多个“IB交换机”构造大规模IB网络每个IB交换机内部是胖树结构,.,119,64NodeClusterusingbladesandShark-GTs,.,120,972NodeFullCBBusingShark/Orca(max11,664),.,121,CoreFabric,8xSFSTS740288portseach,Edge,256xTS12024-portseach,18ComputeNodes),18ComputeNodes),8192Processor60TFlopSuperCluster,2048uplinks(7m/10m/15m/20m),.,122,RealDeploymentsToday:WallStreetBankwith512NodeGrid,SAN,LAN,296-portTS-270,2324-portTS-120,512ServerNodes,2TS-360w/EthernetandFibreChannelGateways,CoreFabric,EdgeFabric,GRIDI/O,ExistingNetworks,FibreChannelandGigEconnectivitybuiltseamlesslyintothecluster,.,123,NCSANationalCenterforSupercomputingApplications,CoreFabric,EdgeFabric,ParallelMPIcodesforcommercialclientsPointtopoint5.2usMPIlatency,.,124,1,066NodeSuperComputer,FaultTolerantCoreFabric,EdgeFabric,1296-portTS-270,8924-portTS-120,1,0685m/7m/10m/15muplinkcables,1,0661mcables,12ComputeNodes,12ComputeNodes,1,066FullyNon-BlockingFaultTolerantIBCluster,.,125,当前的网络存储技术,New,.,126,典型IO互联架构,SAN,ServerFabric,LAN/WAN,ServerCluster,FibreChanneltoInfiniBandgatewayforstorageaccess,EthernettoInfiniBandgatewayforLANaccess,SingleInfiniBandlinkfor:-Storage-Network,.,127,SAN/NAS存储结构,S,A,N,NAS,NAS,NAS,tape,.,128,数据中心的IO加速,.,129,内容提要,超级计算机系统及其互连结构Infiniband互连网络的体系结构在HPC中的典型互连架构及应用IB网络优化技术未来展望,.,130,有效的IB通信优化方法,GPUDirect,CORE-Direct,Offloading,CongestionControl,AdaptiveRouting,Management,MessagingAccelerations,AdvancedAuto-negotiation,MPI,.,131,IB网络中典型的MPI通信性能,.,132,IB网络路由和拥塞控制,通过子网管理器SM（软件）集中管理每个节点（host和switch）驻留管理代理SMA，与SM交换信息，实现路由和拥塞控制功能,.,133,路由算法,寻径过程，为两个机器之间选择一条通信路径。目标：最小代价(最小跳步数)无死锁、活锁平衡网络流量负载避免拥塞，避免通信“热点”竞争,.,134,网络拓扑,规则网络网络具有规则的拓扑图结构(ring,meshes,Fat-tree，hypercube,etc)易于优化不规则网络不规则的网络图形状拓扑发现比较关键需要精心设计路由算法，保证无死锁,.,135,路由算法的分类：oblivious和adaptive,Oblivious（确定性路由）为每个源和目的对分配一个路由，而不考虑网络流量。这种路由具有一定的吸引力attractive，因为其路由可以事先计算出来，尽管计算的代价可能很高。Adaptive（自适应路由）力图根据当前流量来调节节点间的路由。这种路由能够对全局网络的通信状况迅速作出反应，并实时改变路径以达到流量均衡的目的，通常会使用快速但并非最优化的算法来实现。,.,136,IB网络路由,IB网络路由是确定性路由（oblivious）因为IB网络使用基于目标LID的路由转发表在网络构建之初已经形成，转发表是线性的:目的地的LID号下一跳输出端口任意网络上的确定性路由（oblivious）的最优化问题是NP-hard问题oblivious路由算法通常是保守的，即不需要监控网络实时状态，可采用完