-
-
Save davehull/952852 to your computer and use it in GitHub Desktop.
Example script to show how to do an intelligent merge-sort in parallel
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/bash | |
# determines number of proccessors, splits a large file into sizes that | |
# can be consumed by n-1 sort processes (where n is the number of processors) | |
# | |
# After the file has been split up properly, it will run a sort on each split | |
# file in parallel. Once all processes have completed, a merge sort is executed. | |
# | |
# mthomas@n2o:~/words [100%] $ du -h big | |
# 1.7G big | |
# | |
# Using normal sort: | |
# mthomas@n2o:~/words [100%] $ time sort -T . -o blop big | |
# real 7m4.264s | |
# | |
# Using this shell script: | |
# mthomas@n2o:~/words [100%] $ time ./msort.sh big | |
# Splitting big into 3 pieces. | |
# big.001 582483968 bytes | |
# big.002 582483968 bytes | |
# big.003 582478144 bytes | |
# Done! | |
# Attempting cache on big.001 | |
# Running sort on big.001 on cpu 0x00000001 | |
# Attempting cache on big.002 | |
# Running sort on big.002 on cpu 0x00000002 | |
# Attempting cache on big.003 | |
# Running sort on big.003 on cpu 0x00000004 | |
# Finalizing sort into big.sorted | |
# Removing temporary files | |
# | |
# real 4m54.142s | |
# | |
# That's a 2 minute speedup, of course the more procs/mem you have will affect | |
# the time. | |
if [ "$#" -ne 1 ] | |
then | |
echo "You need to specify an input file" | |
exit 1 | |
fi | |
num_procs=`grep "cores" /proc/cpuinfo|uniq|cut -d " " -f 3-` | |
big_file=$1 | |
if [ "$num_procs" -gt 1 ] | |
then | |
let proc_mask_count="$num_procs - 2" | |
let proc_count="$num_procs - 1" | |
let mem_percnt=$((100/$num_procs)) | |
affinity_masks=() | |
# create an array of processor masks for affinity tasking | |
for cpu_n in `seq 0 $proc_mask_count` | |
do | |
let mask="1 << $cpu_n" | |
affinity_masks[$cpu_n]=`printf "%#.8x" $mask` | |
done | |
# determine size of the split files based on number of procs | |
file_size=`du -b $1 | awk '{print $1}'` | |
split_size=`echo "scale=10; $file_size / $proc_count" | bc | python -c "import math; print math.ceil(float(raw_input()))"` | |
echo $file_size | |
echo $split_size | |
lxsplit -s $1 $split_size\b | |
for i in `seq 1 $proc_count` | |
do | |
infile="$1.00$i" | |
let offset="$i - 1" | |
echo "Running sort on $infile on cpu ${affinity_masks[$offset]}" | |
taskset ${affinity_masks[$offset]} sort -S mem_percnt% -T . -o $infile.s $infile & | |
done | |
wait | |
echo "Finalizing sort into $1.sorted" | |
sort -o $1.sorted -m $1.0*.s -S mem_percnt% | |
echo "Removing temporary files" | |
rm $1.0* | |
else | |
echo "No need for parallel sorting op" | |
exit 1 | |
fi |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment