シングルスレッドによるパフォーマンスの改善

Question

私はクラスの割り当てをツリー検索しています。私はツリー検索の部分を理解していますが、余分な時間があるので、スレッドを追加することでスピードアップしたかったのです。

最終的な作業は、制約、クラス、タイムスロットのセットを取り込み、すべてのクラスを含むスケジュールを出力し、すべての制約を満たすことです。空または部分的な割り当てが入ると、完全なクラス割り当てが出ます。

検索はツリーのように設計されており、入力はルートノードです。 div(n)は次のようになります。ノードnの場合、未使用のクラスCを見つけて、未使用の各スロットSについて、Cを持つ子ノードをSにします。検索を効率化するために、品質をランク付けする検索コントロールを使用します最良の候補が最初に選択され、悪い候補の時間を無駄にすることはありません。

ノードは検索コントロールを使用してcompareTo()で実装されたComparableを実装しています。優先待ち行列を使用して処理待ちのノードを格納するので、「最良の」ノードは常に次の行にあります。ワーカーはノードを削除し、div()を適用し、子を優先度キューに追加します。

私の最初のアプローチは、共有優先度キュー、特にPriorityBlockingQueueを使用していました。キューはほとんど常にブロックされていたので、パフォーマンスは非常に厳しいものでした。

バックグラウンドワーカーとConcurrentLinkedQueueバッファを追加して修正しようとしました。ワーカーはバッファに追加し、ワーカーは定期的にバッファから優先順位キューに要素を移動します。これはどちらもうまくいかなかった。

私が見つけた最高のパフォーマンスは、それぞれのワーカーに自分の優先キューを与えることです。私はこれが得られるほど良いと思っています。スレッドは他の人の行動につながっていないからです。この設定では、4C/8Tマシンでは、〜2.5のスピードアップが得られます。ここのボトルネックは、これらすべてのノードのメモリの割り当てだと思いますが、ここで間違っている可能性があります。サーチャーから

：スケジュールから

private PriorityQueue<Schedule> workQueue; 
private static volatile boolean shutdownSignal = false; 
private Schedule best; 

public Searcher(List<Schedule> instances) { 
    workQueue = new PriorityQueue<>(instances); 
} 

public static void stop() { 
    shutdownSignal = true; 
} 

/** 
* Run the search control starting with the first node in the workQueue 
*/ 
@Override 
public void run() { 

    while (!shutdownSignal) { 
     try { 
      Schedule next = workQueue.remove(); 
      List<Schedule> children = next.div(checkBest); 
      workQueue.addAll(children); 
     } catch (Exception e) { 
      //TODO: handle exception 
     } 
    } 
    //For testing 
    System.out.println("Shutting down: " + workQueue.size()); 
} 

//passing a function as a parameter 
Consumer<Schedule> checkBest = new Consumer<Schedule>() { 
    public void accept(Schedule sched) { 
     if (best == null || sched.betterThan(best)) { 
      best = sched; 
      Model.checkBest.accept(sched); 
     } 
    } 
}; 

：

public List<Schedule> div(Consumer<Schedule> completion) { 
    List<Schedule> n = new ArrayList<>(); 

    int selected = 0; 
    List<Slot> available = Model.getSlots(); 
    List<Slot> allocated = getAssigned(); 

    while (allocated.get(selected) != null) { 
     selected++; 
    } // find first available slot to fill. 
     // Iterate through all available slots 
    for (Slot t : available) { 
     //Prepare a fresh copy 
     List<Slot> newAssignment = new ArrayList<>(allocated.size()); 
     Collections.copy(newAssignment, allocated); 

     //assign the course to the timeslot 
     newAssignment.set(selected, t); 
     Schedule next = new Schedule(this, newAssignment); 
     n.add(next); 
    } 

    /** 
    * Filter out nodes which violate the hard constraints and which are solved, 
    * and check if they are the best in a calling thread 
    */ 

    List<Schedule> unsolvedNodes = new ArrayList<>(); 

    for (Schedule schedule: n) { 
     if (schedule.constr() && !schedule.solved()){ 
      unsolvedNodes.add(schedule); 
      completion.accept(schedule); 
     } 
    } 
    return unsolvedNodes; 
} 

Answer 1

私は、フレームワークは、あなたの仕事のための適切なツールであるフォークジョインと言うでしょう。 ResursiveTaskまたはResursiveActionからあなたの仕事を拡張し、それをForkJoinPoolに提出する必要があります。ここに擬似コードサンプルがあります。また、shutdownフラグはvolatileである必要があります。

public class Task extends RecursiveAction { 
    private final Node<Integer> node; 

    public Task(Node<Integer> node) { 
     this.node = node; 
    } 

    @Override 
    protected void compute() { 
     // check result and stop recursion if needed 

     List<Task> subTasks = new ArrayList<>(); 

     List<Node<Integer>> nodes = div(this.node); 
     for (Node<Integer> node : nodes) { 
     Task task = new Task(node); 
     task.fork(); 
     subTasks.add(task); 
     } 

     for(Task task : subTasks) { 
     task.join(); 
     } 
    } 

    public static void main(String[] args) { 
     Node root = getRootNode(); 
     new ForkJoinPool().invoke(new Task(root)); 
    }