Wouldn't it be a better idea to assign priority tasks based on deadlines minus the estimated computation times, rather than just the deadlines?
---------------- From: [email protected] Subject: Re: [boinc_dev] Ideas for BOINC client/task prioritization. The CPU scheduler already takes deadlines into account. First there is the concept of computation deadline as distinct from report deadline. The computation deadline = report deadline - ("Connect every X" + "task switch interval"). If, given all of the other work on the system and the resource shares of all of the other tasks on the system, that task is not estimated to complete within 90% of the time between now and the computation deadline, that task is given high priority. At every task switch opportunity (interval and several events) the high priority tasks are assigned CPUs in Earliest Deadline First. If there are any remaining CPUs these are assigned to tasks in FIFO within a project and modified round robin between projects. If everything were to run strictly by EDF, there would be a problem with long tasks with correspondingly long deadlines. These could be starved of all CPU time until such a time that they would be returned late. Example: Project A Deadline 5 days Computation time ~1 day. Project CPDN Deadline 90 days, computation time ~30 days. On a multi CPU system, the following is likely to happen: Download a CPDN task. Download 1 task from Project A / CPU. Since all tasks from Project A have an earlier deadline than CPDN, they get the CPU. Repeat above 2 lines until CPDN task is< 5 days from deadline. Now try to compress 30 days of computation into 5 days. I believe what you are asking for is already in place. jm7 |------------> | From: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |Mark Sterling<[email protected]> | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | To: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |<[email protected]> | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | Date: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |11/04/2011 04:49 PM | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | Subject: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |[boinc_dev] Ideas for BOINC client/task prioritization. | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | Sent by: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |<[email protected]> | >--------------------------------------------------------------------------------------------------------------------------------------------------| I was directed here by pepo from the BOINC forums. Anyhow, I had an idea about the client and its behavior with prioritizing tasks. I don't know if this is possible with the way BOINC is set up, but the things that would be cool to see: 1) Prioritize tasks based on deadline...preemptively increase priority on tasks that with a bit of a time buffer after examining deadline on other tasks. For instance: Task #1 will take 2d to complete and has a deadline of 3d. Task #2 will take 3d to complete and has a deadline of 8d...so the client should have task #1 run non-stop until completion and then run task #2. An exception could be if task #1 will definitely not complete on time, but task #2 has a chance to or will complete if it runs immediately, then the client could just give up on task #1 and focus on task #2. This type of calculation can be fine-tuned somewhat by monitoring stats over a period of time on each project run to see how the computer behaves on average. 2) If the queue is getting full and it has almost reached a maximum work capacity for the time allotted, even after reporting work units, the client should throttle getting new tasks until the work queue has emptied out some. This also could be fine-tuned by past history. 3) Take into account total time in the calculation of maximum work possible by factoring in competition for GPU resources as well as work units that are set to use multiple CPUs (like some of the Milkyway units which gobble up all of them). Additionally, "high priority" work units should not always run if it is more efficient to run other work units that are due earlier. (Primegrid often locks processors so other work units won't run and might pass its deadline even though there may be plenty of time to run them afterwards.) In any case, a lot of the projects don't play nice with each other, and I find myself having to babysit them manually which is lame. Just some ideas. Sorry my thought processes aren't completely clear and coalesced. Figured I'd get the general gist out and let the more software engineery/mathematician types see if it's feasible, desirable, and if so, the best way to implement them. I guess really what I'm asking is to have a best fit algorithm added. Or maybe Tetris. :) _______________________________________________ boinc_dev mailing list [email protected] http://lists.ssl.berkeley.edu/mailman/listinfo/boinc_dev To unsubscribe, visit the above URL and (near bottom of page) enter your email address.
