There is a growing body of work on using Graph Neural Networks (GNNs) to learn representations of circuits, focusing primarily on their static characteristics. However, these models fail to capture circuit runtime behavior, which is crucial for tasks like circuit verification and optimization. To address this limitation, we introduce DR-GNN (DynamicRTL-GNN), a novel approach that learns RTL circuit representations by incorporating both static structures and multi-cycle execution behaviors. DR-GNN leverages an operator-level Control Data Flow Graph (CDFG) to represent Register Transfer Level (RTL) circuits, enabling the model to capture dynamic dependencies and runtime execution. To train and evaluate DR-GNN, we build the first comprehensive dynamic circuit dataset, comprising over 6,300 Verilog designs and 63,000 simulation traces. Our results demonstrate that DR-GNN outperforms existing models in branch hit prediction and toggle rate prediction. Furthermore, its learned representations transfer effectively to related dynamic circuit tasks, achieving strong performance in power estimation and assertion prediction.

As hardware design complexity increases, hardware fuzzing emerges as a promising tool for automating the verification process. However, a significant gap still exists before it can be applied in industry. This paper aims to summarize the current progress of hardware fuzzing from an industry-use perspective and propose solutions to bridge the gap between hardware fuzzing and industrial verification. First, we review recent hardware fuzzing methods and analyze their compatibilities with industrial verification. We establish criteria to assess whether a hardware fuzzing approach is compatible. Second, we examine whether current verification tools can efficiently support hardware fuzzing. We identify the bottlenecks in hardware fuzzing performance caused by insufficient support from the industrial environment. To overcome the bottlenecks, we propose a prototype, HwFuzzEnv, providing the necessary support for hardware fuzzing. With this prototype, the previous hardware fuzzing method can achieve a several hundred times speedup in industrial settings. Our work could serve as a reference for EDA companies, encouraging them to enhance their tools to support hardware fuzzing efficiently in industrial verification.

Debugging hardware designs requires significant manual effort during hardware development. After engineers identify a bug-triggering test case in simulation-based hardware verification, they usually spend considerable time analyzing the execution trace to localize the bug. Although numerous automated hardware debugging techniques exist, they are not applicable to large designs and deep bugs. A primary reason for their limitations is that these techniques only utilize the information of a single bug-triggering test case for bug localization, which prevents them from effectively analyzing intricate hardware systems and figure out the root cause of bugs. To solve this problem, in this paper, we transform the hardware bug localization problem into a test generation problem, aiming to find a set of effective witness test cases beyond the initial bug-triggering test case to enhance hardware bug localization. Witness test cases refer to the cases that do not trigger the bug in the faulty design. By analyzing the execution differences between passing and failing test cases with spectrum-based method, we can eliminate innocent design statements and localize the buggy ones. To further refine the suspicious area, we define the criteria for effective witness test cases and use a mutation-based strategy to generate such test cases. Based on this approach, we propose an automated hardware bug localization framework named Wit-HW. We evaluate Wit-HW on 41 bugs from various hardware designs. The experimental results show that Wit- effectively localize 49% / 73% / 88% bugs within Top-1 / Top-5 / Top-10 ranks, significantly outperforming state-of-the-art bug localization techniques. Additionally, we evaluate Wit-HW on 13 real-world bugs collected from open-source hardware projects, showcasing the robust performance of our method.

The Total Focusing Method (TFM) is a highresolution ultrasonic imaging technique widely adopted in nondestructive testing (NDT). However, the computational intensity and memory access demands of TFM hinder its real-time deployment, particularly on conventional computing devices such as CPUs and GPUs. This paper presents TensTFM, a novel TFM acceleration framework optimized for dataflow architectures. Firstly, we characterize the bottlenecks of existing GPU and FPGA solutions and demonstrate the potential of spatially distributed processing on dataflow accelerators. Secondly, we formulate the mapping of TFM operators onto 2D Tensix core arrays as a constrained optimization problem, and propose a simulated annealing-based strategy for efficient mapping space exploration. Thirdly, we introduce tensorized and pipelined implementations for key tasks at the operator level, including Hilbert transform and pixel-wise delay-and-sum interpolation. Finally, experiments on the Tenstorrent Wormhole architecture show that TensTFM can achieve up to$7.9 \times$throughput improvements and$32.5 \times$energy efficiency gain over the optimized GPU baselines. It can also achieve$3.1 \times$throughput improvements compared to the state-of-the-art specialized FPGA accelerators, while offering strong scalability in various imaging configurations.

As context windows expands, Large Language Models (LLMs) are being more capable of handling long-context tasks. However, long-context inference is hindered by high latency and memory usage due to the linearly growing Key-Value (KV) cache. Prior work has shown that a dynamic subset of the KV cache dominates attention outcomes and selectively loads these subsets instead of the full cache. These methods partition the KV cache into segments (block-wise and token-wise) and identify critical ones for recall. However, for block-wise ones, their recall accuracy is often compromised by semantic inconsistencies among consecutive tokens, and for token-wise ones, they suffer from inefficiency in memory management and offloading. To these ends, we propose Dispenser, a hierarchical KV cache management algorithm inspired by multi-level page tables. Dispenser organizes the KV cache based on token semantic similarity and partitions it into pages and blocks, which enables straightforward integration into modern serving engines such as vLLM. It employs a two-level lookup mechanism to identify and load the most relevant blocks for the current query. Experimental results demonstrate that Dispenser achieves up to a$5.75 \times$speedup in self-attention, reducing inference latency by$2.1 \times$on tasks with long dependencies with negligible accuracy loss.

Network on chip (NoC) has surfaced as a crucial interconnection strategy in modern digital systems, thereby demanding meticulous verification. Due to its multiple nodes and high concurrency, verifying an NoC is labor-intensive, making it complex to generate a multitude of test cases. Recently, hardware fuzzing has been identified as a promising automated approach for hardware verification. However, when we tried to apply these fuzzing techniques to our internally developed NoC design, we discovered that they were incompatible with the specificities of NoC. Additionally, they are also incompatible with the standard IC verification workflow and universal verification methodology (UVM) environment. In this work, we aim to automate our verification process of NoC with fuzzing. We propose a fuzzing strategy specifically tailored for industrial NoC UVM verification. We employ fuzzing in NoC verification at multiple levels, including router verification, network verification, and stress testing. As a case study we apply our approach to an open-source NoC component in OpenPiton. Remarkably, our fuzzing methods automatically achieved complete code and functional coverage in the router and mesh network. We also effectively detect injected starvation bugs with fuzzing. The evaluation results clearly demonstrate the practicability of our fuzzing approach to considerably reduce the manpower required for test case generation compared with traditional NoC verification.

This article introduces OpenLS-DGF, an adaptive logic synthesis dataset generation framework, to enhance machine-learning (ML) applications within the logic synthesis process. Previous dataset generation flows were tailored for specific tasks or lacked integrated ML capabilities. While OpenLS-DGF supports various ML tasks by encapsulating the three fundamental steps of logic synthesis: 1) Boolean representation; 2) logic optimization; and 3) technology mapping. It preserves the original information in both Verilog and ML-friendly GraphML formats. The Verilog files offer semi-customizable capabilities, enabling researchers to insert additional steps and incrementally refine the generated dataset. Furthermore, OpenLS-DGF includes an adaptive circuit engine that facilitates the final dataset management and downstream tasks. The generated OpenLS-D-v1 dataset comprises 46 combinational designs from established benchmarks, totaling over 966 000 Boolean circuits. OpenLS-D-v1 supports integrating new data features, making it more versatile for new tasks. This article demonstrates the versatility of OpenLS-D-v1 through four distinct downstream tasks: circuit classification, circuit ranking, quality of results (QoR) prediction, and probability prediction. Each task is chosen to represent essential steps of logic synthesis, and the experimental results show the generated dataset from OpenLS-DGF achieves prominent diversity and applicability. The source code and datasets are available athttps://github.com/Logic-Factory/ACE/blob/master/OpenLS-DGF.

The feasibility-seeking approach offers a systematic framework for managing and resolving intricate constraints in continuous problems, making it a promising avenue to explore in the context of floorplanning problems with increasingly heterogeneous constraints. The classic legality constraints can be expressed as the union of convex sets. However, conventional projection-based algorithms for feasibility-seeking do not guarantee convergence in such situations, which are also heavily influenced by the initialization. We present a quantitative property about the choice of the initial point that helps good initialization and analyze the occurrence of the oscillation phenomena for bad initialization. In implementation, we introduce a resetting strategy aimed at effectively reducing the problem of algorithmic divergence in the projection-based method used for the feasibility-seeking formulation. Furthermore, we introduce the novel application of the superiorization method (SM) to floorplanning, which bridges the gap between feasibility-seeking and constrained optimization. The SM employs perturbations to steer the iterations of the feasibility-seeking algorithm towards feasible solutions with reduced (not necessarily minimal) total wirelength. Notably, the proposed algorithmic flow is adaptable to handle various constraints and variations of floorplanning problems, such as those involving I/O assignment. To evaluate the performance of Per-RMAP, we conduct comprehensive experiments on the MCNC benchmarks and GSRC benchmarks. The results demonstrate that we can obtain legal floorplanning results 166× faster than the branch-and-bound (B&B) method while incurring only a 5% wirelength increase compared to the optimal results. Furthermore, we evaluate the effectiveness of the algorithmic flow that considers the I/O assignment constraints, which achieves an 6% improvement in wirelength. Besides, considering the soft modules with a larger feasible solution space, we obtain 15% improved runtime compared with PeF, the state-of-the-art analytical method. Moreover, we compared our method with Parquet-4 and Fast-SA on GSRC benchmarks which include larger-scale instances. The results highlight the ability of our approach to maintain a balance between floorplanning quality and efficiency.

By leveraging the power of open-source software, the EDA tool offers a cost-effective and flexible solution for designers, researchers, and hobbyists alike. Open-source EDA promotes collaboration, innovation, and knowledge sharing within the EDA community. It emphasizes the role of the toolchain in accelerating the development of electronic systems, reducing design costs, and improving design quality. This paper presents an open-source EDA project, iEDA, aiming to build a basic infrastructure for EDA technology evolution and closing the industrial-academic gap in the EDA area. As the foundation for developing EDA tools and researching EDA algorithms and technologies, iEDA is mainly composed of file system, database, manager, operator and interface. To demonstrate the effectiveness of iEDA, we implement and tape out four chips of different scales (from 700k to 500M gates) on different process nodes (110nm and 28nm) with iEDA. iEDA is publicly available on the project home page https://github.com/OSCC-Project/iEDA.

Performance estimation is a crucial component in the optimization processes of accelerator development on the Versal ACAP architecture. However, existing approaches present limitations - they are either too slow to facilitate efficient iterations, or they lack the necessary accuracy due to the specific AIE array architecture and two-level programming model of Versal ACAP. To tackle this challenge, we propose G2PM, a performance modeling technique based on a hierarchical graph representation centered on the AIE array. More specifically, we employ a hierarchical graph neural network to identify features of both kernel programs and dataflow programs, taking into account the hardware and software characteristics of the Versal ACAP architecture. In our evaluations, our method demonstrates significant improvements, achieving a mean error rate of less than 1.6% and providing a speed-up factor of 4165X compared to the simulation-based method.

Coarse-Grained Reconfigurable Array (CGRA) is a parallel architecture providing high energy efficiency and spatial-temporal re-configurability. Beyond loop scheduling for throughput optimization, program transformation is also crucial in CGRA mapping to optimize overall performance and efficiency. However, existing studies on program transformation optimization face challenges in exploring the transformation space systematically and evaluating candidates efficiently, leading to sub-optimal results. To tackle these challenges, this paper introduces PT-Map, an efficient program transformation optimization framework for CGRA mapping. PT-Map defines a comprehensive transformation space and employs a CGRA-specialized top-down exploration approach. It also incorporates a bottom-up evaluation scheme using architectural parameters and a graph neural network-based predictive model. Experiments demonstrate that PT-Map achieves up to 2.95X/1.80X speedups and 59.0%/23.2% energy-delay-product (EDP) reductions over the state-of-the-art approaches MapZero and PBP, respectively.

Generating high-quality sub-circuits for local substitution is an effective optimization technique in logic synthesis. There have been abundant works on generating area- and delay-optimal sub-circuits, greatly enhancing the logic optimization quality. However, power-oriented sub-circuit generation is rarely discussed, while optimizing power consumption in this sub-15 nm era is of paramount interest. We propose PONO, an SMT-based near optimal sub-circuit generation flow for power optimization. PONO enables power-oriented circuit library building and fills the gap in generating circuits near the Pareto frontier in PPA (Power, Performance, and Area). It manifests superiority in power reduction over traditional one in rewrite, a key logic optimization algorithm. We test PONO on EFPL benchmarks, and it shows 8.7% less power consumption without degrading the post-place-and-route performance and area.

The Versal Adaptive Compute Acceleration Platform (ACAP) is a new architecture that combines AI Engines (AIEs) with reconfigurable fabric. This architecture offers significant acceleration potential for uniform recurrences in various domains, such as deep learning, high-performance computation, and signal processing. However, efficiently mapping these computations onto the Versal ACAP architecture while achieving high utilization of AIEs poses a challenge. To address this issue, we propose a mapping scheme called WideSA, which aims to accelerate uniform recurrences on the Versal ACAP architecture by leveraging the features of both the hardware and the computations. Considering the array architecture of AIEs, our approach utilizes space-time transformations based on the polyhedral model to generate legally optimized systolic array mappings. Concurrently, we have developed a routing-aware PLIO assignment algorithm tailored for communication on the AlE array, and the algorithm aims at successful compilation while maximizing array utilization. Furthermore, we introduce an automatic mapping framework. This framework is designed to generate the corresponding executable code for uniform recurrences, which encompasses the AlE kernel program, programmable logic bitstreams, and the host program. The experimental results validate the effectiveness of our mapping scheme. Specifically, when applying our scheme to matrix multiplication computations on the VCK5000 board, we achieve a throughput of 4.15TOPS on float data type, which is 1.11 x higher compared to the state-of-the-art accelerator on the Versal ACAP architecture.

Stochastic computing (SC) is an unconventional computing paradigm with unique features. Designing SC circuits is dramatically different from designing binary computing (BC) circuits. To support the agile design of SC circuits, we propose SCGen, a versatile generator framework, which provides users with a C++ interface to easily specify SC circuits and supports 1) accelerated accuracy simulation, 2) accelerated design space exploration (DSE) for accuracy maximization guided by simulated annealing (SA) and genetic algorithm (GA), 3) circuit optimization by random number source (RNS) sharing, 4) circuit verification via symbolic expression analysis, and 5) automatic Verilog code generation. Furthermore, we extend SCGen to also support agile design of hybrid SC-BC circuits. The experimental results show that our proposed DSE acceleration methods achieve up to 59x speedup, the DSE with SA and GA can get an average reduction of 4.0% and 12.7%, respectively, in accuracy loss compared to random search, and RNS sharing reduces the average area and power by 41% and 47%, respectively.

We endeavor to make hardware fuzzing compatible with the standard IC development process and apply that to NoC verification in a real-world industrial environment. We systematically employ fuzzing throughout the entire NoC verification process, including router verification, network verification, and stress testing. As a case study, we apply our approach to an open-source NoC component in OpenPiton. Remarkably, our fuzzing methods automatically achieved complete code and functional coverage in the router and mesh network, and effectively detect injected starvation bugs. The evaluation results clearly demonstrate the practicability of our fuzzing approach to considerably reduce the manpower required for test case generation compared with traditional NoC verification.

SAT-based exact synthesis is a critical technique in logic synthesis to generate optimal circuits for given Boolean functions. The lengthy trial-and-error process limits its application in on-the-fly logic optimization and optimal netlist library construction. Previous research focuses on reducing the execution time of each trial. However, unnecessary SAT solver calls and varying execution times among encoding methods remained issues. This paper presents BESWAC to boost exact synthesis from the flow level. It leverages initial value prediction, encoding method selection, and an optional early exit to call SAT solvers efficiently and wisely. Moreover, BESWAC can seamlessly integrate existing acceleration methods focusing on individual trials. Experimental results show that BESWAC achieves a 1.79x speedup compared to state-of-the-art exact synthesis flows.

Exact synthesis is a critical technique in logic synthesis to generate optimal circuits for given Boolean functions. Recent progress in SAT solvers makes SAT-based methods practical. However, the intractable and unpredictable execution time has limited its application with potential quality degradation and runtime overhead. To ease such limitations, we propose an incremental SAT-based method for exact synthesis (IncSyn). It leverages previous knowledge to accelerate the finding of a new optimal circuit. IncSyn uncovers the relationships between functions and modifies the encoding and synthesis flow correspondingly. We speed up the exact synthesis by up to 15x and achieve scale advancements, solving considerable cases of up to 12-input Boolean functions within tolerable time. The proposed method reduces the average runtime for optimal library building and on-the-fly rewrite by 6% and 64%, respectively.

This paper introduces AceRoute, an adaptive compute-efficient FPGA router that tackles the long-standing issue of lengthy FPGA compilation times given complicated FPGA architectures and designs to synthesize. We thoroughly profile modern FPGA routing patterns and identify the runtime hotspot: routing bottleneck connections in congested designs. However, previous works on routing acceleration hardly target mitigating connection-wise routing difficulties by characterizing device resource expansions and shifting path-exploration modes of connections.

Sketch algorithms are crucial for data stream analysis, offering one-pass processing, sub-linear storage, and accuracy-performance balance. FPGA-based sketch accelerator helps sketch algorithms keep up with modern network inter-connections' speed. However, deploying and optimizing multiple sketches simultaneously is not widely considered, leaving a vast optimization space untouched. This paper introduces MuSA, a multi-sketch FPGA accelerator that exploits hybrid parallelism during sketch maintenance and coalesced memory organization for merging different sketch states. MuSA supports FIFO merging and architecture-specific parameter selection for hybrid parallelism, reducing memory consumption and enabling more considerable parallelism. Evaluation results validate MuSA's effectiveness, with a 15.2 x kernel performance enhancement compared to the state-of-the-art method, enabling on-the-fly high-speed network measurement and high-velocity database analysis.

Due to the escalating complexity of chip design and the exorbitant cost of building cutting-edge manufacturing facilities, outsourcing the fabrication of Integrated Circuits (ICs) is prevalent in modern semiconductor industry. However, significant security risks may arise because untrustworthy foundries can conduct insidious attacks without close supervision. Since prior works show the feasibility of implementing practical foundry-level Trojan attacks that circumvent post-fabrication detection, IC designers should protect their IC layouts before sending them to a third-party foundry, and such protections are known as design-time defenses. To this end, security metrics for layout vulnerability assessment are crucial to test the effectiveness of the proposed defenses. However, existing metrics are geometric-only and Trojan-oblivious, failing to capture the fundamental aspects of foundry-level Trojan insertion and the associated side effects.To bridge the gap between real attacks and threat prediction, we present SiliconCritic, a simulation-based, extensible framework that leverages design-time techniques to simulate the blackbox foundry-level Trojan attacks and post-fabrication analysis. SiliconCritic encodes the difficulty of inserting a specific Trojan into a finalized physical layout by measuring the variation of side-channel parameters (timing, power) after the simulated Trojan insertion, where larger deviations denote better detectability and thus enhanced security. SiliconCritic allows IC designers to interactively refine defensive strategies against the objective Trojan based on the feedback of side-channel analysis. Through evaluations on real-world ASIC designs and reported hardware Trojans, SiliconCritic demonstrates the limitations of existing layout-level defenses and highlights the influence of Trojan properties on defensive efficacy. Our work refreshes the understanding of Trojan prevention and suggests future directions for defenses against untrustworthy foundries.

Abstract Within the electronic design automation (EDA) domain, artificial intelligence (AI)-driven solutions have emerged as formidable tools, yet they typically augment rather than redefine existing methodologies. These solutions often repurpose deep learning models from other domains, such as vision, text, and graph analytics, applying them to circuit design without tailoring to the unique complexities of electronic circuits. Such an “AI4EDA” approach falls short of achieving a holistic design synthesis and understanding, overlooking the intricate interplay of electrical, logical, and physical facets of circuit data. This study argues for a paradigm shift from AI4EDA towards AI-rooted EDA from the ground up, integrating AI at the core of the design process. Pivotal to this vision is the development of a multimodal circuit representation learning technique, poised to provide a comprehensive understanding by harmonizing and extracting insights from varied data sources, such as functional specifications, register-transfer level (RTL) designs, circuit netlists, and physical layouts. We champion the creation of large circuit models (LCMs) that are inherently multimodal, crafted to decode and express the rich semantics and structures of circuit data, thus fostering more resilient, efficient, and inventive design methodologies. Embracing this AI-rooted philosophy, we foresee a trajectory that transcends the current innovation plateau in EDA, igniting a profound “shift-left” in electronic design methodology. The envisioned advancements herald not just an evolution of existing EDA tools but a revolution, giving rise to novel instruments of design-tools that promise to radically enhance design productivity and inaugurate a new epoch where the optimization of circuit performance, power, and area (PPA) is achieved not incrementally, but through leaps that redefine the benchmarks of electronic systems’ capabilities.

In modern times, domain-specific accelerators require numerous functional components to execute complex applications in a particular domain. To ensure efficient development, the conventional approach involves decomposing, implementing, and integrating modules. Over the past decade, the generator-based method has proven to enhance the productivity of module implementation. However, current abstractions pose challenges for integrating modules implemented by generators, due to implicit interface definitions, nonunified performance modeling, and fragmented memory management. These limitations result in a lower productivity of the integration process and decreased performance of the integrated accelerators. To overcome these drawbacks, we propose Weave, an abstraction for integrating generated modules and an agile design flow for domain-specific accelerators. The Weave abstraction guides module implementation and integration with a unified performance model and memory management. Furthermore, the Weave integration flow, consisting of generation, selection, and integration phrases, enables optimization of the performance of the integrated accelerator with a design space exploration algorithm and hierarchical memory management. In the experiments, the accelerator developed by Weave achieves$1.93\times $higher performance in the deep learning domain compared to an open-source accelerator, and the integrated accelerator maintains performance for various applications with different memory access patterns.

Power is a great concern in integrated circuits (ICs) design flow, especially in portable devices. As an early stage in electronic design automation (EDA), logic synthesis can significantly affect the quality of the design. It is essential to optimize power in logic synthesis. However, logic synthesis only has a limited concern in power due to its inaccurate estimation. This is because critical physical information is missing at this stage. Furthermore, the empirical optimization sequences need enhancement, and they are not optimal for power, while optimizing power in the early stage is effective. Technology mapping can also improve power optimization with comprehensive power metrics in this sub-15 nm era. Therefore, we propose PowerSyn, a logic synthesis framework with early power optimization. It consists of a practical power model, a power-oriented logic optimization module, and a technology mapping stage. The power model leverages probability propagation considering glitches and static power. The acrlong RL-based logic optimization generates high-quality and rapid-convergence command sequence with early power optimization. We also modify traditional technology mapping with novel power-related metrics. We evaluate PowerSyn on the EPFL benchmark suite. Experiment results show that our flow achieves an average power savings of 16.1% compared to the state-of-the-art open-source logic optimization flow. It also delivers an 8.8% and a 2.1% reduction in latency and area, respectively. The flow incurs less than 12.2% execution time overhead during inference for command generation.

With the ever-shrinking feature size of transistors, the exorbitant cost has driven the massive outsourcing of integrated circuits (IC) fabrication. However, this outsourcing poses significant security risks because untrustworthy foundries can conduct insidious fabrication-time attacks without close supervision. Therefore, it is crucial to undertake design-time protection before sending finalized design layouts to the foundry. Foundry-level hardware Trojan has emerged as a major security threat, but existing design-time countermeasures lack sufficient consideration of good trade-offs between design security and performance.This work proposes an automatic framework, GDSII-Guard, to strengthen implemented physical layouts against potential fabrication-time Trojan attacks while preserving design performance, power, and quality. We develop an Engineering Change Order (ECO) placement and routing (P&R) flow containing elaborate anti-Trojan operators to prevent Trojan insertion. Moreover, we introduce a multi-objective optimization model with evolutionary strategies that incorporate anti-Trojan flow information to exploit balances between the aforementioned multiple design metrics. Experimental results demonstrate that GDSII-Guard reduces the overall risk of Trojan attacks on given designs by 98.8% with minimized timing, power, and design quality impact, surpassing existing approaches prominently.

NPN classification is an essential problem in the design and verification of digital circuits. Most existing works explored variable symmetries and cofactor signatures to develop their classification methods. However, cofactor signatures only consider the face characteristics of Boolean functions. In this paper, we propose a new NPN classifier using both face and point characteristics of Boolean functions, including cofactor, influence, and sensitivity. The new method brings a new perspective to the classification of Boolean functions. The classifier only needs to compute some signatures, and the equality of corresponding signatures is a prerequisite for NPN equivalence. Therefore, these signatures can be directly used for NPN classification, thus avoiding the exhaustive transformation enumeration. The experiments show that the proposed NPN classifier gains better NPN classification accuracy with comparable speed.

As domain-specific accelerators demand multiple functional components for complex applications in a domain, the conventional wisdom for effective development involves module decomposition, module implementation, and module integration. In the recent decade, the generator-based design methodology improves the productivity of module implementation. However, with the guidance of current abstractions, it is difficult to integrate modules implemented by generators because of implicit interface definition, non-unified performance modeling, and fragmented memory management. These disadvantages cause low productivity of the integration flow and low performance of the integrated accelerators.

NPN classification has many applications in the synthesis and verification of digital circuits. The canonical-form-based method is the most common approach, designing a canonical form as representative for the NPN equivalence class first and then computing the transformation function according to the canonical form. Most works use variable symmetries and several signatures, mainly based on the cofactor, to simplify the canonical form construction and computation. This paper describes a novel canonical form and its computation algorithm by introducing Boolean influence to NPN classification, which is a basic concept in analysis of Boolean functions. We show that influence is input-negation-independent, input-permutation-dependent, and has other structural information than previous signatures for NPN classification. Therefore, it is a significant ingredient in speeding up NPN classification. Experimental results prove that influence plays an important role in reducing the transformation enumeration in computing the canonical form. Compared with the state-of-the-art algorithm implemented in ABC, our influence-aided canonical form for exact NPN classification gains up to 5.5x speedup.

IoT uplink performance is crucial for a wide variety of IoT applications such as health sensing and industrial control, which demand reliable delivery of sensor data to the cloud. However, due to the limited transmission power budget imposed on many power-constrained IoT devices, IoT uplinks are highly susceptible to cross-technology interference (CTI) caused by coexisting networks. Previous approaches to mitigating CTI have relied on MAC/PHY designs. They suffer from poor performance and limited generality in the presence of wideband CTI sources such as Wi-Fi and RF jammer, which transmit aggressively on large spectrum chunks using diverse radio technologies.

Super-resolution (SR) techniques aim to restore a high-resolution (HR) image from low-resolution (LR) images, which are often used to assist the enhancement of image/video quality under the rapid development of HR and high-frame-rate media. Recently, neural network (NN)-based methods perform much better image reconstruction quality than classical approaches. However, the unacceptable computation complexity as well as the huge memory footprints of NNs limit the throughputs and scalability of these SR systems. In this work, we analyze several key issues in the design of NN-based SR systems first. Then, we propose a three-level systematic optimization methodology for SR systems to reduce computation overhead and keep image quality. At the algorithm level, we introduce image blocking to SR tasks and develop a block-wise SR algorithm based on the hybrid of NN and interpolation with a consistent image block evaluation metric. The configurable hybrid parameters help the SR algorithm to achieve a flexible tradeoff between the computation overhead and image quality. At the operator level, we focus on the transpose convolution operators commonly used for upsampling in SR NNs. We propose an efficient Winograd-based transposed convolution acceleration method. Through the efficient subconvolutions conversion and the Winograd specialization, this methods enables unified Winograd transformations and simplified data access patterns. At the data level, we propose a novel quantization method for Winograd-aware SR NNs to get better-quantized accuracy. Comprehensive evaluations demonstrate the effectiveness of these optimizations. Our SR system reduces a large number of multiplications with great scalability and supports 4K@120 fps and 8K@30 fps outputs with acceptable image quality degradation.

Transposed convolution has been prevailing in convolutional neural networks (CNNs), playing an important role in multiple scenarios such as image segmentation and back-propagation process of training CNNs. This mainly benefits from the ability to up-sample the input feature maps by interpolating new information from the input feature pixels. However, the backward-stencil computation constrains its performance and hindered its wide application in diverse platforms. Moreover, in contrast to the efforts on accelerating the convolution, there is a rare investigation on the acceleration of transposed convolution that is identically compute-intensive as the former. For acceleration of transposed convolution, we propose an intermediate-centric dataflow scheme, in which we decouple the generation of the intermediate patch from its further process, aim at efficiently performing the backward-stencil computation . The intermediate-centric dataflow breaks the transposed convolution into several phases/stages, achieving feeding the input feature maps and performing the backward-stencil computation in a pipelining manner. It also provides four-degree computation parallelism and efficient data reuse of input feature maps/weights. Furthermore, we also theoretically analyze the irregular data dependence leveraging the polyhedral model, which constrains the parallel computing of transposed convolution. Additionally, we devise an optimization problem to explore the design space and automatically generate the optimal design configurations for different transposed convolutional layers and hardware platforms. By selecting the representative transposed convolutional layers from DCGAN, FSRCNN, and FCN, we generate the corresponding accelerator arrays of intermediate-centric dataflow on the Xilinx Alveo U200 platform and reach the performance of 3.92 TOPS, 2.72 TOPS, and 4.76 TOPS, respectively.

Multiplier-accumulator (MAC) is a crucial arithmetic element widely used in digital integrated circuits. Customized MACs are necessary for different scenarios but need great effort due to the huge architecture design space. In this paper, we develop EasyMAC, a flexible Chisel-based MAC generator with a canonical architectural representation. We design a compact and canonical sequence representation to express the architecture of MACs. And the MAC generator takes the compact representation as input to gain the Verilog codes. We also give a case study on developing a heuristic design space exploration (DSE) method based on this representation. The experimental result shows the effectiveness of the representation in DSE. Using the percent relative range of the power-delay-area product as a metric to measure the optimization opportunities that this representation exposes, the relative range is 17.4% and 23.1% for 16×16 and 25×18 MACs, respectively. At last, we discuss some promising directions of EasyMAC.

Modern heterogeneous multi-processor system-on-chips (SoCs) have diverse needs of area, performance, and scalability for on-chip networks (OCNs). And it remains a challenge to design, evaluate, and explore a suitable OCN for a specific SoC to meet different requirements. Some open-source OCN generators have been developed to generate synthesizable RTL codes, provide fast testing, and enable design space exploration. However, none of them provides the levels of abstraction to trade off the various needs.In this paper, we propose Purlin, a versatile toolkit for the generation and simulation of OCNs. We put forward a uniform network generation and simulation flow across distributed routing, source routing, and circuit-switched OCNs to enable effective trade-offs. Purlin enables network customization through the network basic, flow control, and routing function interfaces and provides some predefined architectures. Among the architectures, the latency-optimized distributed routing OCN reduces 79.3% latency compared to a state-of-the-art OCN generator. With the routing function customization interface, we implement a deadlock-free adaptive routing function in the library, which reduces 16.1% latency. We provide compilation tools with customizable routing algorithms to generate the packet headers in source-routing or the configurations in circuit-switched OCNs from a programmed destination address. A source routing OCN using a customized routing algorithm further reduces 8.4% latency compared to a distributed routing OCN.

In this paper, we show that true 3D placement approaches, enhanced with reinforcement learning, can offer further PPA improvements over pseudo-3D approaches. To accomplish this goal, we integrate an academic true 3D placement engine into a commercial-grade 3D physical design flow, creating ART-3D flow (Analytical 3D Placement with Reinforced Parameter Tuning-based 3D flow). We use a reinforcement learning (RL) framework to find optimized placement parameter settings of the true 3D placement engine for a given netlist and perform high-quality 3D placement. We then use an efficient 3D optimization and routing engine based on a commercial place and route (P&R) tool to maintain or improve the benefits reaped from true 3D placement till design signoff. We evaluate our 3D flow by designing several gate-only and processor benchmarks on a commercial 28nm technology node. Our proposed 3D flow involving true 3D placement offers the best PPA results compared to existing 3D P&R flows and reduces power consumption by up to 31%, improves effective frequency by up to 25%, and therefore reduces power-delay product by up to 43% compared with commercial 2D IC design flow. These improvements predominantly come from RL-based parameter tuning, as it improves the performance of the 3D placer by up to 12%.

Edge Computing has emerged as a new computing paradigm dedicated for mobile performance enhancement and energy efficiency purposes. Specifically, it benefits today’s interactive applications on power-constrained devices by offloading compute-intensive tasks to the edge nodes in close proximity. Meanwhile, FPGA is well known for its excellence in accelerating (domain-specific) compute-intensive tasks such as deep learning algorithms in a high performance and energy-efficient manner due to its hardware-customizable nature. In this paper, we make the first attempt to leverage and combine the advantages of these two, and proposed a new network-assisted computing model, namely FPGA-based edge computing. As a case study, we choose three computer vision (CV)-based mobile interactive applications, and implement their back-end computation engines on FPGA. By deploying such application-customized accelerator modules for computation offloading at the network edge, we experimentally demonstrate that this approach can effectively reduce response time for the applications and energy consumption for the entire system in comparison with traditional CPU-based edge/cloud offloading approach.

Coarse-grained reconfigurable architecture (CGRA) is a promising programmable device with high performance and power efficiency. The CGRA compilation problem is to map an application onto a 3D time-space model of CGRA. Adding the circuitry of synchronizers can relax the mapping constraint for data alignment in time; and thus, it significantly influences the compilation performance. However, data-departure synchronizers may be infeasible, because an output value may be used multiple times and has a high fan-out. Instead, data-arrival synchronizers can further improve performance and mappability of CGRAs with acceptable overhead, compared to the synchronization methods based on detour routing, register files, and FIFO.In this work, we design two kinds of data-arrival synchronizers and formulate them in an integer linear programming (ILP) based mapping approach. The separate ILP formulations of placement and routing speed up the architecture exploration with synchronizers by up to 3.03x. The experimental study shows that data-arrival synchronizers improve CGRA performance by 19.8% on average. The results of our quantitative study show that synchronizers also improve the mapping success rate by 1.91x on average. In conclusion, CGRAs with appropriate synchronizers have better mappability while using fewer resources.

In recent years, Graph Neural Networks (GNNs) appear to be state-of-the-art algorithms for analyzing non-euclidean graph data. By applying deep-learning to extract high-level representations from graph structures, GNNs achieve extraordinary accuracy and great generalization ability in various tasks. However, with the ever-increasing graph sizes, more and more complicated GNN layers, and higher feature dimensions, the computational complexity of GNNs grows exponentially. How to inference GNNs in real time has become a challenging problem, especially for some resource-limited edge-computing platforms.To tackle this challenge, we propose BlockGNN, a software-hardware co-design approach to realize efficient GNN acceleration. At the algorithm level, we propose to leverage block-circulant weight matrices to greatly reduce the complexity of various GNN models. At the hardware design level, we propose a pipelined CirCore architecture, which supports efficient block-circulant matrices computation. Basing on CirCore, we present a novel BlockGNN accelerator to compute various GNNs with low latency. Moreover, to determine the optimal configurations for diverse deployed tasks, we also introduce a performance and resource model that helps choose the optimal hardware parameters automatically. Comprehensive experiments on the ZC706 FPGA platform demonstrate that on various GNN tasks, BlockGNN achieves up to 8.3× speedup compared to the baseline HyGCN architecture and 111.9× energy reduction compared to the Intel Xeon CPU platform.

Transposed convolution is a learnable up-sampling operator widely-used in deep neural networks. It up-samples the input activations to generate useful information in applications like style transfer and super resolution. There exists a rising demand for accelerating transposed convolution layers since they occupy a large portion of computation in GAN-like networks.

Transmission electron tomography (TET) is a widely used biomedical imaging technique. Iterative reconstruction with regularization is the common approach to obtain high-quality reconstructed images for TET. Mumford-Shah (MS) regularization has the advantage in preserving image edges; but it is computation and memory-intensive because it is NP-hard when applied to TET. In this work, we design an FPGA accelerator for iterative image reconstruction for TET with the MS regularization. We first design the accelerator with multiple processing elements (PE) to leverage the parallelism in the TET reconstruction. We then schedule the forward projection and back projection according to the imaging geometry of TET to optimize off-chip memory access. Finally, we optimize the local buffer with customized partitioning for the stencil memory access of basic operations to increase the throughput of a single PE. Our FPGA accelerator achieves 6.68X and 1.87X speedup with the same image quality compared with the same algorithm implemented on CPU and GPU, respectively. And the off-chip bandwidth requirements of forward and back projection are reduced by one to two orders of magnitude. Compared with the state-of-the-art acceleration works on GPU and FPGA, we achieve 1.18X and 1.91X throughput, respectively.

Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few variables, because the time complexity of such an algorithm for an n-variable Boolean function is O(2n+1n!). Sensitivity is an important characteristic and a measure of the complexity of Boolean functions. It has been used in analysis of the complexity of algorithms in different fields. This measure could be regarded as a signature of Boolean functions and has great potential to help reduce the search space of Boolean matching. In this paper, we introduce Boolean sensitivity into Boolean matching and design several sensitivity-related signatures to enhance fast Boolean matching. First, we propose some new signatures that relate sensitivity to Boolean equivalence. Then, we prove that these signatures are prerequisites for Boolean matching, which we can use to reduce the search space of the matching problem. Besides, we develop a fast sensitivity calculation method to compute and compare these signatures of two Boolean functions. Compared with the traditional cofactor and symmetric detection methods, sensitivity is a series of signatures of another dimension. We also show that sensitivity can be easily integrated into traditional methods and distinguish the mismatched Boolean functions faster. To the best of our knowledge, this is the first work that introduces sensitivity to Boolean matching. The experimental results show that sensitivity-related signatures we proposed in this paper can reduce the search space to a very large extent, and perform up to 3x speedup over the state-of-the-art Boolean matching methods.

Recently, the emerging resistive random access memory (RRAM) shows its potential to construct a processing-in-memory (PIM) architecture. It supports a variety of computation modes, including the digital mode and the analog mode. Both modes can perform parallel computation inside an RRAM crossbar. However, the lack of automatic synthesis flow limits their application scenarios. Although previous works implement several large-scale applications, e.g., image processing algorithms and neural networks, using these two modes, most of their implementations are designed manually or semi-manually. In our view, the lack of a specific application representation is a limiting factor for developing a synthesis flow. Therefore, in this work, we propose the skeleton as an application representation. Users can model applications and their potential parallelism in RRAM with nested skeletons and primitive operations. Then, we propose SSR, a skeleton-based flow that can automatically synthesize large-scale applications to RRAM crossbars. For an application represented in skeletons, SSR first partitions it into the digital part and the potential analog part. After that, SSR optimizes primitive operations and allocates bounding boxes to skeletons for both parts under the guide of pre-synthesis results. Finally, SSR maps bounding boxes of skeletons onto crossbars to enable pipelined computation. Experimental evaluations on several popular applications show that SSR improves throughput, latency, and area multiple times over previous works.

Advanced Driver-Assistance Systems (ADAS) are complex systems consisting of many computer vision tasks including image classification, object detection and semantic segmentation. FPGA is a feasible solution for deep learning based computer vision accelerator due to its high performance and energy efficiency. However, design a high performance FPGA accelerator requires good understanding of basic hardware concepts and consumes a long compilation time. Overlays can alleviate the above problems by accelerating applications in a software via a hardware architecture and a compiler. In this paper, we propose an FPGA-based neural network overlay processor for ADAS. The overlay architecture contains almost all common computation layers for learning based ADAS. In addition, we design a compiler that can automatically compile the high-level description of neural networks from deep learning framework like Caffe and Tensorflow into FPGA configurable codes, which can be executed by our overlay architecture without reprogramming. Experiments show that our overlay can process learning tasks in ADAS with low latency and low memory usage.

X-ray computed tomography (CT) is commonly used to obtain vivo images to characterize diseases but results in radiation exposure to patients. Low-dose CT (LDCT) provides CT images of clinical quality with reduced cumulative radiation dose. Iterative image reconstruction methods with effective regularization are used for LDCT but generally require more computing resources and induce higher computational load than the conventional filtered backprojection (FBP) methods. The high computational demand of the iterative reconstruction (IR) with notably increased reconstruction time precludes its routine clinical application. In this work, we focus on the FPGA acceleration of a compute-intensive full IR (full-IR) algorithm based on the Mumford-Shah regularization. At the algorithmic level, we propose a beam-based asynchronous update algorithm to reduce the computational cost and alleviate the conflicts. At the hardware-level, we first present pipeline-friendly optimization for the original algorithm to increase the computation throughput. We then apply the LDCT-specific tiling strategy to improve the data reuse rate. The experimental results show that our implementation takes 8.5 min to reconstruct a typical physical phantom with the image quality comparable with the vendor's result. The FPGA implementation achieves 11.6× throughput against the state-of-the-art GPU version.

Routing is a very complex process in the field programmable gate array (FPGA) CAD flow. The increase of both FPGA size and design complexity leads to a long routing time hindering the productivity. In this article, we propose a more effective parallel router that combines static and dynamic load balance in parallel routing for FPGAs. First, we explore hierarchical region partitioning to assign routing tasks to different cores for static load balance. Then, we coordinate message propagation and task migration at runtime so that load balance between cores can be dynamically maintained in parallel routing. Finally, we combine static and dynamic load balance in the parallel routing for a higher degree of parallelism. Our parallel router performs on the multicore distributed-memory systems and the communication between cores is through message passing interface messages. We demonstrate the effectiveness of our parallel router using large-scale Titan designs. On average, our parallel router can scale up to 32 cores to achieve about 17× speedup with slight loss of quality, compared with the latest VTR 8 router.

Processing-in-memory (PIM) exploits massive parallelism with high energy efficiency and becomes a promising solution to the von Neumann bottleneck. Recently, the emerging metal-oxide resistive random access memory (RRAM) shows its potential to construct a PIM architecture, because several stateful logic operations, e.g., IMP and NOR, can be executed in an RRAM crossbar in parallel. Previous synthesis flows focus on improving latency with stateful logic operations, but they ignore that the memory should be used primarily for storage. i.e., most of the area in the crossbar is used for computation but not storage. In this situation, storage and computation still have to be separated into different crossbars, which leads to considerable data transfer overhead and limited parallelism. In this work, we define the ratio of storage in a crossbar as area utilization. We aim to improve the area utilization without throughput loss by proposing STAR, a novel synthesis flow for the stateful logic. We present two optimization strategies to reduce the computation area in STAR. First, we reduce the area for redundant inputs. For the shared constants among different rows (or columns), we encode them as immediate values into the control signals without writing them into the crossbar at runtime. For the other inputs, we only store one copy of them in the crossbar. Second, we reduce the area for intermediate variables by reusing invalid cells. And we design a scheduling algorithm to find a computation sequence with the minimal variable erasing cycles. Invalid primary inputs can also be erased in this algorithm. Furthermore, we present a case study of the image convolution to demonstrate the effectiveness of STAR. Experimental evaluation shows that STAR achieves 33.03% more area utilization and a 1.43x throughput compared to SIMPLER, the state-of-the-art stateful logic synthesis flow. Our image convolution implementation also provides 78.36% more area utilization and a 1.48x throughput compared with IMAGING, the state-of-the-art stateful logic-based image processing accelerator.

Routing is a very time-consuming stage in the FPGA design flow, significantly hindering the productivity. This article proposes CPRS, a coarse-grained parallel routing scheme in a distributed computing environment. First, we partition entire routing region to guide the assignment of nets for parallel processing. The partitioning is a recursive fashion, and at each recursive partitioning, the region is partitioned into two subregions forming three subsets of nets. The first subset consists of potentially dependent nets and they are distributed in different subregions. The remaining two subsets consist of potentially independent nets and they are distributed in their own subregions. Second, we route the nets of first subset in serial and process the remaining two subsets in parallel. The parallel processing is a coarse-grained fashion, which is implemented by MPI parallel programming model. Finally, we explore the optimization of both partitioning and parallel processing to further improve the overall speedup of parallel routing. In addition, we adopt MPI message to synchronize the intermediate results between different cores in parallel routing for a feasible solution. Experiments use a set of commonly used benchmarks to demonstrate the effectiveness of CPRS. Notably, CPRS achieves about 18× speedup on average using 32 processor cores with minor loss of quality, compared with the VTR 7.0 serial router. There is about 1.6× improvement over the state-of-the-art parallel router.

Service live migration means migrating the running services from one machine to another with negligible service downtime. It has been considered as a powerful mechanism to facilitate service management. However, conventional live migration methods always come with expensive cost of data transmission, and thus can hardly be applied to a real-world edge computing system directly due to the limited network bandwidth. To tackle this problem, some recent works present various techniques to reduce the data transmission.However, these techniques for data transmission reduction always introduce extra computational costs, which have a great impact on the quality of service (QoS), especially in edge systems containing lots of nodes with insufficient computational resources. To alleviate this issue, we propose an insight to offload data reduction computations to a specific hardware accelerator, thus reducing the burden of CPU cores. To this end, we present a novel hardware accelerator design to speed up the data transmission reduction computations to accelerate the service live migration. For evaluation, we implement a prototype on an FPGA platform. Compared to the normal CPU-based approaches, our specialized accelerator is 3.1× faster, 2.9× more-energy efficient, and can reduce 29%∼47% of total migrating time and 24%∼40% of service downtime in our cases. Furthermore, our architecture has great scalability and is easy-configurable to achieve a balance between cost and performance.

In the process of tomographic reconstruction, the attitude and center point of a specimen, from which the projection data are collected, suffer from misalignment due to mechanical imperfection and calibration error. Such misalignment leads to poor reconstruction quality. And effective automatic alignment approaches have been proposed. The alignment approaches are of good use for kinds of application scenarios such as X-CT and electron tomography. These scenarios demand not only high performance, but also that the component of automatic alignment can be integrated and upgraded in the whole solution. Thus, we propose an FPGA accelerator for state-of-the-art tomographic alignment algorithm. We first introduce a multi-ray access approach that modifies the order of data access for easier on-chip data management. Making use of BRAMs on FPGAs and effective local data management strategy, data reuse is reinforced, and data transfer latency with DRAM is covered by computation. Also, we introduce an FPGA-customized processing engine at a low cost to improve data throughput. Moreover, a streaming structure with multiple paralleled PEs further improves the performance of our algorithm. Experiments demonstrate that our accelerator achieves a 44. 5x speed-up for the state-of-the-art alignment on Xilinx ZCU102 over a 16-thread multicore CPU implementation, and a 1. 60x speed-up with 7. 8x energy reduction over an OpenCL implementation on Nvidia Titan V.

FPGAs are becoming significant for implementing low-latency convolutional neural networks, because of performance demands and power constraints. Conventional implementations of convolutional layers are usually direct convolution, involving nested loops over channels, feature maps, and filters. Explicit general matrix multiplications (GEMMs) cost extra memory space, and the limited on-chip RAMs prevent an efficient GEMM-based implementation. In this paper, we evaluate a low-memory method of GEMMs on FPGAs based systolic arrays. We design a novel accelerator to save the bandwidth and increase the parallelism. We evaluate our design on MobileNet V1 and Inception V4. Our implementation achieves a throughput of around 3.5 TOP/s for both models. We also reduce the memory usage by 21% compared to explicit GEMM implementation for MobileNet V1 and 44% for Inception V4.

In this work, we aim to accelerate the iterative reconstruction (IR) algorithm used for 3D low dose computer tomography (LDCT) reconstruction to reduce the long execution time from an order of several hours on CPU to a few minutes. IR algorithms such as Mumford-Shah (MS) regularization can be used to get high-quality images even though the signal-noise ratio (SNR) of low dose projection data is low. However, IR is a computation and memory-intensive application and the long execution time precludes its clinical application. We adopt the ray-based parallel algorithm and designed a customized processing engine with multiple parallel processing elements (PEs) on field-programmable gate array (FPGA) to improve the computation efficiency. To reduce resource utilization, we proposed a best-first search algorithm combined with pruning to find the optimal bit width for fixed-point reconstruction. Besides, an offline memory optimization framework based on a greedy based clustering algorithm is proposed to reduce external memory bandwidth requirement and balance the workload of parallel PEs. Experiments on a 3D Shepp-Logan phantom show 2.81X and 1.91X speedup over the state of art single GPU and FPGA implementation.

Modern commercial Field-Programmable Gate Array (FPGA) architectures support dual-output look-up tables (LUTs). If the number of total inputs in two small LUTs do not exceed the constraint, e.g., 5 in Xilinx UltraScale+ series, we can pack them into one dual-output LUT to reduce area, i.e., the number of LUTs. However, previous works have not fully utilized this feature. They usually generate single-output LUTs in the technology mapping phase and merge LUTs in a later packing phase. In this situation, they cannot get LUT merging information during technology mapping and will generate some single-output LUTs that are not suitable for merging.

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13× speedup compared to the state-of-the-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.

With the advanced communication sensors are deployed into the modern connected vehicles (CVs), large amounts of traffic information can be collected in real-time, which gives the chance to explore the various techniques to control the routing of CVs in a ground traffic network. However, the control of CVs often suffers from energy inefficiency due to the constant changes of network capacity and traffic demand. In this paper, we propose a cost-based iterative framework, named EEPC, to explore the energy-efficient parallel control of connected vehicles. EEPC enables the control of CVs to iteratively generate a feasible solution, where the control of each vehicle is guided in an energy-efficient way routing on its own trajectory. EEPC eliminates the conflicts between CVs with a limited number of iterations and in each iteration, EEPC enables each vehicle to coordinate with other vehicles for a same road resource of the traffic network, further determining which vehicle needs the resource most. Note that at each iteration, the imposed cost is updated to guide the coordination between CVs while the energy is always used to guide the control of CVs in EEPC. In addition, we also explore the parallel control of CVs to improve the real-time performance of EEPC. We provide two parallel approaches, one is fine grain and the other is coarse grain. The fine grain performs the parallel control of single-vehicle routing while the coarse grain performs the parallel control of multi-vehicle routing. Note that fine grain adopts multi-threading techniques and coarse grain adopts MPI techniques. The simulation results show that the proposed EEPC can generate a feasible control solution. Notably, we also demonstrate that the generated solution is effective in eliminating the resource conflicts between CVs and in suggesting an energy-efficient route to each vehicle. To the best of our knowledge, this is the first work to explore energy-efficient parallel control of CVs.

Processing-in-memory (PIM) provides massive parallelism with high energy efficiency and becomes a promising solution to the memory wall problem. Recently, the emerging metal-oxide resistive random access memory (RRAM) has shown its potential to design a PIM architecture. Several stateful logic operations, e.g., NOR and NAND, can be executed in parallel in an RRAM crossbar. Although previous works have designed some algorithms using the stateful logic, it is still under exploration how to fully exploit its potential high parallelism and design an asymptotically fast algorithm for a given function. In this work, we theoretically analyze the parallelism in an RRAM crossbar and design several asymptotically optimal arithmetic algorithms. In detail, we first propose the Single Instruction Multiple Lines (SIML) model to unify the stateful logic families and prove three lower bounds on the time complexity of a parallel RRAM algorithm. Then, we design three algorithms for integer addition functions with the stateful logic, guided by the lower bound analysis. All of them reach the time complexity lower bound. Finally, We make two extensions of the integer addition algorithms, supporting multiplication functions by decomposing them to additions and supporting the flex-point data type by proposing an exponent and mantissa update flow. Experimental evaluation shows that our integer algorithms achieves a speedup up to 13.79x over the previous RRAM algorithms. Our flex-point implementation achieves a 26.60x speedup and saves 73.68% energy compared to an ARM.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is limited due to higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on asymmetric multi-FPGA architectures. In this approach, the neural network mapping can be formulated as a resource allocation problem. We design a dynamic programming-based partitioning to solve this problem optimally. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Transposed convolution, which is often used to scale up feature maps in various computer vision tasks, is a structural inverse process of convolution. Both convolution and transposed convolution, if any, account for the majority of computation in the inferences of deep neural networks. While convolution has been studied extensively, there are few investigations on accelerating transposed convolution. In this paper, we propose a fast algorithm, FTConv, to reduce the computation of transposed convolution using the Winograd algorithm, which has also been used for convolution with small kernels. Specifically, a transposed convolution can be converted into multiple convolutions after dividing the kernel into several congruence classes. Thus, we can accelerate the multiple convolutions using a modified Winograd algorithm. The transposed convolution can be obtained by interleaving output feature elements of each congruence class. We also design a Winograd ALU in four pipeline stages to further accelerate the computation on FPGA. By carefully designing a sliding window for on-chip buffer reuse according to the memory access pattern of transposed convolution, we save the memory bandwidth by 88.2% compared with a straightforward method. We evaluate FTConv using FSRCNN-s, a neural network for super-resolution. The number of multiplications in the transposed convolution layer can be reduced by 69% over the direct computation of FSRCNN-s.

FPGAs are commercially available off-the-shelf for implementing convolutional neural network (CNN) accelerators to trade off accuracy, performance, and power. Systolic array architecture for CNN accelerators on FPGAs has the potential to run at a high frequency due to its regular and simple interconnections. However, current FPGA CAD tools are unable to synthesize and layout systolic arrays in high quality. In this paper, we identify the reasons for the frequency degradation of systolic array designs for CNN accelerators. We also propose two methods to improve the frequency at the front-end and the back-end, respectively. The experimental results show that our methods are able to achieve 1.29 × higher frequency and attain 1.5TOPS for the VGG16 network on the Xilinx KCU1500 platform.

Coarse-grained reconfigurable architectures (CGRAs) have drawn increasing attention due to their flexibility and energy efficiency. Data flow graphs (DFGs) are often mapped onto CGRAs for acceleration. The problem of DFG mapping is challenging due to the diverse structures from DFGs and constrained hardware from CGRAs. Consequently, it is difficult to find a valid and high quality solution simultaneously. Inspired from the great progress in deep reinforcement learning (RL) for AI problems, we consider building methods that learn to map DFGs onto spatially programmed CGRAs directly from experiences. We propose RLMap, a solution that formulates DFG mapping on CGRA as an agent in RL, which unifies placement, routing and processing element insertion by interchange actions of the agent. Experimental results show that RLMap performs comparably to state-of-the-art heuristics in mapping quality, adapts to different architecture, and converges quickly.

Field Programmable Gate Arrays (FPGAs) are reconfigurable architectures able to provide a good balance between energy efficiency and flexibility with respect to CPUs and ASICs. The main drawback in using FPGAs, however, is their timing-consuming routing process, significantly hindering the designer productivity. An emerging solution to this problem is to accelerate the routing by parallelization. Existing attempts of parallelizing the FPGA routing either do not fully exploit the parallelism or suffer from an excessive quality loss. Massive parallelism using GPUs has the potential to solve this issue but faces non-trivial challenges. To cope with these challenges, this paper explores GPU-accelerated routing approach for FPGAs. We leverage the idea of problem size reduction by limiting the single-net routing in a small subgraph rather than in an entire graph, further enabling the GPU-friendly shortest path algorithm to be used in FPGA routing. We maintain the convergence after problem size reduction by using the dynamic expansion of the routing resource subgraph, where the routing region of subgraph will be progressively expanded to find a feasible solution to each net. In addition, we are based on a GPU platform to explore the fine-grained single-net parallel routing in three ways and propose a hybrid approach to combine the static and dynamic parallelization for better speedup in FPGA routing. To explore the coarse-grained multi-net parallelization, We propose a dynamic programming-based partitioning algorithm to parallelize the routing of multiple nets while generating the equivalent routing results as the original single-net routing. Experimental results show that our proposed approach can provide an average of about 21.53× speedup on a single GPU with a tolerable loss in the routing quality and maintain a scalable speedup on large-scale routing resource graphs. To our knowledge, this is the first work to demonstrate the effectiveness of GPU-accelerated routing for FPGAs.

The market benefits from a barrage of Ultra High Definition (Ultra-HD) displays, yet most extant cameras are barely equipped with Full-HD video capturing. In order to upgrade existing videos without extra storage costs, we propose an FPGA-based super-resolution system that enables real-time Ultra-HD upscaling in high quality. Our super-resolution system crops each frame into blocks, measures their total variation values, and dispatches them accordingly to a neural network or an interpolation module for upscaling. This approach balances the FPGA resource utilization, the attainable frame rate, and the image quality. Evaluations demonstrate that the proposed system achieves superior performance in both throughput and reconstruction quality, comparing to current approaches.

FPGA is reconfigurable architecture able to implement a good trade-off in terms of energy, performance, and flexibility. However, the main drawback in using FPGAs is their very long routing time. Multi-core processors are now ubiquitous, making parallelism an increasingly attractive direction to accelerate the routing time. In this paper, we propose a task-level distributed parallel router that exploits conflict-aware box expansion and equal-sized grid partitioning for parallel FPGA routing. In box expansion, we adopt net bounding box to limit the search space of routing and based on current congestion state among nets, we design conflict-aware box expansion to optimize the serial routing time and provide more non-conflicting nets to obtain significant parallelism. In grid partitioning, we employ equal-sized grid to partition the overall routing region, where the nets in same grid are routed in serial and the grids are processed in parallel. Specifically, the nets distributed in multiple grids can be used to balance the workloads among processor cores. Experiments show that the parallel implementation scales to an average speedup of about 21 × using 32 processor cores compared to state-of-the-art VPR router.

Mainstream FPGA tools contain an extensive set of user-controlled compilation options and internal optimization strategies that significantly impact the design quality. These compilation and optimization parameters create a complex design space that human designers may not be able to effectively explore in a time-efficient manner. In this work we describe DATuner, an open-source extensible distributed autotuning framework for optimizing FPGA designs and design automation tools using an ensemble of search techniques managed by multi-armed bandit algorithms. DATuner is designed for a distributed environment that uses parallel searches to amortize the significant runtime overhead of the CAD tools. DATuner provides convenient interface for extension to user-supplied tools, which enables the end users to apply DATuner to design tools/flows of their interest. We demonstrate the effectiveness and extensibility of DATuner using three case studies, which include clock frequency optimization for FPGA compilation, fixed-point optimization, and autotuning logic synthesis transformations.

Serial equivalency can provide easier regression testing and customer support in production-grade CAD software. While existing parallel routing techniques have become sufficiently advanced to accelerate the execution time, support for serial equivalency has been very limited or ignored due to it was considered costly. In this paper, we propose serial-equivalent parallel routing for FPGAs. We use an optimal dependency-aware scheduling to facilitate serial equivalency of parallel routing algorithm. This capability enables the same answer as the serial version of the parallel algorithm, regardless of how many processing cores are used. We also validate this property across different hardware platforms. Further experimental results show that we achieve a 14.27x speedup on the MPI-based distributed parallel computer and a 19.65x speedup on the GPU-based massively parallel machine. To our knowledge, it is the first parallel routing with a serial equivalency guarantee.

Placement is probably the most critical process in the FPGA design flow. The demand for high performance continues to increase, but existing placers are still faced with numerous challenges including very long runtime, poor scalability, and restricted space exploration. In this paper we propose a novel timing-driven placement algorithm called BoxPlacer, which is supported by the force directed concept. BoxPlacer firstly uses a simple policy to create the initial box for placement. Then a force-directed iterative scheme is used to reduce the box size and determine the global placement. At last, the same concept is employed to eliminate the overlaps between reduced boxes to ensure the legalization in detailed placement. Notice that timing is always used to drive the placement in BoxPlacer. We demonstrate the effectiveness of our BoxPlacer by comparing the experimental results with that produced by the academic simulated annealing-based placer. Notably, our BoxPlacer achieves on average about 8x runtime advantage with 9% smaller critical path delay and 6% shorter wirelength.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single-FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is very limited due to they require higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on an asymmetric multi-FPGA architecture. Relative to the state-of-the-art single-FPGA resource reuse for large-scale DNNs, we consider multi-FPGA fashion to strive for higher performance. In this fashion, the neural network mapping problem can be formulated as a resource allocation problem, and a dynamic programming-based partitioning is designed to solve this problem optimally. Notice that the network topology and communication bandwidth of multiple FPGAs are always used to guide the partitioning to boost the performance while satisfying the constraints of resource-performance trade-off in a single FPGA. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Stochastic gradient descent (SGD) is a widely-used algorithm in many applications, especially in the training process of deep learning models. Low-precision implementation for SGD has been studied as a major acceleration approach. However, if not appropriately used, low-precision implementation can deteriorate its convergence because of the rounding error when gradients become small near a local optimum. In this work, to balance throughput and algorithmic accuracy, we apply the Q-learning technique to adjust the precision of SGD automatically by designing an appropriate decision function. The proposed decision function for Q-learning takes the error rate of the objective function, its gradients, and the current precision configuration as the inputs. Q-learning then chooses proper precision adaptively for hardware efficiency and algorithmic accuracy. We use reconfigurable devices such as FPGAs to evaluate the adaptive precision configurations generated by the proposed Q-learning method. We prototype the framework using LeNet-5 model with MNIST and CIFAR10 datasets and implement it on a Xilinx KCU1500 FPGA board. In the experiments, we analyze the throughput of different precision representations and the precision-selection of our framework. The results show that the proposed framework with adapative precision increases the throughput by up to 4.3× compared to the conventional 32-bit floating point setting, and it achieves both the best hardware efficiency and algorithmic accuracy.

Low-dose X-ray computed tomography (XCT) is a popular imaging technique to visualize the inside structure of object non-destructively. Model-based Iterative Reconstruction (MBIR) method can reconstruct high-quality image but at the cost of large computational demands. Therefore, MBIR of ten resorts to the platforms with hardware accelerators such as GPUs to speed up the reconstruction process.

Recently, Edge Computing has emerged as a new computing paradigm dedicated for mobile applications for performance enhancement and energy efficiency purposes. Specifically, it benefits today's interactive applications on power-constrained devices by offloading compute-intensive tasks to the edge nodes which is in close proximity. Meanwhile, Field Programmable Gate Array (FPGA) is well known for its excellence in accelerating compute-intensive tasks such as deep learning algorithms in a high performance and energy efficiency manner due to its hardware-customizable nature. In this paper, we make the first attempt to leverage and combine the advantages of these two, and proposed a new network-assisted computing model, namely FPGA-based edge computing. As a case study, we choose three computer vision (CV)-based interactive mobile applications, and implement their backend computation parts on FPGA. By deploying such application-customized accelerator modules for computation offloading at the network edge, we experimentally demonstrate that this approach can effectively reduce response time for the applications and energy consumption for the entire system in comparison with traditional CPU-based edge/cloud offloading approach.

FPGAs play a crucial role in the space of customizable accelerators over the next few years. A chief limiting factor is that FPGA CAD tools are cumbersome and time-consuming to most application developers. Routing is the most complex step in FPGA design flow and NP-complete problem. The PathFinder routing algorithm is in dominant use in FPGA CAD research. However, PathFinder is sequential in nature and lengthy in runtime. Parallelization has the potential to solve the issue but faces non-trivial challenges. In this work we introduce Megrez that uses strictly-ordered partitioning to explore the parallelism on GPU. Experimental results show that Megrez achieves an average of 15.13× speedup on GPU with negligible influence on the routing quality.

Routing is a time-consuming process in the FPGA design flow. Parallelization is a promising direction to accelerate the routing. While synchronous parallelization can converge a feasible solution, the ideal speedup is rarely achieved due to excessive communication overheads. Asynchronous parallelization can provide an almost linear speedup, but it is difficult to converge in the limited number of iterations due to net dependency. In this paper we propose SAPRoute, which coordinates synchronous and asynchronous parallelism on distributed multiprocessing environment to accelerate the routing for FPGAs. The objective is to boost the more speedup of parallel routing algorithm under the requirement of convergence. To the best of our knowledge, this is the first work to study the impact of synchronization and asynchronization during parallelization. Experimental results show that our approach have negligible explicit synchronization overhead and achieves significant speedup improvement over a set of commonly used benchmarks. Notably, SAPRoute produces the speedup of 24.27× on average compared to the default serial solution.

Quantitative effects of Moore's Law have driven qualitative changes in FPGA architecture, applications, and tools. As a consequence, the existing EDA tools takes several hours or even days to implement the applications onto FPGAs. Typically, routing is a very time-consuming process in the EDA design flow. While several attempts have accelerated this process through parallelization, they still do not provide a strong parallel scheme for FPGA routing. In this paper we introduce a dependency-aware parallel approach, named Bamboo, to accelerate the routing time for FPGAs. With the dependency detection, Bamboo partitions the nets into multiple subsets, where the nets in the same subsets are independent, and the dependency only exists among different subsets. Specifically, the independent nets in the same subset are routed in parallel, and the subsets are processed in serial according to the original routing ordering. The partitioning problem is solved optimally using dynamic programming, and the parallelization is implemented by speculative parallelism on a single GPU. Experimental results show that our approach achieves an average of 15.13x speedup with negligible influence on the routing quality. Most importantly, it effectively maintains deterministic results and always produces the same results as the serial version.

The non-exact projective NPNP (NP3) Boolean matching problem is practically significant in the applications of technology mapping, logic verification, and hardware security. However, its difficulty compels an unsatisfactory running time, and conventional algorithms for the basic NPNP Boolean matching problem perform terribly on the non-exact and projective type. In this paper, we propose a novel algorithm to solve this newly rising NP3 Boolean matching problem, and multiple types of optimization were applied to further improve the performance. Experimental results indicate that our algorithm has outstanding outcomes.

Traditional transportation systems in metropolitan areas always suffer from energy inefficiencies, evidenced by its uncoordinated behaviors such as system capacity and traffic demand change. With the advanced networked sensors are prevalent deployed into the autonomous vehicles, the information of system status and traffic demand can be collected in real-time. These information provides the potential to perform different types of coordination and control for autonomous vehicles in large-scale intelligent transportation systems. In this paper, we design a coordination-based energy-aware control method for large-scale connected vehicles, named Tiguan. Tiguan enables an iterative scheme to compute a practicable solution, which all vehicles are controlled on different trajectory paths of ground traffic network while achieving the close to the optimal performance. Safety is guaranteed by enabling vehicle to autonomously coordinate with other vehicles for a road traffic resource, and thus determine which vehicle needs the resource most. Experimental results show that Tiguan can effectively generate a feasible control solution with collision avoidance, and minimizing the energy consumption.

Although location awareness and turn-by-turn instructions are prevalent outdoors due to GPS, we are back into the darkness in uninstrumented indoor environments such as underground parking structures. We get confused, disoriented when driving in these mazes, and frequently forget where we parked, ending up circling back and forth upon return. In this paper, we propose VeTrack, asmartphone-only system that tracks the vehicle’s location in real time using the phone’s inertial sensors. It does not require any environment instrumentation or cloud backend. It uses a novel “shadow” trajectory tracing method to accurately estimate phone’s and vehicle’s orientations despite their arbitrary poses and frequent disturbances. We develop algorithms in a Sequential Monte Carlo framework to represent vehicle states probabilistically, and harness constraints by the garage map and detected landmarks to robustly infer the vehicle location. We also find landmark (e.g., speed bumps, turns) recognition methods reliable against noises, disturbances from bumpy rides, and even hand-held movements. We implement a highly efficient prototype and conduct extensive experiments in multiple parking structures of different sizes and structures, and collect data with multiple vehicles and drivers. We find that VeTrack can estimate the vehicle’s real time location with almost negligible latency, with error of$2\sim 4$parking spaces at the 80th percentile.

Since GPS signal is not applicable indoors, vehicle tracking has proven a hassle in underground parking structures. Recent solutions highly rely on floor map to constraint inertial sensors noises. In this paper, we propose VeMap, a road map construction system using only smartphones inside vehicles. It saves effort-intensive and time-consuming business negotiations with building operators, and expensive personnel cost to gather such data. It fuses multiple sensors to calibrate inertial noises, and uses Dynamic Time Warping to align multiple trajectories. We represent the floor plan with occupancy grid mapping, and explore a vision-mobile joint algorithm to extract its skeleton and form the road map. VeMap is tested in a 250mx90m parking structure, and it can be directly used for driving navigation to free parking spaces.

The dual-mode delay model, while being effective for characterizing on-chip timing variations, also yields timing analysis results that are overly pessimistic due to the Common Path Pessimism (CPP). In this paper, we develop a fast and accurate block-based algorithm for removing this pessimism in timing analysis, when the dual-mode delay model is used. We illustrate the effectiveness of our algorithm on a set of benchmarks from the TAU 2014 Contest [1].

Recently, FPGA-based CNN accelerators have demonstrated superior energy efficiency compared to high-performance devices like GPGPUs. However, due to the constrained on-chip resource and many other factors, single-board FPGA designs may have difficulties in achieving optimal energy efficiency. In this paper we present a deeply pipelined multi-FPGA architecture that expands the design space for optimal performance and energy efficiency. A dynamic programming algorithm is proposed to map the CNN computing layers efficiently to different FPGA boards. To demonstrate the potential of the architecture, we built a prototype system with seven FPGA boards connected with high-speed serial links. The experimental results on AlexNet and VGG-16 show that the prototype can achieve up to 21x and 2x energy efficiency compared to optimized multi-core CPU and GPU implementations, respectively.

Due to the continuous scaling of integration density and the increasing diversity of customized designs, there are increasing demands on the scalability and the customization of EDA tools and flows. Commercial EDA tools usually provide an interface of TCL scripting to extract and modify the design information for a flexible design flow. However, we observe that the current TCL scripting is not designed for the complete netlist extraction, resulting in a significant degradation in performance. For example, it takes over 20 minutes to extract the complete netlist of a 466K-cell design using TCL. This extraction may be repeated several times when interfacing between the existing EDA platforms and the actual distributed EDA algorithms. This drastic decrease in efficiency is a great barrier for customized EDA tool development. In this paper, we propose to build a distributed framework on top of TCL to accelerate the netlist extraction and use the distribution detailed placement as an example to demonstrate its capability. This framework is promising in scaling out physical design algorithms to run on a cluster.

Mainstream indoor localization technologies rely on RF signatures that require extensive human efforts to measure and periodically recalibrate signatures. The progress to ubiquitous localization remains slow. In this study, we explore Sextant, an alternative approach that leverages environmental reference objects such as store logos. A user uses a smartphone to obtain relative position measurements to such static reference objects for the system to triangulate the user location. Sextant leverages image matching algorithms to automatically identify the chosen reference objects by photo-taking, and we propose two methods to systematically address image matching mistakes that cause large localization errors. We formulate the benchmark image selection problem, prove its NP-completeness, and propose a heuristic algorithm to solve it. We also propose a couple of geographical constraints to further infer unknown reference objects. To enable fast deployment, we propose a lightweight site survey method for service providers to quickly estimate the coordinates of reference objects. Extensive experiments have shown that Sextant prototype achieves 2-5 m accuracy at 80-percentile, comparable to the industry state-of-the-art, while covering a 150 x 75 m mall and 300 x 200m train station requires a one time investment of only 2-3 man-hours from service providers.

The lack of floor plans is a critical reason behind the current sporadic availability of indoor localization service. Service providers have to go through effort-intensive and time-consuming business negotiations with building operators, or hire dedicated personnel to gather such data. In this paper, we propose Jigsaw, a floor plan reconstruction system that leverages crowdsensed data from mobile users. It extracts the position, size, and orientation information of individual landmark objects from images taken by users. It also obtains the spatial relation between adjacent landmark objects from inertial sensor data, then computes the coordinates and orientations of these objects on an initial floor plan. By combining user mobility traces and locations where images are taken, it produces complete floor plans with hallway connectivity, room sizes, and shapes. It also identifies different types of connection areas (e.g., escalators and stairs) between stories, and employs a refinement algorithm to correct detection errors. Our experiments on three stories of two large shopping malls show that the 90-percentile errors of positions and orientations of landmark objects are about 1~2m and 5~9°, while the hallway connectivity and connection areas between stories are 100 percent correct.

Circuit clustering is usually done through discrete optimizations to enable circuit size reduction or design-specific cluster formation. In this article, we are interested in the register-clustering technique for clock-power reduction by leveraging new opportunities introduced by multibit flip-flop (MBFF). Currently, INTEGRA is the only existing postplacement MBFF clustering optimizer with a subquadratic time complexity. However, it severely degrades the wirelength, especially for realistic designs, which may nullify the benefits of MBFF clustering. In contrast, we formulate an analytical clustering score with a nonlinear programming framework, in which the wirelength objective can be seamlessly integrated and the solver has empirical subquadratic time complexity. With the MBFF library, the application of our analytical clustering method achieves comparable clock power to the state-of-the-art techniques, but further reduces the wirelength by about 25%. Even without the MBFF library, we can still achieve 30% clock wirelength reduction. In addition, the proposed method can potentially be integrated into an in-placement MBFF clustering solver and be applied to other problems that require formulating clustering scores in their objective functions.

The "early/late split" in delay modeling is an effective approach to handle the variability in deep submicron integrated circuits. However, static timing analysis with early/late split is often too conservative due to the common path pessimism, where the common path pessimism removal (CPPR) technique is helpful to eliminate the unnecessary pessimism. In this paper, we propose a fast and simple CPPR algorithm with sub-quadratic time complexity.

X-ray computed tomography is an important technique for clinical diagnose and nondestructive testing. In many applications a number of image processing steps are needed before the image information becomes useful. Image segmentation is one of such processing steps and has important applications. The conventional flow is to first reconstruct the image and then obtain image segmentation afterwards. In contrast, an iterative method for simultaneous reconstruction and segmentation (SRS) with Mumford-Shah model has been proposed, which not only regularizes the ill-posedness of the tomographic reconstruction problem, but also produces the image segmentation at the same time. The Mumford-Shah model is both mathematically and computationally difficult. In this paper, we propose a data-decomposed algorithm of the SRS method, accelerate it using FPGA devices. The proposed algorithm has a structure that invokes a single kernel many times without involving other computational tasks. Though this structure seems best fit on GPU-like devices, experimental results show that a 73X, 11X, and 1.4X speedup can be achieved by the FPGA acceleration over the CPU implementation of the original SRS algorithm and ray-parallel SRS algorithm, and the GPU implementation of the ray-parallel SRS.

FPGA routing is a time-consuming step in the EDA design flow. In this paper we present a coarse-grained recursive partitioning approach to exploit parallelism. The basic idea is to partition the nets into three subsets, where the first subset and the other two subsets consist of potentially conflicting nets and potentially conflicting-free nets, respectively. The two potentially conflicting-free subsets are routed in parallel after the first subset is routed. And all subsets are recursively partitioned in the same way. Furthermore, we point out that the estimated runtime using recursive bisection is close to the optimal estimated runtime using the optimal recursive partitioning, which we can find in polynomial time. The parallel router is implemented using the Message Passing Interface (MPI). Experimental results show that our parallel router ParRoute+ achieves a 7.06× speedup compared to the VPR 7.0 router. This is a 3.36× improvement over a recent coarse-grained parallel router.

Circuit clustering is usually done through discrete optimizations, with the purpose of circuit size reduction or design-specific cluster formation. Specifically, we are interested in the multi-bit flip-flop (MBFF) design technique for clock power reduction, where all previous works rely on discrete clustering optimizations. For example, INTEGRA was the only existing post-placement MBFF clustering optimizer with a sub-quadratic time complexity. However, it degrades the wirelength severely, especially for realistic designs, which may cancel out the benefits of MBFF clustering. In this paper we enable the formulation of an analytical clustering score in nonlinear programming, where the wirelength objective can be seamlessly integrated. It has sub-quadratic time complexity, reduces the clock power by about 20% as the state-of-the-art techniques, and further reduces the wirelength by about 25%. In addition, the proposed method is promising to be integrated in an in-placement MBFF clustering solver and be applied in other problems which require formulating the clustering score in the objective function.

Although location awareness and turn-by-turn instructions are prevalent outdoors due to GPS, we are back into the darkness in uninstrumented indoor environments such as underground parking structures. We get confused, disoriented when driving in these mazes, and frequently forget where we parked, ending up circling back and forth upon return.In this paper, we propose VeTrack, a smartphone-only system that tracks the vehicle's location in real time using the phone's inertial sensors. It does not require any environment instrumentation or cloud backend. It uses a novel "shadow" tracing method to accurately estimate the vehicle's trajectories despite arbitrary phone/vehicle poses and frequent disturbances. We develop algorithms in a Sequential Monte Carlo framework to represent vehicle states probabilistically, and harness constraints by the garage map and detected landmarks to robustly infer the vehicle location. We also find landmark (e.g., speed bumps, turns) recognition methods reliable against noises, disturbances from bumpy rides and even hand-held movements. We implement a highly efficient prototype and conduct extensive experiments in multiple parking structures of different sizes and structures, with multiple vehicles and drivers. We find that VeTrack can estimate the vehicle's real time location with almost negligible latency, with error of 2-4 parking spaces at 80-percentile.

The conventional approach of computed tomography (CT) is to solve each image processing task individually in sequence. An obvious drawback is that the measured data is only used once at the first step, and the possible errors, from noises in the measured data, inappropriate modeling, or inappropriate parameters, are not easy to be corrected and will be propagated into the later steps. As a consequence, approaches that combine the reconstruction and the specific processing task have become popular. This work adopts an iterative algorithm with simultaneous reconstruction and segmentation using the Mumford-Shah model, which can be applied not only to regularize the ill-posedness of the tomographic reconstruction problem, but also to compute segmentation directly from the measured data. The Mumford-Shah model is both mathematically and computationally difficult. In this paper, we accelerated this computation and data intensive application by FPGA devices and achieved 9.24X speedup over the conventional CPU implementation.

In this paper we propose a quantitative approach to analyze the impact of heterogeneous blocks (H-blocks) on the FPGA placement quality. The basic idea is to construct synthetic heterogeneous placement benchmarks with known optimal wire-length to facilitate the quantitative analysis. To the best of our knowledge, this is the first work that enables the construction of wirelength-optimal heterogeneous placement examples. Besides analyzing the quality of existing placers, we further decompose the impacts of H-blocks from the architectural aspect and netlist aspect. Our analysis shows that a heterogeneous design hides the wirelength degradation by a more compact netlist than its homogeneous version; however, the heterogeneity results in a optimality gap of 52% in wirelength, where 25% is from architectural heterogeneity and 27% is from netlist heterogeneity. Therefore, new heterogeneous placement algorithms are needed to bridge the optimality gap and improve design quality.

Modern application specific system-on-chip platforms allow customization of caches. Such flexibility enables the designers to identify the suitable cache configurations through design space exploration of caches. Trace-driven simulation is widely used to obtain the cache hits and misses for design space exploration. However, simulation is normally slow. Meanwhile, as the embedded system moves toward cache hierarchies with multi-level caches, such expanded design space leads to extremely long simulation time. In this paper, we propose a rapid design space exploration technique for two-level unified caches. Given the application trace, our technique determines the cache hits and misses for multiple cache configurations in a single pass. Our exploration technique adopts a novel LRU linked list data structure, lookup tables, and search algorithms to effectively improve the exploration time. Experimental results indicate that our analysis is 7-239X times faster compared to the fastest known design space exploration technique, in estimating cache hits and misses for popular embedded benchmarks.

We present VeLoc, a smartphone-based vehicle localization approach that tracks the vehicle's parking location without GPS or WiFi signals. It uses only the embedded accelerometer and gyroscope sensors. VeLoc harnesses constraints imposed by the map and landmarks (e.g., speed bumps) recognized from inertial data, employs a Bayesian filtering framework to estimate the location of the vehicle. We have conducted experiments in three parking structures of different sizes and configurations, using three vehicles and three kinds of driving styles. We find that VeLoc can always localize the vehicle within 10m, which is sufficient for the driver to trigger a honk using the car key.

One of the necessary requirements for the placement process is that it should be capable of generating routable solutions. This paper describes a simple but effective method leading to the reduction of the routing congestion and the final routed wirelength for large-scale mixed-size designs. In order to reduce routing congestion and improve routability, we propose blocking narrow regions on the chip. We also propose dummy-cell insertion inside regions characterized by reduced fixed-macro density. Our placer consists of three major components: (i) narrow channel reduction by performing neighbor-based fixed-macro inflation; (ii) dummy-cell insertion inside large regions with reduced fixed-macro density; and (iii) pre-placement inflation by detecting tangled logic structures in the netlist and minimizing the maximum pin density. We evaluated the quality of our placer using the newly released DAC 2012 routability-driven placement contest designs and we compared our results to the top four teams that participated in the placement contest. The experimental results reveal that our placer improves the routability of the DAC 2012 placement contest designs and effectively reduces the routing congestion.

Clock power contributes a significant portion of chip power in modern IC design. Applying multi-bit flip-flops can effectively reduce clock power. State-of-the-art work performs multi-bit flip-flop clustering at the post-placement stage. However, the solution quality may be limited because the combinational gates are immovable during the clustering process. To overcome the deficiency, in this paper, we propose multi-bit flip-flop bonding at placement. Inspired by ionic bonding in Chemistry, we direct flip-flops to merging friendly locations thus facilitating flip-flop merging. Experimental results show that our algorithm, called FF-Bond, can save 27% clock power on average. Compared with state-of-the-art post-placement multi-bit flip-flop clustering, FF-Bond can further reduce 14% clock power.

In this paper, we present a high-quality analytical 3-D placement framework. We propose using a Huber-based local smoothing technique to work with a Helmholtz-based global smoothing technique to handle the nonoverlapping constraints. The experimental results show that this analytical approach is effective for achieving tradeoffs between the wirelength and the through-silicon-via (TSV) number. Compared to the state-of-the-art 3-D placer ntuplace3d, our placer achieves more than 20% wirelength reduction, on average, with a similar number of TSVs. Furthermore, we extend this analytical 3-D placement framework with thermal awareness. While 2-D thermal-aware placement simply follows uniform power distribution to minimize temperature, we show that the same criterion does not work for 3-D ICs. Instead, we are able to prove that when the TSV area in each bin is proportional to the lumped power consumption of that bin and the bins in all tiers directly above it, the peak temperature is minimized. Based on this criterion, we implement thermal awareness in our analytical 3-D placement framework. Compared with a TSV oblivious method, which only results in an 8% peak temperature reduction, our method reduces the peak temperature by 34%, on average, with slightly less wirelength overhead. These results suggest that considering the thermal effects of TSVs is necessary and effective during the placement stage.

Achieving optimal throughput by extracting parallelism in behavioral synthesis often exaggerates memory bottleneck issues. Data partitioning is an important technique for increasing memory bandwidth by scheduling multiple simultaneous memory accesses to different memory banks. In this paper we present a vertical memory partitioning and scheduling algorithm that can generate a valid partition scheme for arbitrary affine memory inputs. It does this by arranging non-conflicting memory accesses across the border of loop iterations. A mixed memory partitioning and scheduling algorithm is also proposed to combine the advantages of the vertical and other state-of-art algorithms. A set of theorems is provided as criteria for selecting a valid partitioning scheme. This is followed by an optimal and scalable memory scheduling algorithm. By utilizing the property of constant strides between memory addresses in successive loop iterations, an address translation optimization technique for an arbitrary partition factor is proposed to improve performance, area and energy efficiency. Experimental results show that on a set of real-world medical image processing kernels, the proposed mixed algorithm with address translation optimization can gain speed-up, area reduction and power savings of 15.8%, 36% and 32.4% respectively, compared to the state-of-art memory partitioning algorithm.

There are two prominent problems with technology scaling: increasing design complexity and more challenges with interconnect design, including routability. High-level synthesis has been proposed to solve the complexity problem by raising the abstraction level. In this paper, we share our vision that high-level synthesis can potentially help the routability problem as well. We show that many interconnect problems that occur in layout can be avoided or mitigated by adopting a layout-friendly RTL architecture generated from high-level synthesis. We also evaluate some structural metrics that can be used to estimate the routability impact of design decisions in high-level synthesis. Experimental results have demonstrated correlations between the metrics and the routability of the resulting design.

Existing thermal-aware 3D placement methods assume that the temperature of 3D ICs can be optimized by properly distributing the power dissipations, and ignoring the heat conductivity of though-silicon-vias (TSVs). However, our study indicates that this is not exactly correct. While considering the thermal effect of TSVs during placement appears to be quite complicated, we are able to prove that when the TSV area in each bin is proportional to the lumped power consumption in that bin, together with the bins in all the tiers directly above it, the peak temperature is minimized. Based on this criterion, we implement a thermal-aware 3D placement tool. Compared to the methods that prefer a uniform power distribution that only results in an 8% peak temperature reduction, our method reduces the peak temperature by 34% on average with even slightly less wirelength overhead. These results suggest that considering thermal effects of TSVs is necessary and effective during the placement stage. To the best of the authors' knowledge, this is the first thermal-aware 3D placement tool that directly takes into consideration the thermal and area impact of TSVs.

The design of high-performance servers has always been a challenging art. Now, server designers are being asked to explore a much larger design space as they consider multicore heterogeneous architecture and the limits of advancing silicon technology. Bringing automation to the early stages of design can enable more rapid and accurate trade-off analysis. In this paper, we introduce an Early Chip Planner which allows designers to rapidly analyze microarchitecture, physical and package design trade-offs for 2D and 3D VLSI chips and generates an attributed netlist to be carried on to the implementation stage. We also describe its use in planning a 3D special-purpose server processor.

A unified optimization framework is presented for simultaneous gate sizing and placement. These processes are unified using Lagrangian multipliers, which synchronize the efforts of the gate sizing and placement subproblems. As far as we know, this is the first work that formulates and solves the simultaneous gate sizing and placement under area density constraints, which are handled by the quadratic penalty method. We show that this rigorous framework results in an algorithm that is faster than separate iterations of gate sizing and placement steps, and leads to more robust results for a set of benchmarks.

Existing 3D placement techniques are mainly used for standard-cell circuits, while mixed-size placement is needed to support high-level functional units and intellectual property (IP) blocks. In this paper we present an analytical 3D placement method that is capable of placing mixed-size circuits. A multiple-stepsize scheme for the analytical solver is proposed to handle standard cells and macros differently for stability and efficiency. To relieve the difficulty of legalization, 3D floorplan-based initial solutions are used to guide the analytical solver. As far as we know, this is the first work that reports 3D placement results for mixed-size circuits. Our experiments show that the multiple-stepsize scheme is better than single-stepsize schemes in both quality and runtime. The experimental results on the ICCAD'04 mixed-size benchmarks show that the 4-tier 3D mixed-size placement can reduce the wirelength by 27% on average compared to 2D placement. The results also show that the 3D mixed-size placement achieves 5.3% shorter wirelength on average than the pseudo 3D placement with similar amount of through-silicon vias (TS vias).

In this paper we propose a multilevel non-linear programming based 3D placement approach that minimizes a weighted sum of total wirelength and TS via number subject to area density constraints. This approach relaxes the discrete layer assignments so that they are continuous in the z-direction and the problem can be solved by an analytical global placer. A key idea is to do the overlap removal and device layer assignment simultaneously by adding a density penalty function for both area & TS via density constraints. Experimental results show that this analytical placer in a multilevel framework is effective to achieve trade-offs between wirelength and TS via number. Compared to the recently published transformation-based 3D placement method, we are able to achieve on average 12% shorter wirelength and 29% fewer TS via compared to their cases with best wirelength; we are also able to achieve on average 20% shorter wirelength and 50% fewer TS via number compared to their cases with best TS via numbers.

Recent analytical global placers use density constraints to approximate non-overlap constraints and show very successful results. In this paper we unify a wide range of density smoothing techniques that we call global smoothing, and present a highly efficient method to compute the gradient of such smoothed densities used in several well-known analytical placers [3, 5, 7]. Our method reduces the complexity of the gradient computation by a factor of n compared to a naïve method, where n is the number of modules. Furthermore, with this efficient gradient computation we can come up with an efficient nonlinear programming-based placement framework, which supercedes the existing force-directed placement methods [4, 7]. An application of our technique, as the engine of a multilevel placer, achieved 13% and 15% wirelength improvement compared with SCAMPI [13] and mPL6 [3] on IBM-HB+ benchmark [13]

Recent analytical global placers use density constraints to approximate nonoverlap constraints, and these show very successful results. This paper unifies a wide range of density smoothing techniques called global smoothing and presents a highly efficient method for computing the gradient of such smoothed densities used in several well-known analytical placers. This method reduces the complexity of the gradient computation by a factor ofncompared with a naive method, wherenis the number of modules. Furthermore, with this efficient gradient computation, it is able to support an efficient nonlinear programming-based placement framework, which supersedes the existing force-directed placement methods. Experiments show that replacing the approximated gradient computation in mPL6 with the exact gradient computation improves wire length by 15% on the IBM-HB+ benchmark and by 3% on average on the modified International Symposium on Physical Design 2005 (ISPD'05) and ISPD'06 placement contest benchmarks with movable macros. The results also show that the augmented Lagrangian method outperforms the quadratic penalty method with the exact gradient computation.

3D IC technologies can help to improve circuit performance and lower power consumption by reducing wirelength. Also, 3D IC technology can be used to realize heterogeneous system-on-chip design, by integrating different modules together with less interference with each other. In this paper, we propose a novel thermal-aware 3D cell placement approach, named T3Place, based on transforming a 2D placement with good wirelength to a 3D placement, with the objectives of half-perimeter wirelength, through-the-silicon (TS) via number and temperature. T3Place is composed of two steps, transformation from a 2D placement to a 3D placement and the refinement of the resulting 3D placement. We proposed and compared several different transformation techniques, including local stacking transformation (LST), folding-2, folding-4 and window-based stacking/folding transformation, and concluded that (i) LST can generate 3D placements with the least wirelength, (ii) the folding-based transformations result in 3D placements with the fewest TS vias, and (iii) the window-based stacking/folding transformations provide good TS via number and wirelength tradeoffs. For example, with four device layers, LST can reduce the wirelength by over 2times compared to the initial 2D placement, while window-based stacking/folding can provide over 10times variation in terms of the TS via number, thus adaptive to different manufacturing ability for TS via density. Moreover, we proposed a novel relaxed conflict-net (RCN) graph-based layer assignment method to further refine the 3D placements. Compared to LST results, thermal-aware RCN graph-based layer assignment algorithm (r = 10%) can further reduce the maximum on-chip temperature by 37%, with only 6% TS via number increase and 8% wirelength increase.