Browse Prior Art Database

Look-Ahead Multi-Pass Scheduling For Jobs Of Variable Sizes Disclosure Number: IPCOM000242039D
Publication Date: 2015-Jun-15
Document File: 4 page(s) / 31K

Publishing Venue

The 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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 42% of the total text.

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:

schedule() {

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

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...