Computing surface folding maps has numerous applications ranging from computer graphics to material design. In this work we propose a novel way of computing surface folding maps via solving a linear PDE. This framework is a generalization of the existing computational quasi-conformal geometry and allows precise control of the geometry of folding. This property comes from a crucial quantity that occurs as the coefficient of the equation, namely, the alternating Beltrami coefficient. This approach also enables us to solve an inverse problem of parametrizing the folded surface given only partial data with known folding topology. Various interesting applications such as fold sculpting on 3 dimensional models, study of Miura-ori patterns, and self-occlusion reasoning are demonstrated to show the effectiveness of our method.

As a good tradeoff between central processing unit (CPU) and application specific integrated circuit (ASIC), field-programmable gate array (FPGA) is becoming more widely used in both industry and academia. The increasing complexity and scale of modern FPGA, however, impose great challenges on the FPGA placement and packing problem. In this paper, we propose RippleFPGA to solve the packing and placement simultaneously through a set of novel techniques: 1) smooth stair-step flow; 2) implicit packing similar to ASIC legalization (LG); and 3) two-level detailed placement (DP). To enable the flow, a generic, efficient, and false-alarm-free legality checking method is also proposed. Besides, due to the insufficiency of ASIC-like congestion alleviation methods, some FPGA-routing-architecture-aware optimization techniques are proposed to improve the routability. When evaluated by ISPD 2016 Contest benchmarks, RippleFPGA has 5.1% better routed wirelength and 5.5× speedup compared to all the state-of-the-art FPGA placers.

As the complexity and scale of FPGA circuits grows, resolving routing congestion becomes more important in FPGA placement. In this paper, we propose a routability-driven placement algorithm for large-scale heterogeneous FPGAs. Our proposed algorithm consists of (1) partitioning, (2) packing, (3) global placement with congestion estimation, (4) window-base legalization, and (5) routing resource-aware detailed placement. Experimental results show that our proposed approach can give routable placement results for all the benchmarks in the ISPD2016 contest and can achieve good result compared to the other wining teams of the ISPD2016 contest.

As the sizes of modern circuits become bigger and bigger, implementing those large circuits into FPGA becomes arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement when the input circuit contains millions of lookup tables, excluding the runtime for routing. To expedite the placement process, we propose a routability-driven placement algorithm for FPGA that adopts techniques used in ASIC global placer. Our placer follows the lower-bound-and-upper-bound iterative optimization process in ASIC placers like Ripple. In the lower-bound computation, the total HPWL, modeled using the Bound2Bound net model, is minimized using the conjugate gradient method. In the upper-bound computation, an almost-legalized result is produced by spreading cells linearly in the placement area. Those positions are then served as fixed-point anchors and fed into the next lower-bound computation. Furthermore, global routing will be performed in the upper-bound computation to estimate the routing segment usage, as a mean to consider congestion in placement. We tested our approach using 20 MCNC benchmarks and 4 large benchmarks for performance and scalability. Experimental results show that based on the island-style architecture which VPR is most optimized for, our approach can obtain a placement result 8x faster than VPR with 2% more in channel width, or 3x faster with 1% more in channel width when congestion is being considered. Our approach is even 14x faster than VPR in placing large benchmarks with over 10,000 lookup tables, with only 7% more in channel width.

Due to a significant mismatch between the objectives of wirelength and routing congestion, the routability issue is becoming more and more important in VLSI design. In this paper, we present a high quality placer Ripple 2.0 to solve the routability-driven placement problem. We will study how to make use of the routing path information in cell spreading and relieve congestion with tangled logic in detail. Several techniques are proposed, including (1) lookahead routing analysis with pin density consideration, (2) routing path-based cell inflation and spreading and (3) robust optimization on congested cluster. With the official evaluation protocol, Ripple 2.0 outperforms the top contestants on the ICCAD 2012 Contest benchmark suite.