parallelization strategy

The global design is inspired by an old presentation already published on slideshare.

1. 1 Is it an open door to R. MAHMOUDI – A3SI Laboratory – 2009 April common parallelization strategy for topological operators on multi-core multi-thread architecture ?

2. 2 R. MAHMOUDI – A3SI Laboratory – 2009 April Summary Parallel thinning operator Future work General framework Discussion

3. 3 R. MAHMOUDI – A3SI Laboratory – 2009 April Summary Parallel thinning operator Future work General framework Discussion

4. 4 R. MAHMOUDI – A3SI Laboratory – 2009 April General framework 1. Scientific and technical context (1) Image processing operators Dynamic redistribution Thresholding Point-to-Point operators Associated class Linear filters Opening Thinning Crest restoring Smoothing Watershed Closing Local operators Morphological operators Topological operators Global operators Fourier Transformation Euclidean Distance Transformation Not-linear filters Attributed Filter

5. 5 R. MAHMOUDI – A3SI Laboratory – 2009 April General framework 1. Scientific and technical context (2) Point-to-Point operators (Associated class) Vs ( Parallelization strategies ) Local operators Morphological operators Topological operators Global operators Sienstra [1] (2002) Wilkinson [2] (2007) [1] F. J. Seinstra, D. Koelma, and J. M. Geusebroek, “A software architecture for user transparent parallel image processing”. [2] M.H.F. Wilkinson, H. Gao, W.H. Hesselink, “Concurrent Computation of Attribute Filters on Shared Memory Parallel Machines”. [3] A. Meijster, J. B. T. M. Roerdink, and W. H. Hesselink, “A general algorithm for computing distance transforms in linear time” . Meijster [3]

6. 6 R. MAHMOUDI – A3SI Laboratory – 2009 April General framework 2. Ph. D. objectives (1) Topological operators Thinning operator [1] Crest restoring [1] 2D and 3D smoothing [2] Watershed based on w-thinning [3] Watershed based on graph [4] Homotopic kernel transformation [5] Leveling kernel transformation [5] [1] M. Couprie, F. N. Bezerra, and G. Bertrand, “Topological operators for grayscale image processing”, [2] M. Couprie, and G. Bertrand, “Topology preserving alternating sequential filter for smoothing 2D and 3D objects”. [3] G. Bertrand, “On Topological Watersheds”.   [4] J. Cousty, M. Couprie, L. Najman and G. Betrand “Weighted fusion graphs: Merging properties and watersheds”. [5] G. Bertrand, J. C. Everat, and M. Couprie, "Image segmentation through operators based on topology“ common parallelization strategy

7. 7 R. MAHMOUDI – A3SI Laboratory – 2009 April General framework 2. Ph. D. objectives (2) Shared Memory Machine CPU 1 CPU 2 CPU 3 CPU n Random Access Memory MIMD Machine : (Execute several instruction streams in parallel on different data) Main Architectural Classes SISD machines SIMD machines MISD machines Distributed Memory System

8. 8 R. MAHMOUDI – A3SI Laboratory – 2009 April General framework 2. Ph. D. objectives (3) Common parallelization strategy of topological operators on multi-core multithread architecture (MIMD Machines – Shared Memory System)? Unifying parallelization method of topological operators class ( Algorithmic level ) Implementation Methodology and optimization techniques on multi-core multithread architecture (Architecture level ). Needs Main Objectives

9. 9 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator Future work General framework Discussion

10. 10 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 1. Theoretical background Algorithm : λ –Skeleton (input Ғ , λ ; output : Ғ ) Repeat until stability Among all the points which are λ –deletable and not λ –end Select a point x of minimal value ; F(x)= αˉ( x,F) Filtered thinning method that allows to selectively simplify the topology , based on a local contrast parameter λ . (b) filtered skeleton with λ = 10. (a) After Deriche gradient operator

11. 11 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 1. Parallelization strategy (1) Define search area Start parallel characterization Create new shared data structure End parallel characterization Merge modified search area Restart process until stability

12. 12 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 1. Parallelization strategy (2) SDM-Strategy ( Divide and conquer principle ) Up level DATA PARALLELISM Down level THREAD PARALLELISM MIXED PARALLELISM

13. 13 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 1. Parallelization strategy (3)

14. 14 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 2. Coordination of threads (1) Thread 1 Fail Success Blocked Lock() Unlock() Push() Thread 2 First implementation using a lock-based shared FIFO queue.

15. 15 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 2. Coordination of threads (2) Thread 1 Semaphore Lock() and access semaphore Unlock() and leave semaphore Push() Thread 2 Second implementation using a private-shared concurrent FIFO queue

16. 16 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 3. Performance testing (1) P4 660 E8400 E5335 E5405 Arch. Pentium 4 Core 2 Duo Quad-core Octo-core CPU Speed 3.60 GHz 3 GHz 2 GHz 2 GHz Bus Speed 800 MHz 1333 MHz 1333 MHz 1333 MHz L2 Size 800 MHz 6 MB 8 MB 12 MB L2 Speed 3.6 GHz 3 GHz 2 GHz 2 GHz package Type LGA775 LGA775 LGA771 LGA771 Techno. 90 nm 45 nm 65 nm 45 nm

17. 17 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 3. Performance testing (2) First implementation using a lock-based shared FIFO queue.

18. 18 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 3. Performance testing (3) Second implementation using a private-shared concurrent FIFO queue

19. 19 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator 4. Conclusion Non-specific nature of the proposed parallelization strategy. Threads coordination and communication during computing dependently parallel read/write for managing cache-resident data 1 2

20. 20 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator Future work General framework Discussion

21. 21 R. MAHMOUDI – A3SI Laboratory – 2009 April Future work 1. Extension Parallel Thinning Operator SDM - Strategy Performance enhancement (speed up) Efficiency (work distribution) Cache miss Crest restoring IMBRICATE TWO Operators

22. 22 R. MAHMOUDI – A3SI Laboratory – 2009 April Future work 2. New parallel topological watershed Parallel watershed Operator SDM - Strategy Performance enhancement (speed up) Efficiency (work distribution) Cache miss % Achievement 80%

23. 23 R. MAHMOUDI – A3SI Laboratory – 2009 April Parallel thinning operator Future work General framework Discussion

24. 24 R. MAHMOUDI – A3SI Laboratory – 2009 April Discussion Introduce future programming model (make it easy to write programs that execute efficiently on highly parallel C.S) Introduce new “Draft” to design and evaluate parallel programming models (instead of old benchmark) Maximize programmer productivity , future programming model must be more human-centric (than the conventional focus on hardware or application)

25. 25 R. MAHMOUDI – A3SI Laboratory – 2009 April