并行處理系統(tǒng)中的互連網(wǎng)絡(luò)及其路由算法-資料下載頁(yè)
2025-05-19 17:08本頁(yè)面
【導(dǎo)讀】,f’0),where(f’n-1,f’n-2,…
【正文】 IF tk,k=1 9 THEN 10 BEGIN 11 IF k=aux 12 THEN aux:=n。 13 rk:=ek。 14 /* Modify R according to Equation . */ 15 END 16 ELSE 17 BEGIN 18 IF aux=n 19 THEN 20 Find a such that tk,a=1, and aux:=a。 21 raux :=rauxrkek。 22 rk:=ek。 23 /* Modify R according to Equation . */ 24 END。 25 T:=R1。 /* Modify T according to R. */ 26 IF aux=n 27 THEN 28 Pick up an unselected dimension b。 29 ELSE 30 Find b such that tb,a=1。 31 k:=b。 32 END。 33 END。 ? Routing: ``FOR k:=1 TO n DO IF dSeq[k]≠ sSeq[k], THEN send the packet along dimension Seq[k].39。39。. 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1100 1101 1010 1011 1110 1111 0000 1100 1000 0100 1101 0001 1001 0101 0010 1110 1010 0110 0011 1111 1011 0111 0001 0001 1100 1100 1100 1000 1000 0100 0100 0100 1101 1001 1001 1001 1001 0110 0101 0010 0010 1110 1110 1110 0110 0110 0011 0011 0011 0011 1111 1011 0111 1011 Routing for D=(T S)⊕ (0000) ?An Example: D=(T S)⊕ (0000) ?Sequence (3, 1, 2, 0) ?Feature of the routing algorithm –Circuit switch or wormhole routing –The order of the use of the n dimensions for a type of permutations –Preputation plexity (bitlevel) : O(n3)Sequential, O(n2)Parallel –Distributed routing –Only an XOR operation is needed in each intermediate node –N independent (shortest) paths (no conflict) are setup simultaneously ?Proof of the Conflictfree feature –Modification of the Transformation matrices in the Algorithm Sequencing is valid, (existence of aux an b in each step, keeping the transformation matrices nonsingular) –In the routing process, if two packets meet on any node S, they can never meet on any neighbor node of S –All the packets reach their destinations in one pass 6, Conclusions ? Conflicts in routing make munication not efficient – buffer – schedule process ? Frequently used permutations need highly efficient routing ? Three Routing Strategies have been developed – Conflictfree – Preputations are simple (with low plexity of putation) – Preputations can be carried out offline – Preputation each for a type of permutations – Routing process is fast: one xor operation each step – Routing process is totally distributed ? Further Research Directions – New topological structure of works – Communication requirements for new application algorithms – A particular problem of distance3 permutation routing Thank You!
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1