An efficient algorithm is provided for solving a class of linear programming problems containing a large set of distance constraints of the form x/sub i/-x/sub j//spl ges/k and a small set of multivariable constraints of forms other than x/sub i/-x/sub j//spl ges/k. This class of linear programming formulation is applicable to very large scale integration (VLSI) layout spacing problems, including hierarchy-preserving hierarchical layout compaction, layout compaction with symmetric constraints, layout compaction with attractive and repulsive constraints, performance-driven layout compaction, etc. The longest path algorithm is efficient for solving spacing problems containing only distance constraints. However, it fails to solve problems that involve multiple-variable constraints. The linear programming formulation of a spacing problem requires use of the simplex method, which involves many matrix operations. This can be very time consuming when handling huge constraints systems derived from VLSI layouts. Herein it is found that most of the matrix operations can be replaced with fewer and faster graph operations, creating a more efficient graph-theory-based algorithm. Theoretical analysis shows that the proposed algorithm reduces the computation complexity of the simplex method.

In the past 20 years, DES has been the most widely used symmetric block cipher for information security. Recently, a novel method called Differential Fault Analysis (DFA) has been proposed to attack DES. Under the assumption that the attacker can induce errors into the cipher device, the key of DES can be unveiled easily. The assumed technique is not mature today, but is like to appear in the near future, especially for attacking a tamper resistant device with an embedded DES VLSI chip. In this paper, we proposed a new hardware design for the DES cipher to resist DFA. By adding some protection circuitry, all the unidirectional faults induced into the registers of a DES chip can be detected, and then alter to the cryptosystem immediately. A hardware emulation experiment using Altera's CPLD chip shows the effectiveness of the protection design.

The layout compaction problem with performance consideration is studied. In our approach, the delay upper-bound on the timing critical paths is reduced first, then the layout size is minimized without increasing that delay bound. Either step is formulated as a linear programming problem, and we propose a graph-based simplex algorithm, which replaces most of the matrix operations with graph operations, to solve the problem. Both theoretical analysis and experimental results show that this algorithm is quite efficient.