Show simple item record

dc.contributor.author
Besta, Maciej
dc.contributor.author
Fischer, Marc
dc.contributor.author
Ben-Nun, Tal
dc.contributor.author
Stanojevic, Dimitri
dc.contributor.author
de Fine Licht, Johannes
dc.contributor.author
Hoefler, Torsten
dc.date.accessioned
2020-08-31T09:20:40Z
dc.date.available
2020-08-27T03:06:27Z
dc.date.available
2020-08-31T09:20:40Z
dc.date.issued
2020-06
dc.identifier.issn
1936-7406
dc.identifier.issn
1936-7414
dc.identifier.other
10.1145/3377871
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/432797
dc.description.abstract
Developing high-performance and energy-efficient algorithms for maximum matchings is becoming increasingly important in social network analysis, computational sciences, scheduling, and others. In this work, we propose the first maximum matching algorithm designed for FPGAs; it is energy-efficient and has provable guarantees on accuracy, performance, and storage utilization. To achieve this, we forego popular graph processing paradigms, such as vertex-centric programming, that often entail large communication costs. Instead, we propose a substream-centric approach, in which the input stream of data is divided into substreams processed independently to enable more parallelism while lowering communication costs. We base our work on the theory of streaming graph algorithms and analyze 14 models and 28 algorithms. We use this analysis to provide theoretical underpinning that matches the physical constraints of FPGA platforms. Our algorithm delivers high performance (more than 4× speedup over tuned parallel CPU variants), low memory, high accuracy, and effective usage of FPGA resources. The substream-centric approach could easily be extended to other algorithms to offer low-power and high-performance graph processing on FPGAs.
en_US
dc.language.iso
en
en_US
dc.publisher
ACM
en_US
dc.subject
Graph computations
en_US
dc.subject
Energy-efficient graph processing
en_US
dc.subject
Streaming graph processing
en_US
dc.title
Substream-Centric Maximum Matchings on FPGA
en_US
dc.type
Journal Article
dc.date.published
2020-04-24
ethz.journal.title
ACM Transactions on Reconfigurable Technology and Systems
ethz.journal.volume
13
en_US
ethz.journal.issue
2
en_US
ethz.journal.abbreviated
ACM Trans. Reconig. Technol. Syst.
ethz.pages.start
8
en_US
ethz.size
33 p.
en_US
ethz.grant
DAPP: Data-Centric Parallel Programming
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02666 - Institut für Hochleistungsrechnersysteme / Inst. f. High Performance Computing Syst::03950 - Hoefler, Torsten / Hoefler, Torsten
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02666 - Institut für Hochleistungsrechnersysteme / Inst. f. High Performance Computing Syst::03950 - Hoefler, Torsten / Hoefler, Torsten
ethz.grant.agreementno
678880
ethz.grant.fundername
EC
ethz.grant.funderDoi
10.13039/501100000780
ethz.grant.program
H2020
ethz.date.deposited
2020-08-27T03:06:32Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-08-31T09:20:51Z
ethz.rosetta.lastUpdated
2022-03-29T03:00:24Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Substream-Centric%20Maximum%20Matchings%20on%20FPGA&rft.jtitle=ACM%20Transactions%20on%20Reconfigurable%20Technology%20and%20Systems&rft.date=2020-06&rft.volume=13&rft.issue=2&rft.spage=8&rft.issn=1936-7406&1936-7414&rft.au=Besta,%20Maciej&Fischer,%20Marc&Ben-Nun,%20Tal&Stanojevic,%20Dimitri&de%20Fine%20Licht,%20Johannes&rft.genre=article&rft_id=info:doi/10.1145/3377871&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record