JPS60108973A - 配列要素の最小値および最小要素の要素番号を求める方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 発明の属する技術分野 本発明は情報処理システムの主記憶装置に記憶された配
列データの配列要素の最小値および最小要素の要素番号
をめる方法に関する。

従来技術 従来、科学技術計算においては配列データを扱う場合が
非常に多い。配列データに対する演算はしばしばそれぞ
れの要素に対する同一の演算のくり返えしとなる。従来
の情報処理システムにおいてはこのくシ返えしを分岐命
令を用いて特定の命令シニケンスをループさせることに
よシ実現しているりしかしこの方法による演算ではイン
デックスレジスタの確定待ち等による遅れがｓｂ、分岐
命令などの余分な命令が必要であるだめ、実行時間が速
くならないという欠点がある。この欠点を無くすための
一方法として配列データを専門に扱う命令、いわゆるベ
クトル命令が使用されることがある。このベクトル命令
は１つの配列に対する演算を１命令で行い、しかもルー
プ制御用の分岐命令やインデックスレジスタの確定待ち
もｋいため、高速に演算を行うことが可能である。配列
データに対する演算のうちで配列データの要素の最小値
または最小要素の要素番号をめるような演算もよく使用
される。たとえば［２つの同じ要素数を持った配列Ａと
Ｂにおいて、配列Ａの最小値を持った要素を対応する配
列Ｂの要素と入れかえる」という問題を実行する場合に
は最小要素の要素番号をめることが必要である。また配
列要素の最小値そのものが必要な場合もある。しかし従
来のベクトル命令では配列要素の最小値と最小要素の要
素番号を同時にめることができなかったため下記のよう
な欠点がある。すなわち、最小値のみをめる命令ては前
述の「要素の入れかえ」という動作を行うことができな
い。まだ最大要素の要素番号のみをめる命令では最小値
そのものはまらないため、最小値そのものか必要な場合
にはめられた要素番号をもとにして主記憶装置から対応
する要素を読み出す必要がある。

発明の目的 本発明の目的は上記欠点を解決するため、１命令で配列
要素の最小値および最小要素の要素番号をめる方法を提
供することにある。

発明の構成 本発明による配列要素の最小値および最小要素の要素番
号をめる方法は、演算のＰｊｉ類を指定するオペレージ
百ンコードフイールドと配列の先頭要素のアドレスを指
定するアドレス指定フィールドと要素間の距離を指定す
る要素間距離指定フィールドと演算を行う要素数ｎを指
定する要素数指定フィールドとを有する命令語に従って
主記憶装置から配列要素を読み出し、読み出された配列
要素の１番目（ｉ二１１２＋ｎ）までの要素のうちの最
小値を第１の保持手段に格納し、最小値を有する要素の
要素番号を第２の保持手段に格納しておき、前記第１の
保持手段の内容と（ｉ＋１　）番目の要素を比較しくｉ
＋１）番目の要素の方が小さい値を持つ場合にはその値
を前記第１の保持手段に格納するとともに（ｉ＋１）番
目の要素の要素番号を前記第２の保持手段に格納し、ｎ
番目の要素までの比較が終了した時点で前記第１の保持
手段の内容を第１のレジスタに格納し、さらに前記第２
の保持手段の内容を第２のレジスタに格納する手順から
成る。

次に本発明の一実施例について図面を参照して説明する
。第１図を参照すると・本発明の方法を具体化して実施
した情報処理装置は、主記憶装置１、メモリバッファユ
ニット２．セレクタ３．レジスタ４および５．比較回路
６．制御ユニット７゜レジスタ８および９．アンドゲー
ト１０．レジスタ１１および１２．およびセレクタ１３
から構成されている。前記主記憶装置１にはプログラム
およびデータが格納されている。前記主記憶装置１には
信号＃１０１を介してデータが省き込まれるとと本に信
号線１０２を介してその内容が読み出される。前記メモ
リバッファユニット２は前記主記憶装置ｌに対す読み出
しアクセスおよび書き込みアクセスを行うユニットであ
る。前記主記憶装置１から読み出されたデータは前記メ
モリバッフ丁−ユニット２．信号線１０３．および前記
セレクタ３を介してレジスタ４に転送される＃１か、信
号８１０３を介してレジスタ５に直接転送される〇前記
比較回路６Ｉ／ｉ、前記レジスタ４の内容と、前記レジ
スタ５の内容とを比較し、その結果を信号線１０８に出
力する。すなわち前記レジスタ４に格納されている値よ
シも前記レジスタ５に格納されている値の方が小さい場
合に信号線１０８は「１」となる。前記制御ユニット７
は本発、明による方法によシ第１図の回路を制御するだ
めのユニットである。第４図を参照すると、前記制御ユ
ニット７は命令先取シ制御回路７０１．命令先取シバッ
７丁７０２．第１命令レジスタ７０３１第２命令レジス
タ７０４．インデックスレジスタファイル７０５　、セ
レクタ７０６および７０７．実効アドレスアダー７０８
．実効アドレスレジスタ７０９゜ベースアドレスレジス
タ７１０．ベースアドレスアダー７１１．仮想アドレス
レジスタ７１２．マイクロアドレス制御回路７１３．制
御記憶７１４゜マイクロ命令レジスタ７１５．要素数レ
ジスタ７１６　、およびゼロ検出回路７１７を有してい
る。

この制御ユニット７は次のような動作を行なう・命令先
取シ制御回路７０１から思号線１１６を介してメモリバ
ッファユニット２に送られる命令断取シ出し要求に応答
して、ユニット２から信号線１１７を介して命令語が読
み出され、命令先取シバッ７ア７０２に格納される。命
令先取シバッ７丁７０２からは、処理すべき命令語が順
次読み出される。読み出された命令が本発明の命令であ
る場合、第１命令レジスタ７０３に命令の１番目の語・
第２命令レジスタ７０４に命令の２番目の語がセットさ
れる。配列データの先頭の要素の実効アドレスは、命令
語のソフィールドの（ｆ［（ト、ＭＰフィールドで指定
されるインデックスレジスタの値を加算することによシ
得られる。インデックスレジスタは合計８個あり、イン
デックスレジスタファイル７０５に格納さｒしている。

また実効アドレスの生成は実効アドレスアダー７０８に
よシ行われる。生成された実効アドレスは実効アドレス
レジスタ７０９に格納さ、れる。実効アドレスレジスタ
７０９の内容はベースアドレスアダー７１１によってベ
ースアドレスレジスタ７１０の内容ト加算され仮想アド
レスレジスタ７１２に格納される。仮想アドレスレジス
タ７１２の内容は信号線１１８によりメモリバッファユ
ニット２へ送られる。メモリバッファユニット２ではア
ドレス変換を行った後、配列要素の読み出しアドレスと
して使用される。２番目以降の要素の読み出しアドレス
の生成は、１つ前の要素のアドレスに命令語のＶｌフィ
ールドの値を加算することにょ夛求返られる。この加算
は実効アドレスアダー７０８により行われ、その入力の
切シがえはセレクタ７０６およびセレクタ７０７によシ
行われる。

一方、第１命令レジスタ７０３のＯＦフィールドはマイ
クロアドレス制御回路７１３に送られる。

マイクロアドレス制御回路７１３ではオペレーションコ
ードに対応してマイクロ命令の先頭アドレスが生成され
、制御記憶７１４からマイクロ命令が読み出され、マイ
クロ命令レジスタ７１５にセットされる。以降のマイク
ロ命令の読み出しはマイクロ令の分岐制御フィールドの
情報をもとにして行われる。第２命令レジスタ７０４０
ＲＮフイールドで指定されるインデックスレジスタには
配列データの要素数が格納されておシ、その値は要素数
レジスタ７１６にセットされる。要素数レジスタ７１６
の値は１要素の処理が終了する毎に・１ずつカウントダ
ウンされ、全要素の処理が終了した時にゼロとなる。こ
れはゼロ検出回路７１７で極用され、マイクロアドレス
制御回路７１３へ送られ、マイクロ命令の分岐条件とな
る。

前記レジスタ８は前記制御ユニット７の指示に従ってそ
の内容が「１」　つつ増加される。前記レジスタ９は前
記制御ユニット７の指示に従って前記レジスタ８の出力
がセットされる。前記レジスタ１１へは前記レジスタ４
の内容がセットされ、前記レジスタ１２には前記レジス
タ９の内容がセットされる。前記レジスタ１１およびレ
ジスタ１２の内容は前記セレクタ１３にょシ切シがえら
れ、前記メモリバッファユニット２を介して主記憶装置
１に書き込まれる。

′本発明の方法によシ主記憶装置１に格納−されている
配列データの要素の最小値および最小要素をめるための
処理動作は第２図のフローチャートに示され、以下の順
序で行われる。

制御ユニット７から信号線１１６を介して命令断取シ出
し要求がメモリバッファユニット２に出力されると主記
憶装置１から実行すべき命令の命令語が読み出されてメ
モリバッファユニット２および信号線１１７を介して制
御ユニット７に送られる。制御ユニット７では取り出さ
れた命令語の解読が行われる。今、取シ出された命令語
が本発明の方法を使用して配列要素の最小′値および最
小要素をめるような命令を示している場合を考える。こ
の命令語は２ワード（＝７２ビット）の長さを持ち、第
３図に示すような形式を持っている。

第３図においてＵＰはオペレーションコードフィールド
で、演算の種類を指定している。Ｙは配列要素の先頭ア
ドレスを指定するだめのアドレスフィールドであシ、ア
ドレス修飾フィールドＭＰによシ指定されたアドレス修
飾がアドレスフィールドＹの値に対して＃１とこされ、
その結果の値が要素の先頭アドレスを表わしている。〜
■！はとなシ合う要素同志のアドレスの差すなわち要素
間距離を指定し、ＲＮは要素数が格納されているレジス
タを指定している。制御ユニット７によシ本命令が解読
されると、まず先頭要素のアドレス計算が行われ、その
計算結果のアドレスから先頭要素が読み出される。先頭
要素の読み出しは命令語の読み出しと同様に主記憶装置
１からメモリバッファユニット２を介して行われる。読
み出されたデータは信号憩１０３を介してレジスタ４お
よびレジスタ５にセットされる。この時にはセレクタ３
は信号＃１０５の内容によシ制御され、信号線１０３の
内容を選択するようになっている。要素番号は「０」　
から始まっているため、先頭要素がレジスタ４およびレ
ジスタ５にセットされた時にレジスタ８は「０」にクリ
アされ、以後要素が読み出される毎に「１」づつカウン
トアツプされる。２番目の要素（要素番号「１」　）の
アドレスは先頭要素Ｇアドレスに要素間距離を加算して
得られる。

こうして得られた主記憶装置１のアドレスから２番目の
要素が読み出され、レジスタ５ヘセツトされる。このと
きレジスタ４の制御は次のように行われる。すなわち比
較回路６にょシレジスタ４とレジスタ５との内容が比較
され、レジスタ５に入っているデータの値の方が小さい
場合には信号線１０８がｒｌＪ　となる・またセレクタ
３は信号線１０４すなわちレジスタ５の内容を選択する
ように制御される。レジスタ５に２番目の要素がセット
−ａれるときに目、信号線ｔｏ６（、レジスタ５のセッ
ト信号）が「１」となるが、このとき信号線１０７も「
１」となる。アンドゲート１０によシ信号線１０７の内
容と信号線１０Ｂの内容との論理積がとられ、その出力
である信号線１０９が１１」　となった場合にはレジス
タ４にはレジスタ５の内容が移されるとともにレジスタ
９にはレジスタ８の内容が移される。同様にして３番目
からｎ番目までの要素が順番に読み出され、前記のよう
な処理がくシ返えされる。こうして最終的にレジスタ４
に格納されている値はｎ個の要素の値のうちの最ｌＪＳ
値であＪルジスタ９に格納されている値は、最小値を持
つ要素の「０」から始まる要素番号に等しい。レジスタ
４の内容はさらにレジスタ１１に転送され、レジスタ９
の内容はレジスタ１２に転送されて本命令に終了する。

レジスタ１１およびレジスタ１２の内容は信号線１１５
を通してメモリバッファユニット２に転送され、主記憶
装置１へ書き込むことができるｔ念か、他の命令によシ
使用することができる。

発明の効果 本発明に祉配列要素の最小値および最小要素の要素番号
を１命令でめることができるためプログラムのステップ
数を減らすことが可能と１６、従って処理が高速に行え
るという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示す図、第２図は第１図の
回路の動作を示すフローチャート、第３図は第２図に示
された動作を指示するための命令語の形式を表わす図お
よび第４図は第４図の制御ユニット７の詳細な構成を示
す図である。 第１図から第４図において、１・・・・主記憶装置、２
・・・・・・メモリハッファユニッ）、３．１３・・・
・・セレクタ、４，５，８，９．１１．１２・・・・・
・レジスタ、６・・・・比較回路、７・・・・・・制御
ユニット、１０・・・・・アンドゲート、７０１・・・
・・・命令先取シ制御回路、７０２・・・・・・命令先
取シバラフ了、７０３・・・・・第１命令レジスタ、７
０４・・・・・・第２命令レジスタ、７ｏ５・・・・・
・インデックスレジスタ７了イル、７０６．７０７・・
・・・セレクタ、７０８　・・・・実効アドレスアダー
、７０９　・・・実効アドレスレジスタ、７１０　・・
ベースアドレスレジスタ、７１１ベースアドレスアダー
、７１２・・・・仮想アドレスレジスタ、７１３・・・
・・マイクロアドレス制御回路、７１４・・・・・・制
御記憶、７１５・・・・・マイクロ命令レジスタ、７１
６・・・・・要素数レジスタ、７１７・・・・・・ゼロ
検出回路。 午１　図 早２　図 第３　図

Claims (1)

1. 【特許請求の範囲】 それぞれの要素に対して要素番号が付与された配列要素
   の最小値および最小要素の要素番号をめる方法であって
   、 演算の種類を指定するオペレージ目ンコードフィールド
   と配列の先頭要素のアドレスを指定するアドレス指定フ
   ィールドと要素間の距離を指定する要素間距離指定フィ
   ールドと演算を行なう要素数ｎを指定する要素数指定フ
   ィールドとを有する命令語に従って主記憶装置から配列
   要素を読み出す第１のステップと、読み出された配列要
   素のｉ番目（ｉ＝１．２．・・・＋ｎ）までの要素のう
   ちの最小値を第１の保持手段に格納し、最小値を有する
   要素の要素番号を第２の保持手段に格納する第２のステ
   ップと、前記第１の保持手段の内容と（ｊ＋１）番目の
   要素を比較するＭ３のステップと、（ｊ＋１　）番目の
   要素の方が小さい値を持つ場合にはその値を前記第１の
   保持手段に格納するとともに（ｉ＋１）番目の要素の要
   素番号を前記第２の保持手段に格納する第４のステップ
   と、ｎ番目の要素までの比較が終了した時点で前記第１
   の保持手段の内容を第１のレジスタに格納する第５のス
   テップと、さらに前記第２の保持手段の内容を第２のレ
   ジスタに格納する第６のステップとを含むことを特徴と
   する配列要素の最小値および最小要素の要素番号をめる
   方法。