Jan Verschelde

With Graphics Processing Units (GPUs) capable of teraflop performance double digit speedups over single core execution are possible. An alternative application of GPU acceleration is quality up: if we can afford to wait the same amount of time as on a single core, then how much more accurately can we compute the same result? A multiple double is an unevaluated sum of doubles and multiple double arithmetic exploits the optimized hardware for floating-point arithmetic, with predictable overhead and simple memory management.

The talk will present experiences with software package QDlib (Hida, Li, Bailey, 2001) and the more recent CAMPARY software (Joldes, Muller, Popescu, Tucker, 2016) on NVIDIA GPUs, in particular the P100, V100, and RTX 2080. Code to evaluate and differentiate polynomials at power series and to accelerated the blocked Householder QR in multiple double precision is used in the software PHCpack, publicly available at github, and released under the GNU GPL v3.0 license.

The source code is located at https://github.com/janverschelde/PHCpack

The objective is to demonstrate the making of Ada software available to Python and Julia programmers using GPRbuild. GPRbuild is the project manager of the GNAT toolchain. This talk will first present a self-contained small example to illustrate the making of shared object files from Ada software, so the software can be used in Python and Julia. The second part of the talk concerns the application to PHCpack, a free and open source software package to solve polynomial systems by homotopy continuation methods, written mainly in Ada, and available at github at https://github.com/janverschelde/PHCpack.

Tasks in Ada are effective to speed up computations on multicore processors. In writing parallel programs we determine the granularity of the parallelism with respect to the memory management. We have to decide on the size of each job, the mapping of the jobs to the tasks, and on the location of the input and output data for each job.

A multitasked Newton's method will show the effectiveness of Ada to speed up the computation of power series. This application belongs to the free and open source package PHCpack, a package to solve polynomial systems by polynomial homotopy continuation.

PHCpack is a software package for solving polynomial systems with homotopy continuation. The talk will tell the story of the development of phcpy, a scripting interface for PHCpack, which has been under development for the past five years. One result is the availability of the software in a Python2, Python3, and SageMath kernel of JupyterHub, which runs at https://pascal.math.uic.edu/hub/login (www.phcpack.org).

Other relevant details: https://arxiv.org/abs/1310.0056 (EuroSciPy 2013 proceedings paper) http://homepages.math.uic.edu/~jan/phcpydochtml/index.html (documentation) https://github.com/janverschelde/PHCpack (github repository)

PHCpack is a software package for solving polynomial systems with homotopy continuation. The talk will tell the story of the development of phcpy, a scripting interface for PHCpack, which has been under development for the past five years. Working on phcpy involved the following activities: (1) Accessing code in a shared object file from Python. (2) Documenting the code with Sphinx. (3) CGI processing, managing user information and user data. (4) Making the code available online with JupyterHub. The presentation will provide examples of the expertise acquired for the four tasks mentioned above.

Tasking in Ada provides an effective tool for shared memory parallelism. An "any time" algorithm is an algorithm that, given some more resources, will improve the accuracy of an estimate. For example, consider the estimation of Pi by a Monte Carlo method. With multitasking, the status of the running of an "any time" algorithm can be monitored without interrupts.

The programming concepts will be illustrated with examples of algorithms in polyhedral geometry. The demonstrated code belongs to the free and open source PHCpack, at https://github.com/janverschelde/PHCpack.

Tasking in Ada provides an effective tool for shared memory parallelism. For coarse grained regular parallelism, load balancing works with one single job queue. For finer grained and irregular parallelism, work stealing balances the load with multiple job queues. The programming concepts will be illustrated with examples of algorithms in polyhedral geometry. The demonstrated code belongs to the free and open source PHCpack, at https://github.com/janverschelde/PHCpack.

Consider the organization of parallel heterogeneous computations. The sequential version runs in two stages: the first stage produces jobs that can be computed independently from each other in the second stage. The producer in the first stage is executed by one task, while the other tasks compute the jobs from the second stage, as the jobs are managed by a queue, implemented by a thread safe package.

This design will be illustrated with an application that involves the refactoring of code in the free and open source package PHCpack, a package to solve polynomial systems by polynomial homotopy continuation.

PHCpack originated from bundling programs to solve polynomial systems with symbolic-numeric and polyhedral methods. The core of PHCpack consists mainly of Ada code, with interfaces to C and Python. Its blackbox solver is accessible from various scientific software packages such as Macaulay2, Maple, MATLAB, Octave, and Sage.

The goal of the talk is to explain the application of software engineering principles and the role of Ada in the development of PHCpack.

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.