Numerical methods for high performance computing

April 25, 2014

Ralf ÖstermarkMy research focuses on designing nonlinear optimization tools and vector-valued time series algorithms on parallel computers. The computational resources can be linked as support libraries to the Genetic Hybrid Algorithm (GHA). I have been developing GHA since the beginning of 2000. The scalability of the platform has been previously demonstrated on the massively parallel supercomputers Cray T3E and IBMSC at the Centre of Scientific Computing (CSC) Helsinki in vector-valued time series estimation, MINLP and difficult simulation problems.

During 2009-2011, I have demonstrated scalability of GHA on Cray XT at CSC with up to 4048 cores and at the Jugene supercomputer within the PRACE project with up to 65536 cores. The computational platform does not restrict the number of processors to be used. The possible limitations arise from the computational problem at hand.

GHA is listed on the web-site of CSC as one of the few fully scalable parallel algorithms with permission to use all available cores.  Cray XT belongs to the group of the top 500 parallel supercomputers in the world. During 03/2013 I demonstrated scalability of GHA + its MINLP switch board on the new Cray XC30 supercomputer at CSC with the maximum number of processors made available for testing. The corresponding web site is currently under construction at CSC. The test was conducted on my current research topic, a non-convex scheduling-problem with discontinuous, multi-modal parameter generating functions.

In November 2012, Cray XC30 reached the position #118 of the Top500 list of fastest supercomputers in the world, with a theoretical peak of 244.9 teraflop/s (TF). The measured Linpack benchmark performance is 211.8 TF, giving a sustained performance of 86%. (http://www.top500.org)

I have shown that the complexity of binary mixed-integer-nonlinear problems can be significantly reduced on parallel processors using asynchronic mesh interrupts and binary coding of local box constraints. The local branch-and-bound trees are solved using efficient non-linear optimization algorithms monitored by GHA. Lately, I have extended the approach to general discrete valued MINLP-problems using shifted Gray-coding of the local box constraints. This approach allows a complete mapping of the Cartesian search space in MINLP-problems and a corresponding simplification of the computational task for the local processors.

GHA is founded on two main principles: (i) allowing meaningful connections to available high-performance algorithms, (ii) maximizing the intelligence of the processors with respect to computational resources. These principles support the construction of scalable algorithms for numerical problems in computational finance and engineering.

For example, disjunctive programming problems can be solved geno-mathematically or in parallel using Gray-coding of the disjunctions and a switch board for the truth-conditions, connected to high-performance non-linear programming algorithms. This way, the exponential increase of the variable space required by MINLP-formulations can be completely avoided or at least significantly reduced, the quality of the solution improved and the time absorbance of the solution process reduced in several important cases.

In difficult quadratic assignment problems with a small integer gap, the geno-mathematical tools applied on parallel processors can yield near-optimal solutions without an excessive branch-and-bound tree.

In finance, the computational tools of GHA are of relevance when quantifying the risk surface of the firm or solving multi-period models of portfolio selection. In these problems, parallel programming is often a practical necessity.

The heap memory usage of GHA and the MINLP switch board was tested using Valgrind in March 2013 by the author on the Linux main frame computer at Åbo Akademi University on 40000 MINLP-problems with average branch-and-bound tree size 22. The Valgrind-report indicated zero memory leakage. (cf. Valgrind.org on the powerful debugger).

Contact information

Ralf Östermark
Professor of financial accounting and optimization systems
School of Business and Economics at Åbo Akademi University
Henriksgatan 7, 20500 Åbo, Finland

E-mail: ralf.ostermark@abo.fi

The Genetic Hybrid Algorithm (GHA) user’s guide is available here.

Full publication list available here.

Cooperation partner: Process Flow Ltd.