FrontPage
&math(y=ax^2+bx+c);

Fundamentals of Dependency Graphs(依存関係グラフ)

Introduction(導入)

依存関係グラフとは ~

サンドウィッチの例
簡単な具体例を見てみることにしましょう。 サンドウィッチを作るときの依存関係グラフ
https://www.xlsoft.com/jp/products/intel/perflib/tbb/43/tbb_ugref/tbb_userguide/Dependence_Graph.htm

このグラフはサンドウィッチを作るという一連のタスクのステップを示しています。
(読者のみなさんの中には、この方法以外でサンドウィッチを作りたいという強いこだわりを持つ方々もいるかもしれませんが、今回はこの方法で、我慢していただきたいと思います。)

一般的なグラフはnode(点)とedge(nodeをつなぐ線)から構成されます。
このdependency graphの場合は、nodeが各ステップごとのタスクを表しており、edgeはそのタスクの依存関係を示しています。

なので、このグラフに従えば、
step1: まず、食パンを二枚用意
step2: 1枚にピーナツバターを塗る、もう一枚にジャムを塗る
step3: ピーナツバターを片付ける、二枚を合わせる、ジャムを片付ける

というステップでサンドウィッチがつくられます。
同じ階層のステップにあるタスクはどちらを先でも構いません。
これを半順序(partially ordered set / poset)と言います。
例えば、step2ではピーナッツバターかジャムのどちらを先に塗っても構いません。 (image:https://www.xlsoft.com/jp/products/intel/perflib/tbb/43/tbb_ugref/index.htm#tbb_userguide/Dependence_Graph.htm)

dependency graphの一般化

単純な依存関係グラフ
https://www.xlsoft.com/jp/products/intel/perflib/tbb/43/tbb_ugref/index.htm#tbb_userguide/Dependence_Graph.htm
下の図は、上記のグラフを一般化した例です。
グラフのトポロジーは同じですが、各ノードにはサンドウィッチを作る手順ではなく簡単な関数が割り当てられています。この半順序で、関数 A はほかの計算が実行を開始する前に完了している必要があります。
関数 B は、C と D が実行を開始する前に完了している必要があり、E は、D と F が実行を開始する前に完了している必要があります。

(image:https://www.xlsoft.com/jp/products/intel/perflib/tbb/43/tbb_ugref/index.htm#tbb_userguide/Dependence_Graph.htm)

Contents

では、実際にコンピュータアーキテクチャの中でdependency graphがどのように働くのか見ていきましょう。
しかし、その前にコンピュータの基礎的な構造をおさらいしておきましょう。

*** コンピュータ内部の基本的な処理~

https://ufcpp.net/study/computer/memory.htmlhttps://yttm-work.jp/hardware/hardware_0001.html
コンピュータの内部では、上図のように、メインメモリとCPU内部の処理とのやりとりによって、様々なプログラムを実現しています。例えば、加算処理であれば、メモリに保存されている数値を計算のためにCPU内部のレジスターと呼ばれる場所に、一時的に保管します。レジスターに保管されている値を元にALU(Arithmetic and Logic Unit)で加算処理を行い、出力を再びれレジスターに保管し、メモリに移動させます。また、メインメモリ内にはプログラムに当たる部分とデータに当たる部分が区別なく格納されています。プログラムに当たる部分はCPUによって順次読み出され実行されます。そのためには今メモリの中のどのアドレスのプログラムを読み出せばいいかを覚えておく必要があります。その役割を果たすのがプログラムカウンタと呼ばれる機構です。プログラムカウンタの詳しい解説は別の章譲るとして、コンピュータ内部ではこのような小規模なタスクを高速に行なっているのです。

dependency graphと算術処理

次のような算術計算をdependency graphで表すことができます。

(3 + 4 )×7

http://web.sfc.keio.ac.jp/~rdv/computer-architecture-2019-wiki/index.php?Dependency%20Graphs

レイヤー1としてまず3と4が用意されていて、レイヤー2ではレイヤー1の結果に基づく加算処理と7が定義されています。
レイヤー3ではレイヤー2に基づく乗算処理が定義されています。
このようにして、数値計算をdependency graphとして定義することができます。

これを実際のコンピュータ内部での処理に置き換えて考えると次のようなフローになります。

レイヤー1: CPU内部のレジスターにメインメモリから3と4読み込む
レイヤー2: CPU内部でALUを用いて加算処理を行い出力をレジスターに保管する。メインメモリからCPU内部のレジスターに7を読み込む。
レイヤー3: CPU内部でALUを用いて乗算処理を行い、出力をレジスターに保管。のちにメインメモリに保管。'

Reference

rum(Yasuhiro Ohkura)


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-06-20 (木) 10:21:47 (892d)