PhD student in Computing Science with focus on Compilation of Linear Algebra Expressions

Department of Computing Science
The Department of Computing Science, characterized by world-leading research in several scientific fields and a multitude of educations ranked highly in international comparisons, is looking for a doctoral student to work on a compiler for linear algebra expressions.

The Department of Computing Science has been growing rapidly in recent years where focus on an inclusive and bottom-up driven environment are key elements in our sustainable growth. The 60 doctoral students within the department form a diverse group with different nationalities, backgrounds, and fields. If you work as a doctoral student with us you will receive the benefits of support in career development, networking, administrative and technical support functions along with good employment conditions.

See more information at:
https://www.umu.se/en/department-of-computing-science/

Is this interesting for you? We welcome your application no later than 30 January 2025.

Project description

Linear algebra expressions are evaluated in an efficient and robust way by mapping them to a carefully chosen sequence of calls to optimized functions as offered by libraries such as BLAS and LAPACK. The mapping is by no means unique, and different mappings differ in terms of time, space, and accuracy. When the sizes of the matrices are unknown at compile-time, as is often the case, then the problem is further complicated by the fact that no single mapping is optimal for all combinations of matrix sizes. As a consequence, any code generated (at compile-time) to evaluate the at run-time) must consist of more than just a single sequence of function calls.

We recently received a 4-year grant from the Swedish Research Council to investigate how to effectively compile linear algebra expressions when the matrix sizes are unknown at compile-time. The project aims to address the problem using e-graphs. An e-graph is a data structure commonly used in automated theorem provers and recently popularized for optimizing compilers and many other optimization tasks. We hypothesize that an e-graph would be an effective tool for discovering and encoding a large set of alternative ways of evaluating a particular expression with unspecified matrix sizes. When a concrete expression is evaluated at run-time, thus revealing the matrix sizes, an extraction algorithm can identify an optimal evaluation scheme for that particular instance of the expression from the compiled e-graph.

The project extends our previous work on linear algebra compilers: https://linnea.cs.umu.se/

This position is funded by the Swedish Research Council, through project 2024-04957 “Compiling General-size Linear Algebra Expressions using Equality Graphs”. The doctoral student will be part of the High-Performance and Automatic Computing group (HPAC), and jointly supervised by Paolo Bientinesi and Lars Karlsson.

HPAC’s webpage: https://hpac.cs.umu.se/

Admission requirements
The general admission requirements for doctoral studies are a second-cycle level degree or completed course requirements of at least 240 ECTS credits, of which at least 60 ECTS credits are at second-cycle level, or have an equivalent education from abroad or equivalent qualifications. To fulfill the specific entry requirements for doctoral studies in computing science, the applicant is required to have completed at least 90 ECTS credits in computing science. Applicants who otherwise have acquired skills that are deemed equivalent are also eligible.

Strong command of both written and spoken English language is a key requirement.

You are expected to have solid foundations in programming languages, compilers, as well as algorithms and data structures. Proficiency in C, C++, and/or Rust is a requirement.

It is a strong merit to have previous experience with e-graphs, or is familiar with theory and algorithms used by, for example, proof assistants, term rewriting systems, optimizing compilers, program analysis tools, constraint solvers, or similar.

Familiarity with linear algebra libraries and high-performance computing is a merit, but not a requirement.

About the position
The position provides you with the opportunity to pursue PhD studies in Computing Science for four years, with the goal of achieving the degree of Doctor of Philosophy in Computing Science. While the position is mainly devoted to PhD studies (at least 80% of the time), it may include up to 20% department service (usually teaching). If so, the total time for the position is extended accordingly, resulting in a maximum of five years.

The procedure for recruitment for the position is in accordance with the Higher Education Ordinance (chapter 12, 2§) and the decision regarding the position cannot be appealed.

The candidate is expected to start as early as possible and no later than September 2025.

Application
Applications must be submitted electronically using the e-recruitment system of Umeå University.

A complete application should contain the following documents:

• A cover letter that motivates the interest in the position and that describes how the qualifications and experience are relevant to the employment (maximum 2 A4 pages with 11pt font). 
• A curriculum vitae.
• Reprints / copies of completed BSc and/or MSc theses and other relevant publications, if any.
• Copies of degree certificates, including documentation of completed academic courses and obtained grades.
• Contact information for three reference persons.
• Documentation and description of other relevant experiences or competences, including software projects.

The application must be written in English or Swedish. If attached documents are written a different language, then a translation to English or Swedish must be included. Attached documents must be in pdf format. Applications must be submitted electronically using the e-recruitment system of Umeå University, and be received no later than 2025-01-30.

Selected applicants will be invited for an interview round, including a programming assignment.

For additional information, please contact Paolo Bientinesi (pauldj@cs.umu.se).

We look forward to receiving your application!