Date: 25 Jan 2008
From: jyrki@diku.dk
Subject: PE-lab's annual report 2007

Performance Engineering Laboratory (PE-lab)
http://www.diku.dk/~jyrki/PE-lab/

* Annual Report 2007

The following people have contributed for the research done at the
PE-lab during the year 2007:

Kasper Egdø (M.Sc. student; expected graduation 2008)
Amr Elmasry (External collaborator, Alexandria University)
Joachim Gudmundsson (External collaborator, National ICT Australia)
Torben Hagerup (External collaborator, Universität Augsburg)
Claus Jensen (Ph.D. student; expected graduation 2008)
Jyrki Katajainen (Lab leader)
Damian Merrick (External collaborator, University of Sydney)
Cahya Ong (External collaborator, University of New South Wales)
S. Srinivasa Rao (External collaborator, University of Aarhus)
Jens Rasmussen (M.Sc. student; expected graduation 2009)
Thomas Wolle (External collaborator, National ICT Australia)
Lars Yde (Ph.D. student; expected graduation 2012)

Other members of the group were:

Søren Gade (M.Sc. student)
Andrei Bjarke Moskvitin Josephsen (M.Sc. student)
Anders Kristian Lyhne Thøgersen (M.Sc. student; on Erasmus exchange at
Dresden University of Technology)

Most research articles written are available online via the CPH STL
website http://cphstl.dk, and theses written via the PE-lab's home
page http://www.diku.dk/~jyrki/PE-lab/.

A more detailed description of the projects completed or started in
2007 is given below.


* Comparison complexity of data-structural problems [Amr, Claus, and Jyrki]

We continued our theoretical research on the comparison complexity of
various data-structural problems (priority queues, meldable priority
queues, double-ended priority queues, and meldable double-ended
priority queues).  The basic goal was to produce journal versions of
our earlier publications that had appeared in conference proceedings
and technical reports (in the CPH STL report series).

Research output: 2 accepted journal papers (ACM Transactions on
Algorithms, Acta Informatica), 2 other journal submissions, and 1
conference paper (CATS'07)


* Computational geometry of moving points [Joachim, Damian, Cahya,
  Thomas, and Jyrki]

My visit at NICTA (National ICT Australia) in Sydney made me take up
the research on computational geometry. (I was active in this area
twenty years ago.)  The group in Sydney had many open problems on
moving points which are relevant in many application areas. We
studied two of those (trajectory compression and finding popular
places) during my short visit at Sydney Research Laboratory.

A trajectory is a sequence of locations, each associated with a time
stamp, describing the movement of a point.  In the published work, we
studied the problem of compressing planar trajectories such that the
most common spatio-temporal queries can still be answered
approximately after the compression has taken place.  In the process,
we developed an implementation of the Douglas-Peucker
path-simplification algorithm which works efficiently even in the case
the polygonal path given as input is allowed to self-intersect.

Research output: 1 conference paper (ISAAC'07)


* Strong guarantees for generic software components [Jyrki]

The development of the CPH STL (www.cphstl.dk) has continued. At
present the most important goal is to design library components that
are highly reliable. My students have done most of the implementation
work whereas I have been responsible for the design of the components.

Research output: 3 technical reports (CPH STL Reports 2007-3, 2007-4,
and 2007-5)

* Implementing and benchmarking meldable priority queues [Jens]

An implementation of the newly designed data structure, relaxed weak
queue by Elmasry, Jensen, and Katajainen, was produced.  The
programming language used in the production was C++, and the
implementation supports the container requirements specified in the
C++ standard and provides constant-time iterator operations.  As
relaxed weak heaps have never been implemented before, the sole focus
of the project was to produce a correct implementation of a meldable
priority queue that supports the operations find-min, insert and
decrease in O(1) worst-case time; delete in O(lg n) worst-case time, n
denoting the number of elements stored prior to the operation; and
meld in O(min{lg m, lg n}) worst-case time, m and n denoting the sizes
of the sub-collections to be melded.  Lastly, relaxed weak queues were
compared experimentally with other meldable priority queues.

Research output: 1 technical report (CPH STL Report 2008-1)


* Compact dictionaries [Srinivasa and Jyrki]

A dictionary is a classical data structure that stores a (multi)set of
elements and supports searches, insertions, and deletions. An in-place
dictionary is one that requires only O(1) words of extra storage in
addition to the elements stored. Recently, an optimal in-place
dictionary was developed, but the method does not work for multisets.
In this study we asked what is the most compact dictionary that can
maintain a dynamic multiset. Our most compact dictionary requires
O(n/lg n) bits and O(1) words in addition to the n elements stored. It
is an open problem whether a more compact dictionary exists.

Research output: a research paper in preparation


* Software transactional memory [Kasper]

An increasing number of cores (or CPUs) per computer is creating a
need for good programming tools for exploiting these cores. Locks are
traditionally used but issues with deadlocks and race conditions
easily arise and choosing the correct granularity for locking is often
non-trivial. In addition, the usage of locks does not generally enable
the programmer to compose existing correct lock-based program pieces
into a new larger correct lock-based pieces.

An alternative to locks is Software Transactional Memory (STM) which
is a concurrency approach that does not use locks as its primary
method. Instead an STM system relies on an optimistic concurrency
control mechanism; using memory transactions similar to transactions
in database systems. Programs built with the STM approach avoid
deadlocks and race conditions and enable composition of program pieces
from existing pieces.

In this work, design criteria for building an STM system for C++ were
explored and some Standard Template Library containers were built on
top of such a system. The emphasis was put on correctness, not on
performance.  The system was developed having the generic programming
approach in mind. It can be used in template-based code which directly
facilitates the reuse of existing algorithms and data structures.

Research output: Master's thesis