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.

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.

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.

The increasing design complexity of modern circuits has made traditional FPGA placement techniques not efficient anymore. To improve the scalability, commercial FPGA placement tools have started migrating to analytical placement. In this paper, we propose the first academic multilevel timing-and-wirelength-driven analytical placement algorithm for FPGAs. Our proposed algorithm consists of (1) multilevel timing-and-wirelength-driven analytical global placement with the novel block alignment consideration, (2) partitioning-based legalization, (3) wirelength-driven block matching-based detailed placement, and (4) timing-driven simulated-annealing-based detailed placement. Experimental results show that our proposed approach can achieve 6.91x speedup on average with 7% smaller critical path delay and 1% shorter routed wirelength compared to VPR, the well-known, state-of-the-art academic simulated-annealing-based FPGA placer.

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.

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.