Method on scan chain reordering for lowering VLSI power consumption

Abstract

A method for reordering a scan chain meets given constraints and minimizes peak power dissipation. The given constraints include a maximum peak power dissipation, a maximum scan chain length and a maximum distance between two successive registers. The method includes embedding a developed tool into an existing VLSI design flow for low-power circuit designs. Furthermore, the characteristics quickly judge if the problem has corresponding feasible solutions and searching the optimal solution. Modified data from the given scan chain declaration data and the scan pattern data, which satisfy the constraints, can be obtained.

1. A method of reordering a scan chain for design of testability on VLSI with low power dissipation, comprising:
 (a) inputting scan chain register circuit data, including a name of each register, 2D coordinates, and power dissipation value(s); 
 (b) inputting test pattern data on the scan chain; 
 (c) inputting conditions of design specification including peak value of power dissipation at a time of potential conversion of register; maximum of total connection length of the scan chain; and maximum of connection distance between two adjacent registers; 
 (d) determining whether a Feasible Solution meeting the maximum of connection distance between the two adjacent registers is provided; 
 (e) creating a database of the two adjacent registers; 
 (f) if an event meeting both the maximum of the total connection length and the maximum of connection distance, the total length of the scan chain being ignored; 
 (g) for a given test pattern, re-ordering the registers on the scan chain for reduction of power dissipation, and whether determining peak value limit of power dissipation and the maximum of total connection length for the scan chain accord; and 
 (h) outputting an updated scan chain arrangement and a corresponding scan chain test pattern data, wherein the event meeting the maximum of the total connection length of the scan chain is ignored in case of: 
 (a) L lim <L min : no feasible solution given; 
 (b) L min <=L lim <L max : at the time of the arrangement of the scan chain register at a next step, in addition to a search for a combination of the peak values in the adjacent registers so as to reduce power dissipation, a case beyond the total limit of length of the maximum scan chain also being taken into consideration so that the registers must be arranged to shorten the scan chain on the occasion; and 
 (c) L lim <L max : at the time of arrangement of the scan chain registers at a next step, the total limit of length of the maximum scan chain not being taken into consideration but a search for a set of peak values in the adjacent registers to reduce power dissipation; wherein i stands for any of the registers, and the distance D i   min  indicates the distance of a register i closer to the other registers, the distance D i   max  indicates the distance of a register i further from the other registers, and the distance D i   avg  indicates the distance of a register i equidistant from the other registers are estimated, namely L min =Σ i D i   min , L max =, Σ i D i   max , and L avg =Σ i D i   avg . 
 
   
   
     2. The method as claimed in  claim 1 , wherein creating the database of the two adjacent registers includes:
 (a) dividing distributed areas on coordinates of all registers into a form of grids, and storing a grid attributed to each register; 
 (b) recording a register falling in each grid; and 
 (c) searching for and recording a group of the two adjacent registers according to the maximum of connection distance in the grid and in a circumference of the grid. 
 
   
   
     3. The method as claimed in  claim 1 , wherein the event meeting both the maximum of the connection length and the maximum limited distance of connection is ignored in case of:
 (a) existence in a register without any corresponding group of the two adjacent registers which indicates that the design is provided with no feasible solution; 
 (b) existence in a register with only an adjacent register which indicates that the register must be the output terminal of the scan chain, and the adjacent register is second in arrangement order; 
 (c) existence in two registers with only an adjacent register:
 i. both of the two adjacent registers which indicates that no feasible solution is given; and 
 ii. two registers different from each other which indicates that one register can be made to be an input terminal of the scan chain, and the other, to be an output terminal; and 
 
 (d) at least four registers with only an adjacent register which indicates that no feasible solution is given. 
 
   
   
     4. The method of reordering a scan chain for the design of testability on VLSI with low power dissipation as claimed in  claim 3 , wherein the scan chain registers are reordered to:
 (a) decide a next optimal register to be arranged; and 
 (b) decide an optimal register of the output terminal. 
 
   
   
     5. The method of reordering a scan chain for the design of testability on VLSI with low power dissipation as claimed in  claim 4 , further comprising:
 using a logical XOR calculation every time to sort out a next optimal register in a set of registers having not been arranged in the course of arrangement so that the opposite test patterns can be little different from the test patterns of registers so far having been arranged, thereby reducing the probability of register state conversion in each shift. 
 
   
   
     6. The method of reordering a scan chain for the design of testability on VLSI with low power dissipation as claimed in  claim 3 , wherein in order to decide an optimal register of the output terminal after the scan chain registers reordered includes:
 (a) the special case of the built database of registers adjacent to each other occurs when (1) a register exists with an adjacent register only; and (2) two registers exist respectively with an adjacent register only, and the two registers are different from their adjacent registers; 
 (b) when no special cases occur, the minority of adjacent registers among all registers is used as the registers at the output; and 
 (c) when a database of registers adjacent to each other is provided, of all registers, a register of maximum power dissipation is used as the output terminal, and that less different from the test pattern is used as the input terminal.