并行处理系统中的互连网络及其路由算法(编辑修改稿)

并行处理系统中的互连网络及其路由算法(编辑修改稿)内容摘要：

lictfree – 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。 ={(S,D C)|0≤S,D,C≤N1}, where P={(S,D)|0≤S,D≤N1} is a linear permutation. • Transformation Matrices: T , and • A “Type” of LCPermutations: with the same T • C does not have effect on the routing process with respect to conflict avoidance 1TR• Routing Strategy: – Detour instead of buffering – Go around – Two dimensions being used cooperatively so that circles are generated • Generate a vector of detour dimensions for each dimension • Detour Routing: Circulation or Exchange 0010000110001100T0010001110000100R D=T S⊕ (0000). S: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 D: 0, 12, 8, 4, 1, 13, 9, 5, 2, 14, 10, 6, 3, 15, 11, 7 Algorithm DetourFinding。 /* 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。 rk=ek。 /* Modify R using Equation . */ ELSE Find b such that bk and tk,b=1。 detour[k]=b。 rb=rb⊕ rk⊕ ek。 rk=ek。 /* Modify R using . */ T:=R1。 /* Modify T according to R. */ END。 Algorithm ExCirRouting。 BEGIN。