It would have been interesting to know how the performance with Cholesky varies depending on the platform size.

Also, we adapt HEFT to consider cost average weighted by the number of proc.

cd 17_cholesky_varying_proc/
for i in $(seq 2 15)
do
  ./generate_cholesky.py $i
done
mkdir -p instances/gml
mv *.gml instances/gml
mkdir -p instances/cholesky
mkdir -p instances/params

We generate many HEFT schedules (for each platforms):

k_s <- c(1, 2, 4, 8)
mk_s <- c(1, 2, 3, 5)
for (i in 2:15) {
  prefix <- "17_cholesky_varying_proc/instances"
  name_gml <- paste("gml/cholesky_", i, ".gml", sep = "")
  g <- read_instance_gml(paste(prefix, name_gml, sep = "/"))
  name_dot <- paste("cholesky/cholesky_", i, ".dot", sep = "")
  write_graph_str(g, paste(prefix, name_dot, sep = "/"), "dot")
  for (k in k_s)
    for (mk in mk_s) {
      m <- k * mk
      schedule <- HEFT(m, k, g)
      LB <- LB_europar(cbind(get.vertex.attribute(g, "CPU"),
                             get.vertex.attribute(g, "GPU")), m, k)
      params <- data.frame(rank = i, m = m, k = k, CP = CP(g),
                           LB_europar = LB, HEFT = schedule$mks)
      name_params <- paste("params/cholesky", i, m, k, sep = "_")
      write.table(params, paste(prefix, name_params, sep = "/"),
                  row.names = FALSE, sep = ",")
      name_HEFT <- paste(name_params, "HEFT", sep = ".")
      capture.output(schedule, file = paste(prefix, name_HEFT, sep = "/"))
    }
}

We are ready to launch the heuristics.

cd 17_cholesky_varying_proc/
# Generating results
PARAM=cholesky
RESULT=result_$PARAM.csv
rm -rf src/input/$PARAM
mkdir -p src/input/$PARAM
cp instances/cholesky/cholesky_*.dot src/input/$PARAM
> $RESULT
for k in 1 2 4 8
do
  for mk in 1 2 3 5
  do
    m=$((k * mk))
    ./src/test -m $m -k $k -i src/input/$PARAM
    sed "s/_\([0-9]*\).dot/_\1_$m\_$k/" -i output_$m-$k.dat
    grep cholesky output_$m-$k.dat >> $RESULT
  done
done
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $RESULT

# Mixing results with lower bounds
sed -i "s/\t/,/g" $RESULT
sed -i "s/ //g" $RESULT
for file in $(awk -F',' 'NR>1 { print "instances/params/" $1 }' $RESULT)
do
    header=$(head -n 1 $file)
    tail -n 1 $file
done > $RESULT.tmp1
paste $RESULT <(echo $header; cat $RESULT.tmp1) > $RESULT.tmp2
rm $RESULT.tmp1
mv $RESULT.tmp2 $RESULT

We can finally compare the performance.

data <- read.csv("17_cholesky_varying_proc/result_cholesky.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("Rati", "QALS", "ERLS", "Quik", "EFiT",
                                        "MxQE", "HEFT"))) %>%
  ggplot(aes(x = rank, y = mks / LB, col = algo, shape = algo)) +
  geom_point() +
  geom_line() +
  facet_grid(m / k ~ k)
## Warning: The shape palette can deal with a maximum of 6 discrete values
## because more than 6 becomes difficult to discriminate; you have 7.
## Consider specifying shapes manually if you must have them.
## Warning: Removed 224 rows containing missing values (geom_point).

It is also interesting to make the ratio to HEFT instead than to the lower bound.

data %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati) %>%
  mutate(algo = factor(algo, levels = c("Rati", "QALS", "ERLS", "Quik", "EFiT",
                                        "MxQE"))) %>%
  ggplot(aes(x = rank, y = mks / HEFT, col = algo, shape = algo)) +
  geom_point() +
  geom_line() +
  facet_grid(m / k ~ k)

HEFT is not always the best. It is surprising to see that an online strategy can sometimes beat a static one.

## R version 3.4.3 (2017-11-30)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.3 LTS
## 
## Matrix products: default
## BLAS: /usr/lib/openblas-base/libblas.so.3
## LAPACK: /usr/lib/libopenblasp-r0.2.18.so
## 
## locale:
##  [1] LC_CTYPE=fr_FR.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=fr_FR.UTF-8        LC_COLLATE=fr_FR.UTF-8    
##  [5] LC_MONETARY=fr_FR.UTF-8    LC_MESSAGES=fr_FR.UTF-8   
##  [7] LC_PAPER=fr_FR.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=fr_FR.UTF-8 LC_IDENTIFICATION=C       
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] bindrcpp_0.2  igraph_1.0.1  ggplot2_2.2.1 dplyr_0.7.4   tidyr_0.2.0  
## [6] purrr_0.2.0   stringr_1.2.0
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.10     knitr_1.15.1     bindr_0.1        magrittr_1.5    
##  [5] munsell_0.4      colorspace_1.2-2 R6_2.1.0         rlang_0.1.6     
##  [9] plyr_1.8.1       tools_3.4.3      grid_3.4.3       gtable_0.1.2    
## [13] pacman_0.4.6     htmltools_0.3.6  lazyeval_0.2.0   yaml_2.1.13     
## [17] rprojroot_1.2    digest_0.6.3     assertthat_0.1   tibble_1.3.1    
## [21] reshape2_1.2.2   glue_1.2.0       evaluate_0.10    rmarkdown_1.8   
## [25] labeling_0.1     stringi_0.5-5    compiler_3.4.3   scales_0.4.1    
## [29] backports_1.0.5  pkgconfig_2.0.1