Browsing by Author "Chakrabarty, Krishnendu"

The relentless growth in information technology and artificial intelligence (AI) is placing demands on integrated circuits and boards for high performance, added functionality, and low power consumption. As a result, design complexity and integration continue to increase, and emerging devices are being explored. However, these new trends lead to high test cost and challenges associated with semiconductor test.

Machine learning has emerged as a powerful enabler in various application domains, and it provides an opportunity to overcome the challenges associated with expert-based test. Taking the advantages of powerful machine-learning techniques, useful information can be extracted from history testing data, and this information helps facilitate the testing process for both chips and boards.

Moreover, to attain test cost reduction with no test quality degradation, adaptive methods for testing are now being advocated. In conventional testing methods, variations among different chips and different boards are ignored. As a result, the same test items are applied to all chips; online testing is carried out after every fixed interval; immutable fault-diagnosis models are used for all boards. In contrast, adaptive methods observe changes in the distribution of testing data and dynamically adjust the testing process, and hence reduce the test cost. In this dissertation, we study solutions for both chip-level test and board-level test. Our objective is to design the most proper solutions for adapting machine-learning techniques to testing area.

For chip-level test, the dissertation first presents machine learning-based adaptive testing to drop unnecessary test items and reduce the test cost in high-volume chip manufacturing. The proposed testing framework uses the parametric test results from circuit probing test to train a quality-prediction model, partitions chips into different groups based on the predicted quality, and selects the different important test items for each group of chips. To achieve the same defect level as in prior work on adaptive testing, the proposed fine-grained adaptive testing method significantly reduces test cost.

Besides CMOS-based chips, emerging devices (e.g., resistive random access memory (ReRAM)) are being explored to implement AI chips with high energy efficiency. Due to the immature fabrication process, ReRAMs are vulnerable to dynamic faults. Instead of periodically interrupting the computing process and carrying out the testing process, the dissertation presents an efficient method to detect the occurrence of dynamic faults in ReRAM crossbars. This method monitors an indirect measure of the dynamic power consumption of each ReRAM crossbar, determines the occurrence of faults when a changepoint is detected in the monitored power-consumption time series. This model also estimates the percentage of faulty cells in a ReRAM crossbar by training a machine learning-based predictive model. In this way, the time-consuming fault localization and error recovery steps are only carried out when a high defect rate is estimated, and hence the test time is considerably reduced.

For board-level test, the cost associated with the diagnosis and repair due to board-level failures is one of the highest contributors to board manufacturing cost. To reduce the cost associated with fault diagnosis, a machine learning-based diagnosis workflow has been developed to support board-level functional fault identification in the dissertation. In a production environment, the large volume of manufacturing data comes in a streaming format and may exhibit a time-dependent concept drift. In order to process streaming data and adapt to concept drifts, instead of using an immutable diagnosis model, this dissertation also presents the method that uses an online learning algorithm to incrementally update the identification model. Experimental results show that, with the help of online learning, the diagnosis accuracy is improved, and the training time is significantly reduced.

The machine learning-based diagnosis workflow can identify board-level functional faults with high accuracy. However, the prediction accuracy is low when a new board has a limited amount of fail data and repair records. The dissertation presents a diagnosis system that can utilize domain-adaptation algorithms to transfer the knowledge learned from a mature board to a new board. Domain adaptation significantly reduces the requirement for the number of repair records from the new board, while achieving a relatively high diagnostic accuracy in the early stage of manufacturing a new product. The proposed domain adaptation workflow designs a metric to evaluate the similarity between two types of boards. Based on the calculated similarity value, different domain-adaptation algorithms are selected to transfer knowledge and train a diagnosis model.

In summary, this dissertation tackles important problems related to the testing of integrated circuits and boards. By considering variations among different chips or boards, machine learning-based adaptive methods enable the reduction of test cost. The proposed machine learning-based testing methods are expected to contribute to quality assurance and manufacturing-cost reduction in the semiconductor industry.

A three-layer hierarchy is typically used in modern telecommunication systems in order to achieve high performance and reliability. The three layers, namely core, distribution, and access, perform different roles for service fulfillment. The core layer is also referred to as the network backbone, and it is responsible for the transfer of a large amount of traffic in a reliable and timely manner. The network devices (such as routers) in the core layer are vulnerable to hard-to-detect/hard-to-recover errors. For example, the cards that constitute core router systems and the components that constitute a card can encounter hardware failures. Moreover, connectors between cards and interconnects between different components inside a card are also subject to hard faults. Also, since the performance requirement of network devices in the core layer is approaching Tbps levels, failures caused by subtle interactions between parallel threads or applications have become more frequent. All these different types of faults can cause a core router to become incapacitated, necessitating the design and implementation of fault-tolerant mechanisms in the core layer.

Proactive fault tolerance is a promising solution because it takes preventive action before a failure occurs. The state of the system is monitored in a real-time manner. When anomalies are detected, proactive repair actions such as job migration are executed to avoid errors, thereby maintaining the non-stop utilization of the entire system. The effectiveness of proactive fault-tolerance solutions depends on whether abnormal behaviors of core routers can be accurately pinpointed in a timely manner.

This dissertation first presents an anomaly detector for core router systems using correlation-based time series analysis. The proposed technique monitors a set of features obtained from a system deployed in the field. Various types of correlations among extracted features are identified. A set of features with minimum redundancy and maximum relevance are then grouped into different categories based on their statistical characteristics. A hybrid approach is developed to analyze various feature categories using a combination of different anomaly detection methods, leading to the detection of realistic anomalies.

Next, this dissertation presents the design of a changepoint-based anomaly detector such that anomaly detection can be adaptive to changes in the statistical features of data streams. The proposed method first detects changepoints from collected time-series data, and then utilizes these changepoints to detect anomalies. A clustering method is developed to identify a wide range of the normal/abnormal patterns from changepoint windows. Experimental results show that changepoint-based anomaly detector can detect outliers even when the statistical properties of the monitored data change significantly with time.

An efficient data-driven anomaly detector is not adequate to obtain a full picture of the health status of monitored core routers. It is also essential to learn how healthy a core router system is and how different task scenarios can affect the system. Therefore, this dissertation presents a symbol-based health status analyzer that first encodes, as a symbol sequence, the long-term complex time series collected from a number of core routers, and then utilizes the symbol sequence for health analysis. Symbol-based clustering and classification methods are developed to identify the health status.

In order to accurately identify the health status, historical operation data needs to be fully labeled, which is a challenge in the early stages of monitoring. Therefore, this dissertation presents an iterative self-learning procedure for assessing the health status. This procedure first computes a representative feature matrix to capture different characteristics of time-series data. Hierarchical clustering is then utilized to infer labels for the unlabeled dataset. Finally, a classifier is built and iteratively updated using both labeled and unlabeled datasets. Partially-labeled field data collected from a set of commercial core routers are used to experimentally validate the proposed method.

In summary, the dissertation tackles important problems of anomaly detection and health status analysis in complex core router systems. The results emerging from this dissertation provide the first comprehensive set of data-driven resiliency solutions for core router systems. It is anticipated that other high-performance computing systems will also benefit from this framework.

Timing-related defects are becoming increasingly important in nanometer-technology integrated circuits (ICs). Small delay variations induced by crosstalk, process variations, power-supply noise, as well as resistive opens and shorts can potentially cause timing failures in a design, thereby leading to quality and reliability concerns. All these effects are noticeable in today's technologies and they are likely to become more prominent in the next-generation process technologies~\cite{itrs2007}.

The detection of small-delay defects (SDDs) is difficult because of the small size of the introduced delay. Although the delay introduced by each SDD is small, the overall impact can be significant if the target path is critical, has low slack, or includes many SDDs. The overall delay of the path may become larger than the clock period, causing circuit failure or temporarily incorrect results. As a result, the detection of SDDs typically requires fault excitation through least-slack paths. However, widely-used automatic test-pattern generation (ATPG) techniques are not effective at exciting small delay defects. On the other hand, the usage of commercially available timing-aware tools is expensive in terms of pattern count inflation and very high test-generation times. Furthermore, these tools do not target real physical defects.

SDDs are induced not only by physical defects, but also by run-time variations such as crosstalk and power-supply noise. These variations are ignored by today's commercial ATPG tools. As a result, new methods are required for comprehensive coverage of SDDs.

Test data volume and test application time are also major concerns for large industrial circuits. In recent years, many compression techniques have been proposed and evaluated using industrial designs. However, these methods do not target sequence- or timing-dependent failures while compressing the test patterns. Since timing-related failures in high-performance integrated circuits are now increasingly dominated by SDDs, it is necessary to develop timing-aware compression techniques.

This thesis addresses the problem of selecting the most effective test patterns for detecting SDDs. A new gate and interconnect delay-defect probability measure is defined to model delay variations for nanometer technologies. The proposed technique intelligently selects the best set of patterns for SDD detection from a large pattern set generated using timing-unaware ATPG. It offers significantly lower computational complexity and it excites a larger number of long paths compared to previously proposed timing-aware ATPG methods. It is shown that, for the same pattern count, the selected patterns are more effective than timing-aware ATPG for detecting small delay defects caused by resistive shorts, resistive opens, process variations, and crosstalk. The proposed technique also serves as the basis for an efficient SDD-aware test compression scheme. The effectiveness of the proposed technique is highlighted for industrial circuits.

In summary, this research is targeted at the testing of SDDs caused by various underlying reasons. The proposed techniques are expected to generate high-quality and compact test patterns for various types of defects in nanometer ICs. The results of this research are expected to provide low-cost and effective test methods for nanometer devices, and they will lead to higher shipped-product quality.

With fast-decreasing cost of electronic devices and the increasing use of mobile phones, vehicular ad hoc networks (VANETs) are emerging as a popular form of mobile ad hoc networks. VANETs are useful for supporting many applications that improve road safety and enhance driving convenience. Moreover, they also provide real-time data for traffic and travel management.

A VANET is composed of fast-moving mobile nodes (vehicles) that have intermittent and short contacts, fixed road-side units (RSUs) that overhear and broadcast to vehicles, and a central server. Vehicles move along roads, collect data and process them, and disseminate the data to other vehicles and RSUs. The central server aggregates data collected by vehicles, overviews traffic and road status, and generates keys and certificates when necessary. RSUs overhear the data sent from vehicles, broadcast road-side information to vehicles, and communicate to the central server via backhaul network.

With smartphones equipped on vehicles, many interesting research topics emerge, such as traffic-congestion detection and road-bump detection. After data are collected and processed, they are disseminated, such that other vehicles can collaboratively sense the road and traffic status. This motivates the need for data dissemination algorithms in a VANET. Due to the limited bandwidth and insufficient coverage of 3G/4G networks, direct peer-to-peer communication between nodes is important.

Other major concerns in a VANET are security and privacy, since a malicious user can track vehicles, report false alarms, create undesirable traffic congestion, and illegally track vehicles. It is important to ensure the authenticity of messages propagated within VANETs, while protecting the identity and location privacy of vehicles that send messages. This thesis addresses data collection, data processing, dissemination, and security.

First, we estimate the location of vehicles in the scenario of weak/faded GPS signals by using the built-in sensors on smartphones. This method combines landmark recognition and Markov-chain predictions to localize a vehicle. Compared to the coarse-grained localization embedded in an Android smartphone using cellular and wifi signals, this method significantly improves accuracy.

For data dissemination, we observe habitual mobility as well as deviations from habits, characterize their impact on latency, and exploit them through the Diverse Routing (DR) algorithm.

Comparing to existing protocols, we show that DR leads to the least packet delay, especially when users deviate from expected behavior.

An important challenge for secure information dissemination in a VANET lies in Sybil attacks, where a single vehicle fakes multiple identities. We propose the Privacy-perserving Detection of Sybil Attack Protocl (P2DAP) scheme to detect such Sybil attacks. The P2DAP method does not require any vehicle in the network to disclose its identity, hence privacy is preserved at all times. Our results also quantify the inherent trade-off between security, i.e., the detection of Sybil attacks and detection latency, and the privacy provided to the vehicles in the network.

Due to the dependency of P2DAP on RSUs, and the fact that RSUs are usually semi-trusted in VANETs, we need an additional protection mechanism for RSUs. This observation motivates the Predistribution and Local-Collaboration-Based Authentication (PLCA) scheme, which combines Shamir secret sharing with neighborhood collaboration. In PLCA, the cost of changing the infrastructure is relatively low, and any compromise of RSUs can be quickly detected.

In summary, this thesis addresses problems that are relevant to various stages of the life-cycle of information in a VANET. The proposed solution handle data collection, data processing and information extraction, data dissemination, and security/privacy issues. Together, these adverses contribute to a secure and efficient environment for VANET, such that better driving experience and safety can be achieved.

Microfluidic biochips have now come of age, with applications to biomolecular recognition for high-throughput DNA sequencing, immunoassays, and point-of-care clinical diagnostics. In particular, digital microfluidic biochips, which use electrowetting-on-dielectric to manipulate discrete droplets (or "packets of biochemical payload") of picoliter volumes under clock control, are especially promising. The potential applications of biochips include real-time analysis for biochemical reagents, clinical diagnostics, flash chemistry, and on-chip DNA sequencing. The ease of reconfigurability and software-based control in digital microfluidics has motivated research on various aspects of automated chip design and optimization.

This thesis research is focused on facilitating advances in on-chip bioassays, enhancing the automated use of digital microfluidic biochips, and developing an "intelligent" microfluidic system that has the capability of making on-line re-synthesis while a bioassay is being executed. This thesis includes the concept of a "cyberphysical microfluidic biochip" based on the digital microfluidics hardware platform and on-chip sensing technique. In such a biochip, the control software, on-chip sensing, and the microfluidic operations are tightly coupled. The status of the droplets is dynamically monitored by on-chip sensors. If an error is detected, the control software performs dynamic re-synthesis procedure and error recovery.

In order to minimize the size and cost of the system, a hardware-assisted error-recovery method, which relies on an error dictionary for rapid error recovery, is also presented. The error-recovery procedure is controlled by a finite-state-machine implemented on a field-programmable gate array (FPGA) instead of a software running on a separate computer. Each state of the FSM represents a possible error that may occur on the biochip; for each of these errors, the corresponding sequence of error-recovery signals is stored inside the memory of the FPGA before the bioassay is conducted. When an error occurs, the FSM transitions from one state to another, and the corresponding control signals are updated. Therefore, by using inexpensive FPGA, a portable cyberphysical system can be implemented.

In addition to errors in fluid-handling operations, bioassay outcomes can also be erroneous due the uncertainty in the completion time for fluidic operations. Due to the inherent randomness of biochemical reactions, the time required to complete each step of the bioassay is a random variable. To address this issue, a new "operation-interdependence-aware" synthesis algorithm is proposed in this thesis. The start and stop time of each operation are dynamically determined based on feedback from the on-chip sensors. Unlike previous synthesis algorithms that execute bioassays based on pre-determined start and end times of each operation, the proposed method facilitates "self-adaptive" bioassays on cyberphysical microfluidic biochips.

Another design problem addressed in this thesis is the development of a layout-design algorithm that can minimize the interference between devices on a biochip. A probabilistic model for the polymerase chain reaction (PCR) has been developed; based on the model, the control software can make on-line decisions regarding the number of thermal cycles that must be performed during PCR. Therefore, PCR can be controlled more precisely using cyberphysical integration.

To reduce the fabrication cost of biochips, yet maintain application flexibility, the concept of a "general-purpose pin-limited biochip" is proposed. Using a graph model for pin-assignment, we develop the theoretical basis and a heuristic algorithm to generate optimized pin-assignment configurations. The associated scheduling algorithm for on-chip biochemistry synthesis has also been developed. Based on the theoretical framework, a complete design flow for pin-limited cyberphysical microfluidic biochips is presented.

In summary, this thesis research has led to an algorithmic infrastructure and optimization tools for cyberphysical system design and technology demonstrations. The results of this thesis research are expected to enable the hardware/software co-design of a new class of digital microfluidic biochips with tight coupling between microfluidics, sensors, and control software.

Microfluidic biochips are now being used for biochemical applications such as high-throughput DNA sequencing, point-of-care clinical diagnostics, and immunoassays. In particular, digital microfluidic biochips (DMFBs) are especially promising. They manipulate liquid as discrete droplets of nanoliter or picoliter volumes based on the principle of electrowetting-on-dielectric under voltage-based electrode actuation. DMFBs have been commercially adopted for sample preparation and clinical diagnostics. Techniques have also been developed for high-level synthesis, module placement, and droplet routing.

However, reliability is a major concern in the use of DMFBs for laboratory protocols. In addition to manufacturing defects and imperfections, faults can also arise during a bioassay. For example, excessive or prolonged actuation voltage may lead to electrode breakdown and charge trapping, and DNA fouling may lead to the malfunction of electrodes. Faults may eventually result in errors in droplet operations. If an unexpected error appears during an experiment, the outcome of the experiment will be incorrect. The repetition of an experiment leads to wastage of valuable reagents and time.

Therefore, it is necessary to ensure the correctness of the hardware and bioassay execution on the biochip. In this thesis, we focus on three types of reliability: biochip testing, error/fault recovery, and fault-tolerant synthesis. First, when a biochip is fabricated, defects might occur in parts of the biochip. Therefore, our objective is to develop biochip testing methods to detect and locate faults. Second, to faults that appear during droplet operation or in the hardware, we develop error-recovery procedures and redundancy solutions. Finally, we develop fault-tolerant synthesis techniques so that even if faults occur during droplet operations (e.g., unbalance splitting), the bioassay can proceed unimpeded. The proposed solutions are applied to two new types of biochip platforms, namely micro-electrode-dot-array (MEDA) and digital acoustofluidics.

Digital microfluidic biochips (DMFBs) are revolutionizing many biochemical analysis procedures, e.g., high-throughput DNA sequencing and point-of-care clinical diagnosis. However, today's DMFBs suffer from several limitations: (1) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner; (2) the lack of integrated sensors for real-time detection; (3) the need for special fabrication processes and the associated reliability/yield concerns.

To overcome the above limitations, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have recently been proposed. Unlike conventional digital microfluidics, where electrodes of equal size are arranged in a regular pattern, the MEDA architecture is based on the concept of a sea-of-micro-electrodes. The MEDA architecture allows microelectrodes to be dynamically grouped to form a micro-component that can perform different microfluidic operations on the chip.

Design-automation tools can reduce the difficulty of MEDA biochip design and help to ensure that the manufactured biochips are versatile and reliable. In order to fully exploit MEDA-specific advantages (e.g., real-time droplet sensing), new design, optimization, and test problems are tackled in this dissertation.

The dissertation first presents a droplet-size aware synthesis approach that can configure the target bioassay on a MEDA biochip. The proposed synthesis method targets reservoir placement, operation scheduling, module placement, and routing of droplets of various sizes. An analytical model for droplet velocity is proposed and experimentally validated using a fabricated MEDA chip.

Next, this dissertation presents an efficient error-recovery strategy to ensure the correctness of assays executed on MEDA biochips. By exploiting MEDA-specific advances in droplet sensing, the dissertation presents a novel probabilistic timed automata (PTA)-based error-recovery technique to dynamically reconfigure the biochip using real-time data provided by on-chip sensors. An on-line synthesis technique and a control flow are also proposed to connect local-recovery procedures with global error recovery for the complete bioassay.

A potentially important application of MEDA biochips lies in sample preparation via a series of dilution steps. Sample preparation in digital microfluidic biochips refers to the generation of droplets with target concentrations for on-chip biochemical applications. The dissertation presents the first droplet size-aware and error-correcting sample-preparation method for MEDA biochips. In contrast to previous methods, the proposed approach considers droplet sizes and incorporates various mixing models in sample preparation.

In order to ensure high confidence in the outcome of biochemical experiments, MEDA biochips must be adequately tested before they can be used for bioassay execution. The dissertation presents efficient structural and functional test techniques for MEDA biochips. The proposed structural test techniques can effectively detect defects and identify faulty microcells, and the proposed functional test techniques address fundamental fluidic operations on MEDA biochips.

In summary, the dissertation tackles important problems related to key stages of MEDA chip design and usage. The results emerging from this dissertation provide the first set of comprehensive design-automation solutions for MEDA biochips. It is anticipated that MEDA chip users will also benefit from these optimization methods.

As integrated circuits (ICs) continue to scale to smaller dimensions, long interconnects

have become the dominant contributor to circuit delay and a significant component of

power consumption. In order to reduce the length of these interconnects, 3D integration

and 3D stacked ICs (3D SICs) are active areas of research in both academia and industry.

3D SICs not only have the potential to reduce average interconnect length and alleviate

many of the problems caused by long global interconnects, but they can offer greater design

flexibility over 2D ICs, significant reductions in power consumption and footprint in

an era of mobile applications, increased on-chip data bandwidth through delay reduction,

and improved heterogeneous integration.

Compared to 2D ICs, the manufacture and test of 3D ICs is significantly more complex.

Through-silicon vias (TSVs), which constitute the dense vertical interconnects in a

die stack, are a source of additional and unique defects not seen before in ICs. At the same

time, testing these TSVs, especially before die stacking, is recognized as a major challenge.

The testing of a 3D stack is constrained by limited test access, test pin availability,

power, and thermal constraints. Therefore, efficient and optimized test architectures are

needed to ensure that pre-bond, partial, and complete stack testing are not prohibitively

expensive.

Methods of testing TSVs prior to bonding continue to be a difficult problem due to test

access and testability issues. Although some built-in self-test (BIST) techniques have been

proposed, these techniques have numerous drawbacks that render them impractical. In this dissertation, a low-cost test architecture is introduced to enable pre-bond TSV test through

TSV probing. This has the benefit of not needing large analog test components on the die,

which is a significant drawback of many BIST architectures. Coupled with an optimization

method described in this dissertation to create parallel test groups for TSVs, test time for

pre-bond TSV tests can be significantly reduced. The pre-bond probing methodology is

expanded upon to allow for pre-bond scan test as well, to enable both pre-bond TSV and

structural test to bring pre-bond known-good-die (KGD) test under a single test paradigm.

The addition of boundary registers on functional TSV paths required for pre-bond

probing results in an increase in delay on inter-die functional paths. This cost of test

architecture insertion can be a significant drawback, especially considering that one benefit

of 3D integration is that critical paths can be partitioned between dies to reduce their delay.

This dissertation derives a retiming flow that is used to recover the additional delay added

to TSV paths by test cell insertion.

Reducing the cost of test for 3D-SICs is crucial considering that more tests are necessary

during 3D-SIC manufacturing. To reduce test cost, the test architecture and test

scheduling for the stack must be optimized to reduce test time across all necessary test

insertions. This dissertation examines three paradigms for 3D integration - hard dies, firm

dies, and soft dies, that give varying degrees of control over 2D test architectures on each

die while optimizing the 3D test architecture. Integer linear programming models are developed

to provide an optimal 3D test architecture and test schedule for the dies in the 3D

stack considering any or all post-bond test insertions. Results show that the ILP models

outperform other optimization methods across a range of 3D benchmark circuits.

In summary, this dissertation targets testing and design-for-test (DFT) of 3D SICs.

The proposed techniques enable pre-bond TSV and structural test while maintaining a

relatively low test cost. Future work will continue to enable testing of 3D SICs to move

industry closer to realizing the true potential of 3D integration.

Very deep sub-micron process technologies are leading to increasing defect rates for integrated circuits (ICs) and multi-chip boards. To ensure the quality of test patterns and more effective defect screening, functional tests, delay tests, and n-detect tests are commonly used in industry for detecting unmodeled defects. However, the resulting test data volume and test application time are prohibitively high. Moreover, functional tests suffer from low defect coverage since they are mostly derived in practice from existing design-verification test sequences. Another challenge is that it is hard to find the root cause for board-level functional failures caused by various types of unmodeled defects. Therefore, there is a need for efficient testing, design-for-testability (DFT), and fault diagnosis methods to target these unmodeled defects.

To address the problem of high test data volume, a number of test ompression methods have been proposed in the literature based on Linear-Feedback-Shift-Register (LFSR) reseeding. A seed can be computed for each test cube by solving a system of linear equations based on the feedback polynomial of the LFSR. To improve the effectiveness of these seeds for unmodeled defects, this thesis shows how the recently proposed output-deviations metric can be used to select appropriate LFSR seeds. To further reduce the requirement for automatic test equipment (ATE) memory, the thesis describes a DFT technique for increasing the effectiveness of LFSR reseeding for unmodeled defects, which relies on seed selection using the output-deviations metric and the on-chip augmentation of seeds using simple bit-operations.

Functional test sequences are often used in manufacturing testing to target defects that are not detected by structural test. In order to reduce the test application time caused by long functional test, which is needed to obtain high defect coverage, a deviation-based method to grade functional test sequences at register transfer (RT)-level is presented. The effectiveness of the proposed method is evaluated by the correlation between the RT-level deviations and gate-level fault coverage. It is also evaluated on the basis of coverage ramp-up data. Since functional test usually suffer from low defect coverage, there is a need to increase their effectiveness using DFT techniques. A DFT method has therefore been developed--it uses the register-transfer level (RTL) output-eviations metric to select observation points for an RTL design and a given functional test sequence.

A common scenario in industry is "No Trouble Found" (NTF), which means that each chip on the board passes the ATE test while it fails during board-level test. In such case, it is necessary to perform diagnosis at board-level to find the root cause. A promising approach to address this problem is to carry out fault diagnosis in two phases--suspect faulty components on the board or modules within components are first identified and ranked, and then fine-grained diagnosis is used to target the suspect blocks in ranked order. In this thesis, a new method based on dataflow analysis and Dempster-Shafer theory is presented for ranking faulty blocks in the first phase of diagnosis.

To find the root cause of NTF, an innovative functional test approach and DFT methods have been developed for the detection of board-level functional failures. These DFT and test methods allow us to reproduce and detect functional failures in a controlled deterministic environment, which can provide ATE tests to the supplier for early screening of defective parts.

In summary, this research is targeted at the testing, DFT, and diagnosis of unmodeled defects. The proposed techniques are expected to provide high-quality and compact test patterns, and effective DFT methods for various types of defects in integrated circuits. It is also expected to provide accurate diagnosis to find the root cause of defects in multi-chip boards.

The ubiquitous application of DNNs has led to a rise in demand for custom artificial intelligence (AI) accelerators. Domain-specific AI accelerators for machine-learning inferencing applications are homogeneous designs composed of thousands of identical compute cores, or processing elements (PEs), that interface with the on-chip memory (such as local and global buffers). Accelerators can be classified on the basis of two major use-cases: training and inferencing. Inferencing is carried out by using AI accelerators on edge devices as well as in datacenters. They are being deployed for inferencing in autonomous driving, manufacturing automation, and navigation. Many such use-cases require high reliability. However, DNN inferencing applications are inherently fault-tolerant with respect to structural faults in the hardware; it has been shown that many faults are not functionally critical, i.e., they do not lead to any significant error in inferencing. As a result, testing for all faults in an accelerator chip is an "over-kill". Methods of functional criticality assessment need to be devised for low-cost testing of large AI chips. Moreover, testing homogeneous array-based AI accelerators by running automatic test pattern generation (ATPG) at the array level results in a high CPU time and pattern count. Current test methods do not fully exploit the regular dataflow in the accelerators. Hence, we plan on developing a "constant-testable" solution wherein a small test-pattern set is generated for one PE and reused for testing all other PEs.

Deep neural net (DNN)-driven inferencing applications such as image classification are inherently fault-tolerant with respect to structural faults; it has been shown that many faults are not functionally critical, i.e., they do not lead to any significant error in inferencing. This dissertation proposes low-cost structural and functional test methods for AI accelerators. Incorporation of the knowledge of fault criticality in testing enables the application of dedicated test effort for functionally critical faults. The dissertation utilizes supervised learning-driven DNNs, graph convolutional networks (GCNs), and neural twins of digital logic circuits to evaluate the functional criticality of faults in the gate-level netlist of an inferencing accelerator, thereby bypassing the need for computationally expensive brute-force fault simulations.

The generation of labeled data for supervised learning introduces prohibitive computation costs if the labeling process involves time-consuming simulations. For criticality analysis, a large number of fault simulations are needed to collect sufficient information about critical and benign faults. High runtime requirements for collecting sufficient labeled data become the bottleneck in supervised learning-driven fault-criticality analysis. This dissertation presents methodologies that reduce the amount of labeled and balanced data required for accurate classifier training.

Resistive-oxide random-access memory (RRAM) devices constitute a promising technology for building neuromorphic accelerator hardware due to their processing-in-memory (neuromorphic) abilities. The fundamental matrix-multiply operations in AI accelerators can be executed with reduced latency and power consumption by RRAM cells; however, they are known to suffer from high defect rates that contribute to faulty behavior. It is therefore important to analyze RRAM fault models and understand the root causes of defects and variations. In this dissertation, we present a physics-based classification of RRAM fault origins for dense RRAM crossbars---high density is a requirement for the training and inferencing of large neural networks with a high throughput. In this report, we present insights into the RRAM fault origins, which provide valuable feedback for the fabrication and design of RRAM-based accelerators. In addition to fault analysis, we need to tolerate faulty RRAM cells in a crossbar to ensure intended system operation---especially when crossbars suffer from low-to-medium defect densities and it is not economically viable to discard the entire crossbar. Although software-based fault-tolerance schemes have been proposed in the literature, more efficient fault tolerance for RRAM crossbars can be achieved through innovations in the hardware design. The dissertation presents the architecture of a novel processing element to tolerate faults in binary RRAM-based crossbars for in-memory computing.

Monolithic 3D (M3D) ICs have emerged as suitable platforms for high-density vertical integration of large system-on-chips (SoCs) like domain-specific and neuromorphic inferencing accelerators, with significant improvement in power, performance, and area (PPA) over 2D and conventional 3D-stacked ICs. However, the immature M3D fabrication process is prone to defects (especially in the inter-layer vias (ILVs)) and inter-tier process variations. In this dissertation, we present state-of-the-art low-cost built-in self-test (BIST) solutions for detecting and localizing both hard and resistive (small-delay) defects in ILVs. In addition to testing ILVs in high-density and realistic M3D layouts, tier-level fault localization is needed for yield ramp-up prior to high-volume production of M3D accelerator ICs. Due to overhead concerns, only a limited number of observation points can be inserted on the outgoing ILVs of an M3D tier for fault localization. This dissertation introduces NodeRank, an intelligent graph-theoretic algorithm, for observation-point insertion on an optimal set of outgoing ILVs in an M3D tier which lead to an increase in the diagnosability of detected faults in the M3D design.

In summary, the dissertation addresses important problems related to the functional impact of hardware faults in machine learning applications, low-cost test and diagnosis of accelerator faults, technology bring-up and fault tolerance for RRAM-based neuromorphic engines, and design-for-testability (DfT) for high-density M3D ICs. The insights and findings resulting from this dissertation are anticipated to lead to the fabrication of reliable accelerator ICs supported by low-cost DfT infrastructure.

The semiconductor industry continues to relentlessly advance silicon technology scaling into the deep-submicron (DSM) era. High integration levels and structured design methods enable complex systems that can be manufactured in high volume. However, due to increasing integration densities and high operating speeds, subtle manifestation of defects leads to functional failures at the board level. Functional fault diagnosis is, therefore, necessary for board-level product qualification. However, ambiguous diagnosis results can lead to long debug times and wrong repair actions, which significantly increase repair cost and adversely impact yield.

A state-of-the-art diagnosis system involves several key components: (1) design of functional test programs, (2) collection of functional-failure syndromes, (3) building of the diagnosis engine, (4) isolation of root causes, and (5) evaluation of the diagnosis engine. Advances in each of these components can pave the way for a more effective diagnosis system, thus improving diagnosis accuracy and reducing diagnosis time. Machine-learning techniques offer an unprecedented opportunity to develop an automated and adaptive diagnosis system to increase diagnosis accuracy and speed. This dissertation targets all the above components of an advanced diagnosis system by leveraging various machine-learning techniques.

This thesis first describes a diagnosis system based on support-vector machines (SVMs), multi-kernel SVMs (MK-SVMs) and incremental learning. The MK-SVM method leverages a linear combination of single kernels to achieve accurate root-cause isolation. The MK-SVMs thus generated also can be updated based on incremental learning. Furthermore, a data-fusion technique, namely majority-weighted voting, is used to leverage multiple learning techniques for diagnosis.

The diagnosis time is considerable for complex boards due to the large number of syndromes that must be used to ensure diagnostic accuracy. Syndrome collection and analysis are major bottlenecks in state-of-the-art diagnosis procedures. Therefore, this thesis describes an adaptive diagnosis method based on decision trees (DT). The number of syndromes required for diagnosis can be significantly reduced compared to the number of syndromes used for system training. Furthermore, an incremental version of DTs is used to facilitate online learning, so as to bridge the knowledge obtained at test-design stage with the knowledge gained during volume production.

This dissertation also includes an evaluation and enhancement framework based on information theory for guiding diagnosis systems using syndrome and root-cause analysis. Syndrome analysis based on subset selection provides a representative set of syndromes. Root-cause analysis measures the discriminative ability of differentiating a given root cause from others. The metrics obtained from the proposed framework can provide guidelines for test redesign to enhance diagnosis. In addition, traditional diagnosis systems fail to provide appropriate repair suggestions when the diagnostic logs are fragmented and some syndromes are not available. The feature of handling missing syndromes based on imputation methods has therefore been added to the diagnosis system.

Finally, to tackle the bottleneck of data acquisition during the initial product ramp-up phase, a knowledge-discovery method and a knowledge-transfer method are proposed for enriching the training data set, thus facilitating board-level functional fault diagnosis. In summary, this dissertation targets the realization of an automated diagnosis system with the features of high accuracy, low diagnosis time, self-evaluation, self-learning, and ability of selective learning from other diagnosis systems. Machine learning and information-theoretic techniques have been adopted to enable the above-listed features. The proposed diagnosis system is expected to contribute to quality assurance, accelerated product release, and manufacturing-cost reduction in the semiconductor industry.

Advances in the miniaturization of microelectromechanical components have led to battery powered and inexpensive sensor nodes, which can be networked in an ad hoc manner to perform distributed sensing and information processing. While sensor networks can be deployed in inhospitable terrain to provide continuous monitoring and processing capabilities for a wide range of applications, sensor nodes are severely resource-constrained; they typically run on batteries and have a small amount of memory. Therefore, energy-efficient and lightweight protocols are necessary for distributed information processing in these networks.

The data provided by a sensor node is often useful only in the context of the location of the data source. Thus, sensor networks rely on localization schemes to provide location information to sensor nodes. The premise of this thesis is that location-aware protocols, which are based on the assumption that sensor nodes can estimate their location, improve the efficiency of data gathering and resource utilization of wireless sensor networks. Location-awareness improves the energy-efficiency of the protocols needed for routing, transport, data dissemination and self-organization of sensor networks. Existing sensor network protocols typically do not use location information effectively, hence they are not energy-efficient. In this thesis, we show how location information can be leveraged in novel ways in sensor network protocols to achieve energy efficiency. The contributions of this thesis are in four important areas related to network protocol design for wireless sensor networks: 1) self-organization; 2) data dissemination or node reprogramming; 3) service differentiation; and 4) data collection. Work on self-organization (SCARE) and data dissemination (LAF) was carried out from 2002 to 2004 and the work on service differentiation (SensiQoS) and data collection (HTDC) was carried out from 2004 to 2009.

This thesis first presents a new approach for self-configuration of ad hoc sensor networks. The self-configuration of a large number of sensor nodes requires a distributed solution. We propose a scalable self-configuration and adaptive reconfiguration (SCARE) algorithm that exploits the redundancy in sensor networks to extend the lifetime of the network. SCARE distributes the set of nodes in the sensor network into subsets of coordinator nodes and non-coordinator nodes. While coordinator nodes stay awake, provide coverage, and perform multi-hop routing in the network, non-coordinator nodes go to sleep. When nodes fail, SCARE adaptively re-configures the network by selecting appropriate non-coordinator nodes to become coordinators and take over the role of failed coordinators. This scheme only needs local topology information and uses simple data structures in its implementation. SCARE organizes nodes into coordinator and non-coordinator nodes. A recent approach, termed Ripples, has improved upon the selforganization and reconfiguration mechanism proposed in SCARE. It uses a lightweight clustering algorithm to elect cluster heads instead of coordinator nodes based on location information as proposed by SCARE. Ripples selects fewer cluster-head nodes compared to the number of coordinator nodes elected by SCARE by varying the cluster radius and consequently realizes more energy savings while providing comparable sensing coverage.

This thesis next presents an energy-efficient protocol for data dissemination in sensor networks. Sensor networks also enable distributed collection and processing of sensed data. These networks are usually connected to the outside world with base stations or access points through which a user can retrieve the sensed data for further inference and action. Dissemination of information is a challenging problem in sensor networks because of resource constraints. Conventional methods use classical flooding for disseminating data in a sensor network. However, classical flooding suffers from disadvantages such as the broadcast storm problem. We have proposed an energy-efficient scheme that uses the concept of virtual grids to partition (self-configure) the set of nodes into groups of gateway nodes and internal nodes. While gateway nodes forward the packets across virtual grids, internal nodes forward the packets within a virtual grid. The proposed location-aided flooding protocol (LAF) reduces the number of redundant transmissions and receptions by storing a small amount of state information in a packet and inferring the information about nodes that already have the packet from the modified packet header. More recent approach, termed ALAF, has extended the virtual grid concept proposed by LAF to non-uniform sensor network deployments. In ALAF, non-uniform virtual grids are used to improve upon the energy savings provided by LAF and achieve higher energy savings for non-uniform sensor network topologies.

This thesis also addressees the challenging problem of timely data delivery in sensor networks. We propose SensiQos, which leverages the inherent properties of the data generated by events in a sensor network such as spatial and temporal correlation, and realizes energy savings through application-specific in-network aggregation of the data. This data delivery scheme is based on distributed packet scheduling, where nodes make localized decisions on when to schedule a packet for transmission to save energy and to which neighbor they should forward the packet to meet its end-to-end real-time deadline.

Finally, this thesis presents an energy-efficient data collection protocol for sensor networks. It is based on a combination of geographic hash table and mobile sinks that leverage mobile sinks to achieve energy-efficiency in event-driven sensor networks. Next, an analysis of the energy savings realized by the proposed protocol is presented. Simulation results demonstrate significant gains in energy savings for data collection with change in various parameter values.

In summary, this thesis represents an important step towards the design of location-aware energy-efficient protocols for self-configuration, data dissemination, data delivery, and data collection in wireless sensor networks. It is expected to lead to even more efficient protocols for data dissemination, routing, and transport-layer protocols for energy-constrained and failure-prone sensor networks.

Machine learning algorithms are emerging in a wide range of application domains, ranging from autonomous driving, real-time speech translation, and network anomaly detection to pandemic growth and trend prediction. In particular, deep learning, facilitated by highly parallelized processing in hardware accelerators, has received tremendous interest due to its effectiveness for solving complex tasks across different application domains. However, as Moore's law approaches its end, contemporary electronic deep-learning inferencing accelerators show diminishing energy efficiency and have been unable to cope with the performance demands from emerging deep learning applications. To mitigate these issues, there is a need for research efforts on emerging artificial intelligence (AI) accelerators that explore novel transistor technologies with high transconductance at the nanometer technology nodes and low-latency alternatives to metallic interconnects. In this dissertation, we focus on the modeling and optimization of two such technologies: (i) high-speed transistors built using carbon nanotubes (CNTs), and (ii) integrated photonic networks that parallelize matrix-vector multiplications.

CNTs are considered to be leading candidates for realizing beyond-silicon transistors. Owing to the ultra-thin body of CNTs and near-ballistic carrier transport, carbon nanotube field-effect transistors (CNFETs) demonstrate a high on-current/off-current ratio and low subthreshold swing. Integrated circuits (ICs) fabricated from CNFETs are projected to achieve an order of magnitude improvement in the energy-delay product compared to silicon MOSFETs. Despite these advances, several challenges related to yield and performance must be addressed before CNFET-based high-volume production can appear on industry roadmaps. While some of these challenges (e.g., shorts due to metallic CNTs and incorrect logic functionality due to misaligned CNTs) have been addressed, the impact of fabrication process variations and manufacturing defects has largely remained unexplored.

Silicon photonic networks have been known to outperform the existing communication infrastructure (i.e., metallic interconnect) in multi-processor systems-on-chip. In recent years, their application as compute platforms in AI accelerators has attracted considerable attention. Leveraging the inherent parallelism of optical computing, integrated photonic neural networks (IPNNs) can perform the otherwise time-intensive matrix multiplication in O(1) time. Given their competitive integration density, ultra-high energy efficiency, and good CMOS compatibility, IPNNs demonstrate order-of-magnitude higher performance and efficiency than their electronic counterparts. However, the performance of photonic components is highly sensitive to fabrication process variations, manufacturing defects, and crosstalk noise.

In this dissertation, we present the first comprehensive characterization of CNFETs and IPNNs under imperfections. In the case of CNFETs, we consider the impact of fabrication process variations in different device parameters and manufacturing defects that are commonly observed during fabrication. To characterize IPNNs, we consider uncertainties in phase angles and splitting ratios in their building blocks (i.e., Mach--Zehnder interferometers), non-uniform optical loss in the waveguides, and quantization errors due to low-precision encoding of tuned phase angles. Using detailed simulations, we show that these devices can deviate significantly from their nominal performance, even in mature fabrication processes. For example, we show that more than 90% CNFETs can fail due to a 5% change in the CNT diameter. Similarly, the inferencing accuracy of IPNNs can drop below 10% due to uncertainties in the phase angles and splitting ratios.

To ensure the adoption of accelerators based on CNFETs and IPNNs, techniques to test and mitigate the catastrophic impact of imperfections are necessary. As the nature of imperfection in CNFETs vary significantly from those in Si-MOSFETs, existing commercial test pattern generation tools are inefficient when they are applied to ICs with imperfect CNFETs. This thesis presents VADF, a novel CNFET variation-aware test pattern generation tool that significantly improves the efficiency of small delay defect testing under imperfections. Unetched CNTs in the active layer can lead to parasitic FETs that can cause resistive shorts. In addition, we propose ParaMitE, which is a low-cost optimization technique, to reduce the probability of para-FET occurrence and mitigate their impact on performance. The thesis also describes three optimization techniques to improve the power-efficiency and reliability of IPNNs under imperfections. OptimSVD leverages non-uniqueness of the singular value decomposition to minimize the phase angles in an IPNN while guaranteeing zero accuracy loss. We propose CHAMP and LTPrune, which, to the best of our knowledge, are the only photonic hardware-aware magnitude pruning techniques targeted towards IPNNs.

In summary, this dissertation tackles important problems related to the reliability and high-volume yield of next-generation AI accelerators. We show how the criticality of different imperfections can change based on their magnitude and also the location and parameters of the affected components. The methods presented in this dissertation, while targeted towards CNFETs and IPNNs, can be easily extended towards other emerging technologies leveraged for AI hardware. The insights derived from this work can help designers to develop post-silicon AI accelerators that, in addition to demonstrating superior nominal performance, are resilient to inevitable imperfections.

Advances in semiconductor technology and design automation methods have introduced a new era for electronic products. With design sizes in millions of logic gates and operating frequencies in GHz, defects-per-million rates continue to increase, and defects are manifesting themselves in subtle ways. Traditional test methods are not sufficient to guarantee product quality and diagnostic programs cannot rapidly locate the root cause of failure in large systems. Therefore, there is a need for efficient fault diagnosis methods that can provide quality assurance, accelerate new product release, reduce manufacturing cost, and increase product yield.

This thesis research is focused on fault-insertion test (FIT) and fault diagnosis at the board and system levels. FIT is a promising technique to evaluate system reliability and facilitate fault diagnosis. The error-handling mechanism and system reliability can be assessed in the presence of intentionally inserted faults, and artificial faulty scenarios can be used as references for fault diagnosis. However, FIT needs to be deployed under constraints of silicon area, design effort, availability of equipment, and what is actually possible to test from one design to the next. In this research, physical defect modeling is developed to provide an efficient solution for fault-insertion test. Artificial faults at the pin level are created to represent physical defects inside devices. One pin-level fault is able to mimic the erroneous behaviors caused by multiple internal defects. Therefore, system reliability can be evaluated in a more efficient way.

Fault diagnosis is a major concern in the semiconductor industry. As the density and complexity of systems increase relentlessly and the subtle effects of defects in nanometer technologies become more pronounced, fault diagnosis becomes difficult, time-consuming, and ineffective. Diagnosis of functional failure is especially challenging. Moreover, the cost associated with board-level diagnosis is escalating rapidly. Therefore, this thesis presents a multi-pronged approach to improve the efficiency and accuracy of fault diagnosis, including the construction of a diagnostic framework with FIT and Bayesian inference, the extraction of an effective fault syndrome (error flow), the selection of diagnosis-oriented fault-insertion points, and the application of machine learning for intelligent diagnosis.

First, in the inference-based diagnosis framework, FIT is used to create a large number of faulty samples and derive the probabilities needed for the application of Bayes' theorem; next the probability of a fault candidate being the root cause can be inferred based on the given fault syndromes. Results on a case study using an open-source RISC system-on-chip demonstrate the feasibility and effectiveness of the proposed approach. Second, the concept of error flow is proposed to mimic actual data propagation in a circuit, and thus it reflects the logic functionality and timing behavior of circuits. With this additional information, more fault syndromes are distinguishable. Third, diagnosis-oriented fault-insertion points are defined and selected to create the representative and distinguishable syndromes. Finally, machine learning approaches are used to facilitate the debug and repair process. Without requiring the need to understand the complex functionality of the boards, an intelligent diagnostic system is designed to automatically exploit the diagnostic knowledge available from past cases and make decisions on new cases.

In summary, this research has investigated efficient means to perform fault-insertion test and developed automated and intelligent diagnosis methods targeting functional failures at the board level. For a complex circuit board currently in production, the first-time success rate for diagnosis has been increased from 35.63% to 72.64%. It is expected to contribute to quality assurance, product release acceleration, and manufacturing-cost reduction in the semiconductor industry.

With the continuous scaling of transistors to smaller dimensions, it has now become feasible to pack billions of transistors in a single chip. However, interconnect does not scale as well as transistors; hence a significant amount of research is focused today on finding viable alternatives to bus-based interconnects. Coupled with the problem of increasing interconnect delay is the challenge to contain the power footprint. A network-on-chip (NOC) interconnect fabric can alleviate many of these problems, and is therefore viewed as a promising interconnect paradigm of the future. In addition, NOC building blocks consist of reusable components and require minimal design effort in building a large and complex system. In addition to NOCs, 3D integration technology using through-silicon-vias (TSVs) can also alleviate the problems caused by long global interconnects and it offers more innovative design choices compared to traditional 2D integrated circuits (ICs).

Regardless of the choice of interconnect fabric, testing continues to pose a significant challenge. New optimization methods for designing the test-access mechanism (TAM) and minimizing test time are needed. On-chip routing protocols guided by network topology and traffic congestion constraints open new avenues for research in optimizing test-data delivery in NOCs. The thesis describes algorithms for test-data delivery optimization in NOC designs with hundreds of cores, where the NOC is used as a TAM. First, an algorithm based on subset-sum formulation to solve the test-delivery problem in NOCs with arbitrary topology is presented. For the important class of NOCs with a grid topology, the optimization problem is modeled as an NOC partitioning problem and solved using dynamic programming in pseudo-polynomial time. Both the proposed methods yield high-quality results and are scalable to large SOCs with many cores.

Since the proposed methods involve concurrent testing of multiple cores, high power consumption may limit its adoptability in practice; therefore, the thesis also discusses a scheduling algorithm under power constraints using the same dynamic-programming framework. By leveraging the capability of modern multicast routers, the homogeneity of cores is exploited to further minimize test time in such large SOCs.

Three-dimensional (3D) stacking of ICs using through-silicon-vias (TSVs) is a promising integration platform for next-generation ICs. Several complex manufacturing steps involved in the fabrication of 3D-stacked ICs make these chips susceptible to defects. In the scenario where die yields are low, stacking of untested dies further reduces overall yield, and thereby reduces profitability. Moreover, testing at every stage of 3D integration may result in prohibitive test cost. Despite the benefits offered by 3D integration, test cost remains a major concern. The tests have to be inserted at appropriate places in the 3D integration flow. Automated tools are needed to analyze and understand test flows and achieve the desired goal. The thesis describes a generic cost model to account for various test costs involved in 3D integration and formalize the study of test flows as a search problem to minimize the overall cost. An algorithm based on A* to obtain an optimal test flow is presented. Adopting a formal approach to solving the cost-minimization problem provides useful insights that cannot be derived via selective enumeration of a smaller number of candidate test flows.

In 3D-stacked ICs, inaccessibility of TSVs prior to bonding makes it difficult to test the combinational logic between scan flip-flops and TSVs at a pre-bond stage. Addition of wrapper cells on both ends of a TSV solves the testability problem, but at the cost of area overhead, increased latency and performance degradation. The thesis builds on prior work to reuse existing scan flip flops and shows that the general problem of minimizing the wrapper cells is equivalent to the graph-theoretic minimum clique-partitioning problem, and is therefore NP-hard. Efficient heuristic methods are adopted to solve the problem. The proposed methods incorporate a timing-guided and layout-aware approach to address practical timing considerations that were overlooked in prior work. Extensions are also made to post-bond testing stages.

Finally, the thesis describes an end-to-end design of a built-in self-test (BIST) infrastructure for 3D-stacked ICs that facilitates the use of BIST at multiple stages of 3D integration. The proposed BIST design is distributed, reusable, and reconfigurable, hence it is attractive for both pre-bond and post-bond testing. Architectural support for incorporating a static BIST schedule is also provided. Furthermore, two algorithms based on 2D bin packing problem to minimize test time under BIST-resource and power constraints are presented.

In summary, the thesis targets important optimization problems related to test-delivery in manycore SOCs that are assembled using a scalable and flexible integration platform. The proposed research has led to theoretical insights, simulation results, and a set of test and design-for-test methods to make testing effective and feasible from a cost perspective.

Considerable effort has been devoted in recent years to the design and implementation of microfluidic platforms for biomolecular quantitative analysis. However, today's platforms suffer from two major limitations: (1) they were optimized for sample-limited analyses, thus they are inadequate for practical quantitative analysis and the processing of multiple samples through independent pathways; (2) the integrity of these platforms and their biochemical operations is still an open question, since no protection schemes were developed against adversarial contamination or result-manipulation risks.

Design optimization techniques for microfluidics have been studied in recent years, but they overlook the myriad complexities of biomolecular protocols and are yet to make an impact in microbiology research. The realization of microfluidic platforms for real-life quantitative analysis requires: (1) a new optimization flow that is based on the realistic modeling of biomolecular protocols, and (2) a microfluidic security flow that provides a high-level of confidence in the integrity of miniaturized quantitative analysis.

Motivated by the above needs, this dissertation is focused on optimized and trustworthy transfer of benchtop biomolecular analysis, particularly epigenetic studies, to programmable and cyber-physical microfluidic biochips. The dissertation first presents a set of optimization mechanisms that leverages cyber-physical integration to enable real-time execution of multi-sample biomolecular analysis. The proposed methods include a resource-allocation scheme that responds to decisions about the protocol flow, an interactive firmware that collects and analyzes sensor data, and a spatio-temporal reconfiguration technique that aims to enhance the reliability of the microfluidic system. An envisioned design for an Internet-of-Things (IoT)-based microfluidics-driven service is also presented to cope with the complexity of coordinated biomolecular research.

Next, this dissertation advances single-cell protocols by presenting optimized microfluidic methods for high-throughput cell differentiation. The proposed methods target pin-constrained design of reconfigurable microfluidic systems and real-time synthesis of a pool of heterogeneous cells through the complete flow of single-cell analysis. A performance model related to single-cell screening is also presented based on computational fluid-dynamics simulations.

With the increasing complexity of microbiology research, optimized protocol preparation and fault-tolerant execution have become critical requirements in today's biomolecular frameworks. This dissertation presents a design method for reagent preparation for parameter-space exploration. Trade-offs between reagent usage and protocol efficiency are investigated. Moreover, an integrated design for automated error recovery in cyber-physical biochips is demonstrated using a fabricated chip.

In order to ensure high confidence in the outcome of biomolecular experiments, appropriate security mechanisms must be applied to the microfluidic design flow. This dissertation provides an assessment of potential security threats that are unique to biomolecular analysis. Security countermeasures are also proposed at different stages of the biomolecular information flow to secure the execution of a quantitative-analysis framework. Related benchtop studies are also reported.

In summary, the dissertation tackles important problems related to key stages of the biomolecular workflow. The results emerging from this dissertation provide the first set of optimization and security methodologies for the realization of biomolecular protocols using microfluidic biochips.

Microfluidics-based biochips combine electronics with biochemistry to open new application areas such as point-of-care medical diagnostics, on-chip DNA analysis, automated drug discovery and protein crystallization. Bioassays can be mapped to microfluidic arrays using synthesis tools and they can be executed through the electronic manipulation of sample and reagent droplets. The 2007 International Technology Roadmap for Semiconductors articulates the need for innovations in biochip and microfluidics as part of functional diversification ("Higher Value Systems" and "More than Moore"). This document also highlights "Medical" as being a System Driver for 2009 This thesis envisions an automated design flow for microfluidic biochips, in the same way as design automation revolutionized IC design in the 80s and 90s. Electronic design-automation techniques are leveraged whenever possible, and new design-automation solutions are developed for problems that are unique to digital microfluidics. Biochip users (e.g., chemists, nurses, doctors and clinicians) and the biotech/pharmaceutical industry will adapt more easily to new technology if appropriate design tools and in-system automation methods are made available. The thesis is focused on a design automation framework that addresses optimization problems related to layout, synthesis, droplet routing, testing, and testing for digital microfluidic biochips. Optimization goal includes the minimization of time-to-response, chip area, and test complexity. The emphasis here is on practical issues such as defects, fabrication cost, physical constraints, and application-driven design. To obtain robust, easy-to-route chip designs, a unified synthesis method has been developed to incorporate droplet routing and defect tolerance in architectural synthesis and physical design. It allows routing-aware architectural-level design choices and defect-tolerant physical design decisions to be made simultaneously. v In order to facilitate the manufacture of low-cost and disposable biochips, design methods that rely on a small number of control pins have also been developed. Three techniques have been introduced for the automated design of such pin-constraint biochips. First, a droplet-trace-based array partitioning method has been combined with an efficient pin assignment technique, referred to as the "Connect-5 algorithm". The second pin-constrained design method is based on the use of "rows" and "columns" to access electrodes. An efficient droplet manipulation method has been developed for this cross-referencing technique. The method maps the droplet-movement problem to the clique-partitioning problem from graph theory, and it allows simultaneous movement of a large number of droplets on a microfluidic array. The third pin-constrained design technique is referred to as broadcast-addressing. This method provides high throughput for bioassays and it reduces the number of control pins by identifying and connecting control pins with "compatible" actuation sequences. Dependability is another important attribute for microfluidic biochips, especially for safety-critical applications such as point-of-care health assessment, air-quality monitoring, and food-safety testing. Therefore, these devices must be adequately tested after manufacture and during bioassay operations. This thesis presents a cost-effective testing method, referred to as "parallel scan-like test", and a rapid diagnosis method based on test outcomes. The diagnosis outcome can be used for dynamic reconfiguration, such that faults can be easily avoided, thereby enhancing chip yield and defect tolerance. The concept of functional test for digital biochip has also been introduced for the first time in this thesis. Functional test methods address fundamental biochip operations such as droplet dispensing, droplet transportation, mixing, splitting, and capacitive sensing. To facilitate the application of the above testing methods and to increase their effectiveness, the concept of design-for-testability (DFT) for microfluidic biochips has been introduced in this thesis. A DFT method has been proposed that incorporates a test plan into vi the fluidic operations of a target bioassay protocol. The above optimization tools have been used for the design of a digital microfluidic biochip for protein crystallization, a commonly used technique to understand the structure of proteins. An efficient solution-preparation algorithm has been developed to generate a solution-preparation plan that lists the intermediate mixing steps needed to generate target solutions with the required concentrations. A multi-well high-throughput digital microfluidic biochip prototype for protein crystallization has also been designed. In summary, this thesis research has led to a set of practical design tools for digital microfluidics. A protein crystallization chip has been designed to highlight the benefits of this automated design flow. It is anticipated that additional biochip applications will also benefit from these optimization methods.