Files in this item



application/pdf9021666.pdf (10MB)Restricted to U of Illinois
(no description provided)PDF


Title:Orderings and direct methods for coarse granular parallel solutions in equation-based flowsheeting
Author(s):Coon, Alan Blaine
Doctoral Committee Chair(s):Stadtherr, Mark A.
Department / Program:Chemical and Biomolecular Engineering
Discipline:Chemical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Chemical
Computer Science
Abstract:When the cost of interprocessor communication is not insignificant compared to the cost of computation, it becomes important to identify a coarse parallel task granularity in algorithms that are executed on parallel computers. At the same time, such coarse granular tasks should represent a fairly uniform processor load distribution. Previously proposed methods for identifying coarse task granularity in the solution of linear equations for equation-based (EB) flowsheeting have attempted to exploit the natural block structure of these matrices; however, those methods made no attempt to reduce interprocessor communication or balance the processor load distribution.
In this work, two variants of two direct methods are considered for use in EB flowsheeting. These four strategies have the potential to produce large granular balanced tasks, while reducing the amount of interprocessor communication that is required. The success of these strategies is critically dependent on finding a good reordering of the rows and columns of the matrix, for the properties of the reordering actually determine the load distribution and amount of interprocessor commmunication. A new algorithm to determine such an ordering, and several variants of it are also considered.
In particular, the new algorithm provides a partitioning of the bipartite graph associated with the unsymmetric matrix. The partitioning strategy is developed with considerations for the direct methods to be used and the overall structure of the EB flowsheeting matrices being reordered. Since a bipartite graph model is used, the algorithm can consider unsymmetric permutations of rows and columns while still providing a structurally stable reordering. More importantly, some of the variants of this algorithm can be shown to have a worst case running time that is linear in the order of the matrix. Two of these linear time variants provide partitionings that are almost as good, if not better, than those of the more computationally intensive variants. Results for several EB flowsheeting test problems are presented, along with recommendations for other uses of this new partitioning algorithm.
Issue Date:1990
Rights Information:Copyright 1990 Coon, Alan Blaine
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9021666
OCLC Identifier:(UMI)AAI9021666

This item appears in the following Collection(s)

Item Statistics