JPS62160568A

JPS62160568A - ベクトル計算機

Info

Publication number: JPS62160568A
Application number: JP61002773A
Authority: JP
Inventors: Shunichi Torii; 俊一鳥居; Keiji Kojima; 啓二小島
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1986-01-09
Filing date: 1986-01-09
Publication date: 1987-07-16

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、ベクトル計算機に関し、特にディスク上のデ
ータブロック番号から主記憶上に読み込まれたアドレス
に変換する場合、多数のデータブロックを高速に変換す
るためのベクトル計算機に関するものである。

〔発明の背景〕

データベース管理システム（ＤＢＭＳ）のように５多量
のデータをディスク（磁気ディスク、光ディスク等）で
管理するシステムにおいては、ディスク上の領域を固定
長のデータブロック（具体的には、ページと呼ばれる）
に分割し、このデータブロックを単位に主記憶とディス
クとの転送を制御する。データブロックアドレス変換で
は、ディスク上のデータブロック番号を入力として、対
応するデータブロックを格納している主記憶エリアのア
ドレスを出力する。アドレス変換の内部処理としては、
既に読込まれているデータブロックはそのまま変換出力
に流用し、読込まれていないデータブロックのみをディ
スクより新たに読込む。そして、読込んだ主記憶エリア
のアドレスを出力する。従来のアドレス変換装置として
は、例えば。

特開昭５７−１６９９８３号公報に記載されているよう
に、先ずディスクから１デ一タブロツク分のブロック番
号を入力し、これを主記憶上の格納エリアアドレスに変
換して出力し、次にまた１つのデータブロックの番号を
入力して、これを主記憶上のアドレスに変換し出力する
というように、１ブロツクづつ逐次処理を行っていた。

従って。

変換処理に時間がかかり過ぎていた。

一方、半導体メモリの製造技術の発達により、大容量の
主記憶メモリが低価格で製造できるようになってきたの
で５デイスクと主記憶メモリとの容量の差が小さくなり
、従来のように大容量のディスクから小容量の主記憶に
対して、常に使用頻度の高いブロックを読込ませるため
、古いブロックとの入替えを頻繁に行う必要がなくなっ
てきた。

すなわち、大容量の主記憶装置を使用するＤｒ３ＭＳで
は、データブロックが既に読込まれている確率が増大し
、ディスクへの入出力時間は減小する傾向にある。しか
し、上記公報に記載された従来のアドレス変換装置を使
用した場合には、指定データブロックが読込み済みであ
るか否かの判定を行う時間が、読込み済みのデータブロ
ックの個数に比例して増加するので、処理時間を減小で
きないという問題がある。

そこで、複数のデータブロックを一括してアドレス変換
することにより、処理を高速化する方法が提案されてい
る。関係データベースは、操作性がよい等の利点を持つ
反面、実行性能が遅いという欠点を持っているが、一部
提案され、現在も検討中の方法は、ベクトル演算を基本
とするデータベースプロセッサにより高速化を図ってい
る。しかし、従来のベクトル演算方法では、読込み済み
データブロックを管理するベクトルを更新する方法が考
えられておらず、また数値計算を前提としているため、
データベース処理に適用するためには、新しい演算方法
の開発が必要である。

〔発明の目的〕本発明の目的は、このような従来の問題を改碧し、外部
記憶装置と主記憶装置間の多数のデータブロックのアド
レス変換要求と多数の読込みデータブロックに対しても
、データブロック数のオーダに比例した高速なアドレス
変換が可能なベクトル計算機を提案することにある。

〔発明の概要〕

上記目的を達成するため、本発明のベクトル計算機は、
外部記憶上のデータブロックを主記憶上の任意のエリア
に読込んだ後、ソートされた複数のデータブロック番号
を格納したベクトルを入力して、対応する読込まれた主
記憶エリアの各アドレスの一部ベクトルに変換して出力
するベクトル計算機において、ソートされた２つのベク
トルの集合差を求める手段と、ソートされた２つのベク
トルの集合和を求める手段と、ソートされた２つのベク
トルの集合積を求める手段と、主記憶に読込み済みのデ
ータブロックに対しブロック番号順にソートされたエリ
ア管理ベクトル格納手段とを有し、上記エリア管理ベク
トルと入力データブロック番号ベクトルとの集合差を求
めて、主記憶に新たに読込むべきデータブロック番号ベ
クトルを求め、外部記憶より対応するデータブロックを
読込み、上記新しく読込んだデータブロック番号ベクト
ルと上記エリア管理ベクトルとの集合和を求めて、上記
エリア管理ベクトルの更新を行い、更新されたエリア管
理ベクトルと上記入力データブロック順序番号の集合積
を求めて、アドレス変換出力ベクトルを発生することに
特徴がある。

〔発明の実施例〕

以下、本発明の実施例を１図面により詳細に説明する。

先ず最初に、従来のベクトル演算と本発明が対象とする
ベクトル集合演算との相違を説明した後、次に本発明の
アドレス変換の基本手順を説明する。

従来のベクトル演算では、演算の対象となるベクトル要
素番号を順次規則正しく更新しながら、対応する要素間
の演算を行い、所定の要素番号の処理を終了したときに
ベクトル演算が終了するという形式を原則としている。

例えば、それぞれｎ個の要素を有する２つのベクトルを
対象として、第１要素間の演算の次には第２要素間の演
算を行い、以下順番に第ｉ要素間の演算を行って、第ｎ
要素間の演算が終ったところで、このベクトル演算が終
了する。この型のべりｌ・ル演算は、マトリクス演算（
例えば、逆行列計算）のような数１［ｉＩ計算には広く
適用できることが知られており、それに基づくベクトル
計算機が１例えば、ＣＲＡＹ社のＣＲＡＹ−１計算機や
、日立製作所の内蔵アレイプロセッサ等として製品化さ
れている。また、この製品の技術を説明した文献として
は、前者については米国特許第４１２８８８０号明細書
があり、後者については、特公昭５８　５２２６５号公
報がある。しかし、数値計算とは異なる種類の演算に対
しては、前記の型のベクトル演算はあまり有効ではない
。例えば、リレーショナルデータベース管理システム（
ＲＤＢＭＳ）の処理は、一群のデータ（例えば、テーブ
ル）を単位として一定の演算を行う場合が多いので、ベ
クトル計算機を利用して処理の高速化を図りたいのであ
るが、前記の型のベクトル演算機能のみでは、充分な高
速化を達成できない。何故ならば、ベクトル演算機では
。

全演算の９０％以上にベクトル演算が適用されなければ
１期待する速度の向上が実現されないと考えられる。例
えば、ＲＤｒ３ＭＳの処理では、レコードを格納するデ
ータブロック番号から該当ブロックが読込まれている主
記憶アドレスに変換する処理が頻繁に行われ、かつこの
アドレス変換を効率よく前記の型のベクトル演算を用い
て実行するアルゴリズムが未だに知られていないからで
ある。

次に、このＲＤＢにおけるアドレス変換を例にして、従
来の型のベクトル演算の問題点を詳述する。ＲＤＢのレ
コードは、固定長（４ＫＢ）のデータブロックに複数個
が格納されており、ディスクからはこのデータブロック
を単位に読込まれ、主記憶上の適当な空き領域に格納さ
れる。以後、ＲＤＢＭＳの検索等のレコード操作は、全
てこの主記憶上で行われる。ここで、ＲＤＢの全データ
容量は主記憶の容量より大きい場合が多いので、主記憶
の領域には、一部のデータブロックのみを動的に割当て
ることが必要になる。従って、データブロック番号から
対応するブロックが格納されている主記憶領域のアドレ
スを求めるには、上記動的な割当に関する情報を利用し
なければならない。

１個のレコードに関し、そのレコードを含むデータブロ
ックが格納される主起ｔα領域のアドレスを求める方法
として、従来より、特開昭５７−１６９９８３号公報に
記載されている方法が使用されている。しかし、この方
法は、１個のアドレス変換のみを対象としており、ベク
トル演算の前提である多数個のレコードを一括処理する
方法ではない。また、処理時間も、アドレス変換要求の
データブロック数をＸ、主記憶上のデータブロック数を
ｙとすれば、ｘＸｙに比例した時間を必要とする。

第２図は１本発明による新しいベクトル方式のアドレス
変換手順を説明する図である。茅２図におけるベクトル
Ｌ、２，３．３’　、４．５は、それぞれ１個の要素が
前半と後半のご一つのフィールドから構成された新しい
形式のベクトルであり、以下、デュアルベタ１−ルと呼
ぶ。このデュアルベタ１−ルは、主記憶装置に格納され
る。デュアルベクトル１は、アドレス変換の入力となる
もので、各要素の後半には、アドレス変換したいデータ
ブロックの番号ｉが上昇順に格納されている。前半の部
分には、有意な内容が格納されていないので。

１１　　Ｉ＋で示している。以下、デュアルベクトルｌ
を、要求ベクトルと呼ぶ。デュアルベクトル４は、アド
レス変換の出力となるもので、各要素の後半は、デュア
ルベクトルｌと同一内容であるが、前半には対応する各
主記憶領域のアドレス（第２図では、ｍ　ｉ　）が格納
されている。デュアルベタ１−ル２゜５には、主記憶上
に読込まれている全データブロックの番号ｊと対応する
主記憶アドレス（茅２図では、ｍｊ）が各要素の後半と
前半に格納されている。各要素は、データブロックの上
昇順に並んでいる。このデュアルベクトルを、以下、管
理ベクトルと呼ぶ。

アドレス変換は、以下に述べる４つのステップに分けて
実行される。

アドレス変換の第１ステツプでは、後述するデュアルベ
クトル要素集合間の差（以下、ディファレンスＤ　１ｆ
ｆｅｒｅｎｃｅと呼ぶ）の演算６により、主記憶上に読
込まれていないデータブロックの番号を求めるａ　Ｄｘ
ｆｆｅｒｅｎｃｅ°演算は、要求ベクトル１と管理ベク
トル２を入力し、両ベクトルの各要素の後半部を比較し
、右側の管理ベクトルにはないデータブロック番号を持
つ左側ベクトル要素を。

デュアルベクトル３に出力する。第２図の例では、番号
１，５．７のデータブロックは、右側の管理ベクトルに
存在するので、データブロック番号２゜８を含む要素だ
けが出力されている。

第２ステツプでは、読込まれていないデータブロックの
ために、主記憶中の空領域を割当て（ステップ１０１）
、そのアドレスをデュアルベクトル３′の前半に登録す
る。同時に、ディスク１０３から必要なデータブロック
を読込み（ステップ１０２）、先に割当てた空領域に格
納する。デュを追加ベクトルと呼ぶ。

第３ステツプでは、第２ステツプで新しく読込んだデー
タブロック番号を、後述するベクトル要素集合間の和（
以下、ユニオンＵ　ｎ１ｏｎと呼ぶ）の演算８により、
管理ベタ１−ルに追加する。Ｕｎｉｏｎ演算は、追加ベ
クトル３′と管理ベクトル２を入力とし１両者の集合和
となる新しい管理ベクトル５を生成する。管理ベクトル
もデータブロック番号が上昇順になる。

第４ステツプでは、第３のステップで作成した新しい管
理ベクトルを用いて、要求ベクトルｌで指定された全て
のデータブロックについて、アドレス変換し、その結果
をデュアルベクトル４に格納する。このために、ベクト
ル要素集合間の積（以下、ジョインＪ　ｏｉｎと呼ぶ）
の演算７を使用する。Ｊ　ｏｉｎ演算では、左側入力の
新しい管理ベクトルの各要素の後半のデータブロック番
号を、右側入力の要求ベクトルの各要素の後半のデータ
ブロック番号と比較し、一致するものが存在する場合に
のみ、左側の管理ベクトル要素を出力する。

以上に述べたＤ　１ｆｆｅｒｅｎｃｅ　、　Ｕ　ｎ１ｏ
ｎ　＋　Ｊ　ｏｉｎの各演算は、それぞれ入力が上昇順
に並んでいることを利用し、入カベクトルと管理ベタ１
−ルの要素数の和に比例した時間で実行することができ
る。つまり、各ベクトル要素を先頭から順次読出し、要
素の後半部相互を比較し、その結果により出力内容の選
択、出力の要否、左ベクトルの次の読出しの要否、右ベ
クトルの次の読出しの要否を判断するマージの手順を繰
り返すことにより、実行できるからである。

この新しいベクトル型のアドレス変換方法は、それ自体
が効率のよいアルゴリズムであるが、残念ながら従来の
型のベクトル演算方式を適用して、さらに高速化するこ
とはできない。例えば、Ｄｉｆｆｅｒｅｎｃｅ演算では
、３つのベクトルの各要素への参照は、比較結果により
変化し、一様ではない。

つまり、各演算サイクルにおいて、各ベクトルの何番目
の要素を参照、または格納しているかは、過去の要素間
の比較結果により、３つのベクトルごとに異なっている
。このため、同一番目の要素間の演算しな許されない従
来型のベクトル演算方式の計算機では、Ｄ　１ｆｆｅｒ
ｅｎｃｅ演算を高速に実行することができない。Ｕ　ｎ
１ｏｎ　、　Ｊ　ｏｉｎの演算についても、同じように
、従来の型のベクトル演算方式の計算機では、高速に行
うことができない。

第１図は、本発明の一実施例を示すベクトル計算機のブ
ロック図である。

本実施例においては、マージ型のベクトル演算で、比較
の結果を直接各ベク１−ルオペランドのアドレスレジス
タ更新に反映することにより、判定処理のピッチのパイ
プライン化を実現し、アドレス変換処理における読込ま
れていないデータブロックを抽出するベタ１−ル集合差
演算（Ｄ　１ｆｆｅｒｅｎｃｅ）、読込み管理ベクトル
に新規に読込んだデータブロックの管理ベクトルを追加
するベクトル集合和演算（Ｕｎｉｏｎ）、要求データブ
ロックの対応するエリアのアドレスをｆｆ！するベクト
ル集合積演算（Ｊｏｉｎ）の全てを、パイプライン化さ
れたバク１−ル演算装置により高速化する。

第１図において、１０は主記憶装置、１１は命令制御回
路、１８は第２オペランドデータレジスタ、１９は第３
オペランドデータレジスタ、１７は選択回路、６０は比
較回路、６１は判定回路５３０ａは第２オペランド制御
回路、３０ｂは第３オペランド制御回路、３０ｃは第１
オペランド制御回路、１，２．３は第２図に示すデュア
ルベクトルである。主記憶装置１０には、デュアルベク
トル１，２．３が格納されるが、以下、これらのデュア
ルベクトル１，２．３をそれぞれ第２オペランド、第３
オペランド、および第１オペランドと呼ぶ。一般に、第
２、第３オペランドが入力であり、第１オペランドがＤ
　１ｆｆａｒｅｎｃｅ演算の出力である。

命令制御回路１１は、命令語レジスタ５０を含み、ベク
トル命令の起動と終了を制御する。第２オペランド制御
回路３０ａ、第３オペランド制御回路３０ｂ、第１オペ
ランド制御回路３０ｃは、それぞれオペランドの各要素
アドレスの生成と終了判定を行う。３つの制御回路３０
ａ、３０ｂ。

３０ｃは、第３図で後述するように、同一の回路構成に
することができる。。

第２オペランドデータレジスタ１８、第３オペランドデ
ータレジスタ１９は、主記憶装置１０から順次読出され
るオペランド要素を１サイクル以上保持するために使用
される。比較器６０は、第２オペランドデータレジスタ
１８と第３オペランドデータレジスタ１９の後半部分を
比較し、その出力は命令制御回路１１からの演算の種類
を示す信号１３とともに、判定回路６１に入力される。

判定回路６１は、第２オペランドデータレジスタ１８と
第３オペランドデータレジスター９のいずれか一方向の
内容を選択し、主記憶に転送することを選択回路１７に
指示する信号２８と、各オペランドに対してアドレスの
更新と次オペランドの読出し、または選択器出力の格納
を指示する３本の信号２３ａ、２３ｂ、２３ｃを生成す
る。ゲート１５，１６は、ＯＲゲートである。これらの
ＯＲゲート１５．１６には、命令制御回路１１からの信
号と判定回路６１からの信号とを入力して、〉、゛第２オペランドデータレジスター８と第３オペラソ・″ノドデータレジスター９に対し、次オペランドの読
出しアドレスの更新信号を出力する。このようにして、
デュアルベクトル１とデュアルベクトル２のうち一致し
ないオペランド要素２．８を選択回路１７で選択して、
主記憶装置１０に出力する。

これにより、デュアルベクトル３が生成される。

なお、上述の説明は、Ｄ　１ｆｆｅｒｅｎｃｅ演算のみ
であるが、Ｕｎｉｏｎ演算とＪ　ｏｉｎ演算についても
同じようにして処理される。

第３図は、第１図における３個のオペランド制御回路を
示す詳細ブロック図である。３個のオペランド制御回路
３０ａ、３０ｈ、３０ｅは、同一構造であり、加算器３
１，３２、アドレスレジスタ３５、オペランドカウンタ
３４、オール０検出回路３３、およびＯＲゲート３６を
備えている。

線３６には、第２、第３オペランド制御回路３３ａ、３
０ｂでは命令制御回路１１からの信号、第１オペランド
制御回路３０ｃではＩＩ　Ｏｊｌ入力が、それぞれ加え
られ、また９２１，２２には主記憶装置１０へのアドレ
スおよび命令制御回路１１への終了信号が、それぞれ出
力される。

アドレスレジスタ３５は、各ベクトルオペランド要素ア
ドレスを格納するもので、その内容はアドレス線２１に
より主記憶袋［１０に送られる。

本実施例では、１ベクトル要素は、前半と後半の合計２
語で構成されており、次の要素のアドレス計算のために
、＋２を片側入力とする加算器３１が使用される。アド
レスレジスタの更新は、ＯＲゲート３８の機能により起
動トリガ信号３６またはアドレス更新信号２３が１′″
の時、加算が実行され、線２１を介して主記憶装置１０
に送出される。

オペランドカウンタ３４は、残りベクトルオペランド要
素数を格納しており、零検出器３３は残り要素数が１０
”になったサイクルに、終了信号２２を命令制御回路１
１に対し送出する。−１を片側入力とする加算器３２は
、残り要素数を１つづつ減算するために使用され、アド
レス更新信号２３が１°′の時、オペランドカウンタ３
４が更新さ木る。

゛　第４図は、第１図における判定回路の真理値を示す
図である。真理値テーブル４０の左側は入力条件、右側
は出力値である。１行は、１つの入力条件と対応する出
力値を示す、テーブルの列４１〜４４が入力条件であり
１列４５〜４８が出力である。

列４１は、第１図における命令制御回路１１より信号、
ｌＸ１３を経由して入力される演算命令の種類を示す信
号であり、本実施例ではｄｉｆｆｅｒｅｎｃｅ、ｕｎｉ
ｏｎ、ｊｏｉｎの３種がある。列４２，４３．４４は、
比較回路６０より入力される信号であり、第２オペラン
ドデータレジスタ（ＯＦ２）と第３オペランドデータレ
ジスタ（ＯＦ２）の後半部分の比較結果、すなわち、前
者が後者より″小Ｉｔ、１１等ｕ、１１大″とにそれぞ
れ対応している。例外として、片側のベクトルオペラン
ド要素が尺きた時は、尽きた側を゛大きい″と見なす。

ベクトルオペランド要素が尽きたか否かは、第１図には
示されていないが、各−オペランド制御回路３０ａ、３
０ｂ中のオペラン・°、λドカウンタの零検出回路３３
の出力信号２２ａ。

２２ｂから判定することができる。例えば、列４２がｕ
　１″′のときには、第２オペランドデータレジスタ（
ＯＦ２）の後半部の内容が第３オペランドデータレジス
タ（ＯＦ２）より小さいか、または第３オペランドデー
タレジスタ（ＯＦ３）側のベクトル要素が尽きている条
件が成立していることを示す。

同じようにして、列４３９列４４がＩＩ　Ｉ　１１のと
きには、第２オペランドデータレジスタ（ＯＦ２）と第
３オペランドデータレジスタ（ＯＦ２）が等しいこと、
および第２オペランドデータレジスタ（ＯＦ２）が第３
オペランドデータレジスタ（ＯＦ２）より大きいか、ま
たは第２オペランドデータレジスタ（ＯＦ２）が尽きて
いる条件が成立していることを示す。

列４５は、第１図の選択回路１７を制御するための制御
線２８の出力値を示している。ここで、１１　　＃＃印
は、この入力条件では、選択回路１７の出力を主記憶装
置１ｉ１０に転送、格納しないことを示す。ＯＦ２側、
ＯＦ２側は、それぞれ第２オペランドデータレジスタ（
ＯＦ２）側を、または第３オペランドデータレジスタ（
ＯＦ３）側を選択するように指示する信号を出力するこ
とを意味している。

列４６，４７．４８は、各オペランドごとの要素アドレ
スの更新と、主記憶に対するオペランドの読出しまたは
選択器出力の格納を指示する３本の信号線２３ａ、２３
ｂ、２３ｃの出力値を示す。

例えば、列４６の１′″は、第２オペランドに関して、
第３図のアドレスレジスタ３５の更新、オぺランドカウ
ンタ３４の更新、および第１図の第２オペランドデータ
レジスタ（ＯＦ２）の更新を指示することを示す。

第５図は、第１図における動作タイムチャートである。

第５図、第１図を参照して、第２図のｄｉｆｆｅｒｅｎ
ｃｅ演算６を実行するｄｉｆｆｅｒｅｎｃｅ命令を例と
した動作を説明する。

主記憶ｌＯ中には、デュアルベクトルｌ、２゜３の他に
明示されていないが、命令語も格納されている。命令語
には、少なくともｄｉｆｆｅｒｅｎｃｅ　、　ｕｎｉＯ
ｎ＊ｊｏｉｎの３種類があり、命令制御回路１１の制：
制御により主記憶ｌＯから読出され・データ線１４゛′
を経由して命令語レジスタ５０に格納される。

命令語レジスタ５０中の命令語は、４つのフィールドか
ら構成されている。最左端のＣフィールドは、命令の演
算の種類（例えば、ｄｉｆｆｅｒｅｎｃｅ命令）を示す
ために使用され、その内容は信号線１３を経由して判定
回路６１に転送される。その後部のＯＰＩ、ＯＦ２．Ｏ
Ｆ２の３フイールドは、それぞれ第１オペランド、第２
オペランド、第３オペランドのベクトルの主記憶上の先
頭要素アドレスと要素数をペアで示すために使用される
。第１図に示されていないが、命令制御回路１１は。

その内容を主記憶からの各オペランドベクトル要素の読
出しまたは格納に先立って、第３図に示す各オペランド
制御回路３０ａ、３０ｂ、３０ｃ中のアドレスレジスタ
３５とオペランドカウンタ３４に初期設定し、主記憶に
対して第１番目の要素の読出しを指示する。

第１図のベクトル計算機は、ベクトル演算に関して、２
ステージからなる１サイクルピツチのパイプラインにな
っている。第１のステージは、アドレスレジスタ３５ａ
または３５ｂの指定に基づいて主記憶ｌＯよりデュアル
ベクトル１，２の各要素を読出し、第２オペランドデー
タレジスタ（ＯＦ２）Ｉｇまたは第３オペランドデータ
レジスタ（ＯＦ２）１９に転送するまでの処理である。

第２のステージは、第２オペランドデータレジスタ（Ｏ
Ｆ２）１８と第３オペランドデータレジスタ（ＯＦ２）
１９の内容を比較、判定し、判定結果に基づいて、いず
れか片方を選択し、主記憶ＩＯのデュアルベクトル３に
格納するまでである。各レジスタは、サイクルの開始時
点に同期して更新され、主記憶１０もサイクルに同期し
て読出され。

更新を１サイクルで実行する。

第５図においては、サイクルごとに主要なレジスタの内
容の変化、および判定回路６１の第４図の対応する判定
項目番号を示している。なお、第１図等には、図示され
ていないが、各レジスタは全ての１サイクルピツチの基
本クロックに同期してデータの格納を行う。

τ、Ｘ＼８命令制御回路１１は、前述のアドレスレジス
タ］３５ａ、３５ｂ、３５ｃ、およびオペランドカウン
タ３４ａ、３４ｂ、３４ｃの初期設定に引続いて、第１
サイクルとして１サイクルの起動１−リガ信号を信号線
１２に出力すると、次の第２サイクルの開始時点では、
第２オペランドデータレジスタ（ＯＦ２）１８および第
３オペランドデータレジスタ（ＯＦ２）１９には、デー
タ線２０ａおよび２０ｂ上に主記憶１０から転送されて
いる先頭要素の内容、すなわち（−，１）と（ｍｔ＋１
）が格納される。ここで、（ａ、ｂ）は要素の内容の前
半がａ。

後半がｂであることを示す。同時に、第３図のアドレス
レジスタ３５ａ、３５ｂには２番目の要素アドレスが格
納され、第２番目の要素の読出しを指示し、オペランド
カウンタ３４ａ、３４ｂは、それぞれ“５″とＩＩ　４
１＃のままである。

第２サイクルでは、第２オペランドデータレジスタ（Ｏ
Ｆ２）１８と第３オペランドデータレジスタ（ＯＦ３）
の後半部は、ともにＩＩ　１１１であるため、−６１°
”“ｆ４１１ｉ＠（７）４８”′。”９１”１を立した
ことを検出し、信号Ｂ　２３　ａのみをＩＩ　１　ｙＢ
と九で１次の第３サイクル開始時における第２オペラン
ド側のみの更新を指示する。また、主記憶１０への格納
は指示しない。

次の第３サイクルの先頭では、前述の信号線２３ａの指
示により第２オペランドに関するレジスタのみが更新さ
れる。すなわち、ＯＲゲート１５を経由した制御信号に
より第２オペランドデータレジスタ（ＯＦ２）１８は第
２要素の内容である（−，２）に更新され、第３図のア
ドレスレジスタ３５ａの内容は第３要素を読出すために
第３要素アドレスに更新され、オペランドカウンタ３４
ａも１り４″に減少される・第３サイクルでは、第４図の項番＃３の条件が成立する
ので１判定回路６１は信号線２３ｂのみを１”として、
今度は第３オペランド側のみの更新を指示する。このサ
イクルでも、主記憶１０への格納は指示しない。

次の第４サイクルの先頭では、信号線２３ｂの、４指示
により、第３オペランドに関するレジスタの・）丑みが更新される。すなわち、ＯＲゲート１６を経；′ 由した制御信号により、第３オペランドデータレジスタ
（ＯＦ３）１９は第２サイクルから引続いて主記憶１０
より読出されている第２要素の内容である（ｍａ＊３）
に更新され、第３図のアドレスレジスタ３５ｂの内容は
、第３要素アドレスに更新され、オペランドカウンタ３
４ｂは、９３″に減少される。

第４サイクルでは、（−，２）と（ｍ３＋３）の後半部
を比較するので、第４図の項番＃１の条件が成立する。

従って、選択器１７は第２オペランドデータレジスタ（
ＯＦ２）１８の内容を選択し、主記憶１０に書込みデー
タとして転送する。そして、主記憶ｌＯ中のデュアルベ
クトル３の第１要素に（−，２）が書込まれる。また、
第１オペランドおよび第２オペランドに関係するレジス
タの更新が信号線２３ｃ、２３ａを経由して指示される
。

以下、第５サイクルでは、（−，５）と（ｍ３゜３）を
比較し、第４図の項番＃３が成立するので、較し、第４
図の項番＃２が成立し、第２オペランド関係のレジスタ
の更新が指示される。

第７サイクルでは、（−，７）と（ｍｓ＋５）を比較し
、第４図の項番＃３が成立し、第３オペランド関係のレ
ジスタの更新が指示される。

第８サイクルでは、（−，７）と（ｍ７１７）を比較し
、第４図の項番＃２が成立し、第２オペランド関係のレ
ジスタ更新が指示される。

第９サイクルでは、（−，８）と（ｍ７　＋　７）を比
較し、項番＃３が成立し、第３オペランド関係のレジス
タ更新が指示される。

第１０サイクルでは、第２オペランドデータレジスタ（
ＯＦ２）１８の内容は（−，８）であるが、第３オペラ
ンドデータレジスタ（ＯＦ２）１９の側は第３オペラン
ドの要素が尽きた（終了した）状態となっている。従っ
て、第４図の項番＃１が成立し、第２オペランドデータ
レジスタ（ＯＦ２）１８の内容が主記憶１０中のデュア
ルベクトル３の第゛・２要素として書込まれる。

゛゛第１１サイクルでは、信号線２２ａを経由して。

゛命令制御回路１１に第２オペランドベクトルの全ての
要素が読出されたこと、すなわち尽きたことが報告され
、命令の処理が完了する。

このように、ｄ　１ｆｆｅｒｅｎｃｅ命令は、大兄、第
２オペランドと第３オペランドの要素数の和に等してサ
イクル数で実行することが可能である。これは、■サイ
クルピッチの比較動作をパイプラインにより休みなく実
行しているためである。

また、ｕ　ｎ１ｏｎ命令、　ｊｏｉｎ命令についても、
同じように第４図の真理値表に基づいて実行される。

ただし、命令の終了条件が多少異なる。ｄ　１ｆｆｅｒ
ｅｎｃ６命令の終了条件は、信号線２２ａが１″または
信号線２２ｃがＩＩ　１　′１、すなわち、゛１第２オ
ペランドが終了″°、またはパ第１オペランドが満杯″
である。

ｕｎｉｏｎ命令の終了条件は、信号Ｒ２２ａと２２ｂが
、ともに１１”または信号線２２ｃが１１１１１、すな
わち、″第１オペランドが満杯″である。

゛Ｈｊｏｉｎ命令の終了条件は、信号線２２ａと２’２
ｂｇの少なくとも一方がビ、または信号！ｆ２２　ｃが
１″′、すなわち“第２と第３オペランドの少なくとも
一方が終了′″、または′第】オペランドが満杯″であ
る。

ｕｎｉｏｎ命令、ｊｏｉｎ命令の処理時間も、ｄ　１ｆ
ｆｅｒｅｒｌｃｅ命令と同じように、大兄、第２オペラ
ンドと第３オペランドの要素数の和に等しいサイクル数
になる。

なお、実施例では、デュアルベクトルは主記憶装置１０
中に格納されているが、別の記憶装置、例えばベクトル
レジスタに格納されていてもよい。

第２図に示すデュアルベクトルの例では、データブロッ
ク番号に同一値を持つ要素が複数ある場合、すなわち１
重複する場合を含んでいない。しかし、以上に示した実
施例では、ｊｏｉｎ命令において、左側ベクトル（第２
オペランドベクトル）にｎ個の条件に合う重複する要素
があった場合にも、正しくｎ個の重複した要素を出力す
ることができ二左右両ベクトルに重複する要素があって
もよい。

本実施例においては、前述のように、ｄ　１ｆｆｅｒｅ
ｎｃｅ、　ｕｎｉｏｎ、　ｊｏｉｎの各演算は、入力と
なる要素当り約１サイクルの演算時間しか要しない。こ
れを通常の非ベクトル命令（スカラ命令）を用いて実行
すると、各オペランドの読出し、比較判定、オペランド
アドレスの更新、終了条件判定等を要素ごとに少なくと
も５命令、５サイクル以上を必要とする。従って、本実
施例では、５倍以上の高速化が可能であり、ｄ　１ｆｆ
ｅｒｅｎｃｅ、ｕｎｉｏｎ、　ｊｏｉｎのオペランドご
とに要素番号の異なるベクトル要素間の演算に適用でき
る。また、第２図において、ｄｉｆｆｅｒｅｎｃｅ演算
の出力要素数が少ない場合には、アドレス変換の所要時
間は、入力となるアドレス変換したいデータブロック数
をＸ、主記憶１０上に格納されているデータブロック数
をｙとすると、（ｘ＋ｙ）＊２サイクルで実行できる。

それに対して、前述の特開昭５７−１６９９８３号公報
に記載されているような従来の１要素ごとにアドレス変
換を行う方法では、前述のように、（ｘ＊ｙ）に比例し
た処理時間を要している。

（′、アドレス変換のためだけに、データブロック番゛
１、５′ ム゛号順にソートする必要がある場合にも、ソート処理
にはｘｆｆｏｇｘに比例した実行時間で完了するアルゴ
リズム例えばマージソート法等が知られている。本実施
例に示したｕｎｉｏｎ命令は、マージソート法における
マージ処理にそのまま適用できる。

本実施例では、第１図に示した１個のベクトル演算装置
を、命令語の指示により、集合和（ｕｎｉ。

ｎ）、集合差（ｔｉ　１ｆｆｅｒｅｎｃｅ）、集合積（
ｊｏｉｎ）のいずれかを実行するように切換える場合を
示したが。

それぞれ専用のベクトル演算装置を用意し、並列に動作
させれば、さらに高速化できることは勿論である。

〔発明の効果〕

以上説明したように、本発明によれば、■サイクルピッ
チのパイプラインによるマージ手順に基づくベクトル集
合演算が実現できるので、多数のデータブロックアドレ
ス変換要求と、多数の読込みデータブロックに対しても
、データブロック数のオーダに比例した高速なアドレス
変換が可能にｔ＋；’＋。

−７−°なる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すベクトル計算機のブロ
ック図、第２図は本発明の基本原理を示すベクトル方式
のアドレス変換の手順説明図、第３図は第１図における
オペランド制御回路の構成図、第４図は第１図における
判定回路の真理値テーブルの図、第５図は第１図におけ
る動作タイムチャートである。１０：主記憶装置、１１：命令制御回路、１７：選択回
路、１８：第２オペランドデータレジスタ、１９：第３
オペランドデータレジスタ、３０ａ：第２オペランド制
御回路、３０ｂ＝第３オペランド制御回路、３０ｃ：第
１オペランド制御回路、３１．３２：加算器、３４：オ
ペランドベクトル要素カウンタ、３５：オペランドベク
トル要素のアドレスレジスタ、６０：比較回路、６１：
判定回路。第　　　　　３　　　　　図

Claims

【特許請求の範囲】

（１）外部記憶上のデータブロックを主記憶上の任意の
エリアに読込んだ後、ソートされた複数のデータブロッ
ク番号を格納したベクトルを入力して、対応する読込ま
れた主記憶エリアの各アドレスの一覧ベクトルに変換し
て出力するベクトル計算機において、ソートされた２つ
のベクトルの集合差を求める手段と、ソートされた２つ
のベクトルの集合和を求める手段と、ソートされた２つ
のベクトルの集合和を求める手段と、主記憶に読込み済
みのデータブロックに対しブロック番号順にソートされ
たエリア管理ベクトル格納手段とを有し、上記エリア管
理ベクトルと入力データブロック番号ベクトルとの集合
差を求めて、主記憶に新たに読込むべきデータブロック
番号ベクトルを求め、外部記憶より対応するデータブロ
ックを読込み、上記新しく読込んだデータブロック番号
ベクトルと上記エリア管理ベクトルとの集合和を求めて
、上記エリア管理ベクトルの更新を行い、更新されたエ
リア管理ベクトルと上記入力データブロック順序番号の
集合積を求めて、アドレス変換出力ベクトルを発生する
ことを特徴とするベクトル計算機。
（２）外部記憶上のデータブロックを主記憶上の任意の
エリアに読込んだ後、ソートされた複数のデータブロッ
ク番号を格納したベクトルを入力して、対応する読込ま
れた主記憶エリアの各アドレスの一覧ベクトルに変換し
て出力するベクトル計算機において、ソートされた２つ
のベクトルの集合差を求める手段と、ソートされた２つ
のベクトルの集合和を求める手段と、ソートされた２つ
のベクトルの集合積を求める手段を共通のベクトル演算
装置で構成し、該ベクトル演算装置は各ベクトルオペラ
ンドごとの要素の読出し、または書込みアドレスを指定
するアドレスレジスタと、読出された２つのオペランド
要素の全部ないし一部を入力とする比較器と、該比較器
の出力に応じて上記読出された２つのオペランド要素の
一方を演算削果として選択することを指示し、各オペラ
ンドごとに上記アドレスレジスタの更新を別個に指示す
る判定回路と、該判定回路の指示により２つのベクトル
の集合差、集合和、あるいは集合積のいずれかを主記憶
にベクトルとして書込む手段とを有することを特徴とす
るベクトル計算機。
（３）上記判定回路は、上記比較器の出力に応じて、各
オペランドアドレスの更新を指示し、第２オペランドが
小さい場合に、第２オペランド要素の内容を演算結果と
して選択することを特徴とする特許請求の範囲第２項記
載のベクトル計算機。