System and method for maximizing data processing throughput via application load adaptive scheduling and context switching

• US 8,769,543 B2
• Filed: 12/30/2010
• Issued: 07/01/2014
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US12/982,826
• Publication Number:
  US 20120079494A1
• Time in Patent Office: 1,279 Days
• Field of Search: 718 1-108
• US Class Current: 718/104
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The invention enables dynamic, software application load adaptive optimization of data processing capacity allocation on a shared processing hardware among a set of application software programs sharing said hardware. The invented techniques allow multiple application software programs to execute in parallel on a shared CPU, with application ready-to-execute status adaptive scheduling of CPU cycles and context switching between applications done in hardware logic, without a need for system software involvement. The invented data processing system hardware dynamically optimizes allocation of its processing timeslots among a number of concurrently running processing software applications, in a manner adaptive to realtime processing loads of the applications, without using the CPU capacity for any non-user overhead tasks. The invention thereby achieves continuously maximized data processing throughput for variable-load processing applications, while ensuring that any given application gets at least its entitled share of the processing system capacity whenever so demanded.

Claims

1. An application load adaptive digital data processing system, comprising:

a time shared central processing unit (CPU) for processing data and instructions from input data arrays of the system and storing results in output data arrays of the system; and

a scheduler for periodically, once in a set of CPU cycles referred to as an allocation period, producing a schedule that assigns a set of CPU cycles on an upcoming allocation period among a set of software applications sharing the time shared CPU,

wherein the producing of the schedule by the scheduler is done at least in part based on ready-to-execute indicators by at least some among the set of software applications expressing how many CPU cycles on the time shared CPU a given software application is ready to use on the upcoming allocation period,

wherein at least one of the ready-to-execute indicators comprises a number indicating a quantity of CPU cycles that its associated software application is currently ready to consume,

wherein the at least one of the ready-to-execute indicators comprises a software variable mapped to a device register within a memory space of the time shared CPU, with said device register being accessible by the scheduler,

wherein the time shared CPU processes data and instructions of at least some of the set of software applications on the upcoming allocation period with the CPU cycles assigned among the applications according to the schedule produced for that allocation period by the scheduler, and

wherein said CPU cycle is one of;

individual CPU clock cycle, or individual CPU instruction cycle.

2. The system of claim 1, wherein the scheduler is implemented in hardware logic.

3. The system of claim 1, wherein the input and output data arrays comprise at least one of:

i) CPU accessible memories, and ii) CPU accessible input and output communication ports.

4. The system of claim 1, wherein the schedule comprises a digital look-up-table (LUT) within hardware logic of the system, with said LUT storing sequences of application identifiers for CPU allocation periods, and with the application identifiers in successive addresses of the LUT directing multiplexing of application processing contexts for the time shared CPU for successive CPU cycles of the allocation periods.

5. A method for allocating, by a scheduler implemented in digital hardware logic, a processing capacity of a time shared CPU among a set of software applications, the method comprising steps of:

monitoring ready-to-execute indicators of one or more applications among a set of software applications, with said ready-to-execute indicators expressing how many CPU cycles on the time shared CPU the given application is currently able to consume;

once in a set of CPU cycles referred to as an allocation period, allocating a set of CPU cycles for an upcoming allocation period among said set of software applications sharing the time shared CPU at least in part based on values of the ready-to-execute indicators of one or more of said set of applications;

controlling a time sharing of the time shared CPU among said set of software applications according to the allocating of the CPU cycles by the scheduler,

wherein at least one of the ready-to-execute indicators comprises a number indicating a quantity of CPU cycles that its associated software application is currently ready to consume,

wherein the at least one of the ready-to-execute indicators comprises a software variable mapped to a device register within a memory space of the time shared CPU, with said device register being accessible by the scheduler, and

wherein said CPU cycle is one of;

individual CPU clock cycle, or individual CPU instruction cycle.

6. The method of claim 5, wherein the step of allocating the time shared CPU cycles for at least some of the allocation periods is done so that (i) first, any actually materialized CPU cycle demands by any applications up to their entitled share CPU capacity are met, and (ii) following that, any remaining CPU cycles are assigned in an even manner among the applications whose demand for CPU cycles had not been met by the amount of CPU cycles so far allocated to them.

7. The method of claim 5, wherein the step of allocating the time shared CPU cycles for at least some of the allocation periods is done so that (i) first, any actually materialized CPU cycle demands by any applications, up to their entitled share CPU capacity, are met, and (ii) following that, any remaining CPU cycles are assigned in an even manner among all the applications.

8. The method of claim 5, wherein the step of allocating the time shared CPU cycles among the set of software applications produces sequences of application identifiers stored in a hardware logic digital look-up-table (LUT), with the application identifiers stored in successive addresses of the LUT for a given allocation period directing multiplexing of application processing contexts for the time shared CPU for successive CPU cycles of the given allocation period.