Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

9
  • 1
    $\begingroup$ What is the role of $k$? If you can only schedule exactly $k$ workloads (and no less), isn't it equivalent to speak of single workloads that take $k$ times as long? Do the workloads all arrive at t=0? $\endgroup$ Commented Mar 8, 2012 at 18:46
  • $\begingroup$ Would it not be more natural to assume execution times are $f(I)/s$ with $I$ an instance ("workload"), $f$ a known function and $s$ the current machine's speed? If so, you can use machine speeds to inform your decisions, and learn speeds if you do not know them (or they change). Random execution times don't give you any information about how to distribute your work. $\endgroup$ Commented Mar 8, 2012 at 18:58
  • $\begingroup$ @AlextenBrink Yes, all workloads arrive at time t = 0. In a sense, yes, you can assume that k = 1 in this question... but X is for a single workload, not for a batch of k workloads, and in any event, k might be something I want to tune in practice (to overcome communication latency overheads, perhaps). If you can solve the rest for k = 1, the jump to other k should be straightforward (just find out the distribution Y = X + X + ... + X (k times)). $\endgroup$ Commented Mar 8, 2012 at 19:23
  • $\begingroup$ @Raphael I agree that random workload sizes don't give any useful information about how to distribute the work... that's the intent of the problem, though. Several simplifications are being made here, but what I'm interested in is primarily analyzing these simple methods (static and dynamic) with these simplified assumptions, before (possibly) expanding the scope of the question (for instance, by saying we have more information about how much work a particular workload will require, and by dropping the assumption of uniformly - or constantly - performing nodes). $\endgroup$ Commented Mar 8, 2012 at 19:30
  • $\begingroup$ @Raphael In fact, the motivation for this question is exactly this: if you don't know anything about how long a particular workload is going to take, can you do much better than the static and dynamic methods described above? In any event, how much better is the dynamic method compared to the static method (it can't be worse, and I provide an example where dynamic is actually better). $\endgroup$ Commented Mar 8, 2012 at 19:33