Multi-bit flip-flop (MBFF) banking and debanking is a widely adopted technique for optimizing power and total negative slack (TNS) during the post-placement stage of digital design. While banking flipflops can reduce both power and area, excessive banking may lead to increased TNS due to significant register displacement, as well as bin density violations (BDVs) caused by over-placing MBFFs in legalized regions. To address these challenges, the EDA community recently organized a CAD Contest seeking innovative solutions from both academia and industry. In response, we present TIMBER, a fast and effective optimization algorithm that balances competing objectives in MBFF placement. Unlike existing methods, TIMBER employs a bin-density-aware placement strategy that simultaneously minimizes BDVs and TNS, while also achieving gains in power and area efficiency. To further enhance the runtime performance, TIMBER incorporates a parallelization strategy. Experimental results on the official 2024 CAD Contest benchmarks demonstrate that TIMBER outperforms the first-place winner, delivering on average $13.08 \times$ better solution quality, zero BDVs, $5.06 \times$ faster single-threaded runtime, $3.56 \times$ lower memory usage and up to $72.49 \times$ speedup in multi-threaded execution.

Critical path generation (CPG) plays a key role in many circuit timing analysis (CTA) applications. As the design complexity continues to increase, CPG runtime has become a major bottleneck in many timing-driven applications. To mitigate this runtime challenge, several CPU-based algorithms have been introduced by both the CTA and parallel computing communities, but they remain slow for large CPG problems. While GPU-accelerated solutions exist, they are often inexact and incur significant overhead from iterative CPU–GPU data transfers, limiting their practical use in CTA applications. To overcome this challenge, we propose G-PathGen, an exact GPU-parallel CPG algorithm targeting CTA applications. G-PathGen introduces efficient kernel algorithms for generating critical paths in parallel and dynamically adjusts the generated path count to maximize GPU utilization while minimizing redundant work. Compared to a state-of-the-art GPU solution, G-PathGen is 1.6 × –243.8 × faster when generating one million critical paths on industrial circuit graphs.

When multiple videos of a scene are taken from differing viewpoints without precise synchronization, it can be difficult to temporally align them after the fact. Often the metadata or audio needed to do so is missing or inaccurate. But human motion in such videos can provide a strong signal for identifying matching time points across videos, through analysis of pose and movement. In this work, we leverage view-invariant human pose features to synchronize videos. Unlike previous human pose-based alignment techniques, our method can align videos containing multiple people without performing tracking or re-identification across views. We achieve this by aggregating pose information from multiple people into a single frame descriptor. This also enables fast ${\mathcal{O}}\left({n\log n}\right)$ search for the optimal alignment. This simple but effective strategy leads to major and consistent improvements over existing human-based and visual feature temporal alignment techniques.

Graph partitioning is important for the design of many CAD algorithms. However, as the graph size continues to grow, graph partitioning becomes increasingly time-consuming. Recent research has introduced parallel graph partitioners using either multi-core CPUs or GPUs. However, the speedup of existing CPU graph partitioners is typically limited to a few cores, while the performance of GPU-based solutions is algorithmically limited by available GPU memory. To overcome these challenges, we propose G-kway, an efficient multilevel GPU-accelerated k -way graph partitioner. G-kway introduces an effective union find-based coarsening and a novel independent set-based refinement algorithm to significantly accelerate both the coarsening and uncoarsening stages. Furthermore, when kernel launch overhead becomes substantial in the refinement algorithm, G-kway employs CUDA Graph-based uncoarsening to reduce the overhead and improve performance. Experimental results have shown that G-kway outperforms both the state-of-the-art CPU-based and GPU-based parallel partitioners with an average speedup of 8.6× and 3.8×, respectively, while achieving comparable partitioning quality. Additionally, G-kway with CUDA Graph-based uncoarsening can further accelerate graph partitioning, achieving up to 1.93× speedup over the default G-kway.

Critical Path Generation (CPG) is fundamental for many static timing analysis (STA) applications. As the circuit complexity continues to increase, CPG runtime has quickly become the bottleneck due to its time-consuming and iterative nature. Despite many CPG algorithms introduced by existing timers, nearly all of them are limited to a single CPU thread, leading to long runtime for large CPG queries. To mitigate this runtime challenge, we need a parallel CPG algorithm. However, designing a parallel CPG algorithm is very challenging because we need to strategically partition the path search space into multiple groups that can run in parallel while accommodating different slack priorities. To overcome this challenge, we propose PathGen, an efficient CPU-parallel CPG algorithm. Path-Gen introduces a multi-level queue scheduling framework that can efficiently parallelize the search process of critical paths. Compared to a state-of-the-art single-threaded timer, PathGen is up to 7.4× faster with 16 threads and achieves nearly 100% accuracy when generating one million critical paths on large designs.

Hypergraph partitioning plays a critical role in computer-aided design (CAD) because it allows us to break down a large circuit into several manageable pieces that facilitate efficient CAD algorithm designs. However, as circuit designs continue to grow in size, hypergraph partitioning becomes increasingly time-consuming. Recent research has introduced parallel hypergraph partitioners using multi-core CPUs to reduce the long runtime. However, the speedup of existing CPU parallel hypergraph partitioners is typically limited to a few cores. To overcome these challenges, we propose HyperG, a GPU-accelerated multilevel k-way hypergraph partitioning algorithm. HyperG introduces an innovative balanced group coarsening and a sequence-based refinement algorithm to accelerate both the coarsening and uncoarsening stages. Experimental results show that HyperG outperforms both the state-of-the-art sequential and CPU-based parallel partitioners with an average speedup of 133× and 4.1× while achieving comparable partitioning quality.

Recent static timing analysis (STA) tools have utilized task dependency graph (TDG) parallelism to enhance the STA runtime performance. Although TDG parallelism shows promising speedup, the overhead of scheduling a TDG can become dominant as the TDG becomes larger. To minimize the scheduling overhead, several TDG partitioning algorithms have been proposed to reduce the TDG size without affecting its task parallelism. Despite improved performance, existing TDG partitioners all fall short of incremental partitioning, limiting their practical use in STA tools that support timing-driven operations. To overcome this limitation, we propose iTAP, an incremental TDG partitioner to fully leverage the power of TDG partitioning in task-parallel STA applications. Compared to a state-of-the-art full TDG partitioner, iTAP enhances the overall STA performance by up to 2.97×.

Quantum circuit simulation (QCS) plays an important role in the designs and analysis of a quantum algorithm, as it assists researchers in understanding how quantum operations work without accessing expensive quantum computers. Despite many QCS methods, they are largely limited to simulating one input at a time. However, many simulation-driven quantum computing applications, such as testing and verification, require simulating multiple inputs to reason a quantum algorithm under different scenarios. We refer to this type of QCS as batch quantum circuit simulation (BQCS). In this paper, we present BQSim, a GPU-accelerated batch quantum circuit simulator. BQSim is inspired by the state-of-the-art decision diagram (DD) that can compactly represent quantum gate matrices, but overcomes its limitation of CPU-centric simulation. Specifically, BQSim uses DD to optimize a quantum circuit for reduced BQCS computation and converts DD to a GPU-efficient data structure. Additionally, BQSim employs a task graph-based execution strategy to minimize repetitive kernel call overhead and efficiently overlap kernel execution with data movement. Compared with three state-of-the-art quantum circuit simulators, cuQuantum, Qiskit Aer, and FlatDD, BQSim is 3.25×, 159.06×, and 311.42× faster on average.

This paper proposes a novel lightweight model training strategy called Knowledge Distillation Boosted Network Augmentation (KDBNA) for contact-free diagnosis and severity assessment of obstructive sleep apnea (OSA) through audio-based analysis of snoring events. Traditional OSA diagnosis relies on polysomnography (PSG), which is invasive, costly, and inconvenient for patients. To overcome these limitations, we developed a compact deep neural network by integrating knowledge distillation (KD) and network augmentation (NetAug), significantly reducing the parameter count of a ResNet-18 model to only 0.28M parameters—about 1/40 of its original size—without compromising performance. Experimental results show that our proposed method achieves higher sensitivity and F1-score compared to other lightweight approaches, while substantially reducing inference time on CPU-based platforms by approximately 87%. The proposed approach demonstrates strong potential for convenient, accurate, and cost-effective OSA screening, particularly suitable for implementation in edge computing devices and at-home healthcare scenarios.

Statistical Static Timing Analysis (SSTA) is a crucial technique in digital circuit design because it addresses on-chip variations (OCV) by propagating timing distributions instead of fixed delays. However, the computational complexity of SSTA demands significant memory and long runtimes. While GPUs offer opportunities to accelerate SSTA, their limited memory capacity makes it challenging to handle large-scale SSTA workloads. To address this challenge, we propose a statistical timing graph (STG) scheduling algorithm combined with a GPU memory management strategy. We have shown up to $4.9 \times$ speedup on a GPU with 16 GB memory compared to a 20-thread CPU baseline when solving an 18.2 GB STG.

Recent advances in GPU-accelerated graph partitioning have achieved significant performance gains but remain limited to full graph partitioning, lacking support for incremental updates. This limitation is critical in CAD applications, where circuit graphs undergo iterative, incremental modifications during optimization. We present iG-kway, the first GPU-based incremental k-way graph partitioner. iG-kway features an incrementality-aware data structure and a refinement kernel that efficiently updates only affected vertices with minimal quality loss. Experiments show that iG-kway delivers up to $84 \times$ speedup over the state-of-the-art G-kway with comparable partitioning quality.

Text-to-image diffusion models excel at generating diverse portraits, but lack intuitive shadow control. Existing editing approaches, as post-processing, struggle to offer effective manipulation across diverse styles. Additionally, these methods either rely on expensive real-world light-stage data collection or require extensive computational resources for training. To address these limitations, we introduce Shadow Director, a method that extracts and manipulates hidden shadow attributes within well-trained diffusion models. Our approach uses a small estimation network that requires only a few thousand synthetic images and hours of training-no costly real-world light-stage data needed. Shadow Director enables parametric and intuitive control over shadow shape, placement, and intensity during portrait generation while preserving artistic integrity and identity across diverse styles. Despite training only on synthetic data built on real-world identities, it generalizes effectively to generated portraits with diverse styles, making it a more accessible and resource-friendly solution.

Computer-aided design (CAD) tools typically incorporate thousands or millions of functional tasks and dependencies to implement various synthesis and analysis algorithms. Efficiently scheduling these tasks in a computing environment that comprises manycore CPUs and GPUs is critically important because it governs the macro-scale performance. However, existing scheduling methods are typically hardcoded within an application that are not adaptive to the change of computing environment. To overcome this challenge, this paper will introduce a novel reinforcement learning-based scheduling algorithm that can learn to adapt the performance optimization to a given runtime (task execution environment) situation. We will present a case study on VLSI timing analysis to demonstrate the effectiveness of our learning-based scheduling algorithm. For instance, our algorithm can achieve the same performance of the baseline while using only 20% of CPU resources.

Critical Path Generation (CPG) is crucial for static timing analysis (STA) applications to validate timing constraints. Recent years have witnessed CPG algorithms that can rank k critical paths efficiently and accurately. However, they all suffer from the lack of incrementality, which is the ability to quickly update critical paths after the circuit is incrementally modified. To solve this problem, we introduce Ink, an efficient incremental CPG algorithm. Inspired by the large path trace similarity between adjacent CPG queries, Ink identifies a set of paths to reuse for the next query and effectively prunes the path search space. We have demonstrated the promising performance of Ink on large circuit benchmarks. Ink is up to 22.4X faster and consumes up to 31% less memory than a state-of-the-art timer when generating one million paths on a large design.

Graph partitioning is important for the design of many CAD algorithms. However, as the graph size continues to grow, graph partitioning becomes increasingly time-consuming. To overcome these challenges, we propose G-kway, an efficient multilevel GPU-accelerated k-way graph partitioner. G-kway introduces an effective union find-based coarsening and a novel independent set-based refinement algorithm to significantly accelerate both the coarsening and uncoarsening stages. Experimental results have shown that G-kway outperforms both the state-of-the-art CPU-based and GPU-based parallel partitioners with an average speedup of 8.6× and 3.8×, respectively, while achieving comparable partitioning quality.

Composite Current Source (CCS) timing model plays an important role in modern static timing analysis (STA) because it precisely captures the timing behavior of a design at advanced nodes. However, CCS is extremely time-consuming due to its accurate but complicated timing models. To overcome this challenge, we introduce GCS-Timer, a GPU-accelerated CCS-based timing analysis algorithm. Unlike existing methods that perform model order reduction to trade accuracy for speed, GCS-Timer achieves high accuracy through a fast simulation-based analysis using GPU computing. Experimental results show that GCS-Timer can complete CCS analysis with better accuracy and achieve 3.2X faster runtime compared with a 16-threaded industrial standard timer. The source code is available at https://github.com/cuhk-eda/GCS-Timer.

Recent static timing analysis (STA) engines have leveraged task dependency graph (TDG) parallelism to accelerate various STA algorithms, including graph-based analysis and path-based analysis. Despite the promising speedup via task parallelism, the scheduling cost of a TDG has become dominant when handling large TDGs. To overcome this challenge, we propose G-PASTA, a simple and fast TDG partitioning algorithm to reduce the scheduling cost of large task-parallel STA algorithms. By harnessing the power of GPU computing, G-PASTA incurs minimal cost of partitioning while bringing significant runtime improvement to task-parallel STA algorithms. Compared to a state-of-the-art CPU-based TDG partitioner, G-PASTA is up to 41.8× faster in partitioning runtime and can improve the overall STA performance by 43% on large designs.

Static timing analysis (STA) in advanced technology nodes encounter many new challenges in analysis accuracy and speed efficiency. To accurately model complex interconnect networks, existing timers have leveraged reduced-order models with effective capacitance to design advanced delay calculation algorithms. However, the iterative nature of these algorithms makes them extremely time-consuming to use in a timer, significantly limiting their capability in many timing-driven applications. To overcome this challenge, we propose a novel GPU-accelerated delay calculator that targets Arnoldi-based model order reduction with an effective capacitance algorithm. We design efficient numerical kernels for batched nodal analysis model construction, LU decom-position, Krylov subspace calculation, eigenvalue decomposition, and Newton-Raphson iteration. Compared with two industrial standard timers, PrimeTime and OpenSTA, we achieve a strong correlation with up to 7.27x and 14.03x speed-up, respectively.

This paper describes the background, design and application of a new SEI message – the Multiplane Image Information SEI message, which has recently been adopted into the Technology under Consideration (TuC) document of the JVET committee for potential inclusion in the VSEI standard (ITU-T H.274 and ISO/IEC 23002-7). The paper also provides preliminary compression experiment results and analysis on the implications of the coding efficiency and functionality of the different packing options supported in the SEI message.

The pipeline is a fundamental pattern to parallelize a series of stage tasks over a sequence of data in loops. Mainstream pipeline programming frameworks count on data abstractions to perform pipeline scheduling. Although this design is convenient for data-centric parallel applications, it is not efficient for algorithms that only exploit task parallelism in the pipeline. To address the limitation, we introduce a new task-parallel pipeline programming framework called Pipeflow. Pipeflow separates data abstractions and task scheduling, enabling a more efficient implementation of task-parallel pipeline algorithms than existing frameworks. We have evaluated Pipeflow on both micro-benchmarks and real-world applications. For example, in a timing analysis workload that explores pipeline parallelism to speed up the runtime performance, the Pipeflow’s implementation outperforms the oneTBB’s implementation up to 110.33% faster.

Static timing analysis (STA) for large-scale modern circuits requires extensive handling of false paths, multi-cycle paths, and other types of path exceptions. Despite the linear nature of timing propagation, we show that exception-aware STA is NP-hard and thus requires a long runtime to solve using conventional CPU-based methods. To overcome this runtime challenge, we propose a general CPU-GPU heterogeneous algorithm, HeteroExcept, that can handle common types of path exceptions and efficiently generate an accurate path report. Our algorithm targets runtime efficiency at the scale of thousands of exception rules and millions of circuit elements. To further improve the performance, we optimize our GPU implementation by introducing a cost-effective data exchange strategy between CPU and GPU. Experimental results demonstrate up to 6.84× and 12.93× speed-up compared to industrial timers, PrimeTime and OpenSTA.

Graph partitioning is essential for understanding the structure of a dataset, such as social networks and web pages. Among various graph partitioners, stochastic block partitioning (SBP) has shown promise in handling complex graphs with varying community sizes or strong intra-community connections. However, the sequential nature of the Monte Carlo Markov Chain iterations and the stochastic proposal generation process limit the efficiency and scalability of SBP. To overcome this limitation, this paper introduces GSAP, a GPU-accelerated stochastic graph partitioner, to enhance the runtime performance of SBP. We propose a parallel algorithm to speed up the generation process of stochastic proposals on GPU. Additionally, we accelerate the calculation of the minimal description length by dividing the formulation into several independent computations. To achieve better performance, we introduce an efficient blockmodel update algorithm to dynamically manage the blockmodel matrix on GPU. Our experimental results on the 2022 HPEC GraphChallenge dataset demonstrate that GSAP can achieve up to 12.3 × and 60.9 × runtime speedup on a single A4000 GPU compared to two CPU-parallel state-of-the-art SBP algorithms.

Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a high-performance QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages an efficient caching technique to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 34.81× speed-up and 1.93× memory reduction.

Static timing analysis (STA) is an integral part in the overall design flow because it verifies the expected timing behaviors of a circuit. However, as the circuit complexity continues to enlarge, there is an increasing need for enhancing the performance of existing STA algorithms using emerging heterogeneous parallelism that comprises manycore central processing units (CPUs) and graphics processing units (GPUs). In this paper, we introduce several state-of-the-art STA techniques, including task-based parallelism, task graph partition, and GPU kernel algorithms, all of which have brought significant performance benefits to STA applications. Motivated by these successful results, we will introduce a task-parallel programming system to generalize our solutions to benefit broader scientific computing applications.

Hardware fuzzing has emerged as a promising automatic verification technique to efficiently discover and verify hardware vulnerabilities. However, hardware fuzzing can be extremely time-consuming due to compute-intensive iterative simulations. While recent research has explored several approaches to accelerate hardware fuzzing, nearly all of them are limited to single-input fuzzing using one thread of a CPU-based simulator. As a result, we propose Gen-Fuzz, a GPU-accelerated hardware fuzzer using a genetic algorithm with multiple inputs. Measuring experimental results on a real industrial design, we show that GenFuzz running on a single A6000 GPU and eight CPU cores achieves 80× runtime speed-up when compared to state-of-the-art hardware fuzzers.

Path-based Analysis (PBA) is a key process in Static Timing Analysis (STA) to reduce excessive slack pessimism. How-ever, PBA can easily become the major performance bottleneck due to its long execution time. To overcome this bottleneck, recent STA researches have proposed to accelerate PBA algorithms with manycore CPU and GPU parallelisms. However, GPU memory is rather limited when we compute PBA on large industrial designs with millions of gates. In this work, we introduce a new endpoint-oriented partitioning framework that can separate STA graphs and dispatch the PBA workload onto multiple GPUs. Our framework can quickly identify logic overlaps among endpoints and group endpoints based on the size of shared logic. We then recover graph partitions from the grouped endpoints and offload independent PBA workloads to multiple GPUs. Experiments show that our framework can largely accelerate the PBA process on designs with over 10M gates.

Many EDA applications are extremely sparse, irregular, and control-flow intensive. Parallelizing this type of application can benefit from the ability to express dynamic task parallelism across arbitrary decision-making points at runtime. Unlike the traditional construct-and-run models, dynamic task parallelism offers programmers great flexibility to parallelize EDA algorithms that incorporate complex execution logic under dynamic control flow, such as branch-and-bound techniques, on-the-fly pruning, and recursive decomposition strategies. In this paper, we introduce a new programming model that supports the dynamic building of a computational task graph. We will cover scheduling details and best practices for exploring task parallelism under dynamic control flow. We will present a real use case of our model that has successfully parallelized a static timing analysis workload.

The “CAD Contest at ICCAD” is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2023 CAD Contest has 210 teams from all over the world, which generates the highest participation record. Moreover, the problems of this year cover state-of-the-art EDA research trends such as circuit verification, hardware security, 3D-IC, and Machine Learning (ML) for EDA from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

Film grain has been shown as an effective way to improve the look of video in terms of aesthetic feeling and sharpness. For backward compatibility, a strategy is to inject the film grain before video compression at encoder to ensure that any decoder can acquire the film grain injected images after video decompression. Moreover, for designed decoder, the film grain can be removed, and further video processing can be applied, such as adding other type of film grain or adaptive film grain setting according to the viewing environment. Therefore, in this work, we propose a metadata-aided film grain removal system such that the film grain can be removed efficiently using metadata in video bitstream. We propose three filtering methods (Gaussian, optimal FIR, and guided filter) in the proposed system. Experimental results show that the proposed system can remove film grain effectively and yield high PSNR.

Sparse deep neural network (DNN) has become an important technique for reducing the inference cost of large DNNs. However, computing large sparse DNNs is very challenging because inference iterations can incur highly irregular patterns and unbalanced loads. To address this challenge, the recent HPEC Graph Challenge seeks novel high-performance inference methods for large sparse DNNs. Despite the rapid progress over the past four years, solutions have largely focused on static model compression or sparse multiplication kernels, while ignoring dynamic data compression at inference time which can achieve significant yet untapped performance benefits. Consequently, we propose SNICIT, a new GPU algorithm to accelerate large sparse DNN inference via compression at inference time. SNICIT leverages data clustering to transform intermediate results into a sparser representation that largely reduces computation over inference iterations. Evaluated on both HPEC Graph Challenge benchmarks and conventional DNNs (MNIST, CIFAR-10), SNICIT achieves 6 ∼ 444 × and 1.36 ∼ 1.95 × speed-ups over the previous champions, respectively.

Incremental quantum circuit simulation has emerged as an important tool for simulation-driven quantum applications, such as circuit synthesis, verification, and analysis. When a small portion of the circuit is modified, the simulator must incrementally update state amplitudes for reasonable turnaround time and productivity. However, this type of incrementality has been largely ignored by existing research. To fill this gap, we introduce a new incremental quantum circuit simulator called qTask. qTask leverages a task-parallel decomposition strategy to explore both inter- and intra-gate operation parallelisms from partitioned data blocks. Our partitioning strategy effectively narrows down incremental update to a small set of partitions affected by circuit modifiers. We have demonstrated the promising performance of qTask on QASMBench benchmarks. Compared to two state-of-the-art simulators, Qulacs and Qiskit, qTask is respectively 1.46 × and 1.71× faster for full simulation and 5.77× and 9.76× faster for incremental simulation.

Static timing analysis (STA) is an essential yet time-consuming task during the circuit design flow to ensure the correctness and performance of the design. Thanks to the advancement of general-purpose computing on graphics processing units (GPUs), new possibilities and challenges have arisen for boosting the performance of STA. In this work, we present an efficient and holistic GPU-accelerated STA engine. We accelerate major STA tasks, including levelization, delay computation, graph propagation, and multicorner analysis, by developing high-performance GPU kernels and data structures. By dividing the STA workloads into CPU–GPU concurrent tasks with managed dependencies, our acceleration framework supports versatile incremental updates. Furthermore, we have extended our approach to multicorner analysis by exploring a large amount of corner-level data parallelism using GPU computing. Our implementation based on the open-source STA engine OpenTimer has achieved up to$4.07\times $speed-up on single corner analysis, and up to$25.67\times $speed-up on multicorner analysis on TAU 2015 contest designs and a 14-nm technology.

As a key routine in static timing analysis (STA), path-based analysis (PBA) plays a very important role in refining the critical path report by reducing excessive slack pessimism. PBA is also well known for its long execution time, which makes it a hot topic for parallel computing in the STA community. However, nearly all of the parallel PBA algorithms are restricted to CPU architectures, which greatly limits their scalability. To achieve a new performance milestone on PBA, we must leverage the high throughput computing in the graphics processing unit (GPU). Therefore, in this work, we propose a new GPU-accelerated PBA framework which contains compact data structures and highly efficient kernels. By integrating with GPU-accelerated preprocessing steps, our framework can also effectively handle extensive critical path constraints. Besides, we highlight many optimization techniques that can overcome the execution bottleneck and further boost the performance. In experiments, we demonstrate$543\times$speed-up compared to the state-of-the-art PBA algorithm on the design with 1.6 million gates, which outperforms$25\times $–$45\times$over the state-of-the-art parallel PBA algorithm on 40 CPU cores. A fully optimized framework can achieve$3\times$–$5\times$speed-up on top of that.

Path searching is a central step in static timing analysis (STA). State-of-the-art algorithms need to generate path deviations for hundreds of thousands of paths, which becomes the runtime bottleneck of STA. Accelerating path searching is a challenging task due to the complex and iterative path generating process. In this work, we propose a novel path searching algorithm that has asymptotically lower runtime complexity than the state-of-the-art. We precompute the path deviations using mergeable heap and apply a group of deviations to a path in near-constant time. We prove our algorithm has a runtime complexity of$O(n\log n+k\log k)$which is asymptotically smaller than the state-of-the-art$O(nk)$. Experimental results show that our algorithm is up to$60\times$faster compared to OpenTimer and$1.8\times$compared to the leading path search algorithm based on suffix forest.

Graph-based timing propagation (GBP) is an essential component for all static timing analysis (STA) algorithms. To speed up GBP, the state-of-the-art timer leverages the task graph model to explore structural parallelism in an STA graph. However, many designs exhibit linear segments that cause the parallelism to serialize, degrading the performance significantly. To overcome this problem, we introduce an efficient GBP framework by exploring both structural and pipeline parallelisms in an STA task graph. Our framework identifies linear segments and parallelizes their propagation tasks using pipeline in an STA task graph. We have shown up to 25% performance improvement over the state-of-the-art task graph-based timer.

Graph-based propagation (GBP) is a common parallel pattern in many graph computing applications. Many GBP applications compose pipeline parallelism for each linear segment in the graph, where each task encapsulates a sequence of linearly dependent functions. This type of task-parallel pipeline parallelism is hard to express using mainstream programming frameworks (e.g., oneTBB) that count on data-parallel models to perform pipeline scheduling. In this paper, we introduce a new task-parallel method to compose pipeline parallelism in a GBP workload by leveraging the state-of-the-art control taskflow graph model. We demonstrate the promising performance of our method on a real circuit simulation workload.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2022 CAD Contest has 166 teams from all over the world. Moreover, the problems of this year cover state-of-the-art EDA research trends such as circuit security, 3D-IC, and design space exploration from well-known EDA/IC companies. We believe the contest keeps enhancing impact and boosting EDA researches.

High-throughput RTL simulation is critical for verifying today’s highly complex SoCs. Recent research has explored accelerating RTL simulation by leveraging event-driven approaches or partitioning heuristics to speed up simulation on a single stimulus. To further accelerate throughput performance, industry-quality functional verification signoff must explore running multiple stimulus (i.e., batch stimulus) simultaneously, either with directed tests or random inputs. In this paper, we propose RTLFlow, a GPU-accelerated RTL simulation flow with batch stimulus. RTLflow first transpiles RTL into CUDA kernels that each simulates a partition of the RTL simultaneously across multiple stimulus. It also leverages CUDA Graph and pipeline scheduling for efficient runtime execution. Measuring experimental results on a large industrial design (NVDLA) with 65536 stimulus, we show that RTLflow running on a single A6000 GPU can achieve a 40 × runtime speed-up when compared to an 80-thread multi-core CPU baseline.

Common path pessimism removal (CPPR) is imperative for eliminating redundant pessimism during static timing analysis (STA). However, turning on CPPR can significantly increase the analysis runtime by$10\times $–$100\times $in large designs. Recent years have seen much research on improving the algorithmic efficiencies of CPPR, but most are architecturally constrained by either the speed–accuracy tradeoff or design-specific pruning heuristics. In this article, we introduce a novel CPPR algorithm that is provably good and practically efficient. We have evaluated our algorithm on large industrial designs and demonstrated promising performance over the current state of the art. As an example, our algorithm outperforms the baseline by$36\times $–$135\times $faster when generating the top-10K post-CPPR critical paths on a million-gate design. At the extreme, our algorithm with one core is even$4\times $–$16\times $faster than the baseline with eight cores. Our algorithm also outperforms the commercial STA engine PrimeTime up to$26.99\times $faster. By exploiting parallelism within the circuit graph, we can reduce the memory consumption of our algorithm by 30%, with only 3% runtime increase.

Taskflow tackles the long-standing question: How can we make it easier for developers to program parallel and heterogeneous computer-aided design (CAD) applications with high performance and simultaneous high productivity? Taskflow introduces a new powerful task graph programming model to assist developers in the implementation of parallel and heterogeneous algorithms with complex control flow. We develop an efficient system runtime to solve many of the new scheduling challenges arising out of our models and optimize the performance across latency, energy efficiency, and throughput. Taskflow has demonstrated promising performance on both micro-benchmarks and real-world applications. As an example, Taskflow solved a large-scale circuit placement problem up to 17% faster, with$1.3\times $fewer memory,$2.1\times $less power consumption, and$2.9\times $higher throughput than two industrial-strength systems, oneTBB and StarPU, on a machine of 40 CPUs and 4 GPUs.

Taskflow aims to streamline the building of parallel and heterogeneous applications using a lightweight task graph-based approach. Taskflow introduces an expressive task graph programming model to assist developers in the implementation of parallel and heterogeneous decomposition strategies on a heterogeneous computing platform. Our programming model distinguishes itself as a very general class of task graph parallelism with in-graph control flow to enable end-to-end parallel optimization. To support our model with high performance, we design an efficient system runtime that solves many of the new scheduling challenges arising out of our models and optimizes the performance across latency, energy efficiency, and throughput. We have demonstrated the promising performance of Taskflow in real-world applications. As an example, Taskflow solves a large-scale machine learning workload up to 29% faster, 1.5× less memory, and 1.9× higher throughput than the industrial system, oneTBB, on a machine of 40 CPUs and 4 GPUs. We have opened the source of Taskflow and deployed it to large numbers of users in the open-source community.

The ever-increasing size of modern deep neural network (DNN) architectures has put increasing strain on the hardware needed to implement them. Sparsified DNNs can greatly reduce memory costs and increase throughput over standard DNNs, if the loss of accuracy can be adequately controlled. However, sparse DNNs present unique computational challenges. Efficient model or data parallelism algorithms are extremely hard to design and implement. The recent effort MIT/IEEE/Amazon HPEC Graph Challenge has drawn attention to high-performance inference methods for large sparse DNNs. In this paper, we introduce SNIG, an efficient inference engine for large sparse DNNs. SNIG develops highly optimized inference kernels and leverages the power of CUDA Graphs to enable efficient decomposition of model and data parallelisms. Our decomposition strategy is flexible and scalable to different partitions of data volumes, model sizes, and GPU numbers. We have evaluated SNIG on the official benchmarks of HPEC Sparse DNN Challenge and demonstrated its promising performance scalable from a single GPU to multiple GPUs. Compared to the champion of the 2019 HPEC Sparse DNN Challenge, SNIG can finish all inference workloads using only a single GPU. At the largest DNN, which has more than 4 billion parameters across 1920 layers each of 65536 neurons, SNIG is up to 2.3 faster than a state-of-the-art baseline under a machine of 4 GPUs. SNIG receives the Champion Award in 2020 HPEC Sparse DNN Challenge.

As technology advances, the complexity and size of integrated circuits continue to grow. Hierarchical design flow is a mainstream solution to speed up timing closure. Static timing analysis is a pivotal step in the flow but it can be timing-consuming on large flat designs. To reduce the long runtime, we introduce ATM, a high-accuracy extracted timing model for hierarchical timing analysis. Interface logic model (ILM) and extracted timing model (ETM) are the two popular paradigms for generating timing macros. ILM is accurate but large in model size, and ETM is compact but less accurate. Recent research has applied graph compression techniques to ILM to reduce model size with simultaneous high accuracy. However, the generated models are still very large compared to ETM, and its efficiency of in-context usage may be limited. We base ATM on the ETM paradigm and address its accuracy limitation. Experimental results on TAU 2017 benchmarks show that ATM reduces the maximum absolute error of ETM from 131 ps to less than 1 ps. Compared to the ILM-based approach, our accuracy differs within 1 ps and the generated model can be up to 270x smaller.

Common path pessimism removal (CPPR) is imperative for eliminating redundant pessimism during static timing analysis (STA). However, turning on CPPR can significantly increase the analysis runtime by $10-100\times$ in large designs. Recent years have seen much research on improving the algorithmic efficiencies of CPPR, but most are architecturally constrained by either the speed-accuracy trade-off or design-specific pruning heuristics. In this paper, we introduce a novel CPPR algorithm that is provably good and practically efficient. We have evaluated our algorithm on large industrial designs and demonstrated promising performance over the current state-of-the-art. As an example, our algorithm outperforms the baseline by $36-135\times$ faster when generating the top-10K post-CPPR critical paths on a million-gate design. At the extreme, our algorithm with one core is even $4-16\times$ faster than the baseline with 8 cores.

Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by $543\times$ on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by $25-45\times$.

Common path pessimism removal (CPPR) is a key step to eliminating unwanted pessimism during static timing analysis (STA). Unwanted pessimism will force designers and optimization algorithms to waste a significant yet unnecessary amount of effort on fixing paths that meet the intended timing constraints. However, CPPR is extremely time-consuming and can incur 10–100× runtime overheads to complete. Existing solutions for speeding up CPPR are architecturally constrained by CPU-only parallelism, and their runtimes do not scale beyond 8–16 cores. In this paper, we introduce HeteroCPPR, a new algorithm to accelerate CPPR by harnessing the power of heterogeneous CPU-GPU parallelism. We devise an efficient CPU-GPU task decomposition strategy and highly optimized GPU kernels to handle CPPR that scales to large numbers of paths. Also, HeteroCPPR can scale to multiple GPUs. As an example, HeteroCPPR is up to 16×faster than a state-of-the-art CPU-parallel CPPR algorithm for completing the analysis of 10K post-CPPR critical paths in a million-gate design under a machine of 40 CPUs and 4 GPUs.

Path-based Analysis (PBA) is a pivotal step in Static Timing Analysis (STA) for reducing slack pessimism and improving quality of results. Optimization flows often invoke PBA repeatedly with different critical path constraints to verify correct timing behavior under certain logic cone. However, PBA is extremely time consuming and state-of-the-art PBA algorithms are hardly scaled beyond a few CPU threads under constrained search space. In order to achieve new performance milestone, in this work, we propose a new GPU-accelerated PBA algorithm which can handle extensive path constraints and quickly report arbitrary number of critical paths in constrained search space. Experimental results show that our algorithm can generated identical path report and achieve up to 102x speed up on a million-gate design compared to the state-of-the-art algorithm.

The “CAD Contest at ICCAD” is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2021 CAD Contest has 137 teams from all over the world. The contest keeps enhancing impact and boosting EDA research.

Image detail enhancement is widely used in image processing tasks to give better look and higher contrast to images and photos. However, the reverse process that converts an enhanced image back to its original image usually does not have an explicit representation given only the enhanced image is available. In this work, we propose a generic framework of revertible image detail enhancement so that we can estimate the original image without extra information. We define a family of revertible detail enhancement operators that convert each pixel from original image to enhanced image and vice versa. A guidance image is used to decide which operator to use for each pixel. In the enhancement process, the guidance image is generated from the original image. In the reverse process, the guidance image is estimated from iterative optimization, making the process revertible. Experimental results show that the proposed enhancement framework can convert the enhanced image back to its original image without noticeable difference.

Since the first release in 2015, OpenTimer v1 has been used in many industrial and academic projects for analyzing the timing of custom designs. After four-year research and developments, we have announced OpenTimer v2-a major release that efficiently supports: 1) a new task-based parallel incremental timing analysis engine to break through the performance bottleneck of existing loop-based methods; 2) a new application programming interface (API) concept to exploit high degrees of parallelisms; and 3) an enhanced support for industry-standard design formats to improve user experience. Compared with OpenTimer v1, we rearchitect v2 with a modern C++ programming language and advanced parallel computing techniques to largely improve the tool performance and usability. For a particular example, OpenTimer v2 achieved up to 5.33× speedup over v1 in incremental timing, and scaled higher with increasing cores. Our contributions include both technical innovations and engineering knowledge that are open and accessible to promote timing research in the community.

This article introduces Cpp-Taskflow, a high-performance parallel task programming system, to streamline the building of large and complex parallel applications. Cpp-Taskflow leverages the power of modern C++ and task-based approaches to enable efficient implementations of parallel decomposition strategies. Our programming model can quickly handle not only traditional loop-level parallelism but also irregular patterns, such as graph algorithms and dynamic control flows. Compared with existing libraries, Cpp-Taskflow is more cost efficient in performance scaling and software integration. We have evaluated Cpp-Taskflow on both micro-benchmarks and large-scale design automation problems of million-scale tasking. In a particular timing analysis workload, Cpp-Taskflow outperformed OpenMP by 2× faster using 2× fewer lines of code. We have also shown Cpp-Taskflow achieved up to 47.81% speed-up with 28.5% less code over the industrial-strength library, Intel Threading Building Blocks, on a detailed placement problem.

In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

The ever-increasing power of graphics processing units (GPUs) has opened new opportunities for accelerating static timing analysis (STA) to a new milestone. Developing a CPU-GPU parallel STA engine is an extremely challenging job. We need to consider the unique problem characteristics of STA and distinct performance models between CPU and GPU, both of which require very strategic decomposition to benefit from heterogeneous parallelism. In this paper, we propose an efficient implementation for accelerating STA on a GPU. We leverage task-based approaches to decompose the STA workload into CPU-GPU dependent tasks where kernel computation and data processing overlap effectively. We develop GPU-efficient data structures and high-performance kernels to speed up various tasks of STA including levelization, delay calculation, and graph update. Our acceleration framework is flexible and adaptive. When tasks are scarce such as incremental timing, we run the normal CPU mode, and we enable GPU when tasks are massive. We have implemented our algorithms on top of OpenTimer and demonstrated promising performance speed-up on large designs. As an example, we achieved up to 3.69× speed-up on a large design of 1.6M gates and 1.6M nets using one GPU.

This paper introduces Taskflow to address the critical question of "How can we make it easier to implement and deploy parallel computer-aided design (CAD) algorithms on large heterogeneous nodes with high performance and simultaneous high productivity?" Parallelizing CAD is an extremely challenging job. Modern CAD applications exhibit unique computational patterns and user requirements that need very strategic decomposition to benefit from parallelism. Taskflow assists researchers and developers in the implementation complexity of parallel algorithms by introducing a new high-level programming model supported by an efficient runtime. By capitalizing on emerging parallelism comprising many-core central processing units (CPUs), graphics processing units (GPUs), and custom accelerators, Taskflow enables CAD to achieve new performance and productivity milestones that were previously out of reach.

The "CAD Contest at ICCAD" is a challenging, multi-month, research and development competition, focusing on advanced, real-world problems in the field of electronic design automation (EDA). Since 2012, the contest has been publishing many sophisticated circuit design problems, from system-level design to physical design, together with industrial benchmarks and solution evaluators. Contestants can participate in one or more problems provided by EDA/IC industry. The winners will be awarded at an ICCAD special session dedicated to this contest. Every year, the contest attracts more than a hundred teams, fosters productive industry-academia collaborations, and leads to hundreds of publications in top-tier conferences and journals. The 2020 CAD Contest hits a record high of 186 teams from all over the world, which represents more than 50% growth compared to last year. The contest keeps enhancing impact and boosting EDA research.

Work-stealing is a key component of many parallel task graph libraries such as Intel Threading Building Blocks (TBB) FlowGraph, Microsoft Task Parallel Library (TPL) Batch .Net, Cpp-Taskflow, and Nabbit. However, designing a correct and effective work-stealing scheduler is a notoriously difficult job, due to subtle implementation details of concurrency controls and decentralized coordination between threads. This problem becomes even more challenging when striving for optimal thread usage in handling parallel workloads with complex task graphs. As a result, we introduce in this paper an effective work-stealing scheduler for execution of task dependency graphs. Our scheduler adopts a simple and efficient strategy to adapt the number of working threads to available task parallelism at any time during the graph execution. Our strategy is provably good in preventing resource underutilization and simultaneously minimizing resource waste when tasks are scarce. We have evaluated our scheduler on both micro-benchmarks and a real-world circuit timing analysis workload, and demonstrated promising results over existing methods in terms of runtime, energy efficiency, and throughput.

Open source has started energizing both industrial and academic research and development in electronic design automation (EDA) systems. By moving to open source, we can speed up our effort and work with others who are working toward the same goals, while reducing costs and improving end products. However, building an open-source project is much more than placing the codebase on the web. In this paper, we will talk about essential building blocks to create an impactful open-source project, including source repository, project landing page, documentation, and continuous integration. We will also cover the use of web-based frameworks to design a showcase project to bring community's attention. We will then share our experience in developing an open-source timing analyzer (OpenTimer) and a parallel task programming library (Cpp-Taskflow), both of which are being used in many industrial and academic EDA research projects.

As the design complexities continue to grow, the need to efficiently analyze circuit timing with billions of transistors is quickly becoming the major bottleneck to the overall chip design flow. In this work we introduce a distributed timer that (1) has scalable performance, (2) can be seamless integrable to existing EDA applications, (3) enables transparent resource management, (4) has robust fault-tolerant control. We evaluate the distributed timer using a set of large industry benchmarks on a cluster with 24 nodes. The results show that the proposed timer achieves full accuracy over all designs with high performance and good scalability.

The recent TAU 2018 contest was seeking novel idea for efficient generation of timing reports. When the timing graph is updated, users query different forms of timing reports that happen subsequently and sequentially. This process is computationally expensive and inherently complex. Therefore, we introduce in this paper a general cache framework for efficient generation of timing critical paths. Our framework efficiently supports (1) a cache scheme to minimize duplicate calculation, (2) graph contraction to reduce the search space, and (3) multi-threading. We evaluated our framework on the TAU 2018 contest benchmarks and demonstrated promising performance over the top performer.

Recognizing fish species captured live on wild sea surface in videos is a challenging task due to the deformation of fish shape, self-occlusion of body parts and similar texture between different fish classes. To address these issues, we propose a fine-grained image classification method based on a deep convolution neural network (CNN) trained by an innovative metric learning scheme with a temporal constraint. By introducing the temporal constraint in metric learning, we help the network to learn a feature embedding which implicitly takes the shape and pose changes of fish into account. Besides, for each class, we learn the representative features discriminatively by introducing an intermediate layer in the CNN before the classifier. In testing stage, we first aggregate the features of a fish from each frame into several clips in the feature space, send the clips to the classifier and then perform weighted majority vote for the final classification. The experimental results show that our approach outperforms the conventional softmax classification on our rail-fishing dataset.

In this paper we introduce Cpp-Taskflow, a new C++ tasking library to help developers quickly write parallel programs using task dependency graphs. Cpp-Taskflow leverages the power of modern C++ and task-based approaches to enable efficient implementations of parallel decomposition strategies. Our programming model can quickly handle not only traditional loop-level parallelism, but also irregular patterns such as graph algorithms, incremental flows, and dynamic data structures. Compared with existing libraries, Cpp-Taskflow is more cost efficient in performance scaling and software integration. We have evaluated Cpp-Taskflow on both micro-benchmarks and real-world applications with million-scale tasking. In a machine learning example, Cpp-Taskflow achieved 1.5-2.7× less coding complexity and 14-38% speed-up over two industrial-strength libraries OpenMP Tasking and Intel Threading Building Blocks (TBB).

In this paper we present Cpp-Taskflow, a C++ parallel programming library that enables users to quickly develop parallel applications using the task dependency graph model. Developers formulate their application as a task dependency graph and Cpp-Taskflow will manage the task execution and concurrency control.The task graph model is expressive and composable. It can express both regular and irregular parallel patterns, and developers can quickly compose large programs from small parallel modules. Cpp-Taskflow has an intuitive and unified API set. Users only need to learn the APIs to build and dispatch a task graph and no complex parallel programming concept is required. We have conducted experiments using both micro-benchmarks and real-world applications and Cpp-Taskflow outperforms state-of-the-art parallel programming libraries in both runtime and coding effort. Cpp-Taskflow is open-source and has been used in both industry and academic projects. From our users' feedback, we believe Cpp-Taskflow can benefit the industry and research community greatly through its ease-of-programming and inspire new research directions in multimedia system/software design.

Recent years have seen rapid growth in data-driven distributed systems, such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C++ based distributed execution engine to streamline the development of high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details, such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown the promising performance from single multicore machines to clusters of computers. In a particular semiconductor design problem, we achieved 30× speedup with 40 nodes and 15× less development efforts over hand-crafted implementation.

Electronic monitoring of fishery activities has drawn increasing attention. Deformable objects, noise from the wild sea surface, and dynamic background, however, make conventional tracking and segmentation methods unreliable. In this paper, we present an online 3D tracking and segmentation system for stereo video-based monitoring of rail fish catching on the wild sea surface. Based on the result of a pre-trained image object (fish) detector, a Kalman filtering-based tracking system overcomes the issues of low detection scores of deformed objects and of unreliable bounding boxes by rescoring multiple object proposals using spatial information in 3D. A clustering-and-scoring strategy is then applied on the depth map so that a plane classification method can effectively segment the objects from the dynamic background without any prior modeling. The object segmentation is further refined using fully connected conditional random fields based on color and geometric features. Using the segmentation results, we can measure the 3D lengths of objects and update the positions of bounding boxes to help tracking. Experimental results show that a reliable tracking and measurement performance under noisy and dynamic sea surface environment can be achieved.

The ever-increasing design complexities have overwhelmed what is offered by existing EDA tools. As a result, the recent EDA industry is driving the need for distributed computing to leverage large-scale compute-intensive problems, in particular, power grid analysis. In this paper, we introduce a distributed power grid analysis framework based on the stream graph model. We show that the stream graph model has better programmability over the MPI and enables flexible domain decomposition without limited by hardware resource. In addition, we design an efficient scheduling policy for this particular workload to maximize the cluster utilization to improve the performance. The experimental results demonstrated the promising performance of our framework that scales from single multi-core machines to a distributed computer cluster.

In this paper we present DtCraft, a distributed execution engine that enables a new powerful programming model to streamline cluster computing. Applications are described in a set of data-parallel streams, leaving difficult execution details and concurrency controls handled by our system kernel transparently. Compared with existing systems, DtCraft is unique in (1) an efficient stream-oriented programming paradigm using modern C++17, (2) an in-context resource controller and task executor based on Linux container technology, and (3) ease of development from prototyping machines to production cloud environments. These capabilities power industry applications and create new research directions in machine learning, stream processing, and distributed multimedia systems.

The ever-increasing design complexity is driving the need of fast and accurate macro-modeling algorithms to accelerate the hierarchical timing. We introduce LibAbs, an effective macro-modeling algorithm that efficiently supports high accuracy, high compression rate, and multi-threading. LibAbs applies tree-based graph reduction techniques to reduce the model size with comparable accuracy values to the flat model under multi-threaded environment. LibAbs outperforms existing tools including top winners from TAU 2016 macro-modeling contest in terms of model size, accuracy, and runtime on industry benchmarks. The in-context usage of our abstracted model has also demonstrated promising performance for timing-driven optimizations in large hierarchical designs.

Recent years have seen rapid growth in data-driven distributed systems such as Hadoop MapReduce, Spark, and Dryad. However, the counterparts for high-performance or compute-intensive applications including large-scale optimizations, modeling, and simulations are still nascent. In this paper, we introduce DtCraft, a modern C+,+,17-based distributed execution engine that efficiently supports a new powerful programming model for building high-performance parallel applications. Users need no understanding of distributed computing and can focus on high-level developments, leaving difficult details such as concurrency controls, workload distribution, and fault tolerance handled by our system transparently. We have evaluated DtCraft on both micro-benchmarks and large-scale optimization problems, and shown promising performance on computer clusters. In a particular semicondictor design problem, we achieved 30 x speedup with 40 nodes and 15 × less development efforts over hand-crafted implementation.

Given ever-increasing circuit complexities, recent trends are driving the requirement for distributed timing analysis (DTA) in electronic design automation (EDA) tools. However, DTA has received little research attention so far and remains a critical problem. In this paper, we introduce a DTA framework for large designs. Our framework supports (1) general design partitions in distributed file systems, (2) non-blocking IO with event-driven loop for effective communication and computation overlap, and (3) an efficient messaging interface between application and network layers. The effectiveness and scalability of our framework has been evaluated on large hierarchical industry designs over a cluster with hundreds of machines.

Image processing and analysis techniques have drawn increasing attention since they enable a non-extractive and non-lethal approach to fisheries survey, such as fish size measurement, abundance prediction, catch estimation and compliance, species recognition and population counting. In this work, we present an innovative and effective method for measuring the chute-based fish length based on the morphological midline of the fish. The midline is generated through recursive morphological operations on the segmented fish mask. To conduct reliable measurement, even under harsh environment, we also propose a systematic method for detecting water drop on camera lens. The robust detection, which can be performed either in real-time or in offline processing, is based on a blur measure derived from the gradient of the image and the contour of fish.

The recent TAU computer-aided design (CAD) contest has aimed to seek novel ideas for accurate and fast common path pessimism removal (CPPR). Unnecessary pessimism forces the static timing analysis tool to report worse violation than the true timing properties owned by physical circuits, thereby misleading signoff timing into a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper UI-Timer 1.0, a powerful CPPR algorithm which achieves high accuracy and ultrafast runtime. Unlike existing approaches which are dominated by explicit path search, UI-Timer 1.0 proves that by implicit path representation the amount of search effort can be significantly reduced. Our timer is superior in both space and time saving, from which memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 CAD contest have justified that UI-Timer 1.0 achieved the best result in terms of accuracy and runtime over existing CPPR algorithms.

We introduce in this paper, OpenTimer, an open-source timing analysis tool that efficiently supports (1) both block-based and path-based timing propagations, (2) common path pessimism removal (CPPR), and (3) incremental processing. OpenTimer works on industry formats (e.g., .v, .spef, .lib, .sdc) and is designed to be parallel and portable. To further facilitate integration between timing and other electronic design automation (EDA) applications such as timing-driven placement and routing, OpenTimer provides user-friendly application programming interface (API) for inactive analysis. Experimental results on industry benchmarks released from TAU 2015 timing analysis contest have demonstrated remarkable results achieved by OpenTimer, especially in its order-of-magnitude speedup over existing timers.

Path-based timing analysis (PBA) is a pivotal step to achieve accurate timing signoff. A core primitive extracts a large set of paths subject to path-specific or less-pessimistic timing update. However, this process in nature demands a very high computational complexity and thus has been a major bottleneck in accelerating timing closure. Therefore, we introduce in this paper a fast and scalable PBA framework with MapReduce - a recent programming paradigm invented by Google for big-data processing. Inspired by the spirit of MapReduce, we formulate our problem into tasks that are associated with keys and values and perform massively-parallel map and reduce operations on a distributed system. Experimental results demonstrated that our approach can easily analyze million nodes in a single minute.

Common-path-pessimism removal (CPPR) is a pivotal step to achieve accurate timing signoff. Unnecessary pessimism might arise quality-of-result (QoR) concerns such as reporting worse violations than the true timing properties owned by the physical circuit. In other words, signoff timing report will conclude a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper a fast path-based timing analysis for CPPR. Unlike existing approaches which are dominated by explicit path search, we perform implicit path representation which yields significantly smaller search space and faster runtime. Specifically, our algorithm is superior in both space and time saving, from which the memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 timing analysis contest have shown that our algorithm won the first place and achieved the best result in terms of accuracy and runtime over all participating teams.

The recent TAU computer-aided design (CAD) contest has aimed to seek novel ideas for accurate and fast clock network pessimism removal (CNPR). Unnecessary pessimism forces the static-timing analysis (STA) tool to report worse violation than the true timing properties owned by physical circuits, thereby misleading signoff timing into a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper UI-Timer, a powerful CNPR algorithm which achieves exact accuracy and ultra-fast runtime. Unlike existing approaches which are dominated by explicit path search, UI-Timer proves that by implicit path representation the amount of search effort can be significantly reduced. Our timer is superior in both space and time saving, from which memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 CAD contest have justified that UI-Timer achieved the best result in terms of accuracy and runtime over all participating timers.

Electrowetting-on-dielectric (EWOD) chips have become the most promising technology to realize pin-constrained digital microfluidic biochips (PDMFBs). Reliability is a critical factor in the design flow of EWOD chips, it directly affects the execution of bioassays. The trapped charge problem is the major factor degrading chip reliability, and this problem is induced by excessive applied voltage. Nevertheless, to comply with the pin constraint for PDMFBs, signal merging is inevitably involved, and thereby incurring trapped charges due to unawareness of the applied voltage. Except for the trapped charge problem, the wire routing required to accomplish electrical connections increases the design complexity of pin-constrained EWOD chips. However, previous research has failed to address the problems of excessive applied voltage and wire routing. Therefore, the resulting chip is more likely to fail during execution or cannot be realized because of the wire routing problem. A network-flow-based algorithm for reliability-driven pin-constrained EWOD chips is presented in this paper. The proposed algorithm not only minimizes the reliability problem induced by signal merging, but also prevents the operational failure caused by inappropriate addressing results. The proposed algorithm also provides a comprehensive routing solution for EWOD chip-level designs. The experimental results demonstrate the effectiveness of the proposed algorithm on real-life chips.

Recently, digital microfluidic biochips (DMFBs) have revolutionized many biochemical laboratory procedures and received much attention due to their many advantages, such as high throughput, automatic control, and low cost. To meet the challenges of increasing design complexity, computer-aided-design (CAD) tools have been used to build DMFBs efficiently. Current CAD tools generally conduct a two-stage based design flow of fluidic-level synthesis followed by chip-level design to optimize fluidic behaviors and chip architecture separately. Nevertheless, existing fluidic-chip design gap will become even wider with a rapid escalation in the number of assay operations incorporated into a single DMFB. As more and more large-scale assay protocols are delivered in the current emerging marketplace, this problem may potentially restrict the effectiveness and feasibility of the entire DMFB realization and thus needs to be solved quickly. In this paper, we propose the first fluidic-chip co-design methodology for DMFBs to effectively bridge the fluidic-chip design gap. Our work provides a comprehensive integration throughout fluidic-operation scheduling, chip layout generation, control pin assignment, and wiring solution to achieve higher design performance and feasibility. Experimental results show the effectiveness, robustness, and scalability of our co-design methodology on a set of real-life assay applications.

Electrowetting-on-dielectric (EWOD) chips have become the most popular actuators, particularly for droplet-based digital microfluidic biochip (DMFB) systems. In order to enable the electrical manipulations, wire routing is a key problem in designing EWOD chips. Unlike traditional very-large-scale-integration (VLSI) routing problems, in addition to routing-path establishment on signal pins, the pin-constrained EWOD-chip routing problem must address the issue of signal sharing for pin-count reduction under a practical constraint posed by a limited pin-count supply. Moreover, EWOD-chip designs might incur several obstacles in the routing region due to embedded devices for specific fluidic protocols. However, no existing work considers the EWOD-chip routing with obstacles and, therefore, lots of manual design efforts are involved. To remedy this insufficiency, we propose in this paper the first routing algorithm for pin-constrained EWOD chips with obstacle avoidance. The proposed algorithm, based on effective integer-linear-programming (ILP) formulation as well as efficient routing framework, can achieve high routability with a low design complexity. Experimental results based on real-life chips with obstacles demonstrate the high routability of proposed algorithm for pin-constrained EWOD chips with obstacle avoidance.

In recent studies, digital microfluidic biochips (DMFBs) have been a promising solution for lab-on-a-chip and bio-assay experiments because of their flexible application and low fabrication cost. However, the reliability problem is an imperative issue to guarantee the valid function of DMFBs. The reliability of DMFBs decreases when electrodes are excessively actuated, preventing droplets on DMFBs controlled successfully. Because the placement for bio-assays in DMFBs is a key step in generating corresponding actuating signals, the reliability of DMFBs must be considered during biochip placement to avoid excessive actuation. Although researchers have proposed several DMFB placement algorithms, they have failed to consider the reliability issue. In addition, previous algorithms were all based on the simulated-annealing (SA) method, which is time consuming and does not guarantee to obtain an optimal solution. This paper proposes the first reliability-oriented non-SA placement algorithm for DMFBs. This approach considers the reliability problem during placement, and uses the 3-D deferred decision making (3D-DDM) technique to enumerate only possible placement solutions. Large-scale DMFB placement can be synthesized efficiently by partitioning the operation sequential graph of bioassays. Experimental results demonstrate that the proposed technique can achieve reliability-oriented placement for DMFBs without excessive actuation in each electrode, while optimizing bioassay completion time.

Electrowetting-on-dielectric (EWOD) chips have become the most popular actuator particularly for droplet-based digital microfluidic (DMF) systems. In order to enable the electrical manipulations, wire routing is a key problem in designing EWOD chips. Unlike traditional very-large-scale-integration (VLSI) routing problems, in addition to routing-path establishment on signal pins, the EWOD-chip routing problem needs to address the issue of signal sharing for pin-count reduction under a practical constraint posed by limited pin-count supply. Moreover, EWOD-chip designs might incur several obstacles in the routing region due to embedded devices for specific fluidic protocols. However, no existing works consider the EWOD-chip routing with obstacles. To remedy this insufficiency, we propose in this paper the first obstacle-avoiding routing algorithm for pin-constrained EWOD chips. Our algorithm, based on effective integer-linear-programming (ILP) formulation as well as efficient routing framework, can achieve high routability with a low design complexity. Experimental results based on real-life chips with obstacles demonstrate the high routability of our obstacle-avoiding routing algorithm for pin-constrained EWOD chips.

Electrowetting-on-dielectric (EWOD) chips have become the most promising technology to realize pin-constrained digital microfluidic biochips (PDMFBs). In the design flow of EWOD chips, reliability is a critical challenge as it directly affects execution of bioassays. The major factor to degrade chip reliability is the trapped charge problem, which is induced by excessive applied voltage. Nevertheless, to comply with the pin constraint for PDMFBs, signal merging is inevitably involved, and thereby incurring trapped charges due to unawareness of applied voltage. Except for the trapped charge problem, wire routing to accomplish electrical connections increases the design complexity of pin-constrained EWOD chips. Unfortunately, no existing works tackle the problems of excessive applied voltage and wire routing, and thus the resultant chip will have more probabilities to fail during execution or can not be realized because of wire routing problem. In this paper, we present a network-flow based algorithm for reliability-driven pin-constrained EWOD chips with the consideration of voltage issue. Our algorithm not only minimizes the reliability problem induced by signal merging but also provides a comprehensive routing solution for EWOD chip-level designs. The experimental results demonstrate the effectiveness of proposed algorithm on real-life chips.

Recently, digital microfluidic biochips (DMFBs) have revolutionized many biochemical laboratory procedures and received much attention due to many advantages such as high throughput, automatic control, and low cost. To meet the challenges of increasing design complexity, computer-aided-design (CAD) tools have been involved to build DMFBs efficiently. Current CAD tools generally conduct a two-stage based design flow of fluidic-level synthesis followed by chip-level design to optimize fluidic behaviors and chip architecture separately. Nevertheless, existing fluidic-chip design gap will become even wider with a rapid escalation in the number of assay operations incorporated into a single DMFB. As more and more large-scale assay protocols are delivered in current emerging marketplace, this problem may potentially restrict the effectiveness and feasibility of the entire DMFB realization and thus needs to be solved quickly. In this paper, we propose the first fluidic-chip co-design methodology for DMFBs to effectively bridge the fluidic-chip design gap. Our work provides a comprehensive integration throughout fluidic-operation scheduling, chip layout generation, control pin assignment, and wiring solution to achieve higher design performance and feasibility. Experimental results show the effectiveness, robustness, and scalability of our co-design methodology on a set of real-life assay applications.

In recent emerging marketplace, designs for pin-constrained digital microfluidic biochips (PDMFBs) have received much attention due to the large impact on packaging and product cost. One of the major approaches, broadcast addressing, reduces the pin count by assigning a single control pin to multiple electrodes with mutually-compatible control signals. Prior works utilize this addressing scheme by minimally grouping electrode sets with non-conflict signal merging. However, merging control signals also introduces redundant actuations, which potentially cause a high power-consumption problem. Recent studies on PDMFBs have indicated that high power consumption not only decreases the product lifetime but also degrades the system reliability. Unfortunately, this power-aware design concern is still not readily available among current design automations of PDMFBs. To cope with these issues, we propose in this paper the first power-aware broadcast addressing for PDMFBs. Our algorithm simultaneously takes pin-count reduction and power-consumption minimization into consideration, thereby achieving higher integration and better design performance. Experimental results demonstrate the effectiveness of our algorithm.

Designs for pin-constrained digital microfluidic biochips (PDMFBs) are receiving much attention because they simplify chip fabrication and packaging, and reduce product cost. To reduce the pin count, broadcast addressing, by minimally grouping electrode sets with non-conflict signal merging, has emerged as a promising solution. Nevertheless, naive signal merging has the potential to cause excessive electrode actuations, which has been reported to have direct and adverse effect on chip reliability. According to recent studies, reliability is an important attribute for PDMFBs particularly developed for medical applications as it directly affects the final medical decision making. However, no research findings have been reported on the reliability problem in pin-constrained designs. To make PDMFBs more feasible for practical applications, we propose in this paper the first matching-based reliability-oriented broadcast-addressing algorithm for PDMFBs. We identify the factors that affect reliability and incorporate into the design-technique attributes that enhance reliability. Experimental results demonstrate the effectiveness of the proposed algorithm.

With the increasing design complexities, the design of pin-constrained digital microfluidic biochips (PDMFBs) is of practical importance for the emerging marketplace. However, solutions of current pin-count reduction are inevitably limited by simply adopting it after the droplet routing stage. In this paper, we propose the first droplet routing algorithm for PDMFBs that can integrate pin-count reduction with droplet routing stage. Furthermore, our algorithm is capable of minimizing the number of control pins, the number of used cells, and the droplet routing time. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem for PDMFBs with simultaneous multiobjective optimization. Due to the complexity of this ILP formulation, we also propose a two-stage technique of global routing followed by incremental ILP-based routing to reduce the solution space. To further reduce the runtime, we present a deterministic ILP formulation that casts the original routing optimization problem into a decision problem, and solve it by a binary solution search method that searches in logarithmic time. Extensive experiments demonstrate that in terms of the number of the control pins, the number of the used cells, and the routing time, we obtain much better achievement than all the state-of-the-art algorithms in any aspect.

Electrowetting-on-dielectric (EWOD) chips have emerged as the most widely used actuators for digital microfluidic (DMF) systems. These devices enable the electrical manipulation of microfluidics with various advantages, such as low power consumption, flexibility, accuracy, and efficiency. In addressing the need for low-cost and practical fabrication, pin-count reduction has become a key problem to the large-scale integration of EWOD-chip designs. One of the major approaches, broadcast addressing, reduces the pin count by assigning a single control pin to multiple electrodes with mutually compatible control signals. Most previous studies utilize this addressing scheme by scheduling fluidic-level synthesis on pin-constrained chip arrays. However, the associated interconnect routing problem is still not provided in currently available DMF automations, and thus the broadcast-addressing scheme cannot be actually realized. In this paper, we present the first network-flow based pin-count aware routing algorithm for EWOD-chip designs with a broadcast electrode-addressing scheme. Our algorithm simultaneously takes pin-count reduction and wirelength minimization into consideration for higher integration and better design performance. Experimental results show the effectiveness and scalability of our algorithm on a set of real-life chip applications.

Electrowetting-on-dielectric (EWOD) chips have emerged as the most widely used actuators for digital microfluidic (DMF) systems. These devices enable the electrical manipulation of microfluidics with various advantages such as low power consumption, flexibility, accuracy, and efficiency. In addressing the need for low-cost and practical fabrication, pin-count reduction has become a key problem to the large-scale integration of EWOD-chip designs. One of the major approaches, broadcast addressing, reduces the pin count by assigning a single control pin to multiple electrodes with mutually compatible control signals. Most previous studies utilize this addressing scheme by scheduling fluidic-level synthesis on pin-constrained chip arrays. However, the associated interconnect routing problem is still not provided in currently available DMF automations, and thus the broadcast-addressing scheme cannot be actually realized. In this paper, we present the first network-flow based pin-count aware routing algorithm for EWOD-chip designs with a broadcast electrode-addressing scheme. Our algorithm simultaneously takes pin-count reduction and wirelength minimization into consideration for higher integration and better design performance. Experimental results show the effectiveness and scalability of our algorithm on a set of real-life chip applications.

With the increasing design complexities, the design of pin-constrained digital microfluidic biochips (PDMFBs) is of practical importance for the emerging marketplace. However, the solution of current pin-count aware technique is inevitably limited by simply adopting it after the droplet routing stage. In this paper, we propose the first droplet routing algorithm for PDMFBs that can integrate pin-count technique with droplet routing stage. Furthermore, our algorithm is capable of simultaneously minimizing the number of control pins, the number of used cells, and the latest arrival time. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem for PDMFBs with simultaneous multi-objective optimization. Due to the complexity of this ILP formulation, we also propose a two-stage technique of global routing followed by incremental ILP-based routing to reduce the solution space. To further reduce the runtime, we present a deterministic. ILP formulation that casts the original routing optimization problem into a decision problem, and solve it by a binary solution search method that searches in logarithmic time. Extensive experiments demonstrate that in terms of the number of the control pins, the number of the used cells, and the latest arrival time, we acquire much better achievement than all the state-of-the-art algorithms in any aspect.

Recent advances of digital microfluidic biochips (DMFBs) have revolutionized the traditional laboratory procedures. By providing the droplet-based system, DMFB can perform real-time biological analysis and safety-critical biomedical applications. However, different droplets being transported and manipulated on the DMFB may introduce the contamination problem caused by liquid residue between different biomolecules. To overcome this problem, a wash droplet is introduced to clean the contaminations on the surface of the microfluidic array. However, current scheduling of wash droplet does not restrict the extra used cells and execution time of bioassay, thereby degrading the reliability and fault-tolerance significantly. In this paper, we propose a contamination aware droplet routing algorithm for DMFBs. To reduce the routing complexity and the used cells, we first construct preferred routing tracks by analyzing the global moving vector of droplets to guide the droplet routing. To cope with contaminations within one subproblem, we first apply ak-shortest path routing technique to minimize the contaminated spots. Then, to take advantage of multiple wash droplets, we adopt a minimum cost circulation (MCC) algorithm for optimal wash-droplet routing to simultaneously minimize used cells and the cleaning time. Since the droplet routing problem consists of several subproblems, a look-ahead prediction technique is further used to determine the contaminations between successive subproblems. After that, we can simultaneously clean both contaminations within one subproblem and those between successive subproblems by using the MCC-based algorithm to reduce the execution time and the used cells significantly. Based on four widely used bioassays, our algorithm reduces the used cells and the execution time significantly compared with the state-of-the-art algorithm.

As the microfluidic technology advances, the design complexity of digital microfluidic biochips (DMFB) are expected to explode in the near future. One of the most critical challenges for DMFB design is the droplet routing problem, which schedules the movement of each droplet in a time-multiplexed manner. In this paper, we propose a fast routability- and performance-driven droplet router for DMFBs. The main contributions of our work are: (1) a global moving vector analysis for constructing preferred routing tracks to minimize the number of used unit cells; (2) an entropy-based equation to determine the routing order of droplets for better routability; (3) a routing compaction technique by dynamic programming to minimize the latest arrival time of droplets. Experimental results show that our algorithm achieves 100% routing completion for all test cases on three Benchmark Suites while the previous algorithms are not. In addition to routability, compared with the state-of-the-art high-performance routing on the Benchmark Suite I (Cho and Pan, 2008), the experimental results still show that our algorithm performed better in runtime by 40%, reduced the latest arrival time by 21%, reduced the used unit cells by 10%. Furthermore, experiment results on Benchmark Suite II and III are also very promising. Based on the evaluation of three Benchmark Suites, our algorithm demonstrates the efficiency and robustness of handling complex droplet routing problem over the existing algorithms.