星野/研究
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[星野]]
&size(25){''Research''};
#contents
*Research Topic [#ee5f508c]
Advanced optimization Algorithem for QueueCore Processor
-Problem
--Queue overflow problem
--Interrupt problem
--Subroutine call problem
*Tools [#b095a093]
-Simulation
--NC-verilog
---学校の環境
& ncverilog +ncaccess+rwc verilog.v
--verilog-XL
---学校の環境
& verilog verilog.v
--VPI lablary
---$CDS_INST_DIR = /usr/local/cadence/IUS5.6/tools/include
gcc -c -g -l$CDS_INST_DIR/tools/include pli.c
ld -shared -E -o libvpi.so pli.o
--iverilog
---WINDOWSあり(要cygwin)
& iverilog -o my_design verilog.v
& vvp my_design
---[[詳細>星野/日誌/2009-10-06]]
-Waveform veiwer
--simvision
---学校の環境
& simvision &
--GTKwave
---WINDOWSあり
---[[詳細>星野/日誌/2009-10-07]]
*Queue Core 3 (凍結)[#s1aebae2]
**ISA [#f177e14e]
:[[ISA>星野/研究/QC-3/ISA]]|Instruction Set Architecture
**論点(メモ) [#dca89106]
-QO
--今の解決法ではなく、単純にQREGを多くするのはダメか?
---キューを多くとるのはメリットがある
--低消費電力を期待できるか
-LQH
--レジスタを参照するのと、新しく読んで参照するのとどちらが早いか。
---単純にはレジスタ参照のほうが早いが、新しく命令を追加するため、その分遅い
---そのデータからたくさん矢印が出てる場合は有効だと思うが、2本とかだと効果が薄いかも
*Queue Core 2 [#e9f4829c]
**仕様 [#w8b39e99]
-4-way superscalar machine
-fixed 16-bit instructions
-6 stage pipeline
-memory access extention instruction
-ready bit to check dependency
-offset reference
**問題点 [#i9664709]
-オフセット
--もらったコードには、オペランドをオフセットにすることができない
--常にきまった場所から、データを取ってきていた
*GT topic [#nd59ddd2]
Queue overflow problem
**Back Ground [#t1fd0edd]
今までのデザインでは、キューレジスタは無限にあるという想定のもと設計されてきた。しかし、実際は限りあるものである。そのため、使う必要のあるデータの上に結果が上書きされてしまう可能性がある。それを解決することがこの研究の趣旨である。
**Introduction [#i9bc0c2a]
キュープロセッサは3つのポインタを持っていて、それにより内部でレジスタのアドレスを計算する。それにより、レジスタマシンの命令セットアーキテクチャでは命令でアドレス指定していた部分をこのプロセッサでは単にオペコードだけ指定することで実行することが可能である。ゆえにコードサイズが小さくできる特徴をもつ。~
3つのポインタはそれぞれ、QH、QT、LQHというレジスタである。計算をするときはいつもQHの示すアドレスのレジスタからデータをとり、結果をQTに書き込む。またLQHとQHの間はまだ使われる予定があるデータがある領域を示している。~
キューオーバーフローはLQHとQTが同じ時に起こる。これはまだ使われる予定があるデータがLQHに入っている状態で、LQHのアドレスと同じアドレスをもつQTに結果を書き込もうとするからである。この問題を解決する方法として2つのアプローチを考えた。1つ目はレジスタ退避である。2つ目はキューレジスタを拡張する方法である。
**Assumption [#nb8902e5]
まずはこのサイズでやってみる。~
アルゴリズムが確立したら、他のサイズでもやってみる。
|Queue Register|16|
|Spill Register|16|
|Extended Queue Register|16|
**Solution approach [#vaf8b55d]
-Spill Register
--Method
+++オーバーフローを検知する
+++オーバーフローしたレジスタのアドレスを保持しておく
+++QTから戻ってN個のデータをSRにコピーする(退避)
+++QTをN個戻す
+++通常の計算に戻る
+++オーバーフローしたレジスタとQHが同じ(退避したものが必要となった)ことを検知する
+++QCUでストールさせる。
+++通常計算した分をN個分すすめてコピーする
+++退避した値を元に戻す
+++通常の計算に戻る
--Appropriate number of N
---!ここを考える!
--Problem
---レジスタToレジスタのコピーをする命令が必要
---サイクルが余計にかかる
-Extended Queue Register
--Method
+++オーバーフローを検知する
+++オーバーフローした場所を保持しておく
+++QTをEQREGのQTに変える
+++通常計算をする
+++QHがオーバーフローしたところにきたら、QHをEQREGのQHに変える
+++EQREG_QH、EQREG_QTが最後まで(0xF)まで来たらQH,QTを元に戻す
--Appropriate number of extended QREG
---これも退避するのと同じくどれくらい必要なのか調べる必要がある。
---ベンチマークとQREGのサイズによる。
--Advantage
---こちらはQCUでレジスタアドレスの計算をやればいいだけ
---特にレジスタを移動することなく実行できるため速い
---そのため今回はこちらを採用する
**Benchmark test [#p1114059]
***今考えているテストは以下の通り [#qca796ae]
-FFT
--8点のFFT。実際の計算ではなくて、簡略化したバタフライにするかも。
-LU
--できれば大きいほうがいいが。
--4×4のマトリックスを分解する。
-Prefix
--8点から16点くらいを予定
-Newton
--なかみがよくわからないから、増田君にお願いする予定
-Sort
--8点の並べ替えを予定。
***レジスタサイズ調査 [#g7f55ce8]
-各ベンチマークを実行するために必要なレジスタの数
|Benchmark|Needed Number of register|h
|FFT 8|26|
|Butterfly 8|16|
|LU 3x3|12|
|Newton 4|24|
|Prefix 8|13|
~
|Max|26|
|Min|12|
|Ave|18.2|
-今あるベンチマークによるとQREGのサイズを16個にする場合は2つのベンチマークが問題なく通る
-ただし、3つのベンチマークが通らないため、QREGのオーバーフローが発生する。
-EXQREGのサイズを16個にすれば、すべてのベンチマークが通る
***問題 [#ndfe012e]
今、オーバーフローするかどうかを考えるきに、QREGのサイズを8個と想定してやっている。このときはオーバーフローするが、16個でやるとしないと思われる。そこで、もっと大きいベンチマークを用意する必要がある。
*About Queue Computing [#m038a831]
**Queue computing model [#a2ebe4bf]
We adopt the QP computing model.
-Produced consumed order queue computation(QPC)
--Instructions take operand from QH and insert result to QT
--Example
---LD data (means QT <= mem[data])
---ADD (means QT <= (QH) + (QH+1))
-Produced order queue computation(QP)
--Instructions take operands from QH or QH + offset, and insert result to QT
--Example
---ADD +3 (means QT <= (QH) + (QH+3))
-Consumed order queue computation(QC)
--Instructions take operands from QH, and insert result to QT or QT + offset
--Example
---ADD +3 (means (QT+3) <= (QH) + (QH+1))
*Queue Benchmark program [#f4a1c66e]
-FFT8 (only real part completed)
-LU (completed)
-Prefix (making)
-Sort (not start)
/************************************************/
*What I do now [#d58a0864]
-Queue Coreのソースコード
--受け取りました(7/3)
--バグがあるので改善して、最適化します。
-FFTのアセンブリを書くために、フーリエ変換とかの勉強中
--とりあえず、マンガでわかる・・・みたいなやつが図書館で読んだ(6/20)
---授業で習った時はよくわからなかったけど、音と関連付けて書いてあって面白かった。
---FFTまでの道のりは遠い気がする。
*ToDo List [#k8eb0c29]
+'''''Understand the QueueCore architecture'''''
+Think about the Queue Overflow Algorithem (QOA)
+Study the verilog-HDL codes and make for simulation
+Implement the QOA into the QueueCore
+Make simulation
++write small assembly program (FFT, matrix, math...)
/************************************************/
*Read Papers [#yb114bdc]
-Fundamental Design of a Parallel Queue Processor
-Modular Design Structure and High-Level Prototyping for Novel Embedded Processor Core
*Referrence [#jd7d3973]
-http://webfs-int.u-aizu.ac.jp/%7Ebenab/research/projects/QueueCore/
終了行:
[[星野]]
&size(25){''Research''};
#contents
*Research Topic [#ee5f508c]
Advanced optimization Algorithem for QueueCore Processor
-Problem
--Queue overflow problem
--Interrupt problem
--Subroutine call problem
*Tools [#b095a093]
-Simulation
--NC-verilog
---学校の環境
& ncverilog +ncaccess+rwc verilog.v
--verilog-XL
---学校の環境
& verilog verilog.v
--VPI lablary
---$CDS_INST_DIR = /usr/local/cadence/IUS5.6/tools/include
gcc -c -g -l$CDS_INST_DIR/tools/include pli.c
ld -shared -E -o libvpi.so pli.o
--iverilog
---WINDOWSあり(要cygwin)
& iverilog -o my_design verilog.v
& vvp my_design
---[[詳細>星野/日誌/2009-10-06]]
-Waveform veiwer
--simvision
---学校の環境
& simvision &
--GTKwave
---WINDOWSあり
---[[詳細>星野/日誌/2009-10-07]]
*Queue Core 3 (凍結)[#s1aebae2]
**ISA [#f177e14e]
:[[ISA>星野/研究/QC-3/ISA]]|Instruction Set Architecture
**論点(メモ) [#dca89106]
-QO
--今の解決法ではなく、単純にQREGを多くするのはダメか?
---キューを多くとるのはメリットがある
--低消費電力を期待できるか
-LQH
--レジスタを参照するのと、新しく読んで参照するのとどちらが早いか。
---単純にはレジスタ参照のほうが早いが、新しく命令を追加するため、その分遅い
---そのデータからたくさん矢印が出てる場合は有効だと思うが、2本とかだと効果が薄いかも
*Queue Core 2 [#e9f4829c]
**仕様 [#w8b39e99]
-4-way superscalar machine
-fixed 16-bit instructions
-6 stage pipeline
-memory access extention instruction
-ready bit to check dependency
-offset reference
**問題点 [#i9664709]
-オフセット
--もらったコードには、オペランドをオフセットにすることができない
--常にきまった場所から、データを取ってきていた
*GT topic [#nd59ddd2]
Queue overflow problem
**Back Ground [#t1fd0edd]
今までのデザインでは、キューレジスタは無限にあるという想定のもと設計されてきた。しかし、実際は限りあるものである。そのため、使う必要のあるデータの上に結果が上書きされてしまう可能性がある。それを解決することがこの研究の趣旨である。
**Introduction [#i9bc0c2a]
キュープロセッサは3つのポインタを持っていて、それにより内部でレジスタのアドレスを計算する。それにより、レジスタマシンの命令セットアーキテクチャでは命令でアドレス指定していた部分をこのプロセッサでは単にオペコードだけ指定することで実行することが可能である。ゆえにコードサイズが小さくできる特徴をもつ。~
3つのポインタはそれぞれ、QH、QT、LQHというレジスタである。計算をするときはいつもQHの示すアドレスのレジスタからデータをとり、結果をQTに書き込む。またLQHとQHの間はまだ使われる予定があるデータがある領域を示している。~
キューオーバーフローはLQHとQTが同じ時に起こる。これはまだ使われる予定があるデータがLQHに入っている状態で、LQHのアドレスと同じアドレスをもつQTに結果を書き込もうとするからである。この問題を解決する方法として2つのアプローチを考えた。1つ目はレジスタ退避である。2つ目はキューレジスタを拡張する方法である。
**Assumption [#nb8902e5]
まずはこのサイズでやってみる。~
アルゴリズムが確立したら、他のサイズでもやってみる。
|Queue Register|16|
|Spill Register|16|
|Extended Queue Register|16|
**Solution approach [#vaf8b55d]
-Spill Register
--Method
+++オーバーフローを検知する
+++オーバーフローしたレジスタのアドレスを保持しておく
+++QTから戻ってN個のデータをSRにコピーする(退避)
+++QTをN個戻す
+++通常の計算に戻る
+++オーバーフローしたレジスタとQHが同じ(退避したものが必要となった)ことを検知する
+++QCUでストールさせる。
+++通常計算した分をN個分すすめてコピーする
+++退避した値を元に戻す
+++通常の計算に戻る
--Appropriate number of N
---!ここを考える!
--Problem
---レジスタToレジスタのコピーをする命令が必要
---サイクルが余計にかかる
-Extended Queue Register
--Method
+++オーバーフローを検知する
+++オーバーフローした場所を保持しておく
+++QTをEQREGのQTに変える
+++通常計算をする
+++QHがオーバーフローしたところにきたら、QHをEQREGのQHに変える
+++EQREG_QH、EQREG_QTが最後まで(0xF)まで来たらQH,QTを元に戻す
--Appropriate number of extended QREG
---これも退避するのと同じくどれくらい必要なのか調べる必要がある。
---ベンチマークとQREGのサイズによる。
--Advantage
---こちらはQCUでレジスタアドレスの計算をやればいいだけ
---特にレジスタを移動することなく実行できるため速い
---そのため今回はこちらを採用する
**Benchmark test [#p1114059]
***今考えているテストは以下の通り [#qca796ae]
-FFT
--8点のFFT。実際の計算ではなくて、簡略化したバタフライにするかも。
-LU
--できれば大きいほうがいいが。
--4×4のマトリックスを分解する。
-Prefix
--8点から16点くらいを予定
-Newton
--なかみがよくわからないから、増田君にお願いする予定
-Sort
--8点の並べ替えを予定。
***レジスタサイズ調査 [#g7f55ce8]
-各ベンチマークを実行するために必要なレジスタの数
|Benchmark|Needed Number of register|h
|FFT 8|26|
|Butterfly 8|16|
|LU 3x3|12|
|Newton 4|24|
|Prefix 8|13|
~
|Max|26|
|Min|12|
|Ave|18.2|
-今あるベンチマークによるとQREGのサイズを16個にする場合は2つのベンチマークが問題なく通る
-ただし、3つのベンチマークが通らないため、QREGのオーバーフローが発生する。
-EXQREGのサイズを16個にすれば、すべてのベンチマークが通る
***問題 [#ndfe012e]
今、オーバーフローするかどうかを考えるきに、QREGのサイズを8個と想定してやっている。このときはオーバーフローするが、16個でやるとしないと思われる。そこで、もっと大きいベンチマークを用意する必要がある。
*About Queue Computing [#m038a831]
**Queue computing model [#a2ebe4bf]
We adopt the QP computing model.
-Produced consumed order queue computation(QPC)
--Instructions take operand from QH and insert result to QT
--Example
---LD data (means QT <= mem[data])
---ADD (means QT <= (QH) + (QH+1))
-Produced order queue computation(QP)
--Instructions take operands from QH or QH + offset, and insert result to QT
--Example
---ADD +3 (means QT <= (QH) + (QH+3))
-Consumed order queue computation(QC)
--Instructions take operands from QH, and insert result to QT or QT + offset
--Example
---ADD +3 (means (QT+3) <= (QH) + (QH+1))
*Queue Benchmark program [#f4a1c66e]
-FFT8 (only real part completed)
-LU (completed)
-Prefix (making)
-Sort (not start)
/************************************************/
*What I do now [#d58a0864]
-Queue Coreのソースコード
--受け取りました(7/3)
--バグがあるので改善して、最適化します。
-FFTのアセンブリを書くために、フーリエ変換とかの勉強中
--とりあえず、マンガでわかる・・・みたいなやつが図書館で読んだ(6/20)
---授業で習った時はよくわからなかったけど、音と関連付けて書いてあって面白かった。
---FFTまでの道のりは遠い気がする。
*ToDo List [#k8eb0c29]
+'''''Understand the QueueCore architecture'''''
+Think about the Queue Overflow Algorithem (QOA)
+Study the verilog-HDL codes and make for simulation
+Implement the QOA into the QueueCore
+Make simulation
++write small assembly program (FFT, matrix, math...)
/************************************************/
*Read Papers [#yb114bdc]
-Fundamental Design of a Parallel Queue Processor
-Modular Design Structure and High-Level Prototyping for Novel Embedded Processor Core
*Referrence [#jd7d3973]
-http://webfs-int.u-aizu.ac.jp/%7Ebenab/research/projects/QueueCore/
ページ名: