Good Layouts for Pattern Recognizers
- 1 June 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (6) , 514-520
- https://doi.org/10.1109/TC.1982.1676033
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 the speed of the compiler and the experience with these is reported in the conclusions.Keywords
This publication has 8 references indexed in Scilit:
- The compilation of regular expressions into integrated circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Hardware Algorithms for Nonnumeric ComputationIEEE Transactions on Computers, 1979
- A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph RepresentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Bristle Blocks: A Silicon CompilerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Silicon Compilation-A Hierarchical Use of PLAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Introduction to Silicon CompilationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Programmed Logic Array OptimizationIEEE Transactions on Computers, 1978
- A proper model for the partitioning of electrical circuitsPublished by Association for Computing Machinery (ACM) ,1972