Master thesis defense in algorithms.

[Philip Bille]

Master thesis defense. All are welcome. Please forward to other
interested people. For DTU students who consider doing a master thesis in algorithms, I strongly encourage you to go to these defenses.

When: Tuesday, August 14, 11.30-13.00
Location: 308/aud 11
Title: Algorithms for String Comparison on GPUs


Speakers: Kenneth Skovhus Andersen and Lasse Bach Nielsen
Supervisors: Philip Bille and Inge Li Gørtz
External examiner: Rasmus Pagh, IT University of Copenhagen

Abstract:
We consider parallelization of string comparison algorithms, including sequence alignment, edit distance and longest common subsequence. These problems are all solvable using essentially the same dynamic programming scheme over a two-dimensional matrix, where an entry locally depends on neighboring entries. We generalize this set of problems as local dependency dynamic programming (LDDP).

We present a novel approach for solving any large pairwise LDDP problem using graphics processing units (GPUs). Our results include a new superior layout for utilizing the coarse-grained parallelism of the many-core GPU. The layout performs up to 18% better than the most widely used layout. To analyze layouts, we have devised theoretical descriptions, which accurately predict the relative speedup between different layouts on the coarse-grained parallel level of GPUs.

To evaluate the potential of solving LDDP problems on GPU hardware, we implement an algorithm for solving longest common subsequence. In our experiments we compare large biological sequences, each consisting of two million symbols, and show a 40X speedup compared to a state-of-the-art sequential CPU solution by Driga et al. Our results can be generalized on several levels of parallel computation using multiple GPUs.

[Valentin Goranko]

Dear colleagues,

Dr Nils Bulling from the Clausthal University of Technology, Germany, will visit me during August 28-Sept 5 and will give a seminar talk. Assuming — as Paul suggested -- that our section breakfast/meetings and seminar slots will move to Wednesday morning during the coming semester, I have tentatively scheduled his talk (see title and abstract below) to Wednesday, August 29, from 11am.

If any of you is willing to attend the talk but cannot make it in that specific slot, let me know asap. If necessary, I can move the talk to later in that week. The time and venue will be finalized by early next week.  

Med venlig hilsen,
Val
------------------------------------------------------------  

Speaker: Nils Bulling, Clausthal University of Technology
Title: A Game-Theoretic Approach for Optimal Topologies in Opportunistic Networks
Abstract: Opportunistic networks (ONs) are particular types of delay-tolerant networks in which users/network entities participate in order to propagate information. Besides the advantages of these networks (e.g. decentralization, independence of communication infrastructure) they raise new problems regarding for example effectiveness, message routing, message delivery, security issues, and trust. In my talk I introduce a formal description of an ON and of optimal communication topologies, for the non-cooperative and cooperative settings. The approach follows a game theoretic approach and allows users to express properties about how their messages should be handled in the network by means of a logical language (for instance, message privacy may be achieved by requiring that network nodes with internet access should be avoided on the communication path). I briefly discuss the complexity of associated verification and synthesis problems of network topologies.

[Valentin Goranko]

Dear colleagues,

See announcement below. NB: the date of the talk announced in my previous email is shifted to a week later.

Med venlig hilsen,
Val
------------------------------------------------------------  

Time: Wednesday, September 5, 11.00am
Venue: 322/205