System And Method For Maximizing Data Processing Throughput Via Application Load Adaptive Scheduling And Content Switching

• US 20120079494A1
• Filed: 12/30/2010
• Published: 03/29/2012
• Est. Priority Date: 09/27/2010
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Granted Patent: US 8,769,543 B2
• Time in Patent Office: Days
• 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 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 CPU,

wherein the producing of the schedule by the scheduler is done at least in part based on indicators, by at least some among the set of software applications, expressing whether a given software application is ready to use one or more CPU cycles on the upcoming allocation period.

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

3. The system of claim 1, wherein the indicators are software variables mapped to device registers within a memory space of the CPU, with said device registers being accessible by the scheduler.

4. The system of claim 1, wherein at least one of the indicators comprise at least one of:

(i) a binary variable expressing whether its associated software application is currently ready to execute on the CPU, and (ii) a number indicating a quantity of CPU cycles that its associated software application is currently ready to consume.

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

6. 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 CPU for successive CPU cycles of the allocation periods.

7. An application load adaptive digital data processing method, comprising steps of:

by at least one application among a set of software applications configured to share a given processing hardware, maintaining in a hardware device register a ready-to-execute status indicator to be used in determining an optimal allocation of the processing hardware capacity among said set of applications;

by a scheduler hardware logic, periodically determining the optimal allocation of the shared processing hardware capacity among said set of applications at least in part based on the ready-to-execute status indicators of one or more of the set of software applications configured to share the given processing hardware; and

by the shared processing hardware, processing of instructions and data of the set of software applications to produce a set of data processing outputs, with sequences of applications for processing by said shared processing hardware being based at least in part on the determining of the optimal allocation of the processing hardware capacity by the scheduler hardware logic.

8. The method of claim 7, wherein the determining the optimal allocation of the shared processing hardware capacity is done with an objective of maximizing a processing throughput of said shared processing hardware.

9. The method of claim 7, wherein the determining the optimal allocation of the shared processing hardware capacity is done in a manner that maximizes a processing throughput of said shared processing hardware, while ensuring that all applications among said set of software applications get no less than their entitled time-share of the processing hardware capacity whenever they are able to offer at least that level of processing load to the shared processing hardware.

10. The method of claim 7, wherein the determining the optimal allocation of the shared processing hardware capacity is done with an objective of maximizing a processing throughput of one or more applications among the set of software applications sharing said processing hardware taking into consideration a prioritization among said set of applications.

11. The method of claim 7, wherein the step of determining produces a digital hardware logic look-up-table storing sequences assigning units of processing time on the shared hardware among the set of software applications sharing the given processing hardware.

12. The method of claim 7, wherein at least one of the ready-to-execute status indicators comprise at least one of:

(i) a binary variable expressing whether its associated software application is currently ready to execute on the shared processing hardware, and (ii) a number indicating a quantity of processing cycles that its associated software application is currently ready to consume on the shared processing hardware.

13. The method of claim 7, wherein the sequences of applications for processing by the shared processing hardware are stored in a digital hardware logic look-up-table (LUT), with application identifiers in stored successive addresses of the LUT directing multiplexing of application processing contexts for the shared processing hardware.

14. An algorithm 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 algorithm comprising steps of:

monitoring ready-to-execute indicators of one or more applications among a set of software applications, with said indicators expressing at least one of the following;

(a) whether a given software application is currently ready to execute on the CPU, and (b) how many CPU cycles the given application is a 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 CPU at least in part based on values of the ready-to-execute indicators of one or more of said set of applications; and

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

15. The algorithm of claim 14, wherein the step of allocating the CPU cycles for an allocation period results in minimizing a greatest amount of unmet demands for CPU cycles among the set of software applications.

16. The algorithm of claim 14, wherein the step of allocating the CPU cycles for an allocation period is done in a manner that minimizes a greatest amount of unmet demands among the set of software applications, while ensuring that any given application gets at least its entitled share of CPU cycles on such allocation periods on which it so demanded.

17. The algorithm of claim 16, wherein the entitled share of CPU cycles for a given software application on an allocation period is one of:

i) even division of amount of the CPU cycles on the allocation period among the set of applications, or ii) a contract based amount of CPU cycles, or iii) an amount of CPU cycles based on amounts of CPU cycles demanded on the allocation period by applications among said set of applications and the respective priorities of said applications.

18. The algorithm of claim 14, wherein the step of allocating the 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.

19. The algorithm of claim 14, wherein the step of allocating the 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.

20. The algorithm of claim 14, wherein the step of allocating the 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 CPU for successive CPU cycles of the given allocation period.