Record Details

Decomposition of finite state machines for area, delay minimization

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Decomposition of finite state machines for area, delay minimization
 
Creator SHELAR, RUPESH S
DESAI, MP
NARAYANAN, H
 
Subject delays
finite state machines
logic design
minimisation of switching nets
state assignment
 
Description We consider the state assignment problem as that of the decomposition of finite stare machines and transform this decomposition problem into an orthogonal partitioning problem with a certain cost function. We justify this cost function in two ways, first by using an idealized model of multi-level logic implementation, and second by empirical studies of a particular benchmark circuit. We describe a greedy algorithm to minimize this cost function. We present results obtained by running the algorithm on a set of 16 MCNC benchmarks. We compare these results with other state assignment techniques such as JEDI and NOVA. For multilevel implementations of the benchmark state machines, we find that the implementations obtained after using JEDI were, on average, 8.52% larger in area and 81.87% slower in delay than the implementations obtained using our approach. The implementations obtained after using NOVA were, on average, 4.40% larger in area and 104.96% slower in delay when compared with implementations obtained using our approach. Our scheme has the potential to serve as an alternative to conventional state assignment tools since we observe that it produces good results for larger finite state machines.
 
Publisher IEEE
 
Date 2008-12-18T04:48:44Z
2011-11-27T16:04:57Z
2011-12-15T09:56:34Z
2008-12-18T04:48:44Z
2011-11-27T16:04:57Z
2011-12-15T09:56:34Z
1999
 
Type Article
 
Identifier Proceedings of the International Conference on Computer Design, Austin, USA, 10-13 October 1999, 1-6.
0-7695-0406-X
10.1109/ICCD.1999.808606
http://hdl.handle.net/10054/385
http://dspace.library.iitb.ac.in/xmlui/handle/10054/385
 
Language en