Information Technology Reference
In-Depth Information
register int i ;
data type a [ n ];
for ( i =0; i<n ; i = i + uf )
{ a [ i ]= value ;
a [ i +1]= value ;
a [ i +2]= value ;
a [ i +3]= value ;
···
a [ i + uf
register int i ;
data type a [ n ];
for ( i =0; i<n ; i = i + uf )
{ a [ i ]= value ;
a [ i +1]= value ;
a [ i +3]= value ;
a [ i +2]= value ;
···
a [ i + u 2 +1]= value ;
a [ i + u 2 ]= value ;
register int i ;
data type a [ n ];
for ( i =0; i<n ; i ++)
{ a [ i ]= value ;
}
(a) Original Loop
2] = value ;
a [ i + uf
1] = value ;
}
}
(b) LU
(c) LUG
Fig. 2. Generalized form of the original loop, LU and LUG
int, long int, float, double, etc. Each element belonging to a data type consumes
sizeof ( data type ) bytes of memory space, where sizeof ( data type )isapowerof
2. Let, base address ( a ) be the base address or the starting address of the array
a .Let, b be obtained by shifting base address ( a ) log 2 sizeof ( data type ) bits
right. The value of b signifies the portion (bits) of the address of array elements
involved in switching activity. The log 2 sizeof ( data type ) least significant bits
( lsb s) of the address of the array elements are not involved in switching activity,
and remain same for all elements of the array. Let, a be an array of n =2 ʱ
elements and uf =2 ʲ be the loop unrolling factor, where ʱ
ʲ and ʱ , ʲ
uf =2 ʱ−ʲ =2 ʳ times. The
expressions for S LU and S LUG are derived in sections 2.2 and 2.3, respectively,
considering base address ( a )=0and n is divisible by uf .
n
are natural numbers. The unrolled loop iterates,
2.2 Derivation of S LU
S LU is dependent on intra-iteration switching ( S LU intra ) and inter-iteration
switching ( S LU inter ). So, S LU can be written as shown in equation (1)
S LU = S LU intra + S LU inter
(1)
S LU intra is the total number of 0
0 bit transitions on the
address bus of the data memory, which takes place due to the memory address
references of the elements of array a , i.e. a [ i ] ,a [ i +1] , ..., a [ i + uf
1 and 1
to
to
2] ,a [ i + uf
1]
(in ( uf +1) th iteration, where, 0
i<n and i is a multiple of uf ), within the
body of the unrolled loop. For each iteration ʲlsb sof b follows the sequence
0 , 1 , 2 , 3 ,
···
,uf
2 ,uf
1. So, S LU intra can be written as shown in equation (2)
n
uf × t ʲ
S LU intra =
(2)
where t ʲ is the number of intra-iteration switchings per iteration. t ʲ can be
expressed by the recurrence relation as shown in equation (3)
t ʲ =2
×
t ʲ− 1 + ʲ, for ʲ > 1 ,andt 1 =1
(3)
Search WWH ::




Custom Search