• Home
• People
• Jobs
• Visit
• Thesis Topics
• Publications
• Conference Rankings
• Research
• Bcast
• Teaching
• Contact

SPONSORS

COLLABORATIONS

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

M. Besta, R. Kanakagiri, G. Kwasniewski, R. Ausavarungnirun, J. Beránek, K. Kanellopoulos, K. Janda, Z. Vonarburg-Shmaria, L. Gianinazzi, I. Stefan, J. Gómez Luna, M. Copik, L. Kapp-Schwoerer, S. Di Girolamo, N. Blach, M. Konieczny, O. Mutlu, T. Hoefler:
	SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems (In Proceedings of the 54th IEEE/ACM International Symposium on Microarchitecture (MICRO), Oct. 2021) Abstract Simple graph algorithms such as PageRank have recently been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such as clustering or maximal clique listing. These algorithms are memory-bound and thus could be accelerated by hardware techniques such as Processing-in-Memory (PIM). However, they also come with non-straightforward parallelism and complicated memory access patterns. In this work, we address this with a simple yet surprisingly powerful observation: operations on sets of vertices, such as intersection or union, form a large part of many complex graph mining algorithms, and can offer rich and simple parallelism at multiple levels. This observation drives our cross-layer design, in which we (1) expose set operations using a novel programming paradigm, (2) express and execute these operations efficiently with carefully designed set-centric ISA extensions called SISA, and (3) use PIM to accelerate SISA instructions. The key design idea is to alleviate the bandwidth needs of SISA instructions by mapping set operations to two types of PIM: in-DRAM bulk bitwise computing for bitvectors representing high-degree vertices, and near-memory logic layers for integer arrays representing low-degree vertices. Set-centric SISA-enhanced algorithms are efficient and outperform hand-tuned baselines, offering more than 10x speedup over the established Bron-Kerbosch algorithm for listing maximal cliques. We deliver more than 10 SISA set-centric algorithm formulations, illustrating SISA's wide applicability. Documents download article: access preprint on arxiv: download slides: Recorded talk (best effort)
	BibTeX
@inproceedings{,   author={Maciej Besta and Raghavendra Kanakagiri and Grzegorz Kwasniewski and Rachata Ausavarungnirun and Jakub Beránek and Konstantinos Kanellopoulos and Kacper Janda and Zur Vonarburg-Shmaria and Lukas Gianinazzi and Ioana Stefan and Juan Gómez Luna and Marcin Copik and Lukas Kapp-Schwoerer and Salvatore Di Girolamo and Nils Blach and Marek Konieczny and Onur Mutlu and Torsten Hoefler},   title={{SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems}},   year={2021},   month={10},   booktitle={Proceedings of the 54th IEEE/ACM International Symposium on Microarchitecture (MICRO)},   doi={https://doi.org/10.1145/3466752.3480133}, }