Pre-trained video-language models (VLMs) have shown superior performance in high-level video understanding tasks, analyzing multi-modal information, aligning with Deep Video Understanding Challenge (DVUC) requirements.In this paper, we explore pre-trained VLMs' potential in multimodal question answering for long-form videos. We propose a solution called Dual Branches Video Modeling (DBVM), which combines knowledge graph (KG) and VLMs, leveraging their strengths and addressing shortcomings.The KG branch recognizes and localizes entities, fuses multimodal features at different levels, and constructs KGs with entities as nodes and relationships as edges.The VLM branch applies a selection strategy to adapt input movies into acceptable length and a cross-matching strategy to post-process results providing accurate scene descriptions.Experiments conducted on the DVUC dataset validate the effectiveness of our DBVM.

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good for meeting other objectives such as minimizing the total wire length, which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. This paper first shows that the problem can be formulated by linear programming. Thereafter, instead of using the general, but slow, linear programming, this paper proposes an efficient minimum-cost flow-based approach to solve it. This approach guarantees to obtain the minimum total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. This paper also shows that the approach can be easily extended to handle constraints such as fixed frame (fixed area), input-output (IO) pins, preplaced blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient that it finishes in less than 0.4 s for all Microelectronics Center of North Carolina (MCNC) benchmarks of block placement. It is also very effective. Experimental results show that the wire length of very compact floorplans can even be improved by 4.2%. Thus, it provides an ideal way for postfloorplanning refinement

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good to meet other objectives such as minimizing total wire length which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. In this paper, we first show that the problem can be formulated as linear programming. Thereafter, instead of using the general but slow linear programming, we propose an efficient min-cost flow based approach to solve it. Our approach guarantees to obtain the minimum of total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. We also show that the approach can be easily extended to handle constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient in that it finishes in less than 0.4 seconds for all MCNC benchmarks of block placement. It is also very effective. Experimental results show we can improve 4.2% of wire length even on very compact floorplans. Thus it provides an ideal way of post-floorplanning (refine floorplanning).

By putting different chips on the same mask, shuttle mask (or multiple project wafer) provides an economical solution for low volume designs and design prototypes to share the rising mask cost. A challenging floorplanning problem is to optimally pack these chips according to objectives and constraints related to cost and manufacturability. In this paper, we study the problem of CMP aware shuttle mask floorplanning, which is formulated as a rectangle packing problem with objectives of area and post-CMP topography variation minimization. We propose a 3-step procedure to solve the problem. First, we use the low-pass filter oxide CMP model to guide the simulated annealing search to minimize the topography variation. The result is then further improved by sliding each chip in its enclosing rectangle. Finally, we calculate the optimal amount of dummy feature needed with a linear programming method. Our experiment show excellent results on real industry data.

Electron projection lithography (EPL) is a leading candidate for next generation lithography (NGL) in VLSI production. The membrane mask used in EPL is divided into sub-fields by struts for structural support. A layout must be partitioned into these sub-fields on mask and then stitched back together by the EPL tool on wafer. To minimize possible stitching errors, partitioning of a mask layout should minimize cuts of layout features in the overlapping area between two adjacent sub-fields. This paper presents the first formulation of the mask layout partitioning problem for EPL as a graph problem. The graph formulation is optimally solved with a shortest path approach. Two other techniques are also presented to speed up computation. Experimental runs on data from a real industry design show excellent results.

Manufacturability of a design that is processed with shallow-trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish for which all previous studies on dummy-feature placement for single-material polish by Kahng et al. (1999), Tian et al. (2000), and Chen et al. (2000) are not applicable. Based on recent semiphysical models of polish-pad bending by Ouma et al (1998), local polish-pad compression by Grillaert (1999) and Smith (1999), and different polish rates for materials present in a dual-material polish by Grillaert (1999) and Tugbawa et al. (1999), this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy-feature placement for CMP in STI is given as a nonlinear-programming problem. An iterative approach is proposed to solve the dummy-feature placement problem. Computational experience on four layouts from Motorola is given.

In this paper, we review phase shift lithography, rule vs. model based methods for OPC and model-based tiling, and discuss their implications for layout and verificat ion. We will discuss novel approaches, using polarizing films on reticles, which change the game for phase-shift coloring, and could lead to a new direction in c:PSM constraints on physical design. We emphasize the need to do tiling that is model-driven and uses optimization techniques to achieve planarity for better manufacturing tolerance in the subwavelength dimensions era. Electromagnetic solver results will be presented which estimate the effect of tiling on circuit timing.

Buffer insertion and wire sizing are critical in deep submicron VLSI design. This paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. No previous algorithms consider all these factors simultaneously. Previous dynamic programming based algorithm is first extended to solve the problem. However, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. Then a new approach is proposed to formulate the problem as a series of graph problems. The routing tree solution is obtained by finding shortest paths in a series of graphs. In the new approach, wire sizing can be handled almost without any additional time and space requirement, Moreover, the time and space requirement is only polynomial in terms of the size of routing graph. Our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. Both theoretical and experimental results show that the graph-based algorithm outperforms the DP-based algorithm by a large margin. We also propose a hierarchical approach to construct routing tree for a large number of sinks.

Manufacturability of a design that is processed with shallow trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish, for which all previous studies on dummy feature placement for single-material polish [3, 11, 1] are not applicable. Based on recent semi-physical models of polish pad bending [5], local polish pad compression [2, 10], and different polish rates for materials present in a dual-material polish [2, 13], this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy feature placement for CMP in STI is given as a nonlinear programming problem. An iterative approach is proposed to solve the dummy feature placement problem. Computational experience on four layouts from Motorola is given.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block-placement algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e., to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O (n log log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60 /spl times/ speedup over the previous algorithm when input size n = 128. As a result, we can examine a million sequence pairs within one minute for typical input size of placement problems. For all MCNC benchmark block-placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O tree and B* tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm/sup 2/) was obtained by a B*-tree-based algorithm using 4752 s and we obtained a better result (36.5 mm/sup 2/) in 31 s.

Chemical-mechanical polishing (CMP) is an enabling technique used in deep-submicrometer VLSI manufacturing to achieve long range oxide planarization. Post-CMP oxide topography is highly related to local pattern density in the layout. To change local pattern density and, thus, ensure post-CMP planarization, dummy features are placed in the layout. Based on models that accurately describe the relation between local pattern density and post-CMP planarization by Stine et al. (1997), Ouma et al. (1998), and Yu et al. (1999), a two-step procedure of global density assignment followed by local insertion is proposed to solve the dummy feature placement problem in the fixed-dissection regime with both single-layer and multiple-layer considerations. Two experiments conducted with real design layouts gave excellent results by reducing simulated post-CMP topography variation from 767 /spl Aring/ to 152 /spl Aring/ in the single-layer formulation and by avoiding cumulative effect in the multiple-layer formulation. The simulation result from single-layer formulation compares very favorably both to the rule-based approach widely used in industry and to the algorithm by Kahng et al (1999). The multiple-layer formulation has no previously published work.

Chemical-mechanical polishing (CMP) is an enabling technique used in deep-submicron VLSI manufacturing to achieve uniformity in long range oxide planarization [1]. Post-CMP oxide topography is highly related to local spatial pattern density in layout. To change local pattern density, and thus ensure post-CMP planarization, dummy features are placed in layout. Based on models that accurately describe the relation between local pattern density and post-CMP planarization [7; 5; 9], a two-step procedure of global density assignment followed by local insertion is proposed to solve the dummy feature placement problem in the fixed-dissection regime with both single-layer and multiple-layer considerations. Two experiments, conducted with real design data, gave excellent results by reducing post-CMP topography variation from 767Å to 152Å in the single-layer formulation and by avoiding cumulative effect in the multiple-layer formulation. The result from single-layer formulation compares very favorably both to the rule-based approach widely used in industry and to the algorithm in [3]. The multiple-layer formulation has no previously published work.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e. to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O(n log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.