Satisfiability-based method for reconfiguring power efficient VLSI array

Junyan Qian, Wei Cao, Jia Hu, Jingwei Zhang, Zhoubo Xu, Zhide ZhouIEICE Electron. Express 2016 · DOI

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.

VLSI array architecture and reconfiguration mechanisms including row bypass and column rerouting.

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

BibTeX
@article{qian2016satisfiability,
  author = {Junyan Qian and Wei Cao and Jia Hu and Jingwei Zhang and Zhoubo Xu and Zhide Zhou},
  title = {{Satisfiability-based method for reconfiguring power efficient VLSI array}},
  journal = {IEICE Electron. Express},
  year = {2016},
  doi = {10.1587/elex.13.20160930},
}
Figure