Open Access. Powered by Scholars. Published by Universities.®
VLSI and Circuits, Embedded and Hardware Systems Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 2 of 2
Full-Text Articles in VLSI and Circuits, Embedded and Hardware Systems
Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg
Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg
Ronald Greenberg
There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Ronald Greenberg
This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …