Comments
Transcript
Title 並列コンピュータアーキテクチャの動向 Author(s) 内田, 啓一郎
\n Title Author(s) Citation 並列コンピュータアーキテクチャの動向 内田, 啓一郎; Keiichiro Uchida, Uchida Science Journal of Kanagawa University, 20(02): 117-120 Date 2009-10-20 Type Departmental Bulletin Paper Rights publisher KANAGAWA University Repository Science Journal of Kanagawa University 20（2）: 117-120 (2009) ■総 説（内田啓一郎研究室）■ 並列コンピュータアーキテクチャの動向 内田啓一郎 1,2 Trend of Parallel Computer Architecture Keiichiro Uchida1,2 1 2 Department of Information Sciences, Faculty of Sciences, Kanagawa University, Hiratsuka-City, Kanagawa 259-1293, Japan To whom correspondence should be addressed. E-mail: [email protected] Abstract: Parallel computer architecture has been developed for more than 40 years. According to the recent rapid evolution of electronic device technology, 1 billion or more transistors are mounted on a single LSI chip so that it is easy to construct a computer system with multiple processors in a single chip. A super computer includes more than 10 thousand processors and even a personal computer has multiple processors. This article describes the history and trend of parallel computer architecture, including Space Shared Tile Architecture which is proposed for recent device technology. Keywords: SIMD, parallel-processor, interconnect, multi-core system, PC-cluster, tile architecture, electronic device technology, LSI, CMOS, wiring delay はじめに 近 年 の 急 速 な 電 子 回 路 技 術 の 発 展 に 伴 い、LSI (Large Scale Integration) チップには 10 億個以上 のトランジスタ回路が搭載されるようになった。こ のため価格も低減できることにより、容易に多重プ ロセッサが実現できるようになった。したがって、 並列プロセッサシステムは急速に発展し、近年の スーパーコンピュータや大規模サーバでは何万台も のプロセッサが 1 システムの中に搭載されるように なっている。 一方、並列計算機の歴史は古く、すでに 1960 年 代から、並列計算機の概念が構築されていた。その 中でも特に有名な計算機として ILLIAV IV がある。 その後 MPP (Massively Parallel Processor) 方式が 出現したがコスト的な不利によって停滞した。最近 では、プロセッサ価格低減とソフトウエアの進化も あって広く並列コンピュータが普及している。 本論文では、並列計算機の歴史と技術動向および最 近の並列コンピュータアーキテクチャについて、い くつかの例を示しながら解説する。 1．電子回路技術とコンピュータ設計 電子計算機（コンピュータ）が世の中に現れてから 60 年を超える。当初は電子回路素子として真空管 が使われたので、高温熱電子流を発生するための電 力消費と装置体積は巨大であった。その後、固体半 導体によるトランジスタが使われ、消費電力、装置 体積は大幅に減少した。シリコンを材料とする半導 体技術が急激に進歩し、その動作原理は電流の有無 によって 0 または 1 の 2 進数を表現する方式であっ た。その後、電流を流さず、保持電圧によって 2 進 数を表現する CMOS (Complementary Metal Oxide Silicon) 方式に置き換わったことにより、消費電力 は圧倒的に小さくなった。最近の CMOS 半導体技 術は微小化技術によってさらに消費電力、体積の低 減を果たし、それに伴って高集積化と高速化が実 現された。最近では 10 億個以上のトランジスタが 1.5cm 角ほどの LSI チップに実装されており、ふん だんに素子を使うことができるようになった。 現在のプロセッサでは、特に記憶素子を活用して、 高速化を実現した。プロセッサ内に主記憶データを コピーして記憶するキャッシュや、ページアドレス や分岐先命令アドレスを記憶するテーブルなどを配 置し、LSI チップの約 3/4 を占めるようになってい る。過去に走行したプログラムの履歴を利用して、 その後のプログラム走行を予測する方式である。今 後、新規コンピュータアーキテクチャ（構成方式） の創出による大きな性能改善は期待しにくい状況に あり、ハードウエア投資に比べた性能向上率はそれ ©Research Institute for Integrated Science, Kanagawa University 118 Science Journal of Kanagawa University Vol. 20（2） ほど改善されなくなりつつある。つまり単一プロ セッサの高速化に対する技術進歩は飽和状態に近づ いていると言って差し支えない。 単一プロセッサの性能向上率が上限に達したとす れば、システム性能向上のためには、たくさんのプ ロセッサを置かざるを得ない。幸いなことに半導 体集積化技術は進展し続けており、LSI チップの中 に複数のプロセッサを収容することが可能となっ た。したがって現在は、マルチコア（多重プロセッ サ）構成のコンピュータがシステム構成の前提とな り、ハイエンドのスーパーコンピュータのみならず、 個人用 PC においてもマルチコア化が広く流通して いる。したがって、並列プロセッサアーキテクチャ は当たり前のコンピュータ技術になっている。マル チスレッドソフトウエア技術の進展などがマルチコ アシステムの普及を加速したが、さらに並列コン ピュータアーキテクチャを生かし切るために、並列 多重処理用ソフトウエア技術やその開発環境の高度 化となどが今後の IT 技術の挑戦課題である。 それでは、並列プロセッサの進歩について歴史的 観点から振り返ってみる。 2. 並列コンピュータの歴史 本格的な電子計算機（コンピュータ）ENIAC の登 場 か ら 約 60 年 と な り、 近 年 の 単 一 PC (Personal Computer) 用プロセッサでも百万倍（106）を超え る性能を持つようになった。当時の開発費 49 万ド ルは現在の貨幣価値換算で、概略 15 億円と推察し、 かつ PC が十万円とすれば、性能価格比は 15 × 109 （150 億）倍となる。このような圧倒的な進歩があっ た技術分野は他に例を見ない。この進歩は前節で述 べたように電子回路技術の発展とともにコンピュー タアーキテクチャの進展によるものが大きい。 すでに 40 年以上前から複数のプロセッサを配置 して、単一プロセッサの限界を打破するプロジェク トが始まっていた。イリノイ大学は ILLIAC IV 1） というコンピュータを開発した。当初 256 台の PE (Processing Element) を 設 置 す る 計 画（1968 年 ） 図 1．System configuration of ILLIAC IV 1）. であったが、最終的に 64 台の PE に留まった。図 1 にシステム構成を示す。 当時の並列コンピュータアーキテクチャの目的 は科学技術計算の速度を大幅に改善することで あ っ た。 こ の 目 的 を 達 成 す る た め SIMD (Single Instruction stream Multiple Data stream) 方 式 を 採用した。つまり、たくさんのデータに対して同じ 演算を行う方式である。SIMD を実現するにはパイ プライン方式（時間的並列化）と並列方式（物理 的に並列に装置を配置する）がある。1970 年代に は、商用機では価格性能比の優れたパイプラインが 採用され、ILLIAC IV のような挑戦的なプロジェク トでは並列方式が採用された。ILLIAC IV のアーキ テクチャでは CU (Control Unit) は全 PE を統括し、 SIMD 用の命令を各 PE に配信する。PE はそれぞ れ自己メモリ（PEM）を持ち、各 PE 用が使うため のデータを保持する。こうして同じ操作を多重デー タに対して行うことができる。i 番目の PE は i+1、 i-1、i+8、i-8 の 4 つの PE と接続され、そのいずれ かと交信することができた。現在ではこの接続方式 は 2 次元トーラス接続と言われている。 開発費不足と技術的問題点を克服して、64PE の ILLIAC IV は 1976 年頃に稼働し、大規模科学計算 の道具として利用された。ILLIAC IV プロジェクト は SIMD 方式の並列コンピュータを構築するための 基礎技術を生みだしたと言ってよい。 1980 年代には民間企業の努力によって並列コン ピュータの開発が実行された。これらのコンピュー タは MPP (Massively Parallel processor) と呼ばれた。 1983 年に Goodyear MPP、Connection Machine、が 出荷された。これらは 1 ビット演算プロセッサを数 万個結合するシステムであり、8/16/32 ビットデー タはそれぞれの個数のプロセッサを接続して演算す ることもできるなどの特徴的なアーキテクチャでも あった。台数は極端に大きいが、32 ビットの演算に はその数のプロセッサが必要であるため、システム 性能としては通常のスーパーコンピュータにくらべ て同等程度であり、処理形態においては専用計算機 のイメージはぬぐえなかった。 nCUBE という機械は 32 ビット構成のプロセッ サを持ち、PE 間の結合網として n-cube 方式を採用 し、1985 年に出荷された。当時注目を集めた Video On Demand 映像放送システムの構築要素となるこ とが目標でもあった。 これら MPP 方式の機械は当時としては使い勝手 と価格性能比の競合力に対する問題から、販売台数 を確保することができず、結果的にほとんどの企業 は消滅してしまった。 内田啓一郎 : 並列コンピュータアーキテクチャの動向 119 1995 年以降になると、PC 価格は数万円程度に低 減し、サーバ用高速プロセッサで開発された設計技 術を取り入れたことにより、Intel プロセッサは性 能もサーバプロセッサと同等レベルまで向上してき た。PC の出荷台数はサーバのそれを遥かに上回り、 サーバプロセッサのコスト競争力は PC プロセッサ の量産規模に太刀打ちできなくなった。この結果、 PC クラスタと呼ばれるコンピュータアーキテク チャが出現した。つまり標準的な PC と標準的な結 合ネットワーク（インターコネクト）で構成したシ ステムが価格的に優位となり、何万台以上を接続し たスーパーコンピュータが実現し、一般のサーバに も浸透する時代に突入した。 このように最近のハイエンド並列コンピュータ アーキテクチャではプロセッサの数が数万にも及ぶ ため、ネットワークの構成は ILLIAC IV 方式の 2 次元では不十分なので、3 次元トーラス方式に拡張 して採用されるようになった。一方 PC そのものも 先に述べたようにマルチコアが全面的に採用される ようになり、現在殆どのコンピュータは何らかのレ ベルで並列コンピュータであると言う事が出来る。 (a) 時分割方式 (b) 空間分割方式 図 3．マルチスレッドの割り当て． 半導体加工プロセスの微細化の進歩により、トラン ジスタを駆動するゲート遅延時間の減少率に比べ て、配線遅延時間の減少率が鈍いので、ゲート遅延 時間よりも配線遅延時間の割合が相対的に増加して いる。この配線遅延、つまり配列プロセッサ間の距 離を最短化するタイルアーキテクチャが最近提案さ れた 2,3)。 さらに、空間分割によってスレッド並列処理効率 を高めた STA が提案されている 4,5)。図 2 に STA の システム構成を示す。 STA では 4 × 4 の 16 個の演算タイルで計算を行 い、グローバルコントローラで演算タイルと記憶系 統を制御する。演算タイルは命令実行部と 4 つの隣 接演算タイルへのデータリンクを持つ。記憶系統と しては、データキャッシュ、命令キャッシュ、コン テキストレジスタを持つ。キャッシュの背景にメモ リ (MEM) の存在を前提としている。コンテキスト レジスタは、複数のスレッドのコンテキストを保持 する。STA ではできるだけ多くの演算タイルを駆動 して、演算効率を高める。 通常のタイルアーキテクチャでは 2 つのスレッド を割りつけるときは、別時間つまり時分割方式で動 作させる。図 3(a) のように Thread1 は 16 個のタイ ル全体に割り付けられので、Thread1 の切り替え時 点まで Thread2 の実行は待たされる。 STA では図 3(b）のように 16 個のタイルプロセッ サを分割して 2 つのスレッドを同時に割り付けて、 空間分割方式で動かすことができる。したがって演 算タイルを 8 個以下で動かす場合は同一時間間隔で 2 スレッドを実行することができる。 OS はプロセスとプロセス内のスレッドを管理し、 スレッドをグローバルコントローラに割り当てる。 STA では、ハードウェアマルチスレッディングを 実現するため、グローバルコントローラでスレッド を管理する。また、管理できる最大スレッド数は 4 とした。グローバルコントローラはスレッドのスケ ジューリングを行い、実行対象スレッドを選択し、 演算タイルに供給する命令の転送指示を出す。そし て、演算タイルは供給された命令を解釈・実行する。 図 4 に STA 用コンパイラの機能を示す。 コンパイラのバックエンド部分は、ループ展開、 関数インライン化、プレディケート変換などを行っ て並列実行可能な命令群を引き出し、ベーシック ブロックを組み合わせたハイパーブロックを生成す る。そして、ハイパーブロックを物理的な 16 個の 演算タイルにマッピングするためにマップドブロッ 図 2. STA システム構成． 図 4. STA コンパイラ． 3. STA (Space Sharing Tile Architecture) 120 Science Journal of Kanagawa University Vol. 20（2） クを生成する。マップドブロックは並列命令実行数 に合わせてタイルサイズを変える (full/half)。マッ プドブロック対応して演算タイルが実行するコード を命令ブロックとして生成し、ブロックの識別子 （ID）やサイズの情報をブロックヘッダに付加する。 実行可能なコードはメモリに格納される。コンパイ ラは未実装であるが処理の構想を記述している。 図 5 にグローバルコントローラの動作概要を示す。 グローバルコントローラは、TM（Thread Manager）、TS（Thread Scheduler）、EM（Execution Manager） 、BP（Branch Predictor） を 持 つ。TM は、スレッドが実行する命令ブロックに対応するブ ロックヘッダを管理し、スレッド制御の中心として 機能する。TS は、スレッドを適切にマッピングし て、効率よく演算タイルで実行できるように異なる サイズが混在するスレッド群をスケジューリングす る。EM は、演算タイルで実行する命令の供給を制 御する。BP は、次に実行するブロックを予測する。 図 6 にスレッドスケジューリングの例を示す。 スケジューリングを行うために深さ 4 の循環ュー を用いる。キュー内の左側の数字は TM が持つス レッド管理スロットの ID で、右側はスレッドが実 行するブロックのサイズである。図 5 はブロックサ イズが full と half が混在している場合である。まず、 最初に実行するスロット 1 のブロックサイズが half なので、half であるスロット 3 と同時実行する。そ の後、スロット 2、4 という順で実行するので 3 単 位時間でこれらのスレッド実行が完了する。なお、 空間分割をしない場合は 4 単位時間が必要である。 STA の動作検証をするため、ソフトウエアによる シミュレータを開発した。 シミュレータはクロッ クごとに動作を行い、実行サイクル数を測定するこ 図 5．グローバルコントローラ． 図 6．スレッドスケジューリング． とができる。リダクション計算（総和など）によっ て STA の性能を測定した。総和 (sum) 計算では、 空間分割機能がない場合に 48 サイクル、STA では 40 サイクルとなり、1.2 倍の効果があった。最大値 (max) 計算では 1.33 倍の速度向上が見られ、使用 率は 65% になった。世の中の計算には、多くのデー タに対して独立な計算と、リダクション計算のよう に演算結果を次の演算で使う必要がある依存関係を 持つ計算とがある。STA ではタイルプロセッサの数 は 16 個とし、分割数を 2 としたが、現状の半導体 電子回路技術に基づく本格的な実装では 1000 個規 模にすることは容易であろう。その場合に分割数を 100 以上にでき、空間分割処理は依存関係計算に対 して大きな性能向上となることが予想できる。 おわりに 本論文では、コンピュータの誕生から現在までのコ ンピュータアーキテクチャについて、電子回路技術 の発展と並列コンピュータアーキテクチャとの関係 に注目して述べた。現在は高性能・大規模スーパー コンピュータから個人用のコンピュータまで、並列 コンピュータアーキテクチャを持つことになった。 STA は最近の半導体電子回路に最適化された並列 コンピュータアーキテクチャである。今後の課題は、 マルチスレッド管理をミドルウエア階層において十 分にサポートし、ユーザアプリケーションプログラ ムを高い効率で実行できる環境を構築することであ る。この高機能プログラム開発環境を築くことがで きれば、空間分割機能を持つ STA は多数台大規模 並列コンピュータ構築に有効であろう。 文献 1) Barnes G, Brown R, Kato M, Kuck D, Slotnick D and Stokes R (1968) The ILLIAC IV computer. IEEE Transactions on Computer C17: 746-757. 2) Taylor MB, Kim J, Miller J, Wentzlaff D, Ghodrat F, Greenwald B, Hoffmann H, Johnson P, Lee J, Lee W, Ma A, Saraf A, Seneski M, Shnidman N, Strumpen V, Frank M, Amarasinghe S and Agarwal A (2002) The raw microprocessor: A computational fabric for software circuits and general purpose program. IEEE Micro 22: 25-35. 3) Burger D, Keckler SW, McKinley KS, Dablin M, John LK, Lin C, Moore CR, Burrill J. McDonald RG and Yoder W (2004) Scaling to the end of silicon with EDGE architectures. IEEE Computer 37: 44-55. 4) 矢頭岳人，米澤直記，内田啓一郎 (2008) タイルアー キテクチャに対するマルチスレッドの空間分割．第 7 回 FIT 講演論文集 ．pp.231-232. 5）矢頭岳人 (2009) 空間分割マルチスレッディングアー キテクチャ．神奈川大学大学院理学研究科情報科学 専攻修士論文 ．