Area-period tradeoffs for multiplication of rectangular matrices

摘要

A VLSI computation model is presented with a time dimension in which the concept of information transfer is made precise and memory requirements (lower bounds for A) and area-period trade-offs (lower bounds for AP2) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that AP2α = ω((min(mn, mp, np)l)1 + α), 0 ⩽5 α ⩽ 51, for the problem of multiplying m × n and n × p matrices of l-bit elements. We also show that min(mn, mp,np)l is the exact bound for chip area.