BKBradley C. Kuszmaul

Bradley C. Kuszmaul

*This is an algorithmically generated author record based on publicly available information.

Bradley C. Kuszmaul has a total of 23 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically

    by Michael A. Bender, Philip Bille, Martín Farach-Colton, Jeremy Fineman, Inge Li Gørtz, Michael T. Goodrich, Hanna Komlós, Bradley C. Kuszmaul, William Kuszmaul, Rose Silver, et al.

  • Open Access

    Increment - and - Freeze: Every Cache, Everywhere, All of the Time

    by Michael A. Bender, Daniel DeLayo, Bradley C. Kuszmaul, William Kuszmaul, Evan West

    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

    The Connection Machine CM-5, Moore's Law, and the Future of Computational Performance

    by Bradley C. Kuszmaul, Charles E. Leiserson

    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

    There’s plenty of room at the Top: What will drive computer performance after Moore’s law?

    by Charles E. Leiserson, Neil C. Thompson, Joel S. Emer, Bradley C. Kuszmaul, Butler W. Lampson, Daniel Sanchez, Tao B. Schardl

    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

    Everyone Loves File

    by Bradley C. Kuszmaul, Matteo Frigo, Justin Mazzola Paluska, Alexander (Sasha) Sandler

    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.