コンピュータアーキテクチャ特論 hunga＠am．ics．keio．ac．jp テキスト pp.10-12（該当個所なし）

Presentation on theme: "コンピュータアーキテクチャ特論 hunga＠am．ics．keio．ac．jp テキスト pp.10-12（該当個所なし）"— Presentation transcript:

1 コンピュータアーキテクチャ特論 hunga＠am．ics．keio．ac．jp テキスト pp.10-12（該当個所なし）
その他の並列アーキテクチャ コンピュータアーキテクチャ特論 hunga＠am．ics．keio．ac．jp テキスト　pp.10-12（該当個所なし）

2 Ｆｉｎｅ　ｇｒａｉｎ　 ＳＩＭＤ Ｃｏａｒｓｅ　ｇｒａｉｎ　 マルチプロセッサ コントロール フロー制御 バス結合型ＵＭＡ スイッチ結合型ＵＭＡ Ｓｉｍｐｌｅ　ＮＵＭＡ ＣＣ－ＮＵＭＡ ＣＯＭＡ ＭＩＭＤ ＮＵＭＡ ＮＯＲＡ マルチコンピュータ データフロー制御 混合制御 要求駆動 シストリックアレイ その他

3 全プロセッサが同一命令で動作 柔軟性が低い SIMD 命令メモリ 命令 演算プロセッサ データメモリ

4 ＳＩＭＤ型の分類 粗粒度型：各ノードで浮動小数点演算処理が可能 細粒度型：各ノードは１bitまたは数bitの演算しかできない
ILLIAC-IV，BSP,GF-11 最近の高性能CPUのマルチメディア命令 細粒度型：各ノードは１bitまたは数bitの演算しかできない ICL　DAP,　CM-2，MP-2 コネクションマシンは応用分野を人工知能に拡大（CmLispの功績）

5 CM-2のプロセッサ Flags A B F OP C Context s c 256bit memory 1bit serial ALU

6 CM2のプロセッサチップ 4096チップで 命令 64K PE １チップ構成 P Router P P P
4x4 Processor Array 12links 4096 Hypercube connection 256bit x 16 PE RAM

7 SIMD型の将来 粗粒度SIMD 細粒度SIMD 大規模なものの復活はないだろう マイクロプロセッサの高速化技術として小規模なものが生き残る
画像処理等で圧倒的に有利 CM2　→　CM5のようにマルチプロセッサ化した方が性能が高い

8 シストリックアーキテクチャ Data列ｘ 演算アレイ Data列ｙ 特定の演算能力を持つアレイ列に一定の間隔で
リズミカルにデータを送りこみ、並列演算

9 帯行列の行列積 y=Ax y0 y1 y2 y3 a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34
ｙｉ ｙｏ Ｘ＋ ｙｏ＝ ａ ｘ ＋ ｙ ｉ x

10 帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44
Ｘ ＋ x1

11 帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a33
Ｘ ＋ Ｘ ＋ x2 x1

12 帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44

13 帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a44
Ｘ ＋ Ｘ ＋ x2 x3

14 帯行列の行列積 y=Ax a11 a12 0 0 a21 a22 a23 0 0 a32 a33 a34 0 0 a43 a44 a44
Ｘ ＋ x3 x2

15 シストリックアーキテクチャの 特長 入出力ピン数が少ない 単純な同期制御 近接接続のみで構成可能
1980年代Kungらの提案により注目されたがLSI実装面積の不足により普及しなかった 他の「VLSIアルゴリズム」と共に復活の可能性

16 データフローアーキテクチャ データをトークンとして考え、到着と共に計算処理が駆動される。 記憶要素を明示的に指定しない。
アルゴリズムの持つ並列性を最大限に引き出すことができる。

17 データフローグラフ ｄ ｅ ｃ ｘ ａ ｂ ＋ ＋ ｘ （ａ＋ｂ）ｘ（ｃ＋（ｄｘｅ））

18 命令実行サイクル 命令読み出し データ待ち合せ データ読み出し 命令読み出し 命令実行 命令実行 データ格納 あて先指定 データフローマシン
通常のプロセッサ

19 データフローマシンの問題点 純粋なデータフローマシン（Dennisのマシン）は無駄が多い。
色付きトークン等の導入でデータフローグラフの再利用。 構造の複雑化 演算器レベルの処理時間とそれに要する時間の比率の問題 局所性の無視

20 日本はデータフローマシン研究の世界的な中心（だった）
電総研　Sigma-I　：科学技術用 電総研　EM-4/EM-X:演算の粒度を高める工夫 NTT　DFM：関数型言語を指向。Lenient　Consの提案 NEC　ImPP：画像処理用のチップ。商用化を目指した

21 要求駆動マシン（リダクションマシン、デマンドドリブンマシン）
Z：（／，ｘ，ｙ） ｙ：　（－，ａ，ｂ） ｘ：　（＋，ａ，ｂ） ｂ：　（５） ａ：　（３）

22 要求駆動マシン 値が必要になった時点で計算を駆動 実装例はほとんどない（どうやって実装するんだ？？） cf. データフローマシン
データフローマシンに比べて並列性は小さいが、無駄は少ない（のではないか） 実装例はほとんどない（どうやって実装するんだ？？）

23 Reconfigurable System （Custom Computing Machine）
SRAM型プログラマブルデバイスから構成されるシステム上で問題の解法アルゴリズムを直接ハードウェア化して実行する 専用マシンのスピード 汎用マシンの柔軟性 プログラム格納型計算機とはまったく異なる原理でしかも堂々たる体系を作ることができる

24 (Field Programmable Gate Array)
SRAM型FPGA (Field　Programmable　Gate　Array) 5入力テーブル 2　F．F． I/O SRAM(Configuration　Memory） Logic　Block Switch

25 (Complex Programmable Logic Device)
SRAM型CPLD (Complex　Programmable　Logic　Device) I/O SRAM(Configuration　Memory） Logic　Block Switch

26 最近の状況 Xilinx社Virtex、ALTERA社APEX等新世代が登場
ｹﾞｰﾄ数は500Kｹﾞｰﾄに及ぶ（メモリ等を換算する場合が多いが、、、） 最大動作周波数は設計次第だが30MHz程度ならば容易に実現可能 内部データ格納用SRAM Partial　Reconfiguration、マルチコンテキスト等の新機能を持ったデバイスの登場

27 Reconfigurable Systemの分類
スタンドアローン型 独立性の高い専用システム Splash　１・２，　RM-I,II,III,IV，　RASH（三菱）、ATTRACTOR（NTT） コ・プロセッサ型 汎用プロセッサの一部の処理を高速化 PRISM　I,II、DISC-II、PipeRench、CHIMAERA，Chameleonなど

28 Reconfigurable Systemの発達
Stand　Alone Co-processor New　Device 1990年 第1回FPL SPLASH MPLD PRISM-I 1992年 第1回Japanese　FPGA/PLD　Conf. SPLASH-2 PRISM-II RM-I WASMII 1993年 第1回FCCM RM-II Cache　Logic RM-III DISC RM-IV 1995年 YARDS Mult．Context　FPGA RM-V DISC-II HOSMII ATTRACTOR FIPSOC Cont．Switch．FPGA RASH PipeRench DRL PCA 2000年 CHIMERA Chamereon

29 Splash-2 (Arnoldら 92) 米国計算機科学センター
文字列検索、画像処理、ＤＮＡの塩基配列間の距離を求める問題でCray-ＩＩの330倍の性能を発揮 直線シストリックアレイ構造 VHDL,　並列Cによるプログラミング Annapolis　Micro　Systems社より商用化（WILDFIRE)

30 Ｓｐｌａｓｈ-ＩＩ 米国計算機科学センタ 文字列検索、画像処理、ＤＮＡの塩基配列間の距離を求める問題でCray-IIの330倍の性能を発揮
Ｓｐｌａｓｈ-ＩＩ　 米国計算機科学センタ 文字列検索、画像処理、ＤＮＡの塩基配列間の距離を求める問題でCray-IIの330倍の性能を発揮 直線アレイ構造 VHDL,並列Cによるプログラミング

31 RM-IV(神戸大学) ＦＰＧＡ mem． ＦＰＧＡ mem． FPIC Ｉｎｔｅｒｆａｃｅ

32 RASH (三菱電機) 1Unit: 最大6枚のEXEボードとCPUボード（Pentium) 複数のUnitを接続可能 ディスプレイ
CompactPCI bus EXE- ボード CPUボード ディスプレイ disk Ethernet LAN RASH unit CD 1Unit: 最大6枚のEXEボードとCPUボード（Pentium) 複数のUnitを接続可能 &p This slide is supported by Dr.Nakajima of Mitsubishi.

33 EXEボードの構成 FPGA Altera FLEX10K100A (62K-158KGate) リンク接続とバス接続 2系統のクロック
PCI-bus リンク接続とバス接続 2系統のクロック PCIバスＩ／Ｆ ＳＲＡＭ搭載 DRAM付加ボード搭載可 PCI-bus I/F PCI Local-bus SRAM （2MB） EXE-board controller Clocks／Cont. signals Local-bus FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA　Altera　FLEX10K100A　(62K-158KGate) &p

34 ATTRACTOR（NTT） 高速シリアルリンク（1Gbps） RISC FPGA RISC FPGA ATM I/O RAM （LUT)
SW Buffer RISC RISC RISC RISC Ethernet Compact　PCI MPU ATM通信処理に 特化したシステム 多種類のボードを接続 Mem. ボードレベルで再構成可能

35 RHiNETｰ１／NI （RWCP＋Keio U.)
NI board As this figure, an LASN assumes an environment in which personal computers and workstations are distributed within one or more floors of a building of a building and is able to include loop connections. Interconnecting PC nodes with flexible NI

36 RHiNET-1/NI： Flexible Interface
Primitive　Handler （FLEX10K) ＰＣＩ　Interface Optical Interconnect FIFO Address　Translate Table Region Buffer Twin 　Memory Packet　Buffer Various　message　handling　primitives can　be　changed

37 RHiNET-1/NI This photo shows a RHiNET-1/NI board which attaches to PCI bus. CPLD function unit, TLBs memory, network daughter board is mounted.

38 Optical Interconnection Module
133MHz operation 1.5Gbps bandwidth This photo shows an optical interconnection module. This optical module operates with 133MHz and 1.5Gbps bandwidth.

39 コ・プロセッサ型 Core CPUと密接続 プログラムの一部を高速化
NAPA,　Garp,　Chameleon,　Chimaera,　PipeRench

40 PRISM II（Brown大学） プログラムのよく使う部分を高速化 コプロセッサ型の元祖 Am2955 CPU Ｄａｔａ Ａｄｄｒｅｓｓ
Ｃｏｎｔｒｏｌ Boot　ROM Sｗｉｔｃｈ DRAM Burst　Mode Memory　Controller DRAM ＦＰＧＡ　Ｍｏｄｕｌｅ ＦＰＧＡ　Ｍｏｄｕｌｅ ＦＰＧＡ　Ｍｏｄｕｌｅ プログラムのよく使う部分を高速化 コプロセッサ型の元祖

41 Garp (Hauserら 97) UCBのプロジェクト MIPSコアとReconfigurable Arrayが強結合しメモリ階層を共有
Memory queue UCBのプロジェクト MIPSコアとReconfigurable Arrayが強結合しメモリ階層を共有 コンパイラの静的解析によりループ処理を抽出しハードウェア化 画像処理などでUltrasparcの43倍の性能 MIPS Cache Q Q Q Crossbar 32bit buses x 5 Reconfigurable Array

42 DISC (Wirthlinら 95) Brigham Young大学 動的な部分書き換え機能を用いた汎用プロセッサ
FPGA 3 Processor Core System Memory Brigham Young大学 動的な部分書き換え機能を用いた汎用プロセッサ 任意のカスタム命令を基本命令セットに追加可能 各モジュールをユーザが設計 C言語上から関数として利用 FPGAをカスタム命令モジュールのキャッシュのように使用 FPGA 1 Bus I/F Configuration Controller FPGA 2 Custom Instruction Space Host P/C

43 CHIMAERA (Yeら 2000) Northwestern大学 スーパスカラプロセッサのデータパスに可変構造アレイを挿入
シャドウレジスタファイルから9レジスタを一度に読込み Out of Order制御 10～20%の高速化 シャドウレジスタ ファイル レジスタ ファイル 可変構造 アレイ uPコア コントローラ

44 Chameleon（Cｈameleon社）
Field　Programmable　System　Level　Integrated　Circuits　(FPSLICs) 疎粒度のReconfigurable　Processing　Fabric、RISC　Core、PCI　Controller、Memory　Controller、DMA　Controller、SRAMを1チップ上に混載 信号処理、通信プロトコル処理用、高速DSPの5-10倍の性能

45 Chameleon CS2112 32-bit PCI Bus 64-bit Memory Bus PCI Cont. RISC Core
Controller 128-bit RoadRunner Bus Configuration Subsystem DMA Subsystem Reconfigurable Processing Fabric 160-pin Programmable I/O

46 Reconfigurable Processing Fabricの構造
CTL中の最大８命令をDPU中で実行可能 CTLは、同じサイクルで次の命令を決定可能 新しいbit　ｓｔｒｅａｍをloadすることで構成を変えられる Reconfigurable Processing Fabricの構造 DPU CTL LM Tile　0 Slice　0 LM DPU CTL Tile　0 Slice　3 108のDPU(Data　Path　Unit)が４つのSlice（各３Tile）を構成 1Tile:　９DPU＝32bit ALU X 7 16bit + 16bit乗算器　X　２

47 DPUの構成 OP：C、Verilog演算子サポート DPU単位のSIMD,パイプライン Instruction Routing
Register ＆ Mask Routing MUX OP Register Barrel Shifter Register Register ＆ Mask Routing MUX

48 Reconfigurable Systemの 問題点
SRAM型FPGAの演算器は専用CPU,DSPよりも10倍遅く、10倍集積度が劣る メモリとの接続が脆弱 アルゴリズムを変換するための標準的方法が存在しない 問題サイズがシステムサイズを越えるとお手上げ

49 問題の解決 １ SRAM型FPGAの演算器は専用CPU,DSPよりも10倍遅く、10倍集積度が劣る メモリとの接続が脆弱
問題の解決　１ SRAM型FPGAの演算器は専用CPU,DSPよりも10倍遅く、10倍集積度が劣る 最新のプロセス利用により差が縮まる 粗粒度FPGA CPUとの混載 メモリとの接続が脆弱 大規模SRAMとの混載 DRAM混載

50 FPAccA(広島市立大) Array of floating ALU(Add/Mult） model2(0．35um)
Routing　Matrix Array　of　floating ALU(Add/Mult） model2(0．35um) 12ｘ　25MFLOPS　 ＡＬＵ

51 Communication centric FPGA Proteus-Lite （NTT）
Before getting into the details of PROTEUS-Lite, let me summarize the characteristics of telecommunications circuits. We analyzed many telecommunications circuits, and found that they share a number of characteristics. First of all, they have a lot of latches for data pipelines and counters. Second, there are many pattern matching circuits because data checking is always required in order to synchronize the data stream and to extract the data structure such as packets and cells. Moreover, the data almost always moves from left to right. These characteristics were deeply considered when the original PROTEUS FPGA was designed, and we were in fact able to build an FPGA with many latches, with a structure that easily realizes pattern patching, and a routing resource structure that smoothly establishes left-to-right signal propagation. Thus, this time around, we concentrated on improving the routability without sacrificing any these good qualities of PROTEUS. Wide Bit Programmable Interconnection ( Directional ) Logic Block (Lookup Table) Latches Pipelining (Synchronous) F D Large number of latches This slide is supported by Dr.Miyazaki of NTT.

52 Structure of PROTEUS-Lite
This shows an overview of PROTEUS-Lite. This is an SRAM-based FPGA, and consists of basic cells, IO blocks and routing resources. Basically, this is a symmetrical routing resource architecture. However, there are twice as many horizontal middle line tracks as vertical ones. This ratio was determined based on the evaluation results shown in the last slide. Each middle line has one basic cell length, and a long line runs over half of the chip. Four IOBs construct an IO cell or IOC, and both the IOC and BC have the same connection topology for the surrounding routing resources. This homogeneous wiring topology simplifies the routing algorithm. Now, let's look at each part in detail. IOC: I/O Cell BC: Basic Cell Long Lines Middle Lines This slide is supported by Dr.Miyazaki of NTT.

53 DRAM混載型FPGA（NEC) 256 X 256 DRAM Module Logic Element Word Driver(128)
Sense　Amp．(128) Sense　Amp．(128) Logic Element Logic Element Word　Driver(128)

54 問題の解決 ２ アルゴリズムを変換するための標準的方法が存在しない 問題サイズがシステムサイズを越えるとお手上げ CPUとの混載、分担処理
問題の解決　２ アルゴリズムを変換するための標準的方法が存在しない CPUとの混載、分担処理 DA,Compile技術の発展 データフロー型実行 問題サイズがシステムサイズを越えるとお手上げ Partial　Reconfiguration Multi-context　FPGA 仮想ハードウェアの研究が進む

55 ＰＣＡ（Plastic Cell Architecture）
16word x 1bit memory（LUT) 12コマンドを実行する ハードウェアコントローラ 16bits output: 1bit Built-in Part 14bits input: 1bit Logic/メモリ 双方の利用可 Plastic Part 7 16bits 本能の規模はかなり大きくなる(デッドロックを十分に回避しようとすると2000ゲート程度)ので、本能1個に可変部1個というわけにはいかない。本能のオーバヘッドをバランスさせるために、可変部は複数の可変部セル(OHP3の構造)からなるものとする。 14bits 可変部 control: 6bits data: 8bits 7 基本セル→これがさらに格子状接続する

56 マルチコンテキストFPGAの基本構造 ページ間の共有 Partial Configuration との組み合わせ
PAGE1 Logic　Cells PAGE2 Multiplexer PAGE3 ページ間の共有 Partial Configuration との組み合わせ DRL(NEC)は実際に利用可能

57 SRAM型マルチコンテキストFPGA （基本的なもの）
MPLD（Multi-functional Programmable Logic Device） 富士通，1990 WASMII 慶大，1992 Time　Multiplexed　FPGA，Xilinx，1997

58 マルチコンテキスト型FPGA （最近の実現例）
FIPSOC（Field Programmable System On Chip) 混載チップ、2　Context、片方を利用中にもう片方を設定可 Context　Switching　FPGA，　Sanders A Lockheed Martin Company コンテキスト間のデータ共有 Partial　Configuration DRL， NEC　 ８　Context，部分的な切り替え可能

59 CSRC Device （Context Switching Reconfigurable Computing）
Clock Enable あるContextがActiveの間でも、別のContextをDownload可能 Contextの切り替えに５nｓ Private/Public Addressable Sharing (P/PASS) ４ Input ROM （Look Up Table) MUX EN D Q MUX F/F Back Up RAM（SRAM)

60 動的再構成ロジックDRL マルチコンテキスト構成を持つ部分再構成可能な論理デバイス（8コンテキスト） チップ全体の構成 論理ブロックの構成
4×12の論理ブロック（Logic Block, LB） 外部入出力用の制御回路 論理ブロックの構成 4×4の統合セル（Unified Cell, UC） 動的再構成制御回路（Reconfiguration Controller, RC) バスコネクタ（Bus Connector, BC）

61 DRL LB:論理ブロック LB LB Configuration/Data Input(79b) Input Select
External Config. Control(4b) Address Decoder Config. Store Control(2b) Reset CLK Output Select Configuration/Data Output(79b) Configuration　Store　Address(10b) LB:論理ブロック Data Config Vertical Local Bus (4b×2) (3b×2) Horizontal Local Bus Memory UC：統合セル RC：再構成制御回路 BC:バスコネクタ RC UC Global Bus Switch BC Input Selector LB Output Selector BC RC UC

62 WASMIIアーキテクチャ アプリケーションをデータフローグラフで表現 1ページに収まる単位のサブグラフに分割
トークンルータ アプリケーションをデータフローグラフで表現 1ページに収まる単位のサブグラフに分割 チップ内のコンテキスト数は4から8程度 外部メモリからの結線情報の読み込みがボトルネック Active　Page コンテキスト1 結線情報 コンテキストn ページコントローラ 入力トークン レジスタ バックアップメモリ

63 WASMIIシステム Page Controller Page Controller FPGA Page Controller Page1
Token Router Page Controller Page Controller FPGA Page1 Page2 Page3 Configuration Data line Page　ｎ Page Controller Input Token Registers

64 WASMIIシステム FPGA Page Controller Page1 Page2 Page2 Page3 Page ｎ
Token Router FPGA Page1 Page2 Page2 Page3 Configuration Data line Page　ｎ Backup RAM External Input Token Registers Page Controller Input Token Registers

65 PipeRench Architecture（CMU）
Global buses PE PE PE PE Pass registers ・ ・ ・ Interconnection PE PE PE PE stripe ・ ・ ・ Interconnection

66 Pipelined Reconfiguration
Cycle: 3 1 2 5 4 3 6 4 5 1 2 1 4 2 3 Stage 1 Stage 2 大きなlogical designを小さなハードウェアの迅速な書き換えによって実現する方法 Stage 3 Virtual pipeline Stage 4 Stage 5 Cycle: Stage 1 Physical pipeline Stage 2 Stage 3

67 アプリケーション 頻繁にプログラム変更のないもの IEEE標準浮動小数点演算を用いない メモリバウンドでない
画像処理、解析、パタンマッチング 論理シミュレーション、故障シミュレーション ニューラルネットワークシミュレーション 暗号化処理、解読処理 Queuing　Model、Markov解析 電力潮流計算 センサ処理 混載I/Oを利用できるもの 通信処理、プロトコル制御 ソフトウェア無線

68 Reconfigurable Systemのまとめ
Reconfigurable　SystemはいよいよCommercial　Levelに達しつつある 半導体技術の進展の恩恵を直接享受できる システムLSI化によりCPU、I/Oと同一チップに混載可能となった DA、Compile技術が鍵 キラーアプリは通信制御か？

69 まとめ システムLSI時代の到来により、様々な並列アーキテクチャが再び実現される可能性がある。
しかし、滅んで行ったものにはそれなりの理由がある。

70 演習 8行8列の3重対角型行列Aと8行のベクトルxをシストリックアレイで演算するのに要するクロック数を求めよ。ただし、xを左端のアレイに最初に格納する時刻を1と考える。