Janne, As one of those who designed the fair-share component to the multi-factor priority plugin, I'm open to your suggestions below. I would recommend you create it as a separate multi-factor plugin so that we could have the opportunity to switch back and forth and examine the differences in behavior. If it winds up delivering more fairness across all cases, then I'm sure we would abandon the current implementation someday.
I'm not sure how best to handle the sshare utility with regard to the fields it displays. It might make sense to create a new sshare that displays the pertinent components of the new algorithm. Would you mind citing the reference(s) that motivated the formula you presented below? While I understand the shortcomings in the scenario of the A, B, and C accounts you describe, coming up with an elegant design that supports a multi-level hierarchy is not a trivial problem, particularly when one of the requirements is to create something that users will understand intuitively. Don > -----Original Message----- > From: Janne Blomqvist [mailto:[email protected]] > Sent: Thursday, August 23, 2012 12:05 AM > To: slurm-dev > Subject: [slurm-dev] Making hierarchical fair share hierarchical > > > Hello, > > we are seeing an issue with the hierarchical fair share algorithm which > we'd like to get fixed. We think our suggested improvements would be of > benefit to others as well, but we'd like some inputs on how, or indeed > whether, to proceed. > > For some background, we have a cluster shared between several > departments, and we have configured the fair-share such that each > department account has a share corresponding to its financial > contribution (so far it's simple, 3 departments with equal shares each). > Thus it's politically important for us that the fair-share priority > reflects the usage factor of each department as well as between users > belonging to an account. And yes, we're certainly aware that fair share > cannot guarantee that departments get their fair share, but it should at > least push in that direction. > > Thus, we'd like the fair-share factor of a user reflect the account > hierarchy, such that users belonging to underserved accounts always have > a higher fair-share priority than users belonging to an account which > has used more than it's fair share. > > The problem we're seeing is that the current hierarchical fair-share > algorithm does not manage to do this in our case. Our issues seems to be > partly due to the departments having somewhat different usage patterns. > The departments have a roughly equal amount of users, but for two of the > departments (lets call them A and B) most of the users use the cluster > very little, but with a few heavy users. The third department, OTOH, has > a much larger number of active users. The end result of this is that the > heavy users of the A and B departments have very low fair-share > priorities, and department C manages to use most of the resources since > their users have higher fair-share priorities, despite the usage at the > department level being far away from the fair-share target. > > After reviewing literature and thinking about the issue, we suggest to > calculate the hierarchical fair-share as follows (in latex notation): > > fs = ( \sum_{i=0}^d fs_{raw}(i)*k^{(d-i)} ) / k^d > > (for a rendered version, see e.g. > > http://texify.com/?$fs = ( \sum_{i=0}^d fs_{raw}(i)*k^{(d-i)} ) / k^d$ > > ) > > where fs_raw is the non-hierarchical fair-share (2^(-U/S)), d is the > depth of the account/user in the tree hierarchy (i=0 is the root of the > tree), and k is a scaling factor. k should be chosen such that it's > large enough to distinguish between nodes at the same depth of the tree, > and small enough that there are enough digits in the priority so that > reasonably deep trees work as intended. That is, as long as two accounts > at the same level of the tree differ in priority by more than 1/k, the > users under those accounts will not be intermingled with each other. > OTOH, as the priority ultimately is a uint32_t, even with a large > fair-share priority weight there are at most only about 9 digits. We > suggest k=100 as a starting point, which would allow about 4 levels deep > hierarchy (5 when including the root) before the priorities at the > bottom of the tree would start to get filtered out. > > So, how to proceed? We think others would benefit from this as well, and > of course we have the selfish desire to have this upstream so that we > don't have to carry around our own (not yet done) patch indefinitely, or > come up with some other way to solve our problem. Is there a need to > keep the existing hierarchical fair-share algorithm around, or can we > replace it with our version? If so, as our approach doesn't use the > concept of "effective usage", this should be removed from the code and > tool output (e.g. sshare). As this issue is important to us, we're > prepared to do the dirty work, but we'd like some feedback first before > doing anything. > > > > -- > Janne Blomqvist
