The objective is to make the chain-fork instances denser (and slightly more difficult). Also, we will make two more specific figures (one for the CV and one for the size) for a specific pair of values for k and m.

Denser chain-fork instances

The generation method has been adapated to fill the void.

NB <- 10

n_s <- c(10, 30, 100)
k_s <- c(1, 2, 4, 8)
mk_s <- c(1, 2, 3, 5)
CV_s <- c(0.1, 0.2, 0.3, 0.5, 1)

data <- NULL
for (n in n_s)
  for (k in k_s)
    for (m in k * mk_s)
      for (CV in CV_s)
        for (func in c("chain_indep", "chain_fork"))
          for (i in 1:NB) {
            g <- get(func)(m, k, n, CV)
            schedule <- HEFT(m, k, g)
            LB <- LB_europar(cbind(get.vertex.attribute(g, "CPU"),
                                   get.vertex.attribute(g, "GPU")), m, k)
            params <- data.frame(func = func, n = n, m = m, k = k, CV = CV,
                                 num = i, CP = CP(g), LB_europar = LB,
                                 HEFT = schedule$mks)
            data <- rbind(data, params)
          }

Let’s plot the general plot:

data %>%
  mutate(ratio = HEFT / pmax(CP, LB_europar)) %>%
  ggplot(aes(x = ratio)) +
  geom_histogram() +
  facet_grid(m / k ~ k)
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

Some ratios below 1 were due to a bug in the back-filling implementation of HEFT. It has been fixed.

The lower bound works best when there are as much CPUs as GPUs. The worst is when there are much more CPUs than GPUs.

Let’s analyze the distribution by method:

library(knitr)
data %>%
  mutate(ratio = HEFT / pmax(CP, LB_europar)) %>%
  group_by(func) %>%
  do(data_frame_(summary(.$ratio))) %>%
  kable()
func Min. 1st Qu. Median Mean 3rd Qu. Max.
chain_indep 1 1.000000 1.000000 1.061797 1.074030 1.912787
chain_fork 1 1.014301 1.168269 1.200384 1.315632 2.182986 
data %>%
  mutate(ratio = HEFT / pmax(CP, LB_europar)) %>%
  group_by(func) %>%
  do(data_frame_(quantile(.$ratio, probs = seq(0.2, 0.9, 0.1)))) %>%
  kable()
func 20% 30% 40% 50% 60% 70% 80% 90%
chain_indep 1 1.000000 1.00000 1.000000 1.012290 1.055409 1.095315 1.185268
chain_fork 1 1.053859 1.10868 1.168269 1.224646 1.285161 1.349184 1.457351

The lower bound works well for chain_indep in most cases (below 10% in more than three quarters of the cases) and reasonably for chain_fork (below 20% in more than half the cases).

CV effect

set.seed(1)

NB <- 30
n <- 100
k <- 4
mk <- 5
m <- k * mk
CV_s <- c(0.1, 0.2, 0.3, 0.5, 1)

dir_name <- "15_denser_random_graphs/instances/CV"
dir.create(dir_name, showWarnings = FALSE, recursive = TRUE)
for (CV in CV_s)
  for (func in c("chain_indep", "chain_fork"))
    for (i in 1:NB) {
      print(c(n, m, k, CV, func, i))
      name <- paste(func, n, m, k, CV, i, sep = "_") %>%
        paste("dot", sep = ".")
      name <- paste(dir_name, name, sep = "/")
      g <- get(func)(m, k, n, CV)
      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(func = func, n = n, m = m, k = k, CV = CV,
                           num = i, CP = CP(g), LB_europar = LB,
                           HEFT = schedule$mks)
      name_params <- paste(name, "params", sep = ".")
      write.table(params, name_params, row.names = FALSE, sep = ",")
    }
PARAM=CV
RESULT=result_$PARAM.csv
> $RESULT
k=4
m=$((k * 5))
rm -rf src/input/$PARAM
mkdir -p src/input/$PARAM
cp instances/$PARAM/*.dot src/input/$PARAM
./src/test -m $m -k $k -i src/input/$PARAM
grep "[^0-9]\+_[0-9]*_$m\_$k\_" output_$m-$k.dat >> $RESULT
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $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
data <- read.csv("15_denser_random_graphs/result_CV.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("HEFT", "MxQE", "EFiT", "QALS", "ERLS",
                                        "Rati", "Quik"))) %>%
  ggplot(aes(x = factor(CV), y = mks / LB, col = algo)) +
  geom_boxplot() +
  facet_wrap(~ func, ncol = 1)

Differences in performance are higher when the CV is low. Also the differences are more stable.

Size effect

set.seed(2)

NB <- 30
n_s <- c(30, 50, 100, 200, 300)
k <- 4
mk <- 5
m <- k * mk
CV <- 0.3

dir_name <- "15_denser_random_graphs/instances/n"
dir.create(dir_name, showWarnings = FALSE, recursive = TRUE)
for (n in n_s)
  for (func in c("chain_indep", "chain_fork"))
    for (i in 1:NB) {
      print(c(n, m, k, CV, func, i))
      name <- paste(func, n, m, k, CV, i, sep = "_") %>%
        paste("dot", sep = ".")
      name <- paste(dir_name, name, sep = "/")
      g <- get(func)(m, k, n, CV)
      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(func = func, n = n, m = m, k = k, CV = CV,
                           num = i, CP = CP(g), LB_europar = LB,
                           HEFT = schedule$mks)
      name_params <- paste(name, "params", sep = ".")
      write.table(params, name_params, row.names = FALSE, sep = ",")
    }
PARAM=n
RESULT=result_$PARAM.csv
> $RESULT
k=4
m=$((k * 5))
rm -rf src/input/$PARAM
mkdir -p src/input/$PARAM
cp instances/$PARAM/*.dot src/input/$PARAM
./src/test -m $m -k $k -i src/input/$PARAM
grep "[^0-9]\+_[0-9]*_$m\_$k\_" output_$m-$k.dat >> $RESULT
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $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
data <- read.csv("15_denser_random_graphs/result_n.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("HEFT", "MxQE", "EFiT", "QALS", "ERLS",
                                        "Rati", "Quik"))) %>%
  ggplot(aes(x = factor(n), y = mks / LB, col = algo)) +
  geom_boxplot() +
  facet_wrap(~ func, ncol = 1)

The tendencies are exagerated and more stable with a large number of tasks.

Effect of number of GPU

set.seed(3)

NB <- 30
n <- 100
k_s <- c(1, 2, 4, 6, 8)
mk <- 5
CV <- 0.3

dir_name <- "15_denser_random_graphs/instances/k"
dir.create(dir_name, showWarnings = FALSE, recursive = TRUE)
for (k in k_s)
  for (func in c("chain_indep", "chain_fork"))
    for (i in 1:NB) {
      m <- k * mk
      print(c(n, m, k, CV, func, i))
      name <- paste(func, n, m, k, CV, i, sep = "_") %>%
        paste("dot", sep = ".")
      name <- paste(dir_name, name, sep = "/")
      g <- get(func)(m, k, n, CV)
      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(func = func, n = n, m = m, k = k, CV = CV,
                           num = i, CP = CP(g), LB_europar = LB,
                           HEFT = schedule$mks)
      name_params <- paste(name, "params", sep = ".")
      write.table(params, name_params, row.names = FALSE, sep = ",")
    }
PARAM=k
RESULT=result_$PARAM.csv
> $RESULT
for k in 1 2 4 6 8
do
  m=$((k * 5))
  rm -rf src/input/$PARAM
  mkdir -p src/input/$PARAM
  cp instances/$PARAM/*_$m\_$k\_*.dot src/input/$PARAM
  ./src/test -m $m -k $k -i src/input/$PARAM
  grep "[^0-9]\+_[0-9]*_$m\_$k\_" output_$m-$k.dat >> $RESULT
done
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $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
data <- read.csv("15_denser_random_graphs/result_k.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("HEFT", "MxQE", "EFiT", "QALS", "ERLS",
                                        "Rati", "Quik"))) %>%
  ggplot(aes(x = factor(k), y = mks / LB, col = algo)) +
  geom_boxplot() +
  facet_wrap(~ func, ncol = 1)

Large numbers of GPU yield less stable results.

Effect of number of CPU/GPU ratio

set.seed(4)

NB <- 30
n <- 100
k <- 4
mk_s <- c(1, 2, 3, 5, 10)
CV <- 0.3

dir_name <- "15_denser_random_graphs/instances/mk"
dir.create(dir_name, showWarnings = FALSE, recursive = TRUE)
for (mk in mk_s)
  for (func in c("chain_indep", "chain_fork"))
    for (i in 1:NB) {
      m <- k * mk
      print(c(n, m, k, CV, func, i))
      name <- paste(func, n, m, k, CV, i, sep = "_") %>%
        paste("dot", sep = ".")
      name <- paste(dir_name, name, sep = "/")
      g <- get(func)(m, k, n, CV)
      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(func = func, n = n, m = m, k = k, CV = CV,
                           num = i, CP = CP(g), LB_europar = LB,
                           HEFT = schedule$mks)
      name_params <- paste(name, "params", sep = ".")
      write.table(params, name_params, row.names = FALSE, sep = ",")
    }
PARAM=mk
RESULT=result_$PARAM.csv
> $RESULT
k=4
for mk in 1 2 3 5 10
do
  m=$((k * mk))
  rm -rf src/input/$PARAM
  mkdir -p src/input/$PARAM
  cp instances/$PARAM/*_$m\_$k\_*.dot src/input/$PARAM
  ./src/test -m $m -k $k -i src/input/$PARAM
  grep "[^0-9]\+_[0-9]*_$m\_$k\_" output_$m-$k.dat >> $RESULT
done
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $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
data <- read.csv("15_denser_random_graphs/result_mk.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("HEFT", "MxQE", "EFiT", "QALS", "ERLS",
                                        "Rati", "Quik"))) %>%
  ggplot(aes(x = factor(m / k), y = mks / LB, col = algo)) +
  geom_boxplot() +
  facet_wrap(~ func, ncol = 1)

Significant effect: large differences between the number of CPUs and GPUs lead to large differences in the performance of the algorithms.

Effect of cost mean

set.seed(5)

NB <- 30
n <- 100
k <- 4
mk <- 5
CV <- 0.3
mean_cost_s <- 1:5

dir_name <- "15_denser_random_graphs/instances/mean_cost"
dir.create(dir_name, showWarnings = FALSE, recursive = TRUE)
for (mean_cost in mean_cost_s)
  for (func in c("chain_indep", "chain_fork"))
    for (i in 1:NB) {
      m <- k * mk
      print(c(n, m, k, mean_cost, CV, func, i))
      name <- paste(func, n, m, k, mean_cost, CV, i, sep = "_") %>%
        paste("dot", sep = ".")
      name <- paste(dir_name, name, sep = "/")
      g <- get(func)(m, k, n, CV, tau = mean_cost)
      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(func = func, n = n, m = m, k = k, CV = CV,
                           num = i, mean_cost = mean_cost, CP = CP(g),
                           LB_europar = LB, HEFT = schedule$mks)
      name_params <- paste(name, "params", sep = ".")
      write.table(params, name_params, row.names = FALSE, sep = ",")
    }
PARAM=mean_cost
RESULT=result_$PARAM.csv
> $RESULT
k=4
m=$((k * 5))
rm -rf src/input/$PARAM
mkdir -p src/input/$PARAM
cp instances/$PARAM/*_$m\_$k\_*.dot src/input/$PARAM
./src/test -m $m -k $k -i src/input/$PARAM
grep "[^0-9]\+_[0-9]*_$m\_$k\_" output_$m-$k.dat >> $RESULT
head -n 1 output_$m-$k.dat > $RESULT.tmp
cat $RESULT >> $RESULT.tmp
mv $RESULT.tmp $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
data <- read.csv("15_denser_random_graphs/result_mean_cost.csv")
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, MxQE, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("HEFT", "MxQE", "EFiT", "QALS", "ERLS",
                                        "Rati", "Quik"))) %>%
  ggplot(aes(x = factor(mean_cost), y = mks / LB, col = algo)) +
  geom_boxplot() +
  facet_wrap(~ func, ncol = 1)

Some effect. In particular, Quic and Rati are impacted but the tendencies are unclear. However, the performance of QALS and ERLS decreases when the ratio between the costs increases.

Conclusion

This partial exploration:

The next step is to proceed with random layered graphs and cholesky DAGs.

## 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] knitr_1.15.1  bindrcpp_0.2  igraph_1.0.1  ggplot2_2.2.1 dplyr_0.7.4  
## [6] tidyr_0.2.0   purrr_0.2.0   stringr_1.2.0
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.10     bindr_0.1        magrittr_1.5     munsell_0.4     
##  [5] colorspace_1.2-2 R6_2.1.0         rlang_0.1.6      highr_0.3       
##  [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