iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: http://zbmath.org/0761.65034
Document Zbl 0761.65034 - zbMATH Open
×
Gušev, M.; Evans, D. J.; Tasič, J.

Fast linear systolic matrix vector mutliplication. (English) Zbl 0761.65034

Int. J. Comput. Math. 43, No. 3-4, 231-248 (1992).
The paper presents a new derivation of H. T. Kung’s regular bidirectional linear algorithm in the parallel architecture design [cf. H. T. Kung and C. E. Leiserson, Sparse matrix computations, Proc. Symp., Knoxville 1978, 256-282 (1979; Zbl 0404.68037)]. This new approach results in implementations which are executed in less time and use less processors.
The proposed procedure to obtain the fast systolic computation consists of algorithm partitioning, remapping (time compression), interlocking translation and composition of relevant parts. Finally, the fast systolic computation is applied to matrix-vector multiplication, and different implementations are compared.
Reviewer: F.Luban (Bucureşti)

Cited in 1 Review
Cited in 2 Documents

MSC:

65F30 Other matrix algorithms (MSC2010)
65Y05 Parallel numerical computation
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)

Keywords:

systolic array; data dependence; algorithm transformation; linear mapping; algorithm partitioning; interlocking translation; fast systolic computation; matrix vector multiplication

Citations:

Zbl 0404.68037
Cite Review PDF
Full Text: DOI

References:

[1] Kung H. T., Systolic Arrays (for VLSI) (1978) · Zbl 0404.68037
[2] Kung H. T., IEEE Computer 15 pp 37– (1982)
[3] Gušev M., Some Nonlinear Transformations of Matrix Vector Multiplication Algorithm (1991)
[4] Gušev M., Folding Transformation of Systolic Processor Arrays (1991)
[5] Evans D. J., Implementation of Folding Transformations on Linear Systolic or VLSI Processor Arrays (1991)
[6] DOI: 10.1109/TC.1986.1676652 · Zbl 0577.68050 · doi:10.1109/TC.1986.1676652
[7] Cappello, P. R. and Steglitz, K. 1983.Proc. of 1983 Int. Conference on Parallel Processing. Unifying VLSI array designs with geometric transformations. 1983. pp.448–457.
[8] Quinton, P. 1984.Proc. of 11th Annual Int. Symposium on Computer Architecture. Automatic synthesis of systolic arrays from uniform recurrence equations. 1984. pp.208–214.
[9] Kung S. Y., VLSI Array Processors (1988)
[10] Gušev M., Comparative Analysis of Methods for Broadcast Elimination (1991)
[11] DOI: 10.1109/PROC.1983.12532 · doi:10.1109/PROC.1983.12532
[12] DOI: 10.1109/71.80125 · doi:10.1109/71.80125
[13] Chen C. H., Signal Processing Handbook (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.