(Preliminary) SEP 2: Optimizing the SAGE library using Parallel Techniques

AUTHOR: William Stein

COPYRIGHT: GNU Free Documentation License, 2007.

Basic Principles

  1. Parallel methods should be viewed as a means to an end -- speedups. Never parallelize any computation except to speed up a calculation beyond what can be done using sequential techniques.
  2. Parallel methods should never completely replace sequential implementations. Parallel algorithms are often very complicated to understand and test, so we need to at a minimum have a randomized test function that compares with the output of purely sequential code.

  3. Do not write extremely complicated parallel code that nobody can understand or maintain. Because SAGE is an open source system that is widely developed, it is crucial that it be readable.

  4. It is *crucial* that implementation of parallel methods in SAGE have the following properties:
    • It can be done incrementally. One must be able to start with almost any specific operation or algorithm in SAGE and make a parallel version without having to drastically change code all over SAGE. Any proposed solutions that violate this fails our needs.
    • It doesn't depend on any libraries or tools that are not open source and free, and all dependencies must work on the SAGE target platforms: Linux, OS X, Windows, (and soon Solaris).
    • All dependencies for parallel algorithms must be included standard with SAGE.

Architecture

We propose that parallel optimizations for SAGE are carried out (in parallel!) at three distinct levels: low (multithreaded), medium (mpi), and high (dsage task farming).

1. Low level -- shared memory (mostly multicore desktop/laptop)

Proposed tool: the standard POSIX thread library pthread

Justification:

Design issues:

Problems:

2. Middle -- homogeneous trusted cluster

Proposed tool: ipython1 with MPI under the hood.

Justification:

Example problems:

3. High -- heterogenous task farm (both trusted and untrusted)

Proposed tool: dsage

Justification:

Example problems: