Analysis of Graph Processing in Reconfigurable Devices for Edge Computing Applications

Kaan Olgu, Kris Nikov, Jose Nunez-Yanez

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

Graph processing is an area that has received significant attention in recent years due to the substantial expansion in industries relying on data analytics. Alongside the vital role of finding relations in social networks, graph processing is also widely used in transportation to find optimal routes and biological networks to analyse sequences. The main bottleneck in graph processing is irregular memory accesses rather than computation intensity. Since computational intensity is not a driving factor, we propose a method to perform graph processing at the edge more efficiently. We believe current cloud computing solutions are still very costly and have latency issues. The results demonstrate the benefits of a dedicated sparse graph processing algorithm compared with dense graph processing when analysing data with low density. As graph datasets grow exponentially, traversal algorithms such as breadth-first search (BFS), fundamental to many graph processing applications and metrics, become more costly to compute. Our work focuses on reviewing other implementations of breadth-first search algorithms designed for low power systems and proposing our solution that utilises advanced enhancements to achieve a significant performance boost up to 9.2x better performance in terms of MTEPS compared to other state-of-the-art solutions with a power usage of 2.32W.

Original languageEnglish
Title of host publicationProceedings - 2022 25th Euromicro Conference on Digital System Design, DSD 2022
EditorsHimar Fabelo, Samuel Ortega, Amund Skavhaug
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages16-23
Number of pages8
ISBN (Electronic)9781665474047
ISBN (Print)978-1-6654-7405-4
DOIs
Publication statusPublished - 4 Jan 2023
Event25th Euromicro Conference on Digital System Design, DSD 2022 - Maspalomas, Spain
Duration: 31 Aug 20222 Sept 2022

Publication series

NameProceedings - 2022 25th Euromicro Conference on Digital System Design, DSD 2022
ISSN (Print)2639-3859
ISSN (Electronic)2771-2508

Conference

Conference25th Euromicro Conference on Digital System Design, DSD 2022
Country/TerritorySpain
CityMaspalomas
Period31/08/222/09/22

Bibliographical note

Publisher Copyright:
© 2022 IEEE.

Keywords

  • bfs
  • breadth-first
  • computing
  • edge
  • FPGA
  • graph
  • graph processing
  • low-cost
  • search
  • zedboard

Fingerprint

Dive into the research topics of 'Analysis of Graph Processing in Reconfigurable Devices for Edge Computing Applications'. Together they form a unique fingerprint.

Cite this