General areas of interest:
Please contact via: r.j.bradford@bath.ac.uk
I am happy to listen to students' ideas for projects.
Joint with Prof Davenport
There are many interesting algorithms in Computer Algebra. This project is to take your favourite CA algorithm and make it run in parallel.
This could be using Isambard, the regional (Tier 2) HPC resource (10,496 Arm cores)
The choice of parallel architecture (shared memory, distributed memory, etc.), programming approach (pthreads, TBB, OpenMP, MPI, etc.) and language (C, C++, etc.) will be your choice, as appropriate for the CA algorithm.
Pre-requisite knowledge: computer algebra, parallelism, programming, CM30070, CM30078.
Suggested topics:
"Parallel computation of the rank of large sparse matrices from algebraic K-theory" Dumas
-- millions of rows, Coppersmith, Wiedemann, etc.
"Multithreaded parallel implementation of arithmetic operations modulo a triangular set" Moreno Maza
-- parallelises FFT
"Component-level parallelization of triangular decompositions" Moreno Maza
-- large shared memory
"On the parallel computation of comprehensive Gröbner systems" Shutaro Inoue, Yosuke Sato
"POSIX threads polynomials(PTPol): a scalable implementation of univariate arithmetic operations" Mohab Safey El Din, Philippe Trébuchet
-- C library, OpenMP
"A complete modular resultant algorithm targeted for realization on graphics hardware" Pavel Emeliyanenko
-- resultants on GPUs, CUDA
"Parallel Gaussian elimination for Gröbner bases computations in finite fields" Faugère,
-- mod a large prime, C
"Parallel sparse polynomial division using heaps" Monagan
-- fine grain parallelism, C
"Parallel sparse polynomial interpolation over finite fields" Monagan
-- probabilistic
"Parallelising the computational algebra system GAP" R. Behrends, A. Konovalov, S. Linton, F. Lübeck, M. Neunhöffer
-- report on progress
"Modular GCD" Monagan
-- written in Cilk, will need translating to OpenMP or TBB
"Polynomial multiplication mod p" Monagan
-- Cilk
"Faugere F4" Monagan
-- Cilk
"Fast Parallel Multi-point Evaluation of Sparse Polynomials" Michael Monagan
-- Cilk
"Computing Tropical Prevarieties in Parallel" Anders Jensen, Jeff Sommars, Jan Verschelde
-- GMP, Parma Polyhedral Library (PPL)
"Meataxe64: High performance linear algebra over finite fields" Richard Parker
-- ab initio code for large matrices mod p
"An Algorithm For Splitting Polynomial Systems Based On F4" Monagan
-- mod p, in C
parallel bignums (modular or digit-by-digit)
parallel polynomials
parallel GCD (bignum or polynomial), and so on
As we more into the world of multicore processors, programmers are having problems making the best use of the CPU cycles available. So several programming paradigms have arisen. They include
This project is to take as many of the above as feasible, take some algorithms, implement them and compare the simplicity of use, accuracy of code, speed of final code and anything else interesting. (This project is not about parallel speedups of code.)
Pre-requisite knowledge: C programming, parallelism
Indicative reading: Above.
Apple's thesis is that queues are simpler, more lightweight and easier to program with than the traditional threads and locks.
This project is to investigate these claims. You should choose an implements a wide variety of programs in both "traditional" POSIX pthreads and in GCD. Then compare the experience of using both: for example, ease of use; conceptual hurdles in learning; rate of occurrence of parallelism bugs; easy of detection of parallelism bugs; efficiency of code; and so on.
Pre-requisite knowledge: programming using GCD and pthreads, parallelism
Indicative reading: various places on the Web
The University of Bath is a fairly complicated place: even though there is a simple East/West compass arrangement of buildings, many people find it difficult to find individual rooms. The many interconnecting corridors are particularly confusing.
This project is to create a route planner phone app (Android/iPhone/both) that will find a route from the user's position to a requested room.
Additional features might include
Pre-requisite knowledge: programming, app creation
Graphics cards contain some very powerful processors these days. Lately the idea has arisen of using these processors for general computing, not just graphical: this is the premise of GPGPUs (general purpose graphics processors).
CUDA and OpenCL are APIs that allow us to tap into the power of such coprocessors: the intent is that programs written to such APIs will be easily portable to different graphics cards.
This project is to make libraries that enable these APIs to use other parallel architectures. For example
And so on. So a program written using OpenMP would be runnable (likely much less efficiently) on a graphics card, etc. This would be useful for developing and debugging such programs.
Pre-requisite knowledge: Programming skills, parallelism
Indicative reading: see Comparison of Parallelism Techniques, above
There are two main languages in current use for programming GPUs: CUDA and OpenCL. While OpenCL is the "standard", it is CUDA that nearly everybody uses. It would be useful to enable CUDA programs to run on OpenCL.
This project is to
Pre-requisite knowledge: Programming skills, parallelism
There are two main languages in current use for programming GPUs: CUDA and OpenCL. While OpenCL is the "standard", it is CUDA that many people use. It would be useful to enable CUDA programs to run on OpenCL. Such a translator exists, but it seems primitive (much is left to the programmer to do) and unmaintained. Another, CU2CL, has progressed further and needs investigating.
This project is to
Pre-requisite knowledge: Programming skills, parallelism, parsing, compiling
C++ Accelerated Massive Parallelism is a modified C++ intended to make writing parallel code easier. This uses C++-style mechanisms to hide the complexities.
This project is to compare writing in C++ AMP with a few existing methods, including at least OpenCL and CUDA.
You will
Pre-requisite knowledge: C++ programming, parallel computing.
GPUs are very good at massive floating point computations. At least, single precision (float) computations. Double precision (double) is much less well supported. This is due to a couple of reasons
Thus, for example, the latest consumer GPUs from Nvidia have double precision performance 1/32 of their single precision performance.
This project is to revive the ancient technique of "double-single" floating point: namely taking two single precision numbers and glueing them together to make a (nearly) double precision number.
The project will code the basic arithmetic operations and some transcendental functions in a library in CUDA (similar to C++). Then compare the implementation against true double floating point to see if it can do better than the 1/32 slug factor.
Pre-requisite knowledge: C++ programming,
Indicative reading: IEEE floating point standards, double-double code from here. GPU code here.
The output from tcpdump of network traffic between two hosts is somewhat difficult to read. This project is to take such an output (live or from a dump) and produce an arrows diagram such as we see in Stevens' book. This would be annotated with (a configurable amount of) information, e.g,. new connection, dup ACK, etc. More advanced would be to spot Nagle and other TCP strategies.
Pre-requisite knowledge: programming skills, Networking course
Indicative reading: Stevens "TCP/IP Illustrated", a standard Unix graphics system, such as Qt or FLTK.
Recently there has been growing interest in a method that unifies discrete and continuous sytems in a single framework called "Time Scales". This project will involve writing a comprehensible introduction to Time Scales and implementing a selection of generic algorithms (probably using Maple).
Pre-requisite knowledge: Mathematics, programming skills.
Indicative reading: Stefan Hilger. "Differential and difference calculus - unified". In Nonlinear Analysis, Theory, Methods and Applications, 30, 2683-2694, 1997. Available from WebCat E-Journals.
On the face of it, infinite series like
1-1+1+1-1+...
and
1-2+4-8+16-...
do not have meaningful sums: they are divergent. Such sums appear in various parts of physics, particularly quantum mechanics (where it is called regularization).
It has been found that it is possible to extend the definition of "summation" to give them precise and useful values, e.g., 1-1+1+1-1+... "sums" to 1/2.
This project is to take some of the forms of extended summation and implement them in Maple to provide summation for a reasonable range of divergent series. Thus abel_sum((-1)^n,n); will return 1/2.
Pre-requisite knowledge: Computer Algebra; CM30070
Indicative reading: "Divergent Series", GH Hardy, 512.95 HAR. Wikipedia, MathWorld, PlanetMath, PlanetMath Wikipedia, Wikipedia and many other places on the Web.