Chen-Yu Lee, Chun-Liang Li, Hao Zhang, Timothy Dozat, Vincent Perot, Guolong Su, Xiang Zhang, Kihyuk Sohn, Nikolay Glushnev, Renshen Wang, Joshua Ainslie, Shangbang Long, Siyang Qin, Yasuhisa Fujii, Nan Hua, Tomas Pfister. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Chen-Yu Lee, Chun-Liang Li, Timothy Dozat, Vincent Perot, Guolong Su, Nan Hua, Joshua Ainslie, Renshen Wang, Yasuhisa Fujii, Tomas Pfister. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

We propose a new approach for paragraph recognition in document images by spatial graph convolutional networks (GCN) applied on OCR text boxes. Two steps, namely line splitting and line clustering, are performed to extract paragraphs from the lines in OCR results. Each step uses a β-skeleton graph constructed from bounding boxes, where the graph edges provide efficient support for graph convolution operations. With pure layout input features, the GCN model size is 3~4 orders of magnitude smaller compared to RCNN based models, while achieving comparable or better accuracies on PubLayNet and other datasets. Furthermore, the GCN models show good generalization from synthetic training data to real-world images, and good adaptivity for variable document styles.

Floorplanning, as an early stage of the physical design flow, has been extensively studied in literature and developed into several branches. Recently, hierarchical floorplanning is regaining attention due to the rising scale of systems-on-chip, which necessarily requires divide-and-conquer strategies to handle the increasing complexity. This paper introduces a floorplanning scheme targeting hierarchical physical prototyping, answering some of the questions posed by Kahng [8] on classical floorplanning. Our scheme emphasizes practical requirements including runtime scalability, wire length and shape quality. We formulate a new hierarchical floorplanning problem with reduced computational complexity, but without weakening the problem as a global layout optimization. To achieve this goal, a placement seed is taken as input and converted into a slicing floorplan under the given constraints of region area and aspect ratio (region shape). We solve the problem by devising an efficient slicing algorithm with integrated dynamic programming. Implementation of the algorithm shows fast runtime and good quality of result.

Power consumption and the thermal wall have become the major factors limiting the speed of very-large-scale integration (VLSI) circuits, while interconnect is becoming a primary power consumer. These factors bring new demands on the communication architecture of system-on-chips (SoCs). High bandwidth is desired to enhance parallelism for better performance, and the power efficiency on this bandwidth is critical to the overall SoC power consumption. Current bus architectures such as AMBA, Coreconnect, and Avalon are convenient for designers but not efficient on power. This paper proposes a physical synthesis scheme for on-chip buses and bus matrices to minimize the power consumption, without changing the interface or arbitration protocols. By using a bus gating technique, data transactions can take shortest paths on chip, reducing the power consumption of bus wires to minimal. Routing resource and bandwidth capacity are also optimized by the construction of a shortest-path Steiner graph, wire sharing among multiple data transactions, and wire reduction heuristics on the Steiner graph. Experiments indicate that the gated bus from our synthesis flow can save more than 90% dynamic power on average data transactions in current AMBA bus systems, which is about 5-10% of total SoC power consumption, based on comparable amount of chip area and routing resources.

As the thermal wall becomes the dominant factor limiting VLSI circuit performance, and the interconnect wires become the primary power consumer, power efficiency of on-chip data throughput is nowadays a critical target for SoC designers. Under this trend, bus matrices are mostly used in current system-on-chips (SoCs) because of their simplicity and good performance. We introduce a bus matrix synthesis flow to optimize on-chip communications, to keep the low delay of buses, reduce power by bus gating, and reduce wires by wire sharing. The proposed algorithms are able to help designers create high capability yet compact and efficient bus matrices for future low power SoCs.

Interconnect dominated electronic design stimulates a demand for developing circuits on the third dimension, leading to 3-D integration. Recent advances in chip fabrication technology enable 3-D circuit manufacturing. However, there is still a possible barrier of design complexity in exploiting 3-D technologies. This article discusses the impact of migrating from 2-D to 3-D on the difficulty of floorplanning and placement. By looking at a basic formulation of the graph cuboidal dual problem, we show that the 3-D cases and the 3-layer 2.5-D cases are fundamentally more difficult than the 2-D cases in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-to-decide relations between topological connections and geometrical contacts. The results show possible challenges in the future for physical design and CAD of 3-D integrated circuits.

With the popularity of multiple power domain (MPD) design, the multi-domain power network noise analysis and minimization is becoming important. This paper describes an efficient heuristic algorithm to arrange the power-up sequence in a multi-domain power network in order to minimize the noise. We present a formulation of this problem and show it is NP-complete. Therefore, we propose a simulated annealing (SA) based algorithm with preprocessing. Experimental results show that the proposed algorithm can minimize the noise close to the minimal values. In terms of efficiency, the SA algorithm is more than hundreds of times faster than the enumerating method and the running time scales well for these cases with the number of domains. In addition, we discuss the trade off between power-up efficiency and noise.

Power consumption of system-level on-chip communications is becoming more significant in the overall system-on-chip (SoC) power as technology scales down. In this paper, we propose a low power design technique of gated bus which can greatly reduce power consumption on state-of-the-art bus architectures. By adding demultiplxers and adopting a novel shortest-path Steiner graph, we achieve a flexible tradeoff between large power reduction versus small wire-length increment. According to our experiments, using the gated bus we can reduce on average 93.2% of wire capacitance per transaction, nearly half of bus dynamic power and on a scale of 5%~10% of total system power.

This paper proposes a scheme for automatic re-distribution layer (RDL) routing, which is used in chip-package connections. Traditional RDL routing designs are mostly performed manually because the wire geometries are more flexible and therefore more difficult to handle on RDL than on chip. For example, octilinear routing is manufacturable in RDL and is widely adopted due to its higher efficiency than Manhattan routing. In this paper we devise a polynomial time octilinear RDL routing algorithm based on a grid network embedded in the bump array. The grid network is constructed to fully utilize the routing space as well as avoid any spacing violation. Detailed routing solution can be obtained following the min-cost max-flow in the network. Experimental results show the effectiveness of our router.

This paper discusses the impact of migrating from 2-D to 3-D on floorplanning and placement. By looking at a basic formulation of graph cuboidal dual problem, we show that the 3-D case and the 3-layer 2.5-D case are fundamentally more difficult than the 2-D case in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-deciding relations between topological connections and geometrical contacts. The results show future challenges for physical design and CAD of 3-D integrated circuits.

As the feature size of VLSI circuits scales down and clock rates increases, circuit performance is becoming more sensitive to process variations. This paper proposes an algorithm of symmetrical buffer placement in symmetrical clock trees to achieve zero-skew in theory, as well as robust low skew under process or environment variations. With the completely symmetrical structure, we can eliminate many factors of clock skew such as model inaccuracy, environment temperature and intra-die process variations. We devise a new dynamic programming scheme to handle buffer placement and wire sizing under the constraint of symmetry. By classifying the wires by tree levels and defining the level-dependent blockages, the potential candidate points in the gaps of circuit blocks can be fully explored. The algorithm is efficient for minimizing source-sink delay as well as other linear cost functions. Experiments show that our method helps to obtain a balanced design of clock tree with low delay, skew and power.

3-D packing is an NP-hard problem with wide applications in microelectronic circuit design such as 3-D packaging, 3-D VLSI placement and dynamically reconfigurable FGPA design. We present a complete representation for general non-slicing 3-D floorplan or packing structures, which uses a labeled tree and dual sequences. For each compact placement, there is a corresponding encoding. The number of possible tree-sequence combinations is (n+1)n-1(n!)2, the lowest among complete 3-D representations up to date. The construction of placement from an encoding needs O(n2) in the worst case, but in practical cases we expect O(n4⁄3 log n) time on average for circuit blocks with limited length/width ratios. Experimental results show promising performance using the labeled tree and dual sequences on 3-D floorplan and placement optimizations

We devise a central triangular sequence to minimize the escape routing layers in area array packaging. We use a network flow model to analyze the bottleneck of the routable pins. The triangular patterns are generated in a reverse order from the last to the first layer. We demonstrate that the triangular pin sequence maximizes the sum of escape pins in the accumulated layers and thus minimize the number of escape routing layers. A test case is presented to illustrate the approach.

The Corner Block List representation (CBL) introduced in 2000 is an efficient and effective model for floorplanning and placement while still having some limitations such as redundancy and incompleteness. In this paper, we present an auxiliary 3-Route Model to eliminate the redundancy and insert empty rooms to resolve the incompleteness. Finally we attain a P-admissible representation ECBL(2) which has higher performances than the original CBL and the count of its solution space is O((2n)!26n/n!n4).