并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法-文庫吧
2025-04-24 17:08 本頁面
【正文】 ? Rearrangement for the Use of the Dimensions – Order the routing dimensions accordingly 51, TwoStage Routing for BPCPermutations ? BPCPermutations A BPC permutation of N numbers can be defined by an ntuple F=(f’n1, f’n2, …, f’0), where (f’n1, f’n2, …, f’0) is a permutation of (n1, n2, …, 0), and fi=|f’i| for 0≤ i≤ n1, such that ????????.0,039。39。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。 BEGIN /* The nodes do the following in parallel. */ FOR j:=0 TO n2 DO IF (j is not in TOPSET) and (dj=1) THEN send the packet to IMG(j)(S)。 END。 – Note: Top set is known for a type of permutations ? An Example: Bitreversal with every bit being plemented – F=(0, 1, 2), – Cycles: (2, 0), (1) – Top Set: {2, 1} 000 100 101 110 111 001 011 111 010 101 001 011 001 101 101 101 101 100 100 100 100 110 110 110 110 010 010 010 111 111 111 000 000 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 011 000 000 011 010 (a) BPCPartition (b) Naive Routing ? Feature of the routing algorithm – TwoStage Routing – No (or very little) preputation – Distributed routing – Only an XOR operation is needed in each step – Conflictfree ? Proof of the Conflictfree feature – First the BPCPartition routing is conf
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1