JPH0434191B2

JPH0434191B2 -

Info

Publication number: JPH0434191B2
Application number: JP61068387A
Authority: JP
Inventors: Masami Takahata; Juji Aoki
Original assignee: Hitachi Ltd; Hitachi Computer Engineering Co Ltd
Current assignee: Hitachi Ltd; Hitachi Computer Engineering Co Ltd
Priority date: 1986-03-28
Filing date: 1986-03-28
Publication date: 1992-06-05
Also published as: JPS62226275A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明はベクトル処理装置に係り、特に行列形
式データの処理において、疎行列データのアクセ
スを高速に処理するに好適なベクトル処理装置に
関する。

〔従来の技術〕

ベクトル処理装置において、科学技術計算に現
れる大規模の行列計算では、扱うデータが非常に
大きく、そのままの形では主記憶に収まらない場
合がある。また疎行列を扱う行列計算では、計算
結果に関与するのはごく少数の非零の要素であ
る。このため主記憶上には圧縮された形式で行列
データを蓄えておき、計算時にベクトル・レジス
タ上に伸張して転送する機能を備えることによつ
て記憶容量の制約を解消しつつ、行列計算の高速
化をはかつている。

この種のベクトル処理装置では、ベクトル・レ
ジスタ上の伸張されたデータの有効性を示すため
にマスク・レジスタが設けられている。マスク・
レジスタの各ビツトはベクトル・レジスタの対応
する要素の有効性を示す。ベクトル・レジスタの
ｎ番目の要素に対応するマスク・ビツトVMR
（ｎ）が値“１”であるとき該要素は有効、“０”
であるとき無効であることが示される。

主記憶上の圧縮されたデータは、先頭アドレス
を保持するアドレス・レジスタVARと間隔値を
保持するインクリメント・レジスタVIRとによつ
て次のようにアドレス付けされる。ｎ番目の要素
のアドレスは、 a_o＝VAR＋（_o-1 〓ⁱ⁼⁰ VMR(i)）＊VIR ……(1) となる。主記憶ではｎ番目の要素以前の有効要素
のみが主記憶上に圧縮されて配置されるので、ｎ
番目の要素のアドレスは、該要素以前の“１”の
マスク・ビツトのカウント数にインクリメントを
乗じ、先頭アドレスを加えた値となる。

主記憶上の圧縮されたデータとベクトル・レジ
スタ上の伸張されたデータとの間の転送は、マス
ク・レジスタの内容によつて制御される。ｎ番目
の要素に対しては、マスク・ビツトVMR（ｎ）
が値“１”をとる場合に主記憶からベクトル・レ
ジスタへのロード、またはベクトル・レジスタか
ら主記憶へのストアが行われる。値“０”を取る
場合にはロード、ストアは行われない。以上のよ
うにマスク・ビツトによるメモリ・リクエスト制
御が行われ、先頭要素から順次転送が行われる。

このような構成をもつベクトル処理装置では、
従来、アドレス計算は次のように遂次的に行われ
る。

a_o＝a_o-1＋VMR（ｎ−１）＊VIR……(2) ここにa_oはｎ番目の要素の主記憶アドレス、
a_o-1は直前のｎ−１番目の要素の主記憶アドレス
である。このため、データ転送は逐次的に１本の
ロード・ストア・パイプラインで行われていた。
なお、この種の装置として関連するものには例え
ば特開昭58−214963号公報が挙げられる。

〔発明が解決しようとする問題点〕上記従来技術は、要素並列の多重パイプライン
方式の適合性については配慮されておらず、多重
化されたパイプラインが有効に利用されないとい
う問題があつた。つまり、最近のベクトル処理装
置では、主記憶からベクトル・レジスタへデータ
を転送する能力を増強するために、複数のロー
ド・ストア・パイプラインが設置され、データ中
の複数の要素を並列に一度に転送する機構があ
る。ところが上記の圧縮・伸張型のデータ転送の
場合には、主記憶にアクセスすべきアドレスがデ
ータの有効性を示すマスク・ビツトの制御の下で
遂次的にしか生成されない。このため複数設置さ
れたロード・ストア・パイプラインの内、１本で
しかデータ転送を行うことができなかつた。

本発明の目的は、複数設置されたロード・スト
ア・パイプラインにおいて、複数の要素の主記憶
アドレスを並列に計算し、要素並列に圧縮・伸張
型のデータ転送を実行するベクトル処理装置を提
供することにある。

〔問題を解決するための手段〕

本発明は、各パイプラインで処理すべき要素の
主記憶アドレスを並列に計算できるように各パイ
プラインのアドレス計算回路を構成することによ
り達成される。

各パイプラインのアドレス計算回路を、各パイ
プラインで処理すべき要素番号を認識し、マス
ク・ビツトを選択してマスク・ビツトの有効数を
計数するカウンタ、カウンタの内容に基づき要素
の間隔値、インクリメントの倍数を発生する倍数
発生回路、各パイプラインにおいて前ステージに
て処理した要素の主記憶アドレスに上記で発生し
た倍数を加えることによつて、各パイプラインに
おいて該ステージにて処理すべき要素の主記憶ア
ドレスを求める多入力の加算器で構成する。

〔作用〕

要素並列の多重パイプラインにおいて、各パイ
プラインで並列にアドレス計算を実行するために
は次のような計算を実行しなければならない。

ここでＭは多重パイプラインの本数、a_o〜
a_o+M-1は該ステージで処理すべき要素の主記憶ア
ドレス、a_o-M〜a_o-1は前ステージで処理した要素
の主記憶アドレスである。VMR(i)はｉ番目の要
素に対応するマスク・ビツトであり、VIRは要素
の間隔値、インクリメントである。１本のパイプ
ラインについて見ると、前ステージで処理したｎ
＋ｊ−Ｍ番目の要素の主記憶アドレスa_o+j-Mと該
ステージで処理すべきｎ＋ｊ番目の要素の主記憶
アドレスの差は、インクリメントVIRの倍数（_o+j-1 〓^i=n+j-M VMR−(i)）＊VIRとなつている。この
倍数は、前ステージで処理した要素に対応するＭ
個のマスク・ビツトの内、該パイプラインで処理
した要素から要素番号が後の要素に対応する有効
マスク・ビツト数_o-1 〓^i=n+j-M VIR(i)と、該ステージで
処理する要素に対応するＭ個のマスク・ビツトの
内、該パイプラインで処理する要素より要素番号
が前の要素に対応する有効マスク・ビツト数_o+j-1 〓ⁱ⁼ⁿ VMR(i)との和から作られる。

したがつて、各パイプラインのアドレス計算回
路において、カウンタによつて上記有効ビツト数
を計数し、そのカウント値に基づいて倍数発生回
路にてインクリメントVIRの倍数を発生し、加算
器によつて該パイプラインで前ステージに処理し
たｎ＋ｊ−Ｍ番目の要素の主記憶アドレスa_o+j-M
に加算すると、該パイプラインで次のステージで
処理すべきｎ＋ｊ番目の要素の主記憶アドレス
a_o+jが求まる。以上により複数のパイプラインに
おいて複数の要素の主記憶アドレスを並列に得る
ことができる。

各パイプラインにおいて処理すべき要素に対応
するマスク・ビツトが“１”の場合、上記アドレ
ス計算によつて得られた主記憶アドレスを用いて
メモリ・リクエストを主記憶に対して発行し、ロ
ード・ストア処理を行う。マスク・ビツトが
“０”の場合には、アドレス計算は行うが、メモ
リ・リクエストは抑止する。この場合には、アド
レス計算回路内に保持される主記憶アドレスが更
新されるのみである。

処理すべき残り要素数は、現在の残り要素数か
ら、１ステージで処理される要素数（これはパイ
プライン本数に等しい。）を減算することによつ
て得られる。そして、残り要素数が非正になつた
ことを検出器によつて検出し、ロード・ストア処
理を終了する。

〔実施例〕

以下、本発明の内容を図を用いて説明する。

第１図は本発明が適用されるベクトル処理装置
の全体構成を示すものである。第１図において、
１は主記憶（MS）、２はベクトル・レジスタ
（VR）、３はマスク・レジスタ（VMR）、４はロ
ード・ストア・パイプライン（LS）、５は演算器
（ALU）、６はデータ分配回路、７はデータ選択
回路である。ベクトル・レジスタ２は各々Ｌ個の
要素を格納する容量を持ち、全体でVR₀〜VR₇で
示す８本設けられている。マスク・レジスタ３は
Ｌビツトで１本設けられている。マスク・レジス
タ３の１ビツトがベクトル・レジスタ２の１要素
の有効性を示す。尚、本実施例では簡略化のため
マスク・レジスタを１本とするが、マスク・レジ
スタは複数あつても差しつかえない。ロード・ス
トア・パイプライン４はLS₀〜LS₇で示す８本、
演算器５はALU₀〜ALU₇で示す８個とする。

各ロード・ストア・パイプラインは主記憶上の
行列型式データの各要素の主記憶アドレスを順次
計算し、主記憶に対してメモリ・リクエストを発
行する。主記憶アドレスの計算結果はパイプライ
ン動作の基本単位である１ステージごとに得ら
れ、メモリ・リクエストも１ステージ・ピツチで
発行される。ロード命令、またはストア命令が起
動されると、８本のロード・ストア・パイプライ
ン４、LS₀、LS₁、…、LS₇が同時にロード・ス
トア処理を開始する。第１ステージでは、０番、
１番、…、７番の要素の主記憶アドレスa₀、a₁、
…、a₇が８本のパイプライン４において同時に計
算され、８個のメモリ・リクエストが主記憶１に
対して発行される。第２ステージでは、８番、９
番、…、15番の要素の主記憶アドレスa₈、a₉、
…、a₁₅が８本のパイプライン４において同時に
計算され、８個のメモリ・リクエストが主記憶１
に対して発行される。以下、１ステージごとに８
個の要素の主記憶アドレスが８本のロード・スト
ア・パイプライン４において同時に計算され、８
個のメモリ・リクエストが主記憶１に対して発行
される。そして該メモリ・リクエストに基づき、
８個の要素のデータ転送が主記憶１とベクトル・
レジスタ２との間で行われる。

ロード命令の場合には、主記憶上のデータのア
ドレスがロード・ストア・パイプライン４からパ
ス８を介して主記憶１に送られ、データが主記憶
１からパス９を介しロード・ストア・パイプライ
ン４に取り出される。さらにデータはパス１０を
介しデータ分配回路６に入り、命令で指定された
ベクトル・レジスタ２に対してパス１１を介し書
き込まれる。

ストア命令の場合には、命令によつて指定され
たベクトル・レジスタ２上のデータがパス１２を
介しデータ選択回路７に読み出され、パス１５を
介してロード・ストア・パイプライン４に入る。
ロード・ストア・パイプライン４では主記憶アド
レスが与えられ、主記憶アドレスはパス８に乗せ
て、データはパス１６に乗せて主記憶１に送り込
まれる。

データがベクトル・レジスタ２にロードされて
からストアされるまでの間にデータに対する演算
が行われる。演算命令によつて指定される３本の
レジスタ間で演算が行われる。３本のベクトル・
レジスタの内の２本はオペランドが格納されてい
て、オペランドはデータ選択回路７を介して読み
出されパス１３を経由して演算器５に入力され
る。演算結果は演算器５から出力され、パス１４
を経由しデータ分配回路６を介してベクトル・レ
ジスタ２に書き込まれる。演算命令が要素対応に
マスク・ビツトを生成するマスク生成命令である
場合には、演算結果として得られるマスク・ビツ
トはマスク・レジスタ３に書き込まれる。

ロード・ストア・パイプライン４におけるロー
ド・ストア処理は各要素ごとにマスク・レジスタ
３のマスク・ビツトの制御を受ける。このためマ
スク・レジスタ３の内容は１ステージごとにパイ
プラインの本数分、即ち８ビツトずつ読み出さ
れ、パス１７を介して各パイプラインに分配され
る。

次に第２図並びに第３図にて主記憶上の圧縮さ
れたデータとベクトル・レジスタ上の伸張された
データとの間の転送処理動作を示す。

第２図は主記憶上の圧縮されたｌ個のデータ
a₀、a₁、…、a_l-1をベクトル・レジスタ上に伸張
してロードする処理を示したものである。ロード
処理の前にはベクトル・レジスタ２のＬ個の要素
に対してＬビツトのマスク・ビツトがマスク・レ
ジスタ３に設定されている。マスク・ビツトの
内、要素が有効であることを示す“１”の数は、
主記憶１上の圧縮されたデータの要素数に等し
い。主記憶１上のデータは先頭の要素から順にマ
スク・ビツト“１”に対応するベクトル・レジス
タ２の要素位置にロードされる。マスク・ビツト
“０”に対応する要素位置にはロードしない。

第３図はベクトル・レジスタ２上の伸張された
Ｌ個のデータa₀、a₁、…、a_L-1を圧縮して主記憶
１にストアする処理を示したものである。ストア
処理の前にはベクトル・レジスタ２のＬ個の要素
に対してＬビツトのマスク・ビツトがマスク・レ
ジスタ３に設定されている。ロードとは逆に、マ
スクビツト“１”に対応するベクトル・レジスタ
２の要素位置のデータが先頭から順に主記憶１に
ストアされる。

第４図にロード・ストア・パイプライン１本の
アドレス計算回路の構成を示し、圧縮・伸張型の
ロード・ストア処理におけるアドレス計算を説明
する。本図は(3)式の多重度Ｍ＝８の場合の構成を
示したものである。この場合、処理のパイプライ
ン動作の単位である１ステージごとにデータ中の
８個の要素がロード・ストア処理される。各パイ
プラインには信号線３３によつてリクエスタ番号
と称する０〜７の値が与えられている。各パイプ
ラインはリクエスタ番号の値によつて処理すべき
要素の系列を認識し動作する。リクエスタ番号が
０のパイプラインでは、要素a₀、a₈、a₁₆、…が
順次ロード、ストア処理される。

命令解読回路２０において主記憶１上の圧縮デ
ータとベクトル・レジスタ２上の伸張データとの
間のデータ転送を指示するロード・ストア命令が
解読されると、命令解読回路２０から主記憶１上
の圧縮データをアドレス付けする情報がレジスタ
２１，２２，２４に設定される。アドレス・レジ
スタVAR２１にはデータの先頭アドレスが、イ
ンクリメント・レジスタVIR２２にはデータの間
隔値が、レングス・レジスタVLR２４にはデー
タの長さがそれぞれ設定される。データに関する
情報の設定と共に信号線３７によりデータのロー
ド・ストア処理を起動する信号が送られ、ラツチ
３９が“１”にセツトされる。ラツチ３９の出力
はメモリ・リクエストを制御するAND回路４０
を開き、ロード・ストア処理のためのメモリ・リ
クエストの送出が始まる。

マスク・レジスタVMR３からはロード・スト
ア処理に同期してパイプラインの本数分、８ビツ
トのマスク・ビツトが並列に読み出され、パス１
７を介しレジスタ１８にセツトされる。マスク・
ビツトの読み出しは、ロード・ストア処理のパイ
プライン動作の単位と同じく１ステージごとに行
われる。レジスタ１８に入つたマスク・ビツトは
次のステージにはレジスタ１９に転送される。レ
ジスタ１８，１９の出力はビツト選択回路３５，
３６に入力され、リクエスタ番号によつて定まる
ある範囲のビツトのみが抽出され、カウンタ２３
に転送される。カウンタ２３は選択されたマス
ク・ビツト中の“１”のビツトの数を計数し、計
数して得られた数から倍数発生回路２６，２７を
制御し、インクリメント・レジスタVIR２２の０
〜７倍の倍数を発生する。倍数発生回路２６では
８、４、０倍の倍数が、倍数発生回路２７では
２、１、０、−１倍の倍数がそれぞれ発生される。
両者を組み合せることによつて０〜８倍の倍数が
得られる。

ロード・ストア処理の最初のステージではデー
タの先頭アドレスがアドレス・レジスタVAR２
１からセレクタ２５を介しキヤリー・セーブ・ア
ダーCSA２９に入力される。同時にマスク・カ
ウント数に基づくインクリメント・レジスタVIR
の倍数が倍数発生回路２６，２７からキヤリー・
セーブ・アダーCSA２９に入力される。両者は
キヤリー・セーブ・アダーCSA２９とその直後
にあるパラレル・アダーPA３０によつて加算さ
れ、第１ステージで処理される要素の主記憶アド
レスとなる。第２ステージ以降では、前のステー
ジで処理した要素の主記憶アドレスがセレクタ２
５を介しキヤリー・セーブ・アダーCSA２９に
再び入力され、該ステージで処理する主記憶アド
レスを計算するために使用される。第２ステージ
以降のアドレス計算では、アドレス・レジスタ
VAR２１の内容の代りに前ステージで求めた主
記憶アドレスを用いる点のみ異なる。

第５図においてリクエスタ番号３のロード・ス
トア・パイプラインにおけるアドレス計算の一例
を示す。要素a_o-8に引き続く８個の要素に対応す
るマスク・ビツトが“10110100”、その次のステ
ージで処理される要素a_oに引き続く８個の要素に
対応するマスク・ビツトが“01011001”であると
する。リクエスタ番号３のパイプラインでは２ス
テージの間に要素a_o+3-8と要素a_o+3とについてロ
ード・ストア処理を行う。要素a_o+3の主記憶アド
レスは、要素a_o+3-8の主記憶アドレスとマスク・
ビツトVMR(i)（ｉ＝ｎ＋３−８〜ｎ＋２）とか
ら次のようにして求められる。まず、ビツト選択
回路３５によつて要素a_o+3-8から後の５個の要素
a_o+3-8、a_o+4-8、a_o+5-8、a_o+6-8、a_o+7-8に対応す
るマスク・ビツト“10100”が選択され、その内
の有効ビツト数_o-1 〓^i=n+3-8 VMR(i)＝２が得られる。
次にビツト選択回路３６によつて要素a_o+3より前
の３個の要素a_o、a_o+1、a_o+2、に対応するマス
ク・ビツト“010”が選択され、その内の有効ビ
ツト数_o+2 〓ⁱ⁼ⁿ VMR(i)＝１が得られる。カウンタ２３
によつて両者が計数されその和_o+2 〓^i=n+3-8 VMR(i)＝
３をもとに倍数３＊VIRが生成される。倍数発生
回路２６では４＊VIRが、倍数発生回路２７では
（−１）＊VIRが発生され、両者はチヤリー・セ
ーブ・アダーCSA２９とパラレル・アダーPA３
０とにおいてa_o+3-8と加算されa_o+3が得られる。

a_o+3＝a_o+3-8＋（_o-1 〓^i=n+3-8 VMR(i) ＋_o+2 〓ⁱ⁼ⁿ VMR(i)）＊VIR ＝a_o+3-8＋（２＋１）＊VIR ＝a_o+3-8＋３＊VIR ＝a_o+3-8＋４＊VIR＋（−１）＊VIR……(4) 第４図においてビツト選択回路３５は、マス
ク・カウント値を求めるためのビツト選択と共
に、該パイプラインで処理される要素に対応する
マスク・ビツトの選択も行う。リクエスタ番号か
ら処理要素に対応するマスク・ビツト位置を求
め、該マスク・ビツトを抽出し、AND回路４０
に送る。AND回路４０では、ラツチ３９からの
メモリ・リクエスト発行信号とビツト選択回路３
５からのマスク・ビツトとのANDがとられ、メ
モリ・リクエストとしてパス１３に乗せて主記憶
１に送出される。処理すべき要素に対応するマス
ク・ビツトが“１”の場合にはメモリ・リクエス
トが発行され、該当する要素が主記憶１から読み
出されたり、主記憶１に書き込まれたりする。マ
スク・ビツトが０の場合にはメモリ・リクエスト
は抑止される。メモリ・リクエスト発行の際に
は、キヤリー・セーブ・アダーCSA２９とパラ
レル・アダーPA３０とによつて計算された主記
憶アドレスがパス１３に乗せてメモリ・リクエス
トと共に主記憶１に対して送出される。

レングス・レジスタVLR２４にはロード・ス
トア処理に先き立つてデータの長さが格納されて
いる。ロード・ストア処理が１ステージ進行する
ごとにレングス・レジスタVLRの内容は減算回
路２８によつて−８される。ロード・ストア処理
の１ステージにおいて、パイプラインの本数８と
同じ個数の要素が１度に処理されるので−８す
る。すべての要素についてロード・ストア処理が
実行された時点で減算結果は０以下となる。そこ
で符号検出回路３１にて処理の終了を検出し、終
了信号３８によつてラツチ４０を“０”にリセツ
トし、AND回路４０を閉じる。AND回路４０が
閉じられたことによつて以後のメモリ・リクエス
ト送出が停止される。

本実施例によれば、主記憶上の圧縮されたデー
タとベクトル・レジスタ上の伸張されたデータと
の間のデータ転送を並列に設置され複数のロー
ド・ストア・パイプラインにより実行可能とな
る。このためデータ転送速度をパイプラインの本
数と同じだけ向上させることができる。

〔発明の効果〕

本発明によれば、要素並列の多重ロード・スト
ア・パイプラインを具備するベクトル処理装置に
おいて、主記憶上に圧縮されたデータとベクト
ル・レジスタ上の伸張されたデータとの間のデー
タ転送についても要素並列の形態で実行すること
が可能となる。したがつて通常の単純ロード・ス
トアと同様に並列に設置されたパイプライン本数
分のデータ転送速度を得ることができる。これに
よつて圧縮・伸張型のテータ・アクセスを必要と
する疎行列の行列計算が高速に処理される。

【図面の簡単な説明】

第１図は本発明の一実施例のベクトル処理装置
の全体構成図、第２図は主記憶上に圧縮されたデ
ータをベクトル・レジスタ上に伸張してロードす
る処理を示す図、第３図はベクトル・レジスタ上
の伸張されたデータを主記憶に圧縮してストアす
る処理を示す図、第４図はロード・ストア・パイ
プラインのアドレス計算回路の構成を示す図、第
５図はアドレス計算の一例を示す図である。２……ベクトル・レジスタ、３……マスク・レ
ジスタ、４……ロード・ストア・パイプライン、
２１……アドレス・レジスタ、２２……インクリ
メント・レジスタ、３５，３６……ビツト選択回
路、２３……カウンタ、２６，２７……倍数発生
回路、２９……キヤリー・セーブ・アダー、３０
……パラレル・アダー。

Claims

【特許請求の範囲】

１複数の演算器と、複数のベクトル・レジスタ
と、データの有効性を示す複数のベクトル・マス
ク・レジスタと、複数のロード・ストア・パイプ
ラインと、インターリーブされた主記憶装置とに
より構成されるベクトル処理装置において、主記
憶上の圧縮されたデータとベクトル・レジスタ上
の伸長されたデータとの間で圧縮・伸長型データ
転送を行うために、前記パイプラインにより処理
すべきデータを識別するための前記パイプライン
に対して与えられるリクエスタ番号に基づいてマ
スク・レジスタの内容を選択するビツト選択回路
と、選択されたビツト列中の有効ビツト数をカウ
ントするカウンタと、該カウンタのカウント数に
基づきデータの間隔値、すなわち、インクリメン
トの倍数を複数組発生する倍数発生回路と、前記
パイプラインにより前の処理ステージで処理した
データの主記憶アドレスと前記倍数発生回路から
の複数組のインクリメントの倍数とを同時に加算
して次ステージで処理すべきデータの主記憶アド
レスを計算してなる多入力の加算器とを備え、主
記憶アドレスを各パイプライン毎に並列に発生さ
せ、要素並列の多重パイプライン動作による前記
圧縮・伸長型データ転送を行うことを特徴とする
ベクトル処理装置。