Bradley C. Kuszmaul
Research Subjects
Research Interests
Bradley C. Kuszmaul has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Charles E. Leiserson
MIT CSAIL, Cambridge, MA, USA
2 shared publications - Michael A. Bender
Stony Brook University
2 shared publications - William Kuszmaul
Carnegie Mellon University, Pittsburgh, PA, USA
2 shared publications - Alan Theodore Sherman
University of Maryland, Baltimore County, Baltimore, Maryland, USA
1 shared publication Alexander (Sasha) Sandler
Oracle, MA, Massachusetts
1 shared publicationButler W. Lampson
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 405-415
The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 405-415
Open AccessThe Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 129-139
Increment - and - Freeze: Every Cache, Everywhere, All of the Time
One of the most basic algorithmic problems concerning caches is to compute the LRU hit-rate curve on a given trace. Unfortunately, the known algorithms exhibit poor data locality and fail to scale to large caches. It is widely believed that the LRU hit-rate curve cannot be computed efficiently enough to be used in online production settings. This has led to a large literature on heuristics that aim to approximate the curve efficiently. In this paper, we show that the poor data locality of past algorithms can be avoided. We introduce a new algorithm, called Increment-and-Freeze, for computing exact LRU hit-rate curves. The algorithm achieves RAM-model complexity O(n log n), external-memory complexity O(n over B log n), and parallelism Θ(log n). We also present two theoretical extensions of Increment-and-Freeze, one that achieves SORT complexity in the external-memory model, and one that achieves a parallel span of O(log2 n) which is near linear parallelism, while maintaining work efficiency. We implement Increment-and-Freeze and obtain a speedup of up to 9x over the classical augmented-tree algorithm on a single processor. On 16 threads, the speedup becomes as large as 60x. In comparison to the previous state-of-the-art parallel algorithm, Increment-and-Freeze achieves a speedup of up to 10x when both algorithms use the same number of threads.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 129-139
Open AccessIncrement - and - Freeze: Every Cache, Everywhere, All of the Time
One of the most basic algorithmic problems concerning caches is to compute the LRU hit-rate curve on a given trace. Unfortunately, the known algorithms exhibit poor data locality and fail to scale to large caches. It is widely believed that the LRU hit-rate curve cannot be computed efficiently enough to be used in online production settings. This has led to a large literature on heuristics that aim to approximate the curve efficiently. In this paper, we show that the poor data locality of past algorithms can be avoided. We introduce a new algorithm, called Increment-and-Freeze, for computing exact LRU hit-rate curves. The algorithm achieves RAM-model complexity O(n log n), external-memory complexity O(n over B log n), and parallelism Θ(log n). We also present two theoretical extensions of Increment-and-Freeze, one that achieves SORT complexity in the external-memory model, and one that achieves a parallel span of O(log2 n) which is near linear parallelism, while maintaining work efficiency. We implement Increment-and-Freeze and obtain a speedup of up to 9x over the classical augmented-tree algorithm on a single processor. On 16 threads, the speedup becomes as large as 60x. In comparison to the previous state-of-the-art parallel algorithm, Increment-and-Freeze achieves a speedup of up to 10x when both algorithms use the same number of threads.
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 285-286
The Connection Machine CM-5, Moore's Law, and the Future of Computational Performance
In June 1993, the Connection Machine Model CM-5 Supercomputer [6] manufactured by Thinking Machines Corporation was the most powerful computer in the world [10]. At the time, Moore's Law [8, 9] was about halfway through its roughly 60-year reign, and indeed, your smartphone today is likely more powerful than the CM-5, no matter how you want to measure it: FLOPS, bisection bandwidth, storage, etc. As one of the earliest commercially successful parallel supercomputers, the CM-5 network architecture introduced many innovations: a user-level network interface, a fat-tree [5] data network, a global synchronization network, and a system-wide parallel diagnostic network. The CM-5 architecture delivered unprecedented computing power for its day while also simplifying the process of coding for parallel performance. The CM-5 inspired the development of significant software and algorithmic technology still in use today, including work/span analysis [2, Chapter 26], the LogP performance model [3], data-parallel computing [4], task-parallel computing [2, Chapter 26], and work-stealing algorithms [1]. Indeed, although the focus at the time was on the CM-5's hardware innovations, its legacy in the areas of programming models, algorithms, and software performance engineering may be the CM-5's greater contribution. The recent end of Moore's Law [7]--and with it, the attenuation of exponential gains in hardware performance-portends increased relevance of research in these areas, especially in software performance engineering.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 285-286
Open AccessThe Connection Machine CM-5, Moore's Law, and the Future of Computational Performance
In June 1993, the Connection Machine Model CM-5 Supercomputer [6] manufactured by Thinking Machines Corporation was the most powerful computer in the world [10]. At the time, Moore's Law [8, 9] was about halfway through its roughly 60-year reign, and indeed, your smartphone today is likely more powerful than the CM-5, no matter how you want to measure it: FLOPS, bisection bandwidth, storage, etc. As one of the earliest commercially successful parallel supercomputers, the CM-5 network architecture introduced many innovations: a user-level network interface, a fat-tree [5] data network, a global synchronization network, and a system-wide parallel diagnostic network. The CM-5 architecture delivered unprecedented computing power for its day while also simplifying the process of coding for parallel performance. The CM-5 inspired the development of significant software and algorithmic technology still in use today, including work/span analysis [2, Chapter 26], the LogP performance model [3], data-parallel computing [4], task-parallel computing [2, Chapter 26], and work-stealing algorithms [1]. Indeed, although the focus at the time was on the CM-5's hardware innovations, its legacy in the areas of programming models, algorithms, and software performance engineering may be the CM-5's greater contribution. The recent end of Moore's Law [7]--and with it, the attenuation of exponential gains in hardware performance-portends increased relevance of research in these areas, especially in software performance engineering.
- Top Cited Papers
- 5 June 2020
- Published by American Association for the Advancement of Science (AAAS) in Science
- Vol. 368 (6495) , 1079-+
There’s plenty of room at the Top: What will drive computer performance after Moore’s law?
From bottom to top: The doubling of the number of transistors on a chip every 2 years, a seemly inevitable trend that has been called Moore's law, has contributed immensely to improvements in computer performance. However, silicon-based transistors cannot get much smaller than they are today, and other approaches should be explored to keep performance growing. Leisersonet al.review recent examples and argue that the most promising place to look is at the top of the computing stack, where improvements in software, algorithms, and hardware architecture can bring the much-needed boost.Science, this issue p.eaam9744
- 5 June 2020
- Published by American Association for the Advancement of Science (AAAS) in Science
- Vol. 368 (6495) , 1079-+
Top Cited PapersThere’s plenty of room at the Top: What will drive computer performance after Moore’s law?
From bottom to top: The doubling of the number of transistors on a chip every 2 years, a seemly inevitable trend that has been called Moore's law, has contributed immensely to improvements in computer performance. However, silicon-based transistors cannot get much smaller than they are today, and other approaches should be explored to keep performance growing. Leisersonet al.review recent examples and argue that the most promising place to look is at the top of the computing stack, where improvements in software, algorithms, and hardware architecture can bring the much-needed boost.Science, this issue p.eaam9744
- Open Access
- 29 February 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 16 (1) , 1-29
Everyone Loves File
Oracle File Storage Service (FSS) is an elastic filesystem provided as a managed NFS service. A pipelined Paxos implementation underpins a scalable block store that provides linearizable multipage limited-size transactions. Above the block store, a scalable B-tree holds filesystem metadata and provides linearizable multikey limited-size transactions. Self-validating B-tree nodes and housekeeping operations performed as separate transactions allow each key in a B-tree transaction to require only one page in the underlying block transaction. The filesystem provides snapshots by using versioned key-value pairs. The system is programmed using a nonblocking lock-free programming style. Presentation servers maintain no persistent local state making them scalable and easy to failover. A non-scalable Paxos-replicated hash table holds configuration information required to bootstrap the system. An additional B-tree provides conversational multi-key minitransactions for control-plane information. The system throughput can be predicted by comparing an estimate of the network bandwidth needed for replication to the network bandwidth provided by the hardware. Latency on an unloaded system is about 4 times higher than a Linux NFS server backed by NVMe, reflecting the cost of replication. FSS has been in production since January 2018 and holds tens of thousands of customer file systems comprising many petabytes of data.
- 29 February 2020
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 16 (1) , 1-29
Open AccessEveryone Loves File
Oracle File Storage Service (FSS) is an elastic filesystem provided as a managed NFS service. A pipelined Paxos implementation underpins a scalable block store that provides linearizable multipage limited-size transactions. Above the block store, a scalable B-tree holds filesystem metadata and provides linearizable multikey limited-size transactions. Self-validating B-tree nodes and housekeeping operations performed as separate transactions allow each key in a B-tree transaction to require only one page in the underlying block transaction. The filesystem provides snapshots by using versioned key-value pairs. The system is programmed using a nonblocking lock-free programming style. Presentation servers maintain no persistent local state making them scalable and easy to failover. A non-scalable Paxos-replicated hash table holds configuration information required to bootstrap the system. An additional B-tree provides conversational multi-key minitransactions for control-plane information. The system throughput can be predicted by comparing an estimate of the network bandwidth needed for replication to the network bandwidth provided by the hardware. Latency on an unloaded system is about 4 times higher than a Linux NFS server backed by NVMe, reflecting the cost of replication. FSS has been in production since January 2018 and holds tens of thousands of customer file systems comprising many petabytes of data.
- Open Access
- 1 June 1995
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 18 (2) , 124
*Socrates 2.0 Beats Grandmaster Sagalchik
- 1 June 1995
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 18 (2) , 124
Open Access*Socrates 2.0 Beats Grandmaster Sagalchik