并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法-全文預(yù)覽
【正文】 – 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。ififi fifs fifsdii Note that we distinguish +0 and –0 here, and we consider –00 in the above definition, the same as in [Nas81]. ? 3tuple F=(0, 1, 2), , , and . The message on node 6 (110) is to be sent to node 5 (101) . 02 sd ? 11 sd ? 20 sd ?? Cycle representation for BPCPermutations – Cycles: – Top Dimension: – Top Set: The set of all the top dimensions. – Perfect Shuffle: F=(f4, f3, f2, f1, f0)=(3, 2, 1, 0, 4) ? One Cycle: (3, 2, 1, 0, 4) ? Top Set: {4} – Bitreversal: F=(f4, f3, f2, f1, f0)=(0, 1, 2, 3, 4) ? Three Cycles: (0, 4), (1, 3), (2) ? Top Set: {4, 3, 2} ? Complete Residue System: A Complete Residue System modulo m (CRS mod m) is a set of integers which contains exactly one representative of each residue class modulo m. ? Virtual Modular Operation VMOD: Where i∈ {0,1,… ,n1}{k1,k2,…, kl}, 0≤ k1,k2,…,kl≤ n1, α i=||{k|(k∈ {k1,k2,…,kl})∧ (ki)}|| , and ||S|| is the cardinality of set S. ? ??? ,2)(),( 21 il iikkk bBV M O D ??? Passable Condition: A permutation is passable in n steps without conflict by the naive routing algorithm in a high to low order if and only if : for any k such that 0≤ k≤ n1, { VMOD(k)(D)} constitute a CRS mod 2nk . ? Routing Strategy: (TwoStageRouting) – Rearrange the Permutation into a passable permutation – Realize the passable permutation using the Ascending/Descending routing ? Rearrangement: Algorithm BPCPartition。={(S,D C)|0≤S,D,C≤N1}, where P={(S,D)|0≤S,D≤N1} is a linear permutation. ? Transformation Matrices: T , and ? A “Type” of LCPermutations: with the same T ? C does not have effect on the routing process with respect to conflict avoidance 1??TR?? Routing Strategy: – Detour instead of buffering – Go around – Two dimensions being used cooperatively so that circles are generated ? Generate a vector of detour dimensions for each dimension ? Detour Routing: Circulation or Exchange ???????????????0010000110001100T???????????????0010001110000100R D=T S⊕ (0000). S: 0, 1, 2, 3,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1