Abstract
As VLSI manufacturing scales, hardware defects in processor arrays become increasingly common. This paper introduces CPETASAT, a reconfiguration algorithm that utilizes Boolean Satisfiability (SAT) solvers to salvage faulty arrays into functional logical meshes. Unlike previous methods, CPETASAT specifically optimizes for power efficiency by minimizing long interconnections between processing elements (PEs). Experimental results demonstrate a 2% to 6% reduction in long interconnects compared to the state-of-the-art CMTA algorithm.
Introduction
In modern Very-Large-Scale Integration (VLSI) systems, packing numerous processing elements (PEs) onto a single wafer increases the probability of manufacturing defects. To maintain yield, reconfiguration techniques are employed to bypass faulty PEs and connect healthy ones into a functional logical array. This paper focuses on the degradation approach, where the goal is to construct the largest possible functional grid from available healthy PEs.
A critical challenge in reconfiguration is power efficiency. In VLSI circuits, longer interconnects lead to higher capacitance and increased dynamic power consumption. Therefore, the objective is to find a "Power Efficient Target Array" (PETA) that minimizes long-distance connections, thereby reducing both power usage and signal latency.
System Architecture and Reconfiguration
The physical substrate consists of a grid of PEs connected by a network of switches and rerouting channels.
As shown in the figure above, the architecture supports both row and column rerouting. A logical array is formed by mapping healthy physical PEs to logical coordinates. When a PE is faulty, it must be bypassed using the available routing infrastructure. The efficiency of the resulting array is determined by the number of "long" interconnects—those spanning multiple switches—required to maintain the logical grid structure.
The CPETASAT Algorithm
The authors propose transforming the reconfiguration problem into a Boolean Satisfiability (SAT) problem. The CPETASAT algorithm models the physical constraints and optimization goals as a set of logic clauses:
- SAT Modeling: The mapping of a physical PE to a specific logical column is represented as a Boolean variable.
- Constraints: To ensure a valid grid, the model applies uniqueness constraints (one PE per logical position), adjacency constraints (PEs must be within a compensation distance of 1), and non-intersection constraints (logical columns cannot cross).
- Iterative Refinement: Because finding the global optimum is NP-complete, CPETASAT uses an iterative approach. It utilizes a SAT solver (specifically Cryptominisat-4.5.3) to find a valid configuration. If a solution is found but does not meet the desired power efficiency threshold, a "conflict clause" is added to the solver to exclude that solution, and the search continues until an efficient configuration is identified.
Experimental Evaluation
The method was evaluated using simulated host arrays of sizes $16 \times 16$, $18 \times 18$, and $20 \times 20$. Faults were injected using a uniform distribution at densities ranging from 10% to 25%.
Key Results
Compared to the previous state-of-the-art CMTA algorithm, CPETASAT achieved:
- Improved Power Efficiency: A consistent reduction in the number of long interconnects (nlis), with improvements ranging from 2% to over 6%.
- Fault Density Robustness: While the computational effort generally increases with fault density, the algorithm remains effective even at high density levels. Interestingly, at 25% fault density, the search space often shrinks enough that the solver finds solutions more quickly than at moderate densities.
Conclusion
CPETASAT demonstrates that modern SAT solvers can be effectively applied to hardware layout optimization. While the SAT-based approach requires more computation time than simpler heuristics (often capped at 1800 seconds in tests), the resulting gains in power efficiency and reduced latency are significant. Future work will focus on reducing the number of variables in the SAT model to improve scalability for larger, massively parallel processor arrays.
Summary updated