An Approach to the Optimal Specification of Read-Only Memories in Microprogrammed Digital Computers

1 April 1974

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-23 (4) , 375-389
https://doi.org/10.1109/t-c.1974.223953

Abstract

This paper illustrates an algorithm for finding a read-only memory (ROM) specification, optimal in the sense that it results in a minimum ROM bit dimension, starting with an instruction set description which employs acyclic directed graphs. The algorithm selects (by a tabular technique) a descriptive graph subset, shown to be sufficient; then it performs a heuristically guided search among possible solutions generated by the graphs in the subset. The algorithm works for instructions which are such that a microevent occurs at most once in a single instruction; some results apply to the general case as well.

Keywords

This publication has 3 references indexed in Scilit:

Isomorfismo fra grafi: Un algoritmo efficiente per trov are tutti gli isomorfismi
Calcolo, 1971
On the Minimization of READ-ONLY Memories in Microprogrammed Digital Computers
IEEE Transactions on Computers, 1970
An algorithm for minimizing read only memories for machine control
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1968