Search

Deriving the detailed synaptic connections of an entire nervous system is the unrealized goal of the nascent field of connectomics. For the fruit fly Drosophila, in particular, we need to dissect the brain, connectives, and ventral nerve cord as a single continuous unit, fix and stain it, and undertake automated segmentation of neuron membranes. To achieve this, we designed a protocol using progressive lowering of temperature dehydration (PLT), a technique routinely used to preserve cellular structure and antigenicity. We combined PLT with low temperature en bloc staining (LTS) and recover fixed neurons as round profiles with darkly stained synapses, suitable for machine segmentation and automatic synapse detection. Here we report three different PLT-LTS methods designed to meet the requirements for FIB-SEM imaging of the Drosophila brain. These requirements include: good preservation of ultrastructural detail, high level of en bloc staining, artifact-free microdissection, and smooth hot-knife cutting to reduce the brain to dimensions suited to FIB-SEM. In addition to PLT-LTS, we designed a jig to microdissect and pre-fix the fly’s delicate brain and central nervous system. Collectively these methods optimize morphological preservation, allow us to image the brain usually at 8 nm per voxel, and simultaneously speed the formerly slow rate of FIB-SEM imaging.

Due to advances in electron microscopy and deep learning, it is now practical to reconstruct a connectome, a description of neurons and the chemical synapses between them, for significant volumes of neural tissue. Smaller past reconstructions were primarily used by domain experts, could be handled by downloading data, and performance was not a serious problem. But new and much larger reconstructions upend these assumptions. These networks now contain tens of thousands of neurons and tens of millions of connections, with yet larger reconstructions pending, and are of interest to a large community of non-specialists. Allowing other scientists to make use of this data needs more than publication—it requires new tools that are publicly available, easy to use, and efficiently handle large data. We introduce neuPrint to address these data analysis challenges. Neuprint contains two major components—a web interface and programmer APIs. The web interface is designed to allow any scientist worldwide, using only a browser, to quickly ask and answer typical biological queries about a connectome. The neuPrint APIs allow more computer-savvy scientists to make more complex or higher volume queries. NeuPrint also provides features for assessing reconstruction quality. Internally, neuPrint organizes connectome data as a graph stored in a neo4j database. This gives high performance for typical queries, provides access though a public and well documented query language Cypher, and will extend well to future larger connectomics databases. Our experience is also an experiment in open science. We find a significant fraction of the readers of the article proceed to examine the data directly. In our case preprints worked exactly as intended, with data inquiries and PDF downloads starting immediately after pre-print publication, and little affected by formal publication later. From this we deduce that many readers are more interested in our data than in our analysis of our data, suggesting that data-only papers can be well appreciated and that public data release can speed up the propagation of scientific results by many months. We also find that providing, and keeping, the data available for online access imposes substantial additional costs to connectomics research.

SummaryThe detection of visual motion enables sophisticated animal navigation, and studies in flies have provided profound insights into the cellular and circuit basis of this neural computation. The fly’s directionally selective T4 and T5 neurons respectively encode ON and OFF motion. Their axons terminate in one of four retinotopic layers in the lobula plate, where each layer encodes one of four cardinal directions of motion. While the input circuitry of the directionally selective neurons has been studied in detail, the synaptic connectivity of circuits integrating T4/T5 motion signals is largely unknown. Here we report a 3D electron microscopy reconstruction, wherein we comprehensively identified T4/T5’s synaptic partners in the lobula plate, revealing a diverse set of new cell types and attributing new connectivity patterns to known cell types. Our reconstruction explains how the ON and OFF motion pathways converge. T4 and T5 cells that project to the same layer, connect to common synaptic partners symmetrically, that is with similar weights, and also comprise a core motif together with bilayer interneurons, detailing the circuit basis for computing motion opponency. We discovered pathways that likely encode new directions of motion by integrating vertical and horizontal motion signals from upstream T4/T5 neurons. Finally, we identify substantial projections into the lobula, extending the known motion pathways and suggesting that directionally selective signals shape feature detection there. The circuits we describe enrich the anatomical basis for experimental and computations analyses of motion vision and bring us closer to understanding complete sensory-motor pathways.

The hemibrain connectome (Scheffer et al., 2020) provides large scale connectivity and morphology information for the majority of the central brain of Drosophila melanogaster. Using this data set, we provide a complete description of the most complex olfactory system studied at synaptic resolution to date, covering all first, second and third-order neurons of the olfactory system associated with the antennal lobe and lateral horn (mushroom body neurons are described in a parallel paper, Li et al., 2020). We develop a generally applicable strategy to extract information flow and layered organisation from synaptic resolution connectome graphs, mapping olfactory input to descending interneurons. This identifies a range of motifs including highly lateralised circuits in the antennal lobe and patterns of convergence downstream of the mushroom body and lateral horn. We also leverage a second data set (FAFB, Zheng et al., 2018) to provide a first quantitative assessment of inter- versus intra-individual stereotypy. Complete reconstruction of select developmental lineages in two brains (three brain hemispheres) reveals striking similarity in neuronal morphology across brains for >170 cell types. Within and across brains, connectivity correlates with morphology. Notably, neurons of the same morphological type show similar connection variability within one brain as across brains; this property should enable a rigorous quantitative approach to cell typing.

The neural circuits responsible for animal behavior remain largely unknown. We summarize new methods and present the circuitry of a large fraction of the brain of the fruit fly Drosophila melanogaster. Improved methods include new procedures to prepare, image, align, segment, find synapses in, and proofread such large data sets. We define cell types, refine computational compartments, and provide an exhaustive atlas of cell examples and types, many of them novel. We provide detailed circuits consisting of neurons and their chemical synapses for most of the central brain. We make the data public and simplify access, reducing the effort needed to answer circuit questions, and provide procedures linking the neurons defined by our analysis with genetic reagents. Biologically, we examine distributions of connection strengths, neural motifs on different scales, electrical consequences of compartmentalization, and evidence that maximizing packing density is an important criterion in the evolution of the fly’s brain., eLife digest Animal brains of all sizes, from the smallest to the largest, work in broadly similar ways. Studying the brain of any one animal in depth can thus reveal the general principles behind the workings of all brains. The fruit fly Drosophila is a popular choice for such research. With about 100,000 neurons – compared to some 86 billion in humans – the fly brain is small enough to study at the level of individual cells. But it nevertheless supports a range of complex behaviors, including navigation, courtship and learning. Thanks to decades of research, scientists now have a good understanding of which parts of the fruit fly brain support particular behaviors. But exactly how they do this is often unclear. This is because previous studies showing the connections between cells only covered small areas of the brain. This is like trying to understand a novel when all you can see is a few isolated paragraphs. To solve this problem, Scheffer, Xu, Januszewski, Lu, Takemura, Hayworth, Huang, Shinomiya et al. prepared the first complete map of the entire central region of the fruit fly brain. The central brain consists of approximately 25,000 neurons and around 20 million connections. To prepare the map – or connectome – the brain was cut into very thin 8nm slices and photographed with an electron microscope. A three-dimensional map of the neurons and connections in the brain was then reconstructed from these images using machine learning algorithms. Finally, Scheffer et al. used the new connectome to obtain further insights into the circuits that support specific fruit fly behaviors. The central brain connectome is freely available online for anyone to access. When used in combination with existing methods, the map will make it easier to understand how the fly brain works, and how and why it can fail to work correctly. Many of these findings will likely apply to larger brains, including our own. In the long run, studying the fly connectome may therefore lead to a better understanding of the human brain and its disorders. Performing a similar analysis on the brain of a small mammal, by scaling up the methods here, will be a likely next step along this path.

The neural circuits responsible for behavior remain largely unknown. Previous efforts have reconstructed the complete circuits of small animals, with hundreds of neurons, and selected circuits for larger animals. Here we (the FlyEM project at Janelia and collaborators at Google) summarize new methods and present the complete circuitry of a large fraction of the brain of a much more complex animal, the fruit fly Drosophila melanogaster. Improved methods include new procedures to prepare, image, align, segment, find synapses, and proofread such large data sets; new methods that define cell types based on connectivity in addition to morphology; and new methods to simplify access to a large and evolving data set. From the resulting data we derive a better definition of computational compartments and their connections; an exhaustive atlas of cell examples and types, many of them novel; detailed circuits for most of the central brain; and exploration of the statistics and structure of different brain compartments, and the brain as a whole. We make the data public, with a web site and resources specifically designed to make it easy to explore, for all levels of expertise from the expert to the merely curious. The public availability of these data, and the simplified means to access it, dramatically reduces the effort needed to answer typical circuit questions, such as the identity of upstream and downstream neural partners, the circuitry of brain regions, and to link the neurons defined by our analysis with genetic reagents that can be used to study their functions.Note: In the next few weeks, we will release a series of papers with more involved discussions. One paper will detail the hemibrain reconstruction with more extensive analysis and interpretation made possible by this dense connectome. Another paper will explore the central complex, a brain region involved in navigation, motor control, and sleep. A final paper will present insights from the mushroom body, a center of multimodal associative learning in the fly brain.

Recent advances in automatic image segmentation and synapse prediction in electron microscopy (EM) datasets of the brain enable more efficient reconstruction of neural connectivity. In these datasets, a single neuron can span thousands of images containing complex tree-like arbors with thousands of synapses. While image segmentation algorithms excel within narrow fields of views, the algorithms sometimes struggle to correctly segment large neurons, which require large context given their size and complexity. Conversely, humans are comparatively good at reasoning with large objects. In this paper, we introduce several semi-automated strategies that combine 3D visualization and machine guidance to accelerate connectome reconstruction. In particular, we introduce a strategy to quickly correct a segmentation through merging and cleaving, or splitting a segment along supervoxel boundaries, with both operations driven by affinity scores in the underlying segmentation. We deploy these algorithms as streamlined workflows in a tool called Neu3 and demonstrate superior performance compared to prior work, thus enabling efficient reconstruction of much larger datasets. The insights into proofreading from our work clarify the trade-offs to consider when tuning the parameters of image segmentation algorithms.

Reconstructing a connectome from an EM dataset often requires a large effort of proofreading automatically generated segmentations. While many tools exist to enable tracing or proofreading, recent advances in EM imaging and segmentation quality suggest new strategies and pose unique challenges for tool design to accelerate proofreading. Namely, we now have access to very large multi-TB EM datasets where (1) many segments are largely correct, (2) segments can be very large (several GigaVoxels), and where (3) several proofreaders and scientists are expected to collaborate simultaneously. In this paper, we introduce NeuTu as a solution to efficiently proofread large, high-quality segmentation in a collaborative setting. NeuTu is a client program of our high-performance, scalable image database called DVID so that it can easily be scaled up. Besides common features of typical proofreading software, NeuTu tames unprecedentedly large data with its distinguishing functions, including: (1) low-latency 3D visualization of large mutable segmentations; (2) interactive splitting of very large false merges with highly optimized semi-automatic segmentation; (3) intuitive user operations for investigating or marking interesting points in 3D visualization; (4) visualizing proofreading history of a segmentation; and (5) real-time collaborative proofreading with lock-based concurrency control. These unique features have allowed us to manage the workflow of proofreading a large dataset smoothly without dividing them into subsets as in other segmentation-based tools. Most importantly, NeuTu has enabled some of the largest connectome reconstructions as well as interesting discoveries in the fly brain.

Extracting a connectome from an electron microscopy (EM) data set requires identification of neurons and determination of connections (synapses) between neurons. As manual extraction of this information is very time-consuming, there has been extensive research efforts to automatically segment the neurons to help guide and eventually replace manual tracing. Until recently, there has been comparatively little research on automatic detection of the actual synapses between neurons. This discrepancy can, in part, be attributed to several factors: obtaining neuronal shapes is a prerequisite for the first step in extracting a connectome, manual tracing is much more time-consuming than annotating synapses, and neuronal contact area can be used as a proxy for synapses in determining connections. However, recent research has demonstrated that contact area alone is not a sufficient predictor of a synaptic connection. Moreover, as segmentation improved, we observed that synapse annotation consumes a more significant fraction of overall reconstruction time (upwards of 50% of total effort). This ratio will only get worse as segmentation improves, gating the overall possible speed-up. Therefore, we address this problem by developing algorithms that automatically detect presynaptic neurons and their postsynaptic partners. In particular, presynaptic structures are detected using a U-Net convolutional neural network (CNN), and postsynaptic partners are detected using a multilayer perceptron (MLP) with features conditioned on the local segmentation. This work is novel because it requires minimal amount of training, leverages advances in image segmentation directly, and provides a complete solution for polyadic synapse detection. We further introduce novel metrics to evaluate our algorithm on connectomes of meaningful size. When applied to the output of our method on EM data from Drosphila, these metrics demonstrate that a completely automatic prediction can be used to effectively characterize most of the connectivity correctly.

The increasing IC manufacturing cost encourages a business model where design houses outsource IC fabrication to remote foundries. Despite cost savings, this model exposes design houses to IC piracy as remote foundries can manufacture in excess to sell on the black market. Recent efforts in digital hardware security aim to thwart piracy by using XOR-based chip locking, cryptography, and active metering. To counter direct attacks and lower the exposure of unlocked circuits to the foundry, we introduce a multiplexor-based locking strategy that preserves test response allowing IC testing by an untrusted party before activation. We demonstrate a simple yet effective attack against a locked circuit that does not preserve test response, and validate the effectiveness of our locking strategy on IWLS 2005 benchmarks.

Understanding memory formation, storage and retrieval requires knowledge of the underlying neuronal circuits. In Drosophila, the mushroom body (MB) is the major site of associative learning. We reconstructed the morphologies and synaptic connections of all 983 neurons within the three functional units, or compartments, that compose the adult MB’s α lobe, using a dataset of isotropic 8 nm voxels collected by focused ion-beam milling scanning electron microscopy. We found that Kenyon cells (KCs), whose sparse activity encodes sensory information, each make multiple en passant synapses to MB output neurons (MBONs) in each compartment. Some MBONs have inputs from all KCs, while others differentially sample sensory modalities. Only 6% of KC>MBON synapses receive a direct synapse from a dopaminergic neuron (DAN). We identified two unanticipated classes of synapses, KC>DAN and DAN>MBON. DAN activation produces a slow depolarization of the MBON in these DAN>MBON synapses and can weaken memory recall. DOI: http://dx.doi.org/10.7554/eLife.26975.001

Reference EPFL-ARTICLE-226946doi:10.1038/nmeth.4151View record in Web of Science Record created on 2017-03-27, modified on 2017-07-13

Recent results have shown the possibility of both reconstructing connectomes of small but biologically interesting circuits and extracting from these connectomes insights into their function. However, these reconstructions were heroic proof-of-concept experiments, requiring person-months of effort per neuron reconstructed, and will not scale to larger circuits, much less the brains of entire animals. In this paper we examine what will be required to generate and use substantially larger connectomes, finding five areas that need increased attention: firstly, imaging better suited to automatic reconstruction, with excellent z-resolution; secondly, automatic detection, validation, and measurement of synapses; thirdly, reconstruction methods that keep and use uncertainty metrics for every object, from initial images, through segmentation, reconstruction, and connectome queries; fourthly, processes that are fully incremental, so that the connectome may be used before it is fully complete; and finally, better tools for analysis of connectomes, once they are obtained.

Animal behaviour arises from computations in neuronal circuits, but our understanding of these computations has been frustrated by the lack of detailed synaptic connection maps, or connectomes. For example, despite intensive investigations over half a century, the neuronal implementation of local motion detection in the insect visual system remains elusive. Here we develop a semi-automated pipeline using electron microscopy to reconstruct a connectome, containing 379 neurons and 8,637 chemical synaptic contacts, within the Drosophila optic medulla. By matching reconstructed neurons to examples from light microscopy, we assigned neurons to cell types and assembled a connectome of the repeating module of the medulla. Within this module, we identified cell types constituting a motion detection circuit, and showed that the connections onto individual motion-sensitive neurons in this circuit were consistent with their direction selectivity. Our results identify cellular targets for future functional investigations, and demonstrate that connectomes can provide key insights into neuronal computations. Reconstruction of a connectome within the fruitfly visual medulla, containing more than 300 neurons and over 8,000 chemical synapses, reveals a candidate motion detection circuit; such a circuit operates by combining displaced visual inputs, an operation consistent with correlation based motion detection. Three papers in this issue of Nature use the retina as a model for mapping neuronal circuits from the level of individual synaptic contacts to the long-range scale of dendritic interactions. Helmstaedter et al. used electron microscopy to map a mammalian retinal circuit of close to a thousand neurons. The work reveals a new type of retinal bipolar neuron and suggests functional mechanisms for known visual computations. The other two groups study the detection of visual motion in the Drosophila visual system — a classic neural computation model. Takemura et al. used semi-automated electron microscopy to reconstruct the basic connectome (8,637 chemical synapses among 379 neurons) of Drosophila's optic medulla. Their results reveal a candidate motion detection circuit with a wiring plan consistent with direction selectivity. Maisak et al. used calcium imaging to show that T4 and T5 neurons are divided into specific subpopulations responding to motion in four cardinal directions, and are specific to 'ON' versus 'OFF' edges, respectively.

We explore the use of signatures, i.e., partial truth tables generated via bit-parallel functional simulation, during soft error analysis and logic synthesis. We first present a signature-based CAD framework that incorporates tools for the logic-level analysis of soft error rate (x) and for signature-based design for reliability (SiDeR). We observe that the soft error rate (SER) of a logic circuit is closely related to various testability parameters, such as signal observability and probability. We show that these parameters can be computed very efficiently (in linear time) by means of signatures. Consequently, AnSER evaluates logic masking two to three orders of magnitude faster than other SER evaluators while maintaining accuracy. AnSER can also compute SER efficiently in sequential circuits by approximating steady-state probabilities and sequential signal observabilities. In the second part of this paper, we incorporate AnSER into logic synthesis design flows aimed at reliable circuit design. SiDeR identifies and exploits redundancy already present in a circuit via signature comparison to decrease SER. We show that SiDeR reduces SER by 40% with only 13% area overhead. We also describe a second signature-based synthesis strategy that employs local rewriting to simultaneously improve area and decrease SER. This technique yields 13% reduction in SER with a 2% area decrease. We show that combining the two synthesis approaches can result in further area-reliability improvements.

The relatively poor scaling of interconnect in modern digital circuits necessitates a number of design optimizations, which must typically be iterated several times to meet the specified performance objectives. Such iterations are often due to the difficulty of early delay estimation, particularly before placement. Therefore, effective logic restructuring to reduce interconnect delay has been a major challenge in physical synthesis, a phase during which more accurate delay estimates can be finally gathered. In this paper, we develop a new approach that enhances modern high-performance logic synthesis techniques with flexibility and accuracy in the physical domain. This approach is based on the following: 1) a novel criterion based on path monotonicity, which identifies those interconnects that are amenable to optimization through logic restructuring, and 2) a synthesis algorithm relying on logic simulation and placement information to identify placed subcircuits that hold promise for interconnect reduction. Experiments indicate that our techniques find optimization opportunities and improve interconnect delay by 11.7% on average at less than 2% wirelength and area overhead.

Connectomics—the study of how neurons wire together in the brain—is at the forefront of modern neuroscience research. However, many connectomics studies are limited by the time and precision needed to correctly segment large volumes of electron microscopy (EM) image data. We present here a semi-automated segmentation pipeline using freely available software that can significantly decrease segmentation time for extracting both nuclei and cell bodies from EM image volumes.

Identifying complex neural circuitry from electron microscopic (EM) images may help unlock the mysteries of the brain. However, identifying this circuitry requires time-consuming, manual tracing (proofreading) due to the size and intricacy of these image datasets, thus limiting analysis to small brain regions. Potential avenues to improve scalability include automatic image segmentation and crowdsourcing, but current efforts have had limited success. In this paper, we propose a new strategy, focused proofreading, that works with automatic segmentation and aims to limit proofreading to areas that are most impactful to the resulting circuit. We then introduce a novel workflow, which exploits biological information such as synapses, and apply it to a large fly optic lobe dataset. Our techniques achieve significant tracing speedups without sacrificing quality. Furthermore, our methodology makes proofreading more accessible and could enhance the effectiveness of crowdsourcing.

We reconstructed the synaptic circuits of seven columns in the second neuropil or medulla behind the fly's compound eye. These neurons embody some of the most stereotyped circuits in one of the most miniaturized of animal brains. The reconstructions allow us, for the first time to our knowledge, to study variations between circuits in the medulla's neighboring columns. This variation in the number of synapses and the types of their synaptic partners has previously been little addressed because methods that visualize multiple circuits have not resolved detailed connections, and existing connectomic studies, which can see such connections, have not so far examined multiple reconstructions of the same circuit. Here, we address the omission by comparing the circuits common to all seven columns to assess variation in their connection strengths and the resultant rates of several different and distinct types of connection error. Error rates reveal that, overall

Electron Microscopy (EM) image (or volume) segmentation has become significantly important in recent years as an instrument for connectomics. This paper proposes a novel agglomerative framework for EM segmentation. In particular, given an over-segmented image or volume, we propose a novel framework for accurately clustering regions of the same neuron. Unlike existing agglomerative methods, the proposed context-aware algorithm divides superpixels (over-segmented regions) of different biological entities into different subsets and agglomerates them separately. In addition, this paper describes a "delayed" scheme for agglomerative clustering that postpones some of the merge decisions, pertaining to newly formed bodies, in order to generate a more confident boundary prediction. We report significant improvements attained by the proposed approach in segmentation accuracy over existing standard methods on 2D and 3D datasets.

Pixel and superpixel classifiers have become essential tools for EM segmentation algorithms. Training these classifiers remains a major bottleneck primarily due to the requirement of completely annotating the dataset which is tedious, error-prone and costly. In this paper, we propose an interactive learning scheme for the superpixel classifier for EM segmentation. Our algorithm is ‘active semi-supervised’ because it requests the labels of a small number of examples from user and applies label propagation technique to generate these queries. Using only a small set (< 20%) of all datapoints, the proposed algorithm consistently generates a classifier almost as accurate as that estimated from a complete groundtruth. We provide segmentation results on multiple datasets to show the strength of these classifiers.

Redundancy removal, i.e., identifying and eliminating redundant logic, is an essential optimization strategy for decreasing design area, reducing critical path delay, and simplifying circuit testability analysis. However, redundancy removal strategies invoke time-consuming proof engines with worst-case exponential behavior. While continual enhancements to heuristics resident in these engines result in large average runtime improvements, inherent intractability still leads to sub-optimal optimization and occasional large runtime outliers. Such outliers are unacceptable in an industrial setting where an outlier compromises design turnaround time. Our work introduces a semi-local optimization algorithm that mitigates the inherent intractability in redundancy removal and eliminates crippling runtime outliers. We further embed this algorithm within a framework that minimizes any negative impact to delay and area metrics. Using the cutting-edge Synopsys® Design Compiler® logic synthesis tool, we demonstrate 1) statistical neutrality in area and timing while achieving consistent runtime improvements on a large set of proprietary circuit designs of varying type and complexity and 2) over 50% runtime improvement on a suite of computationally intractable industrial designs, even when measured at the end of the physical synthesis flow.

The relatively poor scaling of interconnect in modern digital circuits necessitates a number of design optimizations, which must typically be iterated several times to meet the specified performance objectives. Such iterations are often due to the difficulty of early delay estimation, especially before placement. Therefore, effective logic restructuring to reduce interconnect delay has been a major challenge in physical synthesis, a phase during which more accurate delay estimates can be finally gathered. In this work, we develop a new approach to this problem that enhances modern high performance logic synthesis techniques with flexibility and accuracy in the physical domain. This approach is based on (1) a novel criterion based on path monotonicity, that identifies those interconnects amenable to optimization through logic restructuring and (2) a synthesis algorithm relying on logic simulation and placement information to identify placed subcircuits that hold promise for interconnect reduction. Experiments indicate that our techniques find optimization opportunities and improve interconnect delay by 11.7% on average at less than 2% wirelength and area overhead

Despite the growing research effort in formal verification, constraint-based random simulation remains an integral part of design validation, especially for large design components where formal techniques do not scale. However, stimulating important aspects of a design to uncover bugs often requires the construction of complex constraints to guide stimulus generation. We propose Toggle, a stimulus generation engine, which features (1) an entropy-based coverage analysis to efficiently find portions of the design inadequately sensitized by simulation and (2) a novel strategy to automatically stimulate these portions through a specialized SAT algorithm that uses small randomized XOR constraints. As our experimental results demonstrate, Toggle requires minimal input from the verification engineer, and significantly improves the coverage qualities of the generated stimuli when compared to plain random simulation.

SAT sweeping is the process of merging two or more functionally equivalent nodes in a circuit by selecting one of them to represent all the other equivalent nodes. This provides significant advantages in synthesis by reducing circuit size and provides additional flexibility in technology mapping, which could be crucial in post-synthesis optimizations. Furthermore, it is also critical in verification because it can reduce the complexity of the netlist to be analyzed in equivalence checking. Most algorithms available so far for this goal do not exploit observability don't cares (ODCs) for node merging since nodes equivalent up to ODCs do not form an equivalence relation. Although a few recently proposed solutions can exploit ODCs by overcoming this limitation, they constrain their analysis to just a few levels of surrounding logic to avoid prohibitive runtime. We develop an ODC-based node merging algorithm that performs efficient global ODC analysis (considering the entire netlist) through simulation and SAT. Our contributions which enable global ODC-based optimizations are: (1) a fast ODC-aware simulator and (2) an incremental verification strategy that limits computational complexity. In addition, our technique operates on arbitrarily mapped netlists, allowing for powerful post-synthesis optimizations. We show that global ODC analysis discovers on average 25% more (and up to 60%) node-merging opportunities than current state-of-the-art solutions based on local ODC analysis.

As silicon technologies move into the nanometer regime, transistor reliability is expected to wane as devices become subject to extreme process variation, particle-induced transient errors, and transistor wear-out. Unless these challenges are addressed, computer vendors can expect low yields and short mean-times-to-failure. In this paper, we examine the challenges of designing complex computing systems in the presence of transient and permanent faults. We select one small aspect of a typical chip multiprocessor (CMP) system to study in detail, a single CMP router switch. To start, we develop a unified model of faults, based on the time-tested bathtub curve. Using this convenient abstraction, we analyze the reliability versus area tradeoff across a wide spectrum of CMP switch designs, ranging from unprotected designs to fully protected designs with online repair and recovery capabilities. Protection is considered at multiple levels from the entire system down through arbitrary partitions of the design. To better understand the impact of these faults, we evaluate our CMP switch designs using circuit-level timing on detailed physical layouts. Our experimental results are quite illuminating. We find that designs are attainable that can tolerate a larger number of defects with less overhead than naive triple-modular redundancy, using domain-specific techniques such as end-to-end error detection, resource sparing, automatic circuit decomposition, and iterative diagnosis and reconfiguration.

A disjoint support decomposition (DSD) is a representation of a Boolean function F obtained by composing two or more simpler component functions such that the component functions have no common inputs. The decomposition of a function is desirable for several reasons. First, it's a method to obtain a multiple-level implementation of a function. It leads to a partition in simpler blocks that easily results in smaller areas and fewer interconnects. Moreover, it exposes a parallelism in the computation of the function that can be exploited by hardware as well as during simulation. In this paper we present a novel algorithm, STACCATO, that generates a DSD decomposition starting from the BDD of a function. STACCATO is novel because: 1) it provides a complete description of each decomposition, that is, it computes the "kernel" function K relating the elements of each decomposition; and 2) it has better performance than previously known algorithms. Experimental results run on both IWLS and industrial test-benches show that STACCATO'S performance is in most cases three times as fast or more than previously known solutions.

As silicon technologies move into the nanometer regime, transistor reliability is expected to wane as devices become subject to extreme process variation, particle-induced transient errors, and transistor wear-out. Unless these challenges are addressed, computer vendors can expect low yields and short mean-times-to-failure. In this article, we examine the challenges of designing complex computing systems in the presence of transient and permanent faults. We select one small aspect of a typical chip multiprocessor (CMP) system to study in detail, a single CMP router switch. Our goal is to design a BulletProof CMP switch architecture capable of tolerating significant levels of various types of defects. We first assess the vulnerability of the CMP switch to transient faults. To better understand the impact of these faults, we evaluate our CMP switch designs using circuit-level timing on detailed physical layouts. Our infrastructure represents a new level of fidelity in architectural-level fault analysis, as we can accurately track faults as they occur, noting whether they manifest or not, because of masking in the circuits, logic, or architecture. Our experimental results are quite illuminating. We find that transient faults, because of their fleeting nature, are of little concern for our CMP switch, even within large switch fabrics with fast clocks. Next, we develop a unified model of permanent faults, based on the time-tested bathtub curve. Using this convenient abstraction, we analyze the reliability versus area tradeoff across a wide spectrum of CMP switch designs, ranging from unprotected designs to fully protected designs with on-line repair and recovery capabilities. Protection is considered at multiple levels from the entire system down through arbitrary partitions of the design. We find that designs are attainable that can tolerate a larger number of defects with less overhead than naïve triple-modular redundancy, using domain-specific techniques, such as end-to-end error detection, resource sparing, automatic circuit decomposition, and iterative diagnosis and reconfiguration.