library(ggplot2)
library(plyr)
library(reshape)
##
## Attaching package: 'reshape'
##
## Les objets suivants sont masqués from 'package:plyr':
##
## rename, round_any
Petite journée à Bordeaux et discussions rigolotes avec Olivier et Frédo. En particulier, Olivier se demande dans quel cas l'utilisation du dynamique par rapport statique est vraiment justifiée (typiquement pour l'ordonnancement de DAG dans des runtimes comme StarPU, DAGUE, …). Intuitivement, le statique peut se faire avoir en raison de la variabilité non prévue des temps de calcul mais est capable de prendre des décisions futées. En revanche. le dynamique s'adapte naturellement aux situations où les temps de calcul sont différents de qui était initialement prévu. D'autre part un des intérêt des approches dynamiques est qu'elles travaillent généralement uniquement sur une sous-partie du graphe (avec une fenêtre glissante), ce qui réduit le temps de décision. En même temps, cette myopie empèche potentiellement de faire des choix intelligents.
Bref, au final, intuitivement, il nous semble que ce qui est potentiellement le plus pénalisant pour le statique, c'est les max, i.e., la situation où on a alloué statiquement des tâches aux processeurs et qu'on doit attendre la terminaison d'une mauvaise allocation alors que le dynamique, lui va être capable de rattraper cela. Évidemment, pour bien faire, il faudrait faire ce genre d'évaluation sur des graphes réeels (genre QR, LU, Cholesky) mais il y a peut-être moyen d'étudier la chose pour des graphes simples et d'en déduire une intuition.
On ne propose donc de regarder le cas du join d'un ensemble de tâches indépendantes. On considère qu'on a \( P \) machines et en moyenne \( N \) tâches sur chaque machine (donc \( NP \) tâches en tout). On suppose que la durée de chacune des tâches suit la même distribution et donc dans le cas statique, on met exactement \( N \) tâche sur chaque processeur. On a regardé différentes distributions toute d'espérance 1: uniforme, un gamma avec une très grosse variance, un gamma avec une variance faible. Après, on a également regardé ce qu'il se passait avec une distribution distribution bimodale vallant 1 une probabilité \( 1-\alpha \) et \( x \) avec une probabilité \( \alpha \) (donc cette distribution est moins comparable aux autres…).
La quantité qui nous intéresse, c'est l'espérance du statique par rapport à l'espérance du dynamque. Dans un cas aussi simple que celui-ci, le statique ne peut gagner en moyenne mais combien peut-il perdre ?
simul = function(N = 20, P = 20, n = 1000, typeservice = "bimod", alpha = 0.01,
x = 10) {
df = data.frame()
for (i in 1:n) {
running_times = switch(typeservice, unif = runif(n = N * P, 0, 2), gamma_L = rgamma(n = N *
P, shape = 4, scale = 1/4), gamma_H = rgamma(n = N * P, shape = 0.2,
scale = 1/0.2), bimod = ifelse(runif(N * P, 0, 1) > alpha, rnorm(N *
P, 1, 0), rnorm(N * P, x, 0)))
# static schedule
m = c()
for (j in 1:P) {
m[j] = sum(running_times[((j - 1) * N + 1):(j * N)])
}
static = max(m)
# dynamic schedule
t = seq(from = 0, to = 0, length.out = P)
for (j in 1:(N * P)) {
p = which.min(t)
t[p] = t[p] + running_times[j]
}
dynamic = max(t)
df = rbind(df, data.frame(typeservice = typeservice, alpha = alpha,
x = x, N = N, P = P, static = static, dynamic = dynamic))
}
df
}
Curieusement, le code précédent est très lent quand \( N \) et \( P \) augmentent et je ne vois pas bien pourquoi… Bref, on a pas mal joué avec les différentes valeur et voilà le genre de choses que l'on peut voir.
Commençons par considérer la situation de la distribution bimodale avec de temps en temps (5% des cas) une grosse grosse baffe (300 fois plus lent).
df = data.frame()
for (N in c(5, 10, 15)) {
for (P in c(10, 50, 500)) {
df = rbind(df, simul(N = N, P = P, n = 250, typeservice = "bimod", x = 300,
alpha = 0.05))
}
}
Il y ensuite plusieurs façon d'analyser les choses. On peut par exemple s'intéresser à la différence entre le statique et le dynamique pour chaque instance et essayer d'estimer l'espérance de cette différence.
df2 = ddply(df, c("N", "P", "alpha"), summarize, stat_m = mean(static), stat_ci = 2 *
sd(static)/sqrt(length(static)), dyn_m = mean(dynamic), stat_ci = 2 * sd(dynamic)/sqrt(length(dynamic)),
diff_m = mean(static - dynamic), diff_ci = 2 * sd(static - dynamic)/sqrt(length(static -
dynamic)))
ggplot(df2, aes(x = P, y = diff_m, color = N)) + geom_point() + geom_errorbar(aes(ymin = diff_m -
diff_ci, ymax = diff_m + diff_ci), width = 0.1)
Bon, au moins, un premier constat, c'est que cette différence est croissante en \( N \) et en \( P \). Mais ça ne me dit pas comment évoluent les performances en absolu de chacune des deux politiques. Regardons ça:
df3 = melt(df, id = c("alpha", "x", "N", "P", "typeservice"))
df3 = ddply(df3, c("N", "P", "alpha", "variable"), summarize, m = mean(value),
ci = 2 * sd(value)/sqrt(length(value)))
ggplot(df3, aes(x = P, y = m, color = factor(N), shape = variable)) + geom_point(size = 2) +
geom_line() + geom_errorbar(aes(ymin = m - ci, ymax = m + ci), width = 0.2) +
ylim(0, max(df3$m + df3$ci)) + scale_y_log10()
## Scale for 'y' is already present. Adding another scale for 'y', which will replace the existing scale.
Ah tiens, ça c'est amusant. Les performances de la politique dynamique semblent très peu sensibles au nombre de processeur. Pour le coup, les performances de la politique statiques se dégradent beaucoup quand \( N \) et \( P \) augmentent. Au final, ce qui nous intéresse, c'est le ratio des performances entre ces deux politiques. En fait, c'est le ratio des espérances des performances (et pas l'espérence de ratio des performances). Pas évident de calculer un intervalle de confiance là-dessus (mis à part en calculant un intervalle de confiance sur le numérateur et le dénominateur et en propageant).
df4 = ddply(df, c("N", "P", "alpha"), summarize, diff_m = mean(static - dynamic),
static_m = mean(static), diff_ci = 2 * sd(static - dynamic)/sqrt(length(static)),
static_ci = 2 * sd(static)/sqrt(length(static)))
df4$err_cimin = (df4$diff_m - df4$diff_ci)/(df4$static_m + df4$static_ci)
df4$err_cimax = (df4$diff_m + df4$diff_ci)/(df4$static_m - df4$static_ci)
ggplot(df4, aes(x = P, y = diff_m/static_m, color = N)) + geom_point() + geom_errorbar(aes(ymin = err_cimin,
ymax = err_cimax), width = 3) + geom_point(size = 4)
Bon, donc, clairement, la perte du statique par rapport au dynamique croit bien avec \( N \) et \( P \). Tentons de voir ce que ça donne avec des valeurs un peu extrêmes:
for (N in c(5, 10, 15, 50)) {
for (P in c(1000, 1500)) {
df = rbind(df, simul(N = N, P = P, n = 250, typeservice = "bimod", x = 300,
alpha = 0.05))
}
}
Bon, on redessine:
df4 = ddply(df, c("N", "P", "alpha"), summarize, diff_m = mean(static - dynamic),
static_m = mean(static), diff_ci = 2 * sd(static - dynamic)/sqrt(length(static)),
static_ci = 2 * sd(static)/sqrt(length(static)))
df4$err_cimin = (df4$diff_m - df4$diff_ci)/(df4$static_m + df4$static_ci)
df4$err_cimax = (df4$diff_m + df4$diff_ci)/(df4$static_m - df4$static_ci)
ggplot(df4, aes(x = P, y = diff_m/static_m, color = factor(N))) + geom_point() +
geom_errorbar(aes(ymin = err_cimin, ymax = err_cimax), width = 3) + geom_point(size = 4)
Argh, ça redescend avec \( N \) au bout d'un moment. Et ça stagne franchement même quand \( P \) augmente.
Bon, je vais m'arrêter là, il est tard. Il est très facile de jouer avec les paramètres des lois pour voir leur impact. L'erreur la plus grande que j'ai observée en jouant avec tout ça était de .92 mais je ne me souviens plus bien pour quels paramètres. Ce que l'on subodore, c'est que c'est plus petit que 1 et que cette borne est tight mais pour le montrer…