ヘテロジニアスコンピューティングのスケジューラーを実行しています。
タスクは、期限とデータレートによって識別でき、2次元グラフと見なすことができます。画像を参照してください：
長方形は、GPUでスケジュールされるタスクと、CPUでスケジュールされる外部タスクを識別します。
問題は、最適な長方形を作成するためのパラメータを効率的に特定したいということです。つまり、ほとんどのタスクを含む長方形です。現在の長方形にドットを追加できるかどうかを判断する関数が存在すると見なすことができます。
最大20.000（ドット）のタスクがあり、軸は任意の長さにすることができます
この問題を解決する既知のアルゴリズム/データ構造はありますか？
階層的クラスターを意味する場合は、空間インデックスまたは空間充填曲線を使用して、2次元グラフを象限に細分化できます。象限は、スレッドまたはコアを表すことができます。次に、この関数を使用してドットを並べ替え、ドットが最も多い象限を確認する必要があります。
与えられた情報を使用して、次のことを行うことができます。
すべてのドットの重心に最も近いドットを追加することから始めます。
すでにn個のドットが追加されている場合は、現在の長方形に最も近いドットをn+1番目のドットとして選択します。このドットを追加できるかどうか、指定された関数に問い合わせてください。
その場合は、このドットが含まれるように長方形を膨らませます。すべてのドットが一意のx座標とy座標を持っていると仮定すると、長方形に1つのドットだけを追加することは常に可能です。
そうでない場合は、終了します。
これが希望どおりでない場合は、詳細情報を提供してください。