Circuit partitioning is an NP-hard optimization problem that appears frequently throughout the Very Large Scale Integration (VLSI) design flow. This paper aims to investigate the performance of Graph Neural Networks (GNNs) in addressing this key problem. The proposed solution involves using two sequentially applied GNNs. The first GNN clusters the circuit’s graph representation to identify node features, which are then used as node embeddings by the second GNN to effectively partition the circuit. To evaluate the effectiveness of this approach, a direct performance comparison is conducted against the widely-used Sanchis multi-way partitioning heuristic. The empirical results are promising, demonstrating that GNNs achieve significant improvements in both quality of the partitioning and CPU runtime, especially for larger circuits and larger numbers of partitions.

Routing is the most time-consuming stage in the Field Programmable Gate Array (FPGA) design workflow. We propose a parallel routing technology, based on the Pathfinder algorithm, that enhances parallelism by dividing the search into two phases: one that tolerates overlaps and one that does not. Additional performance optimizations include an improved cost schedule, pruning the routing-resource graph, and selecting efficient data structures for modern CPUs. Evaluated using both the 2023 MLCAD and 2024 FPGA Routing Contest benchmarks, our router achieves average speedups of $6.2 \times$ and $5.2 \times$ compared to RWRoute and Vivado 2023.2, respectively.

The Fiduccia-Mattheyses-Sanchis (FMS) algorithm is a widely used local search method for K-way circuit partitioning, but it’s prone to getting stuck in local minima. Traditionally, this has been addressed by running FMS multiple times with different random initial solutions, hoping for a better result. Building on our previous work with an RL-based local search method that helps FMS avoid these traps, this research explores a new approach: using constructive methods to generate superior initial solutions. We explored two such methods: NDE (node growing algorithm), a commonly used node-based method that maximizes node absorption, and NET (net growing algorithm), an edge-based approach that maximizes net absorption. By integrating NDE and NET with our RL-based local search, we’ve achieved significant improvements. Experiments on ISPD98/IBM benchmarks demonstrate that an edge-based approach provides higher-quality solutions for larger circuits and larger numbers of partitions. Combining these initial solutions with our RL-based approach further reduces the cutsize generate by the RL-based approach by up to 79.5%.

Routing is a time-consuming task in the FPGA design flow, and its task is to build non-overlapping routing trees for all nets. PathFinder is a popular routing algorithm, and it is implemented in the versatile-place-and-route (VPR) tool. The latest version of PathFinder, implemented in VPR 8.0, employs incremental routing in which it rip-up and re-route (RnR) only those branches of the routing trees that have a congested node or their delay has degraded significantly in the last iterations. The initial iterations have a very high workload (i.e., the number of branches to route), and the later ones have fewer branches to build. We propose a parallel-sequential hybrid router for PathFinder with incremental routing that applies deterministic parallel routing to a window of initial iterations having a high routing workload and sequential routing to the remaining iterations. It also uses an intelligent approach to select nets for sequential and parallel routing. Experiments conducted using Titan benchmarks show that it can improve the runtime of PathFinder by upto 32% with no significant degradation in solution quality.

Detailed Placement (DP) is an important, but time-consuming, optimization step within the Field Programmable Gate Array (FPGA) design flow. Given a global placement, DP seeks to refine the global placement to improve the success of the subsequent routing step. In this paper, we show how Reinforcement Learning (RL) can be used to significantly reduce DP runtimes while maintaining Quality-of-Result (QoR). We develop 3 different RL models based on Tabular Q-Learning, Deep Q-Learning, and Actor-Critic. These models are evaluated by integrating them into GPlace3.0 – a state-of-the-art analytic FPGA placement tool – and tested using the 12 ISPD contest benchmarks. Our results show the models achieve total runtime improvements between 2x to 3.5x and similar QoR compared to GPlace3.0’s algorithmic-based detailed placer.

The ability to accurately and efficiently estimate the routability of a circuit based on its placement is one of the most challenging and difficult tasks in the Field Programmable Gate Array (FPGA) flow. In this article, we present a novel, deep learning framework based on a Convolutional Neural Network (CNN) model for predicting the routability of a placement. Since the performance of the CNN model is strongly dependent on the hyper-parameters selected for the model, we perform an exhaustive parameter tuning that significantly improves the model’s performance and we also avoid overfitting the model. We also incorporate the deep learning model into a state-of-the-art placement tool and show how the model can be used to (1) avoid costly, but futile, place-and-route iterations, and (2) improve the placer’s ability to produce routable placements for hard-to-route circuits using feedback based on routability estimates generated by the proposed model. The model is trained and evaluated using over 26K placement images derived from 372 benchmarks supplied by Xilinx Inc. We also explore several opportunities to further improve the reliability of the predictions made by the proposed DLRoute technique by splitting the model into two separate deep learning models for (a) global and (b) detailed placement during the optimization process. Experimental results show that the proposed framework achieves a routability prediction accuracy of 97% while exhibiting runtimes of only a few milliseconds.

The ability to quickly and accurately predict congestion has emerged as one of the most critical problems during placement. In this paper, we present DLCong, a deep learning congestion-estimation framework based on a convolutional encoder-decoder. Experimental results show that compared to MLCong, a state-of-the-art machine-learning based congestion-estimation model, DLCong achieves an almost 9% improvement in congestion accuracy, while exhibiting inference times of a few milliseconds. Moreover, the accuracy of DLCong scales better with increasing congestion compared to MLCong.

Placement for Field Programmable Gate Arrays (FPGAs) is one of the most important but time-consuming steps for achieving design closure. This article proposes the integration of three unique machine learning models into the state-of-the-art analytic placement tool GPlace3.0 with the aim of significantly reducing placement runtimes. The first model, MLCong, is based on linear regression and replaces the computationally expensive global router currently used in GPlace3.0 to estimate switch-level congestion. The second model, DLManage, is a convolutional encoder-decoder that uses heat maps based on the switch-level congestion estimates produced by MLCong to dynamically determine the amount of inflation to apply to each switch to resolve congestion. The third model, DLRoute, is a convolutional neural network that uses the previous heat maps to predict whether or not a placement solution is routable. Once a placement solution is determined to be routable, further optimization may be avoided, leading to improved runtimes. Experimental results obtained using 372 benchmarks provided by Xilinx Inc. show that when all three models are integrated into GPlace3.0, placement runtimes decrease by an average of 48%.

In this paper, we propose a novel, flat analytic timing-driven placer without explicit packing for Xilinx UltraScale FPGA devices. Our work uses novel methods to simultaneously optimize for timing, wirelength and congestion throughout the global and detailed placement stages. We evaluate the effectiveness of the flat placer on the ISPD 2016 benchmark suite for the xcvu095 UltraScale device, as well as on industrial benchmarks. Experimental results show that on average, FTPlace achieves an 8% increase in maximum clock rate, an 18% decrease in routed wirelength, and produces placements that require 80% less time to route when compared to Xilinx Vivado 2018.1.

The ability to accurately and efficiently estimate the routability of a circuit based on its placement is one of the most challenging and difficult tasks in the Field Programmable Gate Array (FPGA) flow. In this paper, we present a novel, deep-learning framework based on a Convolutional Neural Network model for predicting the routability of a placement. We also incorporate the deep-learning model into a state-of-the-art placement tool, and show how the model can be used to (1) avoid costly, but futile, place-and-route iterations, and (2) improve the placer's ability to produce routable placements for hard-to-route circuits using feedback based on routability estimates generated by the proposed model. The model is trained and evaluated using over 26K placement images derived from 372 benchmarks supplied by Xilinx Inc. Experimental results show that the proposed framework achieves a routability prediction accuracy of 97%, while exhibiting runtimes of only a few milliseconds.

Effectively estimating and managing congestion during placement can save substantial placement and routing runtime. In this article, we present a machine-learning model for accurately and efficiently estimating congestion during FPGA placement. Compared with the state-of-the-art machine-learning congestion-estimation model, our results show a 25% improvement in prediction accuracy. This makes our model competitive with congestion estimates produced using a global router. However, our model runs, on average, 291× faster than the global router. Overall, we are able to reduce placement runtimes by 17% and router runtimes by 19%. An additional machine-learning model is also presented that uses the output of the first congestion-estimation model to determine whether or not a placement is routable. This second model has an accuracy in the range of 93% to 98%, depending on the classification algorithm used to implement the learning model, and runtimes of a few milliseconds, thus making it suitable for inclusion in any placer with no worry of additional computational overhead.

Avoiding congestion for routing resources has become one of the most important placement objectives. In this paper, we present a machine-learning model for accurately and efficiently estimating congestion during FPGA placement. Compared with the state-of-the-art machine-learning congestion-estimation model, our results show a 25% improvement in prediction accuracy. This makes our model competitive with congestion estimates produced using a global router. However, our model runs, on average, 291x faster than the global router.

Typically, the overall performance of a university professor is assessed based on three criteria: teaching, research and service. The teaching component is based on students' ratings and comments. However, comments and ratings are highly subjective, thus making the assessment difficult, especially given conscious and unconscious bias. RateMyProfessor.com is a popular publicly accessible website where students rate professors. We use this large corpus to evaluate bias and answer the following questions: 1) what words do students use to describe their professors? 2) is there any correlation between the words used and the rating given? and, 3) are there significant differences across gender and discipline? To answer these questions, we model the reviews using Latent Dirichlet Allocation (LDA) to automatically identify topics and we run several regression models to analyze if there are statistically significant factors that influence the overall rating.

Optimizing for routability during FPGA placement is becoming increasingly important, as failure to spread and resolve congestion hotspots throughout the chip, especially in the case of large designs, may result in placements that either cannot be routed or that require the router to work excessively hard to obtain success. In this article, we introduce a new, analytic routability-aware placement algorithm for Xilinx UltraScale FPGA architectures. The proposed algorithm, called GPlace3.0, seeks to optimize both wirelength and routability. Our work contains several unique features including a novel window-based procedure for satisfying legality constraints in lieu of packing, an accurate congestion estimation method based on modifications to the pathfinder global router, and a novel detailed placement algorithm that optimizes both wirelength and external pin count. Experimental results show that compared to the top three winners at the recent ISPD’16 FPGA placement contest, GPlace3.0 is able to achieve (on average) a 7.53%, 15.15%, and 33.50% reduction in routed wirelength, respectively, while requiring less overall runtime. As well, an additional 360 benchmarks were provided directly from Xilinx Inc. These benchmarks were used to compare GPlace3.0 to the most recently improved versions of the first- and second-place contest winners. Subsequent experimental results show that GPlace3.0 is able to outperform the improved placers in a variety of areas including number of best solutions found, fewest number of benchmarks that cannot be routed, runtime required to perform placement, and runtime required to perform routing.

Traditional FPGA flows that wait until the routing stage to tackle congestion are quickly becoming less effective. This is due to the increasing size and complexity of FPGA architectures and the designs targeted for them. In this paper, we present two new congestion-aware placement tools for Xilinx UltraScale architectures, called GPlace-pack and GPlace-flat, respectively. The former placer participated in the ISPD 2016 Routability-driven Placement Contest for FPGAs, and finished in third place overall. The latter placer was subseqently developed based on our experience in the contest with GPlace-pack. Results obtained indicate that GPlace-flat is on average 5.3× faster than GPlace-pack. The post routing results show that GPlace-flat is able to obtain a further 22.5% improvement in wirelength and a 40.0% improvement in runtime compared to GPlace-pack.

In this paper, we analyze the gender wage gap in Ontario?s public sector. Our analysis is based on the salaries of high earners in the public sector. Although these salaries are publicly available from Ontario?s Sunshine List, a key attribute is missing from the public data, the gender variable. We propose a 2-stage model to predict the gender based on the person?s first name, and we augment the data with the new variable. With the new database created, we analyze, present and discuss results for the gender wage gap in Ontario. The findings of this research are being used by Ontario?s provincial government to reassess and change current policies for pay equity.

Web site privacy policies are often long, difficult to understand, and contain incomplete information. Consequently, users tend not to read the privacy policies, thus putting their privacy at risk. This paper describes an automated approach for assisting users to evaluate online privacy policies based on completeness. The term completeness refers to the presence of 8 sections in an online privacy policy that have been recognized as helpful in establishing the transparency of a privacy policy. Given a new online privacy policy, the proposed system employs a machine-learning based approach to predict a completeness score for the privacy policy. This score can then be used by the user to assess the risk to their privacy.

Placement and routing run-times continue to dominate the automated FPGA design flow. As the size of FPGA architectures continue to grow exponentially, it remains critical to develop parallel tools for FPGA design where the amount of exposed concurrent work scales with the size of the designs to be synthesized. In this paper, we propose a novel algorithm for parallel placement, based on simulated annealing, where the amount of parallel work directly scales with the size of the net-list to be placed. Our approach concurrently evaluates and conditionally applies very large sets of non-conflicting swaps using common parallel computing primitives, including stream compaction, category reduction, and sort. While our design is suitable for targeting all modern parallel computing platforms, we present results from our implementation which targets NVIDIA's CUDA platform, where we achieve a mean speed-up of 19x over VPR with post-routing critical-path-delay and wire-length quality that matches or exceeds VPR. We believe that this work is an important step towards the development of a scalable, high-quality placement tool.

Placement run-times continue to dominate the FPGA design flow. Previous attempts at parallel placement methods either only scale to a few threads or result in a significant loss in solution quality as thread-count is increased. We propose a novel method for generating large amounts of parallel work for placement, which scales with the size of the target architecture. Our experimental results show that we nearly reach the limit of the number of possible parallel swaps, while improving critical-path-delay 4.7% compared to VPR. While our proposed implementation currently utilizes a single thread, we still achieve speedups of 13.3x over VPR.

When the genetic algorithm recombines two parent genotypes, the differences between them define a genotypic subspace, and any offspring produced should be confined to this subspace. Although this might seem insignificant, those recombination (or crossover) operators that violate this principle can direct a search away from the region (in genotypic space) that contains the two parent genotypes. This is contrary to the task for which the recombination operator was originally developed and can be detrimental, so this paper introduces a visualization that can be used to detect violations of this principle. The methodology also inspired the development of a different approach to recombining permutations, and a brief case study shows that an alternative recombination operator that does not violate this principle can be used to achieve a performance improvement over previous attempts to optimize Field-Programmable Gate-Array placements using a genetic algorithm. We believe that this technique will be invaluable for developing additional recombination operators.

In this paper we present a Dynamic Sampling Framework for use with multi-class imbalanced data containing any number of classes. The framework makes use of existing sampling techniques such as RUS, ROS, and SMOTE and ties the classification algorithm into the sampling process in a wrapper like manner. In doing so the framework is able to search for a desirably sampled training set, thus eliminating the need to specify a target distribution and automatically tuning the training set distribution to the classification algorithm's learning preferences. This is important when re-sampling multi-class data where manually searching for an appropriate target distribution would be a daunting task. We test both our Dynamic Sampling approach and traditional Static Sampling using RUS, ROS, SMOTE, ROS+RUS, and SMOTE+RUS with several classification algorithms on a four class, highly imbalanced data set. We compare the results of Static Sampling and Dynamic Sampling and find that overall both techniques are able to raise Recall for the highest minority classes, but Dynamic Sampling is also able to maintain or raise Recall for the majority classes. Also, Dynamic Sampling is overall more robust and resilient, and is better able to sustain classifier Accuracy and to raise G-Mean and Minimum F-Measures.

In this paper we propose a Sequential Ensemble Classification (SEC) technique which is designed to tackle the problem of learning from a data set with an extremely unbalanced distribution of instances among the classes. This system employs a specific decomposition technique that reduces the degree of unbalance in the data by transforming multi-class problem into a sequence of binary class problems. We investigate two different implementations of the proposed method, one based on an ensemble of homogeneous classifiers and a second based on a heterogeneous ensemble of classifiers. A real-world medical data set has been chosen as a case study for the investigation of the proposed method. The data is highly unbalanced, consists of a wide range of class values, some of which contain only a few instances, and which is voluminous. Our experimental results show that both schemes of the SEC system are able to outperform standalone classifiers, with the highest performance being achieved by the homogeneous design of the system.

Scatter Search [1] is an effective and established population-based meta-heuristic that has been used to solve a variety of hard optimization problems. However, like most population-based meta-heuristics, the time required to find high-quality solutions can become prohibitive as problem sizes grow. In this paper, we present a hardware implementation of scatter search on a Field-Programmable Gate-Array (FPGA). Our objective is to improve the runtime of scatter search by exploiting the potentially massive performance benefits that are available through the native parallelism in hardware. When implementing scatter search we employ Handel-C [2] - a programming language specifically designed to enable software developers to easily synthesize C-like programs into synchronous hardware. As far as we know, this is the first time that scatter search has been implemented in hardware (of any form). Our empirical results show that by effectively exploiting data parallelism and pipelining a 28x speedup over software can be achieved.

The Pilot library is a new method for programming MPI-enabled clusters in C, targeted at novice parallel programmers. Formal elements from Communicating Sequential Processes (CSP) are used to realize a process/channel model of parallel computation that reduces opportunities for deadlock and other communication errors. This simple model, plus an application programming inter-face (API) styled after C's formatted I/O, are designed to make the library easy to learn. The Pilot library exists as a thin layer on top of any standard Message Passing Interface (MPI) implementation, preserving MPI's portability and efficiency, with little per-formance overhead arising as result of Pilot's additional features.

Global routing of macro cells remains an important but time-consuming step in the VLSI design cycle. Macro cells are large, irregularly sized parameterized circuit modules that typically contain large numbers of terminals that must be interconnected. The interconnection pattern for each set of terminals (net) that must be connected is a Steiner tree, and the primary sub-problem in the global routing of macro cells is to find a set of dissimilar, low-cost Steiner trees for each net that must be routed. In this paper, a two-phase, parallel (multi-processor) algorithm is proposed for quickly constructing a diverse pool of high-quality Steiner trees for routing of multi-terminal nets. In the first phase, a single Steiner tree is constructed using a heuristic, called Shrubbery. Then, in the second phase, a pool of dissimilar, high-quality trees are created from the original tree, by running multiple instances of a local search in parallel. Computational experiments performed on over 800 commonly used benchmarks show that running multiple instances of the local search in parallel results in near-linear speed-up over the serial case. Most importantly, the trees produced are both high-quality and dissimilar, allowing for numerous routing possibilities for each net.

To increase memory bandwidth, many programmable Digital Signal Processors (DSPs) employ two on-chip data memories. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to occur in parallel. Exploiting dual memory banks, however, is a challenging problem for compilers. This, in part, is due to the instruction-level parallelism, small numbers of registers, and highly specialized register capabilities of most DSPs. In this paper, we present a new methodology based on a genetic algorithm for assigning data to dual-bank memories. Our approach is global, and integrates several important issues in memory assignment within a single model. Special effort is made to identify those data objects that could potentially benefit from an assignment to a specific memory, or perhaps duplication in both memories. Our computational results show that the GA is able to achieve a 54% reduction in the number of memory cycles and a reduction in the range of 7% to 42% in the total number of cycles when tested with well-known DSP kernels and applications.

To increase memory bandwidth, many programmable Digital-Signal Processors (DSPs) employ two on-chip data memories. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to occur in parallel. Exploiting dual memory banks, however, is a challenging problem for compilers. This, in part, is due to the instruction-level parallelism, small numbers of registers, and highly specialized register capabilities of most DSPs. In this paper, we present a new methodology based on a Memetic Algorithm (MA) for assigning data to dual-bank memories. Our approach is global, and integrates several important issues in memory assignment within a single model. Special effort is made to identify those data objects that could potentially benefit from an assignment to a specific memory, or perhaps duplication in both memories. Our computational results show that the MA is able to achieve a 54% reduction in the number of memory cycles and a reduction in the range of 7%–42% in the total number of cycles when tested with well-known DSP kernels and applications. Our computational results also show that, when compared with the Genetic Algorithm in Ref. 3, the memetic algorithm is able to find solutions that, on average, have 7%–20% less cost, with the biggest improvements being found for larger problem instances.

This paper presents a novel approach to the concurrent solution of three high-level synthesis (HLS) problems and solves them in an integrated manner using hierarchical genetic algorithm (HGA). We focus on the core problems of HLS: scheduling, allocation, and binding. Scheduling consists of assigning of operations in an data-flow graph (DFG) to control steps or clock cycles. Allocation selects specific numbers and types of functional units from a hardware library to perform the operations specified in the DFG. Binding assigns constituent operations of the DFG to specific unit instances. A very general version of the problem is considered where functional units may perform different numbers of control steps. The HLS problems are solved by applying two genetic algorithms in a hierarchical manner. The first performs allocation, while the second performs scheduling and binding and serves as the fitness functions for the first. When compared to other, well-known techniques, our results show a reduction in time to obtain optimal solutions for standard benchmarks.

Generating high quality code for embedded processors is made difficult by irregular architectures and highly encoded parallel instructions. Rather than dealing with the target machine at every stage of the compilation, a promising new methodology employs generic algorithms to optimize code for an idealized abstraction of the true target machine. This code, called reference code, is then mapped to the real instruction set by enhanced genetic algorithms. One perturbs the original schedule to find a number of alternative (parallel) instruction sequences, and the other evolves feasible register assignments, if possible, for each sequence. This paper describes the strategy for mapping idealized code into actual code. The COGEN(T) system employs this methodology to produce good code for different commercial DSPs and ASIPs.

Generating high quality code for embedded processors is made difficult by irregular architectures and highly encoded parallel instructions. Rather than deal with the target machine at every stage of the compilation, a promising new methodology employs generic algorithms to optimize code for an idealized abstraction of the true target machine. This code, called reference code, is then mapped to the real instruction set by enhanced genetic algorithms. One perturbs the original schedule to find a number of alternative (parallel) instruction sequences, and the other evolves feasible register assignments, if possible, for each sequence. This paper describes the strategy for mapping idealized code into actual code. The COGEN(T) system employs this methodology to produce good code for different commercial DSPs and ASIPs.

This paper presents a novel approach to the concurrent solution of three High-Level Synthesis (HLS) problems that are modeled as a Constraint-Satisfaction Problem (CSP) and solved using an Enhanced Genetic Algorithm (EGA). We focus on the core problems of high-level synthesis: Scheduling, Allocation, and Binding. Scheduling consists of assigning of operations in a Data-Flow Graph (DFG) to control steps or clock cycles. Allocation selects specific numbers and types of functional units from a hardware library to perform the operations specified in the DFG. Binding assigns constituent operations of the DFG to specific unit instances. A very general version of this problem is considered where functional units may perform different operations in different numbers of control steps. The EGA is designed to solve CSPs quickly and does not require a user to specify appropriate mutation and crossover rates a priori; these are determined automatically during the course of the genetic search. The enhancements include a directed mutation operator and a new type of elitism that avoids premature convergence. The HLS problems are solved by applying two EGAs in a hierarchical manner. The first performs allocation, while the second performs scheduling and binding and serves as the fitness function for the second. When compared to other, well-known techniques, our results show a reduction in time to obtain optimal solutions for standard benchmarks.

This paper addresses the problem of minimizing mode setting instructions for embedded DSPs. Many such processors use a state register to control the mode of ALU operations (e.g., sign extension, round, and shift). Often two or more modes can be changed by a single instruction. A method is given to determine the minimum number of instructions needed to properly set modes, assuming a schedule has been determined. Our approach models the problem as a minimum cover, and is not limited to a basic block. Block frequency information is exploited to encourage mode changes in less frequently executed blocks whenever possible. Special attention is given to the proper optimization of loops.

Presents a novel approach to the high-level synthesis problems of scheduling, allocation, and binding for multiblock behavioral descriptions. Our design tool, JOSHUA, uses an integer linear programming (ILP) formulation to solve the three interdependent subproblems simultaneously and optimally. The system allows the designer to minimize time, area, and the number of microwords for the entire design, or for specific segments of the design. A diverse module library provides a selection of modules that can perform a specific operation in differing amounts of time (control steps). A novel feature is the ability to select an implementation for part of an algorithm from among a set of implementation alternatives. The system can also handle the issues of path frequencies, loops, parallel threads of execution, and register allocation.>