并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法(存儲(chǔ)版)
【正文】 – 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。 /* Find a detour dimension for each dimension. */ /* T, R: transformation matrices, R=T1. rk: the kth row of R. ek: the kth row of the identity matrix. detour[n1:0]: the detour array. */ BEGIN FOR k:=n1 DOWNTO 0 DO IF tk,k=1 THEN detour[k]=n。 Algorithm ExCirRouting。 dimension. This is only used for modifying the transformation matrices, and for the proof of the correctness of the routing algorithm, it has nothing to do with the real routing process. */ 0 BEGIN 1 k:=n1。 21 raux :=rauxrkek。 33 END。 31 k:=b。 13 rk:=ek。 /* T, R: transformation matrices, where R=T1. Selected: the set of dimensions selected so far. Seq[1:n]: an array for the ordered sequence. aux: a variable used to record the ``imaginary39。 /* Modify R using . */ T:=R1。 – 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 conflictfree – The second, the intermediate distribution is really a permutation – The third, the intermediate permutation satisfies the passable condition ? Realize n permutations simultaneously without conflict – The links are used efficiently, no lazy time – Network throughput is increased to its full extent 52, Detour Routing for LCPermutations ? Linear Permutations: A linear permutation is a permutation that any de
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1