Loading article…
並列コンピュータアーキテクチャ では、シストリックアレイは、セルまたはノードと呼ばれる密接に結合されたデータ処理ユニット(DPU) の均質なネットワークです。各ノードまたは DPU は、上流の隣接ノードから受信したデータの関数として部分的な結果を独立して計算し、その結果を自身に格納して下流に渡します。シストリックのようなデータフローの原理は、第二次世界大戦中にドイツのローレンツ暗号を解読するために使用された初期のコンピュータであるColossusで初めて見られました。[ 1 ] Colossus の機密性のため、それらはHT KungとCharles Leisersonによって独立して発明され、帯状行列の多くの密な線形代数計算 (行列積、線形方程式系の解法、LU 分解など) 用のアレイについて説明しました。初期のアプリケーションには、整数と多項式の最大公約数の計算が含まれます。 [ 2 ]現在では、空間設計に基づくNPUおよびハードウェアアクセラレータで見ることができます。これらは、Flynnの分類法では複数命令単一データ（MISD）アーキテクチャに分類されることもありますが、この分類には疑問があります。なぜなら、この記事の後半で説明するように、シストリックアレイをFlynnの4つのカテゴリ（ SISD、SIMD、MISD、MIMD ）のいずれとも区別する強力な議論が可能だからです。
並列入力データは、ハードワイヤードされたプロセッサノードのネットワークを流れ、そこで入力データが結合、処理、統合、またはソートされて、最終的な結果が出力されます。シストリックアレイにおけるデータの波状伝播は、人間の循環器系の脈拍に似ているため、 「シストリック」という名称は医学用語から付けられました。この名称は、心臓による規則的な血液の送り出しを連想させる「収縮期（systole） 」に由来しています。
シストリックアレイは、乗算や累積などの特定の演算がハードワイヤリングされていることが多く、大規模並列積分、畳み込み、相関、行列乗算、データソートなどのタスクを実行します。また、 DNAやタンパク質の配列解析で使用される動的計画法アルゴリズムにも使用されます。
シストリックアレイは通常、特定のアプリケーション向けにハードウェア接続またはソフトウェア構成が可能な、プリミティブなコンピューティングノードの大規模なモノリシックネットワークで構成されます。ノードは通常固定されており同一ですが、相互接続はプログラム可能です。一方、より汎用的なウェーブフロントプロセッサは、アレイのサイズと設計パラメータに応じて、モノリシックである場合もそうでない場合もある、高度で個別にプログラム可能なノードを採用しています。もう一つの違いは、シストリックアレイは同期データ転送に依存するのに対し、ウェーブフロントは非同期で動作する傾向があることです。
一般的なフォン・ノイマン・アーキテクチャでは、プログラムの実行は共通メモリに格納された命令スクリプトに従い、CPUのプログラムカウンタ（PC）の制御下でアドレス指定と順序付けが行われますが、シストリックアレイでは、個々のノードは新しいデータの到着によって起動され、常にまったく同じ方法でデータを処理します。各ノード内の実際の処理はハードワイヤードまたはブロックマイクロコーディングで記述でき、後者の場合、共通ノードの特性はブロックプログラミング可能です。
データカウンタによって駆動されるデータストリームを持つシストリックアレイ方式は、プログラムカウンタによって駆動される命令ストリームを持つフォン・ノイマンアーキテクチャに対応するものです。シストリックアレイは通常、複数のデータストリームを送受信し、これらのデータストリームを生成するために複数のデータカウンタが必要となるため、データ並列処理をサポートします。
シストリックアレイの大きな利点は、すべてのオペランドデータと部分的な結果がプロセッサアレイ内に格納される（通過する）ことです。フォン・ノイマン型やハーバード型の逐次マシンとは異なり、各演算中に外部バス、メインメモリ、内部キャッシュにアクセスする必要はありません。また、アムダールの法則によって規定される並列性能の逐次的な制限も、シストリックアレイには同様には適用されません。これは、データ依存性がプログラマブルノード相互接続によって暗黙的に処理され、高度に並列化されたデータフローの管理に逐次的な手順が存在しないためです。
したがって、シストリックアレイは、人工知能、画像処理、パターン認識、コンピュータビジョンなど、動物の脳が特に得意とするタスクにおいて非常に優れています。また、ウェーブフロントプロセッサ全般は、ハードウェア上で自己構成型ニューラルネットワークを実装することで、機械学習においても非常に優れた性能を発揮します。
シストリックアレイは公式にはMISDに分類されますが、その分類にはやや問題があります。入力は通常、独立した値のベクトルであるため、シストリックアレイはSISDではありません。これらの入力値は結果にマージされ結合されるため、 SIMDベクトル処理ユニットのように独立性を維持しません。したがって、このアレイをSISDとして分類することはできません。結果として、MIMDは単に小型のSISDおよびSIMDマシンの集合と見なせるため、このアレイをMIMDとして分類することもできません。
最後に、データ群はアレイをノードからノードへと通過する際に変換されるため、複数のノードは同じデータに対して動作しているわけではなく、そのためMISDという分類は不適切です。シストリックアレイがMISDとして適格でないもう1つの理由は、SISDカテゴリから除外される理由と同じです。入力データは通常、単一のデータ値ではなくベクトルですが、任意の入力ベクトルは単一のデータ項目であると主張することもできます。
上記にもかかわらず、シストリック配列は並列コンピューティングの教科書や工学系の授業で、MISDアーキテクチャの典型的な例としてよく取り上げられます。配列を外部からアトミックなものとして捉えるならば、おそらくSFMuDMeR（単一関数、複数データ、統合結果）に分類されるべきでしょう。
シストリックアレイは、ノード間を接続する事前定義された計算フローグラフを使用します。カーンプロセスネットワークも同様のフローグラフを使用しますが、シストリックアレイではノードが同期して動作するのに対し、カーンネットワークでは各ノード間にFIFOキューが存在するという点で異なります。
シストリックアレイは、セルと呼ばれるデータ処理ユニットのマトリックス状の行で構成されています。データ処理ユニット（DPU）は、中央処理装置（CPU）に似ています（ただし、通常はプログラムカウンタがありません[ 3 ]。これは、動作がトランスポートトリガー、つまりデータオブジェクトの到着によってトリガーされるためです）。各セルは、処理後すぐに隣接するセルと情報を共有します。シストリックアレイは多くの場合長方形で、データは隣接するDPU間でアレイを横切って流れ、多くの場合、異なる方向で異なるデータが流れます。アレイのポートに出入りするデータストリームは、自動シーケンスメモリユニット（ASM）によって生成されます。各ASMにはデータカウンタが含まれています。組み込みシステムでは、データストリームは外部ソースから入力され、外部ソースに出力されることもあります。
シストリックアルゴリズムの一例として、行列乗算を設計することが考えられます。一方の行列は配列の上部から一度に1行ずつ入力され、配列を下方向に渡されます。もう一方の行列は配列の左側から一度に1列ずつ入力され、左から右に渡されます。各プロセッサが1行と1列全体を処理するまで、ダミー値が渡されます。この時点で、乗算の結果が配列に格納され、配列を下方向または横方向に、一度に1行または1列ずつ出力できるようになります。[ 4 ]
シストリックアレイは、メッシュ状のトポロジーで少数の最近傍DPUに接続されたDPUのアレイです。DPUは、それらの間を流れるデータに対して一連の操作を実行します。従来のシストリックアレイ合成方法は代数アルゴリズムによって行われてきたため、線形パイプのみを持つ均一なアレイしか得られず、すべてのDPUでアーキテクチャが同じになります。その結果、従来のシストリックアレイでは、規則的なデータ依存性を持つアプリケーションしか実装できません。SIMDマシンと同様に、クロック付きシストリックアレイは、各プロセッサが交互に計算フェーズと通信フェーズを実行することで「同期」して計算します。しかし、DPU間で非同期ハンドシェイクを行うシストリックアレイは、ウェーブフロントアレイと呼ばれます。よく知られているシストリックアレイの1つは、Intelが製造したカーネギーメロン大学のiWarpプロセッサです。iWarpシステムは、双方向のデータバスで接続された線形アレイプロセッサを備えています。
シストリックアレイ（ウェーブフロントプロセッサとも呼ばれる）は、 HT KungとCharles E. Leisersonによって初めて記述され、彼らは1979年にシストリックアレイを記述した最初の論文を発表しました。しかし、同様の技術を使用したことが知られている最初のマシンは、1944年のColossus Mark IIでした。Colossusは並列シフトレジスタを使用してデータをパルス化しており、これは機能的にはシストリックアレイに似ていますが、1978年のKung-Leisersonアーキテクチャを定義する相互接続された「処理要素」（PE）が欠けていました。
シストリックアレイとして明示的に設計された最初のマシンは、 1984年のWARPコンピュータであった。
ホーナーの多項式評価規則は次のとおりです。
プロセッサがペアで配置された線形シストリックアレイ：一方のプロセッサは入力を乗算し、そして結果を右に渡すと、次のそして結果を右に渡します。
乗算累積演算を実行する処理要素（PE）の連鎖を考えます。入力データ（）と重み（) 収縮期に、つまり、データは規則的かつリズミカルな方法でアレイを流れます。重みは各 PE 内で静止したままですが、入力データと部分和 (反対方向に移動する。
各PEは以下の操作を実行します。どこ：
左から、入力ストリームは右側から見ると、出力ストリームは。 もし右端のPEに同時に入力すると、左端のPEが出力します。これは1次元畳み込みです。同様に、n次元畳み込みは、n次元のPE配列によって計算できます。
1D畳み込みの他の実装も多数あり、それぞれ異なるデータフローが用いられている。[ 5 ]
1次元および2次元のシストリックアレイを使用してオンザフライ最小二乗法を実行するアルゴリズムについては、 [ 5 ]図12を参照してください。
バブルソートも1次元シストリック計算の一例である[ 6 ]が、サイズNの配列に対してN-1回のパスを適用する。各パスでは、部分シーケンスの最大要素が、ソートされた結果の最終位置に向かってシストリックに移動する。
比較器と 2 つのレジスタを備えた N/2 個の処理要素 (PE) をスタックのような形で配置すれば、サイズ N の配列 (またはストリーム) を 2N 時間でソートできます。これは、シストリック スタックの各レベルで、各 PE に格納されている要素のペアのうち大きい方をさらに下に押し込むときに、要素を押し込むことによって行われます。すべての要素が押し込まれた後、各 PE の最小要素がポップアウト (または「プッシュアップ」) されるという逆の処理が行われ、結果として、要素のストリームが昇順にソートされて出力されます。[ 7 ]
処理要素数 (P) よりも大きいサイズ (N > P) の入力配列をソートすることは、このようなシステムで効率的に行うにはやや複雑ですが、(外部シリアルプロセッサを追加することで) O(N log N/log P) 時間で実現できます。シリアルプロセッサは「バケット B ツリー」を管理する必要があり、B ツリーの各ノードにはP 個の「バケット」があり、それらは最終的に PE を使用して O(P) 時間でソートされます。[ 8 ]
