Skip to main content


Showing posts from April, 2017

Notes for Parallelism

Task: computation of instructions, distinct part of program or algorithm. Task-Parallelism: different tasks at the same time Data-Parallelism: same task ,different data items at the same time (eg. 2 chef slicing one tomato each) Dependencies: execution order of two tasks A and B. A must complete before B executes. Notation: A -> B Dependencies lead s to partial ordering A and B can execute parallel if  -no path in dependence graph from A -> B  -no path in dependence graph from B -> A Note that dependency is transitive, as A->C, C->B implies A->B ----------------------Task parallelism example----------------------- Computing min,max,avg for a large data-set. Task can be divided into T1- MIN, T2 - MAX, T3 - AVG Way to tell compiler to execute task in parallel is to use POSIX threads ----------------------Data parallelism example----------------------- Computing pair-wise sum of two arrays Use a SIMD extension of Intel processor to do sum in o