GRAPH-THEORETIC TECHNIQUES FOR COMPUTER INTRACONNECTION MINIMIZATION

The design and minimization of computer intraconnections have a great influence on system characteristics such as cost, performance, failure rate, and in the case of VLSI, chip area. The problem addressed was t he minimization of computer intraconnections with bandwidth and delay constraints imposed. This research problem has been formally defined a s a graph theory problem. A heuristic algorithm, H-RASP2, is presented which approximates a minimal solution for this NP-complete problem in polynomial time. H-RASP2 was tested using a variety or graph sizes an d fill's. Analysis of the results shows that for the test cases H-RASP 2 provides an excellent approximation to a minimal solution.