Search Results

Documents authored by Johnson, Rob

Found 2 Possible Name Variants:

Johnson, Rob

Document
DOI: 10.4230/LIPIcs.ESA.2022.16
When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

Authors: Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Cache-adaptive algorithms are a class of algorithms that achieve optimal utilization of dynamically changing memory. These memory fluctuations are the norm in today’s multi-threaded shared-memory machines and time-sharing caches. Bender et al. [Bender et al., 2014] proved that many cache-oblivious algorithms are optimally cache-adaptive, but that some cache-oblivious algorithms can be relatively far from optimally cache-adaptive on worst-case memory fluctuations. This worst-case gap between cache obliviousness and cache adaptivity depends on a highly-structured, adversarial memory profile. Existing cache-adaptive analysis does not predict the relative performance of cache-oblivious and cache-adaptive algorithms on non-adversarial profiles. Does the worst-case gap appear in practice, or is it an artifact of an unrealistically powerful adversary? This paper sheds light on the question of whether cache-oblivious algorithms can effectively adapt to realistically fluctuating memory sizes; the paper focuses on matrix multiplication and sorting. The two matrix-multiplication algorithms in this paper are canonical examples of "(a, b, c)-regular" cache-oblivious algorithms, which underlie much of the existing theory on cache-adaptivity. Both algorithms have the same asymptotic I/O performance when the memory size remains fixed, but one is optimally cache-adaptive, and the other is not. In our experiments, we generate both adversarial and non-adversarial memory workloads. The performance gap between the algorithms for matrix multiplication grows with problem size (up to 3.8×) on the adversarial profiles, but the gap does not grow with problem size (stays at 2×) on non-adversarial profiles. The sorting algorithms in this paper are not "(a, b, c)-regular," but they have been well-studied in the classical external-memory model when the memory size does not fluctuate. The relative performance of a non-oblivious (cache-aware) sorting algorithm degrades with the problem size: it incurs up to 6 × the number of disk I/Os compared to an oblivious adaptive algorithm on both adversarial and non-adversarial profiles. To summarize, in all our experiments, the cache-oblivious matrix-multiplication and sorting algorithms that we tested empirically adapt well to memory fluctuations. We conjecture that cache-obliviousness will empirically help achieve adaptivity for other problems with similar structures.
Cite as

Arghya Bhattacharya, Abiyaz Chowdhury, Helen Xu, Rathish Das, Rezaul A. Chowdhury, Rob Johnson, Rishab Nithyanand, and Michael A. Bender. When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2022.16,
  author =	{Bhattacharya, Arghya and Chowdhury, Abiyaz and Xu, Helen and Das, Rathish and Chowdhury, Rezaul A. and Johnson, Rob and Nithyanand, Rishab and Bender, Michael A.},
  title =	{{When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.16},
  URN =		{urn:nbn:de:0030-drops-169543},
  doi =		{10.4230/LIPIcs.ESA.2022.16},
  annote =	{Keywords: Cache-adaptive algorithms, cache-oblivious algorithms}
}
Document
DOI: 10.4230/DagRep.9.3.39
Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111)

Authors: Martin Farach-Colton, Inge Li Gørtz, Rob Johnson, and Donald E. Porter

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19111 "Theoretical Foundations of Storage Systems." This seminar brought together researchers from two distinct communities - algorithms researchers with an interest in external memory and systems researchers with an interest in storage - with the objective of improving the design of future storage systems.
Cite as

Martin Farach-Colton, Inge Li Gørtz, Rob Johnson, and Donald E. Porter. Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111). In Dagstuhl Reports, Volume 9, Issue 3, pp. 39-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{farachcolton_et_al:DagRep.9.3.39,
  author =	{Farach-Colton, Martin and G{\o}rtz, Inge Li and Johnson, Rob and Porter, Donald E.},
  title =	{{Theoretical Foundations of Storage Systems (Dagstuhl Seminar 19111)}},
  pages =	{39--51},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{Farach-Colton, Martin and G{\o}rtz, Inge Li and Johnson, Rob and Porter, Donald E.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.39},
  URN =		{urn:nbn:de:0030-drops-112909},
  doi =		{10.4230/DagRep.9.3.39},
  annote =	{Keywords: Storage Systems, External Memory Algorithms}
}

Johnson, Robert F.

Document
DOI: 10.4230/LIPIcs.DNA.2020.2
Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks

Authors: Robert F. Johnson and Lulu Qian

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
In molecular programming, the Chemical Reaction Network model is often used to describe real or hypothetical systems. Often, an interesting computational task can be done with a known hypothetical Chemical Reaction Network, but often such networks have no known physical implementation. One of the important breakthroughs in the field was that any Chemical Reaction Network can be physically implemented, approximately, using DNA strand displacement mechanisms. This allows us to treat the Chemical Reaction Network model as a programming language and the implementation schemes as its compiler. This also suggests that it would be useful to optimize the result of such a compilation, and in general to find effective ways to design better DNA strand displacement systems. We discuss DNA strand displacement systems in terms of "motifs", short sequences of elementary DNA strand displacement reactions. We argue that describing such motifs in terms of their inputs and outputs, then building larger systems out of the abstracted motifs, can be an efficient way of designing DNA strand displacement systems. We discuss four previously studied motifs in this abstracted way, and present a new motif based on cooperative 4-way strand exchange. We then show how Chemical Reaction Network implementations can be built out of abstracted motifs, discussing existing implementations as well as presenting two new implementations based on 4-way strand exchange, one of which uses the new cooperative motif. The new implementations both have two desirable properties not found in existing implementations, namely both use only at most 2-stranded DNA complexes for signal and fuel complexes and both are physically reversible. There are reasons to believe that those properties may make them more robust and energy-efficient, but at the expense of using more fuel complexes than existing implementation schemes.
Cite as

Robert F. Johnson and Lulu Qian. Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.DNA.2020.2,
  author =	{Johnson, Robert F. and Qian, Lulu},
  title =	{{Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.2},
  URN =		{urn:nbn:de:0030-drops-129557},
  doi =		{10.4230/LIPIcs.DNA.2020.2},
  annote =	{Keywords: Molecular programming, DNA computing, Chemical Reaction Networks, DNA strand displacement}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact