Functional Programming

Fully-funded PhD scholarship in parallel programming and dependent-types

The school of Computer Science at the University of St Andrews has a fully-funded scholarship available working in the Programming Languages Research Group with Dr Christopher Brown. Applications must be received by 1 March 2025.

Background

Algorithmic skeletons provide a convenient and high-level approach to writing efficient parallel software by leveraging common patterns of parallel behaviours. A skeleton library presents the programmer with a library of high-level parallel interfaces, abstracting away the low-level complexities of manually handling concurrency primitives, e.g. locking, synchronisation and thread creation. Skeletons give an excellent compromise between ease of programming and the ability to generate highly efficient parallel software. A wide range of skeletons have been developed for several different languages, including Fastflow, TBB, PPL and OpenMP. However, despite the proliferation of skeleton libraries, there is little support for an increasingly popular class of programming languages equipped with dependent types.

 

Dependently-typed programming languages address the problem of program safety by ensuring that code conforms to its specification. This is achieved by permitting types to depend on values, thereby allowing programmers to express logical properties, and proof, as intrinsic parts of their programs. This conformance is checked at compile-time. This interest in dependent-types has resulted in a number of functional languages such as pi-forall, Agda, Idris and Coq. However, despite these developments in types, these dependently-typed languages still lack a parallel implementation, making development of safe parallel programs impossible.

 

This project will explore approaches to designing and implementing a dependently-typed parallel programming language. These approaches will consider the technical challenges, but also balancing those with the high-level usability that skeletons bring and the performance expectations of a performant system. As part of this exploration, use-cases will also need to be developed, and the scientific evaluation of the performance of the system will need to be carried out.

Topics of Interest

This project is largely exploratory in nature, and may take several different approaches and directions, including (but not limited to):

  • Extending an existing dependently-typed language, such as Idris, with new concurrency primitives.
  • Designing and implementing an efficient parallel runtime system as a backend to the language.
  • Building on top of these primitives to provide dependently-typed concurrency behaviours, such as synchronisation points, channel behaviours, etc.
  • To design and implement a set of dependently-typed algorithmic skeletons such as farms and pipelines.
  • To explore and identify new skeletons that arise from writing dependently-typed programs.
  • To use dependent-types to encode safety and soundness properties and reason about these properties in a formal way.

The Scholarship

We have one fully-funded scholarship available, starting in September 2025, which will be awarded to competitively to the best applicant. The scholarship covers all tuition fees (irrespective of country of origin) and comes with a stipend valued at £19,705 per annum. More details can be found here: https://blogs.cs.st-andrews.ac.uk/csblog/2024/10/24/phd-studentships-available-for-2025-entry/

International applications are welcome. We especially encourage female applicants and underrepresented minorities to apply. The School of Computer Science was awarded the Athena SWAN Silver award for its sustained progression in advancing equality and representation, and we welcome applications from those suitably qualified from all genders, all races, ethnicities and nationalities, LGBT+, all or no religion, all social class backgrounds, and all family structures to apply for our postgraduate research programmes.

To Apply

Informal enquiries can be directed to Chris. Full instructions for formal applications can be found at https://www.st-andrews.ac.uk/computer-science/prospective/pgr/how-to-apply/

The deadline for applications is 1 March 2025.

 

Why Homotopy type Theory (HoTT) matters – Professor Thorsten Altenkirch

Abstract:
Dependent types are a wonderful way to construct correct functional programming and specify interfaces as Edwin has shown in his nice book on type driven development using a welsh dragon. But shall we go further in the esoteric world of homotopy type theory? I will try to motivate this and I am looking forward to some discussions with people who have a more pragmatic attitude to dependent types.

Event details

  • When: 25th May 2018 11:00 - 12:30
  • Where: Cole 1.33a
  • Format: Seminar

The OpenMP and MPI refactoring with ParaFormance – Turkey Alsalkini

Abstract:

The increasing complexity of codes with the growing number of cores that should be utilised make such codes hard to optimise and maintain. In this talk, we present the OpenMP and MPI refactoring implemented in the ParaFormance tool. This tool transforms the sequential code into parallel code able to run on shared memory machines. Further refactoring is implemented to adapt the source code to exploit a larger number of processors on large HPC clusters with message passing support. In addition, the resulting MPI code can be used by developers as a starting point for further optimisation. Both refactorings are preceded by an advanced safety checking which reports concurrency problems and gives hints and suggestions on how to fix them.

Event details

  • When: 17th May 2018 12:00 - 13:00
  • Where: Cole 1.33a
  • Format: Talk

A Type-System for describing System-on-a-Chip Architectures – Jan De Muijnck-Hughes

Title:
A Type-System for describing System-on-a-Chip Architectures

Abstract:
The protocols that describe the interactions between IP Cores on System-on-a-Chip (SoC) architectures are well-documented. These protocols described not only the structural properties of the physical interfaces but also the behaviour of the emanating signals. However, there is a disconnect between the design of SoC architectures, their formal description, and the verification of their implementation in known hardware description languages.

Within the Border Patrol project we are investigating how to capture and reason about the structural and behavioural properties of SoC architectures using state-of-the-art advances in programming language research. Namely, we are investigating using dependent types and session types to capture and reason about hardware communication.

In this talk I will discuss my work in designing a dependent type- system and corresponding language that captures and reasons about the topological structure of a System-on-a-Chip. This language provides correct-by-construction guarantees over:

  • the physical structure of an interaction protocol;
  • the adherence of a component’s interface to a given protocol; and
  • the validity of the specified connections made between components.

We provide these guarantees through the (ab)use of dependent types as presented in Idris; and abuse of indexed monads to reason about resource usage.

Given time I will give an account of how this language enables reasoning about SoC behaviour when considered in conjunction with Session Types.ssion Types.

Event details

  • When: 5th April 2018 12:00 - 13:00
  • Where: Cole 1.33a
  • Format: Talk

Diderot: A Parallel Domain-Specific Language for Image Analysis and Visualization – John Reppy

Diderot: A Parallel Domain-Specific Language for Image Analysis and Visualization

Abstract:
The analysis of structure in three-dimensional images is increasingly valuable for biomedical research and computational science. At the same time, the computational burden of processing images is increasing as devices produce images of higher resolution (e.g., typical CT scans have gone from 128^3 to roughly 512^3 resolutions). With the latest scanning technologies, it is also more common for the the values measured at each sample to be multi-dimensional rather than a single scalar, which further complicates implementing mathematically correct methods.

Diderot is a domain-specific language (DSL) for programming advanced 3D image visualization and analysis algorithms. These algorithms, such as volume rendering, fiber tractography, and particle systems, are naturally defined as computations over continuous tensor fields that are reconstructed from the discrete image data. Diderot combines a high-level mathematical programming notation based on tensor calculus with an abstract bulk-synchronous parallelism model. Diderot is designed to both enable rapid prototyping of new image analysis algorithms and high performance on a range of parallel platforms.

In this talk, I will give an overview of the design of Diderot and examples of its use. I will then describe aspects of its implementation with a focus on how we translate the notation of tensor calculus to efficient code. I will also briefly discuss the automated techniques we use to validate the correctness of the compilation process.

Diderot is joint work with Gordon Kindlmann, Charisee Chiw, Lamont Samuels, and Nick Seltzer.

Bio:
John Reppy is a Professor of Computer Science and a Senior Fellow of the Computation Institute at the University of Chicago. He received his Ph.D. from Cornell University in 1992 and spent the first eleven years of his career at Bell Labs in Murray Hill NJ. He has been exploring issues in language design and implementation since the late 1980’s, with a focus on higher-order, typed, functional languages. His work includes the invention of Concurrent ML and work on combining object-oriented and functional language features. His current research is on high-level languages for parallel programming, including the Diderot, Manticore, and Nessie projects.

Event details

  • When: 2nd April 2018 13:00 - 14:00
  • Where: Cole 1.33b
  • Format: Seminar

Compositional Coinduction with Sized Types – Dr. Andreas Abel

Abstract:

Formal languages and automata are taught to every computer science student.  However, the student will most likely not see the beautiful coalgebraic foundations, which use coindutive reasoning.

In this talk, I recapitulate how infinite tries can represent formal languages (sets of strings).  I explain Agda’s coinduction mechanism based on copatterns and sized types demonstrate that it allows an elegant representation of the usual language constructions like union, concatenation, and Kleene star, with the help of Brzozowski derivatives.

Event details

  • When: 16th February 2018 12:00 - 13:00
  • Where: Cole 1.33b
  • Format: Seminar

Simplifying ARM concurrency – Prof. Susmit Sarkar

ARM has a relaxed memory model, previously specified in informal prose for ARMv7 and ARMv8. Over time, and partly due to work building formal semantics for ARM concurrency, it has become clear that some of the complexity of the model is not justified by the potential benefits. In
particular, the model was originally non-multicopy-atomic: writes could
become visible to some other threads before becoming visible to all —
but this has not been exploited in production implementations, the
corresponding potential hardware optimisations are thought to have
insufficient benefits in the ARM context, and it gives rise to subtle
complications when combined with other ARMv8 features. The ARMv8
architecture has therefore been revised: it now has a multicopy-atomic
model. It has also been simplified in other respects, including more
straightforward notions of dependency, and the architecture now includes
a formal concurrency model.

This is work presented in POPL this year. I will also present some of
the background and context on relaxed memory which is absent from the
necessarily compressed talk format of POPL.

Event details

  • When: 22nd February 2018 12:00 - 13:00
  • Where: Cole 1.33a
  • Format: Talk

Dr. Vladimir Janjic – Efficient Dynamic Mapping of Parallel Applications to NUMA Architectures by Reinforcement Learning

Title: Efficient Dynamic Mapping of Parallel Applications to NUMA Architectures by Reinforcement Learning

 

Abstract: We present a dynamic framework for mapping threads and data of parallel applications to computational cores/memory nodes of parallel non-uniform memory architecture (NUMA) systems. We use a feedback-based mechanism where the performance of each thread is collected and used to drive the reinforcement-learning policy of assigning affinities of threads/data to CPU cores/memory nodes. The proposed framework can address different optimisation criteria, such as maximum processing speed and minimum speed variance. We demonstrate that we can achieve an improvement of 12% in execution time compared to the default Linux operating system scheduling/mapping of threads under varying availability of resources (e.g. when multiple applications are running on the same system).

Event details

  • When: 7th December 2017 12:00 - 12:00
  • Where: Honey 103 - GFB
  • Format: Talk