Maximizing Throughput of Multi-user Parallel Data Processing Systems

Abstract

The invention provides systems and methods for maximizing revenue generating throughput of a multi-user parallel data processing platform across a set of users of the service provided with the platform. The invented techniques, for any given user contract among the contracts supported by the platform, and on any given billing assessment period, determine a level of a demand for the capacity of the platform associated with the given contract that is met by a level of access to the capacity of the platform allocated to the given contract, and assess billables for the given contract at least in part based on such met demand and a level of assured access to the capacity of the platform associated with the given contract, as well as billing rates, applicable for the given billing assessment period, for the met demand and the level of assured access associated with the given contract.

1 - 25 . (canceled) 
     
     
         26 . A system for computing resource management, the system comprising:
 a hardware logic subsystem configured to periodically, once for each successive core allocation period (CAP), execute an algorithm allocating an array of processing cores among a set of software programs, said subsystem comprising:   (i) a piece of logic configured to carry out a first round of the algorithm, by which round a subset of the cores are allocated among the programs so that any actually materialized demands for the cores by each of the programs up to their respective entitled shares of the cores are met;   (ii) a piece of logic configured to carry out a second round of the algorithm, by which round any of the cores that remain unallocated after the first round are allocated among the programs whose materialized demands for the cores had not been met by amounts of the cores so far allocated to them by the present invocation of the algorithm; and   (iii) a piece of logic configured to carry out a third round of the algorithm, by which round any of the cores that remain unallocated after the second round are allocated among the programs,   wherein the materialized demand for the cores by a given one of the programs is expressed as a number of schedulable tasks that the given program has ready for execution for a CAP following a present invocation of the algorithm.   
     
     
         27 . The system of  claim 26  further comprising:
 a hardware logic subsystem configured to assign individual programs of the set to individual cores of the array in a manner that assigns each such instance of the programs, which was selected for execution on the array of cores on consecutive CAPs, to same one of the cores for execution on each of such consecutive CAPs. 
 
     
     
         28 . The system of  claim 26 , wherein the number of schedulable tasks that the given program has ready for execution for the CAP following the present invocation of the algorithm is formed independently of (1) the respective numbers for other programs of the set, (2) the other programs' utilizations of any cores allocated to them, and (3) utilization of the cores across the array. 
     
     
         29 . The system of  claim 26 , wherein, on at least some invocations of the algorithm, the subset of the cores allocated by the first round comprises zero cores, whereas, on at least some of the other invocations of the algorithm, the subset of the cores allocated by the first round comprises at least one, and up to all of the, cores. 
     
     
         30 . A method for allocating an array of processing cores among a set of software programs for successive core allocation periods (CAPs), the method comprising steps of:
 (i) initially, a subset of the cores are allocated among the programs so that any actually materialized demands for the cores by each of the programs up to their respective entitled shares of the cores are met;   (ii) following step (i), any of the cores that remain unallocated are allocated among the programs whose materialized demands for the cores had not been met by amounts of the cores so far allocated to them by the present exercising of the method; and   (iii) following step (ii), any of the cores that remain unallocated are allocated among the programs,
 wherein the materialized demand for the cores by a given one of the programs corresponds to a number of schedulable tasks that the given program has ready for execution for the CAP following a present exercising of the method. 
   
     
     
         31 . The method of  claim 30 , wherein, wherein the number of schedulable tasks that the given program has ready for execution for the CAP following the present exercising of the method is formed (1) independently of the respective numbers for other programs of the set, (2) irrespective of the other programs' utilizations of any cores allocated to them, and (3) so that said number, for at least some of the CAPs, exceeds the number of the cores allocated to the given program for a CAP preceding the present exercising of the method. 
     
     
         32 . The method of  claim 30 , wherein, for such occasions of exercising of the method when there is no materialized demand for the cores by a given one of the programs, the subset of the cores allocated by first round for that given program comprises zero cores. 
     
     
         33 . The method of  claim 30 , wherein the step (iii) allocates the remaining unallocated cores so that any programs with no existing allocated cores are prioritized in getting cores allocated. 
     
     
         34 . The method of  claim 30 , wherein at least one of steps (ii) and (iii) is exercised by iterating through the programs while starting with a revolving program within said set on successive executions of the method. 
     
     
         35 . The method of  claim 30 , wherein one of the schedulable tasks of the given program is: a task, a process, a thread or a function of that given program. 
     
     
         36 . An application program load adaptive data processing system comprising:
 an array of processing cores for processing instructions and data of a set of software programs configured to share the system;   a placer for repeatedly, once for each successive Core Allocation Period (CAP), assigning individual cores of the array to individual programs among said set; and   a processing core ID indexed digital hardware logic look-up-table for storing program to processing core assignment information,   wherein the assigning by the placer (a) is done at least in part based on capacity demand indicators by at least some among the set of programs, with such an indicator by a given program expressing a number of cores of the array that the given program is demanding for a succeeding CAP, and (b) results in storing, in the processing core ID indexed digital hardware logic look-up-table, identifiers indicating which program among the set a given core among the array was assigned to.   
     
     
         37 . The system of  claim 36 , wherein the number of cores of the array that the given program is demanding for the succeeding CAP:
 (i) is formed: (1) independently of the respective numbers for other programs of the set, (2) irrespective of the other programs' utilizations of any cores allocated to them;   (ii) for at least some of the CAPs, exceeds a number of the cores assigned to the program prior to said succeeding CAP; and   (ii) equals a number of cores that the program is able to execute on in parallel on said succeeding CAP.   
     
     
         38 . The system of  claim 36 , wherein the number of cores of the array that the given program is demanding for the succeeding CAP corresponds to a number of schedulable tasks that the given program has ready for execution for that CAP, and wherein, for at least some of the CAPs, said number of schedulable tasks exceeds a number of the cores assigned to the program on the CAP preceding said succeeding CAP. 
     
     
         39 . The system of  claim 36 , wherein the placer comprises logic that, after receiving a new allocation of the cores among the programs to replace a present allocation of the core slots among the programs, maps instances of the programs to the array of cores through logic subsystems configured to:
 (i) identify the following:
 a) a set of instances of the programs from the new allocation that were not included in the present allocation, with this set referred to as activating program instances; 
 b) a set of instances of the programs from the present allocation that are not in the new allocation, with this set referred to as deactivating program instances; and 
 c) a set of cores among the array that were assigned to the set of deactivating program instances in the present allocation, with this set referred to as available cores; and 
   ii) assign the array of cores among the instances of the programs by placing each of the activating program instances to one of the available cores, while keeping each given such program instance, which was included both in the present and the new allocation, assigned for the CAP corresponding to the new allocation to the same core as the given program instance was assigned on the CAP corresponding to the present allocation.   
     
     
         40 . The system of  claim 36 , wherein at least one of the capacity demand indicators comprises a software variable mapped to a hardware device register accessible by the placer. 
     
     
         41 . The system of  claim 36 , wherein:
 the set of programs are identifiable by program ID numbers from 0 through a total count of the programs configured to share the system less one; and   the assigning by the placer involves storing core allocation information in a program ID indexed digital look-up-table (LUT) within hardware logic of the system, so that at least one given program ID indexed element of the LUT stores a number expressing how many cores of the array are being allocated to a program associated with that given program ID indexed element of the LUT.   
     
     
         42 . The system of  claim 36 , further including logic configured to control, at least in part based on the assigning by the placer, which program among the set will execute on which core among the array. 
     
     
         43 . The system of  claim 36 , wherein:
 the cores of the array are identifiable by core ID numbers from 0 through a total count of the cores of the array less one; and   in the core ID indexed look-up-table (LUT) at least one given core ID indexed element of the LUT stores an identifier of a program assigned to the execute on a core associated with that given core ID indexed element of the LUT.   
     
     
         44 . A method for mapping, by a placer implemented in digital hardware logic, a set of software programs to execute on an array of processing cores of a shared data processing hardware, the method comprising a repeatedly exercised series of steps as follows:
 monitoring capacity demand indicators of one or more programs among the set of programs, with said indicator of a given program expressing a number of tasks that the given program has ready for execution for a succeeding Core Allocation Period (CAP); and   allocating the array of cores among the set of programs for the succeeding CAP at least in part based on said capacity demand indicators for that CAP;   wherein the step of allocating for said succeeding CAP leads to storing, in a processing core ID indexed digital hardware logic look-up-table (LUT), identifiers indicating which program among the set a given core among the array was assigned to for that CAP.   
     
     
         45 . The method of  claim 44 , further comprising: after the step of allocating has produced a new allocation of the cores among the programs to replace a present allocation of the core slots among the programs, placing instances of the programs to the array of cores through sub-steps of:
 (i) identifying the following:
 a) a set of instances of the programs from the new allocation that were not included in the present allocation, with this set referred to as activating program instances; 
 b) a set of instances of the programs from the present allocation that are not in the new allocation, with this set referred to as deactivating program instances; and 
 c) a set of cores among the array that were assigned to the set of deactivating program instances in the present allocation, with this set referred to as available cores; and 
   ii) assigning the array of cores among the instances of the programs by placing each of the activating program instances to one of the available cores, while keeping each such program instance, which was included both in the present and the new allocation, assigned for the CAP corresponding to the new allocation to the same core as it was assigned on the CAP corresponding to the present allocation.   
     
     
         46 . The method of  claim 44 , wherein the number of tasks that the given program has ready for execution for the succeeding CAP is formed: (1) independently of the respective numbers for other programs of the set, and (2) irrespective of the other programs' utilizations of any cores allocated to them. 
     
     
         47 . The method of  claim 44 , wherein the number of tasks that the given program has ready for execution for the succeeding CAP equals a number of cores that the program is able to execute on in parallel on said succeeding CAP, and, for at least some of the CAPs, exceeds a number of the cores assigned to the program prior to said succeeding CAP. 
     
     
         48 . The method of  claim 44 , wherein the step of allocating ensures that any given program gets at least its entitled share of the processing cores following such runs of the method for which it demanded at least such entitled share, wherein the entitled share of processing cores for a given program is one of: i) an even division of amount of the cores within the array of cores, or ii) a contract based amount of cores. 
     
     
         49 . The method of  claim 44 , wherein the program identifiers stored in successive addresses of the LUT direct which of the programs will run on which of the cores on said succeeding CAP. 
     
     
         50 . The method of  claim 44  wherein, as a result of the allocating step, a representation of an allocation of the array of cores among the set of programs is stored in a program ID addressed digital hardware logic LUT, with entries at successive addresses of the program ID addressed LUT expressing a quantity of the processing cores being allocated to a program corresponding to a given address of that LUT.