The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical; however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, “Foundations of Innovative Algorithms for Big Data,” which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a “Sublinear Computation Paradigm.” Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.

The security analysis of Keccak, the winner of SHA-3, has attracted considerable interest. Recently, some attention has been paid to distinguishing Keccak sponge function from random permutation. In EUROCRYPT'17, Huang et al. proposed conditional cube tester to recover the key of Keccak-MAC and Keyak and to construct practical distinguishing attacks on Keccak sponge function up to 7 rounds. In this paper, we improve the conditional cube tester model by refining the formulation of cube variables. By classifying cube variables into three different types and working the candidates of these types of cube variable carefully, we are able to establish a new theoretical distinguisher on 8-round Keccak sponge function. Our result is more efficient and greatly improves the existing results. Finally we remark that our distinguishing attack on the the reduced-round Keccak will not threat the security margin of the Keccak sponge function.

This paper describes latest RF Automated Test Equipment (RF ATE) technologies that include device under test (DUT) connections, a calibration method, and an RF test module mainly focusing on low cost of test (COT). Most important respect for low COT is how achieve a number of simultaneous measurements and short test time as well as a plain calibration. We realized these respects by a newly proposed calibration method and a drastically downsized RF test module with multiple resources and high throughput. The calibration method is very convenient for RF ATE. Major contribution for downsizing of the RF test module is RF circuit technology in form of RF functional system in package (RF-SIPs), resulting in very attractive test solutions.

In this paper, we provide a practical formulation of the problem of identifying all error occurrences and all failed scan cells in at-speed scan based BIST environment. We propose a method that can be used to identify every error when the circuit test frequency is higher than the tester frequency. Our approach requires very little extra hardware for diagnosis and the test application time required to identify errors is a linear function of the frequency ratio between the CUT and the tester.

The partially rotational scan (PRS) technique greatly reduces the amount of data needed for n-detection testing. It also enables at-speed testing using low-speed testers. We designed tester intellectual properties (tester IP) with PRS for Viper and COMET II processors. When PRS was applied to a Viper processor, we obtained test data that provided the same fault coverage as with a set of automatic test pattern generation (ATPG) test vectors, although the amount of test data was 16% that of the ATPG. When the PRS technique was applied to a COMET II processor with full-scan design, we obtained test data that provided the same fault coverage as with a set of ATPG test vectors, although the amount of test data was 10% that of the ATPG. We also estimated hardware overhead and test time.

This paper describes a comprehensive simulation and test environment for prototype LSI verification. We develop a Perl package, ST, for simulation & test of digital circuits. A designer can describe a testbench with the Perl syntax, which can be converted to various kinds of simulators and LSI testers. Parameters such as a target simulator/tester, cycle time and voltage levels can be changed very easily just modifying arguments of subroutines. We also develop DUT boards which consist of a tester-dependent mother board and a package-dependent daughter board. Using ST and the DUT boards, a designer can start verification just after getting fabricated LSIs.

To develop ultra high density magnetic recording systems, a quasi-static system with a reciprocating medium motion against a stand still head was developed for a read/write tester. Double-layered perpendicular recording media and merged GMR heads assembled on a conventional head-gimbal assembly (HGA) were applied to evaluate the read/write performances. A smooth sliding contact motion was achieved, however, the head-to-medium spacing was varied depending on the head motion direction. The spacing in the reverse running direction of the conventional head slider seems to be smaller than that of the flying height in a high-speed spin stand. A merged ring head was suitable for perpendicular magnetic recording in the case of the reverse direction sliding.

This paper describes two digital correction algorithms for ADC nonlinearity, targeted for mixed-signal LSI tester applications: an interpolation algorithm and a stochastic algorithm. Numerical simulations show that our algorithms compensate for ADC nonlinearity as well as missing codes and nonmonotonicity characteristics, and improve ADC SNDR and SFDR.

A practical EB-testing-pad method, that enables higher observability of multilevel wiring LSIs without any increase of chip size, has been evaluated by using actual 0.25-µm SIMOX/CMOS devices. First, an 80k-gate logic LSI with testing pads was developed, and it was proved that observability improves from 17% to 87%. Next, two kinds of gate-chain TEGs (test element groups), with and without testing pads was developed to investigate the influence of testing pads on gate delay. It was found that the circuit delay increase due to the pads is very small, less than 2.7%. It was also found that capacitances from neighboring wires will increase only by at most 3% due to the testing pads. Thus, the testing pad method has been proved to be extremely effective in improving observability without any overhead in design.

The EB tester line delay fault localization algorithm for combinational circuits is proposed where line delay fault probabilities are utilized to narrow fault candidates down to one efficiently. Probabilities for two main causes of line delay faults, defects of contact/vias along interconnections and crosstalk, are estimated through layout analysis. The algorithm was applied to 8 kinds of ISCAS'85 benchmark circuits to evaluate its performance where the guided probe (GP) diagnosis was used as the reference method. The proposed method can cut the number of probed lines to about 30% in average compared with those for the GP method. The total fault localization time was 31% of the time for the GP method and was 6% less than that of our previous method where the fault list generated in concurrent fault simulation is utilized.

A novel testing-pad placement method has been developed to greatly improve E-beam observability for multi-level wiring LSIs. In the method, testing pads connecting a lower-metal-layer wire with a top-metal-layer electrode are positioned in the design layout, making removal of the insulator unnecessary. The method features i) pad placement in unoccupied areas in mask patterns to avoid increases in chip size, ii) minimized pad size through the use of stacked vias so that the pads can be placed on as many wire nodes as possible, iii) placement as far as possible from the nearby wires to avoid local field effects, and iv) allocation of one testing pad to one circuit node to minimize the number of testing pads. These measures give us a practical pad-placement method, that has little influence on LSI design. It was shown that the proposed method yielded a dramatic improvement of observability from 13-33% to 88-99% in actual layouts of 0.25-µm ASICs with 20k, 120k, and 390k gates. It was also found that local field effects from nearby wires are negligible for almost all the testing pads. This approach will enable the use of E-beam testing on LSIs made with 0.25-µm technology and the even more sophisticated process technologies to come.

A novel method for the guided-probe diagnosis of high-performance LSIs containing macrocells, which have no internal netlist essential to the diagnosis, has been developed. In this method, the macrocell netlist is derived from its layout by extracting a leaf-cell-level netlist and is combined with the original one. Logic models for the leaf cells in the extracted netlist are also generated to obtain the logic-simulation data in the macrocells. The logic modeling is extended for application to memory macrocells, based on the idea that analog-behavior leaf cells in the memory macrocells are converted into logically equivalent circuits for logic simulation. Specifically, sense amplifiers and wired-or connections on bit lines are replaced with the corresponding logic-behavior models. The proposed method has been successfully applied to actual design data of LSIs containing macrocells, and it has been verified that it enables fault paths inside macrocells to be accurately traced and that the logic models give good timing resolution in the logic simulation. Using the proposed method, LSIs containing macrocells will be able to be diagnosed regardless of the macrocell types, without the need for a "golden" device, by an electron-beam guided probe system.

Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that trans form a faulty program into a less faulty program, and show that (2) if a function f has a self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has self-improver that transforms a faulty program into an alomost correct program.

We developed an on-chip memory tester macro using a microprogram ROM BIST circuit. Only slight modification of address buffers, data bus I/O circuits and control clock generators of the memory core circuits was required to implement this BIST macro. We fabricated a 1 Mb DRAM with the BIST, and experimental results showed that the measured shmoo plot of VCC versus the cycle time by the BIST closely agreed with that of a memory tester. Disagreement was caused by test address signal set-up time delay and VOH/VOL differences in both test conditions. The BIST macro will be especially useful for design-for-testability of embedded memories.

In order to evaluate the effect of testing technologies such as electron beam (EB) testing and focused ion beam (FIB) reconstruction on the VLSI development cycle, the VLSI development period and cost are analyzed by using detailed fault models which make possible to take into consideration the effect of EB and FIB techniques. First, the specifications of fabricated VLSIs and the VLSI development cycle are modeled. Next the faults which can be diagnosed by such testing techniques are modeled. By using the parametric model of the VLSI development cycle, the development period and cost are analyzed. In the fault diagnosis stage, the use of an EB tester or the combinational use of an EB tester and an FIB equipment, instead of a traditional mechanical prober is considered. It is seen that the development period and cost are reduced by using EB and FIB diagnosis equipments by a factor of about 3. The effect of scan path method is also evaluated by making use of the same simulation method. Results show that the scan path design is effective for the reduction in both period and cost in the development cycle.

This paper describes a new timing calibration method for IC testers that uses a Timing Calibration Device (TCD). The TCD is a chip fabricated using the same process the device to be tested. Since the TCD has the same assignment pins as the LSI memory device under test (called the "MUT"), it enables an IC tester to evaluate the timing accuracy at the input/output terminal of MUT. The block-select-access time of a 1 K ECL RAM, which is less than 3.0 nanoseconds, has been accurately measured using this device. A timing-calibration subsystem is proposed for IC testers as an application of the TCD. Such a device would achieve precise measurement of high-speed LSI memory devices.