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 条

[11]

Lee H. K., 1993, 1293 STAT U VIRG POL

[12] A novel test methodology for core-based system LSIs and a testing time minimization problem [J].

Sugihara, M ;

Date, H ;

Yasuura, H .

INTERNATIONAL TEST CONFERENCE 1998, PROCEEDINGS, 1998, :465-472

[13] AMYLOID BETA-PROTEIN PRECURSOR IN CULTURED LEPTOMENINGEAL SMOOTH-MUSCLE CELLS [J].

VANNOSTRAND, WE ;

ROZEMULLER, AJM ;

CHUNG, R ;

COTMAN, CW ;

SAPORITOIRWIN, SM .

AMYLOID-INTERNATIONAL JOURNAL OF EXPERIMENTAL AND CLINICAL INVESTIGATION, 1994, 1 (01) :1-7

[14]

WILLIAMS HP, 1985, MODEL BUILDING MATH

[15] Testing embedded-core based system chips [J].

Zorian, Y ;

Marinissen, EJ ;

Dey, S .

INTERNATIONAL TEST CONFERENCE 1998, PROCEEDINGS, 1998, :130-143

← 1 2 →