Test scheduling for core-based systems using mixed-integer linear programming

被引：134

作者：

Chakrabarty, K ^{[1
]}

机构：

[1] Duke Univ, Dept Elect & Comp Engn, Durham, NC 27708 USA

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 2000年 / 19卷 / 10期

基金：

美国国家科学基金会;

关键词：

embedded core testing; open shop scheduling; resource constraints; system-on-a-chip test; test set selection; testing time;

D O I：

10.1109/43.875306

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present optimal solutions to the test scheduling problem for core-based systems. Given a set of tasks (test sets for the cores), a set of test resources (e.g., test buses, BIST hardware) and a test access architecture, we determine start times for the tasks such that the total test application time is minimized. We show that the test scheduling decision problem is equivalent to the m-processor open shop scheduling problem and is therefore NP-complete. However, a commonly encountered instance of this problem (m = 2) can be solved in polynomial time. For the general case (m > 2), we present a mixed-integer linear programming (MILP) model for optimal scheduling and apply it to a representative core-based system using an MILP solver available in the public domain. We also extend the MILP model to allow optimal test set selection from a set of alternatives. Finally, we present an efficient heuristic algorithm for handling larger systems for which the MILP model may be infeasible.

引用

页码：1163 / 1174

页数：12

共 15 条

[1] Scan chain design for test time reduction in core-based ICs [J].

Aerts, J ;

Marinissen, EJ .

INTERNATIONAL TEST CONFERENCE 1998, PROCEEDINGS, 1998, :448-457

[2]

BRGLEZ F, 1989, 1989 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-3, P1929, DOI 10.1109/ISCAS.1989.100747

[3]

Brglez F., 1985, P IEEE INT S CIRC SY, P695

[4]

Carey M., 1979, COMPUTER INTRACTABIL

[5]

Chakrabarty K., 2000, Proceedings 18th IEEE VLSI Test Symposium, P127, DOI 10.1109/VTEST.2000.843836

[6]

CHAKRABARTY K, P 2000 IEEE ACM DES, P432

[7]

Fourer R, 1993, AMPL MODELING LANGUA

[8]

*GAMS DEV CORP, 1993, GAMS US GUID

[9] A low overhead design for testability and test generation technique for core-based systems [J].

Ghosh, I ;

Jha, NK ;

Dey, S .

ITC - INTERNATIONAL TEST CONFERENCE 1997, PROCEEDINGS: INTEGRATING MILITARY AND COMMERCIAL COMMUNICATIONS FOR THE NEXT CENTURY, 1997, :50-59

[10]

GONZALEZ T, 1976, J ACM, V23, P665, DOI 10.1145/321978.321985

← 1 2 →