CHANNEL ROUTERS FOR LSI LAYOUT USING MERGING TECHNIQUES.

TWO NEW ALGORITHMS ARE PROPOSED FOR THE CHANNEL ROUTING PROBLEM IN THE LAYOUT DESIGN OF LSI CHIPS. ONE OF THE ALGORITHMIS A SIMPLE ONE AND IT DEPENDS ON A PROCESS OF MERGING NETSINSTEAD OF ASSIGNING HORIZONTAL TRACKS TO INDIVIDUAL NETS. THE OTHER IS BASED ON THE SAME IDEA, BUT IT USES A MATCHING ALGORITHM TO IMPROVE THE SOLUTION. THE ALGORITHMS WERE CODEDIN FORTRAN AND IMPLEMENTED ON A VAX 11/780 COMPUTER. EXPERIMENTAL RESULTS ARE QUITE ENCOURAGING. BOTH PROGRAMS GENERATED OPTIMAL SOLUTIONS IN 6 OF 8 CASES, USING EXAMPLES IN PREVIOUSLY PUBLISHED PAPERS. THE COMPUTATION TIMES OF THE ALGORITHMS FOR A TYPICAL CHANNEL (300 TERMINAL, 70 NETS) WERE 1. 0 SECOND AND 2. 1 SECONDS, RESPECTIVELY.