進藤/修士論文
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
//研究室限定
[[進藤/行ってきた研究(2006/8〜)]]
*行列演算の局所性に着目したアレイプロセッサのためのメモリ階層の設計 [#g941044a]
論文貼り付けたら超読みずれぇwww~
スルーしてください。。。m(__)m~
**タスク [#ec395969]
-論文まとめに入る->その辺についてもう一度先生としっかり話をつける。
-英語化->ぼちぼちしっかり添削してもらう。来週頭には副査の先生にも提出。
-IF周辺、制御周辺 ->把握しかけ。行ける気がする。(ML555に限るw)
-テスト、結果算出、理論値計算。->理論値計算は十八番。実装は…
~
~
**論文用まとめ [#z439884f]
***背景 [#j404dea5]
並列処理は一般的に科学計算、信号処理、メディア処理などの分野において有効であることが知られている。画素、音声サンプリング等を行列形式で表現し、その行列に対して簡単な演算を繰り返し用いることで、処理を実現するのが一般的である。それ故、行列演算をいかに効率的に扱うかということは重要であり、近年において、Intel Itanium2[1] 、IBM PowerPC G4[2] 、Sony/Toshiba/IBM Cell processor[3] などの商用プロセッサにおいても、ALUとは別にfused multiply-addやfused multiply-accumulation(fma)と呼ばれる行列演算専用の演算器が用意されており、行列演算の高速処理に貢献している。~
また、並列化による性能向上のために、プロセッサコアの数に応じてスケーラブルに性能向上できるアーキテクチャの研究が進んでいる。現在のチップマルチプロセッサはQuad Core AMD opteron[4] やIntel Core 2 Duo[5] 等、2~4コア搭載のタイプが主流であるが、さらに並列化を進めたプロセッサとして、米国サン・マイクロシステムズの8コア最大64スレッドを同時実行可能なUltra SPARC T2[6] 、米国インテルの数十コアを搭載したLarrabee[7] , Tileraの64コア搭載したTILE64[8] などが研究、開発されている。~
シストリックアレイプロセッサ[9] も並列処理を行う上で有用なプロセッサの一つである。シストリックアレイプロセッサとは専用プロセッサエレメント(PE)をメッシュ、トロイダルメッシュなどの様々なルールに従って接続されている計算ネットワークであり、大量の同一演算を高速に行う事ができる。~
しかし、シストリックアレイにおいて、演算の汎用性を高めようとすればするほど、PE間の接続は複雑になり、処理性能や拡張性に影響が出てしまう。その問題を解決するため、S. G. Sedukhinらは特定の行列演算に特化したアーキテクチャとして、”Rapid MatriX”(以下RMX)[10] を提案した。RMXはプロセッサエレメント(PE)をトーラス状に接続した構造になっている。各PEは3入力fused operation unit(FOU)とレジスタファイルを搭載しており、PE間でデータを特定の方向にシフトさせ、演算する。そのため、複雑なデータ制御を必要とせずに、行列演算を行うことができる。~
しかし、RMXの問題点として、リソースの限界により作成できるプロセッサの規模に限界がある事、ホスト−プロセッサ間の制御命令がないことから、大規模な行列の演算に対応することができない事、RMXは記憶領域として少数のレジスタしか内蔵していないため、保持できるデータ量が限定され、ホストとのやり取りが頻繁になる。その際のデータの入出力に伴うI/O操作が性能のボトルネックになる事が挙げられる。~
本稿では、巨大な行列の演算に対応しつつ、データ転送を円滑に行うことを可能にするため、上記アーキテクチャで実装されているメモリ階層を、行列演算の特性(時間的局所性)の観点から再考慮し、多段化する。また、その階層間のデータ転送および演算をホスト側から考慮した制御命令を提案する。~
この提案アーキテクチャにより、巨大行列に対応可能なメモリ階層および制御命令が完成し、ホストからの制御による汎用的な行列演算が可能となる。~
~
***RapidMatriXとその問題点 [#l4fb1c2f]
記憶階層の重要性は、プロセッサの性能向上と共に大きくなっている。一般に、プロセッサに必要な主記憶の容量は1MIPSあたり1Mbyteであるといわれており、現在の高性能プロセッサの主記憶は数百Mbyteの容量を必要とする。しかし、これに追従するようなアクセス速度と容量を持つメモリは存在しないか、あるいはひどく高価なものとなる。そこで、データの時間的、空間的局所性を考慮し、高速/小容量のメモリと低速/大容量のメモリを組み合わせて記憶階層を構成する必要がある。~
複数レベルでのメモリ階層の説明は次の通りである。レジスタはプロセッサの中に用意された記憶媒体で、非常に高速にアクセスできるが、個数は限定される。キャッシュメモリはプロセッサとメインメモリの間に介在し、メインメモリの一部のデータと命令を取り込んで、プロセッサがより高速にデータや命令にアクセスできるようにする。メインメモリはプログラムを構成する命令やデータを記憶しておくという機能と、プロセッサの要求に応じて必要な命令やデータをプロセッサに渡すと共に、データを指定された場所に書き込む機能がある。ディスクは大容量であるが、アクセス時間は遅い。~
RMXの問題点の一つはメモリ階層である。現在の構成では、PEの内部レジスタの他に(主な、大きな)記憶媒体は無く、部分行列の演算が終わるたびに新たなデータを外部(HOST)から読み込んでこなければならない。その際のデータの入出力に伴うI/O操作がPE内での演算、シフトよりはるかに遅いため、性能のボトルネックになる可能性が高い。そのため、巨大な行列演算に対応するためには、PE内レジスタの他に、キャッシュ、メインメモリ等の記憶媒体を用意し、時間的、空間的局所性を考慮し、データの転送がボトルネックとならないメモリ階層を構成する必要がある。~
~
現在のマクロ命令はPEを直接操作するマイクロ命令と、繰り返し回数を指定するcounter fieldのみで構成されている。マイクロ命令の種類も、即値をPEに書き込むLOAD命令、データを隣接のPEにシフトさせるMOVE命令、そして演算とシフトを行うFMA命令の三つのみである。このことかわ分かる通り(?)、現在のマクロ命令では、(Rapid MatriXと)On-board RAMなど外部記憶媒体とのデータ転送に関する命令が存在していない。また、有効なアセンブリ言語が提供されていないため、大規模な行列を操作する際には命令が複雑化してしまい、ユーザーレベルでのプログラミングが煩雑になってしまう。この問題を解決するためには、メモリ階層を考慮した上で、マクロ命令を再考慮し、大規模な行列演算をサポートし、メモリ階層間のデータ制御をホストから行うRMX 専用アセンブリ言語(API?)を考える必要がある。~
~
***解決案 [#k08a6343]
-block algorthm を使用して、行列を小さい単位に分けて計算->無理にレジスタを取らなくてよい
-FIFOバッファを用意し、一度転送したデータを何度も再利用することで転送を減らす->空間的局所性を利用
-ホスト側から制御できるAPIの開発->演算だけでなく、データ転送も直接制御できるようになる
***現在の実装状態 [#l3bb2a23]
-今までのRMXの構成を変更
--レジスタ数をA,Bひとつ、C二つ(演算と同時に次のデータセットを可能に。)
--I/Oにバッファを取り付けた -> 8x8, 16x16は作ったが他は作ってない。
--PE array, processor_top 自動生成プログラムの作成->手書きでは絶対不可能
--命令制御部・memory IF 作成中。命令制御部はmicro-instructionを使用。めんどい。
--参考書に乗ってるFIFOがエラーを吐く。mfで代用。現在乗算器とFIFOでmfを使っている。
***その他アイデア、メモ、現状、雑記。 [#yf583bb1]
**ミーティング [#s122e5af]
***12/16 [#r691898d]
-task
--RMX<Axx だとしたとき、バッファの限界考察
--N^3とstrassen どちらがいいのか…ヤマキが考える
--インストラクションの確定(strassen, normal op)
--Host からのコマンドを受け取る -> 割り込み(みとめ)
--Host に割り込みをかける ->割り込み(みとめ)
***[[進藤/過去のミーティング内容]] [#e9cc3cc0]
終了行:
//研究室限定
[[進藤/行ってきた研究(2006/8〜)]]
*行列演算の局所性に着目したアレイプロセッサのためのメモリ階層の設計 [#g941044a]
論文貼り付けたら超読みずれぇwww~
スルーしてください。。。m(__)m~
**タスク [#ec395969]
-論文まとめに入る->その辺についてもう一度先生としっかり話をつける。
-英語化->ぼちぼちしっかり添削してもらう。来週頭には副査の先生にも提出。
-IF周辺、制御周辺 ->把握しかけ。行ける気がする。(ML555に限るw)
-テスト、結果算出、理論値計算。->理論値計算は十八番。実装は…
~
~
**論文用まとめ [#z439884f]
***背景 [#j404dea5]
並列処理は一般的に科学計算、信号処理、メディア処理などの分野において有効であることが知られている。画素、音声サンプリング等を行列形式で表現し、その行列に対して簡単な演算を繰り返し用いることで、処理を実現するのが一般的である。それ故、行列演算をいかに効率的に扱うかということは重要であり、近年において、Intel Itanium2[1] 、IBM PowerPC G4[2] 、Sony/Toshiba/IBM Cell processor[3] などの商用プロセッサにおいても、ALUとは別にfused multiply-addやfused multiply-accumulation(fma)と呼ばれる行列演算専用の演算器が用意されており、行列演算の高速処理に貢献している。~
また、並列化による性能向上のために、プロセッサコアの数に応じてスケーラブルに性能向上できるアーキテクチャの研究が進んでいる。現在のチップマルチプロセッサはQuad Core AMD opteron[4] やIntel Core 2 Duo[5] 等、2~4コア搭載のタイプが主流であるが、さらに並列化を進めたプロセッサとして、米国サン・マイクロシステムズの8コア最大64スレッドを同時実行可能なUltra SPARC T2[6] 、米国インテルの数十コアを搭載したLarrabee[7] , Tileraの64コア搭載したTILE64[8] などが研究、開発されている。~
シストリックアレイプロセッサ[9] も並列処理を行う上で有用なプロセッサの一つである。シストリックアレイプロセッサとは専用プロセッサエレメント(PE)をメッシュ、トロイダルメッシュなどの様々なルールに従って接続されている計算ネットワークであり、大量の同一演算を高速に行う事ができる。~
しかし、シストリックアレイにおいて、演算の汎用性を高めようとすればするほど、PE間の接続は複雑になり、処理性能や拡張性に影響が出てしまう。その問題を解決するため、S. G. Sedukhinらは特定の行列演算に特化したアーキテクチャとして、”Rapid MatriX”(以下RMX)[10] を提案した。RMXはプロセッサエレメント(PE)をトーラス状に接続した構造になっている。各PEは3入力fused operation unit(FOU)とレジスタファイルを搭載しており、PE間でデータを特定の方向にシフトさせ、演算する。そのため、複雑なデータ制御を必要とせずに、行列演算を行うことができる。~
しかし、RMXの問題点として、リソースの限界により作成できるプロセッサの規模に限界がある事、ホスト−プロセッサ間の制御命令がないことから、大規模な行列の演算に対応することができない事、RMXは記憶領域として少数のレジスタしか内蔵していないため、保持できるデータ量が限定され、ホストとのやり取りが頻繁になる。その際のデータの入出力に伴うI/O操作が性能のボトルネックになる事が挙げられる。~
本稿では、巨大な行列の演算に対応しつつ、データ転送を円滑に行うことを可能にするため、上記アーキテクチャで実装されているメモリ階層を、行列演算の特性(時間的局所性)の観点から再考慮し、多段化する。また、その階層間のデータ転送および演算をホスト側から考慮した制御命令を提案する。~
この提案アーキテクチャにより、巨大行列に対応可能なメモリ階層および制御命令が完成し、ホストからの制御による汎用的な行列演算が可能となる。~
~
***RapidMatriXとその問題点 [#l4fb1c2f]
記憶階層の重要性は、プロセッサの性能向上と共に大きくなっている。一般に、プロセッサに必要な主記憶の容量は1MIPSあたり1Mbyteであるといわれており、現在の高性能プロセッサの主記憶は数百Mbyteの容量を必要とする。しかし、これに追従するようなアクセス速度と容量を持つメモリは存在しないか、あるいはひどく高価なものとなる。そこで、データの時間的、空間的局所性を考慮し、高速/小容量のメモリと低速/大容量のメモリを組み合わせて記憶階層を構成する必要がある。~
複数レベルでのメモリ階層の説明は次の通りである。レジスタはプロセッサの中に用意された記憶媒体で、非常に高速にアクセスできるが、個数は限定される。キャッシュメモリはプロセッサとメインメモリの間に介在し、メインメモリの一部のデータと命令を取り込んで、プロセッサがより高速にデータや命令にアクセスできるようにする。メインメモリはプログラムを構成する命令やデータを記憶しておくという機能と、プロセッサの要求に応じて必要な命令やデータをプロセッサに渡すと共に、データを指定された場所に書き込む機能がある。ディスクは大容量であるが、アクセス時間は遅い。~
RMXの問題点の一つはメモリ階層である。現在の構成では、PEの内部レジスタの他に(主な、大きな)記憶媒体は無く、部分行列の演算が終わるたびに新たなデータを外部(HOST)から読み込んでこなければならない。その際のデータの入出力に伴うI/O操作がPE内での演算、シフトよりはるかに遅いため、性能のボトルネックになる可能性が高い。そのため、巨大な行列演算に対応するためには、PE内レジスタの他に、キャッシュ、メインメモリ等の記憶媒体を用意し、時間的、空間的局所性を考慮し、データの転送がボトルネックとならないメモリ階層を構成する必要がある。~
~
現在のマクロ命令はPEを直接操作するマイクロ命令と、繰り返し回数を指定するcounter fieldのみで構成されている。マイクロ命令の種類も、即値をPEに書き込むLOAD命令、データを隣接のPEにシフトさせるMOVE命令、そして演算とシフトを行うFMA命令の三つのみである。このことかわ分かる通り(?)、現在のマクロ命令では、(Rapid MatriXと)On-board RAMなど外部記憶媒体とのデータ転送に関する命令が存在していない。また、有効なアセンブリ言語が提供されていないため、大規模な行列を操作する際には命令が複雑化してしまい、ユーザーレベルでのプログラミングが煩雑になってしまう。この問題を解決するためには、メモリ階層を考慮した上で、マクロ命令を再考慮し、大規模な行列演算をサポートし、メモリ階層間のデータ制御をホストから行うRMX 専用アセンブリ言語(API?)を考える必要がある。~
~
***解決案 [#k08a6343]
-block algorthm を使用して、行列を小さい単位に分けて計算->無理にレジスタを取らなくてよい
-FIFOバッファを用意し、一度転送したデータを何度も再利用することで転送を減らす->空間的局所性を利用
-ホスト側から制御できるAPIの開発->演算だけでなく、データ転送も直接制御できるようになる
***現在の実装状態 [#l3bb2a23]
-今までのRMXの構成を変更
--レジスタ数をA,Bひとつ、C二つ(演算と同時に次のデータセットを可能に。)
--I/Oにバッファを取り付けた -> 8x8, 16x16は作ったが他は作ってない。
--PE array, processor_top 自動生成プログラムの作成->手書きでは絶対不可能
--命令制御部・memory IF 作成中。命令制御部はmicro-instructionを使用。めんどい。
--参考書に乗ってるFIFOがエラーを吐く。mfで代用。現在乗算器とFIFOでmfを使っている。
***その他アイデア、メモ、現状、雑記。 [#yf583bb1]
**ミーティング [#s122e5af]
***12/16 [#r691898d]
-task
--RMX<Axx だとしたとき、バッファの限界考察
--N^3とstrassen どちらがいいのか…ヤマキが考える
--インストラクションの確定(strassen, normal op)
--Host からのコマンドを受け取る -> 割り込み(みとめ)
--Host に割り込みをかける ->割り込み(みとめ)
***[[進藤/過去のミーティング内容]] [#e9cc3cc0]
ページ名: