algorithm for binary two-dimensional rectangular partitioning

Question

We are doing a scheduler for heterogeneous computing.

The tasks can be identified by their deadline and their data-rate and can be regarded as a two dimensional graph. See image:

The rectangle identifies tasks to be scheduled on the GPU, and outside tasks to be scheduled on the CPU.

The problem is we want to efficiently identify the parameters for creating the best rectangle. I.e. the rectangle containing most tasks. A function determining whether or not a dot can be added to the current rectangle can be assumed present.

There can be up to 20.000 (dots) tasks, and the axis can be arbitrary long

Are there any known algorithms / data structures solving this problem?

Answer 1

With the given information, you could do the following:

Start by adding the dot which is closest to the center of gravity of all the dots.

If n dots are already added, select as n+1st dot, the dot which is closest to the current rectangle. Ask your given function, whether this dot can be added.

If so, inflate the rectangle so it contains this dot. Assuming all dots have unique x and y coordinates, it is always possible to add just a single dot to the rectangle.

If not, terminate.

If this is not what you want, give more information.

Answer 2

If you mean a hierarchical cluster you can use a spatial index or a space-filling-curve to subdivide the 2d graph in quadrants. A quadrant can represent a thread or a core. Then you need to sort the dots with this function and check for the quadrant with the most dots.