并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法(完整版)
【正文】 01 1101 1100 1100 1101 1100 1101 1001 1111 1111 1110 1110 1111 Step 4 Step 3 Step 2 Step 1 (b) The Dimensions Used in Each Step (a) The Transmission Process ExCirRouting Process ?Feature of the routing algorithm –Two types of transmission: Exchange and Circling –Preputation plexity (bitlevel) : O(n3)Sequential, O(n2)Parallel –Distributed routing –Only an XOR operation is needed in each step –Conflictfree –Every packet will reach its destination in at most n steps ?Proof of the Conflictfree feature –Modification of the Transformation matrices in the Algorithm Detourfinding can proceed in each step (keeping the transformation matrices nonsingular) –Wellformed loops are generated when need to circling –An LCpermutation is generated in each step so that the routing can proceed 53, Set up N Independent Paths for LC ? Circuit Switch/Wormhole Routing Mode ? Set up N independent paths simultaneously for an LCPermutation ? Routing Strategy – Find an appropriate order for the use of the n dimensions Algorithm Sequencing。 rk=ek。 END。39。 /* Modify R using Equation . */ ELSE Find b such that bk and tk,b=1。 END。 3 aux:=n。 23 /* Modify R according to Equation . */ 24 END。39。 /* Modify T according to R. */ 26 IF aux=n 27 THEN 28 Pick up an unselected dimension b。 7 Selected:=Selected+{k}。39。 rb=rb⊕ rk⊕ ek。 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)。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 cardi
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1