A graph partitioning problem for multiple-chip design

A new graph partitioning problem is introduced. It stems from a multiple-chip design style in which there is a chip library of chips containing predesigned circuit components (e.g., adders, multipliers, etc.) which are frequently used. Given an arbitrary circuit data flow graph, it is necessary to realize the circuit by appropriately choosing a set of chips from the chip library. In selecting chips from the chip library to realize a given circuit, both the number of chips used and the interconnection cost are to be minimized. The authors' new graph partitioning problem models this chip selection problem. An efficient solution to this problem is presented.>