24

ファイルから読み取り、何らかの処理を行い、ファイルに書き込むタスクがあります。これらのタスクは、依存関係に基づいてスケジュールされます。また、タスクは並列で実行できるため、依存するタスクを順次実行し、可能な限り並列で実行するようにアルゴリズムを最適化する必要があります。

例えば：

  1. A -> B
  2. A -> C
  3. B -> D
  4. E -> F

したがって、これを実行する 1 つの方法は、1、2、および 4 を並行して実行することです。続いて3。

別の方法として、1 を実行してから 2、3、4 を並行して実行することもできます。

もう 1 つは、1 と 3 を直列に、2 と 4 を並列に実行できます。

何か案は？

4

5 に答える 5

14

各タスク (例: A,B,...) を有向非巡回グラフのノードとし、 に基づいてノード間のアークを定義します1,2,...。

http://en.wikipedia.org/wiki/Topological_sorting

次に、グラフをトポロジー的に並べ替えることができます (またはBFSのような検索ベースの方法を使用します)。あなたの例ではC<-A->B->D、E->F&AのE深さは 0 であり、最初に実行する必要があります。F次に、 を実行し、その後にBをC並行して実行できますD。

また、PERTを見てください。

アップデート：

Bよりも優先度が高いかどうかをどのように知ることができますかF?

これは、順序付けを見つけるために使用されるトポロジカル ソートの背後にある直感です。

最初にルート (着信エッジなし) ノードを見つけます (DAG に存在する必要があるため)。あなたの場合、それはA&Eです。これにより、完了する必要があるジョブの最初のラウンドが解決されます。次に、ルート ノードの子 ( B、CおよびF) を完了する必要があります。これは、グラフをクエリすることで簡単に取得できます。このプロセスは、ノード (ジョブ) がなくなる (終了する) まで繰り返されます。

于 2013-08-19T13:25:45.753 に答える
9

アイテムとアイテムが依存するアイテムとの間のマッピングが与えられると、トポロジカル ソートはアイテムが依存するアイテムの前にアイテムがないようにアイテムを並べ替えます。

この Rosetta コード タスクにはPythonのソリューションがあり、並列処理できる項目を知ることができます。

あなたの入力を考えると、コードは次のようになります。

try:
    from functools import reduce
except:
    pass

data = { # From: http://stackoverflow.com/questions/18314250/optimized-algorithm-to-schedule-tasks-with-dependency
    # This   <-   This  (Reverse of how shown in question)
    'B':         set(['A']),
    'C':         set(['A']),
    'D':         set(['B']),
    'F':         set(['E']),
    }

def toposort2(data):
    for k, v in data.items():
        v.discard(k) # Ignore self dependencies
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
    data.update({item:set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item,dep in data.items() if not dep)
        if not ordered:
            break
        yield ' '.join(sorted(ordered))
        data = {item: (dep - ordered) for item,dep in data.items()
                if item not in ordered}
    assert not data, "A cyclic dependency exists amongst %r" % data

print ('\n'.join( toposort2(data) ))

次に、次の出力が生成されます。

A E
B C F
D

出力の 1 行の項目は、任意の下位順序で処理することも、実際には並行して処理することもできます。依存関係を維持するために、上位行のすべての項目が次の行の項目の前に処理される限り。

于 2013-08-20T05:19:06.230 に答える
2

あなたのタスクは、（できれば）サイクルのない有向グラフです。

I にはsourcesandが含まれていますwells(ソースは依存しない (インバウンド エッジがない) タスクであり、ウェルはタスクをロック解除しない (アウトバウンド エッジがない) タスクです)。

簡単な解決策は、タスクの有用性に基づいてタスクに優先順位を付けることです ( U.

通常、ウェルから開始すると、それらは有用性がありU = 1ます。これは、それらを終了させたいためです。

L 現在評価されているノードのリストにすべての井戸の先行者を入れます。

次に、 の各ノードを取得すると、その値は、そのノードに依存するノードの値の合計 + 1 になります。現在のノードのすべての親をLリストUに入れ ます。UL

すべてのノードが処理されるまでループします。

次に、開始できて最大のU価値を持つタスクを開始します。これは、最大数のタスクのロックを解除するタスクであるためです。

あなたの例では、

U(C) = U(D) = U(F) = 1
U(B) = U(E) = 2
U(A) = 4

つまり、可能であれば最初に A を E で開始し、次に B と C (可能であれば)、次に D と F を開始します。

于 2013-08-19T13:28:41.223 に答える
1

まず、タスクのトポロジー順序を生成します。この段階でサイクルを確認します。その後、最大のアンチチェーンを調べることで並列処理を利用できます。大まかに言えば、これらは要素間に依存関係のないタスク セットです。

理論的な観点から、このホワイト ペーパーではこのトピックについて説明します。

于 2013-08-19T13:39:34.683 に答える
0

問題のシリアル/パラレルの側面を考慮しなくても、このコードは少なくとも全体的なシリアル ソリューションを決定できます。

def order_tasks(num_tasks, task_pair_list):
    task_deps= []
    #initialize the list
    for i in range(0, num_tasks):
        task_deps[i] = {}

    #store the dependencies
    for pair in task_pair_list:
        task = pair.task
        dep = pair.dependency

        task_deps[task].update({dep:1})

    #loop through list to determine order
    while(len(task_pair_list) > 0):
        delete_task = None

        #find a task with no dependencies
        for task in task_deps:
            if len(task_deps[task]) == 0:
                delete_task = task
                print task
                task_deps.pop(task)
                break

        if delete_task == None:
            return -1

        #check each task's hash of dependencies for delete_task
        for task in task_deps:
            if delete_key in task_deps[task]:
                del task_deps[task][delete_key]

    return 0

完全に満たされた依存関係をチェックするループを更新して、リスト全体をループし、依存関係がなくなったタスクを同時に実行/削除すると、平行。

于 2014-12-22T23:00:19.247 に答える