The interconnection problem (Q1208922)

The problem of interconnecting circuit modules in microprocessor and digital system design is studied. Data transfers are described by sets \(T_ i\) of directed edges between the modules, for \(1\leq i\leq m\) time steps. An interconnecting schema, where data transfers are assigned to buses, consists of links between modules and buses. First, it is shown that the problem to find an assignment with minimum number of links NP-complete. Then, the problem to find an embedding of the transfers to a given interconnection schema is studied. The problem can be solved in polynomial time, if there are only transfers with different sources for each time step. But, in general the embedding problem remains NP-complete.