The focus of high-level built-in self-test (BIST) synthesis is register assignment, which involves system register assignment, BIST register assignment, and interconnection assignment. To reduce the complexity involved in the assignment process, existing high-level BIST synthesis methods decouple the three tasks and perform the tasks sequentially at the cost of global optimality. They also try to achieve only one objective: minimizing either area overhead or test time. Hence, those methods do not render exploration of large design space, which may result in a local optimum. In this paper, we propose a new approach to the BIST data path synthesis based on integer linear programming that performs the three register assignment tasks concurrently to yield optimal designs. In addition, our approach finds an optimal register assignment for each k-test session. Therefore, it offers a range of designs with different figures of merit in area and test time. Our experimental results show that our method successfully synthesizes a BIST circuit for every k-test session for all six circuits experimented. All the BIST circuits are better in area overhead than those generated by existing high-level BIST synthesis methods.

In this paper, we present a new method to the built-in selftestable data path synthesis based on integer linear programming (ILP). Our method performs system register assignment, built-in self-test (BIST) register assignment, and interconnection assignment concurrently to yield optimal designs. Our experimental results show that our method successfully synthesizes BIST circuits for all six circuits experimented. All the BIST circuits are better in area overhead than those generated by existing high-level BIST synthesis methods. Keywords high-level BIST synthesis, built-in self-test, BIST, ILP. 1.

A high-level built-in self-test (BIST) synthesis involves several tasks such as system register assignment, interconnection assignment, and BIST register assignment. Existing high-level BIST synthesis methods perform the tasks sequentially at the cost of global optimality. We proposed a new approach based on an integer linear programming (ILP). Our method achieves optimal solutions for most circuits in hardware overhead, but it takes a long processing time. In this paper, we present a heuristic method to address this problem. The heuristic partitions a given data flow graph into smaller regions based on control steps and applies the ILP for each region successively. Our heuristic reduces the processing time by several orders of magnitude, while the quality of the solution is slightly compromised. We present experimental results for six circuits and compare the results with other BIST synthesis methods.

Existing high-level BIST synthesis methods focus on one objective, minimizing either area overhead or test time. Hence, those methods do not render exploration of large design space, which may result in a local optimum. In this paper, we present a method which aims to address the problem. Our method tries to find an optimal register assignment for each k-test session. Therefore, it offers a range of designs to the designer with different figures of merit in area and test time. Experimental results show that our method performs better than or comparable to existing BIST synthesis systems.