High-Level Synthesis (HLS) has transformed the development of complex hardware IPs (HWIPs) by enabling abstraction and configurability through languages such as SystemC and C/C++, particularly for FPGA-based high-performance and cloud computing applications. HLS streamlines design space exploration and functional verification. It allows efficient IP synthesis across various FPGA platforms. However, it also introduces security risks, such as hidden circuitry and hardware Trojans being embedded by untrusted third-party vendors. These threats can lead to data leaks, functionality disruptions, and hardware damage. The risks are particularly concerning in cloud environments with multi-tenant architectures, where multiple FPGA-based IPs operate on shared infrastructure. Detecting such threats before synthesis requires robust security validation frameworks. This work presents GreyConE+ , an advanced security testing framework for FPGA-based HLS IPs, designed to detect rare-trigger vulnerabilities that often evade conventional verification methods. By integrating selective instrumentation, greybox fuzzing, and concolic execution, GreyConE+ enhances test generation and efficiently uncovers hidden Trojans and functional anomalies. Evaluations on diverse HLS benchmarks, including SystemC and ML-based C++ designs, demonstrate higher coverage, faster Trojan detection, reduced memory overhead, and lower testing costs compared to existing techniques, reinforcing its effectiveness in securing FPGA-based HLS designs.

Error syndromes for heavy hexagonal code and other topological codes such as surface code have typically been decoded by using Minimum Weight Perfect Matching– (MWPM) based methods. Recent advances have shown that topological codes can be efficiently decoded by deploying machine learning (ML) techniques, in particular with neural networks. In this work, we first propose an ML-based decoder for heavy hexagonal code and establish its efficiency in terms of the values of threshold and pseudo-threshold for various noise models. We show that the proposed ML-based decoding method achieves ~ 5 × higher values of threshold than that for MWPM. Next, exploiting the property of subsystem codes, we define gauge equivalence for heavy hexagonal code, by which two distinct errors can belong to the same error class. A linear search-based method is proposed for determining the equivalent error classes. This provides a quadratic reduction in the number of error classes to be considered for both bit flip and phase flip errors and thus a further improvement of ~ 14% in the threshold over the basic ML decoder. Last, a novel technique based on rank to determine the equivalent error classes is presented, which is empirically faster than the one based on linear search.

Memristors have recently shown significant promise in designing memory and logic subsystems. A 2D-crossbar architecture built with memristor arrays provides a convenient platform for storing multivalued memory states by utilizing the analog variation of current-induced resistance through these cells. The integration of CMOS components with non-CMOS memristor cells further enhances the scope of their applications to various complex system designs. However, present-day memristors by virtue of their inherent structure are prone to various manufacturing defects and sensitive to operational modalities. Existing techniques for testing memristor arrays are either ad hoc in nature or suited for application-specific designs with little concern for optimizing test time. In this work, we envisage a 2-D memristor crossbar as a network and identify certain paths that are suitable for fault sensitization. For full-size square and rectangular memristive crossbars, the proposed method optimizes test time using a path-based technique guided by maximum matching in bipartite graphs. An integer linear programming (ILP) formulation is then used to solve the problem for a general crossbar, either full or incomplete. Simulation results with LTspice demonstrate the effectiveness and superiority of the method to the prior art in terms of test time and fault coverage.

Exhaustive testing of high-level designs poses an arduous challenge due to complex branching conditions, loop structures, and the inherent concurrency of hardware designs. Test engineers aim to generate quality test cases satisfying various code coverage metrics to ensure minimal presence of bugs in a design. Prior works in testing SystemC designs are time inefficient which obstructs achieving the desired coverage in a shorter time-span. We interleave greybox fuzzing and concolic execution in a systematic manner and generate quality test cases for accelerating test coverage metrics. Our results outperform state-of-the-art methods in terms of number of test cases and branch-coverage for some of the benchmarks, and runtime for most of them.

Next-Generation Lithography techniques such as Electron Beam Lithography (EBL), Multiple E-Beam Lithography (MEBL), and Extreme Ultraviolet Lithography (EUVL), overcome the limitations of 193 nm immersion lithography. In MEBL, the layout is split into vertical stripes, with the stripe boundaries termed stitch-lines, and thousands or even millions of electron beams (e-beams) are used in parallel for good throughput. Patterns in different stripes are written either by distinct e-beams or in different passes. Hence, patterns cut by stitch-lines suffer from overlay error and thereby severe pattern distortions, particularly Via, Vertical Routing, and Short Polygon violations near the stitch-lines. In this paper, we propose a Stitch-avoiding Detailed Router that reduces these violations. It is integrated with (i) a traditional global router, and (ii) a Stitch-avoiding Global Router. Experimental results for these two routing flows are compared with those of a baseline flow comprising a traditional global router followed by a traditional detailed router. Significant reductions in stitch-line violations are obtained, especially for the second routing flow, compared to the baseline flow.

Quantum computing has become a promising computing approach because of its capability to solve certain problems, exponentially faster than classical computers. A n -qubit quantum system is capable of providing 2 n computational space to a quantum algorithm. However, quantum computers are prone to errors. Quantum circuits that can reliably run on today’s Noisy Intermediate-Scale Quantum (NISQ) devices are not only limited by their qubit counts but also by their noisy gate operations. In this article, we have introduced i -QER, a scalable machine learning-based approach to evaluate errors in a quantum circuit and reduce these without using any additional quantum resources. The i -QER predicts possible errors in a given quantum circuit using supervised learning models. If the predicted error is above a pre-specified threshold, it cuts the large quantum circuit into two smaller sub-circuits using an error-influenced fragmentation strategy for the first time to the best of our knowledge. The proposed fragmentation process is iterated until the predicted error reaches below the threshold for each sub-circuit. The sub-circuits are then executed on a quantum device. Classical reconstruction of the outputs obtained from the sub-circuits can generate the output of the complete circuit. Thus, i -QER also provides classical control over a scalable hybrid computing approach, which is a combination of quantum and classical computers. The i -QER tool is available at https://github.com/SaikatBasu90/i-QER .

Dynamic partial reconfiguration (DPR) enabled FPGA-based Cloud architecture acts as a flexible and efficient shared environment to facilitates application support to users’ request at low cost. While on one hand we need to handle a variety of tasks, such as periodic or sporadic, deadline or non-deadline, high or low critical tasks from the point of producing correct results, on the other hand we are constrained to use untrusted FPGA-based application IP blocks procured from various third-party vendors, which may contain hardware Trojan horse (HTH) affecting throughput and reliability of the Cloud. We propose Trojan-aware processing of tasks by monitored execution of a task on different untrusted cores, and then one more execution is done upon detection of hardware Trojan effects. For this stringent scheduling environment, the proposed dynamic scheduling algorithm is also properly extended to guarantee successful recovery from Trojan effects for all accepted tasks. Experimental results show that our algorithm improves worst-case-response-time for all tasks including non-deadline tasks and achieves lower task rejection rate for the deadline tasks, through judicious non-uniform partitioning of FPGAs based on supported jobs and subsequent better resource utilization, compared to that for existing Trojan-aware scheduling techniques.

Large-scale quantum computers mandate error correction and fault tolerance. Due to constraints on the number of qubits, fault tolerance is difficult to achieve in near-term quantum systems. Therefore, error correction should require minimal resources. Gates in the near-term devices are also noisy. Quantum error correction code blocks built with these noisy gates can inject further error in the circuit. The goals for error correction in near-term systems are as follows: (i) using a small number of qubits for encoding, and (ii) keeping cost of circuits for encoding and decoding low. In this paper, we propose two techniques to achieve these mutually orthogonal goals. For a binary quantum system we propose an error estimation method that can aid in reducing the number of error correcting blocks via sparse scheduling. For ternary quantum systems, we propose an approximate code that can correct errors with high probability while significantly reducing the circuit cost. These techniques are expected to be helpful for error mitigation in near-term systems in the absence of fault tolerance.

Magnetic resonance imaging (MRI) is a very effective method for identifying any abnormality in the structure and physiology of the spine. However, MRI is time consuming as well as costly. In this work, the authors propose an algorithm which can reduce the time of MRI and thus the cost, with minimal compromise on accuracy. They reconstruct a three‐dimensional (3D) image of the spine from a sequence of 2D MRI slices along any one axis with reasonable slice gap. In order to preserve the image at the edges properly, they regenerate the 3D image by using a combination of bicubic and bilinear interpolation along the orthogonal axis. From the reconstructed 3D, they use a simple geometric method to slice out any possible location along any axis and get the information in that region. They have tested their algorithm on real data, and found that their algorithm reduces the time by 80%, with high internal data preservation accuracy of about 96%.

Most of the Automatic Test Pattern Generation (ATPG) algorithms for digital circuits rely heavily on netlist description that comprises both network interconnect structure among logic gates and the functionality of each gate. The performance of an ATPG tool on a circuit-under-test (CUT) C is determined by the size of the test set T and its fault coverage (FC). Despite extensive research in the field of testing, the following question remains unanswered: Is the structure or the functionality of C dominant in determining FC of a test-set T for C? In this paper, we present empirical evidence in favour of the dominance of structure on FC by randomly selecting a logic gate from a synthesized netlist for C, and replacing it by a different type of gate. Our experiments provide an un-intuitive result that F C of a test-set T for C under the single stuck-at fault model remains nearly the same on other sibling circuits that have identical structure as of C but with different gate functionality, provided these have similar extent of fault redundancy. This observation supports the view that feeding structural information alone may suffice to train machine-learning models that are currently being used to expedite different problems of digital circuit testing and diagnosis.

The advent of 3-D IC technology facilitates the fabrication of large electronic circuits on small-area chips ensuring high performance. For a 3-D IC, the problem of placement followed by the assignment of through-silicon vias (TSVs) involves optimizing various design objectives such as intertier wirelength, power density, congestion, and separation between the TSVs. Each of the existing techniques for the placement of TSVs deals only with a subset of these objectives. In this paper, we propose an evolutionary computation approach MO_TSV to handle this multiobjective optimization problem. The operators, parameters, and constituents of the framework of genetic algorithm (GA)-based multiobjective optimization have been designed in a novel way so that, on exploration of a variety of nondominated solutions, the search process converges to a near-optimum solution in reasonable time. Experimental results on ISCAS'85, ISCAS'89, ITC'99, and IBM (ISPD'98) benchmarks yield quality solutions in terms of all the parameters as well as convergence times, which are encouraging.

Soaring distortions for immersion lithography with 193nm wavelength has necessiated the Next Generation Lithography (NGLs) such as Electron Beam Lithography (EBL). While single e-beam lithography suffers from very low throughput, Multiple Electron Beam Lithography (MEBL) improves it by writing with multiple e-beams in parallel, each dedicated to a disjoint region called a vertical stripe. However, layout patterns, in particular routing segments, vias and short polygons crossing over stripe boundary (stitch line) causes severe pattern distortion leading to malfunctioning of the chip. We minimize these stitch unfriendly patterns at post-layout stage based on perturbation of wire segments by formulating it as a maximum matching problem. Experimental results comprise two variants of perturbations of wire segments. Each variant shows significant minimization of stitch unfriendly patterns, thereby making an already optimized design more MEBL friendly without increasing the wirelength.

Most computer systems authenticate users only once at the time of initial login, which can lead to security concerns. Continuous authentication has been explored as an approach for alleviating such concerns. Previous methods for continuous authentication primarily use biometrics, e.g., fingerprint and face recognition, or behaviometrics, e.g., key stroke patterns. We describe CABA, a novel continuous authentication system that is inspired by and leverages the emergence of sensors for pervasive and continuous health monitoring. CABA authenticates users based on their BioAura, an ensemble of biomedical signal streams that can be collected continuously and non-invasively using wearable medical devices. While each such signal may not be highly discriminative by itself, we demonstrate that a collection of such signals, along with robust machine learning, can provide high accuracy levels. We demonstrate the feasibility of CABA through analysis of traces from the MIMIC-II dataset. We propose various applications of CABA, and describe how it can be extended to user identification and adaptive access control authorization. Finally, we discuss possible attacks on the proposed scheme and suggest corresponding countermeasures.

While the role of ternary reversible and quantum computation has been growing, synthesis methodologies for such logic, have been addressed in only a few works. A reversible ternary logic function can be expressed as minterms by using projection operators. In this paper, a novel realization of the projection operators using a minimum number of permutative ternary Muthukrishnan-Stroud (M-S) gates is presented. Next, an efficient method for logic simplification for ternary reversible logic is proposed. This method along with the new construction of projection operators yields significantly lower gate cost of approximately 31% less than that obtained by earlier methodologies, for the synthesis of ternary benchmark circuits.

With growing demand for complex and high density integrated chips (IC), optical lithography with 193 nm immersion technology has become a bottleneck in the chip manufacturing industry. IC fabrication industry is looking forward to next generation lithography methods, for example, Extreme Ultraviolet Lithography (EUVL). While EUVL is capable of printing with a wavelength of 13.5 nm, it suffers from a major drawback called flare, due to the scattering of light on blank surfaces. Large flare and/or its large variation cause critical dimension (CD) violations. In this paper, we propose an Integer Linear Programming based method to mitigate the effects of flare in the post routing step through perturbation of wire segments. Experimental results on a set of synthetic circuits show significant reduction of flare and its standard deviation across the chip surface.

Machine learning is being used in a wide range of application domains to discover patterns in large datasets. Increasingly, the results of machine learning drive critical decisions in applications related to healthcare and biomedicine. Such health-related applications are often sensitive, and thus, any security breach would be catastrophic. Naturally, the integrity of the results computed by machine learning is of great importance. Recent research has shown that some machine-learning algorithms can be compromised by augmenting their training datasets with malicious data, leading to a new class of attacks called poisoning attacks. Hindrance of a diagnosis may have life-threatening consequences and could cause distrust. On the other hand, not only may a false diagnosis prompt users to distrust the machine-learning algorithm and even abandon the entire system but also such a false positive classification may cause patient distress. In this paper, we present a systematic, algorithm-independent approach for mounting poisoning attacks across a wide range of machine-learning algorithms and healthcare datasets. The proposed attack procedure generates input data, which, when added to the training set, can either cause the results of machine learning to have targeted errors (e.g., increase the likelihood of classification into a specific class), or simply introduce arbitrary errors (incorrect classification). These attacks may be applied to both fixed and evolving datasets. They can be applied even when only statistics of the training dataset are available or, in some cases, even without access to the training dataset, although at a lower efficacy. We establish the effectiveness of the proposed attacks using a suite of six machine-learning algorithms and five healthcare datasets. Finally, we present countermeasures against the proposed generic attacks that are based on tracking and detecting deviations in various accuracy metrics, and benchmark their effectiveness.

Quantum circuits consist of a cascade of quantum gates. In a physical design-unaware quantum logic circuit, a gate is assumed to operate on an arbitrary set of quantum bits (qubits), without considering the physical location of the qubits. However, in reality, physical qubits have to be placed on a grid. Each node of the grid represents a qubit. The grid implements the architecture of the quantum computer. A physical constraint often imposed is that quantum gates can only operate on adjacent qubits on the grid. Hence, a communication channel needs to be built if the qubits in the logical circuit are not adjacent. In this paper, we introduce a tool called the physical design-aware fault-tolerant quantum circuit synthesis (PAQCS). It contains two algorithms: one for physical qubit placement and another for routing of communications. With the help of these two algorithms, the overhead of converting a logical to a physical circuit is reduced by 30.1%, on an average, relative to previous work. The optimization algorithms in PAQCS are evaluated on circuits implemented using quantum operations supported by two different quantum physical machine descriptions and three quantum error-correcting codes. They reduce the number of primitive operations by 11.5%-68.6%, and the number of execution cycles by 16.9%-59.4%.

A manufacture-ready layout is vulnerable to misappropriation when it is either fabricated as a chip in a fabrication facility, or reused in a system-on-chip house. We propose an intellectual property protection (IPP) scheme IPP_MRL for protection of manufacture-ready layout against unauthorized reuse and inclusion of Trojans. The IPP_MRL inserts watermarks in the layout according to designer's signature with an effect of tuning the delays at selected scan flip-flops. Certain dummy fills are reoriented in the neighborhood of selected net segments and it causes fine tuning of delay; certain other selected net segments are resized for coarse change in delay. The IPP_MRL not only verifies the watermark in the layout, but also captures its effect as delay fault-induced responses from the packaged chips, fabricated from the watermarked layout, by applying a faster test clock. Due to the controlled effect of watermarking on delay, responses are resilient against process and temperature variation, but capable of detecting hardware Trojan. The method is adaptive to device aging. The results for ISCAS'85 and ISCAS'89 benchmark circuits show that the overhead of watermarking on circuit delay is less than 0.05% and the probability of true false or false true can be at most ~10-6.

In nanometer technology regime, design components mandate their reuse to meet the complex design challenges and hence comprise Intellectual Property (IP). Unauthorized reuse raises major security issues. IP mark(s) is embedded into a design for establishing the veracity of a legal IP owner/buyer. However, methods for trustworthy public verification of IP marks are not secure. For field-programmable gate-array (FPGA) designs, marks become prone to tampering, and even being overridden by an attacker's signature after public verification. In order to ensure trustworthy yet leakage-proof public verification based on the marks hidden in a FPGA design, we propose a zero-knowledge protocol Verify_ZKP. It is an interactive two-person game between the prover and the verifier. This protocol is fast, incurs no additional design overhead, and needs no centralized signature database. We establish that Verify_ZKP satisfies zero-knowledge property, and introduce statistical metrics to measure its robustness. We have simulated our protocol for IWLS'05 FPGA benchmarks. Experimental results on robustness and overhead are very encouraging.

Partial reconfiguration on heterogeneous field-programmable gate arrays with millions of gates yields better utilization of its different types of resources by swapping in and out the appropriate modules of one or more applications at any instant of time. Given a schedule of sub-task instances where each instance is specified as a netlist of active modules, reconfiguration overhead can be reduced by fixing the position and shapes of modules common across all instances. We propose a global floorplan generation method PartialHeteroFP to obtain same positions for the common modules across all instances such that the heterogeneous resource requirements of all modules in each instance are satisfied, and the total half-perimeter wirelength over all instances is minimal. Experimental results establish that the proposed PartialHeteroFP produces floorplans very fast, with 100% match of common modules and thereby minimizing the partial reconfiguration overhead.

Recent field-programmable gate array (FPGA) architectures are heterogeneous, owing to the presence of millions of gates in configurable logic blocks (CLBs), block RAMs, and multiplier blocks (MULs) which can host fairly large designs. While their physical design calls for floorplanning, the traditional algorithms for application-specific integrated circuits (ASIC) do not suffice. In this paper, we propose a three-phase algorithm for unified floorplan-topology generation and sizing on heterogeneous FPGAs. The method consists of a recursive balanced bipartitioning followed by the generation of slicing topologies and finally the allocation of CLBs and RAM/MULs to modules by a greedy heuristic and minimum-cost maximum-flow method, respectively. Experimental results on benchmark circuits show that our method HeteroFloorplan produces feasible floorplans within a few seconds with total half-perimeter wirelength (HPWL) improvement of 18%-52% over the very few previous approaches. We also compare our locally greedy CLB allocation with a network-flow formulation to establish its effectiveness.

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O ( d √log n log log n ) for 1D, that is, linear arrangement and O ( d log n log log n ) for the 2D grid, where d is the maximum degree of hyperedges and n , the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O ( 4 √log n √ kd log log n ), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33× speed-up, on average, with only 1.31× degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee.

This article addresses the problem of recursively bipartitioning a given floorplan F using monotone staircases. At each level of the hierarchy, a monotone staircase from one corner of F to its opposite corner is identified, such that (i) the two parts of the bipartition are nearly equal in area (or in the number of blocks), and (ii) the number of nets crossing the staircase is minimal. The problem of area-balanced bipartitioning is shown to be NP-hard, and a maxflow-based heuristic is proposed. Such a hierarchy may be useful to repeater placement in deep-submicron physical design, and also to global routing.

In this paper, we propose a placement method for island-style FPGAs, based on recursive bi-partitioning followed by application of space-filling curves. Experimental results of our method show 55% improvement in cost, when compared to random initial placement of the popular tool VPR. The solutions thus obtained require 44.5% fewer moves during final iterative refinement by ultra-low temperature simulated annealing, whereas the quality of solution is on the average 0.1% better. This establishes the utility of the method for fast reconfiguration of FPGA based co-processors.

Power density of high-end microprocessors has been increasing by approximately 80% per technology generation, while the voltage is scaling by a factor of 0.8. This leads to 225% increase in current per unit area in successive generation of technologies. The cost of maintaining the same IR drop becomes too high. This leads to compromise in power delivery and power grid becomes a performance limiter. Traditional performance related test techniques with transition and path delay fault models focus on testing the logic but not the power delivery. In this paper we view power grid as performance limiter and develop a fault model to address the problem of vector generation for delay faults arising out of power delivery problems. A fault extraction methodology applied to a microprocessor design block is explained.

New techniques are presented for routing straight channels, L-channels, switchboxes, and staircase channels in a two-layer Manhattan-diagonal (MD) model with tracks in horizontal, vertical, and ± 45° directions. First, an O ( l.d ) time algorithm is presented for routing a straight channel of length l and density d with no cyclic vertical constraints . It is shown that the number of tracks h used by the algorithm for routing multiterminal nets satisfies d ≤ h ≤ ( d + 1). Second, an output-sensitive algorithm is reported that can route a channel with cyclic vertical constraints in O ( l.h ) time using h tracks, allowing overlapping of wire segments in two layers. Next, the routing problem for a multiterminal L-channel of length l and height h is solved by an O ( l.h ) time algorithm. If no cyclic vertical constraints exist, its time complexity reduces to O ( l.d ) where d is the density of the L-channel. Finally, the switchbox routing problem in the MD model is solved elegantly. These techniques, easily extendible to the routing of staircase channels, yield efficient solutions to detailed routing in general floorplans. Experimental results on benchmarks show significantly low via count and reduced wire length, thus establishing the superiority of MD routing to classical strategies. The proposed algorithms are also potentially useful for general non-Manhattan area routing and multichip modules (MCMs).

Rectangular dualization method of floorplanning usually involves topology generation followed by sizing. Slicible topologies are often preferred for their simplicity and efficiency. While slicible topologies can be obtained efficiently, existing linear-time algorithms for topology generation from a given rectangular graph does not guarantee slicible topologies even if one exists. Moreover, the class of rectangular graphs, known as inherently nonslicible graphs, do not have any slicible topologies. In this article, new tighter sufficiency conditions for slicibility of rectangular graphs are postulated and utilized in the generation of area-optimal floorplans. These graph-theoretic conditions not only capture a larger class of slicible rectangular graphs but also help in reducing the total effort for topology generation, and in solving problems of larger size.

At very high frequencies, the major potential of asynchronous circuits is absence of clock skew and, through that, better exploitation of relative timing relations. This paper presents Fsimac, a gate-level fault simulator for stuck-at and gate-delay faults in asynchronous sequential circuits. Fsimac not only evaluates combinational logic and typical asynchronous gates such as Muller C-elements, but also complex domino gates, which are widely used in high-speed designs. Our algorithm for desecting feedback loops is designed so as to minimize the iterations for simulating the unfolded circuit. We use min-max timing analysis to compute the bounds on the signal delays. Stuck-at faults are detected by comparing logic values at the primary outputs against the corresponding values in the fault-free design. For delay faults, we additionally compare min-max rime stamps for primary output signals. Fault coverage reported by Fsimac for pseudo-random tests generated by Cellular Automata show some very good results, but also indicate test holes for which more specific patterns are needed. We intend to deploy Fsimac for designing more effective CA-BIST.

Existing algorithms for floorplan topology generation by rectangular dualization usually do not consider sizing issues. In this paper, given a rectangularly dualizable adjacency graph and a set of aspect ratios of the modules, a topology which is likely to yield an optimally sized floorplan, is produced first in a top-down fashion by an AI-based search technique with novel heuristic estimates based on size parameters. It is shown that for any rectangular graph, there exists a feasible topology using only either straight or Z-cutlines recursively within a bounding rectangle. The significance of this result is four-fold: (1) considerable acceleration of the heuristic search, (2) topology generation with minimal number of nonslice cores, (3) guaranteed safe routing order without addition of pseudo modules, and (4) design of an efficient bottom-up heuristic for optimal sizing. Experimental results show that this integrated method elegantly solves floorplan optimization problem for general including inherently nonslicible adjacency graphs.

The graph dualization approach to fIoorplan design with rectangular modules usually involves topology generation followed by sizing.The sizing problem for nonslicible topologies is NP-complete.Slicible topologies are often preferred for their simplicity and efficiency.Linear time algorithms exist for generation of topology corresponding to a given rectangular graph, but these do not guarantee slicible topologies even if one exists.Moreover, there is a class of rectaugular graphs, known as inherently nonslicible graphs, which do not have any slicible topologies.Previous methods for efficient generation of a slicible topology under sizing constraints for any rectangular graph, are likely to require addition of pseudeblocks, thereby more empty area.In this paper, new tighter sufficiency conditions for slicibility of rectangular graphs are postulated and utilized in the generation of slicible area-optimal floorplans.These graph-theoretic conditions not only capture a larger class of slicible rectangular graphs but also help in reducing the total effort for unified topology generation and sizing.

In this paper, it is shown that for any rectangularly dualizable graph, a feasible topology can be obtained by using only either straight or Z-cutlines recursively within a bounding rectangle. Given an adjacency graph, a potential topology, which may be nonslicible and is likely to yield an optimally sized floorplan, is produced first in a top-dozen fashion using heuristic search in AND-OR graphs. The advantage of this technique is four-fold: (i) accelerates top-down search phase, (ii) generates a floorplan with minimal number of nonslice cores, (iii) ensures safe routing order without addition of pseudo-modules, and (iv) solves the bottom-up algorithm efficiently for optimal sizing of general floorplans in the second phase.

Channel graphs for nonsliceable floorplans are studied for determination of feasible channel routing order. The minimum feedback vertex set (MFVS) formulation is revisited and a polynomial time heuristic is presented. It is shown that feasible routing orders with reserved channels, L-channels, and monotone channels can be obtained from a given MFVS for any floorplan. This approach provides a powerful tool to unify all three previous approaches and produces a solution with comparable efficiency and quality.>