Graph Separator Theorem and Its Application to Gaussian Elimination to Optimize Boolean Expressions for Parallel Evaluation

摘要

Gaussian elimination, which has been shown to be applicable to the solution problems in many different domains, is the technique used by COSMOS to symbolically analyze digital MOS networks for their behavior in terms of Boolean expressions. While pivot selection algorithms are known which minimize the total number of operations required to solve a system, this report will focus on pivot selection algorithms that result in expressions of small depth, from which fine-grained parallelism may be extracted. A graph theoretic approach to Gaussian elimination is adopted which allows the structure of sparse systems to be clearly examined, and an elimination ordering based on graph separators is shown to result in expressions of small depth. This report proposes an algorithm related to Gaussian elimination which characterizes graphs in terms of decomposition rules and shows that for graphs which may be reduced by an elimination ordering the results in low total complexity, a reordered elimination sequence may result in expressions of small depth.