AT2 bounds for a class of VLSI problems and string matching

ABSTRACT

We present a class of boolean functions which have regional mappings, a generalization of the transitivity property defined in [12]. We prove that all transitive problems have regional mappings, as do a variety of interesting computational problems such as merging two sorted lists of arbitrary length, generalized integer multiplication and matrix-vector products. We present a general area-time lower bound for VLSI implementations of problems with regional mappings and confirm that the lower bound matches the previously known bound for transitive problems. For generalized integer multiplication, we present a custom VLSI implementation which provides a matching upper bound. The results improve AT2 bounds on a number of open problems. In related work, we consider the problem of finding occurrences of a P-bit pattern in an N-bit text string. We show that every chip capable of solving this string matching problem requires AT2 = &OHgr;(PN). A custom VLSI design, using an idea similar to that used for generalized integer multiplication, provides a matching upper bound when N is polynomial in P.

REFERENCES

• 1: G. Baudet and W. Chen. Area-Time Tradeoffs }or Merging, in VLSI: Algorithms and Architectures, pp. 61-68, 1985.
• 2: G. Bilardi , F. P. Preparata, Area-time lower-bound techniques with applications to sorting, Algorithmica, v.1 n.1, p.65-91, Jan. 1986 [doi>10.1007/BF01840437]
• 3: G. Bilardi and M. Sarrafza.deh. Optimal VLSI Circuits for the DFT, in Advances in Computing Research, Volume 4, pp. 87-101, 1987.
• 4: R. P. Brent , H. T. Kung, The Area-Time Complexity of Binary Multiplication, Journal of the ACM (JACM), v.28 n.3, p.521-534, July 1981 [doi>10.1145/322261.322269]
• 5: Bruno Codenotti , Mauro Leoncini, Introduction to Parallel Processing (International Computer Science Series), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 6: R. Cole and A. Siegel. On Informat,on Flow and Sorting; New Upper and Lower Bounds for VLSI Circuits, in Proc. 26th FOCS, pp. 208-221, 1985.
• 7: Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
• 8: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 9: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 10: Clark David Thompson, A complexity theory for vlsi, 1980
• 11: Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
• 12: J. Vuillemin. A Comb,natomal Lzm,t to the Comput,ng Power of VLSI Circuits, in Proc. 21st FOCS, 1980.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Theory, Verification