并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法-wenkub
2023-05-26 17:08:46 本頁(yè)面
【正文】 01 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 ? 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。 – 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 destination address of a message can be expressed as Dτ =T Sτ , where D is the destination, S is the source (in binary representation of n bits), and T is a n n nonsingular matrix. ? LCPermutations: A permutation is a linearplement (LC) permutation if and only if it can be expressed as P39。 /* Modify R using Equation . */ ELSE Find b such that bk and tk,b=1。 /* Modify R using . */ T:=R1。 END。 /* T, R: transformation matrices, where R=T1. Selected: the set of dimensions selected so far. Seq[1:n]: an array for the ordered
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1