Differential D98976
[CodeGen] Use ProcResGroup information in SchedBoundary Authored by dpenry on Mar 19 2021, 11:46 AM.
Details When the ProcResGroup has BufferSize=0,
Used to model parallel uses from a pool of resources.
Diff Detail
Event TimelineComment Actions I'm not sure this avoids the criticisms from D94604 - we have resource groups and the child resource units, and we can control the width of both of these to model usage each cycle. But for starters, I'd like to see tests of some kind (llvm-mca timeline or whatever you prefer) that clearly shows the issue you think you're encountering. Comment Actions The issue comes when using resource groups with BufferSize = 0 -- MachineScheduler just doesn't care about the group indicating a parallel use of resources, though from the discussion in D94604, it seems clear that this is what resource groups are intended to model. It hasn't shown up as an issue before because resource groups with BufferSize = 0 haven't been used before D98977 (which tries to use resource groups in the CortexM7 scheduling model instead of directly using multiple copies of a resource, as code comments indicate that using a resource twice for an in-order model is supposed to mean using it over multiple cycles.) Some sort of test showing the change in scheduling outcomes is a good idea and I'll come up with something. Comment Actions This patch doesn't look right to me. I share the same concerns as Simon. How resource cycles are contributed by individual units of a group has nothing to do with the value of BufferSize. A BufferSize of zero simply means that the dispatch event must coincide with the issue event. In the absence of a buffer, opcodes are forced to be sent immediately for execution to the underlying resource units. Basically, there is no delayed execution, and resource consumption starts immediately. It doesn't say anything about how and which units are selected for execution. Comment Actions In MachineScheduler, BufferSize = 0 means more than just dispatch = issue. I don't know if this is what was intended originally, but it's certainly what's in the code. Only resources with BufferSize = 0 are "reserved" resources. ReservedCycles is only updated for these resources Thus, if BufferSize <> 0, the consumption is *not* tracked on a cycle-by-cycle basis. This is not anything I have changed; if it doesn't make sense, it hasn't made sense for a long time. But this actually does make sense, I think. When BufferSize = 0, the structural hazard stalls both issue and dispatch; the resource consumption can be assigned to a particular cycle. When it isn't, it's stalling dispatch, but not issue, and the resource consumption can 't really be assigned to a particular cycle. Thus, the current approach of not tracking it exactly but using it to determine overall resource pressure is a valid one when BufferSize <> 0. TableGen doesn't allow a resource to be repeated in the list of processor resources for an instruction, stating in the comments that it's important to use them serially for in-order processors. (I'm not sure I agree with that, but that's what it says and does.) Thus uses of two sub-resources of a resource group, two uses of the same resource, or uses of two resources with the same parent all end up with some resource being used for 2 cycles instead of two uses of 1 cycle. That's perfectly fine if BufferSize <> 0 for the resource, as the amount of resource pressure is the same for two uses of one cycle and one use of two cycles. But for BufferSize = 0, you get weird scheduling results instead. D94604 attempted to get around this by allowing an explicit statement in the scheduling model of how many parallel uses of a resource were intended and carrying that information in the WriteProcRes table. As that was deemed not necessary because uses of resources within resource groups are supposed to imply parallel uses, this patch looks to see if the unbuffered resource at hand is a resource group and adjusts its cycle use as if the uses are intended to be in parallel. If this all seems surprising, it is... who would have thought that it was impossible to schedule multiple uses of a resource by an in-order processor correctly? But it turns out that no processor scheduling model had tried to use BufferSize = 0 with a processor resource group before. The CortexM7 model uses BufferSize = 0 and multiple uses of the same resource, which doesn't produce good results; debugging that is what led to these patches. One use of two cycles and two uses of one cycle are not the same thing for an in-order processor. I will work up a test that shows what is happening currently, and hopefully that will make it more clear. Comment Actions
Thanks for clarifying this particular aspect. I was under the (wrong) impression that resource consumption was always updated regardless of whether BufferSize was 0 or not. Based on your last comment, my understanding is that CortexM7 is the only model really affected by this change. Comment Actions You folks all know more about scheduling than I do, but if you are in accord that is great. I can certainly verify that this improves the accuracy of the M7 schedule for the samples I've seen. There are a number of loops where the if and else are very similar now. Is it possible to combine them, possibly with the use of some lambda functions? It might be worth having a getWriteProcRes that returns an iterator_range. Some other nitpicks inline.
Comment Actions I had another look at the patch. The resource cycle computation doesn't look correct. I think that there is a bit of confusion on how resource cycles of a group are allocated to the underlying sub-units. See my comments below.
Comment Actions I didn't deal with resources assigned to more than one group as an intentional simplification; I had intended to document that. The code can certainly be made to accommodate that with more complexity. Again as a simplification there is an assumption of equal cycle usages among members of a group. You could also think of it as finding the average number of cycles the resource group is used. I wouldn't mind make it more exact, but max is not going to give the right answer for true hazarding; it would need to really recreate the original structure of uses (e.g. 1 instance for 2 cycles in parallel with 1 instance for 1 cycle). Not impossible, but more complexity. However, there must be a tracking of how many uses have been made of a resource group by its members. The whole point of this exercise is to be able to model the simultaneous use of multiple instances of a resource; the resource group represents this resource. If we don't track them in some way, we can't use the right number of them.
Comment Actions It sounds like you are making a lot of simplifications though. I understand that part of the goal is to keep algorithmic complexity low, but the resource usage is definitely inaccurate for units that are in multiple groups. About the number of cycles: For groups, I understand your concern about using MAX (I actually meant to write MIN to be honest - I wrote that message very late). However I disagree that it is about computing the average. A group is "available" if at least one of its sub-units is available. Conversely, it is busy if _all_ the sub-units are also busy.
Normally you would not need to track uses to solve that issue. It might makes sense for your particular algorithm, but in normal circumstances, the resource consumption is never a function of the users, but only of the resource cycles contributed by the writes. Comment Actions I have added a test case which might clarify how the scheduling improves with the scheduler changes; the t2ADDrr is able to dual-issue with VADDD, but VLDRS is not. But more fundamentally, I am not sure that I'm understanding the semantics of ProcResGroup in the same way, so I'll just ask a few questions... Assume: let BufferSize = 0 in {
def X : ProcResource<1>;
def Y : ProcResource<1>;
def A : ProcResGroup<[X, Y]>;
}
def MyWideWrite : SchedWriteRes<[X,Y]> {
let ResourceCycles = [1, 1];
}
def MyNarrowWrite: SchedWriteRes<[A]> {
let ResourceCycles = [1];
}
Comment Actions This is how I see it: A group behaves like a hardware scheduler. Consuming a group for 1cy is equivalent to consuming one of its underlying sub-units for 1cy. In your example, there is only one instance of group A, and it intercepts all the uses/consumptions of X and Y. So, both MyWideWrite and MyNarrowWrite use A. Since MyWideWrite consumes both X and Y for 1cy, group A becomes also unavailable for 1cy. MyWideWrite is basically consuming the entire group, effectively stalling the dispatch from A until at least one between X and Y becomes available again. MyNarrowWrite only consumes one between X and Y for 1cy. That is because consuming A for 1cy is equivalent to consuming one of {X, Y} for 1cy. Group A is still available after the issue of MyNarrowWrite if not all sub-units are busy. Note that this can only happen when X and Y are both available before the issue of MyNarrowWrite. Group A is fully consumed for at least 1cy if either X or Y was busy before MyNarrowWrite was issued. Sequence MyNarrowWrite, MyNarrowWrite can be issued during a same cycle. However, this can only happen if both X and Y are available at the beginning of the sequence. A sequence MyWideWrite, MyNarrowWrite can never be issued during a same cycle, because MyNarrowWrite consumes the entire group of A, this making resource A unavailable for 1cy. Back to your patch. I am OK with a simplified approach like yours as long as a) it fixes your particular cases, b) your case is likely to be the most common one, and c) we document all the assumptions made by your algorithm somewhere in the MachineScheduler. Comment Actions OK, I think we are in agreement about what they're supposed to allow/disallow when ResourceCycles is uniform. I'd like to make a stab at making this work in the general cases of SchedWriteRes you mentioned before as well:
def X : ProcResource<1>;
def Y : ProcResource<1>;
def A : ProcResGroup<[X, Y]>;
def UnevenWideWrite : SchedWriteRes<[X,Y]> {
let ResourceCycles = [1,2];
}
def MyNarrowWrite : SchedWriteRes<[A]> {
let ResourceCycles = [1];
}
def OverWideWrite : SchedWriteRes<[X,Y,A]> {
let ResourceCycles = [1,1,1];
}
def OverNarrowWrite : SchedWriteRes<[X,A]> {
let ResourceCycles = [1,1];
}As an algorithmic detail, though there's logically one instance of a ProcResGroup, the subtarget emitter actually reports it to have as many instances as the total instances of its members. There seem to be a few options for dealing with groups:
Use of the second, third, or fourth alternative will require some means of choosing which member is the victim; first-available, LRU, or plugin are all viable options. At this point, #4 is the way I'm leaning; it's clean and simple -- a resource group is fully used (and thus prevents further issue) when all its members are used. No extra tracking is required. It is also fairly simple to state what model features are not being handled -- write resources which mix the members and the group and for which the group has BufferSize = 0. #2 and #3 just seem like half-solutions that will sometimes work and sometimes not work. #1 will leave code very similar to what you see now (without dividing cycles by units used, but still requiring requests for multiple instances). Comment Actions Sounds good to me. Comment Actions Patch looks good. I left a couple of comments below. Thanks!
Comment Actions Now using APInt (thanks for that.... I'd wanted something like that but had forgotten what it was called!) and a helper function. Thanks for detailed reviews; I think this is much better code than I started with. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
uint64_t is fine in general because models tend to declare less than 30 processor resources on average. On x86 I have seen peaks of ~45 resources (iirc). I don't expect future models to end up declaring more than 63 resources (even mca makes that strong assumption).
That being said, if possible (and if it is not problematic for your code) it would be much safer to use APInt, so that we are not limited to 64-bits and we can manipulate arbitrary big bitmasks.