Speedup of band linear recurrences in the presence of resource constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Speedup of band linear recurrences in the presence of resource constraints

Full text

Pdf (1.29 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 6th international conference on Supercomputing table of contents

Washington, D. C., United States

Pages: 466 - 477

Year of Publication: 1992

ISBN:0-89791-485-6

Authors

Haigeng Wang
Alexandru Nicolau

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 18, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/143369.143452 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
	3	Shyh-Ching Chen, Speedup of iterative programs in multiprocessing systems., 1975
	4	Chert, S. C. and Kuck, D., "Time and Processor Bounds for Linear Recurrence Systems", IEEE Transactions on Computer, Vol. C-24, pp. 701-717, July, 1975.
	5	S. C. Chen , D. J. Kuck , A. H. Sameh, Practical Parallel Band Triangular System Solvers, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.270-277, Sept. 1978 [doi>10.1145/355791.355797]
	6	K. Ebcioglu. "Some Design Ideas for a VLIW Architecture for Sequential-natured Software", Proceedings IFIP, 1988.
	7	Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
	8	J. A. Fisher. "Trace Scheduling: A technique for global microcode compaction". IEEE Transactions on Computers, No. 7,pp. 478-490, 1981.
	9	Gajski, D., "An Algorithm for Solving Linear Recurrence Systems on Parallel and Pipelined Machines", IEEE, Transactions on Computers, Vol. c-30, No.3, March 1981.
	10	K. A. Gallivan , R. J. Plemmons , A. H. Sameh, Parallel algorithms for dense linear algebra computations, SIAM Review, v.32 n.1, p.54-135, March 1990 [doi>10.1137/1032002]
	11	Thomas Gross , Monica S. Lam, Compilation for a high-performance systolic array, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.27-38, June 25-27, 1986, Palo Alto, California, United States
	12	J. R. Allen, K. Kennedy, "PFC: A program to Convert Fortran to Parallel Form", Rice University Tech. Rep. MASC TR 82-6, Houston, TX, 1982.
	13	L. Hyafil , H. T. Kung, The Complexity of Parallel Evaluation of Linear Recurrences, Journal of the ACM (JACM), v.24 n.3, p.513-521, July 1977 [doi>10.1145/322017.322030]
	14	Kogge, P. and Stone, H., "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations", IEEE Transactions on Computer, Vol., C-22, No.8, August 1973.
	15	David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
	16	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	17	J. J. Little , G. E. Blelloch , T. A. Cass, Algorithmic Techniques for Computer Vision on a Fine-Grained Parallel Machine, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.3, p.244-257, March 1989 [doi>10.1109/34.21793]
	18	Alexandru Nicolau , Haigeng Wang, Optimal schedules for parallel prefix computation with bounded resources, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-10, April 21-24, 1991, Williamsburg, Virginia, United States
	19	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	20	B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
	21	H. Wang, A. Nicolau, "Speedup of Programs Confining Band Linear Recurrence with Resource ConstrMnts", Tech. Rep. 92-12, Department of Information and Computer Science, University of California Irvine, December, 1991.
	22	H. Wang, A. Nicolau, "Optimal schedules and new time bounds for parallel evaluation of band linear recurrences", Technical Report, Department of Information and Computer Science, University of California at Irvine, Jan. 1992.

CITED BY 3

	Haigeng Wang , Nikil Dutt , Alexandru Nicolau , Kai-Yeung Sunny Siu, High-level synthesis of scalable architectures for IIR filters using multichip modules, Proceedings of the 30th international conference on Design automation, p.336-342, June 14-18, 1993, Dallas, Texas, United States
	Haigeng Wang , Nikil Dutt , Alexandru Nicolau, Harmonic scheduling of linear recurrences for digital filter design, Proceedings of the conference on European design automation, p.396-401, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Haigeng Wang , Alexandru Nicolau , Stephen Keung , Kai-Yeung Sunny Siu, Computing Programs Containing Band Linear Recurrences on Vector Supercomputers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.769-782, August 1996