Abstract
The branching programs that were studied as a nonuniform computing model providing lower bounds on the space of deterministic sequential computations are considered. It is shown that branching programs can provide lower bounds on the general model of VLSI computations — multilective circuits, and that one-time-only branching programs provide lower bounds on the area of the basic model of VLSI computations. Using this technique we obtain new lower bounds on area complexity of VLSI computations.
Another technique is introduced to prove time and area optimality of some algebraic algorithms for one-dimensional systolic arrays. A new efficient algorithm on two-way systolic array is developed for GCD problem.
This work was supported by the ŠPZV I-1/5/8 grant and the ŠPZV III-8-1/10 grant.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
BABAI, L-HAJNAL, P.-SZEMERÉDI, E.,-TURÁN, G.: A lower bound for read-once only Brancinching programs. JCSS 35 (1987), 153–162.
BOLLOBÁS, B.: Extremal Graph Theory. Academic Press, New York 1987.
BORODIN,A.-DOLEV,D.-FICH,F.E.-Paul,W.: Bounds for width two branching programs. Proc. 15th ACM STOC, ACM 1983, 87–93.
BRENT, R.P.-KUNG, H.T.: Systolic VLSI arrays for linear-time GCD computation. In: VLSI '83 (F. Anceau and E.J. Aas Eds.), North-Holland, Amsterdam 1983, 145–154.
CHANDRA,A.K.-FURST,M.L.-LIPTON,R.J.: Multiparty protocols. In: Proc. 15th ACM STOC, ACM 1983, 94–99.
FTÁČNIK, M.-HROMKOVIČ, J.: Nonlinear lower bound for real-time branching programs. Computers AI 4 (1985), No.3, 353–359.
GEDDES,K.O.: Algebraic algorithms for symbolic computation — Chapt.2, Research report, University of Waterloo, Computer Science Department 1981.
HROMKOVIČ, J.: Lower bound technique for VLSI algorithms. In Proc. IMYCS'86, Hungarian Academy of Sciences, Budapest 1986, 9–19.
HROMKOVIČ,J.: Some complexity aspects of VLSI computations. Part 1. A framework for the study of information transfer in VLSI circuits. Computers AI 7, No.3, to appear.
HROMKOVIČ,J.: Some complexity aspects of VLSI computations. Part 2. Topology of circuits and information transfer. Computers AI 7, No.4, to appear.
JUKNA,S.P.: Lower bounds on the complexity of local circuits. In: 12th MFCS'86, Lecture Notes in Computer Science 233, Springer-Verlag 1986, 440–448.
KATRIŇÁK,T.-GAVALEC,M.-GEDEONOVÁ,E.-SMÍTAL,J.: Algebra a teoretická aritmetika. ALFA — SNTL 1985 (in Slovak).
KUNG,H.T.: Use of VLSI in algebraic computation: Some suggestions. In: Proc. SYMSAC'81, ACM 1981, 218–222.
KUNG,H.T.: Let's design algorithms for VLSI systems. CMU Computer Science Dept., Technical report, 1979.
LIPSON,J.D.: Elements of Algebra and Algebraic Computing. Addison-Wesley 1981.
MASEK,W.: A fast algorithm for the String editing problem and decision graph complexity. M.Sc. Thesis, MIT, May 1976.
NEČIPORUK, E.I.: On a Boolean function. Soviet Math. Dokl. 7 (1966), 999–1000.
PROCHÁZKA, J.: Zložitost' algebraických výpočtov na niektorých modeloch počítačov. Dissertation thesis, VUSEIAR Bratislava, 1986 (in Slovak).
PROCHÁZKA, J.: The polynomial GCD-algorithm implemented in a systolic architecture. Acta Math. Com. Univ. XLVIII-XLIX (1986), 325–333.
PUDLÁK,P.-ŽÁK,S.: Space complexity of computations. Unpublished manuscript, 1982.
PUDLÁK,P.: A lower bound on complexity of branching programs. In Proc. 11th MFCS'84, Lecture Notes in Computer Science 176, Springer-Verlag 1984, 480–489.
THOMPSON, C.O.: A Complexity Theory for VLSI. Doct. dissertation, CMU-CS-80-140, Computer Science Dept., Carnegie-Mellon University, Pittsburg, August 1980.
ULLMAN,J.D.: Computational Aspects of VLSI. Comp. Science Press 1984.
WEGENER,I.: On the complexity of Branching programs and Decision trees for Qlique functions. Universität Frankfurt, Fachbereich Informatik, Int. Rept. 5/84, 1984.
WEGENER, I.: Time-space trade-offs for Branching programs. JCSS 32 (1986), 91–96.
WEGENER, I.: Optimal decision trees and one-time-only branching programs for symetric Boolean functions. Information and Control 62 (1984), 129–143.
ŽÁK,S.: An exponential lower bound for one-time only branching programs. In: Proc. 11th MFCS'84, Lecture Notes in Computer Science 176, Springer-Verlag 1984, 562–566.
COLLINS, G.E.: Subresultants and reduced polynomial remainder sequences. JACM 14 (1967), 128–142.
GRUSKA, J.: Tvorba paralelných výpočtových sietí. Research report, Institute of Technical Cybernetics of the Slovak Academy of Sciences, Bratislava 1985 (in Slovak).
KNUTH, D.E.: The art of computer programming. Vol.2: Seminumerical algorithms. Second ed., Addison-Wesley, Reading, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hromkovič, J., Procházka, J. (1988). Branching programs as a tool for proving lower bounds on vlsi computations and optimal algorithms for systolic arrays. In: Chytil, M.P., Koubek, V., Janiga, L. (eds) Mathematical Foundations of Computer Science 1988. MFCS 1988. Lecture Notes in Computer Science, vol 324. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017159
Download citation
DOI: https://doi.org/10.1007/BFb0017159
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-50110-7
Online ISBN: 978-3-540-45926-2
eBook Packages: Springer Book Archive