System allocating links for data packets in an electronic system

Patent metadata

Field	Value
Publication number	US-10402230-B2
Application number	US-201715623105-A
Country	US
Kind code	B2
Filing date	Jun 14, 2017
Priority date	Dec 13, 2013
Publication date	Sep 3, 2019
Grant date	Sep 3, 2019

Abstract

Methods and systems for performing the methods are disclosed. The methods include splitting a large execution load/execution component link generation job, into a number of smaller execution load/execution component link generation jobs, and conditionally subsplitting one or more of the smaller execution load/execution component link generation jobs. The methods also include solving each of the smaller execution load/execution component link generation jobs to generate links between data packets corresponding with execution loads of each smaller execution load/execution component link generation job and data packets corresponding with execution components of each smaller execution load/execution component link generation job.

First claim

What is claimed is:

1. A method of generating links between a plurality of data packets corresponding with execution loads to a plurality of data packets corresponding with execution components, the data packets corresponding with execution loads and the data packets corresponding with execution components being part of a first execution load to execution component link generation job, the method comprising:
calculating an overall metric of the first execution load to execution component link generation job, wherein the overall metric is determined based at least in part on a quantity of execution loads of the first execution load to execution component link generation job and a quantity of execution components of the first execution load to execution component link generation job;
splitting the first execution load to execution component link generation job into a plurality of smaller execution load to execution component link generation jobs, wherein each of the smaller execution load to execution component link generation jobs comprises a plurality of execution loads and execution components wherein each particular smaller execution load to execution component link generation job has a job metric determined based at least in part on the quantity of execution loads of the particular smaller execution load to execution component link generation job and the quantity of execution components of the particular smaller execution load to execution component link generation job, and wherein a difference between the job metric of each of the smaller execution load to execution component link generation jobs and the overall metric of the first execution load to execution component link generation job is less than a metric threshold;
solving each smaller execution load to execution component link generation jobs, whereby links are generated between the data packets corresponding with execution loads of each smaller execution load to execution component link generation job and the data packets corresponding with execution components of each smaller execution load to execution component link generation job; and
communicating the generated links to the corresponding execution components,
wherein the overall metric is an overall density, and wherein the job metric are job densities,
wherein the overall density is the quantity of execution loads of the execution load to execution component link generation job divided by a sum of the execution loads and execution components of the execution load to execution component link generation job, and
wherein a job density of each particular smaller execution load to execution component link generation job is the quantity of execution loads of the particular smaller execution load to execution component link generation job divided by a sum of the execution load and execution components of the particular smaller execution load to execution component link generation job.

2. The method of claim 1 , wherein a physical region corresponding with each particular smaller execution load to execution component link generation job is contiguous.

3. The method of claim 1 , wherein the first execution load to execution component link generation job corresponds with a physical region, and wherein splitting the first execution load to execution component link generation job into a plurality of smaller execution load to execution component link generation jobs comprises:
splitting the physical region of the first execution load to execution component link generation job into a plurality of sections, wherein each section has a physical region and has one or more execution loads and execution components therein, and wherein a sum of execution loads and execution components within each section is less than a quantity threshold; and
selecting one or more of the sections for each smaller execution load to execution component link generation job, wherein each smaller execution load to execution component link generation job comprises the execution loads and execution components of the selected sections.

4. The method of claim 3 , wherein splitting the physical region of the first execution load to execution component link generation job into a plurality of sections comprises:
splitting the physical region of the first execution load to execution component link generation job into four areas, wherein each area has one or more execution loads and execution components therein;
determining the quantity of execution loads and execution components of each particular area;
subsplitting each particular area having a sum of execution loads and execution components greater than the quantity threshold into four sub-areas;
determining the quantity of execution loads and execution components of each particular sub-area;
subsplitting each particular sub-area having a sum of execution loads and execution components greater than the quantity threshold into four additional sub-areas;
determining the quantity of execution loads and execution components of each particular additional sub-area; and
subsplitting each particular additional sub-area having a sum of execution loads and execution components greater than the quantity threshold into four additional sub-areas, until all sub-areas and additional sub-areas have a sum of execution loads and execution components less than or equal to the quantity threshold.

5. The method of claim 4 , wherein the four areas are substantially equal in size.

6. The method of claim 3 , wherein selecting the sections for each smaller execution load to execution component link generation job comprises:
generating an ordered list of sections;
adding a first section from the ordered list to a particular smaller execution load to execution component link generation job;
calculating a job metric for the particular smaller execution load to execution component link generation job;
calculating a difference between the determined job metric of the particular smaller execution load to execution component link generation job and the overall metric of the first execution load to execution component link generation job;
in response to the calculated difference being greater than the metric threshold, adding a next section from the ordered list to the particular smaller execution load to execution component link generation job; and
in response to the calculated difference being less than the metric threshold, generating a next smaller execution load to execution component link generation job.

7. A computer system, comprising:
a processor; and
a memory, comprising instructions, which, when executed by the processor, cause the computer system to perform a method of generating links between a plurality of data packets corresponding with execution loads to a plurality of data packets corresponding with execution components, the data packets corresponding with execution loads and the data packets corresponding with execution components being part of a first execution load to execution component link generation job, the method comprising:
calculating an overall metric of the first execution load to execution component link generation job, wherein the overall metric is determined based at least in part on a quantity of execution loads of the first execution load to execution component link generation job and a quantity of execution components of the first execution load to execution component link generation job;
splitting the first execution load to execution component link generation job into a plurality of smaller execution load to execution component link generation jobs, wherein each of the smaller execution load to execution component link generation jobs comprises a plurality of execution loads and execution components wherein each particular smaller exe

Assignees

• Mitchell Int Inc

Inventors

• Dattaray Basab
• Baierl Scott

Classifications

• G06F9/505 Primary

  considering the load · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F2209/5017

  Task decomposition · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title