Title :
A "bit-bucket" data structure to optimize local search for microword length minimization
Author :
Koranne, Sandeep
Author_Institution :
VLSI Design Tools & Technol., Indian Inst. of Technol., Delhi, India
Abstract :
The problem of microword length minimization is crucial to the synthesis of microprogrammed controllers in digital systems. Unfortunately, this problem is NP-hard. In this paper, we describe a new data structure based on a "bit-bucket" scheme to optimize local searches for microword length minimization. We present our analysis for space and time complexity, and we compare our scheme with previously published algorithms.
Keywords :
computational complexity; data structures; digital systems; firmware; microcontrollers; microprogramming; minimisation; search problems; NP-hard problem; bit-bucket data structure; digital systems; local search optimization; microprogrammed controller synthesis; microword length minimization; space complexity; time complexity; Automatic control; Computer architecture; Concurrent computing; Control systems; Data structures; Decoding; Digital systems; Encoding; Size control; VLIW;
Conference_Titel :
Electrical and Computer Engineering, 1999 IEEE Canadian Conference on
Conference_Location :
Edmonton, Alberta, Canada
Print_ISBN :
0-7803-5579-2
DOI :
10.1109/CCECE.1999.807250
