(57)【要約】【課題】回路規模の増大を抑制しつつ、ソート処理を高速化する。【解決手段】メモリ１００は、複数の領域を含む。それぞれの領域内において起点から終点へ所定の方向に沿って循環するようにアドレスが付与される。オフセットテーブル２００は、起点となるアドレスを特定するためのオフセットを領域ごとに記憶する。挿入先バンク特定部４２０は、オフセットに基づいて領域から読み出した整列データと追加データとを比較することによって前記追加データを挿入すべき領域を特定する。バンク内データ挿入部４４０は、特定された領域内の整列データと追加データとを比較することによって追加データを挿入すべきアドレスを特定して挿入する。オフセット管理部４３０は、追加データの挿入により領域内から溢れた整列データをオフセットに基づいて領域間で移動させ、整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新する。【選択図】図１
2012089001.tif 000002
【特許請求の範囲】
【請求項１】
複数の領域を含み、それぞれの前記領域内において起点から終点へ所定の方向に沿って循環するようにアドレスが付与されるメモリと、
前記起点となるアドレスを特定するためのオフセットを前記領域ごとに記憶するオフセット記憶部と、
前記複数の領域にまたがって整列した一連の整列データに追加するデータを追加データとして、前記オフセットに基づいて前記領域から読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定する挿入先領域特定部と、
前記挿入先領域特定部により特定された前記領域内の前記整列データと前記追加データとを比較することによって前記追加データを挿入すべきアドレスを特定して挿入する領域内データ挿入部と、
前記追加データの挿入により前記領域内から溢れた整列データを前記オフセットに基づいて領域間で移動させるとともに、前記溢れた整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新するオフセット管理部と
を具備するデータ整列装置。
【請求項２】
それぞれの前記領域内において起点から終点へ所定の方向に沿って循環するようにアドレスを生成するアドレス生成部を更に具備し、
前記挿入先領域特定部は、前記オフセットに基づいて前記アドレス生成部に前記領域内のアドレスを生成させ、生成させた前記アドレスから読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定し、
前記領域内データ挿入部は、前記挿入先領域特定部により特定された前記領域内のアドレスを前記アドレス生成部に生成させ、生成させた前記アドレスから読み出した前記整列データと前記追加データとを比較することにより前記追加データを挿入すべきアドレスを特定して挿入し、
前記オフセット管理部は、前記追加データの挿入により前記領域内から溢れた整列データの移動先のアドレスを前記オフセットに基づいて前記アドレス生成部に生成させ、生成させた前記アドレスへ移動させることによって前記データを領域間で移動させるとともに、前記溢れた整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新する
請求項１記載のデータ整列装置。
【請求項３】
前記メモリのうち、前記整列データおよび前記追加データを格納すべき部分において、前記複数の領域が前記部分を所定の容量ごとに等分するように前記複数の領域を定義するメモリ構成定義部をさらに具備する請求項１に記載のデータ整列装置。
【請求項４】
前記メモリ構成定義部は、前記部分が格納するデータの個数が最大で２のべき乗となるように前記部分を定義する
請求項３記載のデータ整列装置。
【請求項５】
前記メモリ構成定義部は、それぞれの前記領域が格納するデータの個数が最大で２のべき乗となるように前記複数の領域を定義する
請求項３記載のデータ整列装置。
【請求項６】
前記挿入先領域判断部は、
前記複数の領域のうち、前記追加データを挿入すべきか否かを判断する領域を示す変数を保持する変数保持部と、
前記変数の示す前記領域を選択し、選択した前記領域内から前記オフセットに基づいて読み出した前記整列データと前記追加データとを比較することによって前記領域が前記追加データを挿入すべき領域か否かを判断し、判断した結果に基づいて前記変数を更新する挿入先領域判断処理部と
を具備する請求項１記載のデータ整列装置。
【請求項７】
前記整列データと前記追加データとを比較する比較部をさらに具備し、
前記挿入先領域特定部は、前記オフセットに基づいて前記領域から読み出した前記整列データと前記追加データとを前記比較部に比較させ、比較させた結果から前記追加データを挿入すべき領域を特定する挿入先領域特定部と、
前記領域内データ挿入部は、前記挿入先領域特定部により特定された前記領域内の前記整列データと前記追加データとを前記比較部に比較させ、比較させた結果から、前記追加データを挿入すべきアドレスを特定して挿入する
請求項１記載のデータ整列装置。
【請求項８】
前記挿入先領域特定部は、前記領域に対応する前記オフセットの示す始点に対する終点のアドレスから前記整列データを読み出し、読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定する
請求項１記載のデータ整列装置。
【請求項９】
前記オフセット管理部は、前記移動先の領域に対応するオフセットの示す始点に対する終点であったアドレスへ前記溢れたデータを移動させるとともに、前記アドレスが前記移動先の領域内の始点となるように前記オフセットを更新する
請求項１記載のデータ整列装置。
【請求項１０】
複数の領域を含むメモリに、それぞれの前記領域内において起点から終点へ所定の方向に沿って循環するようにアドレスが付与される場合に前記起点となるアドレスを特定するためのオフセットを前記領域ごとにオフセット記憶部に記憶する手順と、
前記複数の領域にまたがって整列した一連の整列データに追加するデータを追加データとして、前記オフセットに基づいて前記領域から読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定する挿入先領域特定手順と、
前記挿入先領域特定手順により特定された前記領域内の前記整列データと前記追加データとを比較することによって前記追加データを挿入すべきアドレスを特定して挿入する領域内データ挿入手順と、
前記追加データの挿入により前記領域内から溢れた整列データを前記オフセットに基づいて領域間で移動させるとともに、前記整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新するオフセット管理手順と
を具備するデータ整列装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ整列装置に関し、特にデータを昇順または降順に整列するデータ整列装置、および、そのデータ整列装置の制御方法に関する。
【背景技術】
【０００２】
従来、データベースや画像などといった大量のデータを扱う機器においては、値の大小関係等に基づいて、それらのデータをソートする必要が生じうる。また、ハードディスクや光学ディスクなどの記憶装置の大容量化や、通信機器の高速化により、機器がソート処理の対象とするデータの量は増大する傾向にある。ソート処理の対象のデータ量が増大するほど、機器のソート処理時間は増大してしまうため、ソート処理を高速化する各種の技術が開発されている。
【０００３】
ソートするデータを抽出する処理を行う抽出処理部と、ソート処理を行うソート処理部とを備える機器について考える。この機器がソート処理を行う場合、抽出処理部が全てのデータを抽出してから、それらのデータをソート処理部が一括してソートする構成とすると、ソート処理部の負担が大きくなり、処理時間の短縮が困難となる。抽出処理部およびソート処理部をパイプライン化して、ソート対象のデータを抽出処理部が抽出するたびに、抽出されたデータをソート処理部がソート済みのデータ列の中に挿入する構成とした方が、機器全体としては、より効率的である。
【０００４】
ここで、整列済みのデータ列にデータを挿入するソート法としては、挿入ソート法、二分挿入ソート法、および、シェルソート法などの方法がある。この中では、アルゴリズムが単純なことから、挿入ソート法が使用されることがよくある。この挿入ソート法は、ソートされたデータ列から、機器が整列順にデータを１つずつ読み出し、挿入するデータと読み出したデータとを比較することにより、挿入位置を探索して挿入する方法である。探索においては、機器はデータを比較するたびに、整列順において比較したデータ以降の各データを後ろへ１つずつずらしてゆく。
【０００５】
データ抽出部がデータを抽出するたびに、ソート処理部が上述した挿入ソート法などを用いて整列済みのデータ列に、抽出されたデータを挿入する構成を想定する。この構成において、機器が行うソート処理がシステム全体のボトルネックとならないためには、データの抽出間隔よりも、抽出されたデータの挿入処理にかかる時間が短くなることが望ましい。
【０００６】
データの挿入処理を高速化するため、この挿入処理を行う回路の一部を並列化する方法が提案されている。例えば、データ間の大小を比較する比較器を複数個備え、これらの比較器を並列動作させることにより、各データと追加データとの間の比較に要する時間を低減する技術が提案されている（例えば、特許文献１参照。）。また、複数の比較器と、複数個のメモリとを備え、各メモリと比較器とを並列または直列に接続することにより、挿入処理におけるパイプライン処理を高速化する技術が提案されている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１０−６２４８３号公報
【特許文献２】特開平８−９５７５３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の従来技術では、挿入処理を行う回路を並列化しているため、その回路の回路規模が増大してしまうという問題があった。また、回路規模の増大に伴い消費電力も増大してしまう。特に比較器などのロジック回路の数は、並列数を増やすほど増加してしまう。
【０００９】
本発明はこのような状況に鑑みてなされたものであり、回路規模の増大を抑制しつつ、ソート処理を高速化することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、複数の領域を含み、それぞれの前記領域内において起点から終点へ所定の方向に沿って循環するようにアドレスが付与されるメモリと、前記起点となるアドレスを特定するためのオフセットを前記領域ごとに記憶するオフセット記憶部と、前記複数の領域にまたがって整列した一連の整列データに追加するデータを追加データとして、前記オフセットに基づいて前記領域から読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定する挿入先領域特定部と、前記挿入先領域特定部により特定された前記領域内の前記整列データと前記追加データとを比較することによって前記追加データを挿入すべきアドレスを特定して挿入する領域内データ挿入部と、前記追加データの挿入により前記領域内から溢れた整列データを前記オフセットに基づいて領域間で移動させるとともに、前記溢れた整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新するオフセット管理部とを具備するデータ整列装置、および、その制御方法である。これにより、追加データの挿入により領域内から溢れた整列データが領域間で移動するとともに、溢れた整列データの移動先のアドレスが移動先の領域内の始点となるようにオフセットが更新されるという作用をもたらす。
【００１１】
また、この第１の側面において、それぞれの前記領域内において起点から終点へ所定の方向に沿って循環するようにアドレスを生成するアドレス生成部を更に具備し、前記挿入先領域特定部は、前記オフセットに基づいて前記アドレス生成部に前記領域内のアドレスを生成させ、生成させた前記アドレスから読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定し、前記領域内データ挿入部は、前記挿入先領域特定部により特定された前記領域内のアドレスを前記アドレス生成部に生成させ、生成させた前記アドレスから読み出した前記整列データと前記追加データとを比較することにより前記追加データを挿入すべきアドレスを特定して挿入し、前記オフセット管理部は、前記追加データの挿入により前記領域内から溢れた整列データの移動先のアドレスを前記オフセットに基づいて前記アドレス生成部に生成させ、生成させた前記アドレスへ移動させることによって前記データを領域間で移動させるとともに、前記溢れた整列データの移動先のアドレスが移動先の領域内の始点となるように前記オフセットを更新してもよい。これにより、挿入先領域特定部、領域内データ追加部、および、オフセット管理部は、アドレス生成部にアドレスを生成させるという作用をもたらす。
【００１２】
また、この第１の側面において、前記メモリのうち、前記整列データおよび前記追加データを格納すべき部分において、前記複数の領域が前記部分を所定の容量ごとに等分するように前記容量を設定するメモリ構成定義部をさらに具備してもよい。これにより、整列データおよび追加データを格納すべき部分が等分されるように複数の領域が定義されるという作用をもたらす。
【００１３】
また、この第１の側面において、上記メモリ構成定義部は、上記部分が格納するデータの個数が最大で２のべき乗となるように上記部分を定義してもよい。これにより、整列データを格納すべき部分が格納するデータの個数が２のべき乗になるという作用をもたらす。
【００１４】
また、この第１の側面において、上記メモリ構成定義部は、それぞれの上記領域が格納するデータの個数が最大で２のべき乗となるように上記複数の領域を定義してもよい。これにより、それぞれの上記領域が格納するデータの個数が最大で２のべき乗になるという作用をもたらす。
【００１５】
また、この第１の側面において、前記挿入先領域判断部は、前記複数の領域のうち、前記追加データを挿入すべきか否かを判断する領域を示す変数を保持する変数保持部と、前記変数の示す前記領域を選択し、選択した前記領域内から前記オフセットに基づいて読み出した前記整列データと前記追加データとを比較することによって前記領域が前記追加データを挿入すべき領域か否かを判断し、判断した結果に基づいて前記変数を更新する挿入先領域判断処理部とを具備してもよい。これにより、変数の示す領域を選択して、その領域が追加データを挿入すべき領域か否かを判断し、判断した結果に基づいて前記変数を更新するという作用をもたらす。
【００１６】
また、この第１の側面において、前記整列データと前記追加データとを比較する比較部をさらに具備し、前記挿入先領域特定部は、前記オフセットに基づいて前記領域から読み出した前記整列データと前記追加データとを前記比較部に比較させ、比較させた結果から前記追加データを挿入すべき領域を特定する挿入先領域特定部と、前記領域内データ挿入部は、前記挿入先領域特定部により特定された前記領域内の前記整列データと前記追加データとを前記比較部に比較させ、比較させた結果から、前記追加データを挿入すべきアドレスを特定して挿入してもよい。これにより、挿入先領域特定部および領域内データ挿入部が比較部にデータを比較させるという作用をもたらす。
【００１７】
また、この第１の側面において、前記挿入先領域特定部は、前記領域に対応する前記オフセットの示す始点に対する終点のアドレスから前記整列データを読み出し、読み出した前記整列データと前記追加データとを比較することによって前記追加データを挿入すべき領域を特定してもよい。これにより、領域内の終点のアドレスから読み出した整列データと追加データを比較することにより、追加データを挿入すべき領域を特定するという作用をもたらす。
【００１８】
また、この第１の側面において、前記オフセット管理部は、前記移動先の領域に対応するオフセットの示す始点に対する終点であったアドレスへ前記溢れたデータを移動させるとともに、前記アドレスが前記移動先の領域内の始点となるように前記オフセットを更新してもよい。これにより、溢れたデータが移動先の領域内の終点のアドレスに移動し、移動先のアドレスが始点となるようにオフセットが更新されるという作用をもたらす。
【発明の効果】
【００１９】
本発明によれば、回路規模の増大を抑制しつつ、ソート処理が高速化するという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】実施の形態におけるデータ整列装置６００の一構成例を示すブロック図である。
【図２】実施の形態におけるメモリ構成定義の一例である。
【図３】実施の形態におけるアドレスの管理方法を説明するための図、および、実施の形態におけるメモリ１００の物理アドレスの一構成例を示す図である。
【図４】実施の形態におけるメモリ１００のアドレス空間の一例を示す図である。
【図５】実施の形態におけるオフセットテーブル２００の一構成例を示す図である。
【図６】実施の形態におけるデータ整列装置６００を実現する具体的な回路の一例を示す回路図である。
【図７】実施の形態におけるセレクタ４４４の動作の一例を示す真理値表である。
【図８】実施の形態におけるデータ整列装置６００の制御手順の一例を示すフローチャートである。
【図９】実施の形態におけるデータ挿入処理の一例を示すフローチャートである。
【図１０】実施の形態における挿入先バンク探索処理の一例を示すフローチャートである。
【図１１】実施の形態におけるバンク内データ挿入処理の一例を示すフローチャートである。
【図１２】実施の形態におけるソートデータ出力処理の一例を示すフローチャートである。
【図１３】実施の形態におけるデータ整列装置６００の動作結果の一例を示すタイミングチャートである。
【図１４】実施の形態におけるデータ整列装置６００の動作結果の一例を説明するための図である。
【図１５】実施の形態におけるデータ整列装置６００の論理バンク数の増減に伴うソート処理時間の増減を示すグラフである。
【図１６】実施の形態におけるデータ整列装置６００の論理バンク数の増減に伴う回路規模の増減を示すグラフである。
【図１７】実施の形態におけるデータ整列装置６００の変形例を示すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．実施の形態（データ整列装置の制御：バッファを複数の論理バンクに区分する例）
２．変形例
【００２２】
＜１．実施の形態＞
［データ整列装置の構成例］
図１は、実施の形態におけるデータ整列装置６００の一構成例を示すブロック図である。このデータ整列装置６００は、メモリ１００、オフセットテーブル２００、アドレス生成部３００、メモリ構成定義部４１０、挿入先バンク特定部４２０、オフセット管理部４３０、および、バンク内データ挿入部４４０を備える。
【００２３】
メモリ１００は、所定の容量のデータを記憶する記憶装置である。メモリ１００には、連続的な物理アドレスが定義されている。物理アドレスは、データが格納されているメモリ１００内の物理的な場所を示すアドレスである。メモリ１００は、アドレス生成部３００からアクセス先の物理アドレスを受け取る。また、メモリ１００は、挿入先バンク特定部４２０、オフセット管理部４３０、または、バンク内データ挿入部４４０からＲ／Ｗ指示信号を受け取る。Ｒ／Ｗ指示信号は、データの読出し、または、データの書込みを指示する信号である。メモリ１００は、Ｒ／Ｗ指示信号に従って、アドレス生成部３００が生成した物理アドレスにアクセスし、その応答を挿入先バンク特定部４２０、オフセット管理部４３０、または、バンク内データ挿入部４４０へ供給する。
【００２４】
メモリ構成定義部４１０は、メモリ１００において複数の領域を定義するものである。詳細には、メモリ構成定義部４１０は、まず、メモリ１００のうち、整列するデータを格納するバッファとして使用する部分を定義する。具体的には、メモリ構成定義部４１０は、そのバッファの先頭の物理アドレスと、バッファのデータサイズとを設定する。次に、メモリ構成定義部４１０は、バッファを等分する複数の領域を定義する。以下、メモリ構成定義部４１０が区分した各領域を論理バンクと称する。具体的には、メモリ構成定義部４１０は、論理バンク１つ当たりのデータサイズを設定する。ここで、メモリ構成の定義は、ユーザの操作またはプログラムの実行により変更することができるものとする。
【００２５】
アドレス生成部３００は、メモリ１００内のいずれかの物理アドレスを生成するものである。アドレス生成部３００は、挿入先バンク特定部４２０、オフセット管理部４３０、または、バンク内データ挿入部４４０からアドレス生成指示信号を受け取る。このアドレス生成指示信号は、アクセス先の物理アドレスが属する論理バンクを示す情報と、その物理アドレスの論理バンク内における相対的なアドレスを示す情報とを含む信号である。アドレス生成部３００は、アドレス生成指示信号に基づいて、論理バンクを求める。論理バンクを求めた後、アドレス生成部３００は、論理バンク内の起点となるアドレスから、終点となるアドレスへ論理バンク内において循環するように論理バンク内における相対的なアドレスを生成する。循環する方向は、整列順に沿った方向、例えば、物理アドレスが増分していく方向とする。アドレス生成部３００は、求めた論理バンクと、その相対的なアドレスとから物理アドレスを生成する。
【００２６】
オフセットテーブル２００は、各論理バンク内のオフセットを保持するものである。オフセットとは、論理バンク内の境界を示すアドレスと、論理バンク内の循環において始点となるアドレスとの間の距離である。以下、オフセットの示すアドレスをオフセットアドレスと称する。ここで、オフセットの値は、必ずしも固定されたものではなく、論理バンク内へのデータの追加に伴いオフセット管理部４３０により変更されうる。
【００２７】
挿入先バンク特定部４２０は、データの挿入先を探索する処理において、各論理バンクが、追加データを挿入すべき論理バンクかを特定するものである。追加データとは、整列されたデータ列に追加するデータとしてデータ整列装置６００に入力されるデータである。挿入先バンク特定部４２０は、メモリ１００に整列されたデータ列が書き込まれた状態において、追加データが入力されると、いずれかの論理バンクを選択し、その論理バンク内の終点のアドレスに書き込まれたデータを比較データとして読み出す。挿入先バンク特定部４２０は、比較データと追加データとを比較し、その比較結果に基づいて論理バンクが追加データを挿入すべき論理バンクであるか否かを判断する。挿入先バンク特定部４２０は、判断結果をオフセット管理部４３０およびバンク内データ挿入部４４０へ通知する。
【００２８】
オフセット管理部４３０は、追加データの挿入により溢れたデータを論理バンク間で移動させるとともに、各論理バンク内のオフセットを管理するものである。オフセット管理部４３０は、挿入先バンク特定部４２０により論理バンクが追加データを挿入すべき論理バンクでないと判断された場合、メモリ構成定義部４１０により定義されたメモリ構成を参照する。そして、オフセット管理部４３０は、メモリ構成に基づいて、データの整列順において比較データの次のデータが格納されている論理バンクを求める。比較データが整列順において追加データより後のデータであった場合、その比較データは、追加データの挿入により、属していた論理バンク内から溢れる。求めた論理バンクは、この溢れた比較データの移動先の論理バンクに該当する。オフセット管理部４３０は、求めた論理バンク内の終点のアドレスに比較データを書き込む。書き込まれた比較データは、書込み先の論理バンク内において、整列順において先頭のデータとなる。オフセット管理部４３０は、比較データを書き込んだ論理アドレスがオフセットアドレスとなるように、オフセットテーブル２００内のオフセットを更新する。オフセットの更新により、論理バンク内において、論理バンク内の各データをオフセットアドレスから循環の方向に沿って読み出して配列すると、配列の順番は整列順になる。つまり、オフセットの更新により、論理バンク内の整列順が維持される。
【００２９】
バンク内データ挿入部４４０は、論理バンク内に追加データを挿入するものである。バンク内データ挿入部４４０は、挿入先バンク特定部４２０により論理バンクが追加データを挿入すべき論理バンクであると判断された場合、メモリ構成定義部４１０により定義されたメモリ構成を参照する。そして、バンク内データ挿入部４４０は、メモリ構成および整列されたデータ総数から、その論理バンク内の整列されたデータ数を求める。バンク内データ挿入部４４０は、求めたデータ数のデータを論理バンク内から順に読み出し、追加データと比較する。バンク内データ挿入部４４０は、比較結果に基づいて追加データを挿入すべき物理アドレスを探索し、探索した物理アドレスに追加データを挿入する。
【００３０】
なお、上述の実施の形態の挿入先バンク特定部４２０は、特許請求の範囲に記載の挿入先領域特定部の一例である。上述の実施の形態のオフセットテーブル２００は、特許請求の範囲に記載のオフセット記憶部の一例である。上述の実施の形態のバンク内データ挿入部４４０は、特許請求の範囲に記載の領域内データ挿入部の一例である。
【００３１】
図２は、メモリ構成定義部４１０が定義したメモリ構成の一例を示す図である。メモリ構成定義部４１０により、「始点アドレス」として「ｘｘ・・・ｘ」が設定され、「バッファサイズ」として「２Ｎワード」が設定され、「バンクサイズ」として「２ｎワード」が設定されている。ここで、「ｘ」は、任意の値をとりうる１ビットの情報であり、「Ｎ」は０以上の整数であり、「ｎ」は「Ｎ」以下の０以上の整数である。始点アドレスは、メモリ１００内において、バッファの始点となる物理アドレスである。「バッファサイズ」は、バッファのデータサイズである。「バンクサイズ」は、各論理バンクのデータサイズである。以下、整列対象の各データのデータサイズは全て１ワードであるとする。定義において「バッファサイズ」として「２Ｎワード」が設定されているため、バッファには、最大で２Ｎ個のデータが格納される。また、「バンクサイズ」として「２nワード」が設定されているため、各論理バンクには、最大で２n個のデータが格納される。以下、バッファサイズが格納するデータ数の最大値のべき指数を「Ｎ」とし、１つの論理バンクが格納するデータ数の最大値のべき指数を「ｎ」とする。なお、この例では、「バッファサイズ」および「バンクサイズ」のそれぞれのワード数をバッファ構成に設定することとしているが、これらのべき指数をバッファ構成に設定することとしてもよい。
【００３２】
図３（ａ）は、実施の形態におけるメモリ１００内の物理アドレスの管理方法を説明するための図である。メモリ構成の定義として、図２に例示したメモリ構成と同様のメモリ構成が設定された場合について考える。この場合、２Ｎワードのサイズのバッファが設定され、このバッファは２ｎワードのサイズの複数の論理バンク「＃１」乃至「＃ｍ」により区分される。各論理バンク内においては、生成される物理アドレスが始点から終端へ循環するように、その論理バンク内の物理アドレスが生成される。言い換えれば、各論理バンクは、アドレスが論理的に環状に配置されたリングバッファとして扱われる。
【００３３】
図３（ｂ）は、実施の形態におけるメモリ１００の物理アドレスのうち、バッファとして使用されるフィールドの構成例を示す図である。メモリ構成の定義として、図２に例示した定義と同様の定義を設定した場合について考える。この場合、メモリ構成定義部４１０は、物理アドレスの０ビット目からｎ−１ビット目までのビット列の示す値がバンク内アドレスを示し、ｎビット目からＮ−１ビット目までのビット列が示す値がバンクアドレスを示すことになる。バンクアドレスは、各論理バンクを識別するための番号である。バンク内アドレスは、バッファ内の物理アドレスの論理バンク内における相対的な位置を示す値である。
【００３４】
図４は、実施の形態におけるメモリ１００のアドレス空間の一例を示す図である。図３（ｂ）に例示した物理アドレスの構成において、Ｎ＝１０、ｎ＝５とした場合について考える。この場合、バッファサイズは２１０（＝１０２４）ワードとなり、各バンクのデータサイズは、２５（＝３２）ワードとなる。物理アドレスの下位５ビットは、「０００００」から「１１１１１」までの中のいずれかの値をとる。物理アドレスの上位５ビットは、「０００００」から「１１１１１」までの中のいずれかの値をとる。このように、バッファサイズおよびバンクサイズを２のべき乗のワード数とすることにより、データ整列装置６００は、物理アドレスの上位のビット列をバンクアドレスに割り当て、下位のビット列をバンク内アドレスに割り当てることができる。このため、データ整列装置６００は、バンクアドレスやバンク内アドレスの増減をビット演算により容易に行うことができる。
【００３５】
図５は、オフセットテーブル２００の一構成例を示す図である。図３（ｂ）に例示した物理アドレスの構成において、Ｎ＝１０、ｎ＝５とした場合について考える。この場合、バンクアドレスは「０００００」から「１１１１１」までの中のいずれかの値をとる。オフセットテーブル２００は、それぞれのバンクアドレスに対応するオフセットを格納する。オフセットの値は、「０００００」から「１１１１１」までの中のいずれかの値となる。例えば、アドレステーブル２００は、バンクアドレス「１１１１１」に対応するオフセットとして「１１１１０」を保持し、バンクアドレス「１１１１０」に対応するオフセットとして「１１１０１」を保持している。
【００３６】
図６は、実施の形態におけるデータ整列装置６００を実現する具体的な回路の一例を示す回路図である。データ整列装置６００は、メモリ１０１、オフセットテーブル２０１、アドレス生成部３０１、制御部４００、バンクカウンタ４２２、ソートデータ数カウンタ４４２、バンク内ワードカウンタ４４３、セレクタ４４４、および、比較部５００を備える。制御部４００は、メモリ構成定義部４１１、挿入先バンク特定処理部４２１、オフセット管理部４３１、および、バンク内データ挿入処理部４４１を備える。
【００３７】
図１におけるメモリ１００は、図６におけるメモリ１０１により実現される。図１におけるオフセットテーブル２００は、図６におけるオフセットテーブル２０１により実現される。図１におけるアドレス生成部３００は、図６におけるアドレス生成部３０１により実現される。図１におけるメモリ構成定義部４１０は、図６におけるメモリ構成定義部４１１により実現される。図１における挿入先バンク特定部４２０は、図６における挿入先バンク特定処理部４２１、バンクカウンタ４２２、および、比較部５００により実現される。図１におけるバンク内データ挿入部４４０は、図６におけるバンク内データ挿入処理部４４１、ソートデータ数カウンタ４４２、バンク内ワードカウンタ４４３、セレクタ４４４、および、比較部５００により実現される。
【００３８】
メモリ１０１は、所定の容量のデータを記憶する記憶装置である。メモリ１０１は、制御部４００からＲ／Ｗ指示信号を受け取り、アドレス生成部３０１から物理アドレスを受け取る。また、メモリ１０１は、セレクタ４４４からデータを受け取る。Ｒ／Ｗ信号がデータの読出しを指示する信号である場合、メモリ１０１は、受け取った物理アドレスからデータを読み出し、比較部５００およびセレクタ４４４へ供給する。Ｒ／Ｗ信号がデータの書込みを指示する信号である場合、メモリ１０１は、セレクタ４４４から受け取ったデータを、アドレス生成部３０１から受け取った物理アドレスに書き込む。
【００３９】
オフセットテーブル２０１は、各論理バンクのオフセットを保持するものである。バンクカウンタ４２２は、挿入先バンク特定処理部４２１の判断に応じてバンクアドレスを計数するカウンタである。ソートデータ数カウンタ４４２は、整列されたデータの個数を計数するカウンタである。バンク内ワードカウンタ４４３は、論理バンク内の物理アドレスを特定する値を計数するカウンタである。バンク内ワードカウンタ４４３は、例えば、カウンタ値を保持するクロック同期式回路と、そのクロック同期式回路の出力に接続された加算器とから構成される。このクロック同期式回路の保持値の設定には１クロックを要するが、加算器の加算処理は、１クロックより短い時間内に完了するものとする。
【００４０】
セレクタ４４４は、メモリ１０１から読み出されたデータ、または、追加データをメモリ１０１に供給するものである。
【００４１】
図７は、セレクタ４４４の動作の一例を示す真理値表である。セレクタ４４４は、バンク内データ挿入処理部４４１からデータ追加指示信号を受け取る。データ追加指示信号は、追加データを挿入すべきか否かを指示する信号である。例えば、追加データを挿入すべき場合に、バンク内データ挿入処理部４４１からハイレベルのデータ追加指示信号が供給され、そうでない場合に、ローレベルのデータ追加指示信号が供給される。データ追加指示信号がハイレベルの場合、セレクタ４４４は追加データを入力元として選択する。データ追加指示信号がローレベルの場合、セレクタ４４４はメモリ１０１から読み出されたリードデータを入力元として選択する。
【００４２】
図６に戻り、比較部５００は、メモリ１０１から読み出されたデータと、追加データとを比較した結果を示す信号を挿入先バンク特定処理部４２１およびバンク内データ挿入処理部４４１へ供給するものである。
【００４３】
アドレス生成部３０１は、メモリ１０１内のいずれかの物理アドレスを生成するものである。アドレス生成部３０１は、挿入先バンク特定処理部４２１、オフセット管理部４３１、または、バンク内データ挿入処理部４４１からアドレス生成指示信号を受け取る。アドレス生成指示信号には、バンクアドレスを増減する値と、オフセットアドレスを増減する値と、ワードカウンタ値を加算するか否かを示す情報とが含まれている。
【００４４】
アドレス生成部３０１は、アドレス生成指示信号を受け取ると、バンクカウンタ４２２からバンクアドレスを読み出して、アドレス生成指示信号の示す値の分だけ増減する。アドレス生成部３０１は、増減した結果に対応するオフセットをオフセットテーブル２０１から読み出し、アドレス生成指示信号の示す値の分だけ読み出したオフセットを増減する。
【００４５】
アドレス生成指示信号がワードカウンタ値の加算を指示しない信号である場合、アドレス生成部３０１は、バンクアドレスを増減した結果と、オフセットを増減した結果から、メモリ構成定義に基づいて物理アドレスを生成する。例えば、バッファサイズが２Ｎワード、論理バンクのデータサイズが２ｎワードである場合、アドレス生成部３０１は、Ｎ−１からｎビット目にバンクアドレスを増減した結果を設定し、ｎ−１から０ビット目までにオフセットを増減した結果を設定する。アドレス生成部３０１は、生成した物理アドレスをメモリ１０１へ供給する。
【００４６】
アドレス生成指示信号がワードカウンタ値の加算を指示する信号である場合、アドレス生成部３０１は、バンク内ワードカウンタ４４３からバンク内ワードカウンタ値を読み出す。アドレス生成部３０１は、オフセットを増減した結果と、バンクアドレスを増減した結果と、バンク内ワードカウンタの値とから、メモリ構成定義に基づいて物理アドレスを生成してメモリ１０１へ供給する。
【００４７】
制御部４００は、データ整列装置６００の初期化を指示する初期化信号と、動作モードを指示する信号と、データイネーブルを示す信号と、比較部５００からの比較結果とを受け取る。動作モードは、整列されたデータ列に追加データを挿入するライトモード、または、整列されたデータ列をメモリ１０１から読み出して出力するリードモードとのいずれかの状態をとる。データイネーブルは、追加データを挿入対象として取り込むか否かを示すものである。例えば、追加データが挿入すべきデータとして１つ送信されるたびに、データの挿入処理に要する時間より短い期間だけデータイネーブルがハイレベルに設定される。データ整列装置６００は、データイネーブルの値により、追加データの追加の有無を判断できる。
【００４８】
メモリ構成定義部４１１は、メモリ１０１のメモリ構成を定義するものである。初期化信号がオンの場合、メモリ構成定義部４１１は、下記の式１および式２が満たされるようにバッファを定義する。
【数１】
2012089001.tif 000003
PhyAdr=BnkAdr×2n+mod(WrdAdr+OfsAdr(BnkAdr),2n)・・・式２
【００４９】
上記式１において、「BnkAdr」は、バンクアドレスである。「WrdAdr」は、ワードアドレスである。ワードアドレスは、メモリ１０１の物理アドレス全体に付与された連続的な番号である。「ｎ」は、各論理バンクに格納されるデータの個数を２のべき乗とした場合のべき指数である。「floor()」は、かっこ内を引数として、引数の整数部分を返す関数である。上記式１により、各論理バンクのバンクアドレスが定義される。
【００５０】
上記式２において、「PhyAdr」は、バッファ内の物理アドレスである。「OfsAdr()」は、かっこ内の値を引数として、引数と同じ論理アドレスの論理バンクに対応するオフセットアドレスを返す関数である。ここで、オフセットアドレスの初期値として、論理バンク内で先頭となるワードアドレスが設定される。「mod(d1,d2)」は、「d1」および「d2」を引数として、「d1」を「d2」により除算した剰余を返す関数である。
【００５１】
上記式２の右辺の第１項により、物理アドレスが属する論理バンクが定義される。上記式２の右辺の第２項により、論理バンク内における相対的なアドレスが定義される。この相対的なアドレスは、ワードアドレスにオフセットアドレスを加算した値を、論理バンクの要素数により除算した剰余であるから、論理バンク内においてオフセットアドレスを始点として循環する。各論理バンク内の物理アドレスには、このような相対的なアドレスが付与される。
【００５２】
メモリ構成が定義された後、挿入先バンク特定処理部４２１は、定義されたメモリ構成に基づいてバンクカウンタ４２２を初期化する。具体的には、挿入先バンク特定処理部４２１は、ソートデータ数カウンタ４４２から、整列されたデータの数を読み出す。挿入先バンク特定処理部４２１は、読み出した数を各論理バンクに格納されるデータ数により除算して端数を切り捨てた値を算出し、算出した値をバンクカウンタ４２２の初期値に設定する。初期値の設定後、動作モードがライトモード、かつ、データイネーブルがハイレベルの場合、データ整列装置６００は、データの挿入処理を開始する。挿入先バンク特定処理部４２１は、データの挿入先を探索する処理において、各論理バンクが、追加データを挿入すべき論理バンクかを特定するものである。
【００５３】
挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値に対応する論理バンクの１つ前の論理バンク内の終点のアドレスをアドレス生成部３０１に生成させる。具体的には、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値から１を減算し、オフセットから１を減算し、バンク内ワードカウンタ値を加算しないように指示するアドレス生成指示信号をアドレス生成部３０１へ供給する。このアドレス生成指示信号より、式３および式４により定義される物理アドレスが生成される。
PhrAdr[N-1:n]=BnkCnt-1・・・式３
PhyAdr[n-1:0]=OfsAdr(BnkCnt-1)-1・・・式４
【００５４】
上記式３および式４において「PhyAdr[b1:b2]」は、物理アドレスの「b1」ビット目から、「b2」ビット目までのビット列を返す関数である。「OfsAdr()」の定義は、上記式２における定義と同様である。「BnkCnt」は、バンクカウンタ４２２の値である。また、アドレス生成部３０１は、式４においてオーバーフローを許容して代入を行うものとする。上記式３により、バンクカウンタ４２２の値から１つ減算した値が、物理アドレスのＮ−１ビット目からｎビット目までに設定される。上記式４により、バンクカウンタ４２２の値から１つ減算した値に対応する論理バンク内のオフセットから１つ減算した値が、物理アドレスのｎ−１ビット目から０ビット目までに設定される。この結果、バンクカウンタ４２２の値に対応する論理バンクの１つ前の論理バンク内の終点のアドレスが生成される。
【００５５】
挿入先バンク特定処理部４２１は、アドレス生成指示信号を供給したクロック内に、データの読出しを示すＲ／Ｗ指示信号をメモリ１０１へ供給する。
【００５６】
メモリ１０１は、Ｒ／Ｗ指示信号に従って、生成された物理アドレスからデータを読み出し、比較部５００は、読み出されたデータと追加データとを比較した結果を挿入先バンク特定処理部４２１およびバンク内データ挿入処理部４４１へ供給する。以下、メモリ１０１から読み出されたデータを「比較データ」と称する。
【００５７】
挿入先バンク特定処理部４２１は、比較部５００から比較結果を受け取り、その比較結果に基づいて、バンクカウンタ４２２の値に対応する論理バンクが追加データを挿入すべき論理バンクであるか否かを判断する。具体的には、整列順において追加データが比較データ以降に位置するデータである場合、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値に対応する論理バンクは、挿入すべき論理バンクであると判断する。整列順において追加データが比較データより前に位置するデータである場合、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値に対応する論理バンクは、挿入すべき論理バンクではないと判断する。例えば、整列順が降順とすると、追加データの値が比較データの値より大きい場合、追加データは比較データより前に位置すると判断され、追加データの値が比較データの値以下の場合、追加データは比較データ以降に位置すると判断される。
【００５８】
対応する論理バンクが追加データを挿入すべき論理バンクでないと判断した場合、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を１つ減算して、減算後の値に対応する論理バンクが追加データを挿入すべき論理バンクであるか否かを判断する。挿入先バンク特定処理部４２１は、追加データを挿入すべき論理バンクが未決定またはバンクカウンタ４２２の値が１以上である限り、この判断処理および減算処理を繰り返す。バンクカウンタ４２２の値が０となった場合は、挿入先バンク特定処理部４２１は、そのときのバンクカウンタ４２２の値（すなわち、「０」）に対応する論理バンクを、追加データを挿入すべき論理バンクと判断する。
【００５９】
オフセット管理部４３１は、追加データの挿入により溢れたデータを論理バンク間で移動させるとともに、各論理バンク内のオフセットを管理するものである。対応する論理バンクが追加データを挿入すべき論理バンクでないと判断された場合、オフセット管理部４３１は、バンクカウンタ４２２の値に対応する論理バンク内の終点のアドレスをアドレス生成部３０１に生成させる。具体的には、オフセット管理部４３１は、バンクカウンタ４２２の値を増減せず、オフセットから値を１つ減算し、バンク内ワードカウンタ値を加算しないように指示するアドレス生成指示信号をアドレス生成部３０１へ供給する。このアドレス生成指示信号より、下記の式５および式６により定義される物理アドレスが生成される。
PhrAdr[N-1:n]=BnkCnt・・・式５
PhrAdr[n-1:0]=OfsAdr(BnkCnt)-1・・・式６
【００６０】
上記式５および式６において「PhyAdr[b1:b2]」の定義は、上記式３および式４における定義と同様である。「OfsAdr()」の定義は、上記式２における定義と同様である。「BnkCnt」の定義は、上記式４における定義と同様である。また、アドレス生成部３０１は、式６においてオーバーフローを許容して代入を行うものとする。上記式５により、バンクカウンタ４２２の値が、物理アドレスのＮ−１ビット目からｎビット目までに設定される。上記式６により、バンクカウンタ４２２の値に対応する論理バンク内のオフセットから１つ減算した値が、物理アドレスのｎ−１ビット目から０ビット目までに設定される。この結果、バンクカウンタ４２２の値に対応する論理バンク内の終点のアドレスが生成される。
【００６１】
オフセット管理部４３１は、アドレス生成指示信号を供給したクロック内に、データの書込みを示すＲ／Ｗ指示信号をメモリ１０１へ供給する。
【００６２】
セレクタ４４４は、前のクロックにおいてメモリ１０１から読み出されたデータをメモリ１０１へ供給する。メモリ１０１は、Ｒ／Ｗ指示信号に従って、セレクタ４４４から受け取ったデータを、生成された物理アドレスに書き込む。
【００６３】
オフセット管理部４３１は、比較データを書き込んだ物理アドレスがオフセットアドレスとなるように、オフセットテーブル２０１内のオフセットを更新する。具体的には、オフセット管理部４３１は、バンクカウンタ４２２の値に対応する論理バンクのオフセットを１つ減少させる。
【００６４】
バンク内データ挿入処理部４４１は、論理バンク内に追加データを挿入するものである。メモリ構成が定義された後、バンク内データ挿入処理部４４１は、ソートデータ数カウンタ４４２およびバンク内ワードカウンタ４４３の値を初期化する。ソートデータ数カウンタの値は、挿入開始前に書き込まれているデータの数が初期値として設定される。バンク内ワードカウンタ４４３には、初期値として０が設定される。そして、挿入先バンク特定処理部４２１が対応する論理バンクが追加データを挿入すべき論理バンクであると判断した場合、バンク内データ挿入処理部４４１は、論理バンク内への追加データの挿入を開始する。
【００６５】
バンク内データ挿入処理部４４１は、まず、挿入すべき論理バンク内のデータ数を加算することによりバンク内ワードカウンタ４４３の値を補正する。具体的には、バンク内データ挿入処理部４４１は、下記の式７を使用して、挿入すべき論理バンク内のデータ数を求める。
【数２】
2012089001.tif 000004
【００６６】
上記式７において、「OfsCnt」は、挿入すべき論理バンク内のデータ数である。バンク内データ挿入処理部４４１は、この「OfsCnt」をバンク内ワードカウンタ４４３の保持値に加算することによりバンク内ワードカウンタ４４３の値を補正する。「BnkCnt」の定義は、上記式３における定義と同様である。「SrtCnt[b1:b2]」は、ソートデータ数カウンタ４４２の「b1」ビット目から「b2」ビット目までのビット列を返す関数である。
【００６７】
上記式７に基づき、バンク内データ挿入処理部４４１は、ソートデータ数カウンタ４４２のＮ−１ビット目からｎビット目までのビット列の示す値がバンクカウンタの値に等しいか否かを判断する。比較した値が等しくない場合、挿入すべき論理バンクは、バンクアドレスが最大値未満の論理バンクである。この場合、バンク内データ挿入処理部４４１は、論理バンク内に格納できる最大のデータ数から１を減算した値（すなわち、２ｎ−１）をバンク内ワードカウンタ４４３内部で加算し、補正する。比較した値が等しい場合、挿入すべき論理バンクは、バンクアドレスが最も大きい論理バンクである。この場合、バンク内データ挿入処理部４４１は、ソートデータ数カウンタ４４２のｎ−１ビット目から０ビット目までのビット列の示す値をバンク内ワードカウンタ４４３内部で加算し、補正する。
【００６８】
バンク内データ挿入処理部４４１が、挿入すべき論理バンク内のデータ数を加算することでバンク内ワードカウンタ４４３の値を補正した後について説明する。バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値から１つ減算した値に対応する物理アドレスをアドレス生成部３０１に生成させる。具体的には、バンク内データ挿入処理部４４１は、バンクカウンタ４２２の値を減算せず、オフセットを１つ減算させ、バンク内ワードカウンタ値を加算するように指示するアドレス生成指示信号をアドレス生成部３０１へ供給する。このアドレス生成指示信号より、下記の式８および式９により定義される物理アドレスが生成される。
PhrAdr[N-1:n]=BnkCnt・・・式８
PhrAdr[n-1:0]=OfsAdr(BnkCnt)+WrdCnt-1・・・式９
【００６９】
上記式８および式９において、「PhyAdr[b1:b2]」の定義は、上記式３および式４における定義と同様である。「OfsAdr()」の定義は、式２における定義と同様である。「BnkCnt」の定義は、上記式３における定義と同様である。また、アドレス生成部３０１は、式９においてオーバーフローを許容して代入を行うものとする。上記式８により、バンクカウンタ４２２の値が、物理アドレスのＮ−１ビット目からｎビット目までに設定される。上記式９により、バンクカウンタ４２２の値に対応する論理バンク内のオフセットにバンク内ワードカウンタ４４３の値を加算した値から１つ減算した値が、物理アドレスのｎ−１ビット目から０ビット目までに設定される。この結果、バンク内ワードカウンタ４４３の値から１を減算した値に対応する物理アドレスが生成される。
【００７０】
バンク内データ挿入処理部４４１は、アドレス生成指示信号を供給したクロック内に、データの読出しを示すＲ／Ｗ指示信号をメモリ１０１へ供給する。
【００７１】
メモリ１０１は、Ｒ／Ｗ指示信号に従って、生成された物理アドレスからデータを読み出し、比較部５００は、読み出されたデータと追加データとを比較した結果を挿入先バンク特定処理部４２１およびバンク内データ挿入処理部４４１へ供給する。
【００７２】
バンク内データ挿入処理部４４１は、比較部５００から比較結果を受け取り、その結果に基づいて、バンク内ワードカウンタ４４３の値に対応する物理アドレスは、追加データを挿入すべき物理アドレスであるか否かを判断する。具体的には、整列順において追加データが比較データ以降に位置するデータである場合、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスは、追加データを挿入すべき物理アドレスであると判断する。整列順において追加データが比較データより前に位置するデータである場合、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスは、追加データを挿入すべき物理アドレスでないと判断する。
【００７３】
バンク内ワードカウンタ４４３の値に対応する物理アドレスが追加データを挿入すべき物理アドレスでないと判断した場合、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスをアドレス生成部３０１に生成させる。具体的には、バンク内データ挿入処理部４４１は、バンクカウンタ４２２の値およびオフセットを減算せず、バンク内ワードカウンタ値を加算するように指示するアドレス生成指示信号をアドレス生成部３０１へ供給する。このアドレス生成指示信号より、下記の式１０および式１１により定義される物理アドレスが生成される。
PhrAdr[N-1:n]=BnkCnt・・・式１０
PhrAdr[n-1:0]=OfsAdr(BnkCnt)+WrdCnt・・・式１１
【００７４】
上記式１０および式１１において、「PhyAdr[b1:b2]」の定義は、上記式３および式４における定義と同様である。「OfsAdr()」の定義は、上記式２における定義と同様である。「BnkCnt」の定義は、上記式３における定義と同様である。また、アドレス生成部３０１は、式１１においてオーバーフローを許容して代入を行うものとする。上記式１０により、バンクカウンタ４２２の値が、物理アドレスのＮ−１ビット目からｎビット目までに設定される。上記式１１により、バンクカウンタ４２２の値に対応する論理バンク内のオフセットに、バンク内ワードカウンタ４４３の値を加算した値が、物理アドレスのｎ−１ビット目から０ビット目までに設定される。この結果、バンク内ワードカウンタ４４３の値に対応する物理アドレスが生成される。
【００７５】
バンク内データ挿入処理部４４１は、アドレス生成指示信号を供給したクロック内に、データの書込みを示すＲ／Ｗ指示信号をメモリ１０１へ供給する。
【００７６】
セレクタ４４４は、前のクロックにおいて読み出された比較データを選択してメモリ１０１へ供給する。メモリ１０１は、Ｒ／Ｗ指示信号に従って、セレクタ４４４から受け取ったデータを、生成された物理アドレスに書き込む。
【００７７】
比較データの書込み後、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値を１つ減算して、減算後の値に対応する物理アドレスが追加データを挿入すべき物理アドレスあるか否かを判断する。バンク内データ挿入処理部４４１は、追加データを挿入すべき物理アドレスが未決定またはバンク内ワードカウンタ４４３の値が１以上である限り、これらの減算処理および判断処理を繰り返す。バンク内ワードカウンタ４４３の値が０となった場合は、バンク内データ挿入処理部４４１は、そのときのバンク内ワードカウンタ４４３の値（すなわち、「０」）に対応する物理アドレスを、追加データを挿入すべき物理アドレスであると判断する。
【００７８】
バンク内ワードカウンタ４４３の値に対応する物理アドレスが追加データを挿入すべき物理アドレスであると判断した場合、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスをアドレス生成部３０１に生成させる。具体的には、バンク内データ挿入処理部４４１は、バンクカウンタ４２２の値およびオフセットを減算せず、バンク内ワードカウンタ値を加算するように指示するアドレス生成指示信号をアドレス生成部３０１へ供給する。このアドレス生成指示信号より、上記の式１０および式１１により定義される物理アドレスが生成される。
【００７９】
バンク内データ挿入処理部４４１は、アドレス生成指示信号を供給したクロック内に、データの書込みを示すＲ／Ｗ指示信号をメモリ１０１へ供給するとともにデータ追加指示信号をセレクタ４４４へ供給する。
【００８０】
セレクタ４４４は、データ追加指示信号に従い、追加データを選択してメモリ１０１へ供給する。メモリ１０１は、Ｒ／Ｗ指示信号に従って、セレクタ４４４から受け取ったデータを、生成された物理アドレスに書き込む。
【００８１】
バンク内データ挿入処理部４４１は、追加データの書込みの後、ソートデータ数カウンタ４４２の値を１つ増加させる。そして、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値を０に初期化する。また、データが挿入された後に、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を初期化する。制御部４００は、動作モードがライトモードである限り、データイネーブルがハイレベルとなるたびに、データの挿入処理を繰り返す。
【００８２】
このようにして、データ整列装置６００は、整列順において適切な位置に追加データを挿入する。この結果、バンクアドレスが小さい論理バンクからバンクアドレスが大きい論理バンクへ整列順にデータが配列される。各論理バンク内では、オフセットに対応する物理アドレスに整列順において先頭のデータが格納される。そして、論理バンク内において相対的なアドレスが循環する方向に沿って、整列順にデータが格納される。
【００８３】
動作モードがリードモードであり、かつ、データイネーブルがハイレベルである場合、制御部４００は、整列されたデータを整列順に読み出す。具体的には、制御部４００は、バンクカウンタ４２２およびバンク内ワードカウンタ４４３の値を０に初期化する。そして、制御部４００は、バンクカウンタ４２２の値に対応する論理バンクのオフセットをオフセットテーブル２００から読み出す。制御部４００は、バンクカウンタ４２２の値に対応する論理バンクにおいて、オフセットにバンク内ワードカウンタ４４３を加算した値に対応する物理アドレスをアドレス生成部３０１に生成させる。制御部４００は、アドレス生成指示信号を供給したクロック内に、データの読出しを示すＲ／Ｗ指示信号をメモリ１０１へ供給する。
【００８４】
メモリ１０１は、Ｒ／Ｗ指示信号に従って、生成された物理アドレスからデータを読み出してデータ整列装置６００の外部へ出力する。
【００８５】
制御部４００は、ソートデータ数カウンタ４４２の値を１つ減算し、バンク内ワードカウンタ４４３の値を１つ増加する。制御部４００は、オフセットに増加後のバンク内ワード数カウンタを加えた物理アドレスを生成させ、その物理アドレスから読み出されたデータをメモリ１０１に出力させる。制御部４００は、バンク内ワードカウンタ４４３の値が最大値である２ｎを越えるまで、論理バンク内のデータを繰り返し出力させる。バンク内ワードカウンタ４４３の値が最大値である２ｎを越えた場合、制御部４００は、バンクカウンタ４２２の値を１つ増加させ、バンク内ワードカウンタ４４３の値を０に初期化する。制御部４００は、ソートデータ数カウンタ４４２の値が０になるまで各論理バンク内のデータを繰り返し出力させる。ソートデータ数カウンタ４４２の値が０になった場合、制御部４００は、メモリ１０１にデータの出力を終了させる。
【００８６】
なお、上述の実施の形態のバンクカウンタ４２２は、特許請求の範囲に記載の変数保持部の一例である。
【００８７】
［データ整列装置の動作］
次に、実施の形態におけるデータ整列装置６００の動作について図８乃至図１０を参照して説明する。
【００８８】
図８は、実施の形態におけるデータ整列装置６００の制御手順の一例を示すフローチャートである。この制御手順は、データを整列するためのアプリケーションが実行されたときなどに開始する。メモリ構成定義部４１１は、初期化信号がオンであるか否かを判断する（ステップＳ９０１）。初期化信号がオンでなければ（ステップＳ９０１：Ｎｏ）、メモリ構成定義部４１１は、ステップＳ９０１に戻る。初期化信号がオンであれば（ステップＳ９０１：Ｙｅｓ）、メモリ構成定義部４１１は、メモリ１０１を等分する複数の論理バンクを定義する（ステップＳ９０２）。制御部４００は、ソートデータ数カウンタ４４２、バンクカウンタ４２２、バンク内ワードカウンタ４４３を初期化する（ステップＳ９０３）。制御部４００は、整列済みのデータ列に追加データを挿入するデータ挿入処理を実行し（ステップＳ９２０）、整列済みのデータ列を整列順に出力するソートデータ出力処理を実行する（ステップＳ９８０）。ステップＳ９８０の後、制御部４００は、動作を終了する。
【００８９】
図９は、実施の形態におけるデータ挿入処理の一例を示すフローチャートである。バンク内データ挿入処理部４４１は、動作モードがライトモードであるか否かを判断する（ステップＳ９３０）。動作モードがライトモードであれば（ステップＳ９３０：Ｙｅｓ）、バンク内データ挿入処理４４１は、データイネーブルがオンであるか否かを判断する（ステップＳ９４０）。データイネーブルがオンでなければ（ステップＳ９４０：Ｎｏ）、バンク内データ挿入処理４４１は、ステップＳ９３０に戻る。
【００９０】
データイネーブルがオンであれば（ステップＳ９４０：Ｙｅｓ）、挿入先バンク特定処理部４２１およびオフセット管理部４３１は、挿入先のバンクを探索するための挿入先バンク探索処理を実行する（ステップＳ９５０）。そして、バンク内データ挿入処理部４４１は、探索された論理バンク内に追加データを挿入するバンク内データ挿入処理を実行する（ステップＳ９６０）。ステップＳ９６０の後、バンク内データ挿入処理部４４１は、ステップＳ９３０に戻る。
【００９１】
動作モードがリードモードであれば（ステップＳ９３０：Ｎｏ）、バンク内データ挿入処理部４４１は、データ挿入処理を終了する。
【００９２】
図１０は、実施の形態における挿入先バンク探索処理の一例を示すフローチャートである。
【００９３】
挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値が１以上であるか否かを判断する（ステップＳ９５２）。バンクカウンタ４２２の値が１以上であれば（ステップＳ９５２：Ｙｅｓ）、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を１つ減算した値に対応する論理バンクの最終要素を比較データとしてメモリ１０１から読み出す。ここで、比較データが読み出される物理アドレスは、上記式３および式４により定義される物理アドレスである（ステップＳ９５３）。ステップＳ９５２乃至Ｓ９５３の各処理は、同一のクロックサイクル内に実行されるものとする。
【００９４】
挿入先バンク特定処理部４２１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータであるか否かを判断する（ステップＳ９５４）。
【００９５】
追加データが比較データより前に挿入すべきデータである場合（ステップＳ９５４：Ｙｅｓ）、オフセット管理部４３１は、バンクカウンタ４２２の値に対応する論理バンクの最終要素の位置に比較データを書き込む。ここで、比較データが書き込まれる物理アドレスは、上記式５および式６により定義される物理アドレスである（ステップＳ９５５）。オフセット管理部４３１は、オフセットテーブル２０１において、バンクカウンタ４２２の値に対応する論理バンクのオフセットを１つ減算する（ステップＳ９５６）。
【００９６】
挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を１つ減算する（ステップＳ９５７）。ステップＳ９５７の後、挿入先バンク特定処理部４２１は、ステップＳ９５２に戻る。ステップＳ９５４乃至Ｓ９５７の各処理は、同一のクロックサイクル内に実行されるものとする。
【００９７】
バンクカウンタ４２２の値が０である場合（ステップＳ９５２：Ｎｏ）、または、追加データが比較データより前に挿入すべきデータでない場合（ステップＳ９５４：Ｎｏ）、挿入先バンク特定処理部４２１は、挿入先バンク探索処理を終了する。
【００９８】
図１１は、実施の形態におけるバンク内データ挿入処理の一例を示すフローチャートである。バンク内データ挿入処理部４４１は、上記式７を使用して、バンクカウンタ４２２の値に対応する論理バンク内のデータ数をバンク内ワードカウンタ４４３の保持値に加算することでバンク内ワードカウンタ４４３の値を補正する（ステップＳ９６１）。
【００９９】
バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値が１以上であるか否かを判断する（ステップＳ９６２）。バンク内ワードカウンタ４４３の値が１以上である場合（ステップＳ９６２：Ｙｅｓ）、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３を１つ減算した値に対応する物理アドレスからデータを比較データとして読み出す。ここで、比較データが読み出される物理アドレスは、上記式８および式９により定義される物理アドレスである（ステップＳ９６３）。ステップＳ９６１乃至Ｓ９６３の各処理は、同一のクロックサイクル内に実行されるものとする。
【０１００】
バンク内データ挿入処理部４４１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータであるか否かを判断する（ステップＳ９６４）。
【０１０１】
追加データが比較データより前に挿入すべきデータである場合（ステップＳ９６４：Ｙｅｓ）、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスに比較データを書き込む。ここで、比較データが書き込まれる物理アドレスは、上記式１０および式１１により定義される物理アドレスである（ステップＳ９６５）。バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値を１つ減算し（ステップＳ９６６）、ステップＳ９６２に戻る。ステップＳ９６４乃至Ｓ９６６の各処理は、同一のクロックサイクル内に実行されるものとする。
【０１０２】
バンク内ワードカウンタ４４３の値が０である場合（ステップＳ９６２：Ｎｏ）、または、追加データが比較データより前に挿入すべきデータでない場合（ステップＳ９６４：Ｎｏ）について説明する。この場合、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスに追加データを書き込む。ここで、追加データが書き込まれる物理アドレスは、上記式１０および式１１により定義される物理アドレスである（ステップＳ９６７）。バンク内データ挿入処理部４４１は、ソートデータ数カウンタ４４２の値を１つ増加する（ステップＳ９６８）。挿入先バンク特定処理部４２１は、バンクカウンタ４２２を初期化し、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３を初期化する（ステップＳ９６９）。ステップＳ９６９の後、バンク内データ挿入処理部４４１は、バンク内データ挿入処理を終了する。ステップＳ９６４乃至Ｓ９６９の各処理は、同一のクロックサイクル内に実行されるものとする。
【０１０３】
図１２は、実施の形態におけるソートデータ出力処理の一例を示すフローチャートである。制御部４００は、バンクカウンタ４２２の値を０に初期化する（ステップＳ９８１）。制御部４００は、バンク内ワードカウンタ４４３の値を０に初期化する（ステップＳ９８２）。
【０１０４】
制御部４００は、バンク内ワードカウンタ４４３の値が最大値である２ｎを越えたか否かを判断する（ステップＳ９８３）。バンク内ワードカウンタ４４３の値が最大値を越えたのであれば（ステップＳ９８３：Ｙｅｓ）、制御部４００は、バンクカウンタ４２２の値を１つ増加する（ステップＳ９８４）。ステップＳ９８４の後、制御部４００は、ステップＳ９８２に戻る。
【０１０５】
バンク内ワードカウンタ４４３の値が最大値を越えていなければ（ステップＳ９８３：Ｎｏ）、制御部４００は、ソートデータ数カウンタ４４２の値が０であるか否かを判断する（ステップＳ９８５）。ソートデータ数カウンタ４４２の値が０でなければ（ステップＳ９８５：Ｎｏ）、制御部４００は、バンクカウンタ４２２の値に対応する論理バンク内において、データの読出し先の物理アドレスをアドレス生成部３０１に生成させる。生成させる物理アドレスは、バンクカウンタ４２２の値に対応する論理バンクのオフセットに、バンク内ワードカウンタ４４３の値を加算した値に対応する物理アドレスである。制御部４００は、生成された物理アドレスからデータを読み出す（ステップＳ９８６）。制御部４００は、ソートデータ数カウンタ４４２の値を１つ減算し（ステップＳ９８７）、バンク内ワードカウンタ４４３の値を１つ増加する（ステップＳ９８８）。ステップＳ９８８の後、制御部４００は、ステップＳ９８３に戻る。ソートデータ数カウンタ４４２の値が０であれば（ステップＳ９８５：Ｙｅｓ）、制御部４００は、ソートデータ出力処理を終了する。
【０１０６】
図１３および図１４を参照して、実施の形態におけるデータ整列装置６００の動作結果について説明する。
【０１０７】
図１３は、実施の形態におけるデータ整列装置６００の動作結果の一例を示すタイミングチャートである。この例では、２１０（＝１０２４）ワードのバッファサイズ、２５（＝３２）ワードのバンクサイズがメモリ構成として定義されているものとする。そして、メモリ１０１内のバッファに、整列されたデータが２１０−１（＝１０２３）ワードだけ書き込まれている状態を想定する。また、各論理バンクのオフセットは、全て「０００００」であるものとする。
【０１０８】
追加データの入力前に、挿入先バンク特定処理部４２１は、データ数をバンクサイズにより除算して端数を切り捨てた値にバンクカウンタ４２２を初期化しておく。この例では、２１０−１（＝１０２３）を２５（＝３２）により除算して端数を切り捨てた値である２５−１（＝３１）が初期値として設定される。
【０１０９】
ステップ「Ｔ０」において追加データが入力されると、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を１つ減算した値に対応する論理バンクの最終要素をアドレス生成部３０１に生成させる。バンクカウンタ４２２の値を１つ減算した値は２進表記において「１１１１０」であり、最終要素は、オフセット「０００００」を１つ減算した「１１１１１」に対応するデータである。アドレス生成部３０１は、これらの値に基づき、物理アドレスとして「１１１１０１１１１１」を生成する。挿入先バンク特定処理部４２１は、データの読出しを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスからデータを比較データとして読み出す。
【０１１０】
次のステップ「Ｔ１」において、挿入先バンク特定処理部４２１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータであると判断したものとする。
【０１１１】
オフセット管理部４３１は、バンクカウンタ４２２の値に対応する論理バンクの最終要素に対応する物理アドレスをアドレス生成部３０１に生成させる。バンクカウンタ４２２の値は２進表記において「１１１１１」であり、最終要素は、オフセット「０００００」を１つ減算した「１１１１１」に対応するデータである。アドレス生成部３０１は、これらの値に基づき、物理アドレスとして「１１１１１１１１１１」を生成する。オフセット管理部４３１は、データの書込みを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスに比較データを書き込む。
【０１１２】
オフセット管理部４３１は、バンクカウンタ４２２の値「１１１１１」に対応する論理バンクのオフセット「０００００」を１つ減算して「１１１１１」にする。オフセット管理部４３１は、バンクカウンタ４２２の値「１１１１１」を１つ減算して「１１１１０」にする。
【０１１３】
ステップ「Ｔ２」において挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値を１つ減算した値に対応する論理バンクの最終要素をアドレス生成部３０１に生成させる。バンクカウンタ４２２の値を１つ減算した値は２進表記で「１１１０１」であり、最終要素は、オフセット「０００００」を１つ減算した「１１１１１」に対応するデータである。アドレス生成部３０１は、これらの値に基づき、物理アドレスとして「１１１０１１１１１１」を生成する。挿入先バンク特定処理部４２１は、データの読出しを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスからデータを比較データとして読み出す。
【０１１４】
ステップ「Ｔ３」において、挿入先バンク特定処理部４２１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータでないと判断したものとする。この結果、挿入先の論理バンクは、バンクカウンタ４２２の値「１１１１０」に対応する論理バンクに確定する。
【０１１５】
バンク内データ挿入処理部４４１は、バンクカウンタ４２２の値に対応する論理バンク内のデータ数を加算することでバンク内ワードカウンタ４４３の値を補正する。バンクカウンタ４２２の値「１１１１０」に対応する論理バンク内には、２５−１（＝３１）個のデータが格納されているので、バンク内ワード数カウンタ４４３の値は、「１１１１１」となる。
【０１１６】
バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３を１つ減算した値に対応する物理アドレスをアドレス生成部３０１に生成させる。ここで、バンクカウンタ４２２の値に対応する論理バンクのオフセットは「０００００」である。アドレス生成部３０１は、物理アドレスの上位５ビットに、バンクカウンタ４２２の値「１１１１０」を設定する。そして、アドレス生成部３０１は、バンク内ワードカウンタ４４３を１つ減算した値「１１１１０」にオフセット「０００００」を加算した値を物理アドレスの下位５ビットに設定する。つまり、アドレス生成部３０１は、物理アドレスとして「１１１１０１１１１０」を生成する。バンク内データ挿入処理部４４１は、データの読出しを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスからデータを比較データとして読み出す。
【０１１７】
ステップ「Ｔ４」において、挿入先バンク特定処理部４２１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータであると判断したものとする。
【０１１８】
バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレスをアドレス生成部３０１に生成させる。ここで、バンクカウンタ４２２の値に対応する論理バンクのオフセットは「０００００」である。アドレス生成部３０１は、物理アドレスの上位５ビットにバンクカウンタ４２２の値「１１１１０」を設定する。そして、アドレス生成部３０１は、バンク内ワードカウンタ４４３の値「１１１１１」にオフセット「０００００」を加算した値を物理アドレスの下位５ビットに設定する。つまり、アドレス生成部３０１は、物理アドレスとして「１１１１０１１１１１」を生成する。バンク内データ挿入処理部４４１は、データの書込みを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスに比較データを書き込む。バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値「１１１１１」を1つ減算して「１１１１０」にする。
【０１１９】
ステップ「Ｔ５」において、バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３を１つ減算した値に対応する物理アドレスをアドレス生成部３０１に生成させる。ここで、バンクカウンタ４２２の値に対応する論理バンクのオフセットは「０００００」である。アドレス生成部３０１は、物理アドレスの上位５ビットに、バンクカウンタ４２２の値「１１１１０」を設定する。そして、アドレス生成部３０１は、バンク内ワードカウンタ４４３を１つ減算した値「１１１０１」にオフセット「０００００」を加算した値を物理アドレスの下位５ビットに設定する。つまり、アドレス生成部３０１は、物理アドレスとして「１１１１０１１１０１」を生成する。バンク内データ挿入処理部４４１は、データの読出しを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスからデータを比較データとして読み出す。
【０１２０】
ステップ「Ｔ６」において、バンク内データ挿入処理部４４１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータであると判断したものとする。
【０１２１】
バンク内データ挿入処理部４４１は、ステップ「Ｔ４」のときと同様に、バンク内ワードカウンタ４４３の値に対応する物理アドレスに比較データを書き込む。バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値「１１１１０」を1つ減算して「１１１０１」にする。
【０１２２】
ステップ「Ｔ７」において、バンク内データ挿入処理部４４１は、ステップ「Ｔ５」のときと同様に、バンク内ワードカウンタ４４３を１つ減算した値「１１１００」に対応する物理アドレスから比較データを読み出す。
【０１２３】
ステップ「Ｔ８」において、バンク内データ挿入処理部４４１は、比較部５００の判断結果に基づき、追加データは比較データより前に挿入すべきデータでないと判断したものとする。この結果、挿入先の物理アドレスは、バンク内ワードカウンタ４４３の値「１１１０１」に対応する物理アドレスに確定する。
【０１２４】
バンク内データ挿入処理部４４１は、バンク内ワードカウンタ４４３の値に対応する物理アドレス「１１１１０１１１０１」をアドレス生成部３０１に生成させる。また、バンク内データ挿入処理部４４１は、データ追加指示信号をセレクタ４４４へ供給する。セレクタ４４４は、データ追加指示信号に従って追加データを選択してメモリ１０１へ供給する。バンク内データ挿入処理部４４１は、データの書込みを指示するＲ／Ｗ指示信号をメモリ１０１へ供給することにより、生成された物理アドレスにセレクタ４４４からの追加データを書き込む。
【０１２５】
ステップ「Ｔ９」において、バンク内データ挿入処理部４４１は、バンク内ワードカウンタの値を０に初期化する。そして、バンク内データ挿入処理部４４１は、ソートデータ数カウンタ４４２の値２１０−１（＝１０２３）を１つ加算して２１０（＝１０２４）とする。
【０１２６】
図１４は、実施の形態におけるデータ整列装置６００の動作結果の一例を説明するための図である。図１４の左側の図は、追加データの書込み前のメモリ１０１の構成の一例を示す図である。この例では、図１３で説明した場合と同様に、２１０（＝１０２４）ワードのバッファサイズ、２５（＝３２）ワードのバンクサイズがメモリ構成として定義されている。そして、メモリ１０１内のバッファに、整列されたデータが２１０−１（＝１０２３）ワードだけ書き込まれている。また、各論理バンクのオフセットは、全て「０００００」であるものとする。図１４の斜線部分は、各論理バンク内のオフセットの示す物理アドレスである。
【０１２７】
図１４の右側の図は、図１３と同様の処理が実行された場合における、追加データの挿入後のメモリ１０１の構成の一例を示す図である。図１４の矢印の始点は、データの読出し先の物理アドレスを示し、矢印の終点はデータの書込み先の物理アドレスを示している。図１３のステップ「Ｔ０」において物理アドレス「１１１１０１１１１１」から比較データが読み出される。追加データは比較データより前に挿入すべきデータであったので、ステップ「Ｔ１」において、物理アドレス「１１１１１１１１１１」にデータが書き込まれる。オフセット管理部４３１は、この物理アドレスの位置を示すように、オフセットを更新する。
【０１２８】
ステップ「Ｔ２」において物理アドレス「１１１０１１１１１１」から比較データが読み出されて、比較結果から、バンクアドレス「１１１１０」の論理バンクが挿入先のバンクと判断される。
【０１２９】
ステップ「Ｔ３」において物理アドレス「１１１１０１１１１０」から比較データが読み出される。追加データは比較データより前に挿入すべきデータであったので、ステップ「Ｔ４」において、物理アドレス「１１１１０１１１１１」に比較データが書き込まれる。
【０１３０】
ステップ「Ｔ５」において物理アドレス「１１１１０１１１０１」から比較データが読み出される。比較結果から、追加データは比較データより前に挿入すべきデータであったので、ステップ「Ｔ６」において、物理アドレス「１１１１０１１１１０」に比較データが書き込まれる。
【０１３１】
ステップ「Ｔ７」において、物理アドレス「１１１１０１１１００」から比較データが読み出される。比較結果から、物理アドレス「１１１１０１１１０１」が挿入先の物理アドレスであると判断されたので、ステップ「Ｔ８」において、物理アドレス「１１１１０１１１０１」に追加データが書き込まれる。
【０１３２】
図１５は、実施の形態におけるデータ整列装置６００の論理バンク数の増減に伴うソート処理時間の増減を示すグラフである。同図の縦軸は、下記式１３により得られるデータの挿入に必要なクロックサイクル数であり、横軸は、「バンクサイズ」を２ｎワードとしたときのべき指数ｎである。
【０１３３】
図１０および１１に例示した処理により、データが挿入される場合を想定する。整列されたデータ数をＭ個とした場合に、Ｍ＋１個目のデータを挿入するのに要する処理時間は、最小３クロックサイクルとなる。具体的には、図１０のＳ９５１乃至Ｓ９５３の処理と、図１０のＳ９５４および図１１のＳ９６１乃至Ｓ９６３の処理と、図１１のＳ９６４およびＳ９６７乃至Ｓ９６９の処理とを少なくとも各１回ずつ実行した場合に３クロックサイクルとなる。これに対して、最大のクロックサイクル数は、下記の式１２により算出される。
【数３】
2012089001.tif 000005
【０１３４】
上記式１２における「worst_cycle()」は、かっこ内の値に等しい順番のデータの挿入に要する処理時間を示す。「Ｍ」は、整列されたデータの個数である。「ｎ」は、論理バンク内に格納されるデータ数の最大値を「２ｎ」とした場合のべき指数である。「floor()」の定義は、上記式１における定義と同様である。上記式１２の右辺第１項は、図１０のＳ９５２乃至Ｓ９５３の処理と図１０のＳ９５４乃至Ｓ９５７の処理の実行回数の和を示す。上記式１２の右辺第２項は、図１０のＳ９５４および図１１のＳ９６１乃至Ｓ９６３の処理の実行回数と図１１のＳ９６４乃至Ｓ９６６の処理の実行回数の和を示す。上記式１２の右辺第３項は、図１１のＳ９６４およびＳ９６７乃至Ｓ９６９の処理の実行回数を示す。
【０１３５】
整列するデータ数「Ｍ」が増加するほど、挿入処理の処理時間も増大する。このため、上記式１２の左辺が最大値をとるのは、「バッファサイズ」が２Ｎワードの場合においてＭが最大値「２Ｎ−１」のとき、すなわち、最後の「２Ｎ」個目を挿入するときである。Ｍが「２Ｎ−１」のときの処理時間は、下記の式１３により算出される。
worst_cycle(2N)=2N-n+1+2n+1-3・・・式１３
【０１３６】
図１５の縦軸は、「Ｎ」を「１０」とした場合に上記式１３により算出される値である。上記式１３の値が最小となる「ｎ」について考える。「ｎ」を変数とし、「Ｎ」を固定値として、上記式１３の右辺を微分し、微分した右辺が「０」となる「ｎ」を算出する。この結果、「ｎ」の値として「Ｎ／２」が算出される。図１５においても、Ｎ＝１０として、「ｎ」が「Ｎ／２」すなわち「５」となるとき、処理時間が最小となっている。上記式１３の右辺の「ｎ」に「Ｎ／２」を代入すると、下記式１４が算出される。
【数４】
2012089001.tif 000006
【０１３７】
上記式１４により、「ｎ」を最適値にした場合の、処理時間の最大値が算出される。
【０１３８】
一方、上記式１３の値が最大となるのは「ｎ」が「Ｎ」と等しいとき、すなわち論理バンクが格納するデータ数が２Ｎで論理バンク数が１つのときである。最後の「２ｎ」個目を挿入するときの処理時間は、上記式１３の右辺の「ｎ」に「Ｎ」を代入して得られた下記式１５により算出される。
worst_cycle(2N)=2N+1-1・・・式１５
【０１３９】
図１６は、実施の形態におけるデータ整列装置６００の論理バンク数の増減に伴う回路規模の増減を示すグラフである。同図の縦軸は、挿入ソート法を行う回路を基準としたフリップフロップ数の増加分であり、横軸は、ｎである。
【０１４０】
データ整列装置６００の回路規模の増減の算出において、バッファサイズを論理バンクに区分せずに挿入ソート法を行う回路を基準とする。この基準となる回路は、論理バンク内でなくバッファ全体において、図１１に示したバンク内データ整列処理と同様の処理を行う回路である。この基準となる回路と比較して、データ整列装置６００の回路の増分としては、オフセットテーブル２０１を格納するレジスタと、ソートデータ数カウンタ４４２を実現するフリップフロップが考えられる。バッファサイズを「２Ｎ」ワード、論理バンクのデータサイズを「２ｎ」ワードと想定する。この場合、オフセットテーブル２０１を格納するレジスタは、オフセットのデータサイズ「ｎ」ビットにバンク数「２Ｎ−ｎ」個を乗算した「ｎ×２Ｎ−ｎ」個のフリップフロップにより実現される。ソートデータ数カウンタ４４２は、バッファサイズである「Ｎ」ビット分のフリップフロップにより実現される。従って、フリップフロップの増分は、「ｎ×２Ｎ−ｎ＋Ｎ」個となる。図１６の縦軸は、「ｎ」を変数とし、Ｎ＝１０とした場合のフリップフロップ数の増分である。
【０１４１】
図１６に示すように、「ｎ」を小さくするほど、言い換えれば論理バンクの数を多くするほどフリップフロップ数の増分が大きくなる。一方、図１５に示すように、「ｎ」を「Ｎ／２」に近づけつけるほど、処理時間が小さくなる。「ｎ」の値は、図１６に例示した回路規模の増分と、図１５に例示した処理時間との間のバランスを考慮して、システムの要件を満たすように設定される。
【０１４２】
このように、実施の形態によれば、メモリ１００は、複数の領域を含み、それぞれの領域内には、始点から終点へ循環するようにアドレスが付与される。オフセットテーブル２００は、各論理バンクの始点を特定するオフセットを記憶しておき、挿入先バンク特定部４２０は、オフセットに基づいて論理バンクから読み出したデータと追加データとを比較することによって挿入先の論理バンクを特定する。バンク内データ挿入部４４０は、特定された領域内に追加データを挿入する。オフセット管理部４３０は、追加データの挿入により溢れたデータを論理バンク間で移動させ、移動先のアドレスが始点となるようにオフセットを更新する。
【０１４３】
この構成によれば、バッファが複数の論理バンクに区分されているので、挿入先バンク特定部４２０は、各論理バンク内の１つのデータと追加データを比較することにより、挿入先の論理バンクを特定できる。また、溢れたデータを論理バンク間で移動させても、オフセットの更新により移動先のデータが論理バンク内の始点となり、論理バンク内では、その始点からアドレスが循環する。このため、各論理バンク内ではデータを移動させなくとも整列順が維持される。
【０１４４】
つまり、バッファサイズを論理バンクに区分しない挿入ソート法と比較して、整列された各データと追加データとの比較回数が減少し、データをずらす回数も減少する。一方、比較器を多数設けて回路を並列化する構成ではないため、回路規模はそれほど増大しない。この結果、回路規模の増大を抑制しつつ、ソート処理の処理時間が低減する。
【０１４５】
また、挿入先バンク特定部４２０、オフセット管理部４３０、および、バンク内データ挿入部４４０は、アドレス生成部３００にアクセス先のアドレスを生成させている。この構成によれば、アドレスを生成する回路やプログラムの拡張や保守が容易となる。
【０１４６】
また、メモリ構成定義部４１０がメモリ構成を定義している。この構成によれば、データ整列装置６００は、メモリ構成を一元管理することができる。
【０１４７】
また、メモリ構成定義部４１０は、バッファ内の要素数が２のべき乗となるようにバッファを定義している。このため、バッファ内の物理アドレスをビット演算により求めることが容易となる。
【０１４８】
また、メモリ構成定義部４１０は、論理バンク内の要素数が２のべき乗となるように論理バンクのデータサイズを定義している。このため、論理バンク内の相対的なアドレスをビット演算により求めることが容易となる。
【０１４９】
また、挿入先バンク特定処理部４２１およびバンク内データ挿入処理部４４１が比較部５００にデータの比較をさせ、その比較結果を受け取っている。この構成によれば、データの整列順が降順から昇順などへ変更される場合、比較部５００のみを変更すればよいため、整列順の変更に対して柔軟に対応できる。
【０１５０】
また、データ整列装置６００は、挿入先バンク特定処理部４２１およびバンクカウンタ４２２を備える。バンクカウンタ４２２はバンクアドレスの値を計数し、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値に基づいて、挿入すべき論理バンクを探索している。このため、バンクアドレスを計数する処理を挿入先バンク特定処理部４２１が実行しなくて済み、挿入先バンク特定処理部４２１を実現する回路やプログラムの実装が容易となる。
【０１５１】
また、オフセット管理部４３０は、挿入先バンク特定部４２０が論理バンク内の終点のアドレスから読み出したデータを、その論理バンクの次の論理バンク内の終点となるアドレスへ書き込んでいる。このため、オフセット管理部４３０は、終点のアドレスを生成するという容易な手順により、移動先のアドレスを決定することができる。
【０１５２】
また、挿入先バンク特定部４２０は、論理バンク内の終点となるアドレスから読み出したデータと追加データとを比較し、その比較結果に基づいて、論理バンクが追加データを挿入すべき領域であるか否かを判断している。このため、挿入先バンク特定部４２０は、各論理バンクの最大値または最小値を読み出して、追加データの値と比較することができ、効率よく論理バンクを探索できる。
【０１５３】
なお、上述の実施の形態では、メモリ構成定義部４１０においてメモリ構成を一元管理する構成としている。しかし、メモリ構成定義部４１０を設けず、挿入先バンク特定部４２０、オフセット管理部４３０、バンク内データ挿入部４４０、および、アドレス生成部３００のそれぞれがメモリ構成を保持する構成としてもよい。
【０１５４】
上述の実施の形態では、挿入先バンク特定部４２０、オフセット管理部４３０、および、バンク内データ挿入部４４０は、アドレス生成部３００を共有する構成としている。しかし、アドレス生成部３００を設けず、オフセット管理部４３０、および、バンク内データ挿入部４４０のそれぞれが自身で物理アドレスを生成してメモリ１００にアクセスする構成としてもよい。
【０１５５】
上述の実施の形態では、データ整列装置６００は、バッファ内の要素数を２のべき乗としているが、要素数を２のべき乗以外としてもよいのは勿論である。
【０１５６】
また、上述の実施の形態では、データ整列装置６００は、論理バンク内の要素数を２のべき乗としているが、バッファを等分できるのであれば、要素数を２のべき乗以外としてもよいのは勿論である。
【０１５７】
また、上述の実施の形態では、データ整列装置６００は、バンクカウンタ４２２を備える構成としているが、バンクカウンタ４２２を設けない構成としてもよい。例えば、挿入先バンク特定処理部４２１が、バンクアドレスのカウントをコンピュータプログラムの実行により行う構成としてもよい。
【０１５８】
また、上述の実施の形態では、データ整列装置６００は、論理バンク内において、挿入ソート法を使用してデータを挿入している。しかし、整列順が維持されるようにデータを挿入できるのであれば、データ整列装置６００は、挿入ソート法以外の方法を使用することができる。例えば、データ整列装置６００は、論理バンク内において、挿入ソート法の改良である二分挿入ソート法やシェルソート法を使用してもよい。
【０１５９】
また、上述の実施の形態では、データ整列装置６００は、データのデータサイズの単位を１ワードとしていたが、単位を１ワード以外としてもよいのは勿論である。
【０１６０】
また、上述の実施形態では、バンクカウンタ４２２はバンクアドレスを保持し、挿入先バンク特定処理部４２１は、バンクカウンタ４２２の値に基づいて挿入先のバンクを探索する構成としている。しかし、バンクカウンタ４２２の保持する値は、追加データを挿入すべきか否かを判断する領域を示す変数であれば、バンクアドレス以外の値であってもよい。例えば、バンクカウンタ４２２は、挿入先バンク特定処理部４２１が挿入先の論理バンクであるか否かを判断した回数を計数してもよい。
【０１６１】
＜２．本発明の変形例＞
［データ整列装置の構成例］
図１７は、実施の形態におけるデータ整列装置６００の変形例を示すブロック図である。変形例のデータ整列装置６０１の構成は、メモリ１０１および制御部４００の代わりにメモリ１０２および制御部４０１を備え、比較部５００を備えない点において、実施の形態のデータ整列装置６００と異なる。制御部４０１は、挿入先バンク特定処理部４２１およびバンク内データ挿入処理部４４１の代わりに挿入先バンク特定処理部４２５およびバンク内データ挿入処理部４４５を備える点において制御部４００と異なる。
【０１６２】
メモリ１０２は、比較部５００でなく、挿入先バンク特定処理部４２５およびバンク内データ挿入処理部４４５へ追加データを供給する点において、メモリ１０１と異なる。
【０１６３】
挿入先バンク特定処理部４２５は、比較部５００から比較結果を受け取るのでなく、比較データと追加データとを自身が比較する点において、挿入先バンク特定処理部４２１と異なる。
【０１６４】
バンク内データ挿入処理部４４５は、比較部５００から比較結果を受け取るのでなく、比較データと追加データとを自身が比較する点において、バンク内データ挿入処理部４４１と異なる。
【０１６５】
この構成によれば、比較部５００を備えないので、比較部５００を備える構成と比較して回路規模を小さくできる。
【０１６６】
なお、実施の形態は本発明を具現化するための一例を示したものであり、実施の形態において明示したように、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１６７】
また、実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０１６８】
１００、１０１、１０２  メモリ
２００、２０１  オフセットテーブル
３００、３０１  アドレス生成部
４００、４０１  制御部
４１０、４１１  メモリ構成定義部
４２０  挿入先バンク特定部
４２１、４２５  挿入先バンク特定処理部
４２２  バンクカウンタ
４３０、４３１  オフセット管理部
４４０  バンク内データ挿入部
４４１、４４５  バンク内データ挿入処理部
４４２  ソートデータ数カウンタ
４４３  バンク内ワードカウンタ
４４４  セレクタ
５００  比較部
６００、６０１  データ整列装置
【図１】
2012089001.tif 000007
【図２】
2012089001.tif 000008
【図３】
2012089001.tif 000009
【図４】
2012089001.tif 000010
【図５】
2012089001.tif 000011
【図６】
2012089001.tif 000012
【図７】
2012089001.tif 000013
【図８】
2012089001.tif 000014
【図９】
2012089001.tif 000015
【図１０】
2012089001.tif 000016
【図１１】
2012089001.tif 000017
【図１２】
2012089001.tif 000018
【図１３】
2012089001.tif 000019
【図１４】
2012089001.tif 000020
【図１５】
2012089001.tif 000021
【図１６】
2012089001.tif 000022
【図１７】
2012089001.tif 000023