二元二维矩形划分算法
我们正在做一个异构计算的调度器。
任务可以通过它们的截止日期和数据速率来识别，并且可以被视为二维图。请参见图像：
矩形标识要在 GPU 上调度的任务以及要在 GPU 上调度的外部任务中央处理器。
问题是我们想要有效地识别用于创建最佳矩形的参数。即包含大多数任务的矩形。可以假设存在确定是否可以将点添加到当前矩形的函数。
最多可以有 20.000 个（点）任务，并且轴可以是任意长
有任何已知的算法/数据结构可以解决这个问题吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
根据给定的信息，您可以执行以下操作：
首先添加距离所有点的重心最近的点。
如果已经添加了n个点，则选择距离当前矩形最近的点作为第n+1个点。询问你给定的函数，是否可以添加这个点。
如果是这样，请膨胀矩形，使其包含该点。假设所有点都有唯一的 x 和 y 坐标，则始终可以仅向矩形添加一个点。
如果不是，则终止。
如果这不是您想要的，请提供更多信息。
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.
如果您指的是分层集群，您可以使用空间索引或空间填充曲线将二维图细分为象限。象限可以代表一个线程或一个核心。然后，您需要使用此功能对点进行排序，并检查点最多的象限。
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.