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