Report Number: CS-TR-81-871
Institution: Stanford University, Department of Computer Science
Title: Good layouts for pattern recognizers
Author: Trickey, Howard W.
Date: August 1981
Abstract: A system to lay out custom circuits that recognize regular languages can be a useful VLSI design automation tool. This paper describes the algorithms used in an implementation of a regular expression compiler. Layouts that use a network of programmable logic arrays (PLA's) have smaller areas than those of some other methods, but there are the problems of partitioning the circuit and then placing the individual PLA's. Regular expressions have a structure which allows a novel solution to these problems: dynamic programming can be used to find layouts which are in some sense optimal. Various search pruning heuristics have been used to increase thc speed of the compiler, and the experience with these is reported in the conclusions.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/871/CS-TR-81-871.pdf