2 Search Results for "Abel, Norbert"

Document
DOI: 10.4230/LIPIcs.SEA.2026.13
Practical Parallel Block Tree Construction

Authors: Robert Clausecker, Florian Kurpicz, and Etienne Palanga

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-n text that supports access, rank, and select queries while requiring only O(z log n/z) words of space, where z is the number of Lempel-Ziv factors of the text. In other words, its space requirements are asymptotically comparable to those of the compressed text itself. In practice, block trees offer query performance comparable to that of state-of-the-art compressed rank and select indices. However, their construction is significantly slower, and the fastest known construction algorithms additionally require a significant amount of working memory. To address these limitations, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar construction speed than the currently fastest block tree construction algorithm on a single core and is up to eight times faster using 64 cores, while requiring an order of magnitude less memory. Overall, we achieve a speedup of up to 15.5 on 64 cores, which is in line with the parallel construction of the Lempel-Ziv compression.
Cite as

Robert Clausecker, Florian Kurpicz, and Etienne Palanga. Practical Parallel Block Tree Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{clausecker_et_al:LIPIcs.SEA.2026.13,
  author =	{Clausecker, Robert and Kurpicz, Florian and Palanga, Etienne},
  title =	{{Practical Parallel Block Tree Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.13},
  URN =		{urn:nbn:de:0030-drops-260175},
  doi =		{10.4230/LIPIcs.SEA.2026.13},
  annote =	{Keywords: block tree, shared memory, compression, SIMD, Karp-Rabin fingerprints}
}
Document
DOI: 10.4230/DagSemProc.10281.7
Design and Implementation of an Object-Oriented DPR-Framework

Authors: Norbert Abel

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Nowadays, two innovative future trends regarding hardware development and hardware description can be found. The first trend concerns the hardware itself. Modern Xilinx FPGAs provide the possibility to be reconfigured partially and dynamically - which is called dynamical partial reconfiguration (DPR). DPR opens a huge field of new functionalities on FPGAs. However, using DPR means struggling with architectural details of the used FPGAs and the according synthesis and implementation tools. A developer would focus most of the time on DPR and only a small part of the time on the implementation of the actual modules - of course that is the opposite of what hardware engineers want to do. The second trend concerns the way hardware is described. Many hardware developing groups are looking forward to an HDL which operates on the algorithmic level, since this would come with a significant increase in productivity. The aim is to be able to translate common software algorithms to hardware in an efficient way (which is called high-level synthesis or HLS). Although both DPR and HLS are important future trends regarding hardware design, they develop quite independently. Today's software-to-hardware compilers focus on conventional hardware and therefore have to remove dynamic aspects such as the instantiation of calculating modules at runtime. Even object-oriented languages like SystemC do not support the dynamic instantiation of objects (that means the usage of new or delete outside of the constructor) for synthesis at all. On the other hand, DPR tools are working on the lowest possible layer regarding FPGAs: the bitfile level. Our research focuses on the design and the implementation of a Framework combining the two technologies, since this has the potential to kill two birds with one stone. Firstly, DPR can change the programming paradigm in future HDLs regarding dynamic instantiations. Dynamic parts would not have to be removed any longer but could be realized on the target FPGA using DPR. Secondly, a high-level language support of DPR technologies could help end its shadowy existence and turn it into a commonly used method.
Cite as

Norbert Abel. Design and Implementation of an Object-Oriented DPR-Framework. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{abel:DagSemProc.10281.7,
  author =	{Abel, Norbert},
  title =	{{Design and Implementation of an Object-Oriented DPR-Framework}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.7},
  URN =		{urn:nbn:de:0030-drops-28365},
  doi =		{10.4230/DagSemProc.10281.7},
  annote =	{Keywords: FPGA, DPR, HLS, Object-Orientation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2010

  • Refine by Author
  • 1 Abel, Norbert
  • 1 Clausecker, Robert
  • 1 Kurpicz, Florian
  • 1 Palanga, Etienne

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Computer systems organization → Single instruction, multiple data
  • 1 Theory of computation → Data compression
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 DPR
  • 1 FPGA
  • 1 HLS
  • 1 Karp-Rabin fingerprints
  • 1 Object-Orientation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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