Parallel-algorithm-structure

並列アルゴリズム-構造

アルゴリズムを適切に適用するには、適切なデータ構造を選択することが非常に重要です。 これは、データ構造で実行される特定の操作は、別のデータ構造で実行される同じ操作と比較して時間がかかる可能性があるためです。

例-配列を使用してセット内のi ^ th ^要素にアクセスするには一定の時間がかかりますが、リンクリストを使用すると、同じ操作を実行するのに必要な時間が多項式になる場合があります。

したがって、データ構造の選択は、実行するアーキテクチャと操作の種類を考慮して行う必要があります。

以下のデータ構造は、並列プログラミングで一般的に使用されます-

• リンクリスト
• 配列
• ハイパーキューブネットワーク

リンクリスト

リンクリストは、ポインターで接続された0個以上のノードを持つデータ構造です。 ノードは、連続したメモリ位置を占有する場合と占有しない場合があります。 各ノードには2つまたは3つの部分があります。1つはデータを格納する*データ部分*で、残りの2つは前または次のノードのアドレスを格納する*リンクフィールド*です。 最初のノードのアドレスは、 head と呼ばれる外部ポインターに保存されます。 * tail、*と呼ばれる最後のノードには、通常、アドレスが含まれていません。

リンクリストには3種類あります-

• 単一リンクリスト
• 二重リンクリスト *循環リンクリスト

単一リンクリスト

片方向リンクリストのノードには、データと次のノードのアドレスが含まれます。* head *と呼ばれる外部ポインターは、最初のノードのアドレスを保存します。

単一リンクリスト

二重リンクリスト

二重リンクリストのノードには、前のノードと次のノードの両方のデータとアドレスが含まれます。 head と呼ばれる外部ポインターは最初のノードのアドレスを保存し、 tail と呼ばれる外部ポインターは最後のノードのアドレスを保存します。

二重リンクリスト

循環リンクリスト

循環リンクリストは、最後のノードが最初のノードのアドレスを保存したという事実を除いて、単一リンクリストに非常に似ています。

循環リンクリスト

配列

配列は、同様のタイプのデータを格納できるデータ構造です。 1次元でも多次元でもかまいません。 配列は静的または動的に作成できます。

• *静的に宣言された配列*では、コンパイル時に配列の次元とサイズがわかります。
• *動的に宣言された配列*では、実行時に配列の次元とサイズがわかります。

共有メモリプログラミングの場合、アレイは共通メモリとして使用でき、データ並列プログラミングの場合は、サブアレイに分割して使用できます。

ハイパーキューブネットワーク

Hypercubeアーキテクチャは、各タスクが他のタスクと通信する必要がある並列アルゴリズムに役立ちます。 ハイパーキューブトポロジは、リングやメッシュなどの他のトポロジを簡単に埋め込むことができます。 nキューブとも呼ばれます。 n は次元数です。 ハイパーキューブは再帰的に構築できます。

画像：/parallel_algorithm/images/hypercube.jpg [Hypercube]画像：/parallel_algorithm/images/hypercube1.jpg [Hypercube 1]