In this article, we introduce a new method to estimate a directed acyclic graph (DAG) from multivariate functional data. We build on the notion of faithfulness that relates a DAG with a set of conditional independences among the random functions. We develop two linear operators, the conditional covariance operator and the partial correlation operator, to characterize and evaluate the conditional independence. Based on these operators, we adapt and extend the PC-algorithm to estimate the functional directed graph, so that the computation time depends on the sparsity rather than the full size of the graph. We study the asymptotic properties of the two operators, derive their uniform convergence rates, and establish the uniform consistency of the estimated graph, all of which are obtained while allowing the graph size to diverge to infinity with the sample size. We demonstrate the efficacy of our method through both simulations and an application to a time-course proteomic dataset.

In this paper we introduce a statistical model, called additively faithful directed acyclic graph (AFDAG), for causal learning from observational data. Our approach is based on additive conditional independence (ACI), a recently proposed three-way statistical relation that shares many similarities with conditional independence but without resorting to multi-dimensional kernels. This distinct feature strikes a balance between a parametric model and a fully nonparametric model, which makes the proposed model attractive for handling large networks. We develop an estimator for AFDAG based on a linear operator that characterizes ACI, and establish the consistency and convergence rates of this estimator, as well as the uniform consistency of the estimated DAG. Moreover, we introduce a modified PC-algorithm to implement the estimating procedure efficiently, so that its complexity is determined by the level of sparseness rather than the dimension of the network. Through simulation studies we show that our method outperforms existing methods when commonly assumed conditions such as Gaussian or Gaussian copula distributions do not hold. Finally, the usefulness of AFDAG formulation is demonstrated through an application to a proteomics data set.

In this paper, we formulate a problem of simultaneous redundant via insertion and line end extension for via yield optimization. Our problem is more general than previous works in the sense that more than one type of line end extension is considered and the objective function to be optimized directly accounts for via yield. We present a zero-one integer linear program based approach, that is equipped with two speedup techniques, to solve the addressed problem optimally. In addition, we describe how to modify our approach to exactly solve a previous work. Extensive experimental results are shown to demonstrate the effectiveness and efficiency of our approaches.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we studied the problem ofsimultaneous double via insertion and wire bending(DVI/WB) in a postrouting stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The primary goal of the DVI/WB problem is to insert as many double vias as possible; the secondary objective is to minimize the amount of layout perturbation. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We proposed algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. We also proposed a zero-one integer linear program (0–1 ILP)-based approach to solve the mWMIS problem. Moreover, we studied the problem of DVI/WB with the consideration of via density and extended our 0–1 ILP-based approach to solve it. Experimental results show that our approaches can improve the insertion rate by up to 6.34% at the expense of up to 1.29% wirelength increase when compared with the state-of-the-art double via insertion methods that do not consider wire bending. Moreover, when compared with an existing method that considers wire bending, our DVI/WB approach can insert 2% more double vias and produce 32% less wirelength increase rate on average.

As on-track double vias take less routing resources and have better electrical characteristics, we study in this paper the problem of double via insertion with a preference for on-track double vias (DVI/ON) in a postrouting stage. The primary goal is to insert as many double vias as possible, and maximizing the number of on-track double vias is a secondary objective. We present a zero-one integer linear program-based approach to optimally solve the DVI/ON problem. Moreover, we also discuss a special case of the DVI/ON problem and present a maximum-weighted bipartite matching-based optimal approach. Experimental results indicate that our approaches outperform existing algorithms in terms of solution quality.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double via insertion with wire bending (DVI/WB) in a post-routing stage, where a single via can have at most one redundant via inserted next to it. Aside from this, we are allowed to bend existing signal wires for enhancing the insertion rate of double vias. The goal of DVI/WB is to primarily insert as many double vias as possible and to minimize the amount of layout perturbation as the secondary objective. We formulate the DVI/WB problem as that of finding a minimum-weight maximum independent set (mWMIS) on an enhanced conflict graph. We propose algorithms to perform wire bending and to construct the enhanced conflict graph from a given design. Moreover, we also propose a zero-one integer linear program (0-1 ILP) based approach to solve mWMIS. Experimental results show that our approach can improve the insertion rate by up to 5.58% at the expense of up to 0.37% wirelengh increase when compared with a state-of-the-art double via insertion method that does not consider wire bending.

Redundant via insertion is highly recommended for improving chip yield and reliability. In this paper, we study the problem of double-cut via insertion (DVI) in a post-routing stage, where a single via can have at most one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing optimal DVI solution, with up to 35.3 times speedup over existing heuristic algorithms.

Redundant via insertion is highly effective in improving chip yield and reliability. In this paper, we study the problem ofdouble-cutviainsertion(DVI) in a post-routing stage, where a single via can have, at most, one redundant via inserted next to it and the goal is to insert as many redundant vias as possible. The DVI problem can be naturally formulated as a zero-one integer linear program (0-1 ILP). Our main contributions are acceleration methods for reducing the problem size and the number of constraints. Moreover, we extend the 0-1 ILP formulation to handle via density constraints. Experimental results show that our 0-1 ILP is very efficient in computing an optimal DVI solution, with up to 73.98 times speedup over existing heuristic algorithms.

As IC process geometries scale down to the nanometer territory, the industry faces severe challenges of manufacturing limitations. To guarantee yield and reliability, physical design for manufacturability and reliability has played a pivotal role in resolution and thus yield enhancement for the imperfect manufacturing process. In this paper, we introduce major challenges arising from nanometer process technology, survey key existing techniques for handling the challenges, and provide some future research directions in physical design for manufacturability and reliability.

Reducing the yield loss due to via failure is one of the important problems in design for manufacturability. A well known and highly recommended method to improve via yield/reliability is to add redundant vias. In this paper, we study the problem of post-routing redundant via insertion and formulate it as a maximum independent set (MIS) problem. We present an efficient graph construction algorithm to model the problem, and an effective MIS heuristic to solve the problem. The experimental results show that our MIS heuristic inserts more redundant vias and distributes them more uniformly among via layers than a commercial tool and an existing method. The number of inserted redundant vias can be increased by up to 21.24%. Besides, since redundant vias can be classified into on-track and off-track ones, and on-track ones have better electrical properties, we also present two methods (one is modified from the MIS heuristic, and the other is applied as a post processor) to increase the amount of on-track redundant vias. The experimental results indicate that both methods perform very well.

Redundant via insertion and line end extension employed in the post-routing stage are two well known and highly recommended techniques to reduce yield loss due to via failure. However, if the amount of inserted redundant vias is not well controlled, it could violate via density rules and adversely worsen the yield and reliability of the design. In this paper, we first study the problem of redundant via insertion, and present two methods to accelerate a state-of-the-art approach (which is based on a maximum independent set (MIS) formulation) to solve it. We then consider the problem of simultaneous redundant via insertion and line end extension. We formulate the problem as a maximum weighted independent set (MWIS) problem and modify the accelerated MIS-based approach to solve it. Lastly, we investigate the problem of simultaneous redundant via insertion and line end extension subject to the maximum via density rule, and present a two-stage approach for it. In the first stage, we ignore the maximum via density rule, and enhance the MWIS-based approach to find the set of regions which violate the maximum via density rule after performing simultaneous redundant via insertion and line end extension. In the second stage, excess redundant vias are removed from those violating regions such that after the removal, the maximum via density rule is met while the total amount of redundant vias removed is minimized. This density-aware redundant via removal problem is formulated as a set of zero-one integer linear programming (0-1 ILP) problems each of which can be solved independently without sacrificing the optimality. The superiorities of our approaches are all demonstrated through promising experimental results.