Download to read offline
Wilkinson [2](2007)Meijster [3][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” .R. MAHMOUDI – A3SI Laboratory– 2009 April](https://image.slidesharecdn.com/atelieravril2009fv-100111070920-phpapp02/75/parallelization-strategy-5-2048.jpg)
![6General framework2. Ph. D. objectives (1)Topological operatorsThinning operator [1]commonparallelizationstrategyCrest 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“ R. MAHMOUDI – A3SI Laboratory– 2009 April](https://image.slidesharecdn.com/atelieravril2009fv-100111070920-phpapp02/75/parallelization-strategy-6-2048.jpg)
parallelization strategy
- 1. 1Is it anopen door tocommon parallelization strategy for topological operators on multi-core multi-thread architecture ?R. MAHMOUDI – A3SI Laboratory– 2009 April
- 2. 2SummaryGeneral frameworkParallel thinningoperatorFuture workDiscussionR. MAHMOUDI – A3SI Laboratory– 2009 April
- 3. 3SummaryGeneral frameworkParallel thinningoperatorFuture workDiscussionR. MAHMOUDI – A3SI Laboratory– 2009 April
- 4. 4General framework1. Scientificand technical context (1)Image processingoperatorsFourierTransformationOpeningThinningDynamic redistributionLinear filtersClosingCrest restoringNot-linear filters Euclidean DistanceTransformationThresholdingSmoothingAttributedFilterWatershed Associated classTopological operatorsMorphological operatorsLocal operatorsPoint-to-Point operatorsGlobaloperatorsR. MAHMOUDI – A3SI Laboratory– 2009 April
- 5. 5General framework1. Scientificand technical context (2)(Associated class) Vs (Parallelizationstrategies)GlobaloperatorsTopological operatorsMorphological operatorsLocal operatorsPoint-to-Point operatorsSienstra [1](2002)Wilkinson [2](2007)Meijster [3][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” .R. MAHMOUDI – A3SI Laboratory– 2009 April
- 6. 6General framework2. Ph.D. objectives (1)Topological operatorsThinning operator [1]commonparallelizationstrategyCrest 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“ R. MAHMOUDI – A3SI Laboratory– 2009 April
- 7. 7General framework2. Ph.D. objectives (2)Main Architectural Classes SISD machinesSIMD machinesMISD machinesMIMD Machine :(Execute several instruction streams in parallel on different data)Shared Memory MachineDistributed Memory SystemCPU1CPU2CPU3CPUnRandom Access Memory R. MAHMOUDI – A3SI Laboratory– 2009 April
- 8. 8General framework2. Ph.D. objectives (3)NeedsCommon parallelization strategy of topological operators on multi-core multithread architecture (MIMD Machines – Shared Memory System)?Main ObjectivesUnifyingparallelizationmethod of topologicaloperators class (Algorithmiclevel)Implementation Methodology and optimization techniques on multi-core multithread architecture (Architecture level).R. MAHMOUDI – A3SI Laboratory– 2009 April
- 9. 9General frameworkParallel thinningoperatorFuture workDiscussionR. MAHMOUDI – A3SI Laboratory– 2009 April
- 10. 10Parallel thinning operator1.Theoretical backgroundFiltered thinning method that allows to selectively simplify the topology, based on a local contrast parameter λ.(b) filtered skeleton with λ = 10.(a) After Deriche gradient operatorR. MAHMOUDI – A3SI Laboratory– 2009 April
- 11. 11Parallel thinning operator1.Parallelization strategy (1)Definesearch areaStartparallelcharacterization Create new shared data structureEnd parallelcharacterization Mergemodifiedsearch areaRestart process until stabilityR. MAHMOUDI – A3SI Laboratory– 2009 April
- 12. 12Parallel thinning operator1.Parallelization strategy (2)SDM-Strategy(Divide and conquer principle)Up levelDATA PARALLELISMMIXEDPARALLELISMDown levelTHREAD PARALLELISMR. MAHMOUDI – A3SI Laboratory– 2009 April
- 13. 13Parallel thinning operator1.Parallelization strategy (3)R. MAHMOUDI – A3SI Laboratory– 2009 April
- 14. 14Parallel thinning operator2.Coordination of threads (1)Thread 1Thread 2First implementation using a lock-based shared FIFO queue.Lock()Unlock()Push()FailSuccessBlockedR. MAHMOUDI – A3SI Laboratory– 2009 April
- 15. 15Parallel thinning operator2.Coordination of threads (2)Thread 1Thread 2Lock() and access semaphoreUnlock() and leave semaphoreSemaphorePush()Second implementation using a private-shared concurrent FIFO queueR. MAHMOUDI – A3SI Laboratory– 2009 April
- 16. 16Parallel thinning operator3.Performance testing (1)R. MAHMOUDI – A3SI Laboratory– 2009 April
- 17. 17Parallel thinning operator3.Performance testing (2)First implementation using a lock-based shared FIFO queue.R. MAHMOUDI – A3SI Laboratory– 2009 April
- 18. 18Parallel thinning operator3.Performance testing (3)Second implementation using a private-shared concurrent FIFO queueR. MAHMOUDI – A3SI Laboratory– 2009 April
- 19. 19Parallel thinning operator4.ConclusionNon-specific nature of the proposed parallelization strategy.Threads coordination and communication during computing dependently parallel read/write for managing cache-resident data 12R. MAHMOUDI – A3SI Laboratory– 2009 April
- 20. 20General frameworkParallel thinningoperatorFuture workDiscussionR. MAHMOUDI – A3SI Laboratory– 2009 April
- 21. 21Future work1. ExtensionSDM- StrategyPerformance enhancement (speed up)Efficiency (work distribution)Cache missParallelThinning OperatorIMBRICATE TWOOperatorsCrest restoring R. MAHMOUDI – A3SI Laboratory– 2009 April
- 22. 22Future work2. Newparallel topological watershed% AchievementParallelwatershed OperatorSDM - StrategyPerformance enhancement (speed up)Efficiency (work distribution)Cache miss80%R. MAHMOUDI – A3SI Laboratory– 2009 April
- 23. 23General frameworkParallel thinningoperatorFuture workDiscussionR. MAHMOUDI – A3SI Laboratory– 2009 April
- 24. 24DiscussionIntroduce future programmingmodel (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)R. MAHMOUDI – A3SI Laboratory– 2009 April
- 25. 25R. MAHMOUDI –A3SI Laboratory– 2009 April