VARIABLE-COMPLEXITY MULTIDISCIPLINARY

OPTIMIZATION ON PARALLEL COMPUTERS

Progress Report for NASA Grant NAG-1-1562
7 December 1993 to 3 October 1994

Principal Investigators
Dr. Bernard Grossman, Dr. Raphael T. Haftka,
Dr. William H. Mason, Dr. Layne T. Watson
Multidisciplinary Analysis and Design (MAD) Center for Advanced Vehicles
Virginia Polytechnic Institute and State University
Blacksburg, Virginia 24061-0203

Graduate Research Assistants
Vladimir Balabanov, Susan Burgee, Anthony Giunta
Multidisciplinary Analysis and Design (MAD) Center for Advanced Vehicles
Virginia Polytechnic Institute and State University
Blacksburg, Virginia 24061-0203

1. Introduction

This progress report covers work conducted under grant NAG1-1562 for the NASA High Performance Computing and Communications Program (HPCCP) from December 7, 1993, to October 3, 1994. The three tasks identified in our HPCCP proposal are:
  1. development of parallel multipoint approximation methods with primary application to the aerodynamic design of the High Speed Civil Transport (HSCT),
  2. use of parallel multipoint approximation methods for structural optimization of the HSCT,
  3. mathematical and algorithmic development including support in the integration of parallel computation for items (1) and (2).

During the past year, Virginia Tech acquired a twenty-eight node Intel Paragon parallel computer (a distributed memory architecture with 32 MB of memory at each node). Substantial research has been conducted using the Paragon to develop our variable-complexity multidisciplinary design optimization strategies. This research is detailed below.

2. Aerodynamic Analysis

The aerodynamic analysis of the HSCT is conducted for a vehicle modeled using twenty-six geometric and mission design variables along with fifty-five aerodynamic/geometric constraints. This analysis includes the use of algebraic weight relations for both structural and fuel weight estimation. In research conducted by members of the Multidisciplinary Analysis and Design (MAD) Center at Virginia Tech, convergence difficulties were encountered in the aerodynamic-structural optimization of the HSCT. The convergence problems were traced to numerical noise in the computation of aerodynamic drag components. This inhibited the use of gradient based optimization techniques. To address this problem, we developed a variable-complexity response surface technique which provides a smooth approximation to the noisy drag data [1]. As outlined in our HPCCP proposal, several sub-tasks were identified under item (1):
    a. definition of the approximate feasible design space using simple analysis methods,
    b. selection of points in the feasible space for refined analysis,
    c. application of response surface approximation methods.

Our research of the past year has addressed items (b) and (c) and was documented in Reference 1. Our ongoing and future efforts regarding item (a) are discussed in this report.

2.1 Example Design Problem

To develop our design methods, we created an example design problem with two of the eight design variables used to model the HSCT wing planform; the leading-edge and trailing-edge break locations of the wing. These two parameters determine the leading-edge and trailing-edge sweep angles and thus have a large effect on aerodynamic performance. We then calculated drag due to lift for various leading-edge and trailing-edge sweep angles. The numerical noise found in the drag due to lift data illustrated the need for a non-derivative based optimization technique. The use of response surfaces yielded a smooth approximation to this noisy data and provided an optimization method that was amenable to coarse-grained parallel computing.

With the drag due to lift database as a reference, the objective function for the example design problem was to minimize drag due to lift with respect to the two design variables. We then applied our variable-complexity response surface modeling strategy to this design problem.

2.2 Response Surface Methods

Response surfaces are used to approximate an objective function over an entire design space, or portions of it, using smooth functions. Since the topography of a multidimensional objective function generally is unknown and may have many local minima, the smooth response surface functions are selected so that the prominent features of the objective function are retained. Thus, in the optimization process the region where the global minimum exists may be readily found while inferior local minima may be avoided.

We investigated both polynomial and rational functions as response surface approximations to the drag due to lift data. The polynomial functions included a quadratic in two variables, along with bilinear, quadratic-linear, and biquadratic tensor products. The rational functions produced response surfaces similar to those obtained from the polynomials but at a higher cost. Therefore, we do not plan further use of rational functions.

The construction of a response surface from a polynomial with k coefficients requires a minimum of k function evaluations. Typically, 1.5k analyses are used to smooth out noise and local minima. Our research confirmed that approximately 1.5k function analyses were required to produce response surfaces which accurately approximated the global trends of the objective function data. However, the choice of points selected for evaluation of the objective function is of great importance to the accuracy of the response surface.

2.3 Point Selection Techniques

We have examined three design point selection and distribution techniques: D-optimal, central composite design, and random selection.

To explain the D-optimal criterion [2], or D-optimality, we consider the linear system Y=Xc, where Y is the m by 1 vector of objective function values, c is the k by 1 vector of coefficients to be estimated, and X is an m by k matrix of constants having rank k. The rows of matrix X are formed from the response surface functions which relate the independent variables to the evaluated objective function at each design point. In short, the D-optimality criterion states that the m points to choose are those which maximize the determinant |X'X|.

However, finding the m D-optimal points is not trivial since there are l!/(m!(l-m)!) combinations of m points from the set of l candidate points. For example, a small problem in two design variables may be to choose twenty-five points from 121 possible points. This leads to a total of 5.26x10^25 possible combinations, one or more of which are D-optimal. To counter this we have developed an efficient search routine which uses a genetic algorithm to identify the set of D-optimal points [1].

The second candidate point selection criterion we examined was central composite design (CCD). This criterion, which is based on design of experiments theory [3], uses m=2^n + 2n + 1 points, where n is the number of design variables. This is in contrast to the m=3^n points required for a full factorial design. Unfortunately, for twenty-six design variables, even CCD requires an unacceptably large number of evaluations. However, the CCD criterion provided a useful standard of comparison to the other point selection techniques.

The third point selection technique involved m unique points which were randomly chosen from the set of previously calculated drag due to lift data points. For this process a uniform, unique random integer generator was used.

Results of our study, some of which appear in Reference 1, indicated that the D-optimal point selection technique was superior to both CCD and random selection. Response surfaces formed from the D-optimal points provided significantly higher accuracy than the other methods for a given number of m points. For example, with a quadratic polynomial response surface, the same level of accuracy using thirty randomly selected points was attained using only ten D-optimal points.

3. Structural Optimization

The second goal outlined in the HPCCP proposal was the use of parallel response surface approximation methods for structural optimization of the HSCT. The structural optimization acutely needs parallelization because the optimization is repeated many times within the overall HSCT optimization. The first step in the application of the parallel computing structural analysis was to choose a finite element program that could be efficiently run on the Paragon. Three software packages were considered: NASTRAN, GENESIS, and MAESTRO.

NASTRAN does not currently have a parallel version and will not have one in the near future. Because NASTRAN is proprietary software it was not possible to get access to the source code to convert it for use on a parallel computer. However, NASTRAN will be used as a standard to check results from other programs in our future research. For that reason we developed a NASTRAN model of the HSCT.

GENESIS is a finite element structural optimization code developed and supported by Vanderplaats, Miura and Associates (VMA), Inc. An attempt was made to develop a coarse-grained parallel version of this code. However, GENESIS relies heavily on on disk input/output (I/O), which limits parallel performance on the Paragon. Thus, it was not possible to obtain speedup beyond a factor of 2.3 even with a large number of nodes. We are negotiating with VMA to obtain a reduced I/O version of GENESIS which should improve performance on the Paragon.

MAESTRO is a computer program for optimum design of large complex thin-walled structures developed by Professor Owen Hughes of Virginia Tech, and it is extensively used for ship design. It has the following features:

    (a) a rapid design-oriented finite element analysis for the complete structure,
    (b) an explicit evaluation of all limit states both at member and multi-member levels,
    (c) formulation of the linearized state equations, which utilize partial safety factors to achieve a consistent degree of structural reliability,
    (d) multiobjective optimization based on any combination of individual measures of merit.

Like GENESIS, MAESTRO suffers from excessive disk I/O. However, due to the availability of the source code and the help of Prof. Hughes, we developed a coarse-grained parallel version of MAESTRO by replacing disk I/O with memory usage. This was accomplished by converting all the intermediate temporary files into common blocks. This process required a significant amount of time to complete due to the size of the original code. The parallel version of MAESTRO is currently being tested for both accuracy and parallel performance.

4. Parallel Computation

A coarse-grained parallelization of the aerodynamic analysis modules within the full HSCT analysis code [4] has been developed. The parallelization makes use of a master-slave paradigm on the Paragon whereby one designated master node controls the data transfer and file I/O of the remaining slave nodes. This coarse-grained approach is used for the numerous independent analyses required for response surface construction.

Using one of the point selection methods described above, a group of analysis points is determined and input to the master node. The master node then computes the subset of the points which each slave node will analyze and sends that information to the appropriate slave. Both the master and slave nodes then analyze their respective subsets of the selected points and store the results in an array local to each node. When each slave has finished its portion of the analyses, it sends the array of analysis values to the master node for output.


Figure 1. Speedup obtained from parallelization of the aerodynamic analysis code.


Figure 2. Efficiency obtained from parallelization of the aerodynamic analysis code.

Speedup and efficiency results have shown improvement since our initial attempt at parallelization [5]. This improvement was a result of the following modifications to the aerodynamics code: incorporating input data directly into the analysis code, removing unnecessary output, and sending necessary output from the slave nodes to the master node for output. As evident in Figures 1 and 2, for a relatively small number of nodes (less than ten), reasonable speedup and efficiency were obtained from the coarse-grained parallelization. When the number of nodes was increased, speedup leveled off and efficiency was drastically reduced. This is a result of the large amount of temporary file I/O occurring during the analysis of each HSCT design point. Further, at the beginning and end of the aerodynamic analyses there is a portion of the HSCT code which must be executed serially. This also contributed to the unreasonably low speedup, compared to ideal linear speedup, as the number of processors increased.

5. Future Research Directions

Aerodynamic Analysis

We have completed a design problem involving two design variables in which the response surface approximation methods were demonstrated. Currently we are investigating design problems with four to eight design variables to further validate this methodology. In addition, we are implementing several dimensionality reducing strategies. First we use the the simple, inexpensive analysis methods in our variable-complexity modeling approach to identify the feasible regions of the design space. We then apply principal factor analysis [6] to identify the design variables which have the most impact on the overall HSCT design. Those variables having the most effect will be modeled using higher order response surface functions while those having less effect will be modeled using lower order functions. An example of such a response surface function is a quadratic-linear tensor product in which the variable x is modeled using a quadratic polynomial and the variable y is modeled with a linear polynomial.

Eventually we will apply this variable-complexity response surface design methodology to the full HSCT design problem which involves twenty-six design variables. In addition, we plan to integrate more detailed aerodynamic and structural analysis methods into the HSCT analysis software. We have begun initial evaluation of an Euler/Navier-Stokes solver for use with our HSCT design methodology and the development of a parallel version of MAESTRO was described above. The implementation of these more detailed analysis methods will be conducted concurrently with our parallelization efforts.

Structural Analysis

We plan to apply the coarse-grained parallel version of MAESTRO to variable-complexity structural optimization and to integrate MAESTRO into the HSCT design process. In particular, we plan to develop a response surface approximation for the ratio of wing structural weight obtained from weight equations to the weight obtained from structural optimization.

Using coarse-grained parallelization, structural optimization will be performed with a finite element program to analyze a large number of points in the design domain. Candidate points will first be screened using a weight equation to eliminate infeasible points. The D-optimal criterion will then be applied to select points for refined analysis from the set of feasible candidate points. Principal factor analysis will also be used to reduce the dimensionality of the design space. The approximation will provide a means of assessing the effects of aerodynamic changes on both structural weight and aircraft performance in our aerodynamic optimization process.

In addition, we plan to develop a fine-grained parallel version of the finite element program. It will be used for two-level structural optimization and for the same tasks as the coarse-grained parallel version.

Parallel Computation

The variable-complexity response surface approach permits coarse-grained parallelization with reasonable parallel performance only for less than ten processors. Future work is directed at improving the speedup and efficiency for more than ten processors, if possible. This will require a further reduction in the temporary file I/O as well as parallelization of the portions of the HSCT analysis code which require serial execution. Our work will focus on using both coarse- and fine-grained parallelization of our HSCT aerodynamic analysis code to improve parallel speedup and efficiency. This will require further parallel programming and algorithmic development.

6. References

  1. Giunta, A. A., Dudley, J. M., Narducci, R., Grossman, B., Haftka, R. T., Mason, W. H., and Watson, L. T., ``Noisy Aerodynamic Response and Smooth Approximations in HSCT Design,'' Proceedings of the 5th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Panama City Beach, FL, 1994, pp. 1117-1128. (AIAA Paper 94-4376)

  2. Box, M. J. and Draper, N. R., ``Factorial Designs, the |X'X| Criterion, and Some Related Matters,'' Technometrics, vol. 13, No. 4, 1971, pp. 731-742.

  3. Mason, R. L., Gunst, R. F., and Hess, J. L., Statistical Design and Analysis of Experiments, John Wiley & Sons, New York, N. Y., 1989, pp. 215-221.

  4. Hutchison, M. G., ``Multidisciplinary Optimization of High-Speed Civil Transport Configurations Using Variable-Complexity Modeling,'' Ph.D. Dissertation, VPI&SU, March 1993.

  5. Burgee, S., Giunta, A. A., Grossman, B., Haftka, R. T., and Watson, L. T., ``A Coarse Grained Variable-Complexity Approach to MDO for HSCT Design,'' Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, Editors: Bailey, D. H., Bjorstad, P. E., Gilbert, J. R., Masagni, M. V., Schreiber, R. S., Simon, H. D., Torczon, V. J., and Watson, L. T., SIAM, Philadelphia, PA, 1995, pp. 96-101.

  6. Lawley, D. N., and Maxwell, A. E., Factor Analysis as a Statistical Method, American Elsevier Publishing Co., New York, N.Y., 1971, pp. 15-18.

Publications

  1. Giunta, A. A., Dudley, J. M., Narducci, R., Grossman, B., Haftka, R. T., Mason, W. H., and Watson, L. T., ``Noisy Aerodynamic Response and Smooth Approximations in HSCT Design,'' Proceedings of the 5th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Panama City Beach, FL, 1994, pp. 1117-1128. (AIAA Paper 94-4376)

  2. Burgee, S., Watson, L. T., Giunta, A. A., Grossman, B., Haftka, R. T., and Mason, W. H., ``Parallel Multipoint Variable-Complexity Approximations for Multidisciplinary Design,'' Proceedings of the IEEE Scalable High-Performance Computing Conference, 1994, pp. 734-740.

  3. Burgee, S., Giunta, A. A., Grossman, B., Haftka, R. T., and Watson, L. T., ``A Coarse Grained Variable-Complexity Approach to MDO for HSCT Design,'' Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, Editors: Bailey, D. H., Bjorstad, P. E., Gilbert, J. R., Masagni, M. V., Schreiber, R. S., Simon, H. D., Torczon, V. J., and Watson, L. T., SIAM, Philadelphia, PA, 1995, pp. 96-101.