Effective use of the recent innovations in computer architecture can be limited by difficulties in writing functionally correct parallel applications that also achieve high performance. Hybrid algorithms combine the advantages of more than one computing method to optimize the solution of mathematical problems with large numbers of parameters and many solutions that are “best” only for limited ranges of a particular parameter or set of parameters (local minima).

The University of Texas at El Paso (UTEP) associate professors Miguel Argáez and Leticia Velázquez (mathematical sciences) and computational science graduate students Miguel Hernandez IV, Carlos Ramirez, and Reinaldo Sánchez are developing mathematical and computational tools that facilitate the implementation of problem-solving applications on highly parallel systems. They are also demonstrating a practical migration path from current programming approaches to a transaction-based model.

Step by Step
The mathematical side of this project focuses on a hybrid algorithmic approach for solving general optimization problems, including automated parameter estimation problems (see schematic, next page). In particular, efforts are focused on global optimization problems having many local minima—that is, finding a set of parameters that works best over the entire region of interest from a large group of locally viable candidates.

The UTEP team has developed a method that begins with one of several global stochastic techniques: Simultaneous Perturbation Stochastic Approximation (SPSA), Global Levenberg–Marquardt (GLM), Genetic Algorithms (GA), or Simulated Annealing (SA). These techniques are sampling methods that perform a global search of the parameter space (illustration, below left). This search may start from multiple initial guesses (parallel multi-start). In many real applications, it is difficult or impossible to compute derivatives of the function being optimized (gradient directions in which the function is increasing or decreasing). Most of these global methods do not use derivatives, and thus do not require this information in order to work.

The stochastic search produces target regions where the global optimal solution may lie. A surrogate model is constructed by filtering data points from these regions. The surrogate model behaves in a mathematically similar fashion to the function of interest while being less demanding in terms of computational resources. In particular, multiquadric, cubic and Gaussian radial basis functions are selected to build the surrogate model.

The surrogate model is used to perform local searches, using the Newton–Krylov Interior Point (NKIP) algorithm developed by the UTEP team. This method calculates gradients and evaluates whether a given gradient is steep enough to lead to a global minimum. Moreover, the algorithm allows the inclusion of physical bounds for obtaining feasible approximate solutions to the problem.

Making it Work
Implementing these algorithms for a parallel computing environment requires several novel approaches. For example, introducing transactions (individual small operations) as the key abstraction for expressing parallelism facilitates maintaining a computer system in a known, consistent state by ensuring that interdependent operations are either all completed successfully or all canceled successfully.

The UTEP group is developing a simple distributed-memory programming model that can scale to systems with thousands of processors. Their C version software framework (also available in Matlab) is being tested on two high performance machines: the Mana Dell Tera-Scale HPC system (Maui High Performance Computing Center, Air Force Research Laboratory) and the Lonestar Dell Linux cluster (Texas Advanced Computing Center, University of Texas).

The first version of a semigraphical ncurses-type software interface for the hybrid optimization algorithm has been completed. (ncurses is a library of functions written for Unix applications.) This interface enables the user to call the HPC hybrid optimization C code with a choice of global methods: SPSA, GLM, GA, or SA. It also enables the use of a surrogate model and an option to continue with NKIP. Documentation for this interface is in progress, along with a manual for the hybrid algorithm in general.

Applications
One area of particular interest is estimation theory—a branch of statistics that is often used to assist in interpreting the results of scientific experiments. Mathematical calculations use observable information as input to produce an approximation to the parameter of interest when an exact solution is not possible. Such techniques are especially useful for signal processing and telecommunications problems, as well as for scientific applications with irregular and adaptive behavior.

Hybrid optimization codes developed as a result of this work are being applied to Stanford’s AERO-F computational fluid dynamics code. This code is used by AHPCRC researchers in Technical Area 1 to develop flapping and twisting wing models for micro-aerial vehicles, hummingbird-sized airborne vehicles that can be used for sensing and surveillance. Large-scale simulations using this code are planned for 2010.

The hybrid algorithm is also being implemented in the PyADH simulator’s adaptive hydraulics modeling modules from the Engineer Research and Development Center, U.S. Army Corps of Engineers, for use on the Lonestar cluster. Large-scale applications are being prepared to run on this simulator in 2010.

Moving forward
Uncertainty issues and regularization techniques for the hybrid algorithm are currently being evaluated. Additional functionalities are being developed, for inclusion in the hybrid package. For example, users will have the option to approximate derivatives using random forward and backward differences. They can compare the results with the well-known difference approximations used in most algorithms. The goal of this effort is to reduce the number of function evaluations per iteration.

Recently, the UTEP team proposed a path-following fixed-point method for large-scale l1 underdetermined problems and their applications in compressed sensing (a technique for acquiring and reconstructing signals). Also, the team has developed a projected conjugate gradient algorithm for solving overdetermined systems in lq quasinorms.

Source: AHPCRC Bulletin Vol. 2 No. 1 (2010)