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

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

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

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

Weblog

STXXL simple logo

Released STXXL 1.4.1

Posted on 2014-10-29 11:17 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ university stxxl

STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i.e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. While the compatibility to the STL supports ease of use and compatibility with existing applications, another design priority is high performance.

More history about STXXL can be found in the blog post to 1.4.0. Today, the second release of the new 1.4 branch was published:

What's new in 1.4.1 ?

See the CHANGELOG for further minor changes.


Screenshot of YouTube View Counter of the "15 Sorting Algorithms in 6 Minutes"

1.000.000 Views of Sound of Sorting YouTube Video

Posted on 2014-10-26 17:30 by Timo Bingmann at Permlink with 0 Comments. Tags: sorting frontpage

Some time last week my YouTube video "15 Sorting Algorithms in 6 Minutes" reached 1 million views. The original video was uploaded on 2013-05-20 which is just 524 days ago, so on average about every 45.2 seconds someone started to watch the video (which itself is about 6 minutes long). The world is a really big place. Most of the views, however, occured in spikes of interest, as seen in the graph below.

The original video contained only 15 algorithms. The program "Sound of Sorting" itself, which was used to create the animations, now contains 30 algorithms or variants. For some of the additional algorithms I also created videos on YouTube, which are also worthwhile watching.

There are two parallel algorithms based on sorting networks, where each left-to-right sweep is one parallel sorting step:

An algorithm, which is optimal in terms of the number of writes to sort the array:

An adaptive sorting algorithm which detects presorted areas, and is used in many modern programming language runtime libraries:

An in-place stable mergesort with O(1) extra space:

And two algorithms, that have a high asymptotic worst-case complexity, and are thus more a joke, but still pretty to watch:

This blog entry continues on the next page ...

Algorithm schema of Recurse Last Parallel Multiway Mergesort

Practical Massively Parallel Sorting -- Basic Algorithmic Ideas

Posted on 2014-10-24 22:30 by Timo Bingmann at Permlink with 0 Comments. Tags: research massive-sorting

Last Friday we were able to finish a technical report on "Practical Massively Parallel Sorting -- Basic Algorithmic Ideas", which is now available on arXiv as 1410.6754 or locally: 1410.6754v1.pdf 1410.6754v1.pdf with source 1410.6754v1.tar.gz 1410.6754v1.tar.gz (130 KiB). A big thanks goes to all the other authors, Michael Axtmann, Peter Sanders, and Christian Schulz.

The report proposes two new hierarchical algorithms "Recurse Last Mergesort" (RLM-Sort) and "Adaptive Multipass Sample Sort" (AMS-Sort), together with randomized data exchange schemes to avoid worst case behavior on large instances.

Download 1410.6754v1.pdf

We now plan to implement some of the new algorithms.

Abstract

To obtain sorting algorithms that scale to the largest available machines, conventional parallel sorting algorithms cannot be used since they either have prohibitive communication volume or prohibitive critical path length for computation. We outline ideas how to combine a number of basic algorithmic techniques which overcome these bottlenecks.

Short screencast from xubuntu.

Recording Frame-Perfect, High-Resolution Screencasts on Linux in the Year 2014

Posted on 2014-06-30 20:35 by Timo Bingmann at Permlink with 0 Comments. Tags: vncrec

Last week I produced a recording of a talk about "STXXL 1.4.0 and Beyond". I thought it would be trivial in the year 2014 to create a frame-perfect high-resolution recording of a PDF presentation slideshow with moving mouse cursor on Linux. I was so wrong.

In the end, I created a patched version of vncrec: now called "vncrec-rgb 0.4", and the tutorial on the vncrec-rgb webpage. But now, why do screen recording with vncrec?

This blog entry continues on the next page ...

First slide of the talk showing the inside of a hard disk

Recording of a Talk "STXXL 1.4.0 and Beyond"

Posted on 2014-06-22 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ stxxl talk frontpage

This is a recording of a talk that I gave last week at the 3rd LSDMA Topical Meeting in Berlin. The talk covers a basic introduction into the STXXL library's features and contains many short code examples that serve as a tutorial.

The slides of the presentation 2014-06-22 STXXL 1.4.0 and Beyond.pdf 2014-06-22 STXXL 1.4.0 and Beyond.pdf are available online and the recorded talk can be seen on Youtube video below.

Download 2014-06-22 STXXL 1.4.0 and Beyond.pdf

And here is the video of the recording: http://www.youtube.com/watch?v=UswxcAOJKBE

This blog entry continues on the next page ...

Ternary search tree used in parallel super scalar string sample sort and LCP-aware tournament tree

Released parallel-string-sorting 0.6
including Parallel Super Scalar String Sample Sort and Parallel Multiway LCP-Mergesort

Posted on 2014-03-09 10:20 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ parallel-string-sorting sorting

This short post announces the second public version of our parallel string sorting project. It is a test framework and algorithm collection containing most sequential and parallel string sorting implementations.

The collection includes parallel super scalar string sample sort (pS5), which we developed and showed to have the highest parallel speedups on modern single-socket multi-core shared memory systems. Additionally, the collection now contains parallel multiway LCP-mergesort, which can be used to speed up string sorting on NUMA multi-socket machines.

See the parallel-string-sorting project page for our technical report and more information about version 0.6.

STXXL simple logo

Released STXXL 1.4.0

Posted on 2013-12-12 16:50 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ university stxxl

STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i.e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. While the compatibility to the STL supports ease of use and compatibility with existing applications, another design priority is high performance.

The project was originally created by Roman Dementiev and Peter Sanders at MPI Informatik in Saarbrücken. It moved to Karlsruhe with them in 2004. After Roman's PhD defense, there was a cooperation with the Algorithm Engineering group at the University of Frankfurt to create better parallel asynchronous sorting. Afterwards, stewardship moved to Frankfurt, where work on flash/SSD drives and various external memory graph algorithms was done.

After a longer stretch without further work, I have decided to take part in future development as a maintainer. This is partly due to my previous experience with it while implement in eSAIS, the external memory suffix and LCP array construction algorithm. And thus, today, the first release of the new 1.4 branch was published:

What's new in 1.4.0 ?


Screenshot of KIT Informatik Webpage

Sound of Sorting: Viral Video on KIT Informatik Webpage

Posted on 2013-10-24 22:45 by Timo Bingmann at Permlink with 0 Comments. Tags: fun sorting frontpage

Little did I expect what would happen when coding the Sound of Sorting demo program. The initial motivation was to create a program that counts the number of comparisons of sorting algorithms, so that the students in our lecture "Algorithms 1" could compare the results of theoretical analysis and real implementations. There were many programs similar to the one I finally made, but there was no program in which the sorting algorithms were easily readable, and not entwined with visualization code. I needed the third-year students to see "simple" code and at the same time have comparison counting and nice visualizations. And none of the existing programs highlighted the internal workings of the algorithms well.

These were the initial goals what became the Sound of Sorting. The program itself took only about seven days of coding work, which was done from the 17th to 21st of May this year. The program had to be finished for the lecture on the 22nd, so there was a hard deadline to meet. The videos were created on the following weekends, and additional algorithms were added later.

Adding sound effects was very much an afterthought, because I had done some similar work previously with manipulating waveforms. Thus there was no learning curve to overcome to have comparisons play sounds. What kind of sound to play, however, needed a lot of artistic touch, trial and error, and the ability to map and transform frequency, oscillators and envelopes as needed. Forming, mixing and bending sound waves as done in the Sound of Sorting requires a mathematical mindset and some appropriate background.

The by-product of this demo program for teaching sort algorithms was the YouTube video "15 Sorting Algorithms in 6 Minutes" which, to my great surprise, went viral on social networks and was viewed 420.000 times to-date. I'm glad that many people with otherwise no connections to algorithmics find this video interesting, and hope that those with further interest view the slower videos, which provide more insight into the algorithms.

Today, the video infected the front page of my current employer: the Department of Informatics at the Karlsruhe Institute of Technology (KIT), which is of course whom I originally made the demo program for. The text, which I wrote for that occasion, can be viewed in German at the original news article about the viral video (or in the screenshots below). I have translated it into English below, since it contains some further comments about the video.

This blog entry continues on the next page ...

Example of intuition behind the inducing process

Presented Short Paper about eSAIS at MASSIVE'13 Workshop

Posted on 2013-09-05 18:00 by Timo Bingmann at Permlink with 0 Comments. Tags: research stringology c++ talk

Today, we presented a shorter version of our work on "Inducing Suffix and LCP Arrays in External Memory" at the MASSIVE Workshop 2013, held adjacently with ESA at ALGO 2013 in Sophia Antipolis, France.

The slides of our presentation 2013-09-05 eSAIS @ MASSIVE'13.pdf 2013-09-05 eSAIS @ MASSIVE'13.pdf and the corresponding short paper massive13esais.pdf massive13esais.pdf are available online via this webpage.

Download 2013-09-05 eSAIS @ MASSIVE'13.pdf
Download massive13esais.pdf

Please refer to the first eSAIS posting for details and source code.

Our thanks goes to all the organizers for making such an inspiring workshop possible.

The Sound of Sorting demo program

Published "The Sound of Sorting" 0.6

Posted on 2013-05-22 23:50 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ university fun sorting

This post announces the publication of my demo program for integer string sorting algorithms, called "The Sound of Sorting". It both visualizes the internals of sorting algorithms, and generates sound effects from the values being compared!

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

There are also many videos of the sorting algorithm on my new YouTube channel.

See the Sound of Sorting project page for the demo program and source code, and more information about version 0.6.

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