プロセッサ装置及びその演算方法
【課題】複数のPEを備えた並列型SIMDプロセッサにおいて並列性の高い行列転置方法等を提供する。
【解決手段】プロセッサ装置は、各PE方向に行ベクトルデータが配列され、かつ各PE内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、各PE間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、最小2次の行列(2×2要素)では対角要素データの移動又は交換を行い、上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換し、これらの手順を上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理する。
【解決手段】プロセッサ装置は、各PE方向に行ベクトルデータが配列され、かつ各PE内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、各PE間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、最小2次の行列(2×2要素)では対角要素データの移動又は交換を行い、上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換し、これらの手順を上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数のプロセシングエレメント(Processing Elements:以下、PEという。)を備え、画像データ等を高速処理するために同一の命令で複数データに対して同じ処理を行うSIMD(Single Instruction-stream Multiple Data-stream)型マイクロプロセッサなどのプロセッサ装置及びその演算方法に関し、特に、複数の行列(マトリクス)データの転置処理を効率よく並列処理するプロセッサ装置及びその演算方法に関する。
【背景技術】
【0002】
近年、デジタル複写機やファクシミリ装置等の画像処理においては、画素数の増加、画像処理の多様化などにより画質の向上が図られている。このような画像処理では、複数(多数)のデータに対して同時に同じ処理を施すことが多い。その際、高速性を高めるため、1命令で1つのデータを処理するSISD(Single Instruction-stream Single Data-stream)型マイクロプロセッサよりも、1命令で複数のデータを同時処理する、SIMD型マイクロプロセッサが用いられることが多くなっている。
【0003】
図1は従来技術に係る一般的なSIMD型マイクロプロセッサ2の基本構成を示すブロック図である。当該SIMD型マイクロプロセッサ2は、概略、グローバルプロセッサ(以下、GPという。)4、及びPE3により構成されるのであるが、複数のデータを一度に処理するためにPE3を複数個装備している。各PE3は、レジスタファイル6と演算アレイ8を備える。GP4は、プロセッサ2全体の制御を行い、PE3は、外部入出力装置(図示せず。)からデータを入力しデータ処理を行い、外部入出力装置に出力する。
【発明の概要】
【発明が解決しようとする課題】
【0004】
上記のSIMD型マイクロプロセッサ2は、通常、1クロックサイクルで1命令を処理するが、1命令でPE3の個数分のデータを一度に処理することができる。SIMD型マイクロプロセッサ2の性能を表す際には、SIMD型マイクロプロセッサ2の動作周波数や、PE3の個数、すなわち1命令で処理できるデータの数などが重要視されるが、さらに、命令サイクル数も重要な要素とされる。つまり、同じ画像処理を行う限り1命令サイクルでも少ないほうが性能がよいとされるのである。しかし、1命令で複雑な処理を行うために、複雑な回路を設計して利用するならば、どうしてもコストが増大するという問題点があった。
【0005】
ところで、近年、マルチメディア社会の進展からの懇請によって、大規模な二次元画像データ等のデジタル処理を高速に行う要請は日々増大しており、この要求を満たすための演算処理プロセッサのハードウェア、ソフトウェアの技術開発がたゆまなくなされている。その中で単一のプロセシングユニットもしくはプロセシングエレメントを備えるプロセッサの高速化を目指す技術開発は、その都度、ハードウェアの集積(複雑さと物量の増大)の限界と電気特性的な限界(例えば電気素子の動作遅延)に直面し、別の技術開発のアプローチとして、複数の演算ユニットで複数の信号データを同時並列に処理する、いわゆる「並列処理アプローチ」がある。
【0006】
並列処理を行うプロセシングハードウェアは、複数データを同時に扱う際の分類としてSIMD(単一命令複数データ)アプローチとMIMD(複数命令複数データ)アプローチがある。SIMDアプローチのプロセッサにおけるデジタル処理では、命令処理の制御や、ソフトウェアの構成が比較的容易であることから、これらのハードウェア、ソフトウェア分野の技術開発が盛んに行われている。
【0007】
SIMDアプローチのプロセッサは、さらにそのハードウェア構成によって、多倍精度のプロセシングユニットをビットスライス分割して、単一命令で、複数データを同時に一括処理する装置と方法、(以下、スライス型という。)一方、比較的規則的かつハードウェア規模の小さなプロセシングエレメント(PE)を多数並列に配列してプロセシングユニットを構成し、単一命令でそれらを同時に演算処理させるような装置と方法(以下、並列型という。)に分類される。
【0008】
前者のアプローチのプロセシングユニットは比較的大きなビット幅のデータを扱う演算ユニットと比較的複雑かつ高速な演算命令体系と実行機能を備え、まれに実験的な組み立てを除き、通常は単一、多くとも数個のユニットから構成されるプロセッサであることがほとんどである。前者の具体的な従来技術として著名なものはインテル社のプロセッサにおけるMMX(Multi-Media eXtension)やSSE(Streaming SIMD Extension)技術などが挙げられる。MMXやSSE技術は、スライス分割によって複数データを同時処理するためのマルチメディアデジタル処理に適した命令セット拡張体系である。
【0009】
図4は従来技術に係るMMX技術を用いた行列転置方法の好適例を示すプログラムを示す図である。すなわち、図4はスライス型のSIMDアプローチにおける、並列性を有したデータ移動、交換によるデータ配置変換処理の一般概念をも好適に示す。
【0010】
図4の従来例においてプロセッサは128ビット幅の語長をもつプロセシングユニットを4個の32ビット語長のスライス(以下、レーンデータという。)に分割し、これらを同時並列にデータ演算する命令体系を備えている。4つのレジスタm0からレジスタm3までに、m00からm33までの4×4の行列データが格納されており、これをレジスタ内データの配置変換命令を使って転置処理を行うものである。結果はレジスタm0からレジスタm3までに戻されるように構成されている。プログラムリストはC言語の表記をなしているが、6行目以降の
[数1]
__builtin_ia32_unpcklps(),__builtin_ia32_unpckhps()
がプロセッサの配置変換(インターリーブやパック命令と一般に呼称されるものである)命令(もしくは命令マクロ)に対応している。
【0011】
これらのステートメント表記を見ても明らかなように、本命令ではソースオペランドとして2項のレジスタを、デスティネーションオペランドとして1項のレジスタを取る構成である。レジスタ内のビットスライスを下位ビットから順に第1レーン、第2レーン、第3レーン、第4レーンとすると、前者の命令ではソースレジスタの下位2レーン分のスライスに着目し、第1オペランドの第1レーンと第2レーンのビットスライスデータをデスティネーションの第1レーンと第3レーン、第2オペランドの第1レーンと第2レーンのビットスライスデータをデスティネーションの第2レーンと第4レーンに配置して格納する作用をする。同様に後者の命令では、ソースレジスタの上位2レーン分のスライスに着目し、第1オペランドの第3レーンと第4レーンのビットスライスデータをデスティネーションの第1レーンと第3レーン、第2オペランドの第3レーンと第4レーンのビットスライスデータをデスティネーションの第2レーンと第4レーンに配置して格納する作用をする。中間の配置結果の時刻t0からt3までを使ってさらに配置変換を繰り返すことにより10行目以降で最終的に転置された行列データがm0からm3までに格納されることがわかる。複数のレーンデータを同時並列に移動・配置できることから、単に複数データを同時に算術演算するだけでなくデータ配置変換処理においてもスライス型のSIMDプロセッサ装置及び方法が有効に機能することが示される好例である。
【0012】
さらに、別の従来例では、インターリーブ命令を強化して、分割するビットスライス幅の変更と、それに合わせた配置変換パターンの制御の変更を行える装置を開示し、行列転置や他のデータ配列変換処理をさらに効率よく行える方法が、例えば特許文献1において開示されている。
【0013】
さらに、過去をさかのぼり別の従来技術では、レジスタのビットシフトと、レジスタ間のデータ複写又は移動の際にデータマスク機能を使うことにより、近代のスライス型SIMDアプローチに似た手法でレジスタ内の部分データをインターリーブする手法を行列転置に応用した事例の方法が、例えば特許文献2において開示されている。
【0014】
これらSIMDアプローチのプロセッサによる配置変換方法では一般的にいって、レジスタを含むプロセシングユニットの演算語長を複数にスライス分割することが本質であるため、同時に処理できるスライスデータ(レーン)の数はプロセシングユニットの演算語長に依存して限定されることになる。通常は数個程度のデータ(レーン)しか同時並列に扱うことはできない欠点が見られる。スライス分割数を超えるデータの配置変換には必ず、外部キャッシュ又は外部メモリとの通信が必要となり、全体の処理速度が低下する欠点も見られる。
【0015】
さらに、プロセッサ装置のサイクル速度とハードウェア規模とのトレードオフにより、データレーンの配置変換命令においては、通常は数種程度の固定化された配置変換パターンしか持ち得ず、それらアトミックな配置変換パターンを組み合わせて様々な配置変換を実現することになり、固定パターンになじまない種類の配置変換処理ではこれらを複数組み合わせて実現することになり、処理効率を損なうとともに柔軟性に欠けると見ることもできる。
【0016】
さらに、特許文献1において開示された装置のごとく、配置変換パターンに自由度をもたせるためには多大なハードウェアコストを支払う必要があること、そのことにより演算サイクルの低下を招く傾向にあることが欠点として認められる。さらに、特許文献2において開示された従来例における転置処理の方法は、ビットスライスの配置変換専用命令を持たない旧来のプロセッサを用いて、多倍精度語長のレジスタ内のスライスデータの配置変換をビットシフトとデータマスクを用いて逐次的に実現したものであり、並列同時にデータ移動がなされているわけではなく多大なステップが必要となってしまう欠点があるが、スライス型SIMDアプローチの黎明期の方法事例として好適である。
【0017】
以上はスライス型のSIMDアプローチの装置及び方法における全般的な問題点を示しているが、それは同時に本アプローチのプロセッサで行列転置処理を方法実現する際の問題としてそのまま示されることは容易に理解される。
【0018】
次に、並列型のSIMDアプローチの具体的な従来技術であるプロセッサ装置が、例えば、特許文献6及び7において開示されている。本アプローチにおける以降の説明及び実施形態で引用されるプロセッサ装置例となる。これら文献で示される並列型のSIMDアプローチをとるプロセッサ装置では、比較的規則的かつ演算語長が小さく小規模なプロセシングエレメント(PE)が多数並列に配列され、単一命令に従って、PEに分散された多数の複数データを同時並列に演算処理するものである。これらのプロセッサにきわめて特徴的な機能として、近傍PEのレジスタアクセス機能と、PE個々の演算の実行又は演算の非実行を制御するための演算マスク機能が挙げられる。本発明における行列転置方法ではこれらの機能を有効利用するものである。また以下で述べる発明者らの従来の転置方法においてもこれらの機能を利用し、多数個の行列の転置処理を並列処理で転置する方法を示している。
【0019】
さらに、並列型のSIMDアプローチの具体的な従来技術であるプロセッサ装置が、例えば特許文献3において開示されている。このプロセッサ装置によれば、PEを跨ぐデータアクセスのためのネットワーク機構を柔軟かつ強化し、その転送パターンを命令セットとは切離して独立に設定できるようにしたプロセッサ装置を開示し、応用方法として行列転置処理方法をも示している。転送ネットワークを任意に設定できるためPE間のデータ移動の自由度は増大するが、データネットワークの回路規模が膨大になることが予想され、PEの回路の規則性も損なわれるため、大規模多数のPEを集積することは困難であると予想される。集積されるPEの数が限定されることは処理の並列度の低下を意味し、プロセッサ内に留めることのできる要素データの数が限定され、大規模多数のデータに演算を施し、PE間でのデータ移動、配置変換を複数回内包するような演算処理では、外部キャッシュや外部メモリへのアクセスが頻繁に発生し、処理の効率と速度を落とす原因となる欠点が認められる。
【0020】
以下は、並列型のSIMDアプローチを取るプロセッサで、発明者らが従来実施してきた多数個の行列転置処理を並列処理で転置する方法を示している。この従来例では、352個のPEを備えるプロセッサ装置で処理を行う方法を示す。PEにはそれぞれに、識別するためのPE番号(アドレス)が0(下位側)から351(上位側)まで付加されている。以下、この従来例では8×8要素の行列転置処理を行う方法について示している。
【0021】
図5は従来例に係る行列転置方法において、行列データが列方向(図5の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。すなわち8個のPEで1つの行列データを保持するよう配列されている。この従来例では352個のPEを配するプロセッサであるため全てのPEにデータを配置することで総計44個の行列を並列に処理することができるようになる。転置処理の結果はTmR20からTmR27までの別のレジスタに格納される。
【0022】
以下の表1〜表10は、上記並列型のSIMDプロセッサで行列転置処理方法の手順を示したプログラムリストである。プログラムリストのそれぞれのステートメントはプロセッサの機械語に対応し、処理内容に合わせたニモニック表示となっている。セミコロン以下はコメント行である。
【0023】
命令
[数2]
settb/t1 #1,#3f8h
はプロセシングエレメント(PE)の処理実行又は処理非実行を制御するための演算マスクビットを設定する命令であり、即値とPE番号とのビット比較により、演算マスクビットの設定を行うものである。第1オペランドが比較値、第2オペランドは比較の際無視するビットを指定するアドレスマスクである。演算マスクビットは各PE毎にT1からT7までの7個を持ち、同時に7種類の演算マスクを保持してPEの演算実行制御を個々に行うことができる。先の命令の場合、PE番号の下位3ビットを除く上位ビットを全て無視して、即値「1」と比較し一致するPEのT1ビットをセット(すなわち「1」を書き込む)するように動作する。結果、PE番号を8で割り算した余りが1である全てのPEのT1ビットがセットされることになる。さらに、Lda命令は指定されたソースレジスタ内容を第1アキュムレータAにロードする命令、Ldf命令は第2アキュムレータFにロードする命令である。
【0024】
命令
[数3]
lda/t1 TmR1:L1
は2つのオプションが付加されており、/t1により演算マスクT1ビットがセットされたPEだけで実行される命令となり、T1ビットがクリアされているPEでは実行されない(NOP)。オペランドのTmR1はソースレジスタの指定で、:L1は1つ下位(Lower:PE番号が小さいもの)のPEのレジスタを参照するように修飾される。この従来例のプロセッサでは自身以外のPEのレジスタ参照は、上位側、下位側それぞれ3つの距離まで可能であり、先のレジスタ修飾は:L1からL3まで、及びU1からU3まで使うことができる。ここで、Uは上位番号のPEを表す。これらの修飾子が付加されない場合は自身のレジスタが参照される。本機能により、PE方向のデータの移動が可能となり、このような態様を以下、「PEシフト」という。
【0025】
Sta、Stfはそれぞれのアキュムレータからデスティネーションレジスタまでにストア(格納)する命令である。デスティネーションレジスタにも隣接PEの参照を制御する修飾子(:L1〜:L3、:U1〜:U3)があり、同様に下位PEもしくは上位PEのレジスタに内容を格納するよう制御される。
[数4]
ldf TmR4:L3,TmR10
命令のように、ロード命令で2項のオペランドが配される場合は、アキュムレータにソースレジスタの内容がロードされた後、同時にアキュムレータの内容が第2項のデスティネーションレジスタにストア(複写)されるように動作する。
【0026】
この従来例に係るプロセッサ装置の場合は、最大上下3個先のPEのレジスタをアクセスできるが、それ以上離れた場所のアクセスを行うには、テンポラリレジスタを介して、PEシフトの距離量を組み合わせることで実現する。その分、ステップ数が増える問題はあるが柔軟に手順を組み立てることができる。しかしながら、どの距離のPEまでアクセスできるかは、時代の集積技術と応用分野からの性能要請に基づきトレードオフで決定されるものであるので、この従来例ではあくまで一例として示したにすぎず、以降の説明や本発明の内容をなんら制約するものではない。
【0027】
[表1]
;===================================================
;行列転置
;---------------------------------------------------
;Input
; TmR00(1行目)〜TmR07(8行目)
;---------------------------------------------------
;Output
; TmR20(1行目)〜TmR27(8行目)
;---------------------------------------------------
;Tmp
; TmR10,TmR11,TmR12,TmR13,TmR14,
; t1,t2,t3,t4,t5,t6,t7
;===================================================
;
【0028】
[表2]
;演算マスクの設定
settb/t1 #1,#3f8h ;01000000 ;STEP1
settb/t2 #2,#3f8h ;00100000 ;STEP2
settb/t3 #3,#3f8h ;00010000 ;STEP3
settb/t4 #4,#3f8h ;00001000 ;STEP4
settb/t5 #5,#3f8h ;00000100 ;STEP5
settb/t6 #6,#3f8h ;00000010 ;STEP6
settb/t7 #7,#3f8h ;00000001 ;STEP7
;
【0029】
[表3]
;1行目の配置
lda TmR0 ;STEP8
lda/t1 TmR1:L1 ;STEP9
lda/t2 TmR2:L2 ;STEP10
lda/t3 TmR3:L3 ;STEP11
ldf TmR4:L3,TmR10 ;STEP12
ldf TmR5:L3,TmR11 ;STEP13
ldf TmR6:L3,TmR12 ;STEP14
ldf TmR7:L3 ;STEP15
lda/t4 TmR10:L1 ;STEP16
lda/t5 TmR11:L2 ;STEP17
stf TmR10:U1 ;STEP18
lda/t6 TmR12:L3 ;STEP19
lda/t7 TmR10:L3,TmR20 ;STEP20
【0030】
[表4]
;2行目の配置
lda TmR0:U1 ;STEP21
lda/t1 TmR1 ;STEP22
lda/t2 TmR2:L1 ;STEP23
lda/t3 TmR3:L2 ;STEP24
lda/t4 TmR4:L3 ;STEP25
ldf TmR5:L3,TmR10 ;STEP26
ldf TmR6:L3,TmR11 ;STEP27
ldf TmR7:L3,TmR12 ;STEP28
lda/t5 TmR10:L1 ;STEP29
lda/t6 TmR11:L2 ;STEP30
lda/t7 TmR12:L3,TmR21 ;STEP31
【0031】
[表5]
;3行目の配置
lda TmR0:U2 ;STEP32
lda/t1 TmR1:U1 ;STEP33
lda/t2 TmR2 ;STEP34
lda/t3 TmR3:L1 ;STEP35
lda/t4 TmR4:L2 ;STEP36
lda/t5 TmR5:L3 ;STEP37
ldf TmR6:L3,TmR10 ;STEP38
ldf TmR7:L3,TmR11 ;STEP39
lda/t6 TmR10:L1 ;STEP40
lda/t7 TmR11:L2,TmR22 ;STEP41
【0032】
[表6]
;4行目の配置
lda TmR0:U3,TmR10 ;STEP42
lda/t1 TmR1:U2 ;STEP43
lda/t2 TmR2:U1 ;STEP44
lda/t3 TmR3 ;STEP45
lda/t4 TmR4:L1 ;STEP46
lda/t5 TmR5:L2 ;STEP47
ldf TmR7:L3,TmR11 ;STEP48
lda/t6 TmR6:L3 ;STEP49
lda/t7 TmR11:L1,TmR23 ;STEP50
【0033】
[表7]
;5行目の配置
lda TmR10:U1 ;STEP51
lda/t1 TmR1:U3 ;STEP52
lda/t2 TmR2:U2 ;STEP53
lda/t3 TmR3:U1 ;STEP54
lda/t4 TmR4 ;STEP55
lda/t5 TmR5:L1 ;STEP56
lda/t6 TmR6:L2 ;STEP57
lda/t7 TmR7:L3,TmR24 ;STEP58
【0034】
[表8]
;6行目の配置
ldf TmR1:U3,TmR11 ;STEP59
lda TmR10:U2 ;STEP60
lda/t1 TmR11:U1 ;STEP61
lda/t2 TmR2:U3 ;STEP62
lda/t3 TmR3:U2 ;STEP63
lda/t4 TmR4:U1 ;STEP64
lda/t5 TmR5 ;STEP65
lda/t6 TmR6:L1 ;STEP66
lda/t7 TmR7:L2,TmR25 ;STEP67
【0035】
[表9]
;7行目の配置
ldf TmR2:U3,TmR12 ;STEP68
lda TmR10:U3 ;STEP69
lda/t1 TmR11:U2 ;STEP70
lda/t2 TmR12:U1 ;STEP71
lda/t3 TmR3:U3 ;STEP72
lda/t4 TmR4:U2 ;STEP73
lda/t5 TmR5:U1 ;STEP74
lda/t6 TmR6 ;STEP75
lda/t7 TmR7:L1,TmR26 ;STEP76
【0036】
[表10]
;8行目の配置
ldf TmR10 ;STEP77
stf TmR14:L1 ;STEP78
lda TmR14:U3 ;STEP79
ldf TmR3:U3,TmR13 ;STEP80
lda/t1 TmR11:U3 ;STEP81
lda/t2 TmR12:U2 ;STEP82
lda/t3 TmR13:U1 ;STEP83
lda/t4 TmR4:U3 ;STEP84
lda/t5 TmR5:U2 ;STEP85
lda/t6 TmR6:U1 ;STEP86
lda/t7 TmR7,TmR27 ;STEP87
;
【0037】
次に、この従来例に係るプログラムリストで実現されている手順について説明する。まず、STEP1からSTEP7まで演算マスクビットを設定する。T1ビットはPE番号を8で割って余りが1のPEの全てについてそれぞれセットされる。T2ビットは同様に余りが2のPE全てについて、T3ビットは余りが3のPE全てについて、T4ビットは余りが4のPE全てについて、T5ビットは余りが5のPE全てについて、T6ビットは余りが6のPE全てについて、T7ビットは余りが7のPE全てについて各々セットされる。STEP8からSTEP20までは転置結果の1行目の配置変換を行う手順である。以下にデータ移動の様子を図示している。
【0038】
図6は従来例に係る行列転置方法において、STEP8〜STEP20までの手順により転置結果の1行目の配置変換を示す行列データを示す図である。図6に示すように、対角要素を除き、ハッチング部分のデータがこれらのステップで移動される。TmR20からTmR27までのレジスタに処理結果が格納される。TmR20は転置結果の1行目が配置されるが、図6とプログラムリストを見て明らかなように、行の要素の8PE毎に1個ずつ、PEシフト操作を介して列要素からデータ移動されていることがわかる。352個のPEに跨って44個の8×8の行列が配置されているので、行列要素としては1個ずつではあるが、全体としては44個のデータが同時並列に移動、配置されるステップである。
【0039】
以下同様に、各行の処理内容の図を示す。図7は従来例に係る行列転置方法において、STEP21〜STEP31までの手順により2行目の配置変換を示す行列データを示す図である。また、図8は従来例に係る行列転置方法において、STEP32〜STEP41までの手順により3行目の配置変換を示す行列データを示す図である。さらに、図9は従来例に係る行列転置方法において、STEP42〜STEP50までの手順により4行目の配置変換を示す行列データを示す図である。またさらに、図10は従来例に係る行列転置方法において、STEP51〜STEP58までの手順により5行目の配置変換を示す行列データを示す図である。また、図11は従来例に係る行列転置方法において、STEP59〜STEP67までの手順により6行目の配置変換を示す行列データを示す図である。さらに、図12は従来例に係る行列転置方法において、STEP68〜STEP76までの手順により7行目の配置変換を示す行列データを示す図である。またさらに、図13は従来例に係る行列転置方法において、STEP77〜STEP87までの手順により8行目の配置変換を示す行列データを示す図である。
【0040】
以上、並列型のSIMDプロセッサで近傍PEのレジスタアクセス機能と、PEの演算マスクにより、複数の行列転置処理を同時並列に実施する従来例に係る行列転置方法を示した。近傍PEのレジスタアクセスにより、PE間を跨るデータとPE内に配置されるデータを柔軟に移動、配置できることが示されている。また多数のPEを配列するプロセッサではその並列性により多数の行列データを並列同時に処理する方法が提供されうることが示されている。
【0041】
しかしながら、この従来例で示した方法では行列あたり1要素ずつ移動させるステップから構成されるため、並列性が高く処理効率が良いとはいえない欠点があった。さらにレジスタアクセス可能なPE間の距離が小さく限定されるプロセッサでは、回路の規則性が高く、複雑度、回路規模が小さく、より多数のPEを集積できうる利点はあるものの、可能な最大距離を超えた位置のPEのレジスタアクセスを行うには追加のステップが必要となり、処理速度と効率が低下する欠点が認められる。具体的には、この従来例においてデータ要素移動の個々のステップで距離3を越えるPEのデータへのアクセスは、都度3以下のPEシフトを組み合わせて多段ステップで実現しており、ステップ数が増えると全体のステップ数に与える影響が大きいという欠点がある。
【0042】
従来技術に係るビットスライス型のSIMDプロセッサでは一般的にプロセシングユニットの演算語長の制約から同時に並列処理できるデータの数に、最大で数個程度という制限があり、制限を越える大量のデータ処理を行うためには逐次外部キャッシュやメモリアクセスが必要となり、並列処理の効率が比較的低く速度の低下を招く問題点があった。
【0043】
さらに、別の形態に係る、プロセシングユニットを多数並列に配列する並列型のSIMDプロセッサでは、規則性が高く比較的小規模のプロセシングエレメント(PE)をより多数個配列して集積するものほど処理の並列性が増大し、処理効率はきわめて高くなる一方、データ移動可能なPEの範囲は装置回路的にPE自身の近傍距離に限られる傾向にあり、行列転置のようなデータ移動のPE間距離が比較的大きい処理ほど、データ移動ステップが多段で煩雑となり、処理ステップが増大して処理速度が低下する問題点があった。
【0044】
本発明の第1の目的は以上の問題点を解決し、多数のプロセシングエレメント(PE)を集積しうる並列型のSIMDプロセッサにおいて並列性の高い行列転置方法を用いたプロセッサ装置及びその演算方法を提供することにある。
【0045】
また、本発明の第2の目的は上記第1の目的に加えて、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップ数がより少ない行列転置方法を用いたプロセッサ装置及びその演算方法を提供することにある。
【0046】
さらに、本発明の第3の目的は上記第1及び第2の目的に加えて、PE間のデータ移動の並列性を高めて処理ステップがさらに少なく効率的な行列転置方法をプロセッサ装置及びその演算方法を提供することにある。
【課題を解決するための手段】
【0047】
第1の発明に係るプロセッサ装置は、複数のプロセシングエレメントを備えたプロセッサ装置において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とする。
【0048】
上記プロセッサ装置において、行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする。
【0049】
第2の発明に係るプロセッサ装置の演算方法は、複数のプロセシングエレメントを備えたプロセッサ装置の演算方法において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とする。
【0050】
上記プロセッサ装置の演算方法において、行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする。
【発明の効果】
【0051】
従って、本発明に係るプロセッサ装置及びその演算方法によれば、2のべき乗次の部分行列を対象に対角位置のブロックのデータを一括して移動、交換するステップを含み、データのPE間移動は2のべき乗の距離の移動を組み合わせ、それぞれの2のべき乗距離のデータ移動は並列に一括して行うことが可能となるため、データのPE間の移動距離が自身の近傍位置に限られるような、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップがより少ない行列転置方法を提供することができる。また、複数の行列データの転置処理を同時一括して並列処理することができるので処理全体のスループットは高くなる。さらに、複数の行列データをプロセッサ装置内に留め置き演算処理を進めることができるので外部キャッシュやメモリとのアクセス頻度を減らすことができ処理のスループット向上を図ることができる。
【0052】
また、本発明に係るプロセッサ装置及びその演算方法によれば、所定の演算マスク値を設定し、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータに対応する連続PEを並列動作させて並列同時にデータの移動、交換するステップを含むので、並列動作するPEの数が最大に保たれ、並列性が高く効率のきわめて高い行列転置方法を提供することができる。
【図面の簡単な説明】
【0053】
【図1】従来技術及び本発明の実施形態に係るSIMD型マイクロプロセッサ装置の基本構成を示すブロック図である。
【図2】本発明の実施形態に係るSIMD型マイクロプロセッサ装置の詳細構成を示すブロック図である。
【図3】図2のレジスタファイルのレジスタと演算アレイとを結び付けるマルチプレクサの機能構成を示すブロック図である。
【図4】従来例に係るMMX技術を用いた行列転置方法の一例を示すプログラムを示す図である。
【図5】従来例に係る行列転置方法において、行列データが列方向(図5の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。
【図6】従来例に係る行列転置方法において、STEP8〜STEP20までの手順により転置結果の1行目の配置変換を示す行列データを示す図である。
【図7】従来例に係る行列転置方法において、STEP21〜STEP31までの手順により2行目の配置変換を示す行列データを示す図である。
【図8】従来例に係る行列転置方法において、STEP32〜STEP41までの手順により3行目の配置変換を示す行列データを示す図である。
【図9】従来例に係る行列転置方法において、STEP42〜STEP50までの手順により4行目の配置変換を示す行列データを示す図である。
【図10】従来例に係る行列転置方法において、STEP51〜STEP58までの手順により5行目の配置変換を示す行列データを示す図である。
【図11】従来例に係る行列転置方法において、STEP59〜STEP67までの手順により6行目の配置変換を示す行列データを示す図である。
【図12】従来例に係る行列転置方法において、STEP68〜STEP76までの手順により7行目の配置変換を示す行列データを示す図である。
【図13】従来例に係る行列転置方法において、STEP77〜STEP87までの手順により8行目の配置変換を示す行列データを示す図である。
【図14】本実施形態に係る行列転置方法において、行列データが列方向(図14の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。
【図15】本実施形態に係る行列転置方法において、STEP4〜STEP7までの手順を実行後の行列データの配置を示す図である。
【図16】本実施形態に係る行列転置方法において、STEP19による2×2部分行列の処理終了時点での行列データの配置を示す図である。
【図17】本実施形態に係る行列転置方法において、STEP20〜STEP23までの手順を実行後の行列データの配置を示す図である。
【図18】本実施形態に係る行列転置方法において、STEP24〜STEP27までの手順を実行後の行列データの配置を示す図である。
【図19】本実施形態に係る行列転置方法において、STEP24〜STEP27、STEP28〜STEP31、STEP32〜STEP35までの手順を実行後の行列データの配置を示す図である。
【図20】本実施形態に係る行列転置方法において、STEP36〜STEP41までの手順を実行後の行列データの配置を示す図である。
【図21】本実施形態に係る行列転置方法において、STEP42〜STEP47までの手順を実行後の行列データの配置を示す図である。
【図22】本実施形態に係る行列転置方法において、STEP48〜STEP53までの手順を実行後の行列データの配置を示す図である。
【図23】本実施形態に係る行列転置方法において、STEP54〜STEP59までの手順を実行後の行列データの配置を示す図である。
【発明を実施するための形態】
【0054】
以下、本発明に係る実施形態について図面を参照して説明する。なお、以下の各実施形態において、同様の構成要素については同一の符号を付している。
【0055】
実施形態の基本構成.
図1は本発明の実施形態に係るSIMD型マイクロプロセッサ2の基本構成を示すブロック図である。実施形態に係るSIMD型マイクロプロセッサ2は、主としてプロセッサ2全体を制御するグローバルプロセッサ(GP)4と、主として外部入出力装置からデータを入力しデータ処理を行い、外部入出力装置にデータを出力するプロセシングエレメント(PE)3とを備えて構成される。PE3は、複数データを同時に処理するために複数用意されている。図1では、1個のGP4と、256個のPE3とにより、SIMD型マイクロプロセッサ2が構成されている。
【0056】
図2は本発明の実施形態に係るSIMD型マイクロプロセッサ装置の詳細構成を示すブロック図である。図2に示されるように、GP4は、
(a)命令コードで構成されるプログラムを格納するためのプログラムRAM10と、
(b)GP4での演算データを格納するデータRAM12と、
(c)プログラムを解読し各種ブロックに各種制御信号を送るシーケンシャルユニット(SCU)9と、
(d)データを格納する複数の汎用レジスタ(G0〜G3)と、
(e)SCU9にプログラムの命令コードを送るためにプログラムのアドレスを保持するプログラムカウンタ(PC)14と、
(f)データメモリにスタックを形成するためデータメモリのアドレスを格納するスタックポインタ(SP)24と、
(g)プログラムの途中でサブルーチン処理を行う際には分岐が発生するが分岐前のアドレスを格納する複数のリンクレジスタ(LS、LI、LN)と、
(h)データメモリのデータ、命令コード中に記述された数値(即値)データ、もしくは汎用レジスタに格納されているデータのいずれかの組み合わせに対して、算術論理演算を行う算術論理演算装置(ALU)11と、
(i)プロセッサの状態を保持するプロセッサステータスレジスタ(図示せず。)と、
(j)ハードウェア割り込みとソフトウェア割り込みを制御する割り込み制御回路(図示せず。)と、
(k)外部入出力に直接接続され外部からのデータの入出力を制御する外部入出力制御回路(図示せず。)とを備えて構成される。
【0057】
図2では図示していないが、上記SCU9は、GP命令を解読し主にGP内の各ブロックに制御信号を発生するGP命令デコーダと、PE命令を解読し主にPE内の各ブロックに制御信号を発生するPE命令デコーダとで、構成される。すなわち、本プロセッサに係る命令コードは、主にGP4内の各ブロックを制御し、プログラムのシーケンスを決定したり、PEに転送する共通データをGP4内のALU11で加工したりするGP命令と、外部入出力装置から一度に入力されたデータをPE3毎に処理をさせるプロセシングエレメント命令とに分類される。
【0058】
図1に示すように、各PE3は、外部入出力装置からの入出力データを一時的に保持するレジスタファイル6と、PE3内で算術論理演算やビット演算のデータ処理を行うための演算アレイ8を含む。さらに、図2に示すようにレジスタファイル6には、例えば、R0〜R31までの8ビットのレジスタ34が32個用意されている。これらのレジスタ34からデータが演算アレイ8に転送され、また逆に、演算アレイ8からデータが転送されてレジスタ34に格納される。レジスタ34と演算アレイ6とのバスは、8ビットの双方向バスである。
【0059】
さらに、図2に示すように、単体の演算アレイ8は演算ユニットであり、
(a)レジスタファイル6からのデータをシフトして符号付き拡張もしくは符号無し拡張をして16ビットデータに加工するシフト拡張器44と、
(b)例えば、Aレジスタ38とFレジスタ40などを含む複数の汎用レジスタと、
(c)レジスタファイル6からのデータを、シフト拡張器44を経由して加工し1入力とし、他方の入力をAレジスタ36からの入力とする算術論理演算装置(ALU)36と、
(d)PE番号マスク回路、固定値選択回路、及びnおきにビットパターンデータ出力回路のそれぞれからの出力を入力とし、自らの出力をAレジスタ38やTレジスタ54に繋げる選択回路35とを備えて構成される。
【0060】
算術論理演算装置(ALU)36の出力は、Aレジスタ36もしくはFレジスタ40に一時格納されように設定されているが、Aレジスタ36からレジスタファイル6の所定の1レジスタ34にデータ転送されることも可能である。
【0061】
また、演算アレイ8は、詳細後述するように、「Tレジスタ」と呼ばれる演算制御レジスタ54を備える。ALU36からの出力は、当該Tレジスタ54によって、Aレジスタ36もしくはFレジスタ40への書き込み内容が制御される。例えば、演算制御レジスタ(Tレジスタ)54の中の所定の1ビットの状態に応じて、「1」であればAレジスタ36もしくはFレジスタ54への書き込みを行い、「0」であれば行わないというような制御が行われる。
【0062】
図3は図2のレジスタファイルのレジスタと演算アレイとを結び付けるマルチプレクサの機能構成を示すブロック図である。図3において、PEi(i=0,1,2,…,255)のPEに備わるマルチプレクサは7対1のマルチプレクサであり、PEi−3(PEiから3つ左隣りに位置する)、PEi−2(PEiから2つ左隣りに位置する)、PEi−1(PEiから1つ左隣りに位置する)、PEi、PEi+1(PEiから1つ右隣りに位置する)、PEi+2(PEiから2つ右隣りに位置する)、PEi+3(PEiから3つ右隣りに位置する)のPE3のレジスタファイル6からのデータを入出力することができるように設定されている。この機能を、PEシフト機能と称する。マルチプレクサによって選択されたデータは、演算アレイ8のシフト拡張器44に転送される。
【0063】
ここで、PE3の番号を含む呼称について定義する。図2に示すように、本実施形態に係るSIMD型マイクロプロセッサ2には256個のPE3が設置されており、それらPE3の個々に対し、(図2では左側から)PE0、PE1、PE2、PE3、…、PE254、PE255というように、PE番号を付すと定義する。
【0064】
実施形態.
本発明に係る好適な実施形態を以下に説明する。以下に示す表11〜表15は並列型のSIMDプロセッサにおいて行列転置処理方法の手順を示したプログラムリストである。本実施形態に係るSIMDプロセッサの形態及び命令セットの説明は、上述の従来例と同様であるので省略する。命令に付加される/f1オプションは、マスクビットT1に基づく演算制御のための修飾で、T1ビットが0であれば命令実行を行うよう制御される。/fに続く数字はT1〜T7ビットを指定するものである。プロセッサにおいてどの距離のPEまでアクセスできるかは、時代の集積技術と応用分野からの性能要請に基づきトレードオフで決定されるものであるので、本実施形態ではあくまで一例として示したにすぎず、以降の説明や本発明の内容をなんら制約するものではない。
【0065】
本実施形態では、352個のPEを備えるプロセッサ装置で処理を行う方法を示す。PEにはそれぞれに、識別するためのPE番号(アドレス)が0(下位側)から351(上位側)まで付加されている。以下、本実施形態では8×8要素の行列転置処理を行う方法について示している。
【0066】
図14は本実施形態に係る行列転置方法において、行列データが列方向(図14の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。すなわち、8個のPEで1つの行列データを保持するよう配列されている。本実施形態では、352個のPEを配するプロセッサであるため全てのPEにデータを配置することで総計44個の行列を並列に処理することができるようになる。転置処理の結果はTmR0からTmR7までのレジスタに再び格納されるよう動作する。
【0067】
[表11]
;===================================================
;行列転置
;---------------------------------------------------
;Input
; TmR0(1行目)〜TmR7(8行目)
;---------------------------------------------------
;Output
; TmR0(1行目)〜TmR7(8行目)
;---------------------------------------------------
;Tmp
; TmR8~TmR9
; t1,t2,t3
;===================================================
;
【0068】
[表12]
;演算マスクの設定
settb/t1#1,#3feh ;01010101 ;STEP1
settb/t2#2,#3fdh ;00110011 ;STEP2
settb/t3#4,#3fbh ;00001111 ;STEP3
;
【0069】
[表13]
;2×2部分行列の転置
lda TmR0,TmR8 ;STEP4
ldf TmR1,TmR9 ;STEP5
ldf/f1 TmR8:u1,TmR1 ;STEP6
lda/t1 TmR9:l1,TmR0 ;STEP7
;
lda TmR2,TmR8 ;STEP8
ldf TmR3,TmR9 ;STEP9
ldf/f1 TmR8:u1,TmR3 ;STEP10
lda/t1 TmR9:l1,TmR2 ;STEP11
;
lda TmR4,TmR8 ;STEP12
ldf TmR5,TmR9 ;STEP13
ldf/f1 TmR8:u1,TmR5 ;STEP14
lda/t1 TmR9:l1,TmR2 ;STEP15
;
lda TmR6,TmR8 ;STEP16
ldf TmR7,TmR9 ;STEP17
ldf/f1 TmR8:u1,TmR7 ;STEP18
lda/t1 TmR9:l1,TmR6 ;STEP19
;
【0070】
[表14]
;4×4部分行列の転置
lda TmR0,TmR8 ;STEP20
ldf TmR2,TmR9 ;STEP21
ldf/f2 TmR8:u2,TmR2 ;STEP22
lda/t2 TmR9:l2,TmR0 ;STEP23
;
lda TmR1,TmR8 ;STEP24
ldf TmR3,TmR9 ;STEP25
ldf/f2 TmR8:u2,TmR3 ;STEP26
lda/t2 TmR9:l2,TmR1 ;STEP27
;
lda TmR4,TmR8 ;STEP28
ldf TmR6,TmR9 ;STEP29
ldf/f2 TmR8:u2,TmR6 ;STEP30
lda/t2 TmR9:l2,TmR4 ;STEP31
;
lda TmR5,TmR8 ;STEP32
ldf TmR7,TmR9 ;STEP33
ldf/f2 TmR8:u2,TmR7 ;STEP34
lda/t2 TmR9:l2,TmR5 ;STEP35
;
【0071】
[表15]
;8×8最終行列の転置
lda TmR0 ;STEP36
sta TmR8:l2 ;STEP37
ldf TmR4 ;STEP38
stf TmR9:u2 ;STEP39
ldf/f3 TmR8:u2,TmR4 ;STEP40
lda/t3 TmR9:l2,TmR0 ;STEP41
;
lda TmR1 ;STEP42
sta TmR8:l2 ;STEP43
ldf TmR5 ;STEP44
stf TmR9:u2 ;STEP45
ldf/f3 TmR8:u2,TmR5 ;STEP46
lda/t3 TmR9:l2,TmR1 ;STEP47
;
lda TmR2 ;STEP48
sta TmR8:l2 ;STEP49
ldf TmR6 ;STEP50
stf TmR9:u2 ;STEP51
ldf/f3 TmR8:u2,TmR6 ;STEP52
lda/t3 TmR9:l2,TmR2 ;STEP53
;
lda TmR3 ;STEP54
sta TmR8:l2 ;STEP55
ldf TmR7 ;STEP56
stf TmR9:u2 ;STEP57
ldf/f3 TmR8:u2,TmR7 ;STEP58
lda/t3 TmR9:l2,TmR3 ;STEP59
【0072】
STEP1からSTEP3までは処理で必要な演算マスク値の設定を以下のごとく行っている。
[数5]
settb/t1 #1,#3feh
命令は、PE番号の最下位ビット(bit0)が1のもの全てのT1ビットをセット(1を設定)する。このことにより、T1ビットの値は、最下位PEから010101010…が設定される。すなわち、偶数番号のPEのT1ビットは0に、奇数ビットのT1ビットは1に設定される。
【0073】
[数6]
settb/t2 #2,#3fdh
命令は、PE番号のbit1(最下位ビットから次のビットをいう。)が1のもの全てのT2ビットをセット(1を設定)する。このことにより、T2ビットの値は、最下位PEから001100110011…が設定される。すなわち、連続する4つのPE毎に連続する下位2つのPEのT2ビットは0に、上位2つのPEのT2ビットは1に設定される。
【0074】
[数7]
settb/t3 #4,#3fbh
命令は、PE番号のbit2(最下位ビットから2ビット目のビットをいう。)が1のもの全てのT3ビットをセット(1を設定)する。このことにより、T3ビットの値は、最下位PEから0000111100001111…が設定される。すなわち連続する8つのPE毎に連続する下位4つのPEのT3ビットは0に、上位4つのPEのT3ビットは1に設定される。
【0075】
STEP4からSTEP19までは、隣り合う2行のデータを対象に、これに内包される2×2部分行列の対角要素の交換処理を行うステップである。参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離1のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、偶数もしくは奇数のPEが常に動作していることから処理の並列度が高いことを特徴としている。
【0076】
図15は本実施形態に係る行列転置方法において、STEP4〜STEP7までの手順を実行後の行列データの配置を示す図である。また、図16は本実施形態に係る行列転置方法において、STEP19による2×2部分行列の処理終了時点での行列データの配置を示す図である。
【0077】
STEP20からSTEP35までは、隣り合う連続4行のデータを対象に、これに内包される4×4部分行列を対象にその中の対角ブロック(2×2要素)の交換処理を行うステップである。交換処理を行う2行データを対象に参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離2のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、4つのPE毎に2つのPEが常に動作していることから処理の並列度が高いことを特徴としている。
【0078】
図17は本実施形態に係る行列転置方法において、STEP20〜STEP23までの手順を実行後の行列データの配置を示す図である。図17から明らかなように、最初の2行分のデータ移動を行っている。
【0079】
図18は本実施形態に係る行列転置方法において、STEP24〜STEP27までの手順を実行後の行列データの配置を示す図である。図18から明らかなように、次の2行分のデータ移動を行っている。これで前半の4×4部分行列の対角2×2要素ブロックの移動が完了している。
【0080】
図19は本実施形態に係る行列転置方法において、STEP24〜STEP27、STEP28〜STEP31、STEP32〜STEP35までの手順を実行後の行列データの配置を示す図である。図19から明らかなように、2行目と6行目、3行目と7行目、4行目と8行目の配置変換がそれぞれ実施される。
【0081】
次いで、STEP36からSTEP59までは、最後に8行のデータを対象に、その対角ブロック(4×4要素)の交換処理を行うステップである。交換処理を行う2行データを対象に参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離4のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、8つのPE毎に4つのPEが常に動作していることから処理の並列度が高いことを特徴としている。移動距離4の場合は、1段のPEシフトでは届かないので、2段のPEシフトで対応している。1段目は距離2のシフトを行ったデータをテンポラリレジスタに一時的に保存し、そのレジスタをさらに距離2のPEシフトで参照して距離4の移動配置を行う。1段目の距離2のPEシフトをともなう移動命令は全数のPEで同時並列に実行できるため、ステップ数の増加の影響は最小限にすることができる。
【0082】
図20は本実施形態に係る行列転置方法において、STEP36〜STEP41までの手順を実行後の行列データの配置を示す図である。図20から明らかなように、最初の2行分のデータ移動を行っている。STEP36とSTEP37は、1行目のデータ(TmR0)を距離2の下位へのPEシフトを行い、テンポラリレジスタTmR8に複写する手順である。同様に、STEP38とSTEP39は5行目のデータ(TmR4)を距離2の上位へのPEシフトを行い、テンポラリレジスタTmR9に複写する手順である。以上は全てのPEで実行される。STEP40とSTEP41でさらに距離2のPEシフトを行って先のテンポラリレジスタを参照することで距離4のデータ移動、交換を実現している。以上は演算マスクビットの設定により、8つのPE毎に4つのPEで同時並列に実行される。
【0083】
以下同様にSTEP42〜47、STEP48〜53、STEP54〜59実施後のデータ配置を以下の図に示す。すなわち、図21は本実施形態に係る行列転置方法において、STEP42〜STEP47までの手順を実行後の行列データの配置を示す図である。また、図22は本実施形態に係る行列転置方法において、STEP48〜STEP53までの手順を実行後の行列データの配置を示す図である。さらに、図23は本実施形態に係る行列転置方法において、STEP54〜STEP59までの手順を実行後の行列データの配置を示す図である。
【0084】
以上説明したように、本実施形態によれば、2×2部分行列から始めて、2のべき乗次の行列である4×4、8×8行列を対象に各々対角位置のブロックのデータを一括交換する手順を順次行うステップを含んでいることが本実施形態の別の特徴である。
【0085】
本実施形態によれば、行列要素を1つずつ個々に多段の移動ステップと組み合わせて移動させていた自社従来例に比べて、データのPE間移動を2のべき乗の距離に分割して(例えば7つの位置移動であれば、1+2+4のように組み合わせて移動することに結果としてなる)それぞれの2のべき乗距離の移動は並列に一括して行うため、回路及び命令セットで制限される最大のPEシフト量を超えるデータの移動においてもステップ数の増加が少なく効率が良いという特有の効果を有する。
【0086】
また、各部分行列の処理ステップでは、演算マスク値設定の工夫によって、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータを対応する連続PEを並列動作さることにより並列同時に移動可能となるステップを含んでいる特長的な処理手順が示されている。このことにより、並列動作するPEの数が常に最大に保たれており、並列処理効率はきわめて高い。
【0087】
以上の優位点から、自社従来例に比べて処理ステップは30%強縮減され(87個のステップ数から59個のステップ数に減縮)、命令数も縮減されるのでコードサイズを減らすこともできる。さらにプロセッサに集積された最大PE数まで対象行列をマッピングすることで、複数の行列データを同時一括して並列処理することができるので処理全体のスループットは高くなる。できるだけ大量のデータをプロセッサ内に留め置き、並列処理を進め、外部キャッシュやメモリとのアクセス頻度を減らすことは全体のスループット向上に資すると認められる。もしくは、本実施形態では、2×2部分行列から始めて、4×4、8×8行列を対象に各々対角位置のブロックのデータを一括交換する手順を順次行うステップを含んでいるが、8×8行列から始めて順に4×4、2×2と繰り返し処理するステップに構成しても有効に機能することは明らかである。
【産業上の利用可能性】
【0088】
以上詳述したように、本発明に係るプロセッサ装置及びその演算方法によれば、2のべき乗次の部分行列を対象に対角位置のブロックのデータを一括して移動、交換するステップを含み、データのPE間移動は2のべき乗の距離の移動を組み合わせ、それぞれの2のべき乗距離のデータ移動は並列に一括して行うことが可能となるため、データのPE間の移動距離が自身の近傍位置に限られるような、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップがより少ない行列転置方法を提供することができる。また、複数の行列データの転置処理を同時一括して並列処理することができるので処理全体のスループットは高くなる。さらに、複数の行列データをプロセッサ装置内に留め置き演算処理を進めることができるので外部キャッシュやメモリとのアクセス頻度を減らすことができ処理のスループット向上を図ることができる。
【0089】
また、本発明に係るプロセッサ装置及びその演算方法によれば、所定の演算マスク値を設定し、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータに対応する連続PEを並列動作させて並列同時にデータの移動、交換するステップを含むので、並列動作するPEの数が最大に保たれ、並列性が高く効率のきわめて高い行列転置方法を提供することができる。
【0090】
さらに、本発明に係るプロセッサ装置及びその演算方法によれば、画像信号などの二次元信号のデータのデジタル処理において、例えばそのデータの圧縮や伸張を行うための二次元離散コサイン変換(DCT又はDCT変換)における変換処理の次元の方向を入れ替える処理すなわち2次元行列における数学的転置処理に広く適用できる。
【符号の説明】
【0091】
2…SIMD型マイクロプロセッサ、
3…プロセシングエレメント(PE)、
4…グローバルプロセッサ(GP)、
6…レジスタファイル、
8…演算アレイ、
9…シーケンシャルユニット(SCU)、
10…プログラムRAM、
11…算術論理演算装置(ALU)、
12…データRAM、
14…プログラムカウンタ(PC)、
24…スタックポインタ(SP)、
34,38,40,54…レジスタ、
44…シフト拡張器、
G0〜G3…汎用レジスタ、
LS,LI,LN…リンクレジスタ。
【先行技術文献】
【特許文献】
【0092】
【特許文献1】特開2005−174293号公報
【特許文献2】特開昭62−107381号公報
【特許文献3】特開2005−267615号公報
【特許文献4】特開2002−149400号公報
【特許文献5】特表2002−518730号公報
【特許文献6】特許第4398965号公報
【特許文献7】特許第3742745号公報
【特許文献8】特許第3779540号公報
【技術分野】
【0001】
本発明は、複数のプロセシングエレメント(Processing Elements:以下、PEという。)を備え、画像データ等を高速処理するために同一の命令で複数データに対して同じ処理を行うSIMD(Single Instruction-stream Multiple Data-stream)型マイクロプロセッサなどのプロセッサ装置及びその演算方法に関し、特に、複数の行列(マトリクス)データの転置処理を効率よく並列処理するプロセッサ装置及びその演算方法に関する。
【背景技術】
【0002】
近年、デジタル複写機やファクシミリ装置等の画像処理においては、画素数の増加、画像処理の多様化などにより画質の向上が図られている。このような画像処理では、複数(多数)のデータに対して同時に同じ処理を施すことが多い。その際、高速性を高めるため、1命令で1つのデータを処理するSISD(Single Instruction-stream Single Data-stream)型マイクロプロセッサよりも、1命令で複数のデータを同時処理する、SIMD型マイクロプロセッサが用いられることが多くなっている。
【0003】
図1は従来技術に係る一般的なSIMD型マイクロプロセッサ2の基本構成を示すブロック図である。当該SIMD型マイクロプロセッサ2は、概略、グローバルプロセッサ(以下、GPという。)4、及びPE3により構成されるのであるが、複数のデータを一度に処理するためにPE3を複数個装備している。各PE3は、レジスタファイル6と演算アレイ8を備える。GP4は、プロセッサ2全体の制御を行い、PE3は、外部入出力装置(図示せず。)からデータを入力しデータ処理を行い、外部入出力装置に出力する。
【発明の概要】
【発明が解決しようとする課題】
【0004】
上記のSIMD型マイクロプロセッサ2は、通常、1クロックサイクルで1命令を処理するが、1命令でPE3の個数分のデータを一度に処理することができる。SIMD型マイクロプロセッサ2の性能を表す際には、SIMD型マイクロプロセッサ2の動作周波数や、PE3の個数、すなわち1命令で処理できるデータの数などが重要視されるが、さらに、命令サイクル数も重要な要素とされる。つまり、同じ画像処理を行う限り1命令サイクルでも少ないほうが性能がよいとされるのである。しかし、1命令で複雑な処理を行うために、複雑な回路を設計して利用するならば、どうしてもコストが増大するという問題点があった。
【0005】
ところで、近年、マルチメディア社会の進展からの懇請によって、大規模な二次元画像データ等のデジタル処理を高速に行う要請は日々増大しており、この要求を満たすための演算処理プロセッサのハードウェア、ソフトウェアの技術開発がたゆまなくなされている。その中で単一のプロセシングユニットもしくはプロセシングエレメントを備えるプロセッサの高速化を目指す技術開発は、その都度、ハードウェアの集積(複雑さと物量の増大)の限界と電気特性的な限界(例えば電気素子の動作遅延)に直面し、別の技術開発のアプローチとして、複数の演算ユニットで複数の信号データを同時並列に処理する、いわゆる「並列処理アプローチ」がある。
【0006】
並列処理を行うプロセシングハードウェアは、複数データを同時に扱う際の分類としてSIMD(単一命令複数データ)アプローチとMIMD(複数命令複数データ)アプローチがある。SIMDアプローチのプロセッサにおけるデジタル処理では、命令処理の制御や、ソフトウェアの構成が比較的容易であることから、これらのハードウェア、ソフトウェア分野の技術開発が盛んに行われている。
【0007】
SIMDアプローチのプロセッサは、さらにそのハードウェア構成によって、多倍精度のプロセシングユニットをビットスライス分割して、単一命令で、複数データを同時に一括処理する装置と方法、(以下、スライス型という。)一方、比較的規則的かつハードウェア規模の小さなプロセシングエレメント(PE)を多数並列に配列してプロセシングユニットを構成し、単一命令でそれらを同時に演算処理させるような装置と方法(以下、並列型という。)に分類される。
【0008】
前者のアプローチのプロセシングユニットは比較的大きなビット幅のデータを扱う演算ユニットと比較的複雑かつ高速な演算命令体系と実行機能を備え、まれに実験的な組み立てを除き、通常は単一、多くとも数個のユニットから構成されるプロセッサであることがほとんどである。前者の具体的な従来技術として著名なものはインテル社のプロセッサにおけるMMX(Multi-Media eXtension)やSSE(Streaming SIMD Extension)技術などが挙げられる。MMXやSSE技術は、スライス分割によって複数データを同時処理するためのマルチメディアデジタル処理に適した命令セット拡張体系である。
【0009】
図4は従来技術に係るMMX技術を用いた行列転置方法の好適例を示すプログラムを示す図である。すなわち、図4はスライス型のSIMDアプローチにおける、並列性を有したデータ移動、交換によるデータ配置変換処理の一般概念をも好適に示す。
【0010】
図4の従来例においてプロセッサは128ビット幅の語長をもつプロセシングユニットを4個の32ビット語長のスライス(以下、レーンデータという。)に分割し、これらを同時並列にデータ演算する命令体系を備えている。4つのレジスタm0からレジスタm3までに、m00からm33までの4×4の行列データが格納されており、これをレジスタ内データの配置変換命令を使って転置処理を行うものである。結果はレジスタm0からレジスタm3までに戻されるように構成されている。プログラムリストはC言語の表記をなしているが、6行目以降の
[数1]
__builtin_ia32_unpcklps(),__builtin_ia32_unpckhps()
がプロセッサの配置変換(インターリーブやパック命令と一般に呼称されるものである)命令(もしくは命令マクロ)に対応している。
【0011】
これらのステートメント表記を見ても明らかなように、本命令ではソースオペランドとして2項のレジスタを、デスティネーションオペランドとして1項のレジスタを取る構成である。レジスタ内のビットスライスを下位ビットから順に第1レーン、第2レーン、第3レーン、第4レーンとすると、前者の命令ではソースレジスタの下位2レーン分のスライスに着目し、第1オペランドの第1レーンと第2レーンのビットスライスデータをデスティネーションの第1レーンと第3レーン、第2オペランドの第1レーンと第2レーンのビットスライスデータをデスティネーションの第2レーンと第4レーンに配置して格納する作用をする。同様に後者の命令では、ソースレジスタの上位2レーン分のスライスに着目し、第1オペランドの第3レーンと第4レーンのビットスライスデータをデスティネーションの第1レーンと第3レーン、第2オペランドの第3レーンと第4レーンのビットスライスデータをデスティネーションの第2レーンと第4レーンに配置して格納する作用をする。中間の配置結果の時刻t0からt3までを使ってさらに配置変換を繰り返すことにより10行目以降で最終的に転置された行列データがm0からm3までに格納されることがわかる。複数のレーンデータを同時並列に移動・配置できることから、単に複数データを同時に算術演算するだけでなくデータ配置変換処理においてもスライス型のSIMDプロセッサ装置及び方法が有効に機能することが示される好例である。
【0012】
さらに、別の従来例では、インターリーブ命令を強化して、分割するビットスライス幅の変更と、それに合わせた配置変換パターンの制御の変更を行える装置を開示し、行列転置や他のデータ配列変換処理をさらに効率よく行える方法が、例えば特許文献1において開示されている。
【0013】
さらに、過去をさかのぼり別の従来技術では、レジスタのビットシフトと、レジスタ間のデータ複写又は移動の際にデータマスク機能を使うことにより、近代のスライス型SIMDアプローチに似た手法でレジスタ内の部分データをインターリーブする手法を行列転置に応用した事例の方法が、例えば特許文献2において開示されている。
【0014】
これらSIMDアプローチのプロセッサによる配置変換方法では一般的にいって、レジスタを含むプロセシングユニットの演算語長を複数にスライス分割することが本質であるため、同時に処理できるスライスデータ(レーン)の数はプロセシングユニットの演算語長に依存して限定されることになる。通常は数個程度のデータ(レーン)しか同時並列に扱うことはできない欠点が見られる。スライス分割数を超えるデータの配置変換には必ず、外部キャッシュ又は外部メモリとの通信が必要となり、全体の処理速度が低下する欠点も見られる。
【0015】
さらに、プロセッサ装置のサイクル速度とハードウェア規模とのトレードオフにより、データレーンの配置変換命令においては、通常は数種程度の固定化された配置変換パターンしか持ち得ず、それらアトミックな配置変換パターンを組み合わせて様々な配置変換を実現することになり、固定パターンになじまない種類の配置変換処理ではこれらを複数組み合わせて実現することになり、処理効率を損なうとともに柔軟性に欠けると見ることもできる。
【0016】
さらに、特許文献1において開示された装置のごとく、配置変換パターンに自由度をもたせるためには多大なハードウェアコストを支払う必要があること、そのことにより演算サイクルの低下を招く傾向にあることが欠点として認められる。さらに、特許文献2において開示された従来例における転置処理の方法は、ビットスライスの配置変換専用命令を持たない旧来のプロセッサを用いて、多倍精度語長のレジスタ内のスライスデータの配置変換をビットシフトとデータマスクを用いて逐次的に実現したものであり、並列同時にデータ移動がなされているわけではなく多大なステップが必要となってしまう欠点があるが、スライス型SIMDアプローチの黎明期の方法事例として好適である。
【0017】
以上はスライス型のSIMDアプローチの装置及び方法における全般的な問題点を示しているが、それは同時に本アプローチのプロセッサで行列転置処理を方法実現する際の問題としてそのまま示されることは容易に理解される。
【0018】
次に、並列型のSIMDアプローチの具体的な従来技術であるプロセッサ装置が、例えば、特許文献6及び7において開示されている。本アプローチにおける以降の説明及び実施形態で引用されるプロセッサ装置例となる。これら文献で示される並列型のSIMDアプローチをとるプロセッサ装置では、比較的規則的かつ演算語長が小さく小規模なプロセシングエレメント(PE)が多数並列に配列され、単一命令に従って、PEに分散された多数の複数データを同時並列に演算処理するものである。これらのプロセッサにきわめて特徴的な機能として、近傍PEのレジスタアクセス機能と、PE個々の演算の実行又は演算の非実行を制御するための演算マスク機能が挙げられる。本発明における行列転置方法ではこれらの機能を有効利用するものである。また以下で述べる発明者らの従来の転置方法においてもこれらの機能を利用し、多数個の行列の転置処理を並列処理で転置する方法を示している。
【0019】
さらに、並列型のSIMDアプローチの具体的な従来技術であるプロセッサ装置が、例えば特許文献3において開示されている。このプロセッサ装置によれば、PEを跨ぐデータアクセスのためのネットワーク機構を柔軟かつ強化し、その転送パターンを命令セットとは切離して独立に設定できるようにしたプロセッサ装置を開示し、応用方法として行列転置処理方法をも示している。転送ネットワークを任意に設定できるためPE間のデータ移動の自由度は増大するが、データネットワークの回路規模が膨大になることが予想され、PEの回路の規則性も損なわれるため、大規模多数のPEを集積することは困難であると予想される。集積されるPEの数が限定されることは処理の並列度の低下を意味し、プロセッサ内に留めることのできる要素データの数が限定され、大規模多数のデータに演算を施し、PE間でのデータ移動、配置変換を複数回内包するような演算処理では、外部キャッシュや外部メモリへのアクセスが頻繁に発生し、処理の効率と速度を落とす原因となる欠点が認められる。
【0020】
以下は、並列型のSIMDアプローチを取るプロセッサで、発明者らが従来実施してきた多数個の行列転置処理を並列処理で転置する方法を示している。この従来例では、352個のPEを備えるプロセッサ装置で処理を行う方法を示す。PEにはそれぞれに、識別するためのPE番号(アドレス)が0(下位側)から351(上位側)まで付加されている。以下、この従来例では8×8要素の行列転置処理を行う方法について示している。
【0021】
図5は従来例に係る行列転置方法において、行列データが列方向(図5の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。すなわち8個のPEで1つの行列データを保持するよう配列されている。この従来例では352個のPEを配するプロセッサであるため全てのPEにデータを配置することで総計44個の行列を並列に処理することができるようになる。転置処理の結果はTmR20からTmR27までの別のレジスタに格納される。
【0022】
以下の表1〜表10は、上記並列型のSIMDプロセッサで行列転置処理方法の手順を示したプログラムリストである。プログラムリストのそれぞれのステートメントはプロセッサの機械語に対応し、処理内容に合わせたニモニック表示となっている。セミコロン以下はコメント行である。
【0023】
命令
[数2]
settb/t1 #1,#3f8h
はプロセシングエレメント(PE)の処理実行又は処理非実行を制御するための演算マスクビットを設定する命令であり、即値とPE番号とのビット比較により、演算マスクビットの設定を行うものである。第1オペランドが比較値、第2オペランドは比較の際無視するビットを指定するアドレスマスクである。演算マスクビットは各PE毎にT1からT7までの7個を持ち、同時に7種類の演算マスクを保持してPEの演算実行制御を個々に行うことができる。先の命令の場合、PE番号の下位3ビットを除く上位ビットを全て無視して、即値「1」と比較し一致するPEのT1ビットをセット(すなわち「1」を書き込む)するように動作する。結果、PE番号を8で割り算した余りが1である全てのPEのT1ビットがセットされることになる。さらに、Lda命令は指定されたソースレジスタ内容を第1アキュムレータAにロードする命令、Ldf命令は第2アキュムレータFにロードする命令である。
【0024】
命令
[数3]
lda/t1 TmR1:L1
は2つのオプションが付加されており、/t1により演算マスクT1ビットがセットされたPEだけで実行される命令となり、T1ビットがクリアされているPEでは実行されない(NOP)。オペランドのTmR1はソースレジスタの指定で、:L1は1つ下位(Lower:PE番号が小さいもの)のPEのレジスタを参照するように修飾される。この従来例のプロセッサでは自身以外のPEのレジスタ参照は、上位側、下位側それぞれ3つの距離まで可能であり、先のレジスタ修飾は:L1からL3まで、及びU1からU3まで使うことができる。ここで、Uは上位番号のPEを表す。これらの修飾子が付加されない場合は自身のレジスタが参照される。本機能により、PE方向のデータの移動が可能となり、このような態様を以下、「PEシフト」という。
【0025】
Sta、Stfはそれぞれのアキュムレータからデスティネーションレジスタまでにストア(格納)する命令である。デスティネーションレジスタにも隣接PEの参照を制御する修飾子(:L1〜:L3、:U1〜:U3)があり、同様に下位PEもしくは上位PEのレジスタに内容を格納するよう制御される。
[数4]
ldf TmR4:L3,TmR10
命令のように、ロード命令で2項のオペランドが配される場合は、アキュムレータにソースレジスタの内容がロードされた後、同時にアキュムレータの内容が第2項のデスティネーションレジスタにストア(複写)されるように動作する。
【0026】
この従来例に係るプロセッサ装置の場合は、最大上下3個先のPEのレジスタをアクセスできるが、それ以上離れた場所のアクセスを行うには、テンポラリレジスタを介して、PEシフトの距離量を組み合わせることで実現する。その分、ステップ数が増える問題はあるが柔軟に手順を組み立てることができる。しかしながら、どの距離のPEまでアクセスできるかは、時代の集積技術と応用分野からの性能要請に基づきトレードオフで決定されるものであるので、この従来例ではあくまで一例として示したにすぎず、以降の説明や本発明の内容をなんら制約するものではない。
【0027】
[表1]
;===================================================
;行列転置
;---------------------------------------------------
;Input
; TmR00(1行目)〜TmR07(8行目)
;---------------------------------------------------
;Output
; TmR20(1行目)〜TmR27(8行目)
;---------------------------------------------------
;Tmp
; TmR10,TmR11,TmR12,TmR13,TmR14,
; t1,t2,t3,t4,t5,t6,t7
;===================================================
;
【0028】
[表2]
;演算マスクの設定
settb/t1 #1,#3f8h ;01000000 ;STEP1
settb/t2 #2,#3f8h ;00100000 ;STEP2
settb/t3 #3,#3f8h ;00010000 ;STEP3
settb/t4 #4,#3f8h ;00001000 ;STEP4
settb/t5 #5,#3f8h ;00000100 ;STEP5
settb/t6 #6,#3f8h ;00000010 ;STEP6
settb/t7 #7,#3f8h ;00000001 ;STEP7
;
【0029】
[表3]
;1行目の配置
lda TmR0 ;STEP8
lda/t1 TmR1:L1 ;STEP9
lda/t2 TmR2:L2 ;STEP10
lda/t3 TmR3:L3 ;STEP11
ldf TmR4:L3,TmR10 ;STEP12
ldf TmR5:L3,TmR11 ;STEP13
ldf TmR6:L3,TmR12 ;STEP14
ldf TmR7:L3 ;STEP15
lda/t4 TmR10:L1 ;STEP16
lda/t5 TmR11:L2 ;STEP17
stf TmR10:U1 ;STEP18
lda/t6 TmR12:L3 ;STEP19
lda/t7 TmR10:L3,TmR20 ;STEP20
【0030】
[表4]
;2行目の配置
lda TmR0:U1 ;STEP21
lda/t1 TmR1 ;STEP22
lda/t2 TmR2:L1 ;STEP23
lda/t3 TmR3:L2 ;STEP24
lda/t4 TmR4:L3 ;STEP25
ldf TmR5:L3,TmR10 ;STEP26
ldf TmR6:L3,TmR11 ;STEP27
ldf TmR7:L3,TmR12 ;STEP28
lda/t5 TmR10:L1 ;STEP29
lda/t6 TmR11:L2 ;STEP30
lda/t7 TmR12:L3,TmR21 ;STEP31
【0031】
[表5]
;3行目の配置
lda TmR0:U2 ;STEP32
lda/t1 TmR1:U1 ;STEP33
lda/t2 TmR2 ;STEP34
lda/t3 TmR3:L1 ;STEP35
lda/t4 TmR4:L2 ;STEP36
lda/t5 TmR5:L3 ;STEP37
ldf TmR6:L3,TmR10 ;STEP38
ldf TmR7:L3,TmR11 ;STEP39
lda/t6 TmR10:L1 ;STEP40
lda/t7 TmR11:L2,TmR22 ;STEP41
【0032】
[表6]
;4行目の配置
lda TmR0:U3,TmR10 ;STEP42
lda/t1 TmR1:U2 ;STEP43
lda/t2 TmR2:U1 ;STEP44
lda/t3 TmR3 ;STEP45
lda/t4 TmR4:L1 ;STEP46
lda/t5 TmR5:L2 ;STEP47
ldf TmR7:L3,TmR11 ;STEP48
lda/t6 TmR6:L3 ;STEP49
lda/t7 TmR11:L1,TmR23 ;STEP50
【0033】
[表7]
;5行目の配置
lda TmR10:U1 ;STEP51
lda/t1 TmR1:U3 ;STEP52
lda/t2 TmR2:U2 ;STEP53
lda/t3 TmR3:U1 ;STEP54
lda/t4 TmR4 ;STEP55
lda/t5 TmR5:L1 ;STEP56
lda/t6 TmR6:L2 ;STEP57
lda/t7 TmR7:L3,TmR24 ;STEP58
【0034】
[表8]
;6行目の配置
ldf TmR1:U3,TmR11 ;STEP59
lda TmR10:U2 ;STEP60
lda/t1 TmR11:U1 ;STEP61
lda/t2 TmR2:U3 ;STEP62
lda/t3 TmR3:U2 ;STEP63
lda/t4 TmR4:U1 ;STEP64
lda/t5 TmR5 ;STEP65
lda/t6 TmR6:L1 ;STEP66
lda/t7 TmR7:L2,TmR25 ;STEP67
【0035】
[表9]
;7行目の配置
ldf TmR2:U3,TmR12 ;STEP68
lda TmR10:U3 ;STEP69
lda/t1 TmR11:U2 ;STEP70
lda/t2 TmR12:U1 ;STEP71
lda/t3 TmR3:U3 ;STEP72
lda/t4 TmR4:U2 ;STEP73
lda/t5 TmR5:U1 ;STEP74
lda/t6 TmR6 ;STEP75
lda/t7 TmR7:L1,TmR26 ;STEP76
【0036】
[表10]
;8行目の配置
ldf TmR10 ;STEP77
stf TmR14:L1 ;STEP78
lda TmR14:U3 ;STEP79
ldf TmR3:U3,TmR13 ;STEP80
lda/t1 TmR11:U3 ;STEP81
lda/t2 TmR12:U2 ;STEP82
lda/t3 TmR13:U1 ;STEP83
lda/t4 TmR4:U3 ;STEP84
lda/t5 TmR5:U2 ;STEP85
lda/t6 TmR6:U1 ;STEP86
lda/t7 TmR7,TmR27 ;STEP87
;
【0037】
次に、この従来例に係るプログラムリストで実現されている手順について説明する。まず、STEP1からSTEP7まで演算マスクビットを設定する。T1ビットはPE番号を8で割って余りが1のPEの全てについてそれぞれセットされる。T2ビットは同様に余りが2のPE全てについて、T3ビットは余りが3のPE全てについて、T4ビットは余りが4のPE全てについて、T5ビットは余りが5のPE全てについて、T6ビットは余りが6のPE全てについて、T7ビットは余りが7のPE全てについて各々セットされる。STEP8からSTEP20までは転置結果の1行目の配置変換を行う手順である。以下にデータ移動の様子を図示している。
【0038】
図6は従来例に係る行列転置方法において、STEP8〜STEP20までの手順により転置結果の1行目の配置変換を示す行列データを示す図である。図6に示すように、対角要素を除き、ハッチング部分のデータがこれらのステップで移動される。TmR20からTmR27までのレジスタに処理結果が格納される。TmR20は転置結果の1行目が配置されるが、図6とプログラムリストを見て明らかなように、行の要素の8PE毎に1個ずつ、PEシフト操作を介して列要素からデータ移動されていることがわかる。352個のPEに跨って44個の8×8の行列が配置されているので、行列要素としては1個ずつではあるが、全体としては44個のデータが同時並列に移動、配置されるステップである。
【0039】
以下同様に、各行の処理内容の図を示す。図7は従来例に係る行列転置方法において、STEP21〜STEP31までの手順により2行目の配置変換を示す行列データを示す図である。また、図8は従来例に係る行列転置方法において、STEP32〜STEP41までの手順により3行目の配置変換を示す行列データを示す図である。さらに、図9は従来例に係る行列転置方法において、STEP42〜STEP50までの手順により4行目の配置変換を示す行列データを示す図である。またさらに、図10は従来例に係る行列転置方法において、STEP51〜STEP58までの手順により5行目の配置変換を示す行列データを示す図である。また、図11は従来例に係る行列転置方法において、STEP59〜STEP67までの手順により6行目の配置変換を示す行列データを示す図である。さらに、図12は従来例に係る行列転置方法において、STEP68〜STEP76までの手順により7行目の配置変換を示す行列データを示す図である。またさらに、図13は従来例に係る行列転置方法において、STEP77〜STEP87までの手順により8行目の配置変換を示す行列データを示す図である。
【0040】
以上、並列型のSIMDプロセッサで近傍PEのレジスタアクセス機能と、PEの演算マスクにより、複数の行列転置処理を同時並列に実施する従来例に係る行列転置方法を示した。近傍PEのレジスタアクセスにより、PE間を跨るデータとPE内に配置されるデータを柔軟に移動、配置できることが示されている。また多数のPEを配列するプロセッサではその並列性により多数の行列データを並列同時に処理する方法が提供されうることが示されている。
【0041】
しかしながら、この従来例で示した方法では行列あたり1要素ずつ移動させるステップから構成されるため、並列性が高く処理効率が良いとはいえない欠点があった。さらにレジスタアクセス可能なPE間の距離が小さく限定されるプロセッサでは、回路の規則性が高く、複雑度、回路規模が小さく、より多数のPEを集積できうる利点はあるものの、可能な最大距離を超えた位置のPEのレジスタアクセスを行うには追加のステップが必要となり、処理速度と効率が低下する欠点が認められる。具体的には、この従来例においてデータ要素移動の個々のステップで距離3を越えるPEのデータへのアクセスは、都度3以下のPEシフトを組み合わせて多段ステップで実現しており、ステップ数が増えると全体のステップ数に与える影響が大きいという欠点がある。
【0042】
従来技術に係るビットスライス型のSIMDプロセッサでは一般的にプロセシングユニットの演算語長の制約から同時に並列処理できるデータの数に、最大で数個程度という制限があり、制限を越える大量のデータ処理を行うためには逐次外部キャッシュやメモリアクセスが必要となり、並列処理の効率が比較的低く速度の低下を招く問題点があった。
【0043】
さらに、別の形態に係る、プロセシングユニットを多数並列に配列する並列型のSIMDプロセッサでは、規則性が高く比較的小規模のプロセシングエレメント(PE)をより多数個配列して集積するものほど処理の並列性が増大し、処理効率はきわめて高くなる一方、データ移動可能なPEの範囲は装置回路的にPE自身の近傍距離に限られる傾向にあり、行列転置のようなデータ移動のPE間距離が比較的大きい処理ほど、データ移動ステップが多段で煩雑となり、処理ステップが増大して処理速度が低下する問題点があった。
【0044】
本発明の第1の目的は以上の問題点を解決し、多数のプロセシングエレメント(PE)を集積しうる並列型のSIMDプロセッサにおいて並列性の高い行列転置方法を用いたプロセッサ装置及びその演算方法を提供することにある。
【0045】
また、本発明の第2の目的は上記第1の目的に加えて、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップ数がより少ない行列転置方法を用いたプロセッサ装置及びその演算方法を提供することにある。
【0046】
さらに、本発明の第3の目的は上記第1及び第2の目的に加えて、PE間のデータ移動の並列性を高めて処理ステップがさらに少なく効率的な行列転置方法をプロセッサ装置及びその演算方法を提供することにある。
【課題を解決するための手段】
【0047】
第1の発明に係るプロセッサ装置は、複数のプロセシングエレメントを備えたプロセッサ装置において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とする。
【0048】
上記プロセッサ装置において、行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする。
【0049】
第2の発明に係るプロセッサ装置の演算方法は、複数のプロセシングエレメントを備えたプロセッサ装置の演算方法において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とする。
【0050】
上記プロセッサ装置の演算方法において、行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする。
【発明の効果】
【0051】
従って、本発明に係るプロセッサ装置及びその演算方法によれば、2のべき乗次の部分行列を対象に対角位置のブロックのデータを一括して移動、交換するステップを含み、データのPE間移動は2のべき乗の距離の移動を組み合わせ、それぞれの2のべき乗距離のデータ移動は並列に一括して行うことが可能となるため、データのPE間の移動距離が自身の近傍位置に限られるような、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップがより少ない行列転置方法を提供することができる。また、複数の行列データの転置処理を同時一括して並列処理することができるので処理全体のスループットは高くなる。さらに、複数の行列データをプロセッサ装置内に留め置き演算処理を進めることができるので外部キャッシュやメモリとのアクセス頻度を減らすことができ処理のスループット向上を図ることができる。
【0052】
また、本発明に係るプロセッサ装置及びその演算方法によれば、所定の演算マスク値を設定し、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータに対応する連続PEを並列動作させて並列同時にデータの移動、交換するステップを含むので、並列動作するPEの数が最大に保たれ、並列性が高く効率のきわめて高い行列転置方法を提供することができる。
【図面の簡単な説明】
【0053】
【図1】従来技術及び本発明の実施形態に係るSIMD型マイクロプロセッサ装置の基本構成を示すブロック図である。
【図2】本発明の実施形態に係るSIMD型マイクロプロセッサ装置の詳細構成を示すブロック図である。
【図3】図2のレジスタファイルのレジスタと演算アレイとを結び付けるマルチプレクサの機能構成を示すブロック図である。
【図4】従来例に係るMMX技術を用いた行列転置方法の一例を示すプログラムを示す図である。
【図5】従来例に係る行列転置方法において、行列データが列方向(図5の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。
【図6】従来例に係る行列転置方法において、STEP8〜STEP20までの手順により転置結果の1行目の配置変換を示す行列データを示す図である。
【図7】従来例に係る行列転置方法において、STEP21〜STEP31までの手順により2行目の配置変換を示す行列データを示す図である。
【図8】従来例に係る行列転置方法において、STEP32〜STEP41までの手順により3行目の配置変換を示す行列データを示す図である。
【図9】従来例に係る行列転置方法において、STEP42〜STEP50までの手順により4行目の配置変換を示す行列データを示す図である。
【図10】従来例に係る行列転置方法において、STEP51〜STEP58までの手順により5行目の配置変換を示す行列データを示す図である。
【図11】従来例に係る行列転置方法において、STEP59〜STEP67までの手順により6行目の配置変換を示す行列データを示す図である。
【図12】従来例に係る行列転置方法において、STEP68〜STEP76までの手順により7行目の配置変換を示す行列データを示す図である。
【図13】従来例に係る行列転置方法において、STEP77〜STEP87までの手順により8行目の配置変換を示す行列データを示す図である。
【図14】本実施形態に係る行列転置方法において、行列データが列方向(図14の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。
【図15】本実施形態に係る行列転置方法において、STEP4〜STEP7までの手順を実行後の行列データの配置を示す図である。
【図16】本実施形態に係る行列転置方法において、STEP19による2×2部分行列の処理終了時点での行列データの配置を示す図である。
【図17】本実施形態に係る行列転置方法において、STEP20〜STEP23までの手順を実行後の行列データの配置を示す図である。
【図18】本実施形態に係る行列転置方法において、STEP24〜STEP27までの手順を実行後の行列データの配置を示す図である。
【図19】本実施形態に係る行列転置方法において、STEP24〜STEP27、STEP28〜STEP31、STEP32〜STEP35までの手順を実行後の行列データの配置を示す図である。
【図20】本実施形態に係る行列転置方法において、STEP36〜STEP41までの手順を実行後の行列データの配置を示す図である。
【図21】本実施形態に係る行列転置方法において、STEP42〜STEP47までの手順を実行後の行列データの配置を示す図である。
【図22】本実施形態に係る行列転置方法において、STEP48〜STEP53までの手順を実行後の行列データの配置を示す図である。
【図23】本実施形態に係る行列転置方法において、STEP54〜STEP59までの手順を実行後の行列データの配置を示す図である。
【発明を実施するための形態】
【0054】
以下、本発明に係る実施形態について図面を参照して説明する。なお、以下の各実施形態において、同様の構成要素については同一の符号を付している。
【0055】
実施形態の基本構成.
図1は本発明の実施形態に係るSIMD型マイクロプロセッサ2の基本構成を示すブロック図である。実施形態に係るSIMD型マイクロプロセッサ2は、主としてプロセッサ2全体を制御するグローバルプロセッサ(GP)4と、主として外部入出力装置からデータを入力しデータ処理を行い、外部入出力装置にデータを出力するプロセシングエレメント(PE)3とを備えて構成される。PE3は、複数データを同時に処理するために複数用意されている。図1では、1個のGP4と、256個のPE3とにより、SIMD型マイクロプロセッサ2が構成されている。
【0056】
図2は本発明の実施形態に係るSIMD型マイクロプロセッサ装置の詳細構成を示すブロック図である。図2に示されるように、GP4は、
(a)命令コードで構成されるプログラムを格納するためのプログラムRAM10と、
(b)GP4での演算データを格納するデータRAM12と、
(c)プログラムを解読し各種ブロックに各種制御信号を送るシーケンシャルユニット(SCU)9と、
(d)データを格納する複数の汎用レジスタ(G0〜G3)と、
(e)SCU9にプログラムの命令コードを送るためにプログラムのアドレスを保持するプログラムカウンタ(PC)14と、
(f)データメモリにスタックを形成するためデータメモリのアドレスを格納するスタックポインタ(SP)24と、
(g)プログラムの途中でサブルーチン処理を行う際には分岐が発生するが分岐前のアドレスを格納する複数のリンクレジスタ(LS、LI、LN)と、
(h)データメモリのデータ、命令コード中に記述された数値(即値)データ、もしくは汎用レジスタに格納されているデータのいずれかの組み合わせに対して、算術論理演算を行う算術論理演算装置(ALU)11と、
(i)プロセッサの状態を保持するプロセッサステータスレジスタ(図示せず。)と、
(j)ハードウェア割り込みとソフトウェア割り込みを制御する割り込み制御回路(図示せず。)と、
(k)外部入出力に直接接続され外部からのデータの入出力を制御する外部入出力制御回路(図示せず。)とを備えて構成される。
【0057】
図2では図示していないが、上記SCU9は、GP命令を解読し主にGP内の各ブロックに制御信号を発生するGP命令デコーダと、PE命令を解読し主にPE内の各ブロックに制御信号を発生するPE命令デコーダとで、構成される。すなわち、本プロセッサに係る命令コードは、主にGP4内の各ブロックを制御し、プログラムのシーケンスを決定したり、PEに転送する共通データをGP4内のALU11で加工したりするGP命令と、外部入出力装置から一度に入力されたデータをPE3毎に処理をさせるプロセシングエレメント命令とに分類される。
【0058】
図1に示すように、各PE3は、外部入出力装置からの入出力データを一時的に保持するレジスタファイル6と、PE3内で算術論理演算やビット演算のデータ処理を行うための演算アレイ8を含む。さらに、図2に示すようにレジスタファイル6には、例えば、R0〜R31までの8ビットのレジスタ34が32個用意されている。これらのレジスタ34からデータが演算アレイ8に転送され、また逆に、演算アレイ8からデータが転送されてレジスタ34に格納される。レジスタ34と演算アレイ6とのバスは、8ビットの双方向バスである。
【0059】
さらに、図2に示すように、単体の演算アレイ8は演算ユニットであり、
(a)レジスタファイル6からのデータをシフトして符号付き拡張もしくは符号無し拡張をして16ビットデータに加工するシフト拡張器44と、
(b)例えば、Aレジスタ38とFレジスタ40などを含む複数の汎用レジスタと、
(c)レジスタファイル6からのデータを、シフト拡張器44を経由して加工し1入力とし、他方の入力をAレジスタ36からの入力とする算術論理演算装置(ALU)36と、
(d)PE番号マスク回路、固定値選択回路、及びnおきにビットパターンデータ出力回路のそれぞれからの出力を入力とし、自らの出力をAレジスタ38やTレジスタ54に繋げる選択回路35とを備えて構成される。
【0060】
算術論理演算装置(ALU)36の出力は、Aレジスタ36もしくはFレジスタ40に一時格納されように設定されているが、Aレジスタ36からレジスタファイル6の所定の1レジスタ34にデータ転送されることも可能である。
【0061】
また、演算アレイ8は、詳細後述するように、「Tレジスタ」と呼ばれる演算制御レジスタ54を備える。ALU36からの出力は、当該Tレジスタ54によって、Aレジスタ36もしくはFレジスタ40への書き込み内容が制御される。例えば、演算制御レジスタ(Tレジスタ)54の中の所定の1ビットの状態に応じて、「1」であればAレジスタ36もしくはFレジスタ54への書き込みを行い、「0」であれば行わないというような制御が行われる。
【0062】
図3は図2のレジスタファイルのレジスタと演算アレイとを結び付けるマルチプレクサの機能構成を示すブロック図である。図3において、PEi(i=0,1,2,…,255)のPEに備わるマルチプレクサは7対1のマルチプレクサであり、PEi−3(PEiから3つ左隣りに位置する)、PEi−2(PEiから2つ左隣りに位置する)、PEi−1(PEiから1つ左隣りに位置する)、PEi、PEi+1(PEiから1つ右隣りに位置する)、PEi+2(PEiから2つ右隣りに位置する)、PEi+3(PEiから3つ右隣りに位置する)のPE3のレジスタファイル6からのデータを入出力することができるように設定されている。この機能を、PEシフト機能と称する。マルチプレクサによって選択されたデータは、演算アレイ8のシフト拡張器44に転送される。
【0063】
ここで、PE3の番号を含む呼称について定義する。図2に示すように、本実施形態に係るSIMD型マイクロプロセッサ2には256個のPE3が設置されており、それらPE3の個々に対し、(図2では左側から)PE0、PE1、PE2、PE3、…、PE254、PE255というように、PE番号を付すと定義する。
【0064】
実施形態.
本発明に係る好適な実施形態を以下に説明する。以下に示す表11〜表15は並列型のSIMDプロセッサにおいて行列転置処理方法の手順を示したプログラムリストである。本実施形態に係るSIMDプロセッサの形態及び命令セットの説明は、上述の従来例と同様であるので省略する。命令に付加される/f1オプションは、マスクビットT1に基づく演算制御のための修飾で、T1ビットが0であれば命令実行を行うよう制御される。/fに続く数字はT1〜T7ビットを指定するものである。プロセッサにおいてどの距離のPEまでアクセスできるかは、時代の集積技術と応用分野からの性能要請に基づきトレードオフで決定されるものであるので、本実施形態ではあくまで一例として示したにすぎず、以降の説明や本発明の内容をなんら制約するものではない。
【0065】
本実施形態では、352個のPEを備えるプロセッサ装置で処理を行う方法を示す。PEにはそれぞれに、識別するためのPE番号(アドレス)が0(下位側)から351(上位側)まで付加されている。以下、本実施形態では8×8要素の行列転置処理を行う方法について示している。
【0066】
図14は本実施形態に係る行列転置方法において、行列データが列方向(図14の縦方向)のベクトルデータがPEの演算レジスタTmR0〜TmR7に配置されかつPE方向に行ベクトルをなすように配列された行列データを示す図である。すなわち、8個のPEで1つの行列データを保持するよう配列されている。本実施形態では、352個のPEを配するプロセッサであるため全てのPEにデータを配置することで総計44個の行列を並列に処理することができるようになる。転置処理の結果はTmR0からTmR7までのレジスタに再び格納されるよう動作する。
【0067】
[表11]
;===================================================
;行列転置
;---------------------------------------------------
;Input
; TmR0(1行目)〜TmR7(8行目)
;---------------------------------------------------
;Output
; TmR0(1行目)〜TmR7(8行目)
;---------------------------------------------------
;Tmp
; TmR8~TmR9
; t1,t2,t3
;===================================================
;
【0068】
[表12]
;演算マスクの設定
settb/t1#1,#3feh ;01010101 ;STEP1
settb/t2#2,#3fdh ;00110011 ;STEP2
settb/t3#4,#3fbh ;00001111 ;STEP3
;
【0069】
[表13]
;2×2部分行列の転置
lda TmR0,TmR8 ;STEP4
ldf TmR1,TmR9 ;STEP5
ldf/f1 TmR8:u1,TmR1 ;STEP6
lda/t1 TmR9:l1,TmR0 ;STEP7
;
lda TmR2,TmR8 ;STEP8
ldf TmR3,TmR9 ;STEP9
ldf/f1 TmR8:u1,TmR3 ;STEP10
lda/t1 TmR9:l1,TmR2 ;STEP11
;
lda TmR4,TmR8 ;STEP12
ldf TmR5,TmR9 ;STEP13
ldf/f1 TmR8:u1,TmR5 ;STEP14
lda/t1 TmR9:l1,TmR2 ;STEP15
;
lda TmR6,TmR8 ;STEP16
ldf TmR7,TmR9 ;STEP17
ldf/f1 TmR8:u1,TmR7 ;STEP18
lda/t1 TmR9:l1,TmR6 ;STEP19
;
【0070】
[表14]
;4×4部分行列の転置
lda TmR0,TmR8 ;STEP20
ldf TmR2,TmR9 ;STEP21
ldf/f2 TmR8:u2,TmR2 ;STEP22
lda/t2 TmR9:l2,TmR0 ;STEP23
;
lda TmR1,TmR8 ;STEP24
ldf TmR3,TmR9 ;STEP25
ldf/f2 TmR8:u2,TmR3 ;STEP26
lda/t2 TmR9:l2,TmR1 ;STEP27
;
lda TmR4,TmR8 ;STEP28
ldf TmR6,TmR9 ;STEP29
ldf/f2 TmR8:u2,TmR6 ;STEP30
lda/t2 TmR9:l2,TmR4 ;STEP31
;
lda TmR5,TmR8 ;STEP32
ldf TmR7,TmR9 ;STEP33
ldf/f2 TmR8:u2,TmR7 ;STEP34
lda/t2 TmR9:l2,TmR5 ;STEP35
;
【0071】
[表15]
;8×8最終行列の転置
lda TmR0 ;STEP36
sta TmR8:l2 ;STEP37
ldf TmR4 ;STEP38
stf TmR9:u2 ;STEP39
ldf/f3 TmR8:u2,TmR4 ;STEP40
lda/t3 TmR9:l2,TmR0 ;STEP41
;
lda TmR1 ;STEP42
sta TmR8:l2 ;STEP43
ldf TmR5 ;STEP44
stf TmR9:u2 ;STEP45
ldf/f3 TmR8:u2,TmR5 ;STEP46
lda/t3 TmR9:l2,TmR1 ;STEP47
;
lda TmR2 ;STEP48
sta TmR8:l2 ;STEP49
ldf TmR6 ;STEP50
stf TmR9:u2 ;STEP51
ldf/f3 TmR8:u2,TmR6 ;STEP52
lda/t3 TmR9:l2,TmR2 ;STEP53
;
lda TmR3 ;STEP54
sta TmR8:l2 ;STEP55
ldf TmR7 ;STEP56
stf TmR9:u2 ;STEP57
ldf/f3 TmR8:u2,TmR7 ;STEP58
lda/t3 TmR9:l2,TmR3 ;STEP59
【0072】
STEP1からSTEP3までは処理で必要な演算マスク値の設定を以下のごとく行っている。
[数5]
settb/t1 #1,#3feh
命令は、PE番号の最下位ビット(bit0)が1のもの全てのT1ビットをセット(1を設定)する。このことにより、T1ビットの値は、最下位PEから010101010…が設定される。すなわち、偶数番号のPEのT1ビットは0に、奇数ビットのT1ビットは1に設定される。
【0073】
[数6]
settb/t2 #2,#3fdh
命令は、PE番号のbit1(最下位ビットから次のビットをいう。)が1のもの全てのT2ビットをセット(1を設定)する。このことにより、T2ビットの値は、最下位PEから001100110011…が設定される。すなわち、連続する4つのPE毎に連続する下位2つのPEのT2ビットは0に、上位2つのPEのT2ビットは1に設定される。
【0074】
[数7]
settb/t3 #4,#3fbh
命令は、PE番号のbit2(最下位ビットから2ビット目のビットをいう。)が1のもの全てのT3ビットをセット(1を設定)する。このことにより、T3ビットの値は、最下位PEから0000111100001111…が設定される。すなわち連続する8つのPE毎に連続する下位4つのPEのT3ビットは0に、上位4つのPEのT3ビットは1に設定される。
【0075】
STEP4からSTEP19までは、隣り合う2行のデータを対象に、これに内包される2×2部分行列の対角要素の交換処理を行うステップである。参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離1のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、偶数もしくは奇数のPEが常に動作していることから処理の並列度が高いことを特徴としている。
【0076】
図15は本実施形態に係る行列転置方法において、STEP4〜STEP7までの手順を実行後の行列データの配置を示す図である。また、図16は本実施形態に係る行列転置方法において、STEP19による2×2部分行列の処理終了時点での行列データの配置を示す図である。
【0077】
STEP20からSTEP35までは、隣り合う連続4行のデータを対象に、これに内包される4×4部分行列を対象にその中の対角ブロック(2×2要素)の交換処理を行うステップである。交換処理を行う2行データを対象に参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離2のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、4つのPE毎に2つのPEが常に動作していることから処理の並列度が高いことを特徴としている。
【0078】
図17は本実施形態に係る行列転置方法において、STEP20〜STEP23までの手順を実行後の行列データの配置を示す図である。図17から明らかなように、最初の2行分のデータ移動を行っている。
【0079】
図18は本実施形態に係る行列転置方法において、STEP24〜STEP27までの手順を実行後の行列データの配置を示す図である。図18から明らかなように、次の2行分のデータ移動を行っている。これで前半の4×4部分行列の対角2×2要素ブロックの移動が完了している。
【0080】
図19は本実施形態に係る行列転置方法において、STEP24〜STEP27、STEP28〜STEP31、STEP32〜STEP35までの手順を実行後の行列データの配置を示す図である。図19から明らかなように、2行目と6行目、3行目と7行目、4行目と8行目の配置変換がそれぞれ実施される。
【0081】
次いで、STEP36からSTEP59までは、最後に8行のデータを対象に、その対角ブロック(4×4要素)の交換処理を行うステップである。交換処理を行う2行データを対象に参照する現データをテンポラリレジスタTmR8、TmR9に複写し、演算マスクを用いて、格納位置のPEから距離4のPEシフトをともなうアキュムレータロード命令で参照位置のレジスタを読出すことでデータの移動配置を行い、特に、8つのPE毎に4つのPEが常に動作していることから処理の並列度が高いことを特徴としている。移動距離4の場合は、1段のPEシフトでは届かないので、2段のPEシフトで対応している。1段目は距離2のシフトを行ったデータをテンポラリレジスタに一時的に保存し、そのレジスタをさらに距離2のPEシフトで参照して距離4の移動配置を行う。1段目の距離2のPEシフトをともなう移動命令は全数のPEで同時並列に実行できるため、ステップ数の増加の影響は最小限にすることができる。
【0082】
図20は本実施形態に係る行列転置方法において、STEP36〜STEP41までの手順を実行後の行列データの配置を示す図である。図20から明らかなように、最初の2行分のデータ移動を行っている。STEP36とSTEP37は、1行目のデータ(TmR0)を距離2の下位へのPEシフトを行い、テンポラリレジスタTmR8に複写する手順である。同様に、STEP38とSTEP39は5行目のデータ(TmR4)を距離2の上位へのPEシフトを行い、テンポラリレジスタTmR9に複写する手順である。以上は全てのPEで実行される。STEP40とSTEP41でさらに距離2のPEシフトを行って先のテンポラリレジスタを参照することで距離4のデータ移動、交換を実現している。以上は演算マスクビットの設定により、8つのPE毎に4つのPEで同時並列に実行される。
【0083】
以下同様にSTEP42〜47、STEP48〜53、STEP54〜59実施後のデータ配置を以下の図に示す。すなわち、図21は本実施形態に係る行列転置方法において、STEP42〜STEP47までの手順を実行後の行列データの配置を示す図である。また、図22は本実施形態に係る行列転置方法において、STEP48〜STEP53までの手順を実行後の行列データの配置を示す図である。さらに、図23は本実施形態に係る行列転置方法において、STEP54〜STEP59までの手順を実行後の行列データの配置を示す図である。
【0084】
以上説明したように、本実施形態によれば、2×2部分行列から始めて、2のべき乗次の行列である4×4、8×8行列を対象に各々対角位置のブロックのデータを一括交換する手順を順次行うステップを含んでいることが本実施形態の別の特徴である。
【0085】
本実施形態によれば、行列要素を1つずつ個々に多段の移動ステップと組み合わせて移動させていた自社従来例に比べて、データのPE間移動を2のべき乗の距離に分割して(例えば7つの位置移動であれば、1+2+4のように組み合わせて移動することに結果としてなる)それぞれの2のべき乗距離の移動は並列に一括して行うため、回路及び命令セットで制限される最大のPEシフト量を超えるデータの移動においてもステップ数の増加が少なく効率が良いという特有の効果を有する。
【0086】
また、各部分行列の処理ステップでは、演算マスク値設定の工夫によって、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータを対応する連続PEを並列動作さることにより並列同時に移動可能となるステップを含んでいる特長的な処理手順が示されている。このことにより、並列動作するPEの数が常に最大に保たれており、並列処理効率はきわめて高い。
【0087】
以上の優位点から、自社従来例に比べて処理ステップは30%強縮減され(87個のステップ数から59個のステップ数に減縮)、命令数も縮減されるのでコードサイズを減らすこともできる。さらにプロセッサに集積された最大PE数まで対象行列をマッピングすることで、複数の行列データを同時一括して並列処理することができるので処理全体のスループットは高くなる。できるだけ大量のデータをプロセッサ内に留め置き、並列処理を進め、外部キャッシュやメモリとのアクセス頻度を減らすことは全体のスループット向上に資すると認められる。もしくは、本実施形態では、2×2部分行列から始めて、4×4、8×8行列を対象に各々対角位置のブロックのデータを一括交換する手順を順次行うステップを含んでいるが、8×8行列から始めて順に4×4、2×2と繰り返し処理するステップに構成しても有効に機能することは明らかである。
【産業上の利用可能性】
【0088】
以上詳述したように、本発明に係るプロセッサ装置及びその演算方法によれば、2のべき乗次の部分行列を対象に対角位置のブロックのデータを一括して移動、交換するステップを含み、データのPE間移動は2のべき乗の距離の移動を組み合わせ、それぞれの2のべき乗距離のデータ移動は並列に一括して行うことが可能となるため、データのPE間の移動距離が自身の近傍位置に限られるような、より大規模な並列性を有するプロセッサにおいてもPE間のデータ移動効率が良く、処理ステップがより少ない行列転置方法を提供することができる。また、複数の行列データの転置処理を同時一括して並列処理することができるので処理全体のスループットは高くなる。さらに、複数の行列データをプロセッサ装置内に留め置き演算処理を進めることができるので外部キャッシュやメモリとのアクセス頻度を減らすことができ処理のスループット向上を図ることができる。
【0089】
また、本発明に係るプロセッサ装置及びその演算方法によれば、所定の演算マスク値を設定し、2N個の連続位置のデータ毎に2N−1個(N=1,2,…)のデータに対応する連続PEを並列動作させて並列同時にデータの移動、交換するステップを含むので、並列動作するPEの数が最大に保たれ、並列性が高く効率のきわめて高い行列転置方法を提供することができる。
【0090】
さらに、本発明に係るプロセッサ装置及びその演算方法によれば、画像信号などの二次元信号のデータのデジタル処理において、例えばそのデータの圧縮や伸張を行うための二次元離散コサイン変換(DCT又はDCT変換)における変換処理の次元の方向を入れ替える処理すなわち2次元行列における数学的転置処理に広く適用できる。
【符号の説明】
【0091】
2…SIMD型マイクロプロセッサ、
3…プロセシングエレメント(PE)、
4…グローバルプロセッサ(GP)、
6…レジスタファイル、
8…演算アレイ、
9…シーケンシャルユニット(SCU)、
10…プログラムRAM、
11…算術論理演算装置(ALU)、
12…データRAM、
14…プログラムカウンタ(PC)、
24…スタックポインタ(SP)、
34,38,40,54…レジスタ、
44…シフト拡張器、
G0〜G3…汎用レジスタ、
LS,LI,LN…リンクレジスタ。
【先行技術文献】
【特許文献】
【0092】
【特許文献1】特開2005−174293号公報
【特許文献2】特開昭62−107381号公報
【特許文献3】特開2005−267615号公報
【特許文献4】特開2002−149400号公報
【特許文献5】特表2002−518730号公報
【特許文献6】特許第4398965号公報
【特許文献7】特許第3742745号公報
【特許文献8】特許第3779540号公報
【特許請求の範囲】
【請求項1】
複数のプロセシングエレメントを備えたプロセッサ装置において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とするプロセッサ装置。
【請求項2】
行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする請求項1記載のプロセッサ装置。
【請求項3】
複数のプロセシングエレメントを備えたプロセッサ装置の演算方法において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とするプロセッサ装置の演算方法。
【請求項4】
行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする請求項3記載のプロセッサ装置の演算方法。
【請求項1】
複数のプロセシングエレメントを備えたプロセッサ装置において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とするプロセッサ装置。
【請求項2】
行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする請求項1記載のプロセッサ装置。
【請求項3】
複数のプロセシングエレメントを備えたプロセッサ装置の演算方法において、
上記各プロセシングエレメントは
複数のデータを保持する演算レジスタと、
所定の演算マスク値に従って命令の実行又は非実行を制御する制御手段とを備え、
上記各プロセシングエレメントはさらに、
処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタ値を参照する手段と、演算結果を処理を行うプロセッシングエレメント自身以外のプロセシングエレメントのレジスタに転送して格納する手段とのうちの少なくとも1つの手段とを備え、
上記プロセッサ装置は、上記各プロセシングエレメント方向に行ベクトルデータが配列され、かつ上記各プロセシングエレメント内レジスタ方向に列ベクトルデータがそれぞれ配列された複数個の行列データの数学的転置を行うときに、
上記各プロセシングエレメント間のレジスタ参照、格納又は移動を行う単一命令複数データ型の演算命令を用いて、対角位置の要素データ又はベクトルデータの移動をして交換を行うステップを含み、行列に含まれる2のべき乗次の部分行列を対象にして、
最小2次の行列(2×2要素)では対角要素データの移動又は交換を行う第1の手順と、
上位のべき乗次数の部分行列では対角位置の下位の部分行列の要素データ群をブロックとして一括に移動又は交換する第2の手順とを実行し、
上記第1及び第2の手順を、上位次数から最小次数まで、又は最小次数から上位次数まで順次繰り返して行って複数の行列データを一括して並列同時に転置処理することを特徴とするプロセッサ装置の演算方法。
【請求項4】
行列データの対角位置の要素又はベクトルデータの移動又は交換を行う手順において、上記プロセッサ装置の単一命令複数データ型の演算命令と演算マスク値による制御を用いて、連続して配置される2N個の各プロセシングエレメント毎に、連続して配置される2N−1個のデータ(ここで、Nは1以上の自然数である。)の移動又は交換を一括して同時並列に行うことを特徴とする請求項3記載のプロセッサ装置の演算方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【公開番号】特開2012−190389(P2012−190389A)
【公開日】平成24年10月4日(2012.10.4)
【国際特許分類】
【出願番号】特願2011−55211(P2011−55211)
【出願日】平成23年3月14日(2011.3.14)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
【公開日】平成24年10月4日(2012.10.4)
【国際特許分類】
【出願日】平成23年3月14日(2011.3.14)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
[ Back to top ]