panthema (page 1 of 1 2 3 4 5 6 7 8 9)

Welcome to panthema.net

This website is a diverse collection of interesting ideas, thus it is panthematic. It contains free open-source software and projects (FOSS), computer science research results, blog articles and more, all created by myself, Timo Bingmann. Over the years, the amount of information, source code and other content has grown rather large. All entries are ordered chronologically in the weblog, with some special projects highlighted in the following summary:

Open-Source Projects

2015-08-22
Thrill (in development)
A C++ framework for distributed Big Data computations with emphasis on high performance and a convenient interface like Apache Spark or Flink.
2018-05-28
TLX
Library of Advanced C++ Data Structures and Algorithms
2014-10-29
STXXL 1.4
Library of external memory algorithms, including external block paging and efficient external sorting
2014-09-19
malloc_count 0.7.1
Simple tool for run-time memory usage analysis and profiling under Linux
2014-07-02
vncrec-rgb 0.4
Patched vncrec for frame-perfect high-resolution screencasts.
2014-05-15
The Sound of Sorting 0.6.5
Viral "audibilization" and visualization of sorting algorithms
2014-03-17
SqlPlotTools
Automatically import key=value experimental RESULTS into SQL tables and generate plots from them.
2013-12-12
pmbw 0.6.2
Benchmark tool for parallel memory bandwidth / measurement under Linux
2013-05-07
disk-filltest 0.7.1
Tool to detect bad disks by filling with random data
2013-05-05
STX B+ Tree 0.9
Main memory B+ tree implementation with STL compatible interfaces
2011-01-30
digup 0.6.40
Console tools to verify file integrity by updating MD5 and SHA digest files
2011-01-30
CryptoTE 0.5.390
Text editor with transparent strong encryption, useful for password lists and more.
2010-07-30
STX ExecPipe 0.7.1
Convenient C++ interface to execute child programs connected via Unix pipes.
2009-09-05
Flex Bison C++ Example 0.1.4
Example of using GNU flex and bison in a C++ program.

Computer Science Research

2015-04-03
External Memory Algorithms
Additionally to maintaining STXXL, we also developed a bulk-parallel priority queue for EM.
2014-03-09
Parallel String Sorting
Experimental implementations of many string sorting algorithms, including Parallel Super Scalar String Sample Sort (pS5) and Parallel Multiway LCP-Mergesort
2012-11-19
External Memory Suffix Sorting
Experimental implementation of eSAIS and DC3, two suffix and LCP array construction algorithms for external memory, using STXXL.

Miscellaneous Weblog Posts

2014-10-26  1.000.000 Views of Sound of Sorting YouTube Video
2014-06-22  Recording of a Talk "STXXL 1.4.0 and Beyond"
2013-10-24  Sound of Sorting: Viral Video on KIT Informatik Webpage
2013-05-06  STX B+ Tree Speed Test Measurements on Raspberry Pi (Model B)
2013-05-05  STX B+ Tree Measuring Memory Usage with malloc_count
2013-01-24  Coding Tricks 101: How to Save the Assembler Code Generated by GCC
2008-09-01  C++ Code Snippet - Print Stack Backtrace Programmatically with Demangled Function Names
2007-03-28  C++ Code Snippet - Compressing STL Strings with zlib

Weblog

First slide of the talk

Dissertation Defense Presentation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools"

Posted on 2018-07-03 18:00 by Timo Bingmann at Permlink with 1 Comments. Tags: talk university dissertation

The road to a Dr. title (PhD in the Anglo-Saxon world) is often long, rough, and twisted. First you have to do original research, produce novel results, publish articles, and then write and ultimately publish a dissertation. Defending your research in the dissertation in front of a panel of professors is one of the final milestones on that journey.

Today, I successfully defended my dissertation at the Karlsruhe Institute of Technology and it will be published soon as a book.

The slides of my presentation during the defense are available for download below:
dissertation-defense-slides.pdf dissertation-defense-slides.pdf.

The presentation was only part of the whole defense. My actual slide set also had almost 200 more backup slides, which however were collected from all the other talks already available on this homepage.

Download dissertation-defense-slides.pdf

TLX Logo

Note about the new tlx library of Advanced C++ Data Structures and Algorithms

Posted on 2018-05-28 18:20 by Timo Bingmann at Permlink with 0 Comments. Tags: c++

Last year on February 19th, I started a new github repository called tlx with the goal of de-duplicating code from three projects: Thrill, STXXL, and a private project. The idea came up after a STXXL code workshop in Frankfurt (fashionably called hackathons nowadays).

Link to library: http://github.com/tlx/tlx and Doxygen Documentation

The first main common pieces of code were:

  1. the fast loser tree implementations from MCSTL by Johannes Singler necessary for efficient multiway merging,
  2. my die() macros for testing and run-time assertions,
  3. a common intrusive reference counter called counting_ptr, and
  4. simple but vital std::string manipulation functions missing from the STL.

The initial reason for tlx to come about was to consolidate all the bug fixes to the loser tree implementations that I had scattered across the three projects. Efficient multiway merging is such a fundamental task and there was no universally available C++ library that implements the tournament tree well.

A long search for an appropriate vacant user account with three letters on github lead to "tlx". This is definitely a good C++ namespace name, but to this day, it is unclear what the letters stand for. Template Libraries for CXX? The missing Library for CXX? Template Library and more eXtensions. Have your pick, someday someone will find a good official expansion.

Since its inception, tlx has grown a lot. Its goal is to consolidate algorithms and data structures from multiple projects. In a sense tlx maybe aims to be the Boost for advanced algorithms. The goals and constraints of tlx are:

Currently, tlx contains

And much more, which one can find on the front page of the Doxygen Documentation

First slide of the talk

Presentation "C++ Goodies" at C++ User Group Karlsruhe

Posted on 2017-03-08 00:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk c++

On March 8th, 2017, I gave a 90min talk in German at the C++ User Group Karlsruhe which consisted mostly of live-coding examples of how to use new C++11/14/17 features in a practical setting. The contents were:

The source code I wrote for the presentation and the slides
are available in a github repository https://github.com/bingmann/2017-cpp-goodies.

Furthermore, a recording of talk in German is available on Youtube: https://www.youtube.com/watch?v=EvSZHXmXR1M


First slide of the talk

Presentation "Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++" at IEEE Big Data 2016

Posted on 2016-12-06 16:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk thrill

Today, I gave a presentation of our paper "Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++" at the IEEE International Conference on Big Data 2016 in Washington D.C., USA. An extended technical report of our paper is also available on this website or on arXiv.

The slides of the presentation at the IEEE conference are available here:
slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP-TalkAsGiven.pdf slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP-TalkAsGiven.pdf.

Below a longer version of the slides is available for download:
slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf.
These slides contain additional figures which are useful to understand the DIA operations in Thrill, along with many extra design slides omitted from shorter talks.

Download slides-Thrill-High-Performance-Algorithmic-Distributed-Batch-Data-Processing-with-CPP.pdf

First slide of the talk

Presentation "STXXL and Thrill (Parallel Batch Processing)" at STXXL Workshop in DFG SPP 1736

Posted on 2016-09-21 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: talk thrill stxxl

Today, I gave a technical presentation comparing STXXL and Project Thrill at the STXXL Workshop organized within the DFG SPP 1736. The main topic of the workshop was to determine the future development course of STXXL, and the biggest question in this regard was how to bring more multi-core parallelization into STXXL. Thrill or an adaptation of its ideas may be the solution to this challenge: 2016-09-21 STXXL and Thrill Slides.pdf 2016-09-21 STXXL and Thrill Slides.pdf.

Download 2016-09-21 STXXL and Thrill Slides.pdf

A figure from the technical report

Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++

Posted on 2016-08-20 09:54 by Timo Bingmann at Permlink with 0 Comments. Tags: research c++ thrill

Our technical report on "Thrill: High-Performance Algorithmic Distributed Batch Data Processing with C++" is now available on arXiv as 1608.05634 or locally: 1608.05634v1.pdf 1608.05634v1.pdf with source 1608.05634v1.tar.gz 1608.05634v1.tar.gz (780 KiB).

This report is the first technical documentation about our new distributed computing prototype called Thrill. Thrill is written in modern C++14, and open source under the BSD-2 license. More information on Thrill is available from the project homepage.

Thrill's source is available from Github.

Download 1608.05634v1.pdf

Abstract

We present the design and a first performance evaluation of Thrill -- a prototype of a general purpose big data processing framework with a convenient data-flow style programming interface. Thrill is somewhat similar to Apache Spark and Apache Flink with at least two main differences. First, Thrill is based on C++ which enables performance advantages due to direct native code compilation, a more cache-friendly memory layout, and explicit memory management. In particular, Thrill uses template meta-programming to compile chains of subsequent local operations into a single binary routine without intermediate buffering and with minimal indirections. Second, Thrill uses arrays rather than multisets as its primary data structure which enables additional operations like sorting, prefix sums, window scans, or combining corresponding fields of several arrays (zipping).

We compare Thrill with Apache Spark and Apache Flink using five kernels from the HiBench suite. Thrill is consistently faster and often several times faster than the other frameworks. At the same time, the source codes have a similar level of simplicity and abstraction.


Sketch of a edge-split-attach operation, which breaks a unique exchange from e.

On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs - Diploma Thesis in Mathematics

Posted on 2016-01-14 18:30 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

After a long exhausting period with many interruptions my diploma thesis in mathematics "On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" is finalized and submitted. The full abstract of the thesis is shown below, and an additional German abstract is available further down the page.

The final version of the thesis is available here: thesis pdf Bingmann-On-the-Structure-of-the-Graph-of-Unique-Symmetric-Base-Exchanges-of-Bispanning-Graphs.pdf, and was also uploaded to arXiv.org as 1601.03526.

The underlying problem discussed in the thesis is best explained using a game on a bispanning graph. You can play the game with this Java Applet or using the Java WebStart Launcher (if the Applet does not work). You play Alice's role and want to flip the colors of all edges in the graph. Bob will try to prevent this from happening.

In addition to the thesis itself, the source code of the accompanying computer program is also available. It was used while preparing the thesis to calculate exchanges graphs and to test many hypothesis about bispanning graphs. The program can enumerate all bispanning graphs and their exchange graphs for small numbers of vertices. See the program page for downloadable lists and PDFs of all bispanning graphs for small numbers of vertices.

Abstract

Bispanning graphs are undirected graphs with an edge set that can be decomposed into two disjoint spanning trees. The operation of symmetrically swapping two edges between the trees, such that the result is a different pair of disjoint spanning trees, is called an edge exchange or a symmetric base exchange. The graph of symmetric base exchanges of a bispanning graph contains a vertex for every valid pair of disjoint spanning trees, and edges between them to represent all possible edge exchanges. We are interested in a restriction of these graphs to only unique symmetric base exchanges, which are edge exchanges wherein selecting one edge leaves only one choice for selecting the other. In this thesis, we discuss the structure of the graph of unique symmetric edge exchanges, and the open question whether these are connected for all bispanning graphs.

This abstract problem can be nicely rephrased into a coloring game with two players: Alice and Bob are given a bispanning graph colored with two disjoint spanning trees, and Alice gets to flip the color of any edge. This creates a cycle in one color and a cut in the other, and Bob must then flip a different edge to repair the constraint that both colors represent disjoint spanning trees. Alice's objective is to invert the color of all edges in the graph, and Bob's to prevent this. We are interested in whether Alice can find a sequence of unique edge exchanges for any bispanning graph, since these leave Bob no choice in which edge to select, hence allowing Alice to win with certainty.

In this thesis, we first define and discuss the properties of bispanning graphs in depth. Intuitively, these are locally dense enough to allow the two disjoint spanning trees to reach all vertices, but sparse enough such that disjoint edge sets do not contain cycles. The whole class of bispanning graphs can be inductively constructed using only two operations, which makes the class tractable for inductive proofs.

We then describe in detail directed, undirected, and simplified versions of edge exchange graphs, first with unrestricted edge exchanges, and then with the restriction to unique symmetric base exchanges. These exchange graphs are related to a set of conjectures put forth by White in 1980 on base exchanges in matroids, and also to conjectures on cyclic base orderings of matroids. To date, these conjectures have not been proven in full generality, despite overwhelming computational evidence.

As steps towards showing the conjecture that the graph of unique symmetric base exchanges is connected for all bispanning graphs, we prove a composition method to construct the unique exchange graph of any bispanning graph from the exchange graphs of smaller bispanning graphs. Furthermore, using a computer program developed alongside this thesis, we are able to enumerate and make statements about all small bispanning graphs and their exchanges graphs.

Our composition method classifies bispanning graphs by whether they contain a non-trivial bispanning subgraph, and by vertex and edge connectivity. For bispanning graphs containing a non-trivial bispanning subgraph, we prove that the unique exchange graph is the Cartesian graph product of two smaller exchange graphs. For 2-vertex-connected bispanning graphs, we show that the bispanning graph is the 2-clique sum of two smaller bispanning graphs, and that the unique exchange graph can be built by joining their exchange graphs and forwarding edges at the join seam. And for all remaining bispanning graphs, we prove a composition method at a vertex of degree three, wherein the unique exchange graph is constructed from the exchange graphs of three reduced bispanning graphs.

We conclude this thesis with ideas and evidence for future approaches to proving the connectivity of the unique exchange graphs and show the most difficult bispanning graphs instances.

This blog entry continues on the next page ...

First slide of the talk

Presentation "Massive Suffix Array Construction with Thrill" at DFG SPP 1736 Annual Colloquium

Posted on 2015-10-01 19:40 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ talk thrill

Today, we gave an overview presentation of the vision behind Project Thrill, its current state, and how it will be used to implement suffix and LCP array construction, and many other distributed algorithms: 2015-10-01 Massive Suffix Array Construction with Thrill.pdf 2015-10-01 Massive Suffix Array Construction with Thrill.pdf.

Download 2015-10-01 Massive Suffix Array Construction with Thrill.pdf

Thumbnail of a small ternary search tree used for classification, and LCP-aware tournament tree.

Publication: Engineering Parallel String Sorting in Algorithmica Journal

Posted on 2015-09-22 15:46 by Timo Bingmann at Permlink with 0 Comments. Tags: research sorting university

Our paper "Engineering Parallel String Sorting" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf Engineering-Parallel-String-Sorting.pdf.

Download Engineering-Parallel-String-Sorting.pdf

Please refer to the main parallel-string-sorting page for details and source code.

This blog entry continues on the next page ...

emacs at work, editing the file that turns into this webpage.

emacs Tutorial: Beating the Learning Curve - From Zero to Lightspeed

Posted on 2015-08-19 13:21 by Timo Bingmann at Permlink with 2 Comments. Tags: talk

At our institute I gave an ambitious presentation today which showcased much of my daily work flow in emacs. People have titled it the "emacs lightshow" due to the speed of flashing and changing lights on my screens. Of course, the idea is to show people what emacs can do and at the same time get them to try it. Emacs is different from other editors in that it is a life operating system that is infinitely complex, is constantly extended, and adapts to what you need.

For this presentation I made an emacs tutorial. There are many emacs tutorials online, and they are probably better than this one. However, I focused on listing something like the top 100 key command sequences that you need in real day-to-day editing life, instead of the most flashy features. This makes this tutorial something that you can print out, and go through step-by-step once to try everything out; and then start over and learn the most important keys from the top.

The emacs tutorial is available as a PDF: emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.pdf emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.pdf

Download emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.pdf

or available as the org-mode source file: emacs Tutorial - Beating the Learning Curve - From Zero to Lightspeed.org

and in my github .emacs.d repo: https://github.com/bingmann/dot-emacs.git

Show Page: 1 2 3 4 5 6 7 8 9 Next >
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2018 Timo Bingmann - Impressum