High performance array processor with nonlinear skewing of elements

Claim 2

An array processor, comprising: N processing elements; N memory modules; an interconnection network interconnecting said processing elements and said memory modules, for effecting parallel access and alignment of rows, columns, diagonals, contiguous blocks and distributed blocks of an N×N array denoted as A, where for an integer i, where O≦i<N, i m denotes bit m in a binary representation of said integer, and where i j:m i p:q denotes a further integer derived by concatenating i p:q at rightward of i j:m , by performing a nonlinear skewing scheme for mapping each element A [i,j] of an N-vector in Γ G l ∪Δ G l to a distinct one of said memory modules denoted as F(i,j), for avoiding memory conflicts, where F(i,j)=ω(i)⊕j for O≦i, j<N, and ω(i n-1:h i h-1:0 )=i h-1:0 (i n-1:h ⊕i h-1:0 ), and where h=n/2; and O (log N) logic gates are provided for said N memory modules for: a) accessing any N-vector in Γ G l by addressing memory location l⊕Gk of memory module k for all O≦k<N, where G is any fixed integer and Γ G l ={A[ω -1 (l⊕Gk), l⊕Gk]|0≦k<N}, where 0≦G,l<N defines a partition of A into N-Vectors; and b) accessing any N-vector in Δ G l by addressing memory location l⊕Gω(k) of memory module k for all 0≦k<N, where Δ G l ={A[ω -1 (l⊕Gω(k)⊕k), l⊕Gω(k)]|0≦k<N}, for 0≦G,l<N.

Claim 3

The array processor of claim 1, wherein an address bus structure for parallel generation of local addresses in said N memory modules for accessing any N-vectors defined by Γ G l and Δ G l , comprising 4n address lines a n-1 , b n-1 , c n-1 , d n-1 , . . . , a o , b o , c o , d o , where n=log N, wherein address lines a i , b i , c i and d i are driven by l i ⊕G i , (l i ⊕G i ), α+l i α, (l i ⊕G i )α+l i α, and l i , respectively, for all 0≦i<n, where + denotes a logical or operation and α is a binary control variable, each memory module being provided with n address pins wherein an ith address pin of said n address pins assumes the ith significant bit position of an n-bit address, said n address pins of each said memory module being connected to predetermined ones of said address lines as follows: for all h≦i<n, address pins i and i-h of memory module k are connected to address lines d i and d i-h if k i =0 and k i-h =0; to address lines c i and a i-h if k i =0 and k i-h =1; to address lines b i and c i-h if k i =1 and k i-h =0, to address lines a i and b i-h of k i =1 and k i-h = 1.

Claim 4

The array processor of claim 1, wherein O (log N) logic gates being provided for said N memory modules for: a) accessing any row, column or distributed block of A by addressing memory location l⊕Gk of memory module k for all O≦k<N, where 0≦G,1<N defines a partition of A into N-vectors; and b) accessing any forward diagonal, backward diagonal, or contiguous block of A by addressing memory location l⊕Gω(k) of memory module k for all 0≦k<N, where 0≦G,1<N.

Claim 5

An array processor, comprising: N processing elements; N memory modules; an interconnection network interconnecting said processing elements and said memory modules, for effecting parallel access and alignment of rows, columns, diagonals, contiguous blocks and distributed blocks of an N×N array denoted as A, where for an integer i, where O≦i<N, i n denotes bit m in a binary representation of said integer, and where i j:m i p:q denotes a further integer derived by concatenating i p:q at rightward of i j:m , by performing a nonlinear skewing scheme for mapping each element A [,J] of an N-vector in Γ G l ∪Δ G l to a distinct one of said memory modules denoted as F(i,j), for avoiding memory conflicts, where F(i,j)=ω(k)⊕j for O≦i, j<N, and ω(i n-1:h i h-1:0 )=i h-1:0 (i n-1:h ⊕i h-1:0 ), and where h=n/2; and said interconnection network comprising n+1 stages wherein a first n stages of said n+1 stages form an indirect binary n-cube network, and a remaining stage of said n+1 stages is adapted to produce one of either an identity permutation for passing the following permutations: a) τi and τ i -1 b) ρ i ; c) δ -1 ; d) λ -1 ; e) τ i and τ i -1 ; or a permutation, where ξ(x n-1:h x h-1:0 )=x n-1:0 x n-1:h for passing the remaining permutations, as follows: f) τ i (x)=F(i,x); g) ρ i (x)=F(x,i); h) δ(x)=F(x,x); i) λ(x)=F(x,x); j) τ i (x)=F(i n-1:h x n-1:h ,i h-1:0 x h-1:0 ; k) μ i (x)=F(x n-1:h i n-1:h ,x h-1:0 i h-1:0 ).

Claim 6

An array processor, comprising: N processing elements; N memory modules; an interconnection network interconnecting said processing elements and said memory modules, for effecting parallel access and alignment of rows, columns, diagonals, contiguous blocks and distributed blocks of an N×N array denoted as A, where for an integer i, where O≦i<N, i n denotes bit m in a binary representation of said integer, and where i j:m i p:q denotes a further integer derived by concatenating i p:q at rightward of i j:m , by performing a nonlinear skewing scheme for mapping each element A [,J] of an N-vector in Γ G l ∪Δ G l to a distinct one of said memory modules denoted as F(i,j), for avoiding memory conflicts, where F(i,j)=ω(k)⊕j for O≦i, j<N, and ω(i n-1:h i h-1:0 )=i h-1:0 (i n-1:h ⊕i h-1:0 ), and where h=n/2; and said interconnection network comprising n+1 stages wherein a first n stages of said n+1 stages form an indirect binary n-cube network, and a remaining stage of said n+1 stages is adapted to produce one of either an identity permutation for passing the following permutations: a) τi and τ i -1 b) ρ i ; c) δ -1 ; d) λ -1 ; e) τ i and τ i -1 ; or a permutation, where ξ(x n-1:h x h-1:0 )=x n-1:0 x n-1:h for passing the remaining permutations, as follows: f) τ i (x)=F(i,x); g) ρ i (x)=F(x,i); h) δ(x)=F(x,x); i) λ(x)=F(x,x); j) τ i (x)=F(i n-1:h x n-1:h ,i h-1:0 x h-1:0 ; k) μ i (x)=F(x n-1:h i n-1:h ,x h-1:0 i h-1:0 ).

Claim 7

An array processor, comprising: N processing elements; N memory modules; an interconnection network interconnecting said processing elements and said memory modules, for effecting parallel access and alignment of rows, columns, diagonals, contiguous blocks and distributed blocks of an N×N array denoted as A, where for an integer i, where O≦i<N, i m denotes bit m in a binary representation of said integer, and where i j:m i p:q denotes a further integer derived by concatenating i p:q at rightward of i j:m , by performing a nonlinear skewing scheme for mapping each element A [i,j] of an N-vector in Γ G l ∪Δ G l to a distinct one of said memory modules denoted as F(i,j), said element A[i,j] is stored in one of either location j or i of said memory module F(i,j), for avoiding memory conflicts, where F(i,j)=ω(i)⊕j for O≦i, j<N, and ω(i n-1:h i h-1:0 )=i h-1:0 (i n-1:h ⊕i h-1:0 ), and where h=n/2; and O (log N) logic gates are provided for said N memory modules for: a) accessing any N-vector in Γ G l by addressing memory location l⊕Gk of memory module k for all O≦k<N, where G is any fixed integer and Γ G l ={A[ω -1 (l⊕Gk),l⊕Gk]|023 k<N}, where 0≦G,l<N defines a partition of A into N-vectors; and b) accessing any N-vector in Δ G l by addressing memory location l⊕Gω(k) of memory module k for all 0≦k<N, where Δ G l ={A[ω -1 (l⊕Gω(k)⊕k), l⊕Gω(k)]|0≦k<N}, for 0≦G,l<N.

Claim 8

An array processor, comprising: N processing elements; N memory modules; an interconnection network interconnecting said processing elements and said memory modules, for effecting parallel access and alignment of rows, columns, diagonals, contiguous blocks and distributed blocks of an N×N array denoted as A, where for an integer i, where O≦i<N, i m denotes bit m in a binary representation of said integer, and where i j:m i p:q denotes a further integer derived by concatenating i p:q at rightward of i j:m , by performing a nonlinear skewing scheme for mapping each element A [i,j] of an N-vector in Γ G l ∪Δ G l to a distinct one of said memory modules denoted as F(i,j), said element A[i,j] is stored in one of either location j or i of said memory module F(i,j), for avoiding memory conflicts, where F(i,j)=ω(i)⊕j for O≦i, j<N, and ω(i n-1:h i h-1:0 )=i h-1:0 (i n-1:h ⊕i h-1:0 ), and where h=n/2; and O (log N) logic gates are provided for said N memory modules for: a) accessing any N-vector in Γ G l by addressing memory location l⊕Gk of memory module k for all O≦k<N, where G is any fixed integer and Γ G l ={A[ω -1 (l⊕Gk),l⊕Gk]|023 k<N}, where 0≦G,l<N defines a partition of A into N-vectors; and b) accessing any N-vector in Δ G l by addressing memory location l⊕Gω(k) of memory module k for all 0≦k<N, where Δ G l ={A[ω -1 (l⊕Gω(k)⊕k), l⊕Gω(k)]|0≦k<N}, for 0≦G,l<N.

Claim 9

The array processor of claim 5, wherein an address bus structure for parallel generation of local addresses in said N memory modules for accessing any N-vectors defined by Γ G l and Δ G l , comprising 4n address lines a n-1 , b n-1 , c n-1 , d n-1 , . . . , a o , b o , c o , d o , where n=log N, wherein address lines a i , b i , c i and d i are driven by l i ⊕G i , (l i ⊕G i ),α+l i α, (l i ⊕G i )α+l i α, and l i , respectively, for all 0≦i<n, where + denotes a logical or operation and α is a binary control variable, each memory module being provided with n address pins wherein an ith address pin of said n address pins assumes the ith significant bit position of an n-bit address, said n address pins of each said memory module being connected to predetermined ones of said address lines as follows: for all h≦i<n, address pins i and i-h of memory module k are connected to address lines d i and d i-h if k i =0 and k i-h =0; to address lines c i and a i-h if k i =0 and k i-h =1; to address lines b i and c i-h if k i =1 and k i-h =0, to address lines a i and b i-h of k i =1 and k i-h =1.

Claim 10

The array processor of claim 5, wherein the O (log N) logic gates are provided for: a) accessing any row, column or distributed block of A by addressing memory location l⊕Gk of memory module k for all O≦k<N, where 0≦G,1<N defines a partition of A into N-vectors; and b) accessing any forward diagonal, backward diagonal, or contiguous block of A by addressing memory location l⊕Gω(k) of memory module k for all 0≦k<N, where 0≦G,1<N.