High Performance Computing (HPC) Strategies

Process systems engineering involves the development and application of computer-aided, model-based techniques for the design, optimization, operation and control of chemical processing systems, as well as for the associated planning, scheduling and maintenance problems. In this field, both in on-line and off-line applications, two core numerical issues are the solution of nonlinear equation systems and of nonlinear programming (optimization) problems. However, neither of these problems can be solved with complete reliability using standard techniques. In this context, we have shown that the ``interval-Newton" technique can be used to solve the nonlinear equation solving and optimization problems with complete reliability, providing a mathematical and computational guarantee that either all roots are found in the nonlinear equation solving problem, or that the global optimum is found in the nonlinear programming problem. However, this guarantee of reliability comes at the cost of a potentially very large computational cost (CPU time). However, the interval-Newton method can be implemented using branch-and-prune (BP) or branch-and-bound (BB) strategies that present a natural parallelism, and which thus are particularly amenable to parallel processing. Thus, in this work the goal is to make effective use of high performance computing technology (parallel computing) to implement BP and BB strategies for reliably and efficiently solving problems in chemical process modeling and engineering.

Of particular interest has been the study and development of strategies for load balancing and work scheduling in the implementation of parallel BB and BP. An efficient dynamic load balancing algorithm, based on an asynchronous diffusive load balancing (ADLB) scheme, was developed and tested. This approach overlaps computation and communication by the use of the asynchronous nonblocking communication functions provided by the Massage Passing Interface (MPI) protocol, and uses a type of diffusive load-adjusting scheme to prevent out-of-work idle states while keeping communication needs small. This approach was then implemented on a cluster of workstations (the Notre Dame Hydra cluster) and used in connection with the interval-Newton method to reliably solve nonlinear equation solving and optimization problems arising in chemical process engineering.

The results of applying ADLB in the equation-solving context has shown that the parallel BP algorithm can achieve a nearly linear speedup, with a consistently high efficiency around 95%, on up to 16 processors when configured in a one-dimensional torus (ring) virtual network. When using a two-dimensional torus virtual network, ADLB provides high scalability up to 32 processors (and likely beyond), and with different sizes of problems. When applying the scheme to deterministic global optimization problems, the parallel BB algorithm using ADLB achieves significantly superlinear speedups (possible since in BB a parallel version may require less work than a serial version), though it is somewhat inconsistent in the extent to which this occurs. By implementing a new dual stack management scheme in connection with ADLB, it appears that a consistently high superlinear speedup on optimization problems can be obtained.

Though the test problems considered in this research work are based on the chemical process systems engineering problems, it should be emphasized that the parallel interval-Newton method is general-purpose and can be used in connection with a wide variety of global optimization problems and nonlinear equation solving problems. Also, the load management schemes described can be applied to a wide variety of other tree-search problems in chemical process engineering, such as in process synthesis and process scheduling, or in many other intelligent search applications, such as in operations research and data mining.


For more details, click here

Related Publications and Presentations

  • C.-Y. Gau, and M. A. Stadtherr, "Parallel Branch-and-Bound for Chemical Engineering Applications: Load Balancing and Scheduling Issues," to appear in Lecture Notes in Computer Science (2000). (Postcript)
  • C.-Y. Gau (speaker), M. A. Stadtherr, "A Systematic Analysis of Dynamic Load Balancing Strategies for Parallel Interval Analysis," AIChE Annual Meeting, Dallas, TX, October 31 - November 5, 1999. SLIDES (Acrobat).
  • C.-Y. Gau (speaker), M. A. Stadtherr, "Reliable High Performance Computing Strategies for Chemical Process Modeling," AIChE Annual Meeting, Dallas, TX, October 31 - November 5, 1999. POSTER (Acrobat).
  • C.-Y. Gau and M. A. Stadtherr (speaker), "Trends in Parallel Computing for Process Engineering," AspenWorld 2000, Orlando, FL, Feb. 6-11, 2000. SLIDES (Acrobat)
  • C.-Y. Gau, M. A. Stadtherr (speaker), "Parallel Branch-and-Bound for Chemical Engineering Application: Load Balancing and Scheduling Issues," Vector and Parallel Processing 2000, Portugal, June 21-23, 2000. (Postcript)
  • C.-Y. Gau, and M. A. Stadtherr, "Parallel Interval Analysis for Chemical Process Modeling," presented at First SIAM Conference on Computations in Science and Engineering, Washington DC, September 21-24, 2000.


 
Back to Research