Cilk benchmarks

Overview

This directory contains some Cilk programs written for pedagogical purposes. To compile, you should have installed Tapir/LLVM as well as the Cilk runtime system.

$ make TAPIR_PATH=path_to_tapir CILKRT_PATH=path_to_cilkrt

Description

The Makefile generates a bunch of executables ending in .bin, including the following ones.

• msort-seq.bin and qsort-seq.bin: sequential merge sort and quicksort.
• msort-par.bin and qsort-par.bin: parallel merge sort and quicksort.
• msort-par-pthread.bin and msort-par-naive.bin: naive versions of parallel merge sort discussed during the first lecture.
• shuffle-seq.bin and shuffle-par.bin: sequential and parallel implementations of Fisher-Yates-Durstenfeld-Knuth (FYDK) shuffling.
• random.bin: random number generator appropriate for benchmarking FYDK shuffling.

Benchmarking

The following commands benchmark sequential and parallel FYDK shuffling on arrays of size 10^8.

$ echo 100000000 > input.csv
$ ./random.bin -i input.csv -o /tmp/perm
$ ./shuffle-seq.bin -i /tmp/perm
$ ./shuffle-par.bin -i /tmp/perm

You may also want to have a look at the exp-* files as well as the benchmark.sh script. For instance, exp-msort-512MB.bench can be used to benchmark parallel sorts on medium-sized arrays.

$ ./benchmark.sh exp-msort-512MB.bench

See also

The Problem Based Benchmark Suite library.