Bus Minimization and Scheduling of Multi-Chip Systems

This paper considers several different algorithms that reduce the required number of buses for multichip module design. An efficient polynomial time algorithm that calculates the minimum number of buses needed given a particular schedule is presented. We also present three algorithms that minimize the number of buses during scheduling. Experimental results are shown that illustrate the efficiency of the algorithms. 1 Introduction The design of computer systems consisting of several chips is referred to as multi-chip module (MCM) design. Such systems are becoming increasingly important for several reasons. First, the complexity and functionality of computer systems being built is increasing at a dramatic rate. This makes it very difficult for many systems to be built in a single chip even with the most advanced computer-aided design tools. Second, multi-chip modules permit designs to be modular. Hence, design time can be dramatically reduced. Finally, multiple chips increase the test..