Kunle Olukotun

Kunle Olukotun

Auto-generated profile, based on publicly available information

Kunle Olukotun

Stanford University, Stanford, CA, USA

Research Focus & Metrics

Academic Career Length

21Years (2006-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2007
Verified
Conference Paper
Closed access
HCHassan Chafi
Hassan Chafi
JCJared Casper
Jared Casper
BCBrian D. Carlstrom
Brian D. Carlstrom
AMAusten McDonald
Austen McDonald
CMChi Cao Minh
Chi Cao Minh
KOKunle Olukotun
Kunle Olukotun
Transactional memory (TM) provides mechanisms that promise to simplify parallel programming by eliminating the need for locks and their associated problems (deadlock, livelock, priority inversion, convoying). For TM to be adopted in the long term, not only does it need to deliver on these promises, but it needs to scale to a high number of processors. To date, proposals for scalable TM have relegated livelock issues to user-level contention managers. This paper presents the first scalable TM implementation for directory-based distributed shared memory systems that is livelock free without the need for user-level intervention. The design is a scalable implementation of optimistic concurrency control that supports parallel commits with a two-phase commit protocol, uses write-back caches, and filters coherence messages. The scalable design is based on transactional coherence and consistency (TCC), which supports continuous transactions and fault isolation. A performance evaluation of the design using both scientific and enterprise benchmarks demonstrates that the directory-based TCC design scales efficiently for NUMA systems up to 64 processors

14 June 2016
Verified
Conference Paper
Open access
CAChristopher R. Aberger
Christopher R. Aberger
STSusan Tu
Susan Tu
KOKunle Olukotun
Kunle Olukotun
CRChristopher Ré
Christopher Ré
There are two types of high-performance graph processing engines: low- and high-level engines. Low-level engines (Galois, PowerGraph, Snap) provide optimized data structures and computation models but require users to write low-level imperative code, hence ensuring that efficiency is the burden of the user. In high-level engines, users write in query languages like datalog (SociaLite) or SQL (Grail). High-level engines are easier to use but are orders of magnitude slower than the low-level graph engines. We present EmptyHeaded, a high-level engine that supports a rich datalog-like query language and achieves performance comparable to that of low-level engines. At the core of EmptyHeaded's design is a new class of join algorithms that satisfy strong theoretical guarantees but have thus far not achieved performance comparable to that of specialized graph processing engines. To achieve high performance, EmptyHeaded introduces a new join engine architecture, including a novel query optimizer and data layouts that leverage single-instruction multiple data (SIMD) parallelism. With this architecture, EmptyHeaded outperforms high-level approaches by up to three orders of magnitude on graph pattern queries, PageRank, and Single-Source Shortest Paths (SSSP) and is an order of magnitude faster than many low-level baselines. We validate that EmptyHeaded competes with the best-of-breed low-level engine (Galois), achieving comparable performance on PageRank and at most 3x worse performance on SSSP.

24 June 2017 in ACM SIGARCH Computer Architecture News
Verified
Journal Article
Open access
CSChristopher De Sa
Christopher De Sa
MFMatthew Feldman
Matthew Feldman
CRChristopher Ré
Christopher Ré
KOKunle Olukotun
Kunle Olukotun
Stochastic gradient descent (SGD) is one of the most popular numerical algorithms used in machine learning and other domains. Since this is likely to continue for the foreseeable future, it is important to study techniques that can make it run fast on parallel hardware. In this paper, we provide the first analysis of a technique called Buck-wild! that uses both asynchronous execution and low-precision computation. We introduce the DMGC model, the first conceptualization of the parameter space that exists when implementing low-precision SGD, and show that it provides a way to both classify these algorithms and model their performance. We leverage this insight to propose and analyze techniques to improve the speed of low-precision SGD. First, we propose software optimizations that can increase throughput on existing CPUs by up to 11X. Second, we propose architectural changes, including a new cache technique we call an obstinate cache, that increase throughput beyond the limits of current-generation hardware. We also implement and analyze low-precision SGD on the FPGA, which is a promising alternative to the CPU for future SGD systems.

25 March 2023
Verified
Conference Paper
Open access
EHErik Orm Hellsten
Erik Orm Hellsten
ASArtur Souza
Artur Souza
JLJohannes Lenfers
Johannes Lenfers
RLRubens Lacouture
Rubens Lacouture
OHOlivia Hsu
Olivia Hsu
LNLuigi Nardi
Luigi Nardi

6 June 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MBManya Bansal
Manya Bansal
OHOlivia Hsu
Olivia Hsu
KOKunle Olukotun
Kunle Olukotun
FKFredrik Kjolstad
Fredrik Kjolstad
We introduce Mosaic, a sparse tensor algebra compiler that can bind tensor expressions to external functions of other tensor algebra libraries and compilers. Users can extend Mosaic by adding new functions and bind a sub-expression to a function using a scheduling API. Mosaic substitutes the bound sub-expressions with calls to the external functions and automatically generates the remaining code using a default code generator. As the generated code is fused by default, users can productively leverage both fusion and calls to specialized functions within the same compiler. We demonstrate the benefits of our dual approach by showing that calling hand-written CPU and specialized hardware functions can provide speedups of up to 206× against fused code in some cases, while generating fused code can provide speedups of up to 3.57× against code that calls external functions in other cases. Mosaic also offers a search system that can automatically map an expression to a set of registered external functions. Both the explicit binding and automatic search are verified by Mosaic. Additionally, the interface for adding new external functions is simple and general. Currently, 38 external functions have been added to Mosaic, with each addition averaging 20 lines of code.

1 August 2017 in Jmlr Workshop and Conference Proceedings
Verified
Conference Paper
Closed access
CSChristopher De Sa
Christopher De Sa
KOKunle Olukotun
Kunle Olukotun
CRChristopher Ré
Christopher Ré
Electronic proceedings of IJCAI 2017