3-D bin packing algorithm proposed for SoC testing

3-D bin packing algorithm proposed for SoC testing
By Nicolas Mokhoff, EEdesign
October 28, 2002 (1:59 p.m. EST)
URL: http://www.eetimes.com/story/OEG20021028S0036

Researchers from Mentor Graphics Corp. are proposing a more complete way to test multiple cores on a system-on-chip. At the International Test Conference, Mentor presented a paper that defines SoC testing as a restricted three-dimensional bin-packing problem and provides a heuristic to determine an optimal solution.

For a given SoC with given pin and peak-power constraints, the proposed technique simultaneously determines an optimal wrapper width for each core, allocates SoC pins to cores and schedules core tests to minimize the test completion time.

A system-on-chip usually includes multiple reusable design blocks and intellectual-property blocks, such as digital logic, processors, memories and analog and mixed-signal circuits. To access the cores from the SoC pins, on-chip hardware infrastructure known as the test access mechanism (TAM) is used to transport test stimuli from the SoC pins to the embedded cores. TAMs also transport test response s from the embedded cores to the SoC pins.

Picking a path

TAM architectures can be classified into two categories: those that use existing functional paths inside cores and those that insert paths outside cores for test purposes.

Designers use wrappers as thin shells around cores that provide interfaces between SoC pins and core terminals during test. Wrappers also allow adjustment of the bandwidth for test to enable optimal utilization of the SoC's external pins.

Controlled by the instruction register, a core can be set in functional mode, test mode or bypass mode. In test mode, it can be accessed via TAM through wrapper boundary cells. The functional input/output bidirectional terminals of a core connect with the wrapper cells. If a core has internal scan chains, the scan input and output terminals of the core can also be connected to the wrapper cells. That leads to multiple choices for configuring a wrapper.

The primary objective of the Mentor effort was to address SoC test scheduling in a way that would minimize SoC test time while satisfying the two constraints (the given number of SoC pins and the allowable SoC peak power consumption). It lays the groundwork for achieving optimum SoC test scheduling.

Under this formulation, each core is represented by a rectangle. The width of the rectangle is the number of SoC pins allocated to the core; the height of the rectangle is the core test time given the number of SoC pins allocated to it. The SoC is represented by a bin with a fixed width that is equal to the number of SoC pins.

The test-scheduling problem is translated into a 2-D bin-packing problem with the objective of minimizing the total bin height. To allow core access from different numbers of SoC pins, "rectangle transformation" is used to reflect the change in the width (the number of SoC pins allocated to a core) and height (the test application time of the core). The width of the transformed core corresponds to the width of the wrapper used for testing the core .

In their paper, the authors proposed a new method, called restricted 3-D bin packing, to accommodate the peak power constraint. The method simultaneously allows selection of an optimal wrapper width for each core, allocation of SoC pins to cores, and scheduling of core tests to achieve optimal test completion time for the SoC design under pin and power constraints.

It's a wrap

A core under one wrapper design can be represented by a 3-D cube, where wrapper width, peak power and test time represent the three dimensions. Similarly, a 3-D bin can be used to represent the pin, peak-power and total-test-time dimensions of the SoC. The objective is to select, for each core, one cube among several permissible cubes and to pack a total of K cubes representing K cores into the bin representing the SoC so that the height of the bin is minimized.

Initially, it may appear that the previous 2-D method can be extended to a 3-D architecture. But the problem at hand is a restricted 3-D bin-packing problem. For example, if two cores are tested concurrently, they overlap in the time dimension and hence cannot have any overlap in the other two dimensions, since both pins and power cannot be shared between cores that are tested concurrently. This differs from normal 3-D bin packing, the authors note.

The method can accommodate any wrapper design, the authors claim. The peak power consumed during core test may vary with the core wrapper design.

The authors gave results on a set of emerging benchmark systems-on-chip called the ITC'02 SOC Benchmarks. They said the proposed formulation could be extended to incorporate more constraints by solving a bin-packing problem with the appropriate number of dimensions.