1
$\begingroup$

I am testing two multiprocessor scheduling algorithms, on the same task sets (same workload), using a simulator. I am comparing the response-time of task execution (end_time - start_time), to see which of the two algorithms performed better (produces lower response-times). Assume 30 unique tasks for the experiment. I have 2 sets of results (30 samples each), each representing the response-time of the 2 algorithms.

Visually I can see that Alg.A is better than Alg.B. I am unsure which test to run, to check if the improvement is indeed statistically significant, or by chance.

From a statistical viewpoint - its the same population (30 individuals), independent treatments, un-paired data, and both distributions non-normal, continuous values. Also the two distributions may/may-not be the same. Also, I do not think this can be considered as repeated measures, as its 2 treatments on the same population, being induced in an independent-way. But they are not also different groups - i.e. same initial population.

From what little I know about non-parametric statistics, I am not sure, if I should use Mann-Whitney-U test OR Wilcoxon signed-rank test. Or something else completely ?

Many thanks

EDIT This is the experiment methodology:

1) Create a workload : $W_i = \{\tau_0, \tau_1..\tau_n\}$. Here, $W_i$ is a set of tasks ($\tau_i$) with properties (priority, computation cost etc.). We measure each task's response time $R(\tau_i) = time_{end} - time_{release}$ after execution (units: seconds). All tasks are release at same time. Different scheduling algorithms will produce different $R(\tau_i)$ due to the order of execution of tasks (e.g. if $\tau_2$ is executed first and $\tau_1$ is executed second, then $tau_1$ has a longer $R(\tau_1)$

2) We want to see the performance of two scheduling algorithms : algA and algB.

3) We schedule and execute $W_i$ using algA : this gives us a $R(\tau_i)$ distribution, lets call it $dist_A[R(\tau_i)]$

4) We schedule and execute $W_i$ using algB : this gives us a $R(\tau_i)$ distribution, lets call it $dist_B[R(\tau_i)]$

5) We draw box-plots for both $dist_A[R(\tau_i)]$ and $dist_B[R(\tau_i)]$. We can see $dist_A[R(\tau_i)]$ has a lower mean/median and slightly lower IQR. Hence, we deduce algA is better than algB (to reduce task response times)

6) Now we want to find if this improvement of algA over algB is 'statistically significant'

$\endgroup$
  • $\begingroup$ It's a repeated measures design. How do you know you don't have normal data? How can you see visually they are different? $\endgroup$ – John Sep 11 '16 at 20:00
  • 1
    $\begingroup$ Well, I also ran a Shapiro-Wilks Normalcy test to test, and also one looks like an long-tailed weibull distribution, other looks like a log-normal distribution. From the simulation viewpoint, non-normal distributions makes sense. How can it be repeated measures, because I don't measure the results before/after treatment. Its just two independent treatments, measured once each at the end of the simulation. $\endgroup$ – bd3lk Sep 11 '16 at 20:04
  • $\begingroup$ Each subject (task set, work load, example??) is in every condition. That's definitely repeated measures. It doesn't have to be before / after. It just has to be taking the measures repeatedly from the same subjects. $\endgroup$ – John Sep 12 '16 at 2:36
  • $\begingroup$ You are taking repeated measures of the speed of accomplishing each workload. Therefore, this is paired data. (repeated measures is the same thing but generalizes to more than one measure) $\endgroup$ – John Sep 14 '16 at 20:59
  • $\begingroup$ Is it still 'paired data' even if there does not exist any link between the two treatments ? i.e. the treatments and the result of the treatments are completely independent. $\endgroup$ – bd3lk Sep 15 '16 at 14:00
1
$\begingroup$

The signed ranks test is for paired data.

You stated that your data are not paired.

That would seem to suggest the signed ranks test is not suitable.

Your criterion of "lower response times" isn't especially clear; what aspects of a distribution are we comparing exactly?

If you're happy with the comparison made by the Wilcoxon-Mann-Whitney test then that would be suitable (which for a one sided alternative could be stated as something like $P(X<Y)>\frac12$ or equivalently as the median of cross-population pairwise differences$X_i-Y_j$ being negative), but since you consider the possibility that the distributional forms might differ, you could easily conclude that $P(X<Y)>\frac12$ but it could also be true at the same time that $E(X)>E(Y)$ ... so you need to be sure you're measuring what you want.

On the other hand, since with times you probably would be interested in measuring ratios -- percentage speed up might be relevant for example, you may be better off working with log times (or possibly even speeds - i.e. inverse-times).

[On the other hand it's not clear to me that a significance test is necessarily the best tool here -- it would seem more sensible to describe the distributions of times or differences of times (or perhaps, as I suggested, ratios of times or differences of log-times) with enough simulations to give CIs that either clearly exclude no difference or are so narrow you don't care what the true difference might be. But the first thing is to clearly identify what you really want to measure]

$\endgroup$
  • $\begingroup$ The problem is that the data are not paired, but its the same population (in my case I run the simulation twice with the 'same' workload, using two speedup algorithms) The two distributions are continuous ratio values (i.e. time in seconds). I can show via box-plots that distribution A has a higher mean/median/IQR than B, indicating technique A is worse than B. But I also want to show that this different in the distributions are not by chance, i.e. the difference between distributions are statistically significant. How can I show this without a significance test ? $\endgroup$ – bd3lk Sep 12 '16 at 22:46
  • $\begingroup$ 1. If you have pairs of the same workload -- a pair at workload 1 (one for each algorithm), then a pair at workload 2 and so on, then that IS paired. In that case you want to look at pair-ratios if the workloads differ substantively between pairs ... this could have been made clearer right at the start (rather than stating they weren't paired when it seems that in fact they were) ... 2. My last paragraph above already contains my suggestion (which is to use confidence intervals). However if you want to use a hypothesis test by all means do so ... but get the pairing issue straight first. $\endgroup$ – Glen_b Sep 12 '16 at 23:43
  • $\begingroup$ Okay, thank you. I have added a brief formal explanation of the experiment. I think It is non-paired data, and not repeated measures also. $\endgroup$ – bd3lk Sep 13 '16 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.