panthema / tags / university

Weblog Articles Tagged with '#university'

Weblog Articles

Thrill Tutorial Title Slide

Thrill YouTube Tutorial: High-Performance Algorithmic Distributed Computing with C++

Posted on 2020-06-01 11:13 by Timo Bingmann at Permlink with 0 Comments. Tags: #talk #university #thrill

This post announces the completion of my new tutorial presentation and YouTube video: "Thrill Tutorial: High-Performance Algorithmic Distributed Computing with C++".

YouTube video link: https://youtu.be/UxW5YyETLXo (2h 41min)

Slide Deck: slides-20200601-thrill-tutorial.pdf slides-20200601-thrill-tutorial.pdf (21.3 MiB) (114 slides)

In this tutorial we present our new distributed Big Data processing framework called Thrill (https://project-thrill.org). It is a C++ framework consisting of a set of basic scalable algorithmic primitives like mapping, reducing, sorting, merging, joining, and additional MPI-like collectives. This set of primitives can be combined into larger more complex algorithms, such as WordCount, PageRank, and suffix sorting. Such compounded algorithms can then be run on very large inputs using a distributed computing cluster with external memory.

After introducing the audience to Thrill we guide participants through the initial steps of downloading and compiling the software package. The tutorial then continues to give an overview of the challenges of programming real distributed machines and models and frameworks for achieving this goal. With these foundations, Thrill's DIA programming model is introduced with an extensive listing of DIA operations and how to actually use them. The participants are then given a set of small example tasks to gain hands-on experience with DIAs.

After the hands-on session, the tutorial continues with more details on how to run Thrill programs on clusters and how to generate execution profiles. Then, deeper details of Thrill's internal software layers are discussed to advance the participants' mental model of how Thrill executes DIA operations. The final hands-on tutorial is designed as a concerted group effort to implement K-means clustering for 2D points.

The video on YouTube (https://youtu.be/UxW5YyETLXo) contains both presentation and live-coding sessions. It has a high information density and covers many topics.

Table of Contents

This article continues on the next page ...

Distributed Merge String Sort

IPDPS Paper "Communication-Efficient String Sorting" and Talk Recording

Posted on 2020-05-18 15:30 by Timo Bingmann at Permlink with 0 Comments. Tags: #talk #university

Due to the coronavirus this year's IPDPS conference is held in a virtual fashion, and we sadly missed a chance to visit New Orleans. Instead, I recorded a YouTube video of our conference talk, because the slides usually are illustrations requiring more explanation.

The paper "Communication-Efficient String Sorting", which I coauthored with Peter Sanders and Matthias Schimek, will still be published in the IEEE proceedings. A preprint of the full paper is available on arXiv:2001.08516 and also from this webpage:

2001.08516v1-Communication-Efficient-String-Sorting.pdf 2001.08516v1-Communication-Efficient-String-Sorting.pdf,

There are two versions of the slides: the longer presentation version slides-20200518-distributed-string-sorting-ipdps.pdf below used for the YouTube recording and a short ten page teaser version slides-20200518-distributed-string-sorting-ipdps-short.pdf for the virtual conference.

Download slides-20200518-distributed-string-sorting-ipdps.pdf

The source code and more documentation about the implementations of our communication-efficient distributed string sorting algorithms can be found on my GitHub repository https://github.com/bingmann/distributed-string-sorting.

Matthias Schimek's master thesis, on which this paper and presentation are based on, can be downloaded from this website 2019_Schimek_Distributed_String_Sorting_Algorithms.pdf as well.

Below you can watch the video recording of my presentation, or head over to YouTube: https://youtu.be/uWro8fsfs5I.

This article continues on the next page ...

Cover images of Youtube lecture series

List of Recordings of Lectures and Exercises on YouTube

Posted on 2020-01-28 01:05 by Timo Bingmann at Permlink with 0 Comments. Tags: #university

This post features a list of videos on Youtube of lectures and exercises which I have given at the KIT. The recordings are all in German and were produced semi-automatically by the Center for Media-Learning (Zentrum für Mediales Lernen) at the KIT.

I have listed various entry time points for topics in the lectures for an easier overview. These entry points are only to those parts of the lectures or exercises which I personally presented. The lecture series are mainly presented by Prof Peter Sanders and exercises were jointly given with colleagues.

The main purpose of this article is that I can never seem to find the lectures on Youtube when I am looking for them. And I can now point people to this post if I want to reference some video explanation on a topic I previously gave.

This article continues on the next page ...

COBS data structure

Presentation "COBS: A Compact Bit-Sliced Signature Index" at SPIRE 2019 (Best Paper Award)

Posted on 2019-10-08 15:30 by Timo Bingmann at Permlink with 0 Comments. Tags: #talk #university

Today, I presented our paper "COBS: A Compact Bit-Sliced Signature Index" at the 26th International Symposium on String Processing and Information Retrieval (SPIRE) 2019 in Segovia, Spain. The full paper is available from this webpage:

paper-COBS-A-Compact-Bit-Sliced-Signature-Index.pdf paper-COBS-A-Compact-Bit-Sliced-Signature-Index.pdf,

from the Springer proceedings in LNCS (same content, somewhat differently typeset), and also from arXiv:1905.09624.

I am honored that our paper won the best paper award at SPIRE'19: bestPaperAward.pdf bestPaperAward.pdf

The slides of my presentation at the SPIRE conference are available here: slides-20191008-cobs-spire.pdf slides-20191008-cobs-spire.pdf.

The source code and more documentation about COBS can be found on GitHub:

https://github.com/bingmann/cobs.

Update 2019-11-06: COBS now has a Python interface and can be downloaded from PyPI.

Download slides-20191008-cobs-spire.pdf

Abstract

We present COBS, a COmpact Bit-sliced Signature index, which is a cross-over between an inverted index and Bloom filters. Our target application is to index k-mers of DNA samples or q-grams from text documents and process approximate pattern matching queries on the corpus with a user-chosen coverage threshold. Query results may contain a number of false positives which decreases exponentially with the query length. We compare COBS to seven other index software packages on 100000 microbial DNA samples. COBS' compact but simple data structure outperforms the other indexes in construction time and query performance with Mantis by Pandey et al. in second place. However, unlike Mantis and other previous work, COBS does not need the complete index in RAM and is thus designed to scale to larger document sets.


Photo of the Uniserv prize and my dissertation

(Foto: Andreas Drollinger, KIT)

Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for my Dissertation

Posted on 2019-06-19 19:00 by Timo Bingmann at Permlink with 1 Comments. Tags: #dissertation #university #frontpage

Today was the ceremonial graduation day on which new bachelors, masters, and also Dr.s (PhDs in the Anglo-Saxon world) were celebrated who received their degrees from the department of informatics at the Karlsruhe Institute of Technology (KIT) within the last year. This year's graduation day coincided with the 50th anniversary of the introduction of computer science as a field of study and as a diploma degree.

I was among those honoured for completing the Dr. last year, (see my dissertation page). In total 44 freshly minted Dr.s, 292 masters, and 261 bachelors where celebrated today.

Furthermore, I was awarded the Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for the best dissertation in the field of fast algorithms in the academic year 2017/2018 at the KIT department of informatics by the talent committee of the department.

I would like to thank Uniserv for endowing the department and my dissertation with this prize and especially the talent committee for selecting my work. It was a great and pleasant surprise to receive such a notification in the morning email inbox, which as usual contained many "prize and distant inheritance" emails. But on that day one of them was real, and I nearly overlooked it.

My dissertation was the central purpose in my life for many years, and receiving the prize helps me feel the time was well spent and consider it as confirmation of having furthered the field of informatics a tiny bit. It is rare to receive such honours and I am truly grateful.

Uniserv wrote a much longer honorific press release in German.


Book Cover of Dissertation

Dissertation "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 #frontpage

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.

On July 3rd, I successfully defended my dissertation at the Karlsruhe Institute of Technology and the dissertation text has now been published as a book.

Published Dissertation

My final dissertation PDF is available here: dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf.

It has also been published at the KIT library, on arXiv:1808.00963, and finally as a print-on-demand paperback from Amazon.

The published book cover's background shows a list of most common words in the Wikipedia. The words are sorted and their distinguishing prefix is marked in blue. The cover is available as a double-page PDF: dissertation-cover.pdf dissertation-cover.pdf, and as front and back separately: dissertation-cover-front.pdf dissertation-cover-front.pdf and dissertation-cover-back.pdf dissertation-cover-back.pdf.

The LaTeX source code for my dissertation is available for download: dissertation-source.zip dissertation-source.zip (791 KiB). The complete text is in one .tex file, all figures (except the creative commons logo) are generated from the LaTeX code.

Dissertation Defense Presentation

The slides of my presentation during the defense are available for download here: 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. These backup slides helped greatly in the examination question after the presentation.

Download dissertation-defense-slides.pdf
This article continues on the next page ...

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 #frontpage

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 article continues on the next page ...

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 article continues on the next page ...

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 ?

  • Integrated support for kernel based asynchronous I/O on Linux (new file type "linuxaio"), which exploits Native Command Queuing (NCQ) if available.
  • Merged stxxl::unordered_map branch, which provides a hash map backed by external memory.
  • Replaced struct default_completion_handler with a NULL pointer, thus avoiding superfluous new/delete work for each I/O request.
  • Added stxxl::external_shared_ptr which is a proxy class to allow use of shared_ptr classes inside stxxl containers.
  • Fixing bugs and warnings on 32-bit systems (yes, they still exist).
  • Use atomic_counted_object in class file for request reference counting.
  • Adding support for MinGW-w64 (64-bit) systems with working SJLJ thread implementations.

See the CHANGELOG for further minor changes.


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 ?

  • reorganized source hierarchy into include/ lib/ tests/ examples/ doc/ tools/
  • CMake build system for cross-platform compilation
  • greatly improved documentation with tutorials and examples
  • efficient external matrix operations
  • new containers stxxl::sequence and stxxl::sorter
  • improved .stxxl disk configuration files and additional options
  • combined stxxl_tool of disk benchmarks
  • simple examples and skew3 as real-world stream application
  • support for Visual Studio 2012 and 2013 without Boost
  • important bug fixes in stxxl::queue and stxxl::priority_queue

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 #sound of 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.


The QuadClip Algorithm

Finding Roots of Polynomials by Clipping - Report and Implementation from my Lab Course in Numerical Mathematics

Posted on 2012-03-20 22:29 by Timo Bingmann at Permlink with 0 Comments. Tags: #maths #university #c++

This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

  • Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
  • Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
  • Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
  • Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
  • Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
  • Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf Slides.pdf, which however are not self-explanatory due to my minimum-text presentation style.

This article continues on the next page ...

Drawing of PG(2,3)

Vervollständigung meiner Seminararbeit in Diskreter Mathematik

Posted on 2011-08-31 20:12 by Timo Bingmann at Permlink with 0 Comments. Tags: #maths #university

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf Seminararbeit-Singer-Differenzenmengen.pdf (2.79 MiB).

Download Seminararbeit-Singer-Differenzenmengen.pdf

Zusammenfassung

Die Entwicklung von Differenzenmengen in der Design Theorie begann 1938 mit einer algebraischen Untersuchung endlicher projektiver Geometrien von James Singer. Nach Einführung der wichtigsten Grundbegriffe der Design Theorie und projektiver Geometrien werden in dieser Ausarbeitung die beiden Resultate von Singer entwickelt. Die Existenz einer Kollineation mit Periode \frac{n^{d+1}-1}{n-1} führt zur Definition von Differenzenmengen und beide Ergebnisse liefern elegante Konstruktionsverfahren für PG(d,p^k).


Thumbnail of three slides from completion talk

Completion Talk on My Diploma Thesis / Abschlussvortrag zu meiner Diplomarbeit

Posted on 2009-06-26 13:30 by Timo Bingmann at Permlink with 0 Comments. Tags: #ns-3 #talk #university

Today I gave the final completion presentation for my diploma thesis. The talk showcased a selection of results published in the thesis. Results and experiments are only sketched, as all further detailed information can be found in the thesis PDF itself.

The talk contains side-by-side comparison plots of feature enhancements made to ns-3 and verifications thereof using ns-2. Furthermore, the EDCA extensions implemented in ns-3 are tested against analytically calculated reference values. In the end, a speed test comparison is done between ns-2 and ns-3, which uses the implemented classes to run an experiment scenario identically on both simulators.

The slides are available as PDFs in following two variants:

Presentation Slides (including appendix): ns-3-wifiex-completion-slides.pdf 1455 kB
Presentation Slides (two per page, excluding appendix): ns-3-wifiex-completion-slides-1x2.pdf 1040 kB

Here the table of contents:

  1. Thesis Objectives
  2. Enhancements
    1. Propagation Loss Models
    2. Reception Criteria
    3. Frame Capture Effect
    4. EDCA Implementation
  3. Speed Comparison
  4. Conclusion
  5. Appendix
    1. Enlarged Plots and Figures
      1. Propagation Loss Models
      2. Reception Criteria
      3. Frame Capture Effect
      4. EDCA Implementation

Thumbnail of front page of thesis

Finished My Diploma Thesis on 802.11 in ns-3

Posted on 2009-04-29 17:30 by Timo Bingmann at Permlink with 2 Comments. Tags: #ns-3 #university

After a very exhausting last week with lots of writing and little sleep, my diploma thesis is finally complete. The thesis is on enhancements to the 802.11 model and EDCA (enhanced distributed coordination access) QoS (quality of service) extensions in the new network simulator ns-3.

The thesis is written in English and a copy of the abstract and table of contents is located below. There is also a Zusammenfassung in German.

It is available as PDF in different variants:

Standard PDF version: thesis-bingmann-ns-3-wifi.pdf (3469 kB)
Better printable version (with black links): in RGB color with binding offset (3482 kB)
in CMYK color with binding offset (3381 kB)

Beyond the thesis itself, an extra page contains additional material like the source code, plot results and a snapshot of ns-3 at that time.

Shortened Table of Contents

This article continues on the next page ...

Thumbnail of two slides in halftime talk

Halftime Talk on My Diploma Thesis / Zwischenvortrag zu meiner Diplomarbeit

Posted on 2009-02-06 17:30 by Timo Bingmann at Permlink with 2 Comments. Tags: #ns-3 #talk #university

For the last three months I have been working intensely on my diploma thesis. The thesis will be about 802.11 enhancements and EDCA QoS extensions in the new network simulator ns-3.

Today I gave my halftime presentation about the current status of my efforts. The talk is composed of a short introduction into ns-3, followed by a detailed discussion of WLAN packet reception criteria and finishes with a review of DCF and how EDCA extends it.

Be warned: many slides are not all self-explanatory and therefore less suitable as a casual introduction into the topics. They are slides meant for presentation.

The slides are available as PDFs in following three variants:

Presentation Slides (including "Animations"): ns-3-wifiex-halftime-slides.pdf 1076 kB
Handout Slides (one per page): ns-3-wifiex-halftime-handout.pdf 1036 kB
Handout Slides (four per page): ns-3-wifiex-halftime-handout-2x2.pdf 1028 kB

Here the table of contents:

  1. ns-3 Basics
    1. Introduction
    2. Showcase: Design Patterns
    3. Current State
  2. Wifi in ns-3
    1. State of 802.11
    2. PHY Layer
    3. Signals, Noise and Interference
    4. Short Recapitulation of DCF
    5. QoS with EDCA
  3. Conclusion

Thumbnail of first slide of presentation

NetFundamentals Seminar - Presentation Today

Posted on 2007-01-29 19:00 by Timo Bingmann at Permlink with 0 Comments. Tags: #netfundamentals #university #talk

Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.

Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.

Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.


Thumbnail of a network in the NetFundamentals Technical Report

NetFundamentals Seminar - Technical Report Finished

Posted on 2006-12-19 18:19 by Timo Bingmann at Permlink with 0 Comments. Tags: #netfundamentals #university

Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.

The technical report can be downloaded as PDF (470 KB)

Abstract

One of the computer science papers most worth reading is Gallager's algorithm for minimum delay routing. The merit of Gallager's paper is its rigorous mathematical approach to a problem, which is more often taken care of using heuristics. The approach is founded on a well designed mathematical network model, which is custom-tailored to describe the minimum total delay routing problem. Mathematical observations on the model lead to two conditions for achieving global optimization, which are based on the marginal delay of links and neighbors. From these observations and conditions an iterative, distributed routing algorithm is naturally derived. Gallager finishes his analysis by proving in detail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.

SDIOS06 Shell Screenshot

SDIOS06 - Source Code and Ready-To-Run Image

Posted on 2006-09-14 09:26 by Timo Bingmann at Permlink with 2 Comments. Tags: #sdios06 #university #c++

As promised the source code to SDIOS06 was released under the GPL.

SDIOS06 is a toy operating system developed during the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. It was designed and written by Timo Bingmann, Matthias Braun, Torsten Geiger and Andreas Mähler. Two games were ported to a custom SDL implementation using the VMware "hard"-ware: SDLjump and SuperTux. For more information and screenshots see my blog entry 20060727-SDI-Demo.

The source code archive was published on the L4Ka.org page: http://www.l4ka.org/86.php

A local copy of the source archive (7.4 MB) is available as well. The README file contains a great deal of information about SDIOS06's design and modules. The complete source code can be browsed on the web.

To make demonstration as easy as possible a ready-to-run binary vmware image (3.8 MB) can be downloaded. The image contains SDIOS06 installed on a virtual vmware disk image. The VMware image can be run using the free VMware Player.


Front page of slides

Talk about Study Thesis - Slides and Movie

Posted on 2006-08-02 19:43 by Timo Bingmann at Permlink with 0 Comments. Tags: #compsci study thesis #graphviz #university #talk

At the University of Karlsruhe it is common to give a concluding talk after finishing a study thesis (Studienarbeit). I presented my study thesis "Visualisation of Very Large Graphs" today at the mid-day seminar of the Theoretical Computer Science Group. The slides of the talk are available as PDFs below:

studythesis-talk-visualisation.pdf (1.6 MB) - also available with two slides per page (1.6 MB)or four slides per page (1.6 MB).

During the talk I showed a movie, in which a r-tree of the autobahnen of Germany is constructed incrementally. I actually produced two movies for this purpose: in the first the edges are added in a given sequential order and in the second the order is randomized. Both movies are encoded using transcode and the XviD codec.

Sequential Movie (3.6 MB)
Randomized Movie (5.1 MB)

The talk was received very well, and I may continue in this field with my diploma thesis.

The visualisation library is used by a route planning algorithm developed at the Theoretical Computer Science Group. By integrating my study thesis it was possible to create a Java web applet which animates the route planning algorithm. The Java applet is currently available at http://algo2.iti.uni-karlsruhe.de/schultes/hwy/demo/.

This article continues on the next page ...

SVG Logo der Universität Karlsruhe

Posted on 2006-08-01 19:22 by Timo Bingmann at Permlink with 2 Comments. Tags: #university

Für meinen morgigen Vortrag zur Studienarbeit, habe ich (viel zu) lange nach einem vektor-gezeichneten Logo der Univerisität Karlsruhe (TH) gesucht. Es war nur sehr schwer eines zu finden. Aus einem nach langen Stöbern gefundenen PDF habe ich dann folgende SVG, PDF und EPS Grafiken mit Inkscape erzeugt, die bestimmt jemand anderem etwas Mühe ersparen:

UniKa Logo Farbig SVG SVG (Inkscape) EPS PDF
UniKa Logo Graustufen SVG SVG (Inkscape) EPS PDF

Hinweis: Die Grafiken sind keineswegs offiziell oder sonst wie von der Univerität bereitgestellt.


Presented Practical Work for SDI (System Design and Implementation)

Posted on 2006-07-27 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: #sdios06 #university

Today was the final demo presentation day for the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. Goal of the course was to implement a simple operating system on top of the L4 microkernel, which is developed at the Group.

SDIJump

Our practical course group was one of the two groups to demonstrate a working system on the last day of the semester. The presented operating system contained following basic components:

  • An initial root task,
  • a pager (memory server and task server combined) creating virtual address spaces,
  • a root name server for servers to register their facilities,
  • a minix file system server which extends the name space to files,
  • a (virtual) console server reading keyboard input and writing to the screen buffer,
  • and a limited shell with two utility programs: ls and cat.

Furthermore we utilized the VMWare video "card" to enable graphics output. The "hardware" is well documented in the source code to the X11 video driver contributed by VMWare.

The frame buffer and keyboard input was linked up to a ported SDL implementation. After adding a lot of POSIX library function calls like fopen, opendir and getenv, it was possible to compile our favourite games: SDLjump and SuperTux. Both run very well on our operating system from scratch project.

Some screenshots of the shell, sdijump and supertux are available. In future the whole source code and compiled binary images may become available

A big thank you to my friends Matthias Braun, Torsten Geiger and Andreas Mähler, who made this practical work possible and especially fun!

This article continues on the next page ...

Studienarbeit "Visualisierung sehr großer Graphen" fertiggestellt

Posted on 2006-06-20 17:31 by Timo Bingmann at Permlink with 0 Comments. Tags: #compsci study thesis #graphviz #university #c++

Heute habe ich meine Studienarbeit "Visualisierung sehr großer Graphen" am Institut für Theoretische Informatik fertig gestellt und abgegeben. Die Studienarbeit ist eine 3-4 monatige wissenschaftliche Arbeit und dient als Vorbereitung auf die Diplomarbeit.

Die Studienarbeit kann zum Durchlesen als PDF (2,4 MB) herunter geladen werden. Auf diesen Abschnitt folgenden die deutsche und englische Zusammenfassung der Arbeit. Weiter gibt es eine Version zum Ausdrucken (PDF 15,3 MB) mit einer hochauflösenden Vektorgraphik im Anhang.

Zusammenfassung

In dieser Studienarbeit wird untersucht, mit welchen Methoden sehr große Graphen wie ein Straßennetzwerk von Europa effizient und komfortabel visualisiert werden können. Als Ausarbeitung entsteht ein C++ Rahmenwerk für die Datenhaltung eines Graphen mit Attributen und ein Java Applet, das mit dem Datenhaltungs-Server mittels CORBA kommuniziert. Das Rahmenwerk kann leicht in bestehende Graphanwendungen integriert werden, um deren Algorithmen zu animieren.

Als Basis-Graphstruktur wird ein Adjazenz-Array verwendet und um Strukturen erweitert, die zu jedem Knoten und jeder Kante beliebig viele Attributwerte speichern. Zwei der Knotenattribute werden als Zeichenkoordinaten verwendet. Der Grundgraph und die Datenhaltung der Attributwerte wird auf möglichst kompakte Art und Weise gelöst. Graphanwendungen können eine Liste von temporären Änderungen erzeugen, die mit dem großen globalen Graphen zusammengeführt werden können. Um das Vorgehen der Graph-Algorithmen zu visualisieren, werden deren Funktionsaufrufe in einer Änderungsfolge kodiert, welche als Animation zum Java Client übertragen wird.

Um die Geschwindigkeit einer Ausschnittsanfrage zu erhöhen, wird die mehrdimensionale Indexstruktur R-Tree verwendet. Diese ermöglicht Anfragezeiten, die linear zur Anzahl der zurückgelieferten Kanten und unabhängig vom gewählten Ausschnitt sind. Es können komplexe Filterausdrücke aus Vergleichsbedingungen mit boolschen und arithmetische Operatoren verwendet werden, um die angezeigten Kanten in einem Visualisierungsauschnitt einzuschränken und so komfortabel bestimmte Aspekte der Anwendungs-Algorithmen zu untersuchen oder hervorzuheben.

Als Referenzanwendung wird das Rahmenwerk von der am Institut für Theoretische Informatik in Karlsruhe entwickelten Routenplanungsanwendung zur Visualisiserung mittels Web Applet verwendet.

Abstract

This study thesis investigates and implements methods used to efficiently visualize very large graphs like a street network of Europe. A C++ server framework is designed, which implements a data management library for graphs with attributes. A Java applet communicates with the data server via CORBA and draws sections of the graph. The graph data management library can easily be integrated into existing graph application to visual and animate calculations.

The data management library uses the adjacency array structure for representing the base graph. It is extended by similar data structures to hold an arbitrary number of attributes for each vertex and edge. The data structures are optimized towards highest storage efficiency. To modify the static global graph an application may construct a list of changes, which are efficiently merged into permanent data storage. To visualize the workings of an algorithm its function call sequence can be recorded into a list of graph changes. This change time line can be transfered to the Java client and displayed as an animation.

To accelerate access to arbitrary sections of the graph the spatial index structure R-Tree is used. It enables query times to linearly increase with the number of returned edges and be independent of the section size or position.

Furthermore complex filter expressions including comparisons and arithmetic operators can be applied to limit the displayed edges. This enables the client to explore the graph's details comfortably and highlight interesting aspects of an algorithm.

The graph data management library is used in a route planning application, which is being developed in a research group of the University of Karlsruhe. It will be used to visualize the route using a web applet.


Thumbnail of a slide from the Name Service Design talk

Talk in SDI Lab: Naming Service Design in a Multi-Server Operating System

Posted on 2006-06-01 17:00 by Timo Bingmann at Permlink with 0 Comments. Tags: #sdios06 #university #talk

As part of my work for the SDI Lab work this summer, I held a short talk about how to design a name service in a multi-server operating system like L4.

The slides are available here:

1 Slide per page: NameServiceDesign.pdf 163 kB
2 Slides per page: NameServiceDesign-1x2.pdf 163 kB
4 Slides per page: NameServiceDesign-2x2.pdf 158 kB

Here the table of contents:

  1. Goals
  2. Name Catalogs
    1. Object Representation
    2. Catalogs
  3. IDL Interfaces
    1. Resolve Interface
    2. Bind Interface
  4. Extension / Ideas

Homepage zu meinem Tutorium zu Info3 im WS2005

Posted on 2005-11-16 20:09 by Timo Bingmann at Permlink with 0 Comments. Tags: #university #compsci #tutorium

Hier findet man noch die alte Homepage, welche ich im WS2005 für mein Tutorium in Info3 gemacht habe.

Dort konnten meine Tutoranden ihren Punktestand und eventuelle Neuigkeiten abfragen.


Thumbnail der ersten Seite

Info2 SS2005 Probeklausur der Tutoren

Posted on 2005-07-11 19:11 by Timo Bingmann at Permlink with 0 Comments. Tags: #university #compsci #tutorium

Zum Abschluss der Tutorien von Informatik 2 im Sommersemester 2005 haben die Tutoren zusammen eine Probeklausur erstellt. Diese wurde im letzten Tutorium geschrieben und anschließend einige Lösungshinweise zu den schwierigeren Aufgaben gegeben.

Kopie der ursprünglichen Veröffentlichung:

Achtung: Die auf dieser Seite bereitgestellten Aufgaben spiegeln die Meinung der Tutoren der Vorlesung Informatik 2 wieder. Die Aufgaben stammen nicht von den Verantwortlichen der Informatik 2 Vorlesung. Die Aufgaben sind lediglich als Hinweis zur Vorbereitung der Klausur gedacht. Die Aufgaben der Probeklausur decken nur einen Teil des gesamten Stoffes der Informatik 2 Vorlesung ab. Auch Themen, die in der Probeklausur nicht behandelt werden, sind Teil des Vorlesungstoffes und können in der offiziellen Informatik 2 Klausur behandelt werden.

Alle Tutoren werden die Probeklausur in ihrem Tutorium schreiben lassen, dies erfolgt entweder in der vorletzten oder letzten Vorlesungswoche. Schaut euch die Probeklausur also möglichst nicht an, bevor ihr die Probeklausur im Tutorium schreibt.

Probeklausur: (Revision r44)
Probeklausur Informatik 2 SS2005
Lösungshinweise zur Probeklausur Informatik 2 SS2005

Beim Vorbereiten der Probeklausur sind einige Aufgaben entstanden, die nicht in die Probeklausur übernommen wurden, da sonst der Umfang der Probeklausur weit über 60 min liegen würde. Diese Aufgaben können zum Üben benutzt werden.

Zusätzliche Übungsaufgaben: (Special Director's Cut Limited Edition) (Revision r44)
Übungsaufgaben
Lösungshinweise zu den Übungsaufgaben


Vortrag "Objekt-orientiertes Programmieren in C"

Posted on 2005-06-14 16:19 by Timo Bingmann at Permlink with 0 Comments. Tags: #university #talk #c++

Im Sommersemester 2005 habe ich am Praktikum "Real-Life Programming" am IPD Lehrstuhl der UniKa teilgenommen. Hier platt die Beschreibung von der Homepage zitiert:

Wie programmiert man richtig?

Viele performancekritische Software wird immer noch in C geschrieben. C erlaubt dem Compiler einen sehr großen Optimierungsspielraum, in diesem Praktikum wird geübt, wie dieser ausgenutzt werden kann und wie die dabei auftretenden Klippen zu umschiffen sind.

In diesem Kontext könnt ihr lernen:

  • Den Umgang mit den UNIX Entwicklungswerkzeugen
  • Schreiben von portablem Code
  • Verständnis des Übersetzungsprozesses von C
  • Analysieren des durch Übersetzer erzeugten Assemblertextes
  • Programmieren, so dass der Übersetzer guten Code erzeugen kann
  • Wie man die Performance von Programmen steigern kann
  • Umgang mit großen Projekten
  • Das Finden von Fehlern in großen und alten Softwaresystemen
  • Beherrschen von Debugging und Profiling Werkzeugen
  • Kniffe des C-Präprozessors
  • Die "Geheimnisse" von C

In diesem Zusammenhang haben zwei Komilitonen und ich einen Vortrag über "Objekt-orientiertes Programmieren in C" (ohne ++) ausgearbeitet und gehalten. Weiteres Schwerpunktthema war die Darstellung von C++ in Maschine, also wie der C++ Übersetzer dann die Klassen abbildet.

Vortragsfolien: OOC-Folien.pdf 179 kB
Handout: OOC-Handout.pdf 122 kB
Beispielcode: OOC-Beispiele.tar.gz 4 kB

Hier noch ein Auszug des Inhaltsverzeichnisses:

  1. Objekt-Orientierte Konzepte
  2. OO in C
    • Kapselung und Geheimnisprinzip
    • Vererbung und Polymorphie
    • Generiztiät
  3. Darstellung von C++ in Maschine
    • vtable
    • Name-Mangling
    • Run-Time-Type Information (RTTI)

Diese Folien geben einen kompetenten Überblick über den Themenbereich.