Look-Ahead Multi-Pass Scheduling For Jobs Of Variable Sizes
Publication Date: 2015-Jun-15
The IP.com Prior Art Database
A method is disclosed for a look-ahead multi-pass scheduling for one or more jobs of variable sizes by examining the one or more jobs to decide on resource assignment.
Page 01 of 4
Disclosed is a method and system for look-ahead multi-pass scheduling for one or more jobs of variable sizes, wherein one or more jobs are examined to decide on resource assignment. The one or more jobs require a finite amount of memory and one or more threads for execution in a sequential manner.
The method dynamically identifies one or more jobs for execution and how much memory and threads to be assigned to each job with a goal to maximize system throughput and provide smooth output rate. Thus, the method looks ahead at multiple
jobs waiting for assignment and tentatively decides on jobs to be assigned. With each pass, assignment parameters such as memory and threads are refined for each job. The following is a C++ pseudo code for the look-ahead scheduling method:
totalMemory = determine total amount of memory, including assigned and unassigned
totalThreads = determine total number of threads, including assigned and unassigned
freeMemory = determine amount of unassigned memory
freeThreads = determine number of unassigned threads
assignedMemoryThisCall = 0;
// Pass 1: consider memory requirement. Jobs are kept in an ordered list and traversed in order.
For each job to be assigned
job.memoryRequirement = compute memory requirement from job size
// Compute thread requirement to be proportional of job size.
job.threadRequirement = totalThreads * job.memoryRequirement / totalMemory
// Oversize jobs will be split. Allocate generous amount of resource (3/4 of total)
// for splitting so that it doesn't block data flow for long. After updating memory and
// thread requirement, the job is scheduled as usual (scheduled when required
// resources are available, otherwise wait). The assigned threads will split the job
// into multiple sub jobs and replace the original job in job list with the sub jobs.
// Sub jobs then go through normal scheduling. They are scheduled for processing
// or even further split. The system does not differentiate original job vs. sub job.
if (job.memoryRequirement > totalMemory)
job.state = "need splitting"
job.memoryRequirement = (3/4) * totalMemory
job.threadRequirement = (3/4) * totalThreads
Ahead Multi - -Pass Scheduling For Jobs Of Variable Sizes
Pass Scheduling For Jobs Of Variable Sizes
Page 02 of 4
job.state = "normal processing"
if (job.memoryRequirement > freeMemory)
break out of loop
if (job.threadRequrement > freeThreads)
break out of loop
// Tentatively assign resources to this job
job.memoryAssigned = job.memoryRequirement;
job.threadAssigned = job.threadRequirement;
freeMemory -= job.memoryRequirement;
freeThreads -= job.threadRequirement;
assignedMemoryThisCall += job.memoryRequirement;
// 2nd pass: Distribute extra threads among assigned jobs. There are
// two causes of extra threads: 1. Remaining memory or threads is not enough
// to fit the next job. 2. Rounding e...