22-05-2014, 02:25 PM
Minimizing the Latency Time of the PCG Systolic Implementation
Minimizing the Latency.ppt (Size: 163.5 KB / Downloads: 10)
“The term “systolic array
Was introduced in computer science by H.T. Kung &C.E. Leiserson (1978,1980).
Is a completely pipelined cellular organization.
Was that when it is connected to a host computer, which supplies it with data and extracts the data which has been processed by the array.
The PCG algorithm for solving linear systems
The Preconditioned Conjugate Gradient (PCG) method is used for solving systems of linear equations with symmetric positive definite matrix.
# The PCG algorithm performs four basics operations:
. Matrix – vector multiplication (MV-product).
. Vector – vector scalar dot product (VV-product).
. Scalar – vector multiplication.
. Vector – vector additions.
# The convergence to the solution of Ax = b is in no more than n steps, Increasing the size of the matrix cause an increase in the time.
Mapping the modified PCG algorithm.
Such a graph can be considered as being cut off from an dependence graph in zn.
# The projection of a graph delivers a systolic parallel algorithm.
# The processor space is zn - 1.
# The respective time periods are different for the same processor.
Conclusions
The modified systolic array was designed can effectively implemented using only local communications on a parallel system.
# The number of clock periods needed by a PCG systolic algorithm to solve one iteration, i.e. latency time, is reduced to n +n + 3 time moments.