SICSA/NAIS Scottish Parallel Computational Mathematics Meeting (SPARC-M)

Friday 19th November 2010

Introduction

The meeting is open and interested participants are encouraged to attend. The meeting is joint between NAIS and SICSA and is funded by the SICSA Complex Systems Engineering (CSE) Theme.

Location

Boardroom
Gateway Building
University of St Andrews
North Haugh, St Andrews, Fife
KY16 9ST

Programme

• 10:30-11:00 arrivals and welcome coffee
• 11:00-13:00 talks:
  • 11:00-11:20 Reimer Behrends
  • 11:30-11:50 Chris Brown
  • 12:00-12:20 Jeff Blanchard
  • 12:30-12:50 Vladimir Janjic
• 13:00-14:00 lunch
• 14:00-15:30 talks:
  • 14:00-14:20 Einar Pius
  • 14:30-14:50 Alexander Konovalov
• 15:00-15:30 concluding discussion
• 15:30-16:00 tea
• 16:00 end of the meeting

• Reimer Behrends (University of St Andrews): Generating and verifying runtime correctness assertions for concurrent C programs
Abstract : HPC-GAP employs runtime assertions to guard shared memory accesses in the C kernel against race conditions. In this talk, we present a tool that can verify the correctness of these assertions and is also able to automatically generate them.

• Jeff Blanchard (University of Edinburgh and Grinnell College, USA): GPU implementations of compressed sensing algorithms
Abstract : Compressed sensing is a new perspective that inserts compression into the data acquisition. Remarkably, it has been proven that sensing can be performed at the optimal information rate using linear sensing. This linearity allows the reconstruction algorithms to be highly parallelised, perfectly suited for the new GPU HPC environment. We sketch compressed sensing and show the increases in speed achieved using GPUs.

• Chris Brown (University of St Andrews): Ever decreasing circles: a parallel skeleton for Orbit calculations in Eden
Abstract : The Orbit algorithm is widely used in symbolic computation, allowing the exploration of a solution space given some initial starting values and a number of mathematically-defined generators. In this paper, we consider how the Orbit algorithm can be encoded in Haskell, and thence how a parallel skeleton can be developed to cover a variety of Orbit calculations, using the Eden parallel dialect of Haskell. Our results with a synthetic benchmark on a modern multicore machine clearly demonstrate the potential of this skeleton to allow simple but effective parallel implementation of the Orbit algorithm, giving relative speedups of up to 8.295 on eight cores. They also demonstrate that a workpool implementation is more effective than a task farm for larger problem sizes, since better task distribution can be achieved. On eight cores, we achieve speedups of up to 8.295 for the workpool, versus 7.851 for the task farm, with a 9% reduction in runtime for the workpool.

• Vladimir Janjic (University of St Andrews): Load-Balancing of Irregular Parallel Applications on Computational Grids
Abstract : Parallel symbolic computations often have irregular parallelism, meaning that sizes of parallel tasks and the volume of communication between them can be highly variable (e.g. parallel mapping of Euler totient function over the list of integers, computing Groebner basis for a polynomial set, solving the system of linear equations). Doing efficient load balancing of such an applications on Computational Grids, which are characterized by variable powers of processing elements (PEs) and latencies between them is a challenging problem, due to irregularity in both the application itself and the computing environment on which it is executed. We investigate the ways in which certain information derived from application (such as application's task sizes) can be used to do good load balancing in Grid-GUM RTS for Glasgow Parallel Haskell.

• Alexander Konovalov (University of St Andrews): Parallel computations in modular group algebras
Abstract : We report about the parallelisation of the algorithm to compute the normalised unit group of a modular group algebra of a finite p-group over the field of p elements in the computational algebra system GAP. We present its distributed memory implementation using the new remote procedure call framework based on the the Symbolic Computation Software Composability Protocol (SCSCP). Using it, we were able for the first time to perform practical computations of normalised unit groups of modular group algebras of groups of orders 512 and 729.

• Einar Pius (University of Edinburgh): Automatic Parallelisation of Quantum Circuits
Abstract : In [1] a method for parallelising quantum circuits via applying optimising rewrite rules to the circuits representation in the Measurement Based Quantum Computing (MBQC) model was introduced. We wrote an application that uses this method to parallelise quantum circuits. A brief description of the parallelisation process and its implementation is given. We also demonstrate how the implemented method does to some of the Quantum Circuits.
[1] Anne Broadbent and Elham Kashefi. Parallelizing quantum circuits. Theoretical Computer Science, 410(26):2489–2510, 2009.

Registration

To register for the event or to view the list of registered participants click on the link "Participate" above.

Contact

Dr. Alexander Konovalov
School of Computer Science
University of St Andrews
Jack Cole Building, North Haugh
St Andrews, Fife, KY16 9SX
alexk at cs [dot] st-andrews [dot] ac [dot] uk