Area-period tradeoffs for multiplication of rectangular matrices

Ferng Ching Lin; I-Chen Wu

doi:10.1016/0022-0000(85)90050-9

Area-period tradeoffs for multiplication of rectangular matrices

Ferng Ching Lin^*
, I-Chen Wu

^*此作品的通信作者

數據科學與工程研究所

研究成果: Article › 同行評審

2 引文斯高帕斯（Scopus）

摘要

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 AP²) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that AP^2α = ω((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.

原文	English
頁（從 - 到）	329-342
頁數	14
期刊	Journal of Computer and System Sciences
卷	30
發行號	3
DOIs	https://doi.org/10.1016/0022-0000(85)90050-9
出版狀態	Published - 6月 1985

存取文件

10.1016/0022-0000(85)90050-9

其它文件與鏈接

Link to publication in Scopus

引用此

@article{5e9194465ced4548ad8013e6128ed640,

title = "Area-period tradeoffs for multiplication of rectangular matrices",

abstract = "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.",

author = "Lin, \{Ferng Ching\} and I-Chen Wu",

year = "1985",

month = jun,

doi = "10.1016/0022-0000(85)90050-9",

language = "English",

volume = "30",

pages = "329--342",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Area-period tradeoffs for multiplication of rectangular matrices

AU - Lin, Ferng Ching

AU - Wu, I-Chen

PY - 1985/6

Y1 - 1985/6

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0022083885

U2 - 10.1016/0022-0000(85)90050-9

DO - 10.1016/0022-0000(85)90050-9

M3 - Article

AN - SCOPUS:0022083885

SN - 0022-0000

VL - 30

SP - 329

EP - 342

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

Area-period tradeoffs for multiplication of rectangular matrices

摘要

存取文件

其它文件與鏈接

指紋

引用此