Two complementary approaches for microcode bit optimization

Author

Park, In-Cheol ; Hong, Se-Kyoung ; Kyung, Chong-Min

Author_Institution

Dept. of Electr. Eng., Korea Adv. Inst. of Sci. & Technol., Taejon, South Korea

Volume

43

Issue

2

fYear

1994

fDate

2/1/1994 12:00:00 AM

Firstpage

234

Lastpage

239

Abstract

In the design of microprogrammed processors, the minimization of microcode width is very crucial to reduce the required microcode ROM area. The paper suggests two different procedures which are complementary in nature: first an integer linear programming formulation which guarantees an optimal solution for small or medium size problems; and second, a heuristic algorithm based on the graph bipartitioning to deal with large size problems. Experimental results show that the proposed heuristic algorithm yields near-optimal solutions with polynomial time complexity

Keywords

computational complexity; linear programming; microprogramming; minimisation; graph bipartitioning; heuristic algorithm; integer linear programming; microcode bit optimization; microcode width; microprogrammed processors; microprogramming; minimization; polynomial time complexity; Algorithm design and analysis; Control systems; Design optimization; Encoding; Fault tolerance; Heuristic algorithms; Integer linear programming; Partitioning algorithms; Read only memory; Size control;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.262130

Filename

262130