PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS
作者:
PETER CAPPELLO,
OMER EGECIOGLU,
CHRIS SCHEIMAN,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 2000)
卷期:
Volume 15,
issue 3-4
页码: 167-199
ISSN:1063-7192
年代: 2000
DOI:10.1080/01495730008947355
出版商: Taylor & Francis Group
关键词: Algebraic path problem;Dag;Diophantine equation;Gaussian eiimination;Matrix product;Optimal;Systolic array;Tensor product;Transitive closure;C.3;F.2.m;F.m;G.2.1;l.l.m
数据来源: Taylor
摘要:
Minimizing the amount of time and number of processors needed to perform an application reduces the application's fabrication cost and operation costs. A directed acyclic graph (dag) model of algorithms is used to define a time-minimal schedule and a processor-time-minimal schedule, We present a technique for finding a lower bound on the number ofprocessorsneeded to achieve a given schedule of an algorithm. The application of this technique is illustrated with a tensor product computation. We then apply the technique to the free schedule of algorithms for matrix product, Gaussian elimination, and transitive closure. For each, we provide a time-minimal processor schedule that meets these processor lower bounds, including the one for tensor product.
点击下载:
PDF (806KB)
返 回