Writing parallel versions for shared memory multi-core computers with Ada tasks requires minimal modifications of the original source code. For pleasingly parallel computations we experienced almost optimal speedups. If we can afford to spend the same amount of time as one core, then we can ask how much better (e.g.: how much more accurate) we can solve a problem with p cores. This leads to the notion to "quality up". Similar to speedup factors, we can compute "quality up" factors.
In this talk we report on our coding efforts to write multi-core versions of the path trackers in PHCpack, a free and open source software package to solve polynomial systems. We started investigating the use of multi-threading to compensate for the overhead of double double and quad double arithmetic.
PHCpack is a software package to solve polynomial systems with homotopy continuation methods. The Ada 83 code of version 1.0 was archived as Algorithm 795 by ACM Transactions on Mathematical Software in 1999. Version 2.0 was rewritten using concepts of Ada 95. Multitasking was introduced in version 2.3.45. Its current version 2.3.84 is available on GitHub.
PHCpack relies on two external software packages: (1) the QD library of Y. Hida, X.S. Li and D.H. Bailey for double double and quad double floating point arithmetic; and (2) MixedVol by T. Gao, T.Y. Li and M. Wu for a faster mixed volume computation. The advantages of double double arithmetic are its simple memory management (a double double is stored in the same way as a complex number) and its predictable cost overhead (just as complex arithmetic). In joint work with Genady Yoffe, we experienced that on 8 cores may already be sufficient to compensate for the cost overhead caused by double double arithmetic.
As computers become more powerful and larger problems lead to more propagation of numerical errors, it may well happen that double double arithmetic replaces common double precision arithmetic.
Speakers: Jan Verschelde