並列アルゴリズム-構造
アルゴリズムを適切に適用するには、適切なデータ構造を選択することが非常に重要です。これは、データ構造に対して実行される特定の操作が、別のデータ構造に対して実行される同じ操作と比較して時間がかかる場合があるためです。
Example−配列を使用してセットのi番目の要素にアクセスするには、一定の時間がかかる場合がありますが、リンクリストを使用すると、同じ操作を実行するために必要な時間が多項式になる場合があります。
したがって、データ構造の選択は、アーキテクチャと実行する操作のタイプを考慮して行う必要があります。
以下のデータ構造は、並列プログラミングで一般的に使用されます-
- リンクリスト
- Arrays
- ハイパーキューブネットワーク
リンクリスト
リンクリストは、ポインタで接続された0個以上のノードを持つデータ構造です。ノードは、連続するメモリ位置を占有する場合と占有しない場合があります。各ノードには2つまたは3つの部分があります-1つdata part データを保存し、他の2つは link fields前または次のノードのアドレスを格納します。最初のノードのアドレスは、と呼ばれる外部ポインタに格納されますhead。として知られている最後のノードtail, 通常、アドレスは含まれていません。
リンクリストには3つのタイプがあります-
- 単一リンクリスト
- 二重リンクリスト
- 循環リンクリスト
単一リンクリスト
単一リンクリストのノードには、データと次のノードのアドレスが含まれます。と呼ばれる外部ポインタhead 最初のノードのアドレスを格納します。
二重リンクリスト
二重リンクリストのノードには、前のノードと次のノードの両方のデータとアドレスが含まれています。と呼ばれる外部ポインタhead 最初のノードのアドレスと呼び出された外部ポインタを格納します tail 最後のノードのアドレスを格納します。
循環リンクリスト
循環リンクリストは、最後のノードが最初のノードのアドレスを保存したという事実を除いて、単一リンクリストと非常によく似ています。
配列
配列は、同様のタイプのデータを格納できるデータ構造です。1次元または多次元にすることができます。配列は静的または動的に作成できます。
に statically declared arrays, 配列の次元とサイズは、コンパイル時にわかっています。
に dynamically declared arrays, 配列の次元とサイズは実行時に認識されます。
共有メモリプログラミングの場合、配列は共通メモリとして使用でき、データ並列プログラミングの場合は、サブ配列に分割して使用できます。
ハイパーキューブネットワーク
ハイパーキューブアーキテクチャは、各タスクが他のタスクと通信する必要がある並列アルゴリズムに役立ちます。ハイパーキューブトポロジは、リングやメッシュなどの他のトポロジを簡単に埋め込むことができます。n-cubesとも呼ばれ、ここでnは次元数です。ハイパーキューブは再帰的に構築できます。
