Maximilian Bremer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Maximilian Bremer has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Cy Chan
Lawrence Berkeley National Laboratory, USA
4 shared publications Clint Dawson
Univ Texas Austin, Oden Inst Computat Engn & Sci, 201 E 24th St, Austin, TX 78712 USA
2 shared publications- John Bachan
Lawrence Berkeley National Laboratory, USA
2 shared publications - John Shalf
Lawrence Berkeley National Laboratory, Berkeley, CA, USA
2 shared publications - Abdul Motaleb Faysal
Computer Science, University of Nevada, Las Vegas, United States of America
1 shared publication - Chao Zhang
Lehigh University
1 shared publication
Latest Publications
- Open Access
- 24 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 35-46
Devastator: A Scalable Parallel Discrete Event Simulation Framework for Modern C++
Parallel discrete event simulation is a fundamental simulation technology that is essential to the parallelization of event-based models including hardware and transportation systems. Parallelization is often difficult due to dynamic data-dependencies and limited computational work for hiding runtime overheads. We present Devastator, a scalable parallel discrete event simulation framework for modern C++. Devastator provides a productive API that leverages C++’s type system to eliminate boilerplate code. Devastator has been designed to specifically optimize performance on distributed many-core architectures with deepening memory hierarchies. Devastator relies on the GASNet-Ex communication runtime as well as lock-free message queues to achieve highly competitive performance. We perform strong and weak scaling studies on NERSC’s Perlmutter up to 32,698 cores and demonstrate an up to 5x speed-up over the ROSS simulator for workloads with substantial locality.
- 24 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 35-46
Open AccessDevastator: A Scalable Parallel Discrete Event Simulation Framework for Modern C++
Parallel discrete event simulation is a fundamental simulation technology that is essential to the parallelization of event-based models including hardware and transportation systems. Parallelization is often difficult due to dynamic data-dependencies and limited computational work for hiding runtime overheads. We present Devastator, a scalable parallel discrete event simulation framework for modern C++. Devastator provides a productive API that leverages C++’s type system to eliminate boilerplate code. Devastator has been designed to specifically optimize performance on distributed many-core architectures with deepening memory hierarchies. Devastator relies on the GASNet-Ex communication runtime as well as lock-free message queues to achieve highly competitive performance. We perform strong and weak scaling studies on NERSC’s Perlmutter up to 32,698 cores and demonstrate an up to 5x speed-up over the ROSS simulator for workloads with substantial locality.
- Open Access
- 7 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 132-141
Fast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs
- 7 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 132-141
Open AccessFast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs
- Open Access
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 32 (4) , 1-30
Performance Analysis of Speculative Parallel Adaptive Local Timestepping for Conservation Laws
Stable simulation of conservation laws, such as those used to model fluid dynamics and plasma physics applications, requires the satisfaction of the so-called Courant-Friedrichs-Lewy condition. By allowing regions of the mesh to advance with different timesteps that locally satisfy this stability constraint, significant work reduction can be attained when compared to a time integration scheme using a single timestep size. However, parallelizing this algorithm presents considerable difficulty. Since the stability condition depends on the state of the system, dependencies become dynamic and potentially non-local. In this article, we present an adaptive local timestepping algorithm using an optimistic (Timewarp-based) parallel discrete event simulation. We introduce waiting heuristics to limit misspeculation and a semi-static load balancing scheme to eliminate load imbalance as parts of the mesh require finer or coarser timesteps. Last, we outline an interface for separating the physics of the specific conservation law from the temporal integration allowing for productive adoption of our proposed algorithm. We present a misspeculation study for three conservation laws, demonstrating both the productivity of the local timestepping API, for which 74% of the lines of code are reused across different conservation laws, and the robustness of the waiting heuristics—at most 1.5% of element updates are rolled back. Our performance studies demonstrate up to a 2.8× speedup versus a baseline unoptimized local timestepping approach, a 4x improvement in per-node throughput compared to an MPI parallelization of synchronous timestepping, and scalability up to 3,072 cores on NERSC’s Cori Haswell partition.
- 31 October 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 32 (4) , 1-30
Open AccessPerformance Analysis of Speculative Parallel Adaptive Local Timestepping for Conservation Laws
Stable simulation of conservation laws, such as those used to model fluid dynamics and plasma physics applications, requires the satisfaction of the so-called Courant-Friedrichs-Lewy condition. By allowing regions of the mesh to advance with different timesteps that locally satisfy this stability constraint, significant work reduction can be attained when compared to a time integration scheme using a single timestep size. However, parallelizing this algorithm presents considerable difficulty. Since the stability condition depends on the state of the system, dependencies become dynamic and potentially non-local. In this article, we present an adaptive local timestepping algorithm using an optimistic (Timewarp-based) parallel discrete event simulation. We introduce waiting heuristics to limit misspeculation and a semi-static load balancing scheme to eliminate load imbalance as parts of the mesh require finer or coarser timesteps. Last, we outline an interface for separating the physics of the specific conservation law from the temporal integration allowing for productive adoption of our proposed algorithm. We present a misspeculation study for three conservation laws, demonstrating both the productivity of the local timestepping API, for which 74% of the lines of code are reused across different conservation laws, and the robustness of the waiting heuristics—at most 1.5% of element updates are rolled back. Our performance studies demonstrate up to a 2.8× speedup versus a baseline unoptimized local timestepping approach, a 4x improvement in per-node throughput compared to an MPI parallelization of synchronous timestepping, and scalability up to 3,072 cores on NERSC’s Cori Haswell partition.
- Open Access
- 16 September 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 19 (4) , 1-24
ASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM
Sparse linear algebra is an important kernel in many different applications. Among various sparse general matrix-matrix multiplication (SpGEMM) algorithms, Gustavson’s column-wise SpGEMM has good locality when reading input matrix and can be easily parallelized by distributing the computation of different columns of an output matrix to different processors. However, the sparse accumulation (SPA) step in column-wise SpGEMM, which merges partial sums from each of the multiplications by the row indices, is still a performance bottleneck. The state-of-the-art software implementation uses a hash table for partial sum search in the SPA, which makes SPA the largest contributor to the execution time of SpGEMM. There are three reasons that cause the SPA to become the bottleneck: (1) hash probing requires data-dependent branches that are difficult for a branch predictor to predict correctly; (2) the accumulation of partial sum is dependent on the results of the hash probing, which makes it difficult to hide the hash probing latency; and (3) hash collision requires time-consuming linear search and optimizations to reduce these collisions require an accurate estimation of the number of non-zeros in each column of the output matrix. This work proposes ASA architecture to accelerate the SPA. ASA overcomes the challenges of SPA by (1) executing the partial sum search and accumulate with a single instruction through ISA extension to eliminate data-dependent branches in hash probing, (2) using a dedicated on-chip cache to perform the search and accumulation in a pipelined fashion, (3) relying on the parallel search capability of a set-associative cache to reduce search latency, and (4) delaying the merging of overflowed entries. As a result, ASA achieves an average of 2.25× and 5.05× speedup as compared to the state-of-the-art software implementation of a Markov clustering application and its SpGEMM kernel, respectively. As compared to a state-of-the-art hashing accelerator design, ASA achieves an average of 1.95× speedup in the SpGEMM kernel.
- 16 September 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 19 (4) , 1-24
Open AccessASA: A ccelerating S parse A ccumulation in Column-wise SpGEMM
Sparse linear algebra is an important kernel in many different applications. Among various sparse general matrix-matrix multiplication (SpGEMM) algorithms, Gustavson’s column-wise SpGEMM has good locality when reading input matrix and can be easily parallelized by distributing the computation of different columns of an output matrix to different processors. However, the sparse accumulation (SPA) step in column-wise SpGEMM, which merges partial sums from each of the multiplications by the row indices, is still a performance bottleneck. The state-of-the-art software implementation uses a hash table for partial sum search in the SPA, which makes SPA the largest contributor to the execution time of SpGEMM. There are three reasons that cause the SPA to become the bottleneck: (1) hash probing requires data-dependent branches that are difficult for a branch predictor to predict correctly; (2) the accumulation of partial sum is dependent on the results of the hash probing, which makes it difficult to hide the hash probing latency; and (3) hash collision requires time-consuming linear search and optimizations to reduce these collisions require an accurate estimation of the number of non-zeros in each column of the output matrix. This work proposes ASA architecture to accelerate the SPA. ASA overcomes the challenges of SPA by (1) executing the partial sum search and accumulate with a single instruction through ISA extension to eliminate data-dependent branches in hash probing, (2) using a dedicated on-chip cache to perform the search and accumulation in a pipelined fashion, (3) relying on the parallel search capability of a set-associative cache to reduce search latency, and (4) delaying the merging of overflowed entries. As a result, ASA achieves an average of 2.25× and 5.05× speedup as compared to the state-of-the-art software implementation of a Markov clustering application and its SpGEMM kernel, respectively. As compared to a state-of-the-art hashing accelerator design, ASA achieves an average of 1.95× speedup in the SpGEMM kernel.
- 21 April 2022
- Published by Elsevier in Journal of Computational Physics
- Vol. 463
Adaptive total variation stable local timestepping for conservation laws
- 21 April 2022
- Published by Elsevier in Journal of Computational Physics
- Vol. 463
Adaptive total variation stable local timestepping for conservation laws
- 2 May 2019
- Published by Springer Nature in Journal of Scientific Computing
- Vol. 80 (2) , 878-902
Performance Comparison of HPX Versus Traditional Parallelization Strategies for the Discontinuous Galerkin Method
- 2 May 2019
- Published by Springer Nature in Journal of Scientific Computing
- Vol. 80 (2) , 878-902
Performance Comparison of HPX Versus Traditional Parallelization Strategies for the Discontinuous Galerkin Method
- 1 November 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 44-56
Semi-Static and Dynamic Load Balancing for Asynchronous Hurricane Storm Surge Simulations
The performance of hurricane storm surge simulations is critical to forecast and mitigate the deadly effects of hurricane landfall. Supercomputers play a key role to run these simulations quickly; however, disruptive changes in future computer architectures will require adapting simulators to maintain high performance, such as increasing asynchrony and improving load balance. We introduce two new multi-constraint, fully asynchronous load balancers and a new discrete-event simulator (DGSim) that is able to natively model the execution of task-based hurricane simulations based on efficient one-sided, active message-based communication protocols. We calibrate and validate DGSim, use it to compare the algorithms' load balancing capabilities and task migration costs under many parameterizations, saving of over 5,000x core-hours compared to running the application code directly. Our load balancing algorithms achieve a performance improvement of up to 56 percent over the original static balancer and up to 97 percent of the optimal speed-up.
- 1 November 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 44-56
Semi-Static and Dynamic Load Balancing for Asynchronous Hurricane Storm Surge Simulations
The performance of hurricane storm surge simulations is critical to forecast and mitigate the deadly effects of hurricane landfall. Supercomputers play a key role to run these simulations quickly; however, disruptive changes in future computer architectures will require adapting simulators to maintain high performance, such as increasing asynchrony and improving load balance. We introduce two new multi-constraint, fully asynchronous load balancers and a new discrete-event simulator (DGSim) that is able to natively model the execution of task-based hurricane simulations based on efficient one-sided, active message-based communication protocols. We calibrate and validate DGSim, use it to compare the algorithms' load balancing capabilities and task migration costs under many parameterizations, saving of over 5,000x core-hours compared to running the application code directly. Our load balancing algorithms achieve a performance improvement of up to 56 percent over the original static balancer and up to 97 percent of the optimal speed-up.