Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Partitioning for Testing

IP.com Disclosure Number: IPCOM000051224D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Kurtzberg, JM: AUTHOR [+2]

Abstract

The problem of generating tests for failures in very large scale integration (VLSI) is acute. While larger and larger designs are predicted in VLSI, running times of the most efficient algorithms remain a function of the square of the complexity -- the number of circuits; designs of boards of 200,000 circuits are immediately contemplated while those of a million do not appear far off. A topological method is described herein for cutting a large design into smaller designs in such manner that test generation, at some cost of extra hardware, may be restricted to these smaller pieces, bringing the running time down to reasonable proportions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Partitioning for Testing

The problem of generating tests for failures in very large scale integration (VLSI) is acute. While larger and larger designs are predicted in VLSI, running times of the most efficient algorithms remain a function of the square of the complexity -- the number of circuits; designs of boards of 200,000 circuits are immediately contemplated while those of a million do not appear far off. A topological method is described herein for cutting a large design into smaller designs in such manner that test generation, at some cost of extra hardware, may be restricted to these smaller pieces, bringing the running time down to reasonable proportions.

While the running of the test-generation programs will be, because of efficiency purposes, run on each primary output segment (cone) separately, the method of partitioning described here considers the entire network together. Each circuit, node, will be labeled with the length of the longest path to a primary output, computed inductively. The constraint on the partitioning is that the SIZE of the partitions should not exceed a certain cardinality, depending upon the effectiveness of the test-generation programs.

Assign to each node of the graph of the design the LEVEL NUMBER (1), which is the length of the longest path to a primary output. The computation starts with the primary outputs and proceeds backwards in inductive fashion. Count at each level (number) the number of branches (to be cut). Select that level with the minimum number of cuts which divides the circuit into two subcircuits of size bounded below by b, a (large) positive integer, of size, e.g., specified for an admissible running time.

Given a subdivision constructed in the above manner, we next perform LOCAL VARIATIONS on the frontier (J. Paul Roth, Computer Logic, Testing and Verification, Computer Science Press, Rockville, Maryland, 1980.), the points of cut. We selectsets of these points whose successors have...