204 PARALLEL ALGORITHMS
would do 32,258,000 multiplications, each one in a separate processor cycle
for 32,258,000 cycles. Using a 5 5 processor mesh (25 processors), we
would do the same number of multiplications, but it would only take
3,612,896 cycles, almost a 90% time savings.■ 7.6.2 Matrix Multiplication in a CRCW PRAM Model
Parallel matrix multiplication in a combining CRCW PRAM model that adds
concurrent writes to one memory location can be done in constant time with
sufficient processors. To multiply an IJ matrix A by a JK matrix B will
require I*J*K processors. Each of these processors will be responsible for
exactly one of the O(N^3 ) multiplications necessary to calculate the overall
result. This gives the following algorithm:
Parallel Start
for x = 1 to I do
for y = 1 to J do
for z = 1 to K do
Pxyz calculates Axy* Byz and stores it in Mxz
end for z
end for y
end for x
Parallel EndAnalysis
As was mentioned, each of the processors does one multiplication and then
stores its result in the proper memory location. This takes one cycle. There will
beJ processors that write concurrently to each of the memory locations that
are part of the result. We indicated that this concurrent write model will com-
bine all concurrent writes by adding the values together, so the write process
handles the additions that are the other component of the standard sequential
matrix multiplication algorithm.
The run time of this algorithm is O(1), when using O(N^3 ) processors where
N = maximum(I,J,K). This gives a total cost of O(N^3 ), which is the same as
our standard sequential algorithm. The run time reduction is even more dra-
matic than with our mesh-based algorithm. Returning again to our convolu-
tion example, we see that with 125 processors, we can do the matrix
multiplication for one location in one processor cycle. This means that the
convolution with the entire image could be done in just 258,064 cycles, 125
times faster than the sequential version.