In this paper, we propose F2-Bubbles, a set overlay visualization technique that addresses overlapping artifacts and supports interactive editing with intelligent suggestions. The core of our method is a new, efficient set overlay construction algorithm that approximates the optimal set overlay by considering set elements and their non-set neighbors. Thanks to the efficiency of the algorithm, interactive editing is achieved, and with intelligent suggestions, users can easily and flexibly edit visualizations through direct manipulations with local adaptations. A quantitative comparison with state-of-the-art set visualization techniques and case studies demonstrate the effectiveness of our method and suggests that F2-Bubbles is a helpful technique for set visualization.

With the advent of the Big Data era, it is usually computationally expensive to calculate the resource usages of a SQL query with traditional DBMS approaches. Can we estimate the cost of each query more efficiently without any computation in a SQL engine kernel? Can machine learning techniques help to estimate SQL query resource utilization? The answers are yes. We propose a SQL query cost predictor service, which employs machine learning techniques to train models from historical query request logs and rapidly forecasts the CPU and memory resource usages of online queries without any computation in a SQL engine. At Twitter, infrastructure engineers are maintaining a large-scale SQL federation system across on-premises and cloud data centers for serving ad-hoc queries. The proposed service can help to improve query scheduling by relieving the issue of imbalanced online analytical processing (OLAP) workloads in the SQL engine clusters. It can also assist in enabling preemptive scaling. Additionally, the proposed approach uses plain SQL statements for the model training and online prediction, indicating it is both hardware and software-agnostic. The method can be generalized to broader SQL systems and heterogeneous environments. The models can achieve 97.9% accuracy for CPU usage prediction and 97% accuracy for memory usage prediction.

Real-time stream processing has become increasingly important in recent years and has led to the development of a multitude of stream processing systems. Given the varying job workloads that characterize stream processing, these systems need to be tuned and adjusted to maintain performance targets in the face of variation in incoming traffic. Current auto-scaling systems adopt a series of trials to approach a job's expected performance due to a lack of performance modelling tools. We find that general traffic trends in most jobs lend themselves well to prediction. Based on this premise, we built a system called Caladrius that forecasts the future traffic load of a stream processing job and predicts its processing performance after a proposed change to the parallelism of its operators. Experimental results show that Caladrius is able to estimate a job's throughput performance and CPU load under a given scaling configuration.

Latest SOC trends include multiple asynchronous clock domains, each covering large silicon areas. Clock-Stop & State-Dump (CSSD) is a commonly used silicon debug technique that relies on stopping clocks and reconfiguring flip-flops as one or more scan chains. This paper describes an architecture for stopping clocks deterministically to allow safe state preservation before reconfiguring a circuit. Conditions for determinism are defined and a design IP to implement CSSD is described. Considerations for supporting an IP-SOC design methodology are also specified. The design was implemented and validated in Xilinx' 16nm FPGA family.

Detecting community structure in epidemics networks is crucial for the assessment of epidemic dynamics and effective control of disease spread by targeting at the individuals bridging communities. Common community detection models (e.g., cut-criteria and modularity-criteria based model) are efficient in optimal quality of network partitions. However, most of the approaches fail to consider the dynamic infected possibility in person-to-person interactions. In addition, they present high computational complexity, which was limited by the scale of networks and the performance of hardware platform. In this paper, we propose a Jaccard distance based community detection model by considering both the quality of network partitions and the dynamics of infected interacts (i.e., edges) between two individuals in epidemic diffusion. Then, we design a novel parallel approach based on the high parallism of GPU, called EpCom, for boosting the performance and scalability of parallel community detection over large-scale epidemic networks. From the evaluation results, the proposed GPU-based implementation EpCom exhibits great performance and achieves maximum 604 million TEPS (traversed edges per second), which corresponds to up to 54.2 times and 15.6 times than CPU-based NCut and Louvain approaches separately.

A new use for ring-oscillators (ROs) is proposed by which PMOS and NMOS transistor strengths can be measured and monitored in the field. A new metric, based on RO duty-cycle is defined. This new metric, along with RO-frequency, offers a way to profile and bin transistors based on their drive strengths. With ROs configured from payload transistors, along with the natural programmability of FPGAs, this strength based profiling can be done in the field at a level of granularity that is not possible with existing methodologies. New applications of the metrics and the profiling methodology include use of on-die ROs as a (a) monitor and control for duty-cycle sensitive designs, (b) replacement for scribe-line test structures, and (c) sensor for payload transistor characteristics over life-time.

FPGAs have evolved rapidly over the past decade with a significant increase in size and complexity. Today's FPGA is indeed a system-on-chip (SOC) with a wide variety of hardened functionality, multiple asynchronous clock domains and widening interactions among different parts of the chip. It is commonplace to find applications that transfer data and control across clock-domains. This growing complexity, coupled with shrinking design cycles, has turned debug and verification into a critical design concern. Although software analysis tools have made significant progress over the years, this is not the case for debugging applications running on FPGAs. This paper describes a framework that enables non-intrusive application hardware debugging in the presence of multiple asynchronous clock domains. It offers full observability at minimal area and performance cost. The proposed approach uses Readback to retrieve the entire state of the circuit, a feature available in one form or another, in most commercial FPGAs today. Features such as single stepping and waveform reconstruction offer the same level of debug capability for applications accelerated on FPGAs, as simulation tools do for RTL implementations.

Hardware redundancy, such as spare processors and cores, has been added to chip multi-processors (CMPs) to improve yield while sustaining all functionalities of CMPs. During post-silicon testing, spares processors and cores are used for repair. Even after repair, some CMPs may have processors with insufficient number of cores; in such CMPs some processors are disabled and such chips are sold at lower prices to improve yield per area. Despite binning on the number of processors, substantial functional resources are wasted in disabled components. In this work, we propose a new utility function and a new repair algorithm which enable utilization of every working core on a CMP. We demonstrate the benefits of the proposed approach for benchmarks from ISPASS and Nvidia CUDA SDK using GPGPU-sim to compute the instructions per cycle (IPC). Results show that our design and repair approaches provide above 50% IPC per wafer area even with 10x the current defect density.

Substantial imperfections in carbon nanotube (CNT) field-effect transistors (CNFETs) are one key obstacle to the demonstration of large-scale CNFET circuits. In this paper, we first categorize transistors based on the impact of resizing on yield improvement and delay penalty for logic circuits. Then we propose an approach to size transistors in different categories by using redundant CNTs to improve yield/area with user-specified limit on delay penalty. We then propose a hybrid redundancy approach for memory arrays by optimally combining redundant CNTs approach with the traditional spare columns (rows) approach. Experimental results show that the proposed approach provides significant improvements in yield/area for logic circuits at very low increase in delays. For SRAM, spare columns (rows) approach becomes ineffective when it is applied alone since spare columns (rows) themselves have very low yield. The proposed hybrid approach for memory array provides 18% improvement in yield/area compared to a redundant-CNTs-only approach as well as reduces delay penalty on address decoder from 19.2% to 15.7%.

Yield of chip-multiprocessors (CMP) can be improved by adding spares to the design. The optimal spare configuration has previously been derived for certain evaluation metrics, such as yield per area, performance-averaged yield, and so on. However, all previous approaches are limited to the scenario where only those chips which have the full-configuration (i.e., have n working processors, where n is the number of processors in the CMP's specifications) can be sold. In the meantime, yield problems have forced vendors of high-volume CMPs to sell chips with different numbers of working processors. The purpose of this paper is to extend our recent framework for the optimal redundancy design to systematically capture such flexibilities. We first define utility function for CMPs in terms of two functions: (i) the number-of-processors-binning (NPB) function, which captures the range of the number of (enabled) working processors over which a chip can be sold, and (ii) the value function, which captures how the value of a chip to the user depends upon the number of processors enabled in the chip. We use case studies to identify the relationships between utility functions and optimal spare configurations. Then we extend our branch and bound algorithm and incorporate a dynamic programming approach to develop the first framework for optimal and e-optimal (i.e., within e of optimal, typically at much lower area overhead) redundancy designs for different utility functions. We demonstrate that even in an era of high defect density which leads to extremely low yield, we are able to combine approaches in a way that provide figure of merit that is up to 83.8% of that of the ideal case, i.e., for a process with zero defect density.

The manufacturing yield of chip multiprocessors (CMPs) has become a significant problem as more transistors are integrated onto a single die and the defect rate keeps increasing for “end-of-Moore” nano-scale CMOS technologies. Since such CMP designs usually have significant structural symmetry, adding spare copies to these should be an effective method for increasing yield per area, as is the case for memories. However, a systematic approach to add spare copies to optimize CMP yield per area has never been developed, primarily due to the lack of: 1) a general model of CMP architectures and 2) a practically-useable model for computing areas of chip versions with different configurations of spare copies. This paper develops such models and, in conjunction with a systematic approach for enumerating a wide range of spare configurations, uses these to compute the area overhead and yield for each configuration. In particular, this paper proposes a general spare cores sharing technique to maximize yield per area of any CMP by efficiently traversing the design space for adding spare cores. Experimental results show that the advantage of the proposed approach over traditional approaches increases with continued technology scaling. Specifically, the proposed approach achieves \(2\times \) yields per area over previous approaches for 32 nm and 22 nm technologies. Also, the obtained yield per area values provided by our approach are around 70% of that obtained for the ideal scenario where defect density is zero and no redundancy is added.

The method of calculating voltage unbalance factor (VUF) recommended by the IEC61000-4-27 has the disadvantage of requiring square root operation. This paper focuses on the fast and accurate calculation of VUF of three-phase power system. The approximate algorithm for calculating the magnitude of the zero, positive, and negative sequences by simple algebraic equation is presented. In the proposed method, the square root operation is first transformed to simple trigonometric equations based on the geometric figure, and then the trigonometric equations are approximated by the algebraic operations, which thus reduced the computation burden sufficiently. The simulation and practical experiment results show that the proposed method can achieve the same level of precision as the method recommended by the IEC61000-4-27, while much less clock cycles are required, which indicates its wide application in digital signal processor (DSP).

Process variations are growing with technology scaling towards nano-scale. This brings new challenges to the design of memory modules, which are often the first circuits to be fabricated using a new technology and usually designed with critical timing. We observed that several delay faults, which are dependent on address transitions, may escape traditional march tests. This paper presents a new march test WT that targets such delay faults. Through Monte Carlo simulations and analytical studies on SRAM designs using an industrial 65nm process, we have demonstrated that WT provides a faulty-chip-coverage that is close to 100%. Most importantly, this is the first march test with test length that targets address-dependent delay faults and hence the first delay test which can be used in practice.

As process variations grow with technology scaling, failure rates increase and are predicted to be so high as to render devices unusable for computing domain. In order to continue to benefit from scaling, three dimensions can be explored: increasing operational margins, testing, and the resilience of applications. The solutions in each dimension bring out different trade-offs in yield, failure rate, test cost, and performance. We use a ternary content-addressable memory (TCAM) as a case study to better understand these trade-offs. We develop two new delay tests for TCAMs, and a new method to estimate yield, failure rate, test cost, and performance of TCAM under process variations when various tests are used. Our results show that with little test overhead and negligible yield loss, our new tests can significantly decrease the failure rates of TCAMs shipped to customers.

Manufacturing yield is a major concern for modern CMOS technologies. Fortunately, evolving chip architectures such as multi-cores have provided new venues for yield enhancement, and calls for a fresh perspective on the classic method of redundancy insertion. In this paper we outline a new approach towards redundancy insertion in modern multi-core CPU architectures. Traditionally, applying redundancy at a finer intra-core level of granularity provides great benefits in yield improvement, but requires additional steering logic and wiring that has a detrimental impact on area and performance. At the other end of the spectrum, coarse-grained core level redundancy can enable spare sharing, but it is only beneficial in highly-parallel GPU architectures. To this end, we will 1) introduce a hybrid spare sharing redundancy insertion scheme that combines the advantages of the above two approaches, while carefully leveraging the associated area and performance overheads, 2) present an extensively verified, systematic scalable model to evaluate the quality of the final design in terms of projected revenue per wafer, and 3) introduce a maximization algorithm to determine the near optimal redundancy configurations during the design stage. Experimental results show that our new design methodology provides more than 15% improvement in revenue per wafer, compared to using existing redundancy insertion techniques.

Networked systems have benefited from unprecedented growth in hardware capabilities, but, as we move closer to the end of the Moore's law era, future networked systems are likely to be more constrained by hardware capabilities than they have been in the past. We take the position that the networking community should, in response to this development, proactively and systematically develop networking roadmaps, which attempt to predict how trends in hardware capabilities will impact networked systems. In this paper, we discuss a possible methodology for developing networking roadmaps, and present two case studies that illustrate the methodology and reveal how increasing hardware unreliability can affect the performance of routing and transport protocols.

Traditional approaches for improving yield are based on the use of hardware redundancy (HR), and their benefits are limited for high defect densities due to increasing layout complexities and diminishing return effects. This research is based on an observation that completely correct operation of user programs can be guaranteed while using chips with one or more unrepairable memory modules if software-level techniques satisfy two condistions: (1) defects only affect a few memory cells rather than cause malfunction for the entire memory module, and (2) either we do not use any part of the memory affected by the un-repaired defect, or we do use the affected part, but only in a manner that does not excite the un repaired defect to cause errors. This paper proposes a software based defect-tolerance (SBDT) approach in combination with HR to utilize defective memory chips for application-specific systems. The proposed approach requires known and fixed program and information about defective locations for each memory module, hence this paper focuses on SoCs and other application-specific systems built around processors, such as DSP and graphics processors. We model an application program and defective memory copies as described next.