On Tuesday 11 August 2009, Alan Stern wrote: > On Tue, 11 Aug 2009, Rafael J. Wysocki wrote: > > > > The general algorithm for maximum parallelism goes as follows: Start by > > > resuming (in parallel) all the devices which don't depend on anything > > > else. Each time a resume finishes, you go on to resume (in parallel) > > > all the devices which depend only on resumed devices and which haven't > > > yet started to resume. > > > > > > As described, this can require a large number of threads. It also > > > requires detailed knowledge of which devices depend on others, which we > > > don't have. > > > > It's even more complicated than that. > > > > Assume we have 7 devices, A-G, such that A is the parent of B and C, > > B is the parent of D and E, and C is the parent of F and G. Assume in addition > > that the PM dependencies between the devices are fully reflected by the > > device tree structure (ie. there are no dependencies that aren't reflected > > parent-child relationships) and that B and G take 0.5 s to resume while the > > others take < 1 ms each. So, the total sequential resume time is > > 2 s + O(1 ms). > > > > Now, if we used the above algorithm, we'd first resume DEFG which would take > > 1 s because of G, then we'd resume BC which would take 1 s because of B and > > the total resume time is again 2 s + O(1 ms). > > (You probably mean "suspend" instead of "resume".) Yes, I got it the other way around here, sorry. > No, you misunderstood my description. We'd start out by suspending > DEFG. DEF will finish quickly, at which time we would start suspending > B because all its dependencies are satisfied. When G finishes we would > start suspending C. When B and C are both finished, we would suspend > A. Total time would be about 1 s because B would be started shortly > after G. Ah, OK. > > However, one can observe that B doesn't need to wait for G to resume, because > > they are independent of each other. So, we can resume BDE in parallel with > > CFG, while of course DE have to wait for B and so on, but this way we can > > theoretically reduce the total resume time to 1 s + O(1 ms). > > > > The question is how to do that and it seems to me that we can use completions > > for this purpose. Namely, add a completion to each device with the following > > rules: > > 1) all completions are reset before dpm_resume(), > > 2) before executing the ->resume() callback for device D, we wait for the > > completion of the D's parent, > > 3) we complete the D's completion after executing its ->resume() callback. > > Also, the items executed in parallel are now the "wait for the parent's > > completion, run our callback and complete our completion" things. > > Yes, that's essentially what I described. Good. > > At first sight I don't see anything fundamentally wrong with this approach. > > Nothing fundamentally wrong. The problems come in the details. Most > notably, the dependencies that are not reflected in the tree structure. > > In practice, rather than completions I'd recommend using a pool of > threads together with a single wait queue and a list of devices which > _might_ be ready. Initially this list can contain every device. > > Each time a thread wakes up it scans the list, removing devices that > aren't actually ready yet (i.e., the dependencies aren't satisfied). > If it doesn't find any devices that are ready, it goes back to sleep. > When it finds a device that _is_ ready, it wakes up another thread and > invokes the callback. When the callback is done, the thread adds to > the list all devices that depend on the one just finished. Then it > goes back to scanning the list. That looks quite complicated at first sight, but asynchronous resume with completions can be done in a relatively simple patch. I've got one, so tomorow I'll post it for further discussion. Thanks, Rafael PS Did you have a chance to look at rev. 15 of the runtime PM patch (http://patchwork.kernel.org/patch/40306/)? -- To unsubscribe from this list: send the line "unsubscribe linux-acpi" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
