Assume that we have a pipeline that can perform addition or multiplication opera
ID: 3682256 • Letter: A
Question
Assume that we have a pipeline that can perform addition or multiplication operations. It consists of k stages, and, each stage has a delay of 1/k time units. When switching between operations ( from +to *, or from * to +), the pipeline should be drained before the data for the new operation canbe applied to the pipeline. Assume that there are adequate memory and buffers. Also, ignore storage time, memory access time, time to set up the pipeline control circuit, and so on. Determine the minimum time required to multiply two n-by-n matrices (where n>k) to produce an n-by-n matrix product.
Explanation / Answer
Suppose A is an n-by-n matrix, and B is an n-by-n matrix, then C = AB will be an n-by-n matrix.
C = AB can be computed in O(n3) time.
Multiplying two N ×N matrices needs "N" number of multiplications and "N 1" number of additions for every element. Thus, there are N2 elements in the matrix this gives a total of N2 (2N 1) floating-point operations, or about 2N3 i.e. O(N3 ).