JPH07120263B2 - ソ−ト機能を備えた処理装置 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、データベースマシンなどに適用して好適な
データのソート機能を備えた処理装置に関する。

［従来の技術］ 例えば、データベースマシンなどのようにデータの並べ
換え（ソート）を必要とする処理装置では、次のような
手順によって、データのソートを行っている。

すなわち、一般にソートを行うには、対象となるデータ
中の２つのデータの大小を比較し、その結果に応じて所
定の並び順となるように、メモリ上でデータ転送が繰り
返し実行される。従って、このソート処理には、メモリ
上でのデータ転送が必要となる。

この場合、メモリ間でのデータのブロック転送には、少
なくとも以下に述べるような一連のサイクルを必要とす
る。

I.転送先アドレス送出 II.被転送データ（ブロック）の読出し III.転送先アドレス送出 IV.データ（ブロック）の書き込み このように、データをソートして対応するデータを並べ
換えるには、このような一連のサイクルが各処理ごとに
実行されるものである。

［発明が解決しようとする問題点］ ところで、このように従来のソートは、メモリに格納さ
れた実際のデータを上述したようなソート処理の手順に
したがって、実際に読出したり書き込んだりしなければ
ならないため、このようなデータ転送時間が意外とかか
り、高速ソートの妨げとなっていた。

特に、この処理時間はメモリに格納された各データのデ
ータ長に比例して増加する傾向にある。

そこで、この発明ではこのような従来の問題点をハード
ウェア的に簡単に解決したものであって、メモリのバン
ク構造を採用することにより、高速ソートを可能にする
ソート機能を有する処理装置を提案するものである。

［問題点を解決するための技術的手段］ 上述の問題点を解決するため、この発明においては、CP
Uからのアドレスラインがメインメモリとバンクレジス
タに所定の配分率をもって分配され、メインメモリの１
つのバンクに割り当てられるメモリ容量を、並べ換えよ
うとするデータ長に関連した値とする。

そして、各バンクに被ソートデータを１つずつ割り当
て、ソート処理に伴なって発生する被ソートデータのCP
Uアドレス（論理アドレス）上での転送要求に際して、
バンクレジスタの内容を変更することで、この転送要求
を処理するようにしたことを特徴とするものである。

［作用］ メインメモリ12の１つのバンクに割り当てるメモリ容量
は、並べ換えようとするデータ長に関連した値に選定さ
れ、データ長が2ⁿワードのとき、ｎビットに選定される
のが望ましい。

例えば、データ長が16ワードであるならば、バンクのメ
モリ容量も16ワードに選定され、下位４ビットのアドレ
スラインが直接メインメモリに供給される。

残りのアドレスラインはバンクレジスタ13に供給され、
アドレス変換された後、メインメモリ12に供給されて、
特定のバンクを指定する。

従って、バンクレジスタ13の内容を書き換えればCPU11
が同一のアドレスを指定しても、異なったバンクをアク
セスすることになる。

換言すれば、メインメモリ12上の任意のバンクを指定し
たCPUアドレス（論理アドレス）ブロックに見せること
ができることになる。

この発明では、１つのバンクに１つの被ソートデータが
割り当てられるようにアドレスラインの配分がなされる
ので、CPU11によるソート処理に伴なって順次バンクレ
ジスタ13の内容を変更するだけで、論理アドレス上で被
ソートデータを整然と並べ換えることが可能となる。

ここで、バンクレジスタ13のデータ内容を変更すると言
っても、変更すべきデータはたかだか１ワード分位のデ
ータ量である。

これに対して、メインメモリ12のデータ転送を実行する
場合には、１つのバンクのデータの全て（例えば16ワー
ド）を変更する必要があるから、従来よりこの発明によ
る方が転送時間が著しく短縮される。また、後者の場合
には、データ長によって転送時間が相違するが、前者の
手段ではデータ長に依存しない。

［実施例］ 続いて、この発明に係るソート機能を備えた処理装置の
一例を第１図以下を参照して詳細に説明する。

第１図はこの発明に係る処理装置10の概要を示すブロッ
ク図であり、この例ではアドレスバスを中心に描いてあ
る。

11はCPUであり、制御プログラムにしたがって所定の処
理が遂行される。12はデータ格納用のメインメモリを示
し、また13はアドレス変換用のバンクレジスタを示す。

CPU11は、まず、被ソートデータをメインメモリ12上に
格納する。次に、被ソートデータのワード長に応じてワ
ード長レジスタ15を設定する。

ワード長レジスタ15は、アドレスライン切り換え用のマ
ルチプレクサ20及びデマルチプレクサ40の夫々をコント
ロールし、ワード長に応じてアドレスラインの配分率を
制御する。

ここで、ワード長が2ⁿで表せないときは、１つのバンク
のサイズをワード長以上の最小の2ⁿワードとし、この値
をワード長レジスタに設定する。そして、ソートの前処
理として、１つのバンクに１つの被ソートデータが割り
当てられるように、実際にデータ転送を行なって、メイ
ンメモリ12上のデータを移動再配置する。

次に、CPU11はソート処理プログラムを実行し、メイン
メモリ12上の２つずつの被ソートデータの大小比較を行
ない、その結果に応じてそれらのデータの論理アドレス
上での並べ換えを、バンクレジスタ13の内容を書き換え
ることで順次実行していく。

ここで、適用できるソート法としては、クイックソー
ト、ヒープソート、順次比較ソートなどあらゆるソート
法を適用できる。

第２図は第１図のブロック図をさらに具体化した一例を
示す。

ここでは、メインメモリ12の容量として1Mワード、バン
クレジスタ13のメモリ容量としては4Kワードを仮定し、
CPU11からのアドレスバスは16本の場合を考える。

ワード長レジスタ15は４ビットのラッチ回路で構成さ
れ、CPU11からのワード長制御情報を保持し、アドレス
ラインA7からA4までの中位４ビットを制御する。この例
では、ワード長として、16、32、64、128、256ワードの
いづれかを指定できるようになされている。

従って、例えば、ワード長が32ワードならワード長レジ
スタ15の出力のうち上位３ビット（Q3〜Q1）を“1"とす
ればよい。

マルチプレクサ20はバンクレジスタ13へのアドレスライ
ンを切り換えるもので、第１及び第２のゲート回路21,2
5で構成される。

第１のゲート回路21はワード長レジスタ15の出力数に対
応して４個のアンド回路を有する。

これらには、ワード長レジスタ15の出力が供給され、A7
〜A4のアドレスラインをバンクレジスタ13に供給する
か、しないかをゲートする。

第２のゲート回路25は12対の２入力セレクト回路を構成
している。

一方のアンド回路26には第１のゲート回路21の各アドレ
スラインが供給されると共に、後述するデコーダ16のデ
コード出力がそのゲート信号として供給される。他方の
アンド回路27には、CPU11から直接12ビットのアドレス
ラインA11〜A0が供給されると共に、上述のデコード出
力が反転された状態で供給される。

第１及び第２のアンド回路26、27の各出力（12ビットの
アドレスライン）はオア回路28を介してバンクレジスタ
13に供給される。

ここで、CPU11から直接供給された12ビットのアドレス
ラインA11〜A0は、バンクレジスタ13のデータ内容を変
更するためにアクセスするときに使用されるものであ
る。上述したように、4Kワードのバンクレジスタ13をア
クセスするには、12ビットのアドレスで必要十分であ
る。

デコーダ16は、４入力ナンド回路からなり、これには上
位４ビットのアドレスラインA15〜A12が入力され、それ
らが全て“1"のとき、すなわち最上位桁が“F_H”（Ｈは
ヘキサデシマル表示）のとき、ゲート回路25を切り換
え、第３図に示すようにバンクレジスタ13をアクセスす
るように構成されている。

これによって、バンクレジスタ13のアドレス０からFFF_H
を、順にCPUアドレスF000_HからFFFF_Hに割り当てること
ができる。

なお、このデコード出力はデータバスの接続切り換えに
も使用される。

つまり、CPU11がF000_H未満をアクセスしたときには、メ
インメモリ12がCPU11のデータバスに接続され、F000_H以
上をアクセスしたときには、メインメモリ12をCPU11の
データバスから切り放し、バンクレジスタ13がCPU11の
データバスに接続されるようになされる（第３図参
照）。

上述したワード長レジスタ15の各出力はデマルチプレク
サ40にも供給される。

デマルチプレクサ40も複数のアンド回路で構成されたア
ンド回路群41と、複数のオア回路で構成されたオア回路
群42とを有する。

アンド回路群41のうち４個のアンド回路41Aは入力否定
形が使用され、これらにはCPU11からのアドレスライン
（無変換アドレス情報）A7〜A4が供給される。残りのア
ンド回路41Bにはバンクレジスタ13から出力されたアド
レスラインのうち、対応する変換後のアドレスライン
（変換アドレス情報）A7〜A4が入力される。そして、ワ
ード長レジスタ15の各出力がこのアンド回路群41にゲー
ト信号として共通に供給される。

そして、無変換アドレス情報と変換アドレス情報（共に
A7〜A4）とがオア回路群42を構成する各オア回路に供給
される。従って、このオア回路群42からは無変換アドレ
ス情報と、変換アドレス情報（共にA7〜A4）が選択され
て出力される。

また、CPU11から送出されたA3〜A0までのアドレスライ
ンと、バンクレジスタ13から出力されたA19〜A8までの
アドレスラインは直接メインメモリ12に供給される。

ここで、ソートすべきデータ長が16ワードであるときに
は、ワード長レジスタ15の各出力とも“1"に設定されて
いるので、これによってデマルチプレクサ40に設けられ
たアンド回路41Aのゲートが閉じ、マルチプレクサ20の
第１のゲート回路21が開く。従って、この場合には変換
アドレス情報A7〜A4が得られる。

これに対して、ソートすべきデータ長が32ワードである
ときには、ワード長レジスタ15の出力のうち上位３ビッ
ト（Q3〜Q1）のみが“1"に設定される。これによって、
論理アドレスラインA3〜A0の他にA4がメインメモリ12の
物理アドレス情報として、直接供給されることになる。

このように、この発明におけるソート処理は究極のとこ
ろ、バンクレジスタ13のデータ内容を変更する処理であ
る。すなわち、対象となるデータ中の２つのデータの大
小が比較され、その結果に応じて所定の並び順となるよ
うにバンクレジスタ13のデータ内容が順次変更される。
この場合変更されるアドレス情報は１ワード（16ビッ
ト）であり、ソート処理によってメインメモリ12上のデ
ータそのものの転送処理はなされない。

［発明の効果］ 以上説明したように、この発明によれば、メインメモリ
をバンク化すると共に、１つのバンクに割り当てるメモ
リ容量を、並べ換えようとするデータ長に関連した値と
すると共に、ソートによってバンクレジスタのデータ内
容を変更するようにしたものである。

これによれば、ソート処理によって実際に変更されるデ
ータはバンクレジスタのデータ内容だけであるから、こ
のデータ内容を変更するだけでソートに伴なう転送処理
を実現できる。

そのため、データ変更のために要する処理時間（上述し
たＩ〜IVの処理時間）を従来よりも大幅に短縮すること
ができ、高速ソートを実現できる特徴を有する。しか
も、この高速ソートは取り扱うデータ長には全く依存し
ない。

従来においては、メインメモリ上のデータそれ自体を転
送して並べ換えしているので、ソート処理中の転送時間
は並べ換えようとするデータのデータ長に依存する。

従って、データ長が長いときにはそれに伴って、転送時
間がかかり、高速ソートが困難である。

このようなことから、この発明に係るソート機能を備え
た処理装置は、データベースマシンなどに適用して極め
て好適である。

【図面の簡単な説明】

第１図はこの発明に係るソート機能を備えた処理装置の
一例を示すブロック図、第２図はその具体例を示す要部
のブロック図、第３図は第２図の例における論理アドレ
スマップを示す図である。 10……処理装置 11……CPU 12……メインメモリ 13……バンクレジスタ 15……ワード長レジスタ 16……デコーダ 20……マルチプレクサ 40……デマルチプレクサ

Claims (2)

【特許請求の範囲】
1. 【請求項１】メインメモリの１つのバンクに割り当てら
   れるメモリ容量が、並べ換えようとするデータ長に関連
   した値となるように、CPUからのアドレスラインをメイ
   ンメモリとバンクレジスタに所定の配分率をもって分配
   し、 上記バンクレジスタにより変換された上位アドレスと上
   記CPUから直接供給された下位アドレスとによって、上
   記メインメモリをアクセスするように構成されたソート
   機能を備えた処理装置において、 ソート処理の進行に伴なって、上記バンクレジスタの内
   容を変更していくことで、上記メインメモリ上にランダ
   ムに配置されたデータを上記CPUアドレス上に所定の順
   序に並べ換える機能を備えた処理装置。
2. 【請求項２】上記データ長ｘが2ⁿ≧ｘ＞2^n-1（n,xは共
   に正の整数）のとき、上記メインメモリに直接供給され
   るアドレスラインがｎビットに選定されてなる特許請求
   の範囲第１項記載のソート機能を備えた処理装置。