2 Search Results for "Pearlmutter, Barak A."

Document
DOI: 10.4230/LIPIcs.CSL.2023.6
Functorial String Diagrams for Reverse-Mode Automatic Differentiation

Authors: Mario Alvarez-Picallo, Dan Ghica, David Sprunger, and Fabio Zanasi

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Abstract
We formulate a reverse-mode automatic differentiation (RAD) algorithm for (applied) simply typed lambda calculus in the style of Pearlmutter and Siskind [Barak A. Pearlmutter and Jeffrey Mark Siskind, 2008], using the graphical formalism of string diagrams. Thanks to string diagram rewriting, we are able to formally prove for the first time the soundness of such an algorithm. Our approach requires developing a calculus of string diagrams with hierarchical features in the spirit of functorial boxes, in order to model closed monoidal (and cartesian closed) structure. To give an efficient yet principled implementation of the RAD algorithm, we use foliations of our hierarchical string diagrams.
Cite as

Mario Alvarez-Picallo, Dan Ghica, David Sprunger, and Fabio Zanasi. Functorial String Diagrams for Reverse-Mode Automatic Differentiation. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alvarezpicallo_et_al:LIPIcs.CSL.2023.6,
  author =	{Alvarez-Picallo, Mario and Ghica, Dan and Sprunger, David and Zanasi, Fabio},
  title =	{{Functorial String Diagrams for Reverse-Mode Automatic Differentiation}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.6},
  URN =		{urn:nbn:de:0030-drops-174674},
  doi =		{10.4230/LIPIcs.CSL.2023.6},
  annote =	{Keywords: string diagrams, automatic differentiation, hierarchical hypergraphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.10
Concurrent Robin Hood Hashing

Authors: Robert Kelly, Barak A. Pearlmutter, and Phil Maguire

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
In this paper we examine the issues involved in adding concurrency to the Robin Hood hash table algorithm. We present a non-blocking obstruction-free K-CAS Robin Hood algorithm which requires only a single word compare-and-swap primitive, thus making it highly portable. The implementation maintains the attractive properties of the original Robin Hood structure, such as a low expected probe length, capability to operate effectively under a high load factor and good cache locality, all of which are essential for high performance on modern computer architectures. We compare our data-structures to various other lock-free and concurrent algorithms, as well as a simple hardware transactional variant, and show that our implementation performs better across a number of contexts.
Cite as

Robert Kelly, Barak A. Pearlmutter, and Phil Maguire. Concurrent Robin Hood Hashing. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kelly_et_al:LIPIcs.OPODIS.2018.10,
  author =	{Kelly, Robert and Pearlmutter, Barak A. and Maguire, Phil},
  title =	{{Concurrent Robin Hood Hashing}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.10},
  URN =		{urn:nbn:de:0030-drops-100701},
  doi =		{10.4230/LIPIcs.OPODIS.2018.10},
  annote =	{Keywords: concurrency, Robin Hood Hashing, data-structures, hash tables, non-blocking}
}
  • Refine by Author
  • 1 Alvarez-Picallo, Mario
  • 1 Ghica, Dan
  • 1 Kelly, Robert
  • 1 Maguire, Phil
  • 1 Pearlmutter, Barak A.
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Mathematics of computing → Automatic differentiation
  • 1 Theory of computation → Categorical semantics

  • Refine by Keyword
  • 1 Robin Hood Hashing
  • 1 automatic differentiation
  • 1 concurrency
  • 1 data-structures
  • 1 hash tables
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2023

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