Prioritizing instances of programs for execution based on input data availability

• US RE47,677 E1
• Filed: 07/26/2018
• Issued: 10/29/2019
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: ThroughPuter, Inc.
• Original Assignee: ThroughPuter, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): Banankhah, Majid A
• Application Number:
  US16/046,718
• Time in Patent Office: 460 Days
• Field of Search: 718105
• CPC Class Codes: N/A

Abstract

Systems and methods provide an extensible, multi-stage, realtime application program processing load adaptive, manycore data processing architecture shared dynamically among instances of parallelized and pipelined application software programs, according to processing load variations of said programs and their tasks and instances, as well as contractual policies. The invented techniques provide, at the same time, both application software development productivity, through presenting for software a simple, virtual static view of the actually dynamically allocated and assigned processing hardware resources, together with high program runtime performance, through scalable pipelined and parallelized program execution with minimized overhead, as well as high resource efficiency, through adaptively optimized processing resource allocation.

Claims

1. A method for periodically arranging a set of N executables of a given software program in an execution priority order, where N is a positive integer, the method comprising:

buffering input data at an array of executable specific input port buffers, with said array including up to M buffers for each of the N executables, where M is a positive integer, and wherein a buffer within said array buffers such input data that is directed to the executable associated with the buffer;

calculating numbers of non-empty buffers associated with each of the executables;

ranking the executables in their descending execution priority order at least in part according to their descending numbers of non-empty buffers through populating a binary matrix of at least M rows by N columns, wherein there is a column associated with each of the N executables, and wherein there is a row corresponding to each of the M possible positive numbers of non-empty buffers per an executable, such that a bit at a given column and a chosen row of the matrix indicates whether the executable associated with the given column has non-empty buffers corresponding to the chosen row; and

executing the executables on one or more processing cores of a processor according to the ranking.

2. The method of claim 1 wherein one of the executable specific input port buffers is statically dedicated to its associated executable.

3. The method of claim 1 wherein an executable among said set is one of the following:

a task, an instance, or an instance of a task of the program.

4. The method of claim 1 implemented by hardware logic that operates without software involvement.

5. The method of claim 1, wherein the populating of the binary matrix involves forming, for each given executable, a 1^st phase bit vector having M bits, and wherein a bit at index x of said vector indicates whether the given executable has exactly x non-empty buffers, with x being an integer between 0 and M.

6. The method of claim 5, wherein the populating of the binary matrix involves forming, from bits at equal index values of the 1^st phase bit vectors of each of the executables, a row of M 2^nd phase bit vectors, so that a bit at index y of the 2^nd phase bit vector at index x of said row indicates whether an executable with ID number y within the set has exactly x non-empty buffers, wherein y is an integer from 0 to a maximum number of the executables less 1.

7. The method of claim 6, wherein the ranking further involves the following sub-steps:

resetting the present priority order index to a value representing a greatest execution priority; and

scanning the row of the 2^nd phase bit vectors for active-state bits, one 2^nd phase bit vector at a time, starting from row index M while decrementing the row index after reaching bit index 0 of any given 2^nd phase bit vector, and based upon encountering an active-state bit;

i) associating the executable with ID equal to the index of the active-state bit within its 2^nd phase bit vector with the present priority order index and ii) changing the present priority order index to a next lower level of execution priority.

8. A system for prioritizing pieces of software programs, said pieces referred to as a set of N executables, where N is a positive integer, for execution, the system comprising:

a processor;

a subsystem for buffering input data at an array of executable specific input port buffers, wherein there is a preset number, M, a positive integer, of the executable specific input port buffers per a given one of the executables, and wherein a given buffer within said array buffers such input data that is directed to the executable associated with the given buffer;

a subsystem for determining, from said array of buffers, respective numbers of non-empty buffers associated with each of the executables;

a subsystem for ranking the executables in their descending execution priority order at least in part according to their determined descending numbers of non-empty buffers through populating a binary matrix of at least M rows by N columns, wherein there is a column associated with each of the N executables, and wherein there is a row corresponding to each of the M possible positive numbers of non-empty buffers per an executable, such that a bit at a given column and a chosen row of the matrix indicates whether the executable associated with the given column has non-empty buffers corresponding to the chosen row; and

one or more processing cores of the processor on which the executables are executed according to the ranked execution priority order.

9. The system of claim 8, wherein at least one of the executable specific input port buffers is a hardware element that is dedicated for its associated one of the executables.

10. The system of claim 8, wherein an executable among said set is one of the following:

a program, a thread, a task or an instance of a program, or an instance of a task of a program.

11. The system of claim 8 implemented by hardware logic that operates without software involvement.