Today’s logic chips and System-on-Chips (SoCs) are ever-growing in size, complexity, and integration density. This drives a continuous need to develop novel and advanced ways to efficiently test such devices after manufacturing. High-bandwidth IJTAG over SSN (HB-IJTAG) is one such innovation that leverages the high-speed and parallel Streaming Scan Network (SSN) bus to concurrently access many local IEEE 1687 (IJTAG) networks.However, every time the high-bandwidth IJTAG access mode is activated, it must first be configured through the global IJTAG network. The initial configuration and subsequent reconfigurations constitute a substantial test time overhead due to the lower shift speed and serial nature of global IJTAG.This paper introduces wide-ranging enhancements to the high-bandwidth IJTAG access to allow for persistent utilization of the high-speed SSN bus. By eliminating the reasons for the expensive reconfigurations, high-bandwidth IJTAG can remain active throughout the entire test session. This results in a significant reduction of test setup time and more efficient test delivery. Our experiments clearly demonstrate these benefits in different pattern delivery scenarios. Persistently using the high-bandwidth data delivery reduced the relevant IJTAG pattern execution time by up to 243x, yielding an up to 18x lower overall test time for SSN ATPG patterns.

As Systems-on-Chip (SOC) designs grow in complexity, so do the challenges associated with testing them. Some of the obstacles SOC designers face include limited I/O and scan channels, routing and timing closure issues, increasing manufacturing test and defect diagnosis time, and growing test data volume. Various design-for-test (DFT) techniques exist to handle complex SOC designs that have multiple cores. One new DFT implementation technique is the streaming scan network (SSN) high-bandwidth parallel data bus. SSN addresses many of the SOC challenges by providing an optimized packet-based scan data delivery system. It also dynamically optimizes test time by adjusting the data applied to each core. However, SSN is limited to delivering scan data; it cannot be used to deliver data to individual instruments in a physical block using the IEEE 1687 (IJTAG) network. This paper introduces a new high-bandwidth IJTAG DFT technology that leverages the existing high-speed parallel SSN bus to drive the serial IJTAG network. It describes the DFT implementation methodology, the impact to the backend in terms of timing and SDC, and how verification was done by Intel as they deployed it on multiple dielets in their next generation client CPU. Moreover, data on area overhead and the overall test cost savings achieved is presented.

The multiple knapsack problem is a well-studied combinatorial optimization problem with several practical and theoretical applications. It consists of packing some subset of n items into m knapsacks such that the total profit of the chosen items is maximum. A new formulation of the problem is presented, where a Lagrangian relaxation is derived, and we prove that it dominates the commonly used relaxations for this problem. We also present a Dantzig-Wolfe decomposition of the new formulation that we solve to optimality using a branch-and-price algorithm, where its main advantage comes from the fact that it is possible to control whether an item is included in some knapsack or not. An improved algorithm for solving the resulting packing subproblems is also introduced. Computational experiments then show that the new approach achieves state-of-the-art results. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) [Grants 2017-06054 and 2021-04037]. This support is gratefully acknowledged.

We investigate the discrete parallel machine scheduling and location problem, which consists of locating multiple machines to a set of candidate locations, assigning jobs from different locations to the located machines, and sequencing the assigned jobs. The objective is to minimize the maximum completion time of all jobs, that is, the makespan. Though the problem is of theoretical significance with a wide range of practical applications, it has not been well studied as reported in the literature. For this problem, we first propose three new mixed-integer linear programs that outperform state-of-the-art formulations. Then, we develop a new logic-based Benders decomposition algorithm for practical-sized instances, which splits the problem into a master problem that determines machine locations and job assignments to machines and a subproblem that sequences jobs on each machine. The master problem is solved by a branch-and-cut procedure that operates on a single search tree. Once an incumbent solution to the master problem is found, the subproblem is solved to generate cuts that are dynamically added to the master problem. A generic no-good cut is first proposed, which is later improved by some strengthening techniques. Two optimality cuts are also developed based on optimality conditions of the subproblem and improved by strengthening techniques. Numerical results on small-sized instances show that the proposed formulations outperform state-of-the-art ones. Computational results on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations demonstrate the effectiveness and efficiency of the algorithm compared with current approaches. Summary of Contribution: This paper employs operations research methods and computing techniques to address an NP-hard combinatorial optimization problem: the parallel discrete machine scheduling and location problem. The problem is of practical significance but has not been well studied in the literature. For the problem, we formulate three novel mixed-integer linear programs that outperform state-of-the-art formulations and develop a new logic-based Benders decomposition algorithm. Extensive computational experiments on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations are conducted to evaluate the performance of the proposed models and algorithms.

Traditional scan test interfaces though general purpose (GP) IOs suffer from bandwidth limitations, contributing to increasing manufacturing test costs. Applying scan test through high speed IOs (i.e. SERDES) is a key interest area for the industry to overcome bandwidth limitations of traditional scan test, but is under the development in the industry today due to the need for compatible technologies across the entire ecosystem of EDA, ATE and IC designers. Guided by IEEE 1149.10, a group of pioneer engineers / users are deploying their robust and complete solutions. In this industry session, engineers from fabless, ATE and EDA companies are sharing their experiences in this area.

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances. Summary of Contribution: We address the two-dimensional bin packing problem (2D-BPP), which calls for packing a set of rectangular items into a minimal set of larger rectangular bins. The 2D-BPP is a very difficult generalization of the standard one-dimensional bin packing problem, and it has been widely studied in the past because it models many real-world applications, including production, warehouse management, and transportation. We solve the 2D-BPP with a combinatorial Benders decomposition that is based on a model in which the two-dimensional items and bins are represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but it is enriched with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The algorithm we developed has been extensively tested on the most well-known benchmark set from the literature, which contains 500 instances. It behaved very well, improving on average upon previous algorithms, and solving for the first time a number of open instances. We analyzed in detail several configurations before obtaining the best one and discussed several insights from this analysis in the manuscript.

IEEE 1687 (IJTAG) provides significant value to the DFT engineer and efficiency in the DFT flow. However, IJTAG requires 4 or 5 pins to drive an IEEE 1149.1 compliant TAP controller. Many of our designs have fewer than 4 pins total, prohibiting the usage of IJTAG. In this paper we describe a solution that drives an embedded TAP controller from a chip interface that consists of only 2 ports, a clock port and a bidirectional data port. The embedded TAP then drives the IJTAG network as usual, providing us all the benefits of IJTAG. To enable this, we needed to expand the used EDA tool's IJTAG support in the direction of IEEE P1687.1. Experiences from the implementation of this solution in a productive chip show significant productivity gains.

System-on-Chip (SoC) designs are increasingly difficult to test using traditional scan access methods without incurring inefficient test time, high planning effort, and physical design/timing closure challenges. The number of cores keeps growing while chip pin counts available for scan remain constant or decline, limiting the ability to drive cores concurrently. With increasingly commonplace tiling and abutment, the scan distribution hardware must be placed inside the cores, making balanced pipelining when broadcasting to identical cores difficult. optimizing test time requires analyzing all the cores and subsequently changing the test hardware in the cores. Internal shift speed constraints may limit the ability to shift data in and out of the chip at high rates. Differences in pattern counts or scan chain lengths between cores tested in parallel can result in padding and increased test time. SSN is a bus-based scan data distribution architecture designed to address all these challenges. It enables simultaneous testing of any number of cores even with few chip I/Os. It facilitates short test time by enabling high-speed data distribution, by efficiently handling imbalances between cores, and by supporting testing of any number of identical cores with a constant cost. It provides a plug-and-play interface in each core that is well suited for abutted tiles, and simplifies scan timing closure. This paper also compares the test cost and implementation productivity of SSN with those of Intel's Structural Test Fabric.

A tile based design methodology consists of developing design blocks that are inserted in design layouts by placing blocks next to each other, making a tile-to-tile connection by abutting corresponding physical signal lines at the border of the tile. Very large systems can be easily and rapidly developed by seamlessly integrating tile elements in the layout. Further, the ease of top-level integration underlines the advantages over a bottom-up approach. However, this tile-based approach is incompatible with traditional DFT tools, which were created to work in accordance with the bottom-up design methodology. This paper outlines some of the obstacles to overcome, to support a truly tile-based DFT methodology. We describe here a working solution for a large production design, underlining a successful implementation of a tile-based Memory Test methodology.

Cutting and packing (C&P) is a fundamental research area that models a large number of managerial and industrial optimization issues. A solution to a C&P problem basically consists of a set of one-dimensional or multidimensional items packed in/cut from one or more bins, by satisfying problem constraints and minimizing a given objective function. Normal patterns are a well-known C&P technique used to build solutions where each item is aligned to the bottom of the bin along each dimension. They are used in several C&P techniques because they can reduce the search space while preserving optimality, but their limit is that their number grows consistently when number of items and size of the bin increase. In this paper we propose a new set of patterns, called meet in the middle, that preserves optimality and leads to several interesting results. Their computation is achieved with the same time complexity as that of the normal patterns, but their number is never higher, and in practical applications it frequently shows reductions of about 50%. These new patterns are applied to improve some exact state-of-the-art C&P techniques, including arc-flow formulations, combinatorial branch-and-bound algorithms, and mixed-integer linear programs. The efficacy of the improved techniques is assessed by extensive computational tests on a number of relevant applications. The online appendix is available at https://doi.org/10.1287/ijoc.2018.0806 .

IEEE 1149.1-based top-level access to IEEE 1500-compliant IP cores is commonly used in industrial designs as the underlying infrastructure to provide test access, control, instrumentation, and ease of use. Validating the test infrastructure and its usage in the early design stages is critical to the success of the project. The new Internal Joint Test Action Group (IJTAG or IEEE 1687-2014) standard is a valuable component of this test infrastructure and is designed to promote efficient embedded instrument access. This paper describes one of first comprehensive applications of an IJTAG-based method to a state-of-the-art server microprocessor design from specification to production. We leveraged IJTAG to automate design modeling, enable faster and more advanced verification, and optimize manufacturing test access. In this work, we demonstrate a very high degree of optimization and automation, which is cost-efficiently enabled by IJTAG, and goes beyond the capabilities of typical in-house IJTAG-like system, currently in use in industry.

An analog test bus and serial digital access to ADC and DAC parallel ports are two widely used analog DFT techniques. Unfortunately, they cannot be described in a standard way that could facilitate automatic test pattern generation (ATPG). Furthermore, serially accessing an ADC/DAC is typically too inefficient for periodic sampling for various reasons, but mostly because of the capture/update-then-shift sequence used in IEEE 1149.1, 1500, and 1687. This paper shows that if a small amount of digital circuitry is added to each accessed ADC/DAC parallel port, they could be described in IEEE 1687 instrument connection language (ICL) to facilitate optimally efficient streaming access to the parallel ports. Furthermore, this could be automated by adding our proposed “iStream” as a new 1687 procedural description language (PDL) command. We provide examples of how it would be used, along with evidence to show it can provide more efficient (up to 2X, or more) serial access rate to ADCs and DACs than previous automatable approaches.

Abstract This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last‐in‐first‐out constraint that states that any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A branch‐and‐cut algorithm is proposed for solving this problem. Computational results are reported on different types of randomly generated instances as well as on classical instances for some well‐known special cases of the problem. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract This article studies a single vehicle pickup and delivery problem with loading constraints. In this problem, the vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy a last‐in‐first‐out constraint where any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A large neighborhood search is proposed for solving this problem. Computational results are reported on different types of randomly generated instances. Results are also reported on benchmark instances for two special cases of our problem and a comparison is provided with state‐of‐the‐art methods. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

The BurstModetrade test clocking methodology, first presented in, is improved to handle circuits with synchronous clocks of different frequencies. An on-chip clock controller allows to select a large number of clock waveforms necessary to test synchronous cross-domain paths at-speed and control supply voltage variations. The methodology is applicable to both ATPG and BIST and only requires combinational analysis tools. The methodology is applied to a large circuit to adjust power supply margins of an at-speed BIST test.

The effort to standardize a methodology for accessing embedded instrumentation as IEEE PI687 continues to progress. This paper captures the current state of mind of the IJTAG working group with respect to the framework built to date and presents a discussion of other issues on which decisions are pending. The key elements of an architectural description language, a procedural language, and a hardware interface scheme are all taking shape, but still have many details to complete. Since this is a snapshot taken during the standard development process, the final form of the draft standard may differ from what is described here; any feedback to the working group is welcome

Gigahertz serialization and deserialization (SERDES) has become a dominant inter-chip and inter-board data transmission technique. Signal integrity is the primary factor determining its bit error rate, typically less than 10/sup -12/, so the primary production test challenges are testing picosecond jitter and the signal eye opening. Off-chip jitter and rise/fall time measurements are limited by hardware complexity, access, bandwidth, and noise. Published on-chip measurement techniques are limited by delay line jitter. This paper presents a new jitter test technique that has been demonstrated on an FPGA to achieve less than 1 ps RMS self-jitter, and a new signal eye test that has unlimited bandwidth; neither test uses high speed circuitry. The all-digital technique uses the receiver itself to demodulate the signal jitter to a low-speed bit stream that is analyzed by a single-clock domain, synthesizable circuit. This is combined with logic BIST and 1149.6 boundary scan to completely test an IC.

A new embedded test technique which provides full at-speed testing of board level interconnect is described. The proposed technique is fully compatible with the IEEE 1149.1 boundary scan standard. The technique extends the standard's architecture to provide for synchronized at-speed timing control of the boundary scan cells so that test data can be applied and captured across the interconnect at system speeds.