CilkIntroductionWhat is Cilk?Multithreaded ComputationSlide 5Slide 6SpawnShared MemorySlide 9LockingInletsSlide 12SYNCHED KeywordAbortingSlide 15Cilk Runtime System(CRS)Slide 17CompilingSlide 19RunningReading ListCilkCISC 879 Parallel ComputationErhan Atilla Avinal2/21IntroductionWhat is Cilk ?Multithreaded ComputationLanguage SpecificationsCilk Runtime SystemCompiling & Running3/21What is Cilk?A language for multithreaded parallel programming based on C.Effective in highly asynchronous parallelism.No message passing4/21Multithreaded ComputationCilk guarantees that programs are scheduled efficiently by its runtime system.Programmer does not deal with message passing.5/21int fib (int n){if (n<2) return (n);else{int x, y;x = fib (n-1);y = fib (n-2);return (x+y);}}int main (int argc, char *argv[]){int n, result;n = atoi(argv[1]);result = fib (n);printf ("Result: %d\n", result);return 0;}#include <cilk.h>cilk int fib (int n){if (n<2) return n;else{int x, y;x = spawn fib (n-1);y = spawn fib (n-2);sync;return (x+y);}}cilk int main (int argc, char *argv[]){int n, result;n = atoi(argv[1]);result = spawn fib(n);sync;printf ("Result: %d\n", result);return 0;}6/21Multithreaded Computation7/21SpawnSpawns Cilk procedures to start parallel computationsint i;float j;cilk int foo();i= spawn foo(); YESj= spawn foo(); NOx = spawn foo() + spawn bar(); NO8/21Shared MemoryCilk supports shared memorySharing occurs by passing pointers to spawned procedures (call by reference).9/21Shared Memorycilk int foo (void){int x = 0, y;spawn bar(&x);y = x + 1;sync;return (y);}cilk void bar (int *px){printf("%d", *px + 1);return;}cilk int foo (void){int x = 0;spawn bar(&x);x = x + 1;sync;return (x);}cilk void bar (int *px){*px = *px + 1;return;}Data RaceData Race10/21LockingCilk_lockvar data type #include <cilk-lib.h>::Cilk_lockvar mylock;:{Cilk_lock_init(mylock);:Cilk_lock(mylock); /* begin critical section */:Cilk_unlock(mylock); /* end critical section */}11/21InletsC Functions internal to a Cilk procedureCannot contain spawn or syncCilk guarantees that all operations in inlets are atomic12/21Inletscilk int fib (int n){int x = 0;inlet void summer (int result){x += result;return;}if (n<2) return n;else {summer(spawn fib (n-1));summer(spawn fib (n-2));sync;return (x);}}13/21SYNCHED KeywordTests if procedure is synchronized.state1 = alloca(state_size);/* fill in *state1 with data */spawn foo(state1);if (SYNCHED)state2 = state1;elsestate2 = alloca(state_size);/* fill in *state2 with data */spawn bar(state2);sync;14/21Aborting“abort” : causes all of the spawned children to abort.Cilk does not guarantee that all children will be aborted instantly.15/21Abortingcilk void baz(int n);cilk void foo(int n){inlet void bar(){abort;}bar(spawn baz(17));spawn baz(28);sync;}16/21Cilk Runtime System(CRS)CRS implements a efficient scheduling policy : work-stealing When a processor runs out of work it steals work from another processor randomly.Deque (Double-Ended Queue)17/21Cilk Runtime System(CRS)18/21Compiling“cilk” commandsupports gcc optionscilk fib.cilk -o fib cilk -cilk-profile -cilk-critical-path -O2 fib.cilk -cilk-profile : how much memory is used, how much time each processor spends, etc.19/21Compiling“cilk” command-cilk-critical-path : measures ideal execution time of your program on an infinite number of processors. It may slow down the execution of the program because of many calls to timing routines.20/21Runningfib --nproc 4 --stats 1 30--stats : shows performance data if -cilk-profile is used incompilation.--nproc : number of processors used21/21Reading ListCilk Main Pagehttp://supertech.lcs.mit.edu/cilkCilk 5.3.2 Reference