Search

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 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.

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.

Due to technological advances in electron microscopy (EM) and deep learning, it is now practical to reconstruct a connectome, a description of neurons and the connections between them, for significant volumes of neural tissue. The limited scope of past reconstructions meant they were primarily used by domain experts, and performance was not a serious problem. But the new reconstructions, of common laboratory creatures such as the fruit fly Drosophila melanogaster, upend these assumptions. These natural neural networks now contain tens of thousands of neurons and tens of millions of connections between them, with yet larger reconstructions pending, and are of interest to a large community of non-specialists. This requires new tools that are easy to use and efficiently handle large data. We introduce neuPrint to address these data analysis challenges. neuPrint is a database and analysis ecosystem that organizes connectome data in a manner conducive to biological discovery. In particular, we propose a data model that allows users to access the connectome at different levels of abstraction primarily through a graph database, neo4j, and its powerfully expressive query language Cypher. neuPrint is compatible with modern connectome reconstruction workflows, providing tools for assessing reconstruction quality, and offering both batch and incremental updates to match modern connectome reconstruction flows. Finally, we introduce a web interface and programmer API that targets a diverse user skill set. We demonstrate the effectiveness and efficiency of neuPrint through example database queries.

Deriving the detailed synaptic connections of the entire nervous system has been a long term but unrealized goal of the nascent field of connectomics. For Drosophila, in particular, three sample preparation problems must be solved before the requisite imaging and analysis can even begin. The first is dissecting the brain, connectives, and ventral nerve cord (roughly comparable to the brain, neck, and spinal cord of vertebrates) as a single contiguous unit. Second is fixing and staining the resulting specimen, too large for previous techniques such as flash freezing, so as to permit the necessary automated segmentation of neuron membranes. Finally the contrast must be sufficient to support synapse detection at imaging speeds that enable the entire connectome to be collected. To address these issues, we report three major novel methods to dissect, fix, dehydrate and stain this tiny but complex nervous system in its entirety; together they enable us to uncover a Focused Ion-Beam Scanning Electron Microscopy (FIB-SEM) connectome of the entire Drosophila brain. They reliably recover fixed neurons as round profiles with darkly stained synapses, suitable for machine segmentation and automatic synapse detection, for which only minimal human intervention is required. Our advanced procedures use: a custom-made jig to microdissect both regions of the central nervous system, dorsal and ventral, with their connectives; fixation and Durcupan embedment, followed by a special hot-knife slicing protocol to reduce the brain to dimensions suited to FIB; contrast enhancement by heavy metals; together with a progressive lowering of temperature protocol for dehydration. Collectively these optimize the brain’s morphological preservation, imaging it at a usual resolution of 8nm per voxel while simultaneously speeding the formerly slow rate of FIB-SEM. With these methods we could recently obtain a FIB-SEM image stack of the Drosophila brain eight times faster than hitherto, at approximately the same rate as, but without the requirement to cut, nor imperfections in, EM serial sections.

Visual pathways from the compound eye of an insect relay to four neuropils, successively the lamina, medulla, lobula, and lobula plate in the underlying optic lobe. Among these neuropils, the medulla, lobula, and lobula plate are interconnected by the complex second optic chiasm, through which the anteroposterior axis undergoes an inversion between the medulla and lobula. Given their complex structure, the projection patterns through the second optic chiasm have so far lacked critical analysis. By densely reconstructing axon trajectories using a volumetric scanning electron microscopy (SEM) technique, we reveal the three-dimensional structure of the second optic chiasm of Drosophila melanogaster, which comprises interleaving bundles and sheets of axons insulated from each other by glial sheaths. These axon bundles invert their horizontal sequence in passing between the medulla and lobula. Axons connecting the medulla and lobula plate are also bundled together with them but do not decussate the sequence of their horizontal positions. They interleave with sheets of projection neuron axons between the lobula and lobula plate, which also lack decussations. We estimate that approximately 19,500 cells per hemisphere, about two thirds of the optic lobe neurons, contribute to the second chiasm, most being Tm cells, with an estimated additional 2,780 T4 and T5 cells each. The chiasm mostly comprises axons and cell body fibers, but also a few synaptic elements. Based on our anatomical findings, we propose that a chiasmal structure between the neuropils is potentially advantageous for processing complex visual information in parallel. The EM reconstruction shows not only the structure of the chiasm in the adult brain, the previously unreported main topic of our study, but also suggest that the projection patterns of the neurons comprising the chiasm may be determined by the proliferation centers from which the neurons develop. Such a complex wiring pattern could, we suggest, only have arisen in several evolutionary steps.

Understanding the circuit mechanisms behind motion detection is a long-standing question in visual neuroscience. In Drosophila melanogaster, recently discovered synapse-level connectomes in the optic lobe, particularly in ON-pathway (T4) receptive-field circuits, in concert with physiological studies, suggest a motion model that is increasingly intricate when compared with the ubiquitous Hassenstein-Reichardt model. By contrast, our knowledge of OFF-pathway (T5) has been incomplete. Here, we present a conclusive and comprehensive connectome that, for the first time, integrates detailed connectivity information for inputs to both the T4 and T5 pathways in a single EM dataset covering the entire optic lobe. With novel reconstruction methods using automated synapse prediction suited to such a large connectome, we successfully corroborate previous findings in the T4 pathway and comprehensively identify inputs and receptive fields for T5. Although the two pathways are probably evolutionarily linked and exhibit many similarities, we uncover interesting differences and interactions that may underlie their distinct functional properties.

Automatic image segmentation is critical to scale up electron microscope (EM) connectome reconstruction. To this end, segmentation competitions, such as CREMI and SNEMI, exist to help researchers evaluate segmentation algorithms with the goal of improving them. Because generating ground truth is time-consuming, these competitions often fail to capture the challenges in segmenting larger datasets required in connectomics. More generally, the common metrics for EM image segmentation do not emphasize impact on downstream analysis and are often not very useful for isolating problem areas in the segmentation. For example, they do not capture connectivity information and often over-rate the quality of a segmentation as we demonstrate later. To address these issues, we introduce a novel strategy to enable evaluation of segmentation at large scales both in a supervised setting, where ground truth is available, or an unsupervised setting. To achieve this, we first introduce new metrics more closely aligned with the use of segmentation in downstream analysis and reconstruction. In particular, these include synapse connectivity and completeness metrics that provide both meaningful and intuitive interpretations of segmentation quality as it relates to the preservation of neuron connectivity. Also, we propose measures of segmentation correctness and completeness with respect to the percentage of “orphan” fragments and the concentrations of self-loops formed by segmentation failures, which are helpful in analysis and can be computed without ground truth. The introduction of new metrics intended to be used for practical applications involving large datasets necessitates a scalable software ecosystem, which is a critical contribution of this paper. To this end, we introduce a scalable, flexible software framework that enables integration of several different metrics and provides mechanisms to evaluate and debug differences between segmentations. We also introduce visualization software to help users to consume the various metrics collected. We evaluate our framework on two relatively large public groundtruth datasets providing novel insights on example segmentations.

Using FIB-SEM we report the entire synaptic connectome of glomerulus VA1v of the right antennal lobe in Drosophila melanogaster. Within the glomerulus we densely reconstructed all neurons, including hitherto elusive local interneurons. The fruitless-positive, sexually dimorphic VA1v included >11,140 presynaptic sites with ~38,050 postsynaptic dendrites. These connected input olfactory receptor neurons (ORNs, 51 ipsilateral, 56 contralateral), output projection neurons (18 PNs), and local interneurons (56 of >150 previously reported LNs). ORNs are predominantly presynaptic and PNs predominantly postsynaptic; newly reported LN circuits are largely an equal mixture and confer extensive synaptic reciprocity, except the newly reported LN2V with input from ORNs and outputs mostly to monoglomerular PNs, however. PNs were more numerous than previously reported from genetic screens, suggesting that the latter failed to reach saturation. We report a matrix of 192 bodies each having >50 connections; these form 88% of the glomerulus’ pre/postsynaptic sites.

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

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.

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

The aim in high-resolution connectomics is to reconstruct complete neuronal connectivity in a tissue. Currently, the only technology capable of resolving the smallest neuronal processes is electron microscopy (EM). Thus, a common approach to network reconstruction is to perform (error-prone) automatic segmentation of EM images, followed by manual proofreading by experts to fix errors. We have developed an algorithm and software library to not only improve the accuracy of the initial automatic segmentation, but also point out the image coordinates where it is likely to have made errors. Our software, called gala (graph-based active learning of agglomeration), improves the state of the art in agglomerative image segmentation. It is implemented in Python and makes extensive use of the scientific Python stack (numpy, scipy, networkx, scikit-learn, scikit-image, and others). We present here the software architecture of the gala library, and discuss several designs that we consider would be generally useful for other segmentation packages. We also discuss the current limitations of the gala library and how we intend to address them.

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.

The ability to automatically segment an image into distinct regions is a critical aspect in many visual processing applications. Because inaccuracies often exist in automatic segmentation, manual segmentation is necessary in some application domains to correct mistakes, such as required in the reconstruction of neuronal processes from microscopic images. The goal of the automated segmentation tool is traditionally to produce the highest-quality segmentation, where quality is measured by the similarity to actual ground truth, so as to minimize the volume of manual correction necessary. Manual correction is generally orders-of-magnitude more time consuming than automated segmentation, often making handling large images intractable. Therefore, we propose a more relevant goal: minimizing the turn-around time of automated/manual segmentation while attaining a level of similarity with ground truth. It is not always necessary to inspect every aspect of an image to generate a useful segmentation. As such, we propose a strategy to guide manual segmentation to the most uncertain parts of segmentation. Our contributions include 1) a probabilistic measure that evaluates segmentation without ground truth and 2) a methodology that leverages these probabilistic measures to significantly reduce manual correction while maintaining segmentation quality.

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.