work queue priority invariants

[benclifford]

I'm seeing behaviour where WQ tasks aren't executed in priority order, for a Parsl user.

I hacked around in the codebase and I can see the priorities delivered all the way into to the operations that work on q->ready_list.

But then it looks like the list is getting out of order: I added this check at the start of send_one_task on a hypothesis I assumed, that q->ready_list should be in priority order. (although I'm unclear if that is expected to be true).

I end up with a q->ready_list that is quite out of order. For example:

BENC: checking list order
BENC: entry priority -18.730013
BENC: entry priority -19.377128
BENC: entry priority -20.990366
BENC: entry priority -21.471784
BENC: entry priority -22.673790
BENC: entry priority -22.888660
BENC: entry priority -25.742648
BENC: entry priority -26.607197
BENC: entry priority -28.126937
BENC: entry priority -29.548732
BENC: entry priority -29.638328
BENC: entry priority -30.239305
BENC: entry priority -33.161287
BENC: entry priority -34.062007
BENC: entry priority -37.991897
BENC: entry priority -40.609988
BENC: entry priority -40.727513
BENC: entry priority -41.533317
BENC: entry priority -44.636339
BENC: entry priority -45.619628
BENC: entry priority -45.753476
BENC: entry priority -45.829790
BENC: entry priority -47.320308
BENC: entry priority -47.816183
BENC: entry priority -48.364868
BENC: entry priority -48.679864
BENC: entry priority -53.935601
BENC: entry priority -56.517787
BENC: entry priority -61.032222
BENC: entry priority -4.027813
BENC: list is out of order - it should be descending
BENC: entry priority -4.034614
BENC: entry priority -4.096619
BENC: entry priority -4.129197
BENC: entry priority -4.259326
BENC: entry priority -4.277225
BENC: entry priority -4.307081
BENC: entry priority -4.629009
BENC: entry priority -4.847665
BENC: entry priority -4.895281
BENC: entry priority -5.912347
BENC: entry priority -6.119405
BENC: entry priority -6.989896
BENC: entry priority -7.565397
BENC: entry priority -7.774574
BENC: entry priority -7.992148
BENC: entry priority -8.028452
BENC: entry priority -8.735769
BENC: entry priority -8.971470
BENC: entry priority -9.086354
BENC: entry priority -9.511160
BENC: entry priority -10.241796
BENC: entry priority -10.438019
BENC: entry priority -10.801479
BENC: entry priority -11.053111
BENC: entry priority -11.512188
BENC: entry priority -11.749560
BENC: entry priority -12.064031
BENC: entry priority -12.781551
BENC: entry priority -13.288103
BENC: entry priority -13.462147
BENC: entry priority -14.395489
BENC: entry priority -14.497951
BENC: entry priority -15.642678
BENC: entry priority -17.450457
BENC: checked list order

Over time that list seems to get permuted rotated around a bit - staying in-order-except-for-one-patch.

Here's the code for the above output I added at the start of send_one_task in work_queue.c

@@ -4589,18 +4598,42 @@ static int send_one_task( struct work_queue *q )
        int tasks_considered = 0;
        timestamp_t now = timestamp_get();
 
+        // the list should be in order, larger values later
+        // because thats how priorities work.
+
+        printf("BENC: checking list order\n"); 
+        void *i = NULL;
+        void *last = NULL;
+        struct list_cursor *cur = list_cursor_create(q->ready_list);
+        for (list_seek(cur, 0); list_get(cur, &i); list_next(cur)) {
+                printf("BENC: entry priority %f\n", work_queue_task_priority(i)); 
+                if(last == NULL) {
+                    last = i;
+                } else {
+                    if(!(work_queue_task_priority(i) < work_queue_task_priority(last))) {
+                        printf("BENC: list is out of order - it should be descending\n");
+                    }
+                    last = i;
+                }
+                // if (p(i) <= p(item)) {
+                i = NULL;
+        }
+        list_cursor_destroy(cur);
+        printf("BENC: checked list order\n"); 

I think that is the superficial explanation of why I'm not seeing tasks run in priority order.

I'm not clear from the code what the invariants are meant to be - what's happening with that list_rotate call right after that as far as I understand it deliberately violates the above invariant.

Let me know if you want a more focused reproducer or any other investigation.

Attached is the parsl code I'm running that generates a prioritised workload, which is what I have been using to investigate. You should be able to run it as python3 priotasks.py. It doesn't actually give any machine-tested validation that tasks are run in priority order, but it does enough to drive the above patch output.

priotasks.py

This is added onto 2c8f80d

[dthain]

Hi Ben, thanks for letting us know. This is actually a complicated question to answer! FYI @colinthomas-z80 @btovar @JinZhou5042

One underlying issue here is that we have made a number of changes over the years that weaken strict priority scheduling in favor of high throughput dispatch. (e.g. if you have 1M tasks of varying requirements that may or may not be runnable, it will be inefficient to always start searching at the top of the list.)

Another is that, due to concurrent dispatch, possible failures, etc, there really isn't any guarantee that tasks will finish in priority order regardless.

So, in the current WQ main loop, instead of searching through the entire list all at once, we consider attempt_schedule_depth tasks via list_rotate, and then leave the scheduler to do other things, like retrieving complete tasks, etc.

Now, we can give you an option to make the priority more strict, but it will likely come at the loss of some throughput at large scale. We can do it either way... but how important is strict priority order for you?

[benclifford]

I did a bit of a bisect and the priority behaviour works ok-ish (in the sense of my test program) before #3373 and then moves to this behaviour when I move to #3373.

[benclifford]

absolute priority order isn't a requirement, I think, but the behaviour we're working on is getting rid batch job long tails by running expected-longer tasks earlier than expected-shorter tasks, so that shorter tasks are available for in-fill near the end.

in some informal experiments, even a 1-bit priority of "long" or "slow" task is enough here to see a decent improvement - and users aren't going to be able to estimate runtimes perfectly (and so an absolute priority doesn't even exist!)

so absolute priority isn't a necessity, but the behaviour I'm seeing right now is giving timings and behaviour that basically is the same as having no priority or random priority: put stuff in the list in some order, spin it round with list_rotate a bunch until it stops, and pick whats at the end of the list. I think that's the case at any scale, in principle, looking at the implementation?

[benclifford]

(rough numbers: the task vine variant of the priotasks script goes from 27% idle cpu-time to 13% cpu-time using time-based priorities. that change is very sensitive to the actual workload, though. the end user is LSST, and I know they have quite well characterised and varied tasks in their workloads so I was hoping for some decent results there, although not as contrived as priotasks.py)

[dthain]

Ok, let me see if I can give you some options on this.

[benclifford]

parallel to this, I'll see how amenable the users are to using either task vine or parsl's high throughput executor which do show the right kind of prioritisation behaviour

[dthain]

@colinthomas-z80 can you give Ben a quick fix for WQ on this?

I am thinking to have a simple switch between two behaviors:
1 - High Throughput - rotate the list by attempt_schedule_depth as now.
2 - Priority - always search the whole list in priority order.

And then we can do 1 by default until someone submits a task in which priority!=0, and then switch to 2.

Does that seem feasible for a quick fix?

[benclifford]

from my user perspective I think that approach is fine: in the specific real use case I have data for, I'm hoping to eliminate around 4h of walltime on a run with batch jobs tasks measured in minutes, so I hope that gives plenty of buffer for spending more time on task selection.

[colinthomas-z80]

That should work. I think the PR which introduced the problem was addressing throughput issues on short-running benchmarks. I would assume that workflows with short running tasks are less likely to have priorities assigned. I'll give it a try.

[dthain]

@colinthomas-z80 also consider pulling the skip list into this implementation, and that may solve both problems handily.