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

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.