并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法(已修改)
2025-06-08 17:08 本頁面
【正文】 并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法 Interconnection Networks and their Routing Algorithms for Parallel Processing Systems 劉志勇 中國科學(xué)院計(jì)算技術(shù)研究所 Zhiyong Liu Institute of Computing Technology Chinese Academy of Sciences June 16, 20xx 1, Introduction 11 The Role of Interconnection Networks Fig. 1 A Structure of A Parallel Computer System P (PE) P (M) Interconnection Network P (M) P (M) P (PE) P (PE) Space for a Designer – Cost ? Hardware Complexity ? Routing Complexity – Performance ? Diameter ? Bandwidth ? Latency ? Reliability ? Functionality Space for a Designer (Continued) – Design Choices ? Topology (Static, Dynamic, Various Topologies of Interconnection) ? Operation Mode (Synch. vs. Asynch.) ? Switch Mode (Circuit vs. Packet) ? Control Strategy (Centralized vs. Distributed) ? Routing Strategy (Route Selection, Packet Schedule) 12, Classification ? Hardware Complexity and Diameter System Switch ? Static vs Dynamic Networks )1()()( l o g)l o g()()( 2ONONONNONONO1,2/,l o g),(1 ?NNNNCSome Interconnection Networks: – Crossbar – Star – Tree – Mesh – Ring – Hypercube – Omega – Perfect Shuffle – ……… 13 Network Routing Strategy – Circuit Switch vs Packet switch – Wormhole Routing – Synchronous vs Asyncronous – Oblivious vs Adaptive – Greedy vs nonGreedy – Route Selection – Buffered Packets Schedule – Throughput – Message Delay – Complexity of the Routing Algorithm (Time? Buffer?) 2, Communication Patterns – Gathering – Broadcast – Permutations – One to One – One to Many – Many to One – Many to Many 3, Hypercubes ? Hardware Complexity O(N*logN) ? Diameter n (=logN) ? Descending and Ascending Routing 2D 3D 4D – FOR j=n1 DOWNTO 0 DO – IF d[j]s[j] – THEN send packet along dimension j。 021021dddDsssSnnnn????????100 101 110 101 101 100 110 010 111 111 000 011 001 111 010 001 001 011 000 101 101 100 100 100 110 110 110 010 111 000 011 111 001 010 001 011 000 000 011 010 Naive Routing 4, Conflicts in Routing Process ? Conflicts on nodes ? Conflicts on links ? Conflicts ? Buffer necessary ? Schedule process ? Longer time in a “step” 000 111 001 011 010 101 011 001 101 100 100 110 110 010 111 000 000 001 011 010 010 011 001 000 101 100 101 100 110 110 111 111 000 000 001 001 010 010 011 011 101 110 100 110 100 010 111 111 000 001 001 000 010 011 011 010 101 110 111 100 110 100 101 111 Dimension 2 Dimension 0 Dimension 1 N5, Conflictfree Routing ? TwoStage Routing – Rearrange the packets ? Detour Routing – Find circles
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1