Statistical algorithm for determining a stopping-point in interconnection design
Original Publication Date: 2002-Nov-15
Included in the Prior Art Database: 2003-Jun-20
A statistical framework is disclosed to decide when to stop the use of a pre-route algorithm in ULSI designs. The main emphasis is on incorporating intervention with custom algorithms in the design process in a seamless manner. The first issue that can influence a decision to stop the use of a pre-route algorithm is the ability of the routing system to complete the remaining design routes without route violations. If the routing task is impossible for the routing system, and violations remain, additional trials are continued until the completed routes contain zero violations. Based on statistical considerations of a design that is routed with custom interconnections over a series of n trials, the question of how to decide whether an additional trial (n+1) should be attempted with the same pre-route algorithm after violations are removed is discussed. Here, the goal is to determine the degree of confidence that an additional step of intervention with custom interconnections will result in further improvement in physical properties of the design routes. The estimated total effectivenesses for netlengths and vias are obtained from data obtained in previous trials. The underlying mean effectivenesses of netlengths and vias are a function of the basic parameters, including the proportions of netlengths in each of the three types of routes (custom, other, or rest), and the effectivenesses of each type. The estimates of the projected effectivnesses for netlengths and vias in the trial (n+1) are computed exclusively based on data obtained in the first n trials. The projected total netlength and projected total via count in a potential subsequent trial (n+1) can be forecast with a statistical analysis of the results of the previous n trials; the total netlength in trial n; the total via count in trial n; the estimated effectivenesses for custom routes, other routes, and the rest of the routes obtained in previous trials; an estimated region of influence R(n+1) that is projected to contain the desired additional custom interconnections. The cumulative netlength effectiveness for proposed trial (n+1) is obtained by taking the ratio of the total projected netlength in trial (n+1) to the total netlength in trial 0, and then subtracting this ratio from unity; the cumulative via effectiveness for the proposed trial (n+1) is obtained by taking the ratio of the total projected netlength in trial (n+1) to the total netlength in trial 0, and then subtracting this ratio from unity.