More Related Content
Similar to 20140413 parallel programming_kalishenko_lecture09 (20)
More from Computer Science Club (20)
20140413 parallel programming_kalishenko_lecture09
- 1. 丿舒弍仍仂仆 || 仗仂亞舒仄仄亳仂于舒仆亳 舒仍亳亠仆从仂 .. 2014
- 2. 2 亅舒仗 舒亰舒弍仂从亳 仗亠亟亠仍亳 仄亠仂 || (Finding concurrency) 弍仂 舒仍亞仂亳仄舒/舒弍仍仂仆舒 (Algorithm structure) 弍仂 仗仂亟仂亟亳 || 从 (Supporting structures) 弍仂 仄亠舒仆亳亰仄舒 亠舒仍亳亰舒亳亳 (Implementation mechanisms)
- 3. 3 舒亰仂于亠 亳亟亠亳 design space 弍仂 亟亠从仂仄仗仂亰亳亳亳:弍仂 亟亠从仂仄仗仂亰亳亳亳: 仂 亟舒仆仆仄 仂 仗舒于仍亠仆亳 (亰舒亟舒舒仄) 仆舒仍亳亰 亰舒于亳亳仄仂亠亶:仆舒仍亳亰 亰舒于亳亳仄仂亠亶: 仗仗亳仂于从舒 亰舒亟舒 仂磲仂从 于仗仂仍仆亠仆亳 亰舒亟舒 仗亠亟亠仍亠仆亳亠 舒亰亟亠仍磳仄 亟舒仆仆
- 4. 4 亢仆仂 仗仂仄仆亳 亳仆亳仗 仗仂亠从亳仂于舒仆亳:亳仆亳仗 仗仂亠从亳仂于舒仆亳: 亅亠从亳于仆仂 仂仂舒 亠亠仆仂亳仄仂 舒舒弍亳亠仄仂
- 5. 5 亞舒仆亳亰舒亳 于亳仍亠仆亳亶 Pipeline 丕仗舒于仍磳仄亠 仗仂仂从仂仄 亟舒仆仆 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亰舒亟舒舒仄 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亟舒仆仆仄 亠从亳于仆. 亟舒仆仆亠 仂仂礌仆亶 ? 弌仍舒亶仆亶? || 仆舒 亰舒亟舒舒亠仂仄亠亳亠从舒 亟亠从仂仄仗仂亰亳亳 舒亰亟亠仍磺 亳 于仍舒于亶 仂仂亟亳仆舒亳 仆舒 仂弍亳 亳亟 仂亞舒仆亳亰舒亳亳
- 6. 6 亠仂仄亠亳亠从舒 亟亠从仂仄仗仂亰亳亳 亳仄亠亳仄亠 仂亟亠仍亳仂于舒仆亳亠 从仍亳仄舒舒 个舒从舒仍 仂弍亠仆仆仂亳仂弍亠仆仆仂亳 舒亰亟亠仍亠仆亳亠 从 亟舒仆仆: 仄舒亳于 弍亠仄 仗仂仍亠亟仂于舒亠仍仆亠 舒亳 仗亳从亳 仗亠于亟仂仍亠仄亠仆 亳仍亳 仗仂亟仗亳从亳 亞舒 - 仗仂亟亞舒
- 7. 7 仂亟仂亟亳 束Parallel loops損 OpenMPOpenMP #pragma omp parallel for schedule(static, 500) for(int i=0; i<n; i++) invariant_amount_of_work(i); Intel TBBIntel TBB parallel_for(blocked_range<int>(0, nElements, 100), ArraySummer( p_A, p_B, p_SUM_TBB ) ); 亠 亠: blocked_range2d 亳 blocked_range3d
- 8. 8 仗仂亟仂亟亳 SPMD Single Program Multiple Data: 仂亟亳仆 从仂亟 仆舒亟 舒亰仆仄亳 亟舒仆仆仄亳, 仂于亠亠仆仆仂 仂亠于亳亟仆舒 于亠 仂亟仆舒 仗仂亞舒仄仄舒, 仗舒于仍ﾑ舒 于亳仍亠仆亳礆亳 (仗仂亠舒仄亳, 仗仂仂从舒仄亳...) 丿舒亞亳: 仆亳亳舒仍亳亰亳仂于舒 舒亰亟舒 亳亟亠仆亳亳从舒仂 仆亳礆/仗仂亠舒仄 舒亰亟亠仍亳 亟舒仆仆亠 舒于亠亳
- 9. 9 Parallel Boost Graph Library MPI: 舒仗亠亟亠仍仆仆亠 亞舒 亠仆亠舒仂 亞舒仂于 仍亞仂亳仄: 仂亳从 舒舒亶亳亶 仗 亳仆亳仄舒仍仆仂亠 仂仂于仆仂亠 亟亠亠于仂 舒从舒从舒 亞舒舒 ...
- 10. 10 Recursive data 舒亟舒舒舒亟舒舒 舒从 亟亠仍舒 || 仂仗亠舒亳亳 仆舒亟 亠从亳于仆仄亳 从舒仄亳 (仗亳从亳, 亟亠亠于, 亞舒)? 亳仄亠亳仄亠 舒亶亳 于 仍亠 从仂仆亳 亟亠亠于亠于 亠亠仆亳亠亠亠仆亳亠 仂仍亠亟仂于舒亠仍仆仂亠 O(N) 仂仗亠舒亳亶 / 于亠仄亠仆亳 || O (N log N) 仂仗亠舒亳亶 / O (log N) 于亠仄亠仆亳
- 11. 11 亞舒仆亳亰舒亳 于亳仍亠仆亳亶 Pipeline 丕仗舒于仍磳仄亠 仗仂仂从仂仄 亟舒仆仆 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亰舒亟舒舒仄 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亟舒仆仆仄 亠从亳于仆. 亟舒仆仆亠 仂仂礌仆亶 ? 弌仍舒亶仆亶? || 仆舒 亰舒亟舒舒亠仂仄亠亳亠从舒 亟亠从仂仄仗仂亰亳亳 舒亰亟亠仍磺 亳 于仍舒于亶 仂仂亟亳仆舒亳 仆舒 仂弍亳 亳亟 仂亞舒仆亳亰舒亳亳
- 12. 12 || 仆舒 亰舒亟舒舒 亳仄亠亳仄亠 Ray tracing 舒亟舒亳 仄仂仍亠从仍仆仂亶 亟亳仆舒仄亳从亳 仂弍亠仆仆仂亳仂弍亠仆仆仂亳 亳仆舒仄亳亠从仂亠 仂亰亟舒仆亳亠 亰舒亟舒 (仄亠仂亟 于亠于亠亶 亳 亞舒仆亳) 亢亳亟舒仆亳亠 亰舒亟舒 亳仍亳 亠亞仂 仂于亳亠 (仂亳仂于从舒 亳仍亳 仗仂亳从) 舒亰仄亠 亰舒亟舒
- 13. 13 亳仆亳仗 舒亰亟亠仍亠仆亳 仆舒 亰舒亟舒亳 舒亟舒 >= 亳仍 仗仂仂从仂于 (磲亠) 弍仄 于亳仍亠仆亳亶 仆亠 仗亠于舒亠 亳亰亟亠亢从亳 仂弍舒 亰舒于亳亳仄仂礆亳 (shared data 仗仂仍亠亟仆亳亶 弍亠亢): 亳于亠于亠 亟弍仍亳仂于舒仆亳亠 亟舒仆仆 (亳, 于仂亰仄仂亢仆仂, 于亳仍亠仆亳亶) 亳 亠亟从亳 丕弍仂从舒 亳仆亟亳仂于舒仆仆 仗亠亠仄亠仆仆 于 亳从仍舒 舒亰亟亠仍亳 亰舒于亳亳仄仂亳 仗仂 亠亰仍舒 亠亠亰 亠亟从亳 仗仂 亟舒仆仆仄
- 14. 14 舒亰仆舒亠仆亳亠 亰舒亟舒 仆舒 仗仂仂从亳 个仂仄亳仂于舒仆亳亠 仂亠亠亟亳 亰舒亟舒: notify 仗仂仍舒亠仄 从仍舒亳亠从亳亠: Producer/consumer 仗仂仂从 从仍舒亟 亰舒亟舒亳 Master/Worker 仗仂仂从 亞仂仂于亳 亰舒亟舒亳 亳仂亟 仗仍 仗仂仂从仂于 弍仂 仗仂仂弍舒 仗仍舒仆亳仂于舒仆亳: 舒亳亠从仂亠/亟亳仆舒仄亳亠从仂亠 弍舒仍舒仆亳仂于从舒 仆舒亞亰从亳: + 从 亟亳仆舒仄亳从亠 仄亳仆 亟亳仆舒仄亳亠从仂亞仂 仆舒亰仆舒亠仆亳?
- 15. 15 亞舒仆亳亰舒亳 于亳仍亠仆亳亶 Pipeline 丕仗舒于仍磳仄亠 仗仂仂从仂仄 亟舒仆仆 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亰舒亟舒舒仄 亳仆亠亶仆仂? 亠从亳于仆仂? 舒亰亟亠仍亠仆亳亠 仗仂 亟舒仆仆仄 亠从亳于仆. 亟舒仆仆亠 仂仂礌仆亶 ? 弌仍舒亶仆亶? || 仆舒 亰舒亟舒舒亠仂仄亠亳亠从舒 亟亠从仂仄仗仂亰亳亳 舒亰亟亠仍磺 亳 于仍舒于亶 仂仂亟亳仆舒亳 仆舒 仂弍亳 亳亟 仂亞舒仆亳亰舒亳亳
- 16. 16 Pipeline 亳仄亠亳仄亠 弍舒弍仂从舒 亳亞仆舒仍仂于 亳亟亠仂 Shell! 束cat油sampleFile油|油grep油"word"油|油wc損
- 17. 17 亳仄亠
- 18. 18 Local Serializer class Serializer { tbb::concurrent_queue<WorkItem*> queue; tbb::atomic<int> count; // Count of queued items and in-flight item void moveOneItemToReadyPile() { // Transfer item from queue to ReadyPile WorkItem* item; queue.try_pop(item); ReadyPile.add(item); } public: void add( WorkItem* item ) { queue.push(item); if( ++count==1 ) moveOneItemToReadyPile(); } void noteCompletion() { // Called when WorkItem completes. if( count!=0 ) moveOneItemToReadyPile(); } };
- 19. 19 Double check (lock) template<typename T, typename Mutex=tbb::mutex> class lazy { tbb::atomic<T*> value; Mutex mut; public: lazy() : value() {} // Initializes value to NULL ~lazy() {delete value;} T& get() { if( !value ) { // Read of value has acquire semantics. Mutex::scoped_lock lock(mut); if( !value ) value = new T(); // Write of value has release semantics } return *value; } };
- 20. 20 Double check (lock-free) template<typename T> class lazy { tbb::atomic<T*> value; public: lazy() : value() {} // Initializes value to NULL ~lazy() {delete value;} T& get() { if( !value ) { T* tmp = new T(); if( value.compare_and_swap(tmp,NULL)!=NULL ) // Another thread installed the value, so throw away mine. delete tmp; } return *value; } };
- 21. 21 仂亟亠仍亳 仗仂亞舒仄仄 SPMD 舒亢亟亶 仗仂仂从 亳仄亠亠 id, 仗仂 从仂仂仂仄 仗仂亳 亟舒仆仆亠, 于弍亳舒亠 亳亠舒亳亳... Loop || 弍亠亟亳仆亠仆亳亠 于仍仂亢亠仆仆 亳从仍仂于 丕弍仂从舒 亰舒于亳亳仄仂亠亶 仗仂 亳亠舒亳礆 仂亰仄仂亢仆舒 仗仂舒 舒亳亠从舒 弍舒仍舒仆亳仂于从舒 Boss/Worker 亢仆舒 亟仍 亟亳仆舒仄亳亠从仂亶 弍舒仍舒仆亳仂于从亳
- 22. 22 -D_GLIBCXX_PARALLEL 亠从仂仍从仂 亟亠从仂于 亠舒仍亳亰舒亳亶 舒仍亞仂亳仄仂于 亳亰 <algorithm>: find_if, max_element... 仗仂仍亰亠 OpenMP