Timothy Mattson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Timothy Mattson has a total of 77 co-authors. Here are the top co-authors by number of shared publications:
- Gal Oren
Stanford University
6 shared publications - Niranjan Hasabnis
Intel Labs United States
5 shared publications - Tal Kadosh
Atomic Energy Commission Israel
4 shared publications - Yuval Pinter
Department of Computer Science Ben-Gurion University of the Negev Beer Sheva Israel
4 shared publications - Justin Gottschlich
Intel Labs Intel Labs Intel Labs Intel Labs Georgia Institute of Technology Intel Labs Intel Labs MIT MIT Intel Labs Intel Labs Intel Labs MIT Intel Labs Georgia Institute of Technology University of Pennsylvania
3 shared publications - Nadav Schneider
Department of Electrical & Computer Engineering Ben-Gurion University Israel
3 shared publications
Latest Publications
- Open Access
- 14 January 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 6 (1) , 1-6
What Quantum Can Learn from Classical Computer Engineering
Quantum computing represents a paradigm shift requiring reconceptualization of algorithms, architectures, and software. Although much is new, there is much that quantum computing can learn from traditional classical computer engineering. In this Special Issue, we focus on examples of quantum research inspired by classical computer engineering, ranging from quantum machine learning and image processing to the extension of the “multi-core” concept to quantum computing. Hardware/software co-design is difficult when communities have their unique jargon and disjoint problem domains. For parallel programming on classical computers, an approach for communicating application developer needs emerged around identifying key bottlenecks that limited software. It was difficult to guess features of future applications, but experienced developers knew features of a computer system that would limit software performance. For each feature, a small kernel was developed with the idea that if the kernel ran well, a system would be an effective system for application developers. This set of kernels was called the Parallel Research Kernels . They have been useful to guide design of parallel computers. We hypothesize that an analogous tool for quantum computing, called Quantum Research Kernels , may aid hardware/software co-design of quantum computing systems. In this article, we motivate the Quantum Research Kernels and provide working examples.
- 14 January 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 6 (1) , 1-6
Open AccessWhat Quantum Can Learn from Classical Computer Engineering
Quantum computing represents a paradigm shift requiring reconceptualization of algorithms, architectures, and software. Although much is new, there is much that quantum computing can learn from traditional classical computer engineering. In this Special Issue, we focus on examples of quantum research inspired by classical computer engineering, ranging from quantum machine learning and image processing to the extension of the “multi-core” concept to quantum computing. Hardware/software co-design is difficult when communities have their unique jargon and disjoint problem domains. For parallel programming on classical computers, an approach for communicating application developer needs emerged around identifying key bottlenecks that limited software. It was difficult to guess features of future applications, but experienced developers knew features of a computer system that would limit software performance. For each feature, a small kernel was developed with the idea that if the kernel ran well, a system would be an effective system for application developers. This set of kernels was called the Parallel Research Kernels . They have been useful to guide design of parallel computers. We hypothesize that an analogous tool for quantum computing, called Quantum Research Kernels , may aid hardware/software co-design of quantum computing systems. In this article, we motivate the Quantum Research Kernels and provide working examples.
- 15 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 01, 979-989
An Abstraction Hierarchy Toward Productive Quantum Programming
The computer industry, with over seven decades of experience to draw on, has shown that to thrive, there must be a community of software engineers that produce the applications users depend on. Supporting those software engineers so they can write code that performs well across multiple generations of hardware (since application software generally lasts longer than hardware) is fundamental to sustaining the computer industry. Today's quantum software developers must reason at a low level, close to the hardware, which is not sustainable. In this paper, we assert that quantum computing needs high-level abstractions that support a quantum computing applications ecosystem. A single abstraction that bridges from the mental models used by a programmer to the details of how qubits are realized in hardware is unlikely to work. We need a hierarchy of tightly coupled models that define a framework for reasoning about the software development process in quantum computing. We propose an abstraction hierarchy and then explore its utility with two approaches to the eigenvalue estimation problem: (1) a variational algorithm with error mitigation, and (2) phase estimation with error correction. We use our proposed abstraction hierarchy to pinpoint key differences between these approaches and demonstrate how an abstraction hierarchy helps us understand software development. This supports our central conclusion; that it is not enough to understand individual components of a software stack. To make progress, we need to think about an abstraction hierarchy holistically.
- 15 September 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 01, 979-989
An Abstraction Hierarchy Toward Productive Quantum Programming
The computer industry, with over seven decades of experience to draw on, has shown that to thrive, there must be a community of software engineers that produce the applications users depend on. Supporting those software engineers so they can write code that performs well across multiple generations of hardware (since application software generally lasts longer than hardware) is fundamental to sustaining the computer industry. Today's quantum software developers must reason at a low level, close to the hardware, which is not sustainable. In this paper, we assert that quantum computing needs high-level abstractions that support a quantum computing applications ecosystem. A single abstraction that bridges from the mental models used by a programmer to the details of how qubits are realized in hardware is unlikely to work. We need a hierarchy of tightly coupled models that define a framework for reasoning about the software development process in quantum computing. We propose an abstraction hierarchy and then explore its utility with two approaches to the eigenvalue estimation problem: (1) a variational algorithm with error mitigation, and (2) phase estimation with error correction. We use our proposed abstraction hierarchy to pinpoint key differences between these approaches and demonstrate how an abstraction hierarchy helps us understand software development. This supports our central conclusion; that it is not enough to understand individual components of a software stack. To make progress, we need to think about an abstraction hierarchy holistically.
- Open Access
- 3 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-6
MPIrigen: MPI Code Generation through Domain-Specific Language Models
The imperative need to scale computation across numerous nodes highlights the significance of efficient parallel computing, particularly in the realm of Message Passing Interface (MPI) integration. While MPI serves as a cornerstone for large-scale parallelism, its seamless integration into codebases, especially concerning domain decomposition, has proven challenging. Static tools aimed at addressing this challenge have exhibited limited effectiveness and scalability. On the other hand, contemporary language models designed for programming problems have demonstrated utility in parallel programming tasks such as OpenMP pragma generation. However, the challenging parallel programming task of generating MPI-based parallel programs has remained unexplored. This study first investigates the performance of state-of-the-art language models in generating MPI-based parallel programs. Findings reveal that widely used models such as GPT-3.5 and PolyCoder (specialized multi-lingual code models) exhibit notable performance degradation when generating MPI-based programs compared to general-purpose programs. In contrast, domain-specific models such as MonoCoder, which are pre-trained on MPI-related programming languages of C and C++, outperform larger models. Subsequently, we introduce a dedicated downstream task of MPI-based program generation by fine-tuning MonoCoder on HPCorpusMPI. We call the resulting model as MPIrigen. We propose an innovative preprocessing for completion only after observing the whole code, thus enabling better completion with a wider context. Comparative analysis against GPT-3.5 zero-shot performance, using a novel HPC-oriented evaluation method, demonstrates that MPIrigen excels in generating accurate MPI functions calls. The success of this tailored solution underscores the importance of domain-specific fine-tuning in optimizing language models for parallel computing code generation, paving the way for a new generation of automatic parallelization tools. The sources of this work are available at our GitHub MPIrigen repository.
- 3 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-6
Open AccessMPIrigen: MPI Code Generation through Domain-Specific Language Models
The imperative need to scale computation across numerous nodes highlights the significance of efficient parallel computing, particularly in the realm of Message Passing Interface (MPI) integration. While MPI serves as a cornerstone for large-scale parallelism, its seamless integration into codebases, especially concerning domain decomposition, has proven challenging. Static tools aimed at addressing this challenge have exhibited limited effectiveness and scalability. On the other hand, contemporary language models designed for programming problems have demonstrated utility in parallel programming tasks such as OpenMP pragma generation. However, the challenging parallel programming task of generating MPI-based parallel programs has remained unexplored. This study first investigates the performance of state-of-the-art language models in generating MPI-based parallel programs. Findings reveal that widely used models such as GPT-3.5 and PolyCoder (specialized multi-lingual code models) exhibit notable performance degradation when generating MPI-based programs compared to general-purpose programs. In contrast, domain-specific models such as MonoCoder, which are pre-trained on MPI-related programming languages of C and C++, outperform larger models. Subsequently, we introduce a dedicated downstream task of MPI-based program generation by fine-tuning MonoCoder on HPCorpusMPI. We call the resulting model as MPIrigen. We propose an innovative preprocessing for completion only after observing the whole code, thus enabling better completion with a wider context. Comparative analysis against GPT-3.5 zero-shot performance, using a novel HPC-oriented evaluation method, demonstrates that MPIrigen excels in generating accurate MPI functions calls. The success of this tailored solution underscores the importance of domain-specific fine-tuning in optimizing language models for parallel computing code generation, paving the way for a new generation of automatic parallelization tools. The sources of this work are available at our GitHub MPIrigen repository.
- Open Access
- 30 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 236-246
Distributed Ranges: A Model for Distributed Data Structures, Algorithms, and Views
Data structures and algorithms are essential building blocks for programs, and distributed data structures, which automatically partition data across multiple memory locales, are essential to writing high-level parallel programs. While many projects have designed and implemented C++ distributed data structures and algorithms, there has not been widespread adoption of an interoperable model allowing algorithms and data structures from different libraries to work together. This paper introduces distributed ranges, which is a model for building generic data structures, views, and algorithms. A distributed range extends a C++ range, which is an iterable sequence of values, with a concept of segmentation, thus exposing how the distributed range is partitioned over multiple memory locales. Distributed data structures provide this distributed range interface, which allows them to be used with a collection of generic algorithms implemented using the distributed range interface. The modular nature of the model allows for the straightforward implementation of distributed views, which are lightweight objects that provide a lazily evaluated view of another range. Views can be composed together recursively and combined with algorithms to implement computational kernels using efficient, flexible, and high-level standard C++ primitives. We evaluate the distributed ranges model by implementing a set of standard concepts and views as well as two execution runtimes, a multi-node, MPI-based runtime and a single-process, multi-GPU runtime. We demonstrate that high-level algorithms implemented using generic, high-level distributed ranges can achieve performance competitive with highly-tuned, expert-written code.
- 30 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 236-246
Open AccessDistributed Ranges: A Model for Distributed Data Structures, Algorithms, and Views
Data structures and algorithms are essential building blocks for programs, and distributed data structures, which automatically partition data across multiple memory locales, are essential to writing high-level parallel programs. While many projects have designed and implemented C++ distributed data structures and algorithms, there has not been widespread adoption of an interoperable model allowing algorithms and data structures from different libraries to work together. This paper introduces distributed ranges, which is a model for building generic data structures, views, and algorithms. A distributed range extends a C++ range, which is an iterable sequence of values, with a concept of segmentation, thus exposing how the distributed range is partitioned over multiple memory locales. Distributed data structures provide this distributed range interface, which allows them to be used with a collection of generic algorithms implemented using the distributed range interface. The modular nature of the model allows for the straightforward implementation of distributed views, which are lightweight objects that provide a lazily evaluated view of another range. Views can be composed together recursively and combined with algorithms to implement computational kernels using efficient, flexible, and high-level standard C++ primitives. We evaluate the distributed ranges model by implementing a set of standard concepts and views as well as two execution runtimes, a multi-node, MPI-based runtime and a single-process, multi-GPU runtime. We demonstrate that high-level algorithms implemented using generic, high-level distributed ranges can achieve performance competitive with highly-tuned, expert-written code.
- Open Access
- 12 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 2-10
MPI-RICAL: Data-Driven MPI Distributed Parallelism Assistance with Transformers
Computational science has made rapid progress in recent years, leading to ever increasing demand for supercomputing resources. For scientific applications that leverage such resources, Message Passing Interface (MPI) plays a crucial role in enabling distributed memory parallelization across multiple nodes. However, parallelizing MPI code manually, and specifically, performing domain decomposition, is a challenging and error-prone task. In this paper, we address this problem by developing MPI-rical, a novel data-driven, programming-assistance tool that assists programmers in writing domain decomposition based distributed memory parallelization code using MPI. Specifically, we leverage Transformer architecture — the invention that led to advancements in the field of natural language processing (NLP) — with a supervised language model to suggest MPI functions and their proper locations in the code on the fly. In addition to the novel model for MPI-based parallel programming, in this paper, we also introduce MPICodeCorpus, the first publicly-available corpus of MPI-based parallel programs that is created by mining more than 15,000 open-source repositories on GitHub. Experimental results demonstrate the effectiveness of MPI-rical on both dataset from MPICodeCorpus and more importantly, on a compiled benchmark of MPI-based parallel programs for numerical computations that represent real-world scientific applications. Specifically, MPI-rical achieves F1 scores between 0.87-0.91 on these programs, demonstrating its accuracy in suggesting correct MPI functions at appropriate code locations. The source code used in this work, as well as other relevant sources, are available at: https://github.com/Scientific-Computing-Lab-NRCN/MPI-rical.
- 12 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 2-10
Open AccessMPI-RICAL: Data-Driven MPI Distributed Parallelism Assistance with Transformers
Computational science has made rapid progress in recent years, leading to ever increasing demand for supercomputing resources. For scientific applications that leverage such resources, Message Passing Interface (MPI) plays a crucial role in enabling distributed memory parallelization across multiple nodes. However, parallelizing MPI code manually, and specifically, performing domain decomposition, is a challenging and error-prone task. In this paper, we address this problem by developing MPI-rical, a novel data-driven, programming-assistance tool that assists programmers in writing domain decomposition based distributed memory parallelization code using MPI. Specifically, we leverage Transformer architecture — the invention that led to advancements in the field of natural language processing (NLP) — with a supervised language model to suggest MPI functions and their proper locations in the code on the fly. In addition to the novel model for MPI-based parallel programming, in this paper, we also introduce MPICodeCorpus, the first publicly-available corpus of MPI-based parallel programs that is created by mining more than 15,000 open-source repositories on GitHub. Experimental results demonstrate the effectiveness of MPI-rical on both dataset from MPICodeCorpus and more importantly, on a compiled benchmark of MPI-based parallel programs for numerical computations that represent real-world scientific applications. Specifically, MPI-rical achieves F1 scores between 0.87-0.91 on these programs, demonstrating its accuracy in suggesting correct MPI functions at appropriate code locations. The source code used in this work, as well as other relevant sources, are available at: https://github.com/Scientific-Computing-Lab-NRCN/MPI-rical.
- 1 September 2023
- Published by Springer Nature
- p. 3-17
Advising OpenMP Parallelization via A Graph-Based Approach with Transformers
- 1 September 2023
- Published by Springer Nature
- p. 3-17
Advising OpenMP Parallelization via A Graph-Based Approach with Transformers
- Open Access
MPI-rical: Data-Driven MPI Distributed Parallelism Assistance with Transformers
Message Passing Interface (MPI) plays a crucial role in distributed memory parallelization across multiple nodes. However, parallelizing MPI code manually, and specifically, performing domain decomposition, is a challenging, error-prone task. In this paper, we address this problem by developing MPI-RICAL, a novel data-driven, programming-assistance tool that assists programmers in writing domain decomposition based distributed memory parallelization code. Specifically, we train a supervised language model to suggest MPI functions and their proper locations in the code on the fly. We also introduce MPICodeCorpus, the first publicly available corpus of MPI-based parallel programs that is created by mining more than 15,000 open-source repositories on GitHub. Experimental results have been done on MPICodeCorpus and more importantly, on a compiled benchmark of MPI-based parallel programs for numerical computations that represent real-world scientific applications. MPI-RICAL achieves F1 scores between 0.87-0.91 on these programs, demonstrating its accuracy in suggesting correct MPI functions at appropriate code locations.. The source code used in this work, as well as other relevant sources, are available at: https://github.com/Scientific-Computing-Lab-NRCN/MPI-rical
Open AccessMPI-rical: Data-Driven MPI Distributed Parallelism Assistance with Transformers
Message Passing Interface (MPI) plays a crucial role in distributed memory parallelization across multiple nodes. However, parallelizing MPI code manually, and specifically, performing domain decomposition, is a challenging, error-prone task. In this paper, we address this problem by developing MPI-RICAL, a novel data-driven, programming-assistance tool that assists programmers in writing domain decomposition based distributed memory parallelization code. Specifically, we train a supervised language model to suggest MPI functions and their proper locations in the code on the fly. We also introduce MPICodeCorpus, the first publicly available corpus of MPI-based parallel programs that is created by mining more than 15,000 open-source repositories on GitHub. Experimental results have been done on MPICodeCorpus and more importantly, on a compiled benchmark of MPI-based parallel programs for numerical computations that represent real-world scientific applications. MPI-RICAL achieves F1 scores between 0.87-0.91 on these programs, demonstrating its accuracy in suggesting correct MPI functions at appropriate code locations.. The source code used in this work, as well as other relevant sources, are available at: https://github.com/Scientific-Computing-Lab-NRCN/MPI-rical
- Open Access
Quantifying OpenMP: Statistical Insights into Usage and Adoption
In high-performance computing (HPC), the demand for efficient parallel programming models has grown dramatically since the end of Dennard Scaling and the subsequent move to multi-core CPUs. OpenMP stands out as a popular choice due to its simplicity and portability, offering a directive-driven approach for shared-memory parallel programming. Despite its wide adoption, however, there is a lack of comprehensive data on the actual usage of OpenMP constructs, hindering unbiased insights into its popularity and evolution. This paper presents a statistical analysis of OpenMP usage and adoption trends based on a novel and extensive database, HPCORPUS, compiled from GitHub repositories containing C, C++, and Fortran code. The results reveal that OpenMP is the dominant parallel programming model, accounting for 45% of all analyzed parallel APIs. Furthermore, it has demonstrated steady and continuous growth in popularity over the past decade. Analyzing specific OpenMP constructs, the study provides in-depth insights into their usage patterns and preferences across the three languages. Notably, we found that while OpenMP has a strong "common core" of constructs in common usage (while the rest of the API is less used), there are new adoption trends as well, such as simd and target directives for accelerated computing and task for irregular parallelism. Overall, this study sheds light on OpenMP's significance in HPC applications and provides valuable data for researchers and practitioners. It showcases OpenMP's versatility, evolving adoption, and relevance in contemporary parallel programming, underlining its continued role in HPC applications and beyond. These statistical insights are essential for making informed decisions about parallelization strategies and provide a foundation for further advancements in parallel programming models and techniques.
Open AccessQuantifying OpenMP: Statistical Insights into Usage and Adoption
In high-performance computing (HPC), the demand for efficient parallel programming models has grown dramatically since the end of Dennard Scaling and the subsequent move to multi-core CPUs. OpenMP stands out as a popular choice due to its simplicity and portability, offering a directive-driven approach for shared-memory parallel programming. Despite its wide adoption, however, there is a lack of comprehensive data on the actual usage of OpenMP constructs, hindering unbiased insights into its popularity and evolution. This paper presents a statistical analysis of OpenMP usage and adoption trends based on a novel and extensive database, HPCORPUS, compiled from GitHub repositories containing C, C++, and Fortran code. The results reveal that OpenMP is the dominant parallel programming model, accounting for 45% of all analyzed parallel APIs. Furthermore, it has demonstrated steady and continuous growth in popularity over the past decade. Analyzing specific OpenMP constructs, the study provides in-depth insights into their usage patterns and preferences across the three languages. Notably, we found that while OpenMP has a strong "common core" of constructs in common usage (while the rest of the API is less used), there are new adoption trends as well, such as simd and target directives for accelerated computing and task for irregular parallelism. Overall, this study sheds light on OpenMP's significance in HPC applications and provides valuable data for researchers and practitioners. It showcases OpenMP's versatility, evolving adoption, and relevance in contemporary parallel programming, underlining its continued role in HPC applications and beyond. These statistical insights are essential for making informed decisions about parallelization strategies and provide a foundation for further advancements in parallel programming models and techniques.
- Open Access
Advising OpenMP Parallelization via a Graph-Based Approach with Transformers
There is an ever-present need for shared memory parallelization schemes to exploit the full potential of multi-core architectures. The most common parallelization API addressing this need today is OpenMP. Nevertheless, writing parallel code manually is complex and effort-intensive. Thus, many deterministic source-to-source (S2S) compilers have emerged, intending to automate the process of translating serial to parallel code. However, recent studies have shown that these compilers are impractical in many scenarios. In this work, we combine the latest advancements in the field of AI and natural language processing (NLP) with the vast amount of open-source code to address the problem of automatic parallelization. Specifically, we propose a novel approach, called OMPify, to detect and predict the OpenMP pragmas and shared-memory attributes in parallel code, given its serial version. OMPify is based on a Transformer-based model that leverages a graph-based representation of source code that exploits the inherent structure of code. We evaluated our tool by predicting the parallelization pragmas and attributes of a large corpus of (over 54,000) snippets of serial code written in C and C++ languages (Open-OMP-Plus). Our results demonstrate that OMPify outperforms existing approaches, the general-purposed and popular ChatGPT and targeted PragFormer models, in terms of F1 score and accuracy. Specifically, OMPify achieves up to 90% accuracy on commonly-used OpenMP benchmark tests such as NAS, SPEC, and PolyBench. Additionally, we performed an ablation study to assess the impact of different model components and present interesting insights derived from the study. Lastly, we also explored the potential of using data augmentation and curriculum learning techniques to improve the model's robustness and generalization capabilities.
Open AccessAdvising OpenMP Parallelization via a Graph-Based Approach with Transformers
There is an ever-present need for shared memory parallelization schemes to exploit the full potential of multi-core architectures. The most common parallelization API addressing this need today is OpenMP. Nevertheless, writing parallel code manually is complex and effort-intensive. Thus, many deterministic source-to-source (S2S) compilers have emerged, intending to automate the process of translating serial to parallel code. However, recent studies have shown that these compilers are impractical in many scenarios. In this work, we combine the latest advancements in the field of AI and natural language processing (NLP) with the vast amount of open-source code to address the problem of automatic parallelization. Specifically, we propose a novel approach, called OMPify, to detect and predict the OpenMP pragmas and shared-memory attributes in parallel code, given its serial version. OMPify is based on a Transformer-based model that leverages a graph-based representation of source code that exploits the inherent structure of code. We evaluated our tool by predicting the parallelization pragmas and attributes of a large corpus of (over 54,000) snippets of serial code written in C and C++ languages (Open-OMP-Plus). Our results demonstrate that OMPify outperforms existing approaches, the general-purposed and popular ChatGPT and targeted PragFormer models, in terms of F1 score and accuracy. Specifically, OMPify achieves up to 90% accuracy on commonly-used OpenMP benchmark tests such as NAS, SPEC, and PolyBench. Additionally, we performed an ablation study to assess the impact of different model components and present interesting insights derived from the study. Lastly, we also explored the potential of using data augmentation and curriculum learning techniques to improve the model's robustness and generalization capabilities.
- 26 May 2022
- Published by Taylor & Francis
- p. 507-524
Introduction to GraphBLAS
508Graphs are powerful tools for modeling complex problems because of their simplicity and generality [Staudt et al. 2016, Bergamini & Meyerhenke 2016]. For this reason, the field of graph algorithms has become one of the pillars of theoretical computer science, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Graph algorithms have been adapted and implemented by the military, commercial industry, and researchers in academia, and have become essential in controlling the power grid, telephone systems, and, of course, computer networks. Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to applications in bioinformatics [Georganas et al. 2014], computer networks, and social media [Ediger et al. 2010, Ediger et al. 2011, Riedy et al. 2012, Riedy & Bader 2013]. Parallel graph algorithms are notoriously difficult to implement and optimize [Ediger et al. 2012, Ediger & Bader 2013, McLaughlin & Bader 2014a, McLaughlin & Bader 2014b, McLaughlin et al. 2014, Staudt & Meyerhenke 2016]. The irregular data access patterns and inherently high communication-to-computation ratios found in graph algorithms mean that even the best algorithms will have parallel efficiencies that decrease as the number of processors is increased [Buluç & Gilbert 2012, Azad et al. 2015]. Recent work on communication-avoiding algorithms, and their applications to graph computations [Ballard et al. 2013, Solomonik et al. 2013], might defer but not completely eliminate the parallel scalability bottleneck. Consequently, novel hardware architectures will also be required 509[Song et al. 2010, Song et al. 2013]. A common graph processing interface provides a useful tool for optimizing both software and hardware to provide high performance graph applications.
- 26 May 2022
- Published by Taylor & Francis
- p. 507-524
Introduction to GraphBLAS
508Graphs are powerful tools for modeling complex problems because of their simplicity and generality [Staudt et al. 2016, Bergamini & Meyerhenke 2016]. For this reason, the field of graph algorithms has become one of the pillars of theoretical computer science, informing research in such diverse areas as combinatorial optimization, complexity theory, and topology. Graph algorithms have been adapted and implemented by the military, commercial industry, and researchers in academia, and have become essential in controlling the power grid, telephone systems, and, of course, computer networks. Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to applications in bioinformatics [Georganas et al. 2014], computer networks, and social media [Ediger et al. 2010, Ediger et al. 2011, Riedy et al. 2012, Riedy & Bader 2013]. Parallel graph algorithms are notoriously difficult to implement and optimize [Ediger et al. 2012, Ediger & Bader 2013, McLaughlin & Bader 2014a, McLaughlin & Bader 2014b, McLaughlin et al. 2014, Staudt & Meyerhenke 2016]. The irregular data access patterns and inherently high communication-to-computation ratios found in graph algorithms mean that even the best algorithms will have parallel efficiencies that decrease as the number of processors is increased [Buluç & Gilbert 2012, Azad et al. 2015]. Recent work on communication-avoiding algorithms, and their applications to graph computations [Ballard et al. 2013, Solomonik et al. 2013], might defer but not completely eliminate the parallel scalability bottleneck. Consequently, novel hardware architectures will also be required 509[Song et al. 2010, Song et al. 2013]. A common graph processing interface provides a useful tool for optimizing both software and hardware to provide high performance graph applications.