Model order reduction for multi-terminals systems : with applications to circuit simulation

Ever since its beginnings in the 1950’s, the integrated circuit (IC) has profoundly changed our lives. The way we work, travel, communicate, or address medical problems today has been facilitated by advances in microelectronics, which permit more functionality to be built on the same silicon area, at decreasing cost. As the feature size of devices on a chip shrink and circuits operate at increasing frequencies, the electromagnetic coupling effects between different IC components can no longer be ignored. To understand their impact on chip performance, these so called parasitic effects must be simulated. Parasitic networks are often so large, that state of the art simulation tools are insufficient to handle them: the simulations are either too lengthy, or cannot be carried out at all. The mathematical reason behind this is that the underlying systems are too large to be solved with the numerical algorithms implemented in simulation software. Model order reduction (MOR) provides one avenue for enabling faster simulations at little accuracy loss. However, when the systems have many input/output nodes, i.e., they have many terminals, performing the reduction itself becomes even more challenging. In this thesis model reduction methods are developed for multi-terminal systems arising in industrial problems. To solve these effeciently, the methods rely jointly on concepts from numerical linear algebra, electrical engineering, and computer science. This thesis begins with an overview of MOR in Chapter 1 and places the reduction of multi-terminal systems in the context of existing approaches. Aside from being efficient and accurate, multi-terminal MOR methods should also ensure that the reduced model is easily inserted in the simulation environment in place of the original, and that it is indeed cheaper to simulate. Although all reduction methods are expected to satisfy these properties, this thesis shows that such expectations are rarely met when traditional approaches are applied to very large electrical networks with many terminals which arise in industrial problems. Hence, an improved framework for multi-terminal model reduction and synthesis is proposed. The methods developed in this thesis address three global problems: (1) the efficient and accurate reduction of multi-terminal circuits, (2) the appropriate synthesis of the reduced model into a netlist equivalent with the same terminal nodes, and (3) the re-simulation of the reduced circuit (instead of the original) with emphasis on accuracy and simulation time. In Chapter 2, a basic framework is developed for the reduction of multi-terminal networks and the synthesis of reduced multi-terminal models. Chapter 2 shows that, if the circuit equations are prepared appropriately, a multi-terminal RLC network can be reduced so that the synthesis step is also greatly simplified. In particular, from the reduced mathematical construction, an equivalent circuit containing only RLC elements can be obtained, without introducing unintended circuit elements such as controlled sources. In addition, the reduced circuit has the same terminal nodes as the original and is coupled easily to other circuit blocks in the simulation setup. The framework establishes the mathematical principle which allows voltage sources, non-linear devices or other parts of a larger network to be de-coupled from to specific linear part to be reduced. It also ensures that these elements can be re-coupled in the simulation phase to the reduced circuit via its terminals. In Chapters 3 and 4, new methods for reducing large, multi-terminal R, and RC networks are derived, with emphasis on accuracy, efficiency and sparsity. It is shown that, if the projection which reduces an R/RC network performs a Schur-complement operation on the original conductance matrix, the resulting reduced network will have only positive resistors, which may be important for certain circuit simulators. This projection is also shown to exactly preserve the path resistance between terminals, and for RC circuits, the slope of the response in addition (in system theoretic terms, two multi-port admittance moments at DC are matched). The efficiency and sparsity considerations are dealt with especially in Chapter 4. These become critical for circuits with terminal numbers exceeding thousands, and node numbers exceeding hundreds of thousands. Reducing them by traditional means is either inefficient, or results in dense reduced models which are more expensive to simulate than the originals. Chapter 4 however develops a new method which is able to reduce efficiently such challenging RC netlists, while ensuring that the reduced models are sparse and fast to simulate. The key principles of the approach are graph partitioning, fill-reducing node re-orderings, and a reducing projection which is constructed accordingly. This preserves sparsity and also maintains accuracy by moment matching irrespective of how the circuit is partitioned. Based on the result of Chapter 2, the reduced models thus obtained are synthesized without controlled sources, have the same terminal nodes as the original ones, and are therefore inserted easily in the desired simulation flow. With the decrease of transistor feature sizes and increase of operating frequencies, it becomes important to also investigate the effects of parasitic inductances (e.g., skin or proximity effects) on chip performance. This requires time-consuming simulations of very large multi-terminal RLC(K) networks, and thus motivates the need for appropriate reduction methods. Chapter 5 identifies the main challenges of multi-terminal RLC reduction, and presents a skeleton for approaching them based on partitioning principles similar to those of Chapter 4. Important problems pertaining to RLC reduction are also identified in Chapter 5, which are otherwise rarely explicitly addressed in the literature. These include matching the response at DC when the underlying conductance matrix is singular, or the presence of singularities in the reduced conductance matrix which in turn negatively affect the simulation of the reduced model. For the latter problem especially, a solution is proposed in Chapter 5 . Two constraints which are known to limit the applicability of traditional reduction methods to multi-terminal systems are as follows: (a) the underlying matrix pencils are often singular and (b) the reducing projections may destroy the structure of the input/output matrices and with that, the physical interpretation of terminal nodes. The advanced methods of Chapters 3, 4 and 5 automatically by-pass these limitations due to the special way in which the reducing projection is formed. Chapter 6 brings an additional contribution by showing how, despite the known limitations, more general reduction methods (e.g., the Loewner approach) are also able to handle multi-terminal systems. The new reduction-synthesis framework of Chapter 6 eliminates the pencil singularity using a simple pre-processing of the original circuit, and recovers the connectivity at all terminal nodes using a post-processing of the reduced model. Among the main results of this thesis is the improvement in reduced model sparsity and reduction efficiency, achieved with the help of graph partitioning. State-of-theart partitioning algorithms such as nested dissection or Mondriaan already served this purpose, nevertheless Chapter 7 shows that the results could be further strengthened with the help of partitioning criteria designed especially for multi-terminal MOR. A high level description of the desired objectives is also derived there.