Memory allocation efficiency remains a significant challenge in High-Level Synthesis (HLS) frameworks. Current dynamic memory management (DMM) techniques suffer from issues such as inefficiency, fragmentation, considerable hardware overhead, and difficulties in handling complex workloads. Conversely, existing static memory approaches often exhibit poor efficiency when addressing large-scale applications. Moreover, both dynamic and static methods lack sufficient support for High Bandwidth Memory (HBM), thereby limiting their effectiveness in complex neural network scenarios. To overcome these challenges, we propose an optimized static memory allocation strategy specifically designed for FPGA systems. Our approach leverages the computational characteristic of neural network applications, which typically exhibit cyclic and fixed-bound behaviors. We tightly integrate an MLIR-based compiler with an efficient static memory allocator, eliminating the need for dedicated allocator hardware while ensuring efficient runtime memory access. Furthermore, we introduce a customized AXI bus distribution mechanism and an address mapping strategy optimized for the multi-port and multi-bank architecture of HBM. This design significantly enhances bandwidth utilization and reduces latency. Experimental results confirm that our proposed methodology substantially improves allocation efficiency, spatial utilization, and effectively manages complex memory scenarios, thereby outperforming existing state-of-the-art solutions.

Multi-corner timing analysis is essential for ensuring the robustness of circuits under variations in process, voltage, and temperature (PVT). Along with clock skew scheduling, delay padding is used to address hold violations. However, applying padding consistently in multiple corners is challenging due to conflicting constraints and the prevalence of “ping-pong” effects. This paper presents a novel methodology that uses dual decomposition to tackle this challenge. The problem is divided into a set of network flow problems, one for each corner. These problems are coupled through shared delay variables. Coordinating these subproblems using Lagrange multipliers ensures consistent padding assignments across corners. Additionally, traditional padding methods often struggle with physical feasibility. The incorporation of path relationship analysis is proposed to identify viable, physically feasible padding locations. Experimental results on industrial benchmarks demonstrate that the proposed method efficiently identifies feasible padding solutions and achieves the minimum clock period that satisfies the setup and hold time constraints for all corners. Compared to the single worst-case corner baseline, the optimized clock period is reduced by up to 9%, highlighting the effectiveness of our approach.

Traditional FPGA PLB designs are constrained by the exponential increase in LUT area with the augmentation of inputs. Recent work has explored a pruned LUT based on the non-uniform distribution of Boolean functions in practical benchmarks, designing an 8-input PLB with enhanced functionality and a modest area overhead. Nonetheless, the existing LUT pruning algorithm is prone to local optima and focuses exclusively on SRAM pruning, neglecting lookahead optimization of the MUX tree. In this paper, we propose Compacted-LUT (CLUT), a fine-grained customizable LUT architecture via SRAM-MUX co-optimization. Based on the principle of LUT pruning, we design a novel representation for Boolean functions. This representation directly associates each Boolean function with the number of required SRAMs and MUX-tree transistors. On this basis, a novel evaluation model for the hardware-friendliness of Boolean functions can be formulated. We further design a beam search algorithm to identify an optimal subset of Boolean functions in target benchmarks based on evaluation results. With this subset, the customizable SRAM-MUX co-optimized CLUT architecture can be generated. Furthermore, we propose Asym-CLUT6, a function-diverse 8-input PLB composed of two variant 6-input CLUTs. We evaluate Asym-CLUT6 on VTR and Koios benchmarks. Post-route results show that, compared to the Altera Stratix 10-like architecture and Dual-RLUT6, Asym-CLUT6 reduces the area-delay product by 13.65% and 10.06% on average.

Coarse-grained Reconfigurable Architecture (CGRA) is a competitive accelerator architecture for computation-intensive loop kernels. Spatial CGRA is a typical CGRA that performs all the operations spatially to reduce reconfiguration costs within a single iteration, demanding high data parallelism. To achieve this goal, one of the main challenges is the loop-carried dependency between memory accesses. Many existing CGRA compilers struggle to precisely analyze the dependency distance, especially when accesses involve complex address patterns. Consequently, these compilers often default to setting the distance to one, based on a worst-case assumption, leading to degraded performance. However, we observe that a precise distance can improve performance significantly, raising the requirement for an efficient distance calculation approach. Another challenge is the performance constraints of single-bank memory, which necessitate the designer partitioning the original data into a multi-bank memory. However, we observe that the mapping result can cause the inter-iteration conflict, thereby invalidating the memory partition scheme. Therefore, an efficient post-mapping conflict detection is required. In this paper, we develop a constraint satisfaction problem (CSP)-based approach for calculating dependency distance and detecting conflicts, which determines the maximum available dependency distance and identifies conflicts within both intra- and inter-iterations. Besides, we formulate access scheduling as a graph coloring problem, which can minimize conflicts and improve performance. Overall, we develop a comprehensive end-to-end framework with architectural and compiler support for efficient data parallelism on spatial CGRA. We conduct extensive experiments to systematically evaluate the impact of different approaches on performance and compilation. Evaluation results show that our architecture can achieve 13.16× and 1.19× (up to 1.68×) average performance improvements compared to a RISC-V CPU and a state-of-the-art CGRA SoC, respectively. Besides, our architecture has 7.38× and 1.18× (up to 1.65×) average energy efficiency gains compared to these two architectures.

As the size of a circuit increases, previous reinforcement learning (RL) approaches struggle to effectively explore the logic optimization sequences of large-scale Boolean networks due to the long runtime overhead with poor optimization results. This article proposes LOFMPL: an open-source logic optimization framework with Maximum Fanout-Free Cone (MFFC) based hypergraph partitioning and reinforcement learning. The novel two-stage MFFC-based hypergraph partitioning can divide the circuit into highly independent subnetworks, which can be explored by an enhanced parallel RL-based design space exploration engine with an improved objective function. The experiment is conducted based on more than 150 benchmarks with logic optimization and ASIC technology mapping tasks and compared with other ML-based and greedy methods. The different partitioning algorithms are also compared for the subsequent logic optimization. Experimental results demonstrate that the proposed partitioning algorithm significantly enhances optimization quality without greatly increasing partitioning time, outperforming the KaHypar algorithm. Additionally, for the logic optimization task, the proposed method achieves a node-level-product improvement of 13% over the RLG synthesis exploration technique, 3% over the ESE reinforcement learning framework, 14% over the Boils synthesis method, and 7% over the DRiLLS synthesis method, while delivering greater reductions in node count compared with the Bulls-Eye optimization technique. For the ASIC technology mapping task, the proposed method achieves an area-delay-product improvement of 23% over the LSOracle framework, 9% over the Boils synthesis method, and 5% over the DRiLLS synthesis method. Hence, LOFMPL can achieve better results within the same runtime constraints compared with state-of-the-art works.

Coarse-Grained Reconfigurable Architecture (CGRA) is a competitive accelerator architecture for computation-intensive loop kernels. Spatial CGRA is a typical CGRA that performs all the operations spatially, demanding high data parallelism. Given the performance limitations of single-bank memory, partitioning original data into multi-bank memory within the spatial CGRA is favored. However, we observe that the mapping result can cause the inter-iteration conflict, thereby invalidating the memory partition scheme.

Clock skew scheduling is a cost-effective technique for enhancing the synchronous digital VLSI systems. The technique solely requires adjusting the clock skew to meet the timing constraints of the signal paths in order to increase the clock frequency or yield. In the past, Gaussian distributions were commonly assumed in the probability density function (PDF) modeling of maximum and minimum path delays under process variations. However, this assumption may not be appropriate due to the notable asymmetry of the actual path delay distributions. In this paper, we suggest the generalized extreme value (GEV) distribution as a potential alternative. Furthermore, we evaluate maximum likelihood estimation, linear-moments, and the method of moments (MoM) for parameter estimation. Experimental results show that the GEV distribution can more accurately approximate the cumulative distribution function (CDF) of the benchmark circuit path delays, resulting in an average improvement of 40% in the Kolmogorov-Smirnov (KS) statistic. Furthermore, yield-driven clock skew scheduling based on the GEV distribution produces superior timing yield outcomes compared to that based on the Gaussian distribution, with an improvement in timing yield up to 33% and average 8%.

Coarse-Grained Reconfigurable Architecture (CGRA) emerges as a competitive accelerator due to its high flexibility and energy efficiency. However, most CGRAs are effective for computation-intensive applications with regular loops but struggle with irregular loops containing control flows. These loops introduce fine-grained logic operations and are costly to execute by coarse-grained arithmetic units in CGRA. Efficiently handling such logic operations necessitates incorporating Boolean algebra optimization, which can improve logic density and reduce logic depth. Unfortunately, no previous research has incorporated it into the compilation flow to support irregular loops efficiently.We proposeCOFFA, an open-source framework for heterogeneous architecture with a RISC-V CPU and a fused-grained reconfigurable accelerator, which integrates coarse-grained arithmetic and fine-grained logic units, along with flexible IO units and distributed interconnects. As a software/hardware co-design framework,COFFAhas a powerful compiler that extracts and optimizes fine-grained logic operations from irregular loops, performs coarse-grained arithmetic and memory optimizations, and offloads the loops to the accelerator.Across various challenging benchmarks with irregular loops,COFFAachieves significant performance and energy efficiency improvements over an in-order, an out-of-order RISC-V CPUs, and a recent FPGA, respectively. Moreover, compared with the state-of-the-art CGRAUE-CGRAandHycube,COFFAcan achieve 2.5× and 3.5× performance gains, respectively.

Coarse-grained reconfigurable architecture (CGRA) is a type of reconfigurable computing architecture suitable for emerging applications that require dynamic compilation hardware. However, the resource utilization of existing CGRA is low due to the lack of flexibility across varied application granularity. In this paper, we propose a CGRA framework for multiple dataflow lanes (MDCRA). It supports post-silicon computational granularity adjustments. Evaluated with Polybench, Machsuite and Express, the speedup of MDCRA is$24.83\times$higher than CPU CVA6, and$2.08\times$higher than vector processor Ara. Compared with TRAM and DSAGEN, MDCRA achieves an area reduction of 27% and 47% respectively with the same speedup. Besides, compared with OpenCGRA, the average utilization of function units is improved by 20.05%.

Convolutional neural networks (CNNs) and transformer neural networks have been adopted in a wide range of applications such as natural language processing and computer vision. Coarse-grained reconfigurable architectures (CGRAs) are highly suitable for CNN and transformer applications due to their high flexibility and energy efficiency. However, current implementations of CGRA for CNNs and transformers have several limitations including the lack of System-on-Chip (SoC), insufficient support for nonlinear functions and the absence of a software toolchain. To address these challenges, we present CFEACT, a CGRA-based framework that enables agile development of CNN and transformer accelerators. CFEACT offers a broad design space of efficient CGRA accelerators through a highly flexible architecture template. The well-designed SoC, innovative mapping schemes, and comprehensive software toolchain offer a complete solution for implementing various CNN and transformer models on the generated CGRAs. Compared with the state-of-the-art works, accelerators generated by CFEACT can achieve more than $2 \times$ improvement in area-delay product for CNNs and an average of $2 \times$ higher performance for transformers.

Lightweight convolutional neural networks (CNNs) have become increasingly popular due to their lower computational complexity and fewer memory accesses with equivalent accuracy compared to previous CNN models. However, the newly proposed networks bring new challenges to efficient hardware design, such as, in EfficientNet, depthwise convolution, squeeze-and-excitation (SE) module, and swish/sigmoid functions. Although individual engine architecture could achieve a high computing efficiency for the standard convolution or the depth-wise convolution, it is still not efficient for EfficientNet because the workload imbalance between two types of convolutional engines causes inevitable idling. To overcome this problem, we present a lightweight reconfigurable computational kernel based on FPGA with an exchangeable-track datapath scheme. In addition, a low-accuracy-loss function replacement strategy is proposed for swish/sigmoid functions. Furthermore, the low-cost hardware architecture to implement the replaced functions is designed. The proposed accelerator (LETA) can implement EfficientNet on Xilinx XCVU37P with a 300 MHz system clock and a 600 MHz kernel clock. The linear growth of resource usage in the 4-kernel implementation in 1 super logic region (SLR) with the same clock frequencies justifies the scalability of LETA. The experimental results show that LETA can achieve 2× throughput/DSP compared to the latest FPGA-based accelerator with 1.6% (0.7%) top-1 (top-5) accuracy loss on EfficientNet-B3.

In-memory key-value store (IMKVS) has gained great popularity in data centers. However, big data brings great challenges in performance and power consumption because of the general-purpose Von Neumann computer architecture. Remote direct memory access (RDMA) technology supporting zero-copy networking could partly alleviate the problem but is still not efficient for KVS. To overcome this problem, we present a flexible and ultra-low-latency IMKVS system named FULL-KV, based on a CPU-FPGA heterogeneous architecture. The FPGA serves as a KVS accelerator that can bypass the CPU and implement both the network stacks and the KVS processing with a highly parallel hardware architecture. The system latency of FULL-KV can achieve as low as 1.5μs/2.2μs for the PUT/GET operation, which is 3.0x/1.5x faster than current state-of-the-art hardware-based KVS systems. Besides, FULL-KV can support 4x larger values (up to 4M bytes). Given a total Ethernet bandwidth of 20Gbps, the peak throughput of the single-node FULL-KV can reach 26.0 million key-value operations per second (Mops). In the two-node test system with a commercial Ethernet switch, the peak throughput can reach 52Mops, manifesting the system scalability and practicability.

End Cutting 1D layout design is a promising candidate for sub-10nm process nodes. Given a 1D layout with horizontal wires, cut redistribution technique is used for sliding the line-end cuts in order to align them vertically or resolve spacing conflicts. The aligned cuts can then be merged into a single shot of cuts. In this paper, we proposed a network flow based method for efficient cut redistribution and insertion. Normally, a pair of movable cuts could have three possible relations, left-of, right-of and merge-into. We observe that if the left-right-merge orderings of cuts are fixed, the cut redistribution can be formulated as a network flow problem, which can be solved efficiently. We also find that inserting cuts can resolve the spacing conflicts in some circumstances. This cut insertion strategy is introduced in our proposed method to reduce the spacing conflicts. Moreover, the complementary e-beam lithography for printing the cuts is also considered in this paper. Experimental results show that compared with a previous ILP-based method, our method can achieve a 200X speedup and competitive solution quality.

The printability problem of chip making becomes challenging in advanced process nodes. At present, various lithography technologies such as multiple patterning (MP), directed self-assembly (DSA), electron beam (e-beam), and their combinations are being considered. In this paper, the corresponding layout decomposition problems for contact/via generation are studied. In particular, we investigate the simultaneous DSA template and e-beam throughput optimization. First, we present an exact method based on an ILP formulation. Then, a graph-based algorithm is developed. The co-optimization problem for DSA double patterning with e-beam is formulated as a minimum hitting set problem. A primal-dual based algorithm is then derived for solving the problem effectively. Experimental results show that compared with a two-stage method, our method can achieve around 20.6% throughput improvement and 18.7% template cost reduction.

Directed self-assembly (DSA) complemented with multiple patterning (MP) is an attractive next generation lithography (NGL) technique for contact-hole generation. Nevertheless, a high-quality DSA-aware layout decomposer is required to enable the technology. In this article, we introduce an efficient method which incorporates a set packing for generating DSA template candidates and a local search method. Besides, a multi-start strategy is integrated into the framework to prevent the local minima. Our framework encourages the reuse of existing coloring solvers. Hence, the development cost can significantly be reduced. In addition, for DSA multiple patterning where the number of masks is larger than two, we present an efficient iterative partition based method. Experimental results show that compared with the state-of-the-art work, our methods can achieve roughly 100× speedup for double patterning, and 78.8% conflict reduction with 5× speedup for triple patterning on the dense graphs.

As the feature size keeps scaling down and the circuit complexity increases rapidly, a more advanced hybrid lithography, which combines multiple patterning and electron-beam lithography (EBL), is promising to further enhance the pattern resolution. In this paper, we formulate the layout decomposition problem for this hybrid lithography as a minimum vertex deletion${K}$-partition problem, where${K}$is the number of masks in multiple patterning. Stitch minimization and EBL throughput are considered uniformly by adding a virtual vertex between two feature vertices for each stitch candidate during the conflict graph construction phase. For${K} {=} 2$, we propose a primal-dual (PD) method for solving the underlying minimum odd-cycle cover problem efficiently. In addition, a chain decomposition algorithm is employed for removing all “noncyclable” edges. Furthermore, we investigate two versions of the PD method, one with planarization and one without. For${K} {>} 2$, we propose a random-initialized local search method that iteratively applies the PD solver. Experimental results show that compared with a two-stage method, our proposed methods reduce the EBL usage by 65.5% with double patterning and 38.7% with triple patterning on average for the benchmarks.

As the feature size keeps scaling down and the circuit complexity increases rapidly, a more advanced hybrid lithography, which combines multiple patterning and e-beam lithography (EBL), is promising to further enhance the pattern resolution. In this paper, we formulate the layout decomposition problem for this hybrid lithography as a minimum vertex deletion K-partition problem, where K is the number of masks in multiple patterning. Stitch minimization and EBL throughput are considered uniformly by adding a virtual vertex between two feature vertices for each stitch candidate during the conflict graph construction phase. For K = 2, we propose a primal-dual method for solving the underlying minimum odd-cycle cover problem efficiently. In addition, a chain decomposition algorithm is employed for removing all “non-cyclable” edges. For K > 2, we propose a random-initialized local search method that iteratively applies the primal-dual solver. Experimental results show that compared with a two-stage method, our proposed methods reduce the EBL usage by 64.4% with double patterning and 38.7% with triple patterning on average for the benchmarks.

In this article we present a pairwise coloring (PWC) approach to tackle the layout decomposition problem for triple patterning lithography (TPL). The main idea is to reduce the problem to a set of bi-coloring problems. The overall solution is refined by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this method is that the existing double patterning lithography (DPL) techniques can be reused effortlessly. Moreover, we observe that each pass can be fulfilled efficiently by integrating an SPQR-tree-graph-division-based bi-coloring method. In addition, to prevent the solution getting stuck in the local minima, an adaptive multi-start (AMS) approach is incorporated. Adaptive starting points are generated according to the vote of previous solutions. The experimental results show that our method is competitive with other works on both solution quality and runtime performance.

While double patterning lithography (DPL) is still in active development, triple or even quadruple patterning has recently been proposed for the next technology node. In this paper, we propose a pairwise coloring (PWC) method to tackle the layout decomposition problem for general multiple patterning lithography (MPL). The main idea is to reduce the problem to sets of concurrent bi-coloring problems. The overall solution is refined iteratively by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this approach is that the existing DPL techniques can be reused seamlessly. Any improvement of them can directly benefit to the MPL counterpart. Moreover, we observe that with the help of the SPQR-tree graph division method, each pass can be fulfilled in nearly linear time. In addition, to prevent the solution getting stuck in the local minima, a randomized initialization strategy is incorporated. The PWC method is executed certain number of times with different randomized initial solutions, out of which the best solution is selected as output. We have implemented our method for particular triple patterning lithography (TPL). The experimental results show that compared with two recently published methods for TPL, our method can reduce the number of conflicts up to 33.2% and 44.9% respectively.

Conventional clock skew scheduling for sequential circuits can be formulated as a minimum cycle ratio (MCR) problem, and hence can be solved effectively by methods such as Howard's algorithm. However, its application is practically limited due to the difficulties in reliably implementing a large set of arbitrary dedicated clock delays for the flip-flops. Multi-domain clock skew scheduling was proposed to tackle this impracticality by constraining the total number of clock delays. Even though this problem can be formulated as a mixed integer linear programming (MILP), it is expensive to solve optimally in general. In this paper, we show that, under mild restrictions, the underlying domain assignment problem can be formulated as a special MILP that can be solved effectively using similar techniques for the MCR problem. In particular, we design a generalized Howard's algorithm for solving this problem efficiently. We also develop a critical-cycle-oriented refinement algorithm to further improve the results. The experimental results on ISCAS89 benchmarks show both the accuracy and efficiency of our algorithm. For example, only 4.3% of the tests have larger than 1% degradation (3% in the worst case), and all the tests finish in less than 0.7 seconds on a laptop with a 2.1GHz processor.

Double patterning lithography is the most likely solution for 32nm and below process nodes due to its cost effectiveness. To enable this technique, layout decomposition is applied to split a layout into two non-conflicting patterns. Nevertheless, this problem is NP-hard in general, especially for layouts with random logic. Thus, high quality results are hard to be achieved in reasonable time. Previously, several graph partitioning techniques have been presented in order to speed up the process, with the tradeoff of the quality of results (QoR). We propose a graph division method that does not have this deficiency. First, we start with a conflict graph derived from a layout. Based on a data structure named SPQR-tree, the graph is divided into its triconnected components in linear time. The solutions of these components are then combined in a way that no QoR is lost. Thus, we call this method a ”lossless” method. Experimental results show that the proposed method can achieve 5X speedup without sacrificing any QoR.

In nanometer technologies, process variations possess growing nonlinear impacts on circuit performance, which causes critical path delays of combinatorial circuits variate randomly with non-Gaussian distribution. In this paper, we propose a novel clock skew scheduling methodology that optimizes timing yield by handling non-Gaussian distributions of critical path delays. Firstly a general formulation of the optimization problem is proposed, which covers most of the previous formulations and indicates their limitations with statistical interpretations. Then a generalized minimum balancing algorithm is proposed for effectively solving the skew scheduling problem. Experimental results show that the proposed method significantly outperforms some representative methods previously proposed for yield optimization, and could obtain timing yield improvements up to 33.6% and averagely 17.7%.

Analog circuit sizing under process/parameter variations is formulated as a mini-max geometric programming problem. To tackle such problem, we present a new method that combines the ellipsoid method and affine arithmetic. Affine arithmetic is not only used for keeping tracks of variations and correlations, but also helps to determine the sub-gradient at each iteration of the ellipsoid method. An example of designing a CMOS operational amplifier is given to demonstrate the effectiveness of the proposed method. Finally numerical results are verified by SPICE simulation.

The increasing effort on full-chip validation constrains design cost and time-to-market. A waveform comparison tool named WCOMP is presented to automate mixed-signal validation regression in memory design. Unlike digital waveform comparison tools, WCOMP compares mixed-signal waveforms for functional match instead of graphical match, which tally with the requirements of full-chip validation regression. Simulations with different regression runs, process parameters, voltages and temperatures can be functionally compared. The methods are proved to be effective in Intelreg Flash memory design.

Two novel suboptimal algorithms for mutual exclusion in distributed systems are presented. One is based on the modification of Maekawa's (1985) grid based quorum scheme. The size of quorums is approximately /spl radic/2/spl radic/N where N is the number of sites in a network, as compared to 2/spl radic/N of the original method. The method is simple and geometrically evident. The second one is based on the idea of difference sets in combinatorial theory. The resulting scheme is very close to optimal in terms of quorum size.