The interconnection problem

摘要

In this paper the problem of interconnecting circuit modules in microprocessor and digital system design is studied. The data transfers are expressed by m sets Ti of directed edges between modules. An interconnecting schema, which is given by an assignment of the data transfers to buses, consists of the links between modules and buses. At first we show, that the problem of finding an assignment with minimum number of links is NP-complete. After that we prove that the problem of using a given interconnection schema is NP-complete, too.