Let’s study how the heuristics perform with a classical application trace (Cholesky factorization). We start by generating the instances.

for i in $(seq 2 15)
do
  ./generate_cholesky.py $i
done

Then, we compute the lower bounds, HEFT and convert the format for the simulator.

m <- 20
k <- 4
for (i in 2:15) {
  prefix <- paste("16_cholesky_instances/cholesky_", i, sep = "")
  g <- read_instance_gml(paste(prefix, "gml", sep = "."))
  name <- paste(prefix, "dot", sep = ".")
  write_graph_str(g, name, "dot")
  schedule <- HEFT(m, k, g)
  name_HEFT <- paste(name, "HEFT", sep = ".")
  capture.output(schedule, file = name_HEFT)
  LB <- LB_europar(cbind(get.vertex.attribute(g, "CPU"),
                         get.vertex.attribute(g, "GPU")), m, k)
  params <- data.frame(rank = i, m = 20, k = 4, CP = CP(g),
                       LB_europar = LB, HEFT = schedule$mks)
  name_params <- paste(name, "params", sep = ".")
  write.table(params, name_params, row.names = FALSE, sep = ",")
}
## Loading required package: igraph
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:dplyr':
## 
##     %>%, as_data_frame, groups, union
## The following objects are masked from 'package:purrr':
## 
##     %>%, compose, simplify
## The following object is masked from 'package:stringr':
## 
##     %>%
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union

We are ready to launch the heuristics.

mkdir -p instances/cholesky
mv cholesky*.dot* instances/cholesky
PARAM=cholesky
RESULT=result_$PARAM.csv
k=4
m=20
rm -rf src/input/$PARAM
mkdir -p src/input/$PARAM
cp instances/cholesky/cholesky_*.dot src/input/$PARAM
head -n 1 output_$m-$k.dat > $RESULT
./src/test -m $m -k $k -i src/input/$PARAM
grep cholesky output_$m-$k.dat >> $RESULT
sed -i "s/\t/,/g" $RESULT
sed -i "s/ //g" $RESULT
for file in $(awk -F',' 'NR>1 { print "instances/'"$PARAM"'/" $1 ".params" }' $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("16_cholesky_instances/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()
## 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 14 rows containing missing values (geom_point).

The plot shows the effect of increasing the size on the instance difficulty (at least on the quality of the lower bound). We see that MxQE achieves very good performance with strong guarantee.

## 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