November 2013 - seminaire

Mercredi 11 décembre 2013 : Michael Wilkinson, Johann Bernoulli Institute, University of Groningen, The Netherlands
by Daniela Becker 19 Nov '13

19 Nov '13

Chers collègues, La deuxième session du séminaire Performance et Généricité du LRDE (Laboratoire de Recherche et Développement de l'EPITA) du mois de décembre aura lieu le Mercredi 11 décembre 2013 (14h--15h30), Salle L0 du LRDE. Au programme: * 14h-15h30: A ``Diplomatic'' Parallel Algorithm for the Component Trees of High Dynamic Range Images -- Michael Wilkinson --- Johann Bernoulli Institute, University of Groningen, The Netherlands http://www.cs.rug.nl/~michael/ Component trees are essential tools in several morphological processing methods, such as attribute filtering, or visualization, or the computation of topological watersheds. Algorithms for computation of these trees fall into two main categories: (i) Flood-filling algorithms, exemplified by the algorithms of Salembier et al (1998), Hesselink (2003), and Wilkinson (2011), and (ii) Union-find methods, such as Najman and Couprie (2006), and Berger et al (2007). As images become larger, and parallel computers become commonplace, there is an increased need for concurrent algorithms to compute these trees. The first such algorithm was published by Wilkinson et al in 2008, and was based on the divide-and-conquer principle. It splits up the data spatially, computes local component trees using any arbitrary algorithm which yields a union-find type representation of each node, and glues these together hierarchically. The main drawback of this method is that it does not work well on high-dynamic-range images, because the complexity of the glueing phase scales linearly with the number of grey levels. In the current work, carried out by Moschini, Meijster, and Wilkinson within the HyperGAMMA project, we develop a new algorithm for floating point or high-dynamic-range integer images. It works in a two-tier process, in which we first compute a pilot component tree at low dynamic range in parallel, with one grey level per processor using dynamic quantization, and Salembier's flood-filling method to build the local trees, and the previous parallellization scheme. After this, a refinement stage is performed. This refinement stage is based on the algorithm of Berger et al. As such, the new algorithm combines the two main types of algorithm in a single framework. Timings on images of up to 3.9 GPixel indicate a speed-up of up to 22 on 64 cores. The algorithm is more than 14x faster than the fastest sequential algorithm on the same machine. We will apply the new algorithm to astronomical data sets, including improvements to the SExtractor tool for object detection. The importance of the new algorithm extends beyond computation of component trees because it allows development of a fast alpha-tree algorithm suitable for any pixel-difference metric in case of vector images (i.e. not just $L_\infty$-based metrics on low dynamic range colour images). -- Michael Wilkinson obtained an MSc in astronomy from the Kapteyn Laboratory, University of Groningen in 1993, after which he worked on image analysis of intestinal bacteria at the Department of Medical Microbiology, University of Groningen, obtaining a PhD at the Institute of Mathematics and Computing Science, also in Groningen, in 1995. After this he worked as a researcher at the Johann Bernoulli Institute for Mathematics and Computer Science (JBI) both on computer simulations and on image analysis of diatoms. He is currently senior lecturer at the JBI, working on morphological image analysis and especially connected morphology. Apart from publishing in many journals and conferences, he edited the book ``Digital Image Analysis of Microbes'' (John Wiley, UK, 1998) with Frits Schut, and is member of the Steering Committee of ISMM. Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/. L'entrée du séminaire est libre. Merci de bien vouloir diffuser cette information le plus largement possible. -- Akim Demaille Akim.Demaille(a)lrde.epita.fr

1 0

Mercredi 4 décembre 2013 : Juliusz Chroboczek, Laboratoire PPS, Université Paris-Diderot (Paris 7)
by Daniela Becker 19 Nov '13

19 Nov '13

Chers collègues, La prochaine session du séminaire Performance et Généricité du LRDE (Laboratoire de Recherche et Développement de l'EPITA) aura lieu le mercredi 4 décembre 2013 (11h--12h), Salle L0 du LRDE. Au programme : * 11-12h: CPC: Une implémentation efficace de la concurrence par passage de continuations -- Juliusz Chroboczek, Laboratoire PPS, Université Paris-Diderot (Paris 7) http://www.pps.univ-paris-diderot.fr/~jch/software/cpc/ CPC est une extension concurrente du langage C. Le code CPC, en style à threads, est traduit par le compilateur CPC en un code à style à événements; ce code peut ensuite être exécuté, au choix du programmeur, par des threads natifs « lourds » ou par un ordonnanceur à événements manipulant des structures de données extrêmement légères. Cette technique d'implémentation induit un style de programmation original, où les threads sont « gratuits ». Cependant, le programmeur peut choisir d'utiliser des threads natifs « lourds » lorsque c'est nécessaire, par exemple pour exploiter le parallélisme du matériel ou utiliser des bibliothèques bloquantes. La technique de compilation de CPC est basée sur des techniques formalisées et bien connues de la communauté de la programmation fonctionnelle, telles que la conversion en style à passage de continuations (CPS), le lambda-lifting, ou l'introduction de fonctions terminales. La correction de ces techniques a été prouvée formellement. Dans cet exposé, je donnerai quelques exemples du style typique de programmation en CPC tirées de Hekate, un seeder BitTorrent écrit en CPC. Je décrirai ensuite la transformation en style à passage de continuations et je décrirai la technique de traduction utilisée par le compilateur CPC. -- Juliusz Chroboczek est Maître de Conférences à l'Université Paris-Diderot (Paris 7). Il travaille sur les implémentations efficaces de la concurrence ainsi que sur la problématique du routage dans les réseaux à commutation de paquets. !! Attention : deuxième session en décembre avec un horaire différent (14h00 - 15h30) !! Le mercredi 11 décembre 2013, nous accueillons Michael Wilkinson, Johann Bernoulli Institute, University of Groningen, Pays-Bas, pour un exposé intitulé "A “Diplomatic” Parallel Algorithm for the Component Trees of High Dynamic Range Images". Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/. L'entrée du séminaire est libre. Merci de bien vouloir diffuser cette information le plus largement possible. -- Akim Demaille Akim.Demaille(a)lrde.epita.fr

1 0

Prochaines sessions du séminaire Performance et Généricité
by Daniela Becker 12 Nov '13

12 Nov '13

Chers collègues, Petit rappel, demain, mercredi 13 novembre 2013 aura lieu l'exposé de Dodji Seketeli, Red Hat, intitulé "Address & Thread Sanitizer in GCC: Etat Actuel et Orientation Future" (11h--12h30), Salle Lα du LRDE. En décembre, nous organisons deux séminaires : * le mercredi 4 décembre 2013, 11h--12h, Salle L0 du LRDE, nous accueillons Juliusz Chroboczek, Laboratoire PPS, Université Paris-Diderot (Paris 7) pour nous parler de "CPC: Une implémentation efficace de la concurrence par passage de continuations" * le mercredi 11 décembre 2013 (horaire à définir), nous invitons Michael Wilkinson, Johann Bernoulli Institute, University of Groningen, Pays-Bas, pour nous faire un exposé intitulé "A “Diplomatic” Parallel Algorithm for the Component Trees of High Dynamic Range Images". Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/. L'entrée du séminaire est libre. Merci de bien vouloir diffuser cette information le plus largement possible. -- Akim Demaille Akim.Demaille(a)lrde.epita.fr

1 0