High-Performance Graph Processing
Applications are now CLOSED
Overview
Many disciplines rely heavily on the efficient analysis of graph-structured data, e.g., bio-informatics and computational genomics, cybersecurity, epidemiology, biology, and social sciences. Graphs can become very large, prompting the use of clusters of computers to achieve fast turn-around times. However, clusters pose multiple challenges to efficient computation, in particular for graph analytics. Very often, graphs have skewed degree distributions, making it hard to partition them properly across the nodes of the cluster. Poor partitioning inflates network communication volume, increases workload imbalance and potentially results in redundant work. Graph analytics are very often communication-bound and spend significant time waiting on network communication to complete. By consequence, constructing fast and energy-efficient graph analytics algorithms with good parallel scalability is non-trivial.
The aim of this PhD project is to analyse and design efficient algorithms for hard graph analytics problems, aiming to shed light on one of these questions (each question could be a different PhD project):
1. How can we combine the goals of parallel scalability and energy-efficiency, given that increasing parallelism for an irregular computation has limited returns on efficiency?
2. How can we design architecture-aware algorithms that adapt the choice and parameterisation of the performance optimisations to the specifics of the memory hierarchy and coherence mechanism?
3. How can we apply algorithmic choice (selecting one of multiple algorithms that compute the same result but with different performance on relevant inputs) in the context of NP hard algorithms such as subgraph isomorphism and clique problems?
4. How can we trade accuracy of computation against reduced energy consumption and increased performance?
You will investigate novel algorithms and their implementation paying attention to both (theoretical) algorithmic techniques and their efficient implementation. Hereto, you can build on our prior research on graph processing, including the GraphGrind, LaganLighter and Graptor graph processing systems, and research results on clique and graph isomorphism problems.
Funding Information
To be eligible for consideration for a Home DfE or EPSRC Studentship (covering tuition fees and maintenance stipend of approx. £19,237 per annum), a candidate must satisfy all the eligibility criteria based on nationality, residency and academic qualifications.
To be classed as a Home student, candidates must meet the following criteria and the associated residency requirements:
• Be a UK National,
or • Have settled status,
or • Have pre-settled status,
or • Have indefinite leave to remain or enter the UK.
Candidates from ROI may also qualify for Home student funding.
Previous PhD study MAY make you ineligible to be considered for funding.
Please note that other terms and conditions also apply.
Please note that any available PhD studentships will be allocated on a competitive basis across a number of projects currently being advertised by the School.
A small number of international awards will be available for allocation across the School. An international award is not guaranteed to be available for this project, and competition across the School for these awards will be highly competitive.
Academic Requirements:
The minimum academic requirement for admission is normally an Upper Second Class Honours degree from a UK or ROI Higher Education provider in a relevant discipline, or an equivalent qualification acceptable to the University.
Project Summary
Prof Hans Vandierendonck
Full-time: 3 or 3.5 years