計測自動制御学会東北支部 第  回研究集会   資料番号 

分散演算を用いた高性能 プロセッサのアーキテクチャ

                 
野崎剛  ，○齊藤優樹  ，恒川佳隆 ，田山典男    ○        
岩手大学大学院 工学研究科
     
キーワード

高速フーリエ変換    分散演算       低消費電力     小面積       ! 評価  ! "  連絡先

〒  #

盛岡市上田 $%&% 岩手大学 工学部

齊藤優樹，  '( ($(#， ) '( ($(#， *  まえがき
近年，ディジタル信号処理の応用分野の拡大に加えて，マルチメディア関連産業の出現に伴い，我々に身近な音声・画像・映像 動画像 などの情報表現を媒介にするアプリケーションが重要になってきている  ．スペクトル解析の主流であるフーリ
エスペクトル分析，そして高速フーリエ変換     は音声・画像認識アルゴ
リズムの基本操作であり，次世代ディジタル信号処理技術の中でますますその重要性が高まるものと考えられる．
 の一般的な構成法として，乗算器を用いたシグナルフローに基づく構成がある．この構成法は，滞在時間を小さくできるが，ハードウェア量が非常に大きい乗算器を多く用いるため， の入力点数が多い場合， への実現が困難となる．
本研究では，分散演算を用いた高性能  プロセッサの  アーキテクチャを提案する．小面積化を実現するために，内積演算をハードウェア量の大きい乗算器を用いずに，処理時間が語長のみに依存する分散演算に着目する．分散演算に基づく従来型の構成法として，を用いた構成が提 

案されている  ．この構成法は内積演算に乗算器を用いずに分散演算を用いることでハードウェア量が小さくなる．しかし，消費電力が大きいを多数用いるため，システム全体に膨大な消費電力が必要となる．
大幅な低消費電力を実現するために，我々が提案してきた最適関数回路の特長  に着目し，小面積化と低消費電力化を実現する  プロセッサの アーキテクチャを提案する．この構成法は入力変数を  ビットずつ入力させることから  ビット         プロセッサと呼ぶことにする．
 は入力点数が多くなるにつれて段数が増える．段数に比例して滞在時間が大きくなるため，滞在時間の減少も重要である．従来の分散演算による構成の滞在時間は各入力変数をビットずつ伝播するため語長に比例する．そこで，我々は滞在時間を減少するために，入力変数を複数ビット入力させることに着目して，滞在時間の減少が可能なプロセッサのアーキテクチャを新たに提案する．この構成法は入力変数を多ビットずつ入力させることから多ビットプロセッサと 呼ぶことにする．最後に， つの提案法を  設計，評価した結果， ビット  プロセッサは低消費電力化と小面積化をあわせ持った特長を有することを示し，多ビットプロセッサは分散演算による構成法において滞在時間の短縮が可能になることを示す．そしてこれらの有効性を明らかにする．

x(0)

A(0)

x(1)

-x(2)
x(3)

は離散フーリエ変換   とし，後半のデータ  を，  

#







$

        



¾



¾  



 #

#



W2A(5)
A(3)

+-W0
A(7)
-

周波数間引き型  の様子

AmWk+- An周波数間引き型のバタフライ演算¾

      

#  ¾)

    ¾

              

*



 



+,

となる．
  がさらに  で割り切れるときは，$ つの  $のデータを持つ離散フーリエ変換に置き換えることができ，このアルゴリズムを繰り返すことにより，より高速化が実現できる．  - の場合の高速フーリエ変換の処理過程を図  に示す．

周波数間引き型の基本演算

図  より，各段における演算は  つのデータ対の演算から構成されている．この演算をバタフライ演算という．バタフライ演算は，図  のようになっており，次式で表される．

  ¾  +-   ¾  

W3W0

は，





++としたとき， の離散フーリエ変換
W2

きは( となる．これより の偶数番目のスペクト
ルを  ，奇数番目を   とすると，

 



+A(1)
W0+xm

 &' 

" W1- &' 





+A(6)

 A(2)W0+-xn

サンプリング値  を前半と後半の  分割にする．前半の  ! のデータから構成されるサンプリング値を ，後半のデータから構成されるサンプリング値を  とする．前半のデータ  を，
W0-x(7)周波数間引き型 

+A(4)



なお， と  はそれぞれ入力点数，サンプリング値と回転因子である．は，式の回転因子   の周期性と対称性を利用したアルゴリズムである．

W2-            ¾
+-x(5)    の演算回数を大幅に減少させる手法である  ． は次式のようにあらわされる．

W0-x(4)       +-x(6)



W0+


%

となる．式%において に掛かる回転因子 ¾は，式より  が偶数のときは となり，奇数のと!

         ####

-. ここで， は，input¾ 


Register

SR(vN) ##

1bit shiftBbits

1bit

SR : Shift Register#Adder     

outputBbits
ROMであるから，式  を式 . に代入すると，
Bbits







1bit

SR(v1)

 &' "


 



"

となり実部と虚部に分けられる．
乗算器を用いた  プロセッサにおいて，ハードウェア量が大きい乗算器を   /&  個も必要とする．このことから，入力点数が増加するに従い，システム全体のハードウェア量が膨大になってしまうために，への実現が困難であるといえる．
そこで，次章ではハードウェア量の減少を図るため，乗算器を用いずに構成できる分散演算に着目する．

分散演算の基本構造である．ここで，分散演算の基本的な構成法を図"に示す．この構成では，      をアドレスとするに，入力変数の各ビットと係数との内積演算の結果 0 をテーブルとして書き込んでおき，計算時にはテーブルを参照して得られた値を順次 ビット右シフトしながら，加え合わせる操作を行なう．このように，分散演算は乗算器を用いずに，語長  回分のシフトと累積で内積演算を行う．

 分散演算を適用した アルゴリズムを乗算器を用いて行う場合， プロセッサのハードウェア量が大きくなってしまう．そこで，内積演算が乗算器を用いずに語長 回分のシフトと累積で計算できる分散演算をに適用する．
 はバタフライ演算を繰り返すことで計算を行っている．バタフライ演算を表す式 -1"において，式 " の実部と虚部は内積演算とみなすことができる．このことに着目して，式 " のバタフライ演算に分散演算を適用する．       とすると，式 " は，
! 分散演算アーキテクチャ
分散演算は，定係数の内積演算をテーブルルックアップによって実現する計算手法である．いま，項数  の係数ベクトル         と変数ベクトル          との内積

$

を考える．ただし，     で， は  ビットの固定小数点形の  の補数表示である．つまり，






#



     0#

0%     )

ただし，0 は     0 #となる．   を ビットの固定小数点形の の補

#-

数表示とすると，で， または  である．式 % を式 $ に代入すると，内積演算  は次式で示される．
#と表される．ここで， は  の  ビット目の値 

##

.

 と表される．ここで，   は    の  ビット目の値で， または  である．式 .1  を式 - に代入すると，

,

"



0   
# 0 

Φ ( v 1k , v 2k , Lv 1k v 2k L v nk

B − 10, v mk )Number of lines subtracted one fromthat of horizontal categoryB − 20w
L w 0000 L 0 w
00 L 1 w 1B − 1 w 1B − 2 L w 10inputoutput•N− 1Bpw− 2Bpw

w 2B m− −1 1 w 2B m− −2 1 L

11 L 1L0Pw

Partial functional
circuit forhorizontal category•

w 20 m − 1

Partial functional
circuit for verticalcategory

B bits(a) The first stageΦ ( v 1k , v 2k , L, v mk )B −1
hc 10hc 1w

w

B−2hc 1L w

Input variablew hcB −2 1 w hcB −2 2 L w hc0 2••••w hcB −i 1 w hcB −i 2 L w hc0 i

また，最適関数回路に基づく分散演算による構成法において滞在時間の減少が可能な構成法も併せて提案する．

(b) The second stagew

Φ ( v 1k , v 2k , L, v mk )vc 1
hc 1vcw

vc 2hc 1L w hc 1j 最適関数回路vcw hcvc 12 w hcvc 22 L w hc 2j
••

•

•

•

•

分散演算において，関数0 の生成に を用い•••

vcw hcvc 1i w hcvc i2 L w hc ij(c) The third stage &' $#

関数 0 に対する冗長性の削除  0 #0   

ただし，0  0 は，   0 

0 

最適関数回路の構成

 &' %••

Number of lines equal to thatof vertical category

た場合，システムに非常に大きな消費電力を必要とする．これは，の消費電力が非常に大きいためである．ゆえに，関数 0 の生成に  ではなく，それと同機能で低消費電力となる回路を用いた構成法が要求される．そこで，我々が提案している最適関数回路に着目して，大幅な低消費電力化を実現できる構成を提案する．
 に書き込まれている関数 0 のテーブルを図$ のように表す．ここで，
 は  ビット長
の入力変 数であ り， は  番 地に格 納されている ビットのデータを示す．同図  の関数
0    を   の行列  とみなすと，#

 # "である．式 11" から，バタフライ演算に分散演算を適用できる．分散演算が  に用いられることにより，小面積化が実現できる．
この分散演算を  に適用した構成はすでに提案されている  ．この構成では比較的大きな消費電力を要するが多数必要となるため，システム全体の消費電力が膨大になってしまう．

      

''''''

$と表せる．ここで，関数 0 の最適化で行われている冗長性の削除を大域的削除と局所的削除に大きく分けて考える．大域的削除とは，図 $ で示すように式 $ の行ベクトルに対して共有可能となる行ベクトルを作り出すことである．その結果，生成される行列  は， " 本提案法

 

本提案法では分散演算の特長だけでなく，我々が提案している最適関数回路の特長  にも着目して，小面積化と低消費電力化が実現できる構成法を提案する．


½'''


   ½   '''%となる．さらに，図 $ で示すように式 % の列ベクトルに対しても同様な手法を施す．その結#

1bit

1bit

xRm (1bit)

serial full
adder

shift
registerSPregister

PSregister

ARm (1bit)

xIm (1bit)

serial full
adder

shift
registerSPregisterPS
registerAIm (1bit)

serial full
subtractor

optimumfunctioncircuitadder

PSregisterARn (1bit)

serial full
subtractor

optimumfunctioncircuitadder

PSregisterAIn (1bit)

summing_nodetable

xRn (1bit)

xIn (1bit)

add

SP register : serial to parallel register
PS register : parallel to serial register: register

serial output butterfly processor

 &' )

ビット  プロセッサにおけるシリアル出力バタフライ演算プロセッサの構成
1bit

1bit

xRm (1bit)

serial full
adder

shift
registerSPregister

ARm (14bits)

xIm (1bit)

serial full
adder

shift
registerSPregister

AIm (14bits)

serial full
subtractor

optimumfunctioncircuitadder

ARn (14bits)

serial full
subtractor

optimumfunctioncircuitadder

AIn (14bits)

summing_node

table

add

xRn (1bit)

xIn (1bit)

SP register : parallel to serial register: register

parallel output butterfly processor

 &' ,

ビット  プロセッサにおけるパラレル出力バタフライ演算プロセッサの構成

果，生成される行列  は，


 
 

½
½'''

½ 
 

最適関数回路に基づく分散演算を用いた本構成法 

 ビット  プロセッサ½''')

となる．ここで，式 ) で表される の相違なる各行ベクトルを横のカテゴリ，同様に， の相違なる各列ベクトルを縦のカテゴリと呼ぶことにする．この冗長性の削除を基にして，最適関数回路
は図 % のように横のカテゴリに対する部分機能回路と縦のカテゴリに対する部分機能回路を縦続接続した回路構成になる．これらの冗長性の削除によって，ゲート数を削減でき，その結果大幅に消費電力を減少できる．この最適関数回路はと同機能であるから  プロセッサに適用できる．これにより，消費電力が大幅に減少される．

低消費電力化と小面積化を実現するために，最適関数回路に基づく分散演算に着目した構成法を提案する．本構成法は入力変数をビットずつ入力していくことから， ビット  プロセッサと呼ぶことにする． ビット  プロセッサのバ
タフライ演算プロセッサは図)1,のような構成で表される．図)の構成は，クロックごとに ビットずつ入出力を行う．図 , の構成は，入力値が  クロッ
クごとに  ビットずつ入力され，出力値が ビット並列に出力される．図,はの計算結果が出力されるプロセッサとなり，それ以外は全て図)のプロセッサとなる．これらを図  のように構成したものが本提案法の  プロセッサである．この $

2bitsxRm(2bits)serialfulladder

SPregisterPS
registerARm(2bits)

xIm(2bits)serialfulladderSPregisterPSregisterAIm(2bits)xRn(2bits)

serial full
subtracter

MSB
selecter

optimumfunctioncircuitadder

PSregisterARn(2bits)xIn(2bits)

serial full
subtracter

MSB
selecter

optimumfunctioncircuitadder

PSregisterAIn(2bits)

serialselecttable

add

MSB selecter : Most Significant Bit selecter
SP register : serial to parallel register
PS register : parallel to serial register: register

serial output butterfly processor
 &' -多ビット  プロセッサにおけるシリアル出力バタフライ演算プロセッサの構成
2bits
xRm(2bits)

xIm(2bits)xRn(2bits)xIn(2bits)

serial fulladder

SPregisterARm(14bits)

serial fulladder

SPregisterAIm(14bits)

serial full
subtracter

MSB
selecter

optimumfunctioncircuitadderARn(14bits)

serial full
subtracter

MSB
selecter

optimumfunctioncircuitadderAIn(14bits)

serialselecttable

add

MSB selecter : Most Significant Bit selecter
SP register : serial to parallel register: register

parallel output butterfly processor

 &' .

多ビット  プロセッサにおけるパラレル出力バタフライ演算プロセッサの構成

プロセッサはカウンタからの信号によって制御される．
式"の計算は，はじめに入力変数 と を実部と虚部においてそれぞれ減算を行い，その結果を最適関数回路に入力させる．最適関数回路には関数 0  0 が格納されており，図 )1, において，上段の最適関数回路が関数0 になり，下段の最適関数回路が 0 になって いる．これら  つの最適関数回路からの出力を順次  ビット右シフトしながら，加算することで式 " は計算される．この加算は同図のに当たる．式-については入力変数と  の実部と虚部においてそれぞれ加算を行い，その結果をシフトレジスタで順次伝播することで計算している．
式 " の内積演算に最適関数回路に基づく分散演算を用いることにより大幅な低消費電力化と小面積化が実現できる．

 

多ビット  プロセッサ$'' で示した構成は，低消費電力化と小面積化が実現できるが， ビットずつ処理を行うために， プロセッサの滞在時間が大きくなるという問題が生じる．そこで，入力変数を複数ビット入力させることで滞在時間の減少が可能となることに着目した構成法を提案する．ここでは，入力変数を  ビットずつ入力して，滞在時間の減少を図る．
多ビットプロセッサのバタフライ演算プロ

セッサは図 -1. のような構成で表される．図 - の構

%counter#parallel output butterfly processor

1bit or 2bits

これまでに提案したつの構成法の性能を明らかにするために  設計システム 34566 を用いて  設計，評価を行う．なお，用いた設計ルールは ') 7 スタンダードセルであり，電源電圧は %' *+ である．
本構成の  プロセッサは入出力値のデータ形
式をの補数表示による語長$ビットの固定小数点とする．ただし，演算語長は，計算時のオーバー14bits

x0
0x40

ARmxRmxIm 0 AImxRnW ARn
AInxIn

W0

W0

AR0
AI0
AR4AI4x1
0x50

W1

W2W0

AR2
AI2
AR6AI6x20x60

W2W0W0AR1
AI1
AR5AI5x30x70

W3W2W0AR3AI3AR7AI7serial output butterfly processor

 &' 

設計，評価プロセッサの構成

成は， クロックごとに  ビットずつ入出力を行う．
図 . の構成は，入力値がクロックごとに  ビットずつ入力され，出力値が  ビット並列に出力される．
図.はの計算結果が出力されるプロセッサとなり，それ以外は全て図-のプロセッサとなる．
プロセッサの構成は，$''で示した構成と同様に，図  のようになる．また，最適関数回路に基づく分散演算も同様に用いられている．
分散演算は式)に示すように，最上位ビットの入力変数と係数の内積演算の結果 0 の減算を行う．
そこで，入力変数を複数ビット入力させる場合，最上位ビットを判別し，最上位ビットと係数の内積演算を求める必要がある．そこで我々は，最上位ビットを判別する回路を構成した．この回路は図-1. の 2  / に当たる．2  /  はカウンタからの信号で制御される．最上位ビットを含んだ複数ビットが 2  /  に入力すると，
2  / は最上位ビットとそれ以外のビットに分ける．そして，2  /  は最上位ビットに を結合した複数ビット を入力変数の最後の出力にする．この最上位ビットに を結合させた複数ビットと係数との内積演算の結果 0 が最適関数回路から出力される．その値は加算器に入力する際にビット反転を行う．このビット反転を行った値を加減算器で処理することにより分散演算が可能となる．
このような処理を行うことで，分散演算に基づく構成において入力変数を複数ビットにすることが可能となり，滞在時間の短縮が実現される．

フローを考慮して整数部をビット設けた)ビットとする．なお， のデータ点数は - 点とした．
本研究で提案した つの構成，関数 0  0 の生成に  を用いた従来型分散演算に基づく構成と乗算器を用いた一般的な構成の評価結果を表  に示す．なお，使用した乗算器は，部分積の生成に2 のアルゴリズムと部分積の加算に 8// の方式と 7 加算器を用いたもので，) ) ビット乗算器である．

  ビット   プロセッサの評価
表より，ビットプロセッサの消費電力は  を用いた従来型分散演算に基づく構成の約 ,%9，乗算器を用いた構成の約 --9削減された．
これは最適関数回路の消費電力が  や乗算器の消費電力に比べて非常に小さいためである．この評価結果から最適関数回路を用いた分散演算に基づく構成は大幅な低消費電力化が可能であるといえる．
面積を比較すると，を用いた構成の約%"9，乗算器を用いた構成の約 -,9削減された．これは最適関数回路のゲート数は  や乗算器のゲート数よりも少ないからである．この評価結果から最適関数回路を用いた分散演算に基づく構成は小面積化が可能であるといえる．
これらの結果から，最適関数回路を用いた分散演算に基づく  ビット  プロセッサは低消費電力化および小面積化に対する効果が大きいという特長を示した．

多ビット   プロセッサの評価

 ビット  プロセッサの滞在時間は，を用いた構成の約" 9，ビットプロセッサの構成の約 )9削減された．これは入力変数を複数ビット入力させることで滞在時間の短縮を図っ

&/

プロセッサの評価

本提案法 最適関数回路

ビット 

ビット 

乗算器

消費電力 *8+- "'%-$"'

"%-'

)$%-'.

面積 * +"'$%)

$' ).

,'" .,,' "%%.

ゲート数

. $$

"".$,$.$.

$"$".

マシンサイクル * +

.

"

.

$)

サンプリングレート *4:+

'%"'.

'%',滞在時間 * +

""$..

$""

たためである．この評価結果より，入力変数を複数ビット入力させた分散演算に基づく構成は滞在時間の短縮が可能であるといえる．滞在時間の短縮により  ビット  プロセッサのサンプリン
グレートはを用いた構成とビットプ
ロセッサの構成の約')倍となり，多ビットプロセッサの有効性が明らかとなった．
また， ビット  プロセッサの消費電力は
 を用いた従来型分散演算に基づく構成の約,"9，乗算器を用いた構成の約-,9削減された．面積を比較すると， を用いた構成の約$$9，乗算器を用いた構成の約 -%9削減された．この結果からも最適関数回路を用いた分散演算に基づく構成は低消費電力化および小面積化に対する効果が大きいといえる．

ビット以外で検討する必要がある．

参考文献$ むすび本研究では分散演算を用いた高性能プロセッ
サの アーキテクチャを提案した．本提案法では，内積演算を乗算器を用いずに行うことができる分散演算に 最適関数回路を 用いることによ り，小面積化と低消費電力化を図った．また最適関数
回路を用いた分散演算において，入力変数を複数ビット入力させることで滞在時間の短縮を図った．
小面積 化と低消 費電力 化を図った提 案法を  ビットプロセッサと，滞在時間の短縮を図った
提 案法 を 多ビット  プロセッサ とを それ ぞれ設計し，その評価を行った．その結果， ビット プロセッサは  を用いた従来型分散演算に基づく構成法と乗算器を用いた構成法に対して大幅な低消費電力化と小面積化が可能となった．
また，多ビット  プロセッサは，分散演算を用いた構成のどれよりも滞在時間が減少できた．
以上のことから，我々が提案した構成法の有効性が明らかとなった．
今後の課題として，多ビット  の入力変数を '

 青木孝文，天田博章，樋口龍雄 +冗長複素数系に基づく実数,複素数再構成型算術演算回路の構成+ 電子
情報通信学会論文誌-! .#-! /# (0$(#  ''0#  1 2 +  3) 456
   + *  *77 ('  /#$ ##$ ''0& 野崎剛，恒川佳隆，三浦守 +滞 在時間を考慮した
高次 !8 フィルタの高速・低消費電力形アーキテク
チャ+ 電気学会論文誌 9 "# 0,# ''#$ 6:  8;   +-  4 7+ 4 <  +468 <*/:/ = > 1  + /株式会社 ''

7 

データ通信