PhD Project in High-Performance Graph Processing

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.

Entrance requirements

Graduate
The minimum academic requirement for admission to a research degree programme is normally an Upper Second Class Honours degree from a UK or ROI HE provider, or an equivalent qualification acceptable to the University. Further information can be obtained by contacting the School.

International Students

For information on international qualification equivalents, please check the specific information for your country.

English Language Requirements

Evidence of an IELTS* score of 6.0, with not less than 5.5 in any component or equivalent qualification acceptable to the University is required (*taken within the last 2 years).

International students wishing to apply to Queen’s University Belfast (and for whom English is not their first language), must be able to demonstrate their proficiency in English in order to benefit fully from their course of study or research. Non-EEA nationals must also satisfy UK Visas and Immigration (UKVI) immigration requirements for English language for visa purposes.

For more information on English Language requirements for EEA and non-EEA nationals see: www.qub.ac.uk/EnglishLanguageReqs.