Deprecated: Assigning the return value of new by reference is deprecated in /u/deptinfo/dalle/www/wiki2/cookbook/sourceblock.php on line 153

Warning: Cannot modify header information - headers already sent by (output started at /u/deptinfo/dalle/www/wiki2/cookbook/sourceblock.php:153) in /u/deptinfo/dalle/www/wiki2/pmwiki.php on line 885
Olivier Dalle's Corner | Main / Open Positions

From Olivier Dalle's Corner

Main: Open Positions

No internship position available at the moment for working with Olivier.

Non local students must send resume and motivation letter to apply.
Local student may apply using the standard procedure.

Using transactional memory for implementing a multithreaded simulation engine

This subject is offered as a 1st year of master project for a group of 2–4 students OR as a Master 2 subject.

Context
Heap structures are critical for the performance of many applications. One good exemple is Discrete-Event Simulation (DES), in which the events which represent the history of the system are stored randomly in such a structure during the simulation, but they have to be processed in in strict increasing order (of occurence time) to follow the chronology. In order to speed-up and/or scale-up the execution of such DES, various algorithms have been proposed for distributing simulations on multiple computers and keep the global synchronisation, using message passing. The advent of many-core architctures opens new perspectives for the parallelization of such algorithms on multiple cores, using multiple threads and shared-memory.
Goal
The goal of this intership/project is to implement and evaluate the performance of such a multi-threaded heap algorithm based on Transactional Memory. Transactional Memory is recent technique proposed to replace the use of locks and mutual exclusion in concurrent algorithms running on a shared-memory architecture. As its name suggests, it borrows the idea of transactions to the database world : when a concurrent action is needed, a transaction is initiated in memory; if the action completes without conflict (with other hreads), the transaction is committed and the new memory state is kept; if the action generates a conflict, some of the conflicting transactions have to be rolled-back (ie. the new memory state is dropped) and restarted. This new technique was proposed a few years ago, but it was only virtually available by means of software emulation. Major actors, such as Intel and IBM have recently started to build or announce hardware support for Transactional Memory in their latests products (Eg. IBM BlueGene/Q super computer already has it[1], and the next generation of Intel Processors is announced with an extension to instruction set for the support of TM[2]).
Work to do
The work to do is to investigate the use of such a TM software emulation library to implement a multi-threaded Heap data structure. The library we chose is TBoost.STM[3,4], a proposed extension to the Boost C++ library. The work to be done during the TER is the following:
  • implement or retrieve various multi-threaded heap data-stractures in C++ using algorithms:
    • without transactional memory , as found in the literature
    • with transactional memory, custom designed
  • run performance comparisons between the various implementations
    • Build a performance benchmark
    • Run experiments on a multi-core computer
Pre-requisites
C/C++ programming, experience with Posix threads and concurrent programming (locks, semaphores)
References
Retrieved from http://deptinfo.unice.fr/~dalle/wiki2/?n=Main.OpenPositions
Page last modified on May 13, 2013, at 04:14 PM CET