Strange behavior Report Deadlines vs Work being performed

Message boards : Number crunching : Strange behavior Report Deadlines vs Work being performed
Message board moderation

To post messages, you must log in.

AuthorMessage
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1091906 - Posted: 31 Mar 2011, 10:40:41 UTC

I've been noticing for a couple years now that quite frequently, my machine will choose a work unit which has a due date far in the future, when there is work waiting to be performed that is due much sooner.

While I do understand that in some cases it might be best for a machine to choose a work unit that isn't the unit that is due in the shortest timeframe, I am not seeing any sort of indication of high priority, except in rare situations.

If I don't see "high priority" next to a work unit that is actively being worked on, why am I not performing the work units that are due soonest? First Due First Worked seems like the best scenario for overall efficiency?
ID: 1091906 · Report as offensive
Profile Gundolf Jahn

Send message
Joined: 19 Sep 00
Posts: 3184
Credit: 446,358
RAC: 0
Germany
Message 1091912 - Posted: 31 Mar 2011, 10:56:49 UTC - in response to Message 1091906.  

First Due First Worked seems like the best scenario for overall efficiency?

That might seem so, but First In First Out is much better.

Gruß,
Gundolf
Computer sind nicht alles im Leben. (Kleiner Scherz)

SETI@home classic workunits 3,758
SETI@home classic CPU time 66,520 hours
ID: 1091912 · Report as offensive
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1091917 - Posted: 31 Mar 2011, 11:28:23 UTC - in response to Message 1091912.  

First Due First Worked seems like the best scenario for overall efficiency?

That might seem so, but First In First Out is much better.

Gruß,
Gundolf


This would only make sense if the due dates are unimportant, or if there was significant loss of effort from task switching.

FIFO doesn't make sense when task switching can happen with very little lost time. Provided of course that there is a real, meaningful reason for report deadlines to be created as they are?
ID: 1091917 · Report as offensive
Richard Haselgrove Project Donor
Volunteer tester

Send message
Joined: 4 Jul 99
Posts: 14488
Credit: 200,643,578
RAC: 874
United Kingdom
Message 1091920 - Posted: 31 Mar 2011, 12:09:17 UTC - in response to Message 1091917.  

Provided of course that there is a real, meaningful reason for report deadlines to be created as they are?

There is intended (though it's not a perfect match) to be a direct correlation between the length of time it will take to crunch a task and the deadline it's allowed from issue to return. So, the 'bigger' tasks require no higher proportion of your computer's time than the smaller ones - which allows older/slower computers to participate on even terms.

That explanation doesn't allow for the Astropulse sub-project, though.
ID: 1091920 · Report as offensive
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1092349 - Posted: 2 Apr 2011, 0:58:38 UTC - in response to Message 1091920.  

Provided of course that there is a real, meaningful reason for report deadlines to be created as they are?

There is intended (though it's not a perfect match) to be a direct correlation between the length of time it will take to crunch a task and the deadline it's allowed from issue to return. So, the 'bigger' tasks require no higher proportion of your computer's time than the smaller ones - which allows older/slower computers to participate on even terms.

That explanation doesn't allow for the Astropulse sub-project, though.


Does this mean that different clients can be assigned different due dates for the same work unit, or does it mean that each group of work units is assigned for machines that fall within a certain average work per day range?

Sorry if I'm being a bit dense here, just trying to understand how it is that scheduling and work unit due dates are assigned / calculated, and why my machine makes the choices it does for the work it performs.
ID: 1092349 · Report as offensive
Profile HAL9000
Volunteer tester
Avatar

Send message
Joined: 11 Sep 99
Posts: 6533
Credit: 196,805,888
RAC: 57
United States
Message 1092356 - Posted: 2 Apr 2011, 1:21:22 UTC - in response to Message 1092349.  
Last modified: 2 Apr 2011, 1:21:52 UTC

Provided of course that there is a real, meaningful reason for report deadlines to be created as they are?

There is intended (though it's not a perfect match) to be a direct correlation between the length of time it will take to crunch a task and the deadline it's allowed from issue to return. So, the 'bigger' tasks require no higher proportion of your computer's time than the smaller ones - which allows older/slower computers to participate on even terms.

That explanation doesn't allow for the Astropulse sub-project, though.


Does this mean that different clients can be assigned different due dates for the same work unit, or does it mean that each group of work units is assigned for machines that fall within a certain average work per day range?

Sorry if I'm being a bit dense here, just trying to understand how it is that scheduling and work unit due dates are assigned / calculated, and why my machine makes the choices it does for the work it performs.


Due dates are assigned when you download the work. My old PII & PIII machines have to return their work in the same amount of time any of the fast machines do.

If a task doesn't contain that much work, Such as a "shorty", it might have a smaller due date on it. Maybe 7 days. If there is a lot to process then the task might have a longer due date. Maybe 20 days.

I'm not exactly how the mechanism to decide how much work is in a task functions. I might guess it may be related to the angle range.
SETI@home classic workunits: 93,865 CPU time: 863,447 hours
Join the BP6/VP6 User Group today!
ID: 1092356 · Report as offensive
Josef W. Segur
Volunteer developer
Volunteer tester

Send message
Joined: 30 Oct 99
Posts: 4504
Credit: 1,414,761
RAC: 0
United States
Message 1092486 - Posted: 2 Apr 2011, 4:56:03 UTC - in response to Message 1092356.  

Due dates are assigned when you download the work. My old PII & PIII machines have to return their work in the same amount of time any of the fast machines do.

If a task doesn't contain that much work, Such as a "shorty", it might have a smaller due date on it. Maybe 7 days. If there is a lot to process then the task might have a longer due date. Maybe 20 days.

I'm not exactly how the mechanism to decide how much work is in a task functions. I might guess it may be related to the angle range.

The shortest deadline is about 13.8 days for "shorties", the longest about 64 days for the extremely rare tasks with angle range just above 0.22549, and they are definitely chosen based on angle range. The basic idea is that a host with a Whetstone benchmark around 40 MIPS will be able to do any MB task within deadline. For more detail, the Estimates and Deadlines revisited thread shows how the deadlines are calculated, though the amount of work was later doubled so the table near the end of that thread shows half the current deadlines.
                                                                  Joe
ID: 1092486 · Report as offensive
Profile Mike Special Project $75 donor
Volunteer tester
Avatar

Send message
Joined: 17 Feb 01
Posts: 33376
Credit: 79,922,639
RAC: 80
Germany
Message 1092554 - Posted: 2 Apr 2011, 7:50:57 UTC

Specially for astropulses it would be better to increase the deadline.
Or to increase system requirements.
20 - 30% of my wingmen dont match the deadline on first attempt.
For such computation times 3 weeks seems a little short.
Not for me running on GPU but for those even without running an optimized ap.

Only a suggestion.

With each crime and every kindness we birth our future.
ID: 1092554 · Report as offensive
Iona
Avatar

Send message
Joined: 12 Jul 07
Posts: 790
Credit: 22,438,118
RAC: 0
United Kingdom
Message 1092606 - Posted: 2 Apr 2011, 12:35:14 UTC - in response to Message 1092554.  

Indeed so, Mike. I got an AP WU this morning that has a deadline date of the 27th of this month and it is already being worked on, ahead of other work. Even under normal situations, it will be finished well before the deadline, but I find it odd that BOINC downloaded an AP which well and truly exceeds my cache by quite a margin. I reverted to a 1 day cache to avoid large numbers of WUs being downloaded and not being worked on, before I went on holiday last month and have not altered that setting, yet.



Don't take life too seriously, as you'll never come out of it alive!
ID: 1092606 · Report as offensive
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1092717 - Posted: 2 Apr 2011, 17:52:10 UTC

OK, looked at the suggested thread about due date calculations for a while, got a headache. (heh)

It seems as if plenty of thought has gone into assigning due dates, and from what I've seen and been able to make heads or tails of, it makes sense.

However I haven't seen anything about how/why my machine chooses the jobs it does for work?

If I have lots of jobs on my machine, some with a due date less than a week out, and others with a due date over a month out, why does my machine more often than not choose the work that is due in over a month rather then the closer due date?

One would think that once my machine has accepted work, it would perform said work based on due dates? I must say that this is the most interesting question for me. The client seems to randomly decide what work units to work on next, I can see no pattern to it.
ID: 1092717 · Report as offensive
Richard Haselgrove Project Donor
Volunteer tester

Send message
Joined: 4 Jul 99
Posts: 14488
Credit: 200,643,578
RAC: 874
United Kingdom
Message 1092720 - Posted: 2 Apr 2011, 18:05:34 UTC - in response to Message 1092717.  

One would think that once my machine has accepted work, it would perform said work based on due dates? I must say that this is the most interesting question for me. The client seems to randomly decide what work units to work on next, I can see no pattern to it.

It possibly depends how you're looking at the tasks. Using BOINC Manager under Windows, it's all too easy to click your mouse on one of the column headers and sort the task list into some unexpected order. Once that has happened (with a triangle showing above one of the columns in the task list), is it almost impossible to view that tasks in their 'natural' order again - you would need to edit the Windows registry.

But if you do that, it suddenly makes sense. The next task to run is the earliest one downloaded (by now at the top of the list), and new tasks are always added to the bottom of the list, and work their way gradually up to 'next to run' at the top.
ID: 1092720 · Report as offensive
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1093109 - Posted: 3 Apr 2011, 21:42:40 UTC - in response to Message 1092720.  

One would think that once my machine has accepted work, it would perform said work based on due dates? I must say that this is the most interesting question for me. The client seems to randomly decide what work units to work on next, I can see no pattern to it.

It possibly depends how you're looking at the tasks. Using BOINC Manager under Windows, it's all too easy to click your mouse on one of the column headers and sort the task list into some unexpected order. Once that has happened (with a triangle showing above one of the columns in the task list), is it almost impossible to view that tasks in their 'natural' order again - you would need to edit the Windows registry.

But if you do that, it suddenly makes sense. The next task to run is the earliest one downloaded (by now at the top of the list), and new tasks are always added to the bottom of the list, and work their way gradually up to 'next to run' at the top.


So, the tasks are worked in the order in which they were received, not based on the due date? They are in fact performed FIFO?

If this is the case, why have due dates?
ID: 1093109 · Report as offensive
Profile Mike Special Project $75 donor
Volunteer tester
Avatar

Send message
Joined: 17 Feb 01
Posts: 33376
Credit: 79,922,639
RAC: 80
Germany
Message 1093121 - Posted: 3 Apr 2011, 22:05:04 UTC

When the deadline gets close boinc turns into EDF.
Early deadline mode first.

With each crime and every kindness we birth our future.
ID: 1093121 · Report as offensive
Cheopis

Send message
Joined: 17 Sep 00
Posts: 156
Credit: 18,451,329
RAC: 0
United States
Message 1093162 - Posted: 4 Apr 2011, 1:14:51 UTC - in response to Message 1093121.  

When the deadline gets close boinc turns into EDF.
Early deadline mode first.


But what is the logic to not always performing work based on it's deadline?

I can understand if you download work, and finish what you work on before going to jobs with an earlier deadline, but I'm having a hard time wrapping my mind around why we are not using deadlines as the prime determination for what work gets done first - especially for work units of roughly the same complexity.
ID: 1093162 · Report as offensive
Profile Bill Walker
Avatar

Send message
Joined: 4 Sep 99
Posts: 3868
Credit: 2,697,267
RAC: 0
Canada
Message 1093169 - Posted: 4 Apr 2011, 1:54:43 UTC - in response to Message 1093162.  

But what is the logic to not always performing work based on it's deadline?



This is another one of those BOINC features that is needed when you run a variety of projects. Some have deadlines 2 years away, some have deadlines two days away. S@H is kind of in the middle. In my experience, I never miss a deadline except when machines blow up, so it seems to work.

ID: 1093169 · Report as offensive
Josef W. Segur
Volunteer developer
Volunteer tester

Send message
Joined: 30 Oct 99
Posts: 4504
Credit: 1,414,761
RAC: 0
United States
Message 1093190 - Posted: 4 Apr 2011, 2:47:06 UTC - in response to Message 1093162.  
Last modified: 4 Apr 2011, 2:48:22 UTC

When the deadline gets close boinc turns into EDF.
Early deadline mode first.

But what is the logic to not always performing work based on it's deadline?

I can understand if you download work, and finish what you work on before going to jobs with an earlier deadline, but I'm having a hard time wrapping my mind around why we are not using deadlines as the prime determination for what work gets done first - especially for work units of roughly the same complexity.

The primary reason is that estimates of how long the crunch will take are notoriously bad. Given that, any possible deadline misses if running EDF (Earliest Deadline First) would impact the longer running tasks. That is, a host might well put in a day's worth of work on a task and have it miss deadline by a couple of hours. That would presumably be because the user had tried for too much cached work, but still the overall BOINC system should do its best to protect users from their own bad judgement.

However, there's a good possibility that BOINC will move toward EDF scheduling. A recent paper in pdf form by Dr. Anderson seems to indicate some emulation and simulation they've done indicate it may be preferable. The hysteresis revision to work fetch and reliance on REC (Recent Estimated Credit) ideas in that paper are already in the BOINC source code though not used by default in the 6.12.x branch.
                                                                  Joe
ID: 1093190 · Report as offensive

Message boards : Number crunching : Strange behavior Report Deadlines vs Work being performed


 
©2022 University of California
 
SETI@home and Astropulse are funded by grants from the National Science Foundation, NASA, and donations from SETI@home volunteers. AstroPulse is funded in part by the NSF through grant AST-0307956.