(57)【要約】  ブロックアクセス機能を有するメモリ装置に対してデータの書き込みを制御するメモリ制御装置であって、前記メモリ装置に配列データを書き込むとき、前記配列データをソートする複数のソートバッファを有する。前記ソートバッファにソートされた前記配列データを、前記メモリ装置に対して、前記ブロックアクセス機能を用いて書き込む。これにより、配列データの書き込みをより一層高速化することができる。
2017179176.tif 000002
【特許請求の範囲】
【請求項１】
ブロックアクセス機能を有するメモリ装置に対してデータの書き込みを制御するメモリ制御装置であって、
前記メモリ装置に配列データを書き込むとき、前記配列データをソートする複数のソートバッファを有し、
前記ソートバッファにソートされた前記配列データを、前記メモリ装置に対して、前記ブロックアクセス機能を用いて書き込む、
ことを特徴とするメモリ制御装置。
【請求項２】
前記ソートバッファに対する前記配列データのソートを、基数ソートを用いて行う、
ことを特徴とする請求項１に記載のメモリ制御装置。
【請求項３】
前記ソートバッファにソートされた前記配列データに基づいて、前記ソートバッファ上にブロック単位のデータ内容を作成し、前記ブロックアクセス機能を用いて前記メモリ装置に書き込む、
ことを特徴とする請求項２に記載のメモリ制御装置。
【請求項４】
さらに、
前記ソートバッファの容量を超えたデータを、ブロックアクセス機能を用いて退避させる退避メモリ装置を有する、
ことを特徴とする請求項１乃至請求項３のいずれか１項に記載のメモリ制御装置。
【請求項５】
さらに、
前記ソートバッファと前記メモリ装置の間に設けられ、前記ソートバッファにソートされた前記配列データを保持し、前記メモリ装置に対して、前記ブロックアクセス機能を用いて纏めて書き込むための書き込みバッファを有する、
ことを特徴とする請求項１乃至請求項４のいずれか１項に記載のメモリ制御装置。
【請求項６】
前記書き込みバッファは、前記メモリ装置に設けられたレジスタを使用する、
ことを特徴とする請求項５に記載のメモリ制御装置。
【請求項７】
前記メモリ装置に書き込む前記配列データの容量が所定の閾値以上のときは、前記メモリ装置に対して前記ブロックアクセスにより書き込みを行い、
前記メモリ装置に書き込む前記配列データの容量が所定の閾値よりも小さいときは、前記メモリ装置に対してランダムアクセスによりで書き込みを行う、
ことを特徴とする請求項１乃至請求項６のいずれか１項に記載のメモリ制御装置。
【請求項８】
前記メモリ装置は、ＤＲＡＭ，フラッシュメモリまたはハードディスクを含む、
ことを特徴とする請求項１乃至請求項７のいずれか１項に記載のメモリ制御装置。
【請求項９】
ブロックアクセス機能を有するメモリ装置に対してデータの書き込みを制御するメモリ制御方法であって、
前記メモリ装置に配列データを書き込むとき、前記配列データを複数のソートバッファにソートし、
前記ソートバッファにソートされた前記配列データを、前記メモリ装置に対して、前記ブロックアクセス機能を用いて書き込む、
ことを特徴とするメモリ制御方法。
【請求項１０】
前記ソートバッファに対する前記配列データのソートを、基数ソートを用いて行う、
ことを特徴とする請求項９に記載のメモリ制御方法。
【請求項１１】
前記ソートバッファにソートされた前記配列データに基づいて、前記ソートバッファ上にブロック単位のデータ内容を作成し、前記ブロックアクセス機能を用いて前記メモリ装置に書き込む、
ことを特徴とする請求項１０に記載のメモリ制御方法。
【請求項１２】
さらに、
前記ソートバッファの容量を超えたデータを、ブロックアクセス機能を用いて退避メモリ装置に退避させる、
ことを特徴とする請求項９乃至請求項１１のいずれか１項に記載のメモリ制御方法。
【請求項１３】
容量を超えた前記ソートバッファに空きができたら、前記退避メモリ装置に退避されたデータを、ブロックアクセス機能を用いて回復させる、
ことを特徴とする請求項１２に記載のメモリ制御方法。
【請求項１４】
前記メモリ装置に書き込む前記配列データの容量が所定の閾値以上のときは、前記メモリ装置に対して前記ブロックアクセスにより書き込みを行い、
前記メモリ装置に書き込む前記配列データの容量が所定の閾値よりも小さいときは、前記メモリ装置に対してランダムアクセスによりで書き込みを行う、
ことを特徴とする請求項１０乃至請求項１３のいずれか１項に記載のメモリ制御方法。
【請求項１５】
前記メモリ装置は、ＤＲＡＭ，フラッシュメモリまたはハードディスクを含む、
ことを特徴とする請求項１０乃至請求項１４のいずれか１項に記載のメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願で言及する実施例は、メモリ制御装置およびメモリ制御方法に関する。
【背景技術】
【０００２】
近年、ＨＰＣ(High-Performance Computing)等の大規模配列データ(配列データ)を用いるアプリケーションは、例えば、有限要素法，電磁場解析および流体解析等に利用されている。このような配列データを用いるアプリケーションは、例えば、アクセラレータとしてハードウェア化することで、より一層の高速化が可能なものと考えられている。【０００３】
例えば、数千万要素を対象とする有限要素法アプリケーションでは、配列データをメモリ装置(素子)に保持して計算を行うが、ハードウェアアクセラレータにより高速化する場合、配列データの読み出しおよび書き込みが性能を左右する大きな要因になっている。【０００４】
ところで、従来、配列データ(大規模配列データ)の書き込みを高速に行うものとしては、例えば、ライトコンバイン(Write Combine)や疎行列・タイリング(ブロック対角化：Block-Diagonal Matrix))といった手法を始めとして様々な提案がなされている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１０／０３５４２６号公報
【特許文献２】特開２０１４−０９３０３０号公報
【特許文献３】特表２００７−０３４４３１号公報
【非特許文献】
【０００６】
【非特許文献１】P. Burovskiy et al., "Efficient Assembly for High Order Unstructured FEM Meshes," in Field Programmable Logic and Applications (FPL), 2015 25th International Conference on. IEEE, 2015, pp.1-6, September 2, 2015
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように、配列データの書き込みを高速に行うものとして、例えば、ライトコンバインや疎行列・タイリングといった手法が提案されている。【０００８】
ここで、ライトコンバインは、書き込むべきデータを直ちにメモリ装置に書き込まないで一旦溜めておき、次に、書き込みデータが来たとき、先の書き込みデータとアドレスが隣同士ならば、データを併合(コンバイン)して纏めてメモリ装置に書き込む。しかしながら、このライトコンバインは、配列データが大規模になるほど、コンバインの確率が減るといった問題がある。【０００９】
また、疎行列・タイリングは、行列計算において、非０係数のみを纏めて保持するデータ表現方法であり、例えば、有限要素法で用いる剛性マトリクスのランダムアクセスについて、データの読み込み処理には効果的なものである。しかしながら、非０係数を纏めた配列自体が密行列になってしまうため、例えば、ランダムアクセス的な書き込みには向いていない。【００１０】
この出願で言及する実施例は、配列データの書き込みをより一層高速化することができるメモリ制御装置およびメモリ制御方法の提供を目的とする。
【課題を解決するための手段】
【００１１】
一実施形態によれば、ブロックアクセス機能を有するメモリ装置に対してデータの書き込みを制御するメモリ制御装置であって、複数のソートバッファを有するメモリ制御装置が提供される。【００１２】
複数の前記ソートバッファは、前記メモリ装置に配列データを書き込むとき、前記配列データをソートする。そして、前記ソートバッファにソートされた前記配列データを、前記メモリ装置に対して、前記ブロックアクセス機能を用いて書き込む。
【発明の効果】
【００１３】
開示のメモリ制御装置およびメモリ制御方法は、配列データの書き込みをより一層高速化することができるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、有限要素法アプリケーションにおける三角形要素分割による処理の一例を説明するための図である。
【図２】図２は、メモリ装置の一例を模式的に示す図である。
【図３】図３は、図２に示すメモリ装置における課題を説明するための図である。
【図４】図４は、一実施形態に係るメモリ制御装置を模式的に示す図である。
【図５】図５は、メモリ制御装置の一実施例を説明するための図である。
【図６】図６は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図(その１)である。
【図７】図７は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図(その２)である。
【図８】図８は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図(その３)である。
【図９】図９は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図(その４)である。
【図１０】図１０は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図(その５)である。
【図１１】図１１は、図５に示す一実施例のメモリ制御装置における振り分け処理の一例を説明するための図である。
【図１２】図１２は、一実施例のメモリ制御装置による効果を説明するための図で(その１)ある。
【図１３】図１３は、一実施例のメモリ制御装置による効果を説明するための図で(その２)ある。
【発明を実施するための形態】
【００１５】
まず、メモリ制御装置およびメモリ制御方法の実施例を詳述する前に、図１〜図３を参照して、有限要素法アプリケーションの一例、メモリ装置の一例およびその課題を説明する。
【００１６】
図１は、有限要素法アプリケーションにおける三角形要素分割による処理の一例を説明するための図である。前述したように、例えば、数千万要素を対象とする有限要素法アプリケーションでは、配列データ(大規模配列データ)をメモリ装置に保持して計算を行う。ここで、アクセラレータ(ハードウェアアクセラレータ)により高速化する場合、配列データの読み出しおよび書き込みが性能を左右する大きな要因になっている。
【００１７】
ここで、有限要素法では、個々の要素に定義される要素剛性マトリクスに基づいて、全体剛性マトリクスを構築する。具体的に、図１に示されるように、三角形要素分割の場合、節点ｊに対応する全体剛性マトリクスの係数は、隣接する要素(1)〜(6)の要素剛性マトリクスの係数の合計値になる。
【００１８】
すなわち、要素剛性マトリクスを構築する度に全体剛性マトリクスの係数を順次更新すると、１つの節点(ｊ)の係数のために、都合６回の書き込みが生じる。また、例えば、非線形有限要素法の場合、繰り返し全体剛性マトリクスの係数を更新することになるため、書き込み時間の短縮は、重要なものとなっている。
【００１９】
図２は、メモリ装置の一例を模式的に示す図である。図２に示されるように、メモリ装置１は、レジスタ１１およびメモリセル１２を含む。メモリ装置１は、例えば、ＤＲＡＭ(Dynamic Random Access Memory(例えば、ＳＤＲＡＭ：Synchronous DRAM))やフラッシュメモリ(Flash Memory)、或いは、ハードディスク(ハードディスクドライブ)といった大容量の記憶装置である。
【００２０】
メモリ装置１において、例えば、メモリセル１２からレジスタ１１に対してブロック単位でデータをコピーし、さらに、レジスタ１１を介してバス幅に合わせたデータを外部(演算回路２等)と遣り取りする。また、メモリ装置１において、演算回路２等からのデータは、レジスタ１１を介してメモリセル１２に書き込まれる。
【００２１】
ここで、例えば、ＤＲＡＭ，フラッシュメモリおよびハードディスクといった大容量の記憶装置(メモリ装置１)は、ブロック単位でデータの読み出しおよび書き込みを行うブロックアクセス機能を有している。なお、ブロックアクセス機能を有するメモリ装置１において、例えば、メモリセル１２の連続するアドレスに対するブロックアクセスは、ランダムアクセスよりもスループットが非常に高い。
【００２２】
具体的に、メモリ装置１の仕様が、例えば、６４バイト幅，ランダムアクセスのレイテンシが１６μｓ，ブロックアクセスのスループットが４ＧＢ／ｓのＤＤＲ ＳＤＲＡＭ(Double-Data-Rate SDRAM)を考える。
【００２３】
メモリ装置１を完全なランダムアクセスした場合のスループットが、ランダムアクセスのスループット＝６４バイト／１６μｓ＝４ＭＢ／ｓのとき、ブロックアクセス(４ＧＢ／ｓ)は、ランダムアクセスに対して、スループットが１０００倍高いことになる。
【００２４】
図３は、図２に示すメモリ装置における課題を説明するための図である。ここで、演算回路２は、例えば、大規模配列データ(配列データ)をＤＲＡＭやフラッシュメモリのようなメモリ装置１に書き込むアプリケーションを実行しているものとする。
【００２５】
アプリケーションからメモリ装置１に格納された配列データ１０に対するアクセスは、アプリケーションが持つアルゴリズムによって自由な順序で行われる。また、例えば、演算回路２が並列化されている場合、配列データ１０における配列の異なる要素に対する同時アクセスも生じ得る。
【００２６】
これをメモリ装置１から見ると、大量のランダムアクセス的な書き込みが生じることになり、アプリケーションとしての性能が劣化する原因となる。例えば、前述した有限要素法のアプリケーションにおける全体剛性マトリクスの構築は、要素剛性マトリクス毎の係数更新でランダムアクセスを行うため、性能劣化の原因となっている。
【００２７】
また、前述したように、ライトコンバインや疎行列・タイリングといった手法により、配列データの書き込みを高速に行うものも提案されているが、ライトコンバインは、配列データが大規模になるほど、コンバインの確率が減るといった問題がある。また、疎行列・タイリングは、非０係数を纏めた配列自体が密行列になってしまうため、例えば、ランダムアクセス的な書き込みには向いていない。
【００２８】
以下、メモリ制御装置およびメモリ制御方法の実施例を、添付図面を参照して詳述する。図４は、一実施形態に係るメモリ制御装置を模式的に示す図である。図４に示されるように、本実施形態のメモリ制御装置３は、例えば、ＤＲＡＭ等の大容量メモリであるメモリ装置１に対する演算回路２(アプリケーション)からのデータ(書き込みデータ)の書き込みを制御する。
【００２９】
メモリ制御装置３は、例えば、ソートバッファ３０を有する書き込みソート回路３１、ＤＲＡＭ等の退避メモリ装置３２、および、書き込みバッファ１１'を含む。ここで、書き込みバッファ１１'としては、専用のバッファを設けずに、例えば、図２を参照して説明したメモリ装置１におけるレジスタ１１を使用することもできる。また、メモリ装置１は、ブロックアクセス機能を有している。
【００３０】
図４に示されるように、メモリ制御装置３(書き込みソート回路３１)は、複数の書き込みデータ(配列データ)を入力として受け取り、書き込みバッファ１１'を経由して、ブロックアクセス機能を利用してメモリ装置１に書き込む。なお、メモリ制御装置３は、例えば、ブロックアクセス機能を有するＤＭＡ(Direct Memory Access)回路を含んでもよい。
【００３１】
ここで、配列データは、例えば、配列要素のインデクスとその要素に書き込む値の組(Index，Value)で表すことができる。また、書き込みソート回路３１は、複数のソートバッファ３０を有し、例えば、ソートバッファ３０の内容を退避させるための退避メモリ装置３２に接続されている。すなわち、退避メモリ装置３２は、ソートバッファ３０に格納されたデータを一時的に退避させるためのものである。
【００３２】
さらに、書き込みバッファ１１'は、ソートバッファ３０からの配列データ(書き込みデータ)を受け取り、例えば、メモリ装置１における配列データ１０の書き換え(書き込み)を行う。なお、メモリ装置１としては、例えば、ブロックアクセス機能を有するＤＲＡＭ(例えば、ＳＤＲＡＭ)，フラッシュメモリまたはハードディスク等を適用できる。
【００３３】
また、退避メモリ装置３２としては、例えば、書き込みソート回路３１が受け取るデータよりも大きな容量(記憶容量)を有するＤＲＡＭ等を適用することができる。ここで、上述した書き込みソート回路３１は、１つに限定されるものではなく、複数(例えば、４個，８個)設けることができるのはいうまでもない。
【００３４】
このように、本実施形態のメモリ制御装置は、ブロックアクセス機能を有するメモリ装置１に対して配列データ(書き込みデータ)を書き込むとき、配列データを複数のソートバッファ３０にソートする。さらに、ソートバッファ３０にソートされた配列データを、メモリ装置１に対して、ブロックアクセス機能を用いて書き込む。これにより、メモリ装置１に対する配列データの書き込みを、ブロックアクセス機能を用いて一括して行い、より一層高速化することが可能になる。
【００３５】
図５は、メモリ制御装置の一実施例を説明するための図であり、図６〜図１０は、図５に示す一実施例のメモリ制御装置におけるアルゴリズム動作の一例を説明するための図である。ここで、例えば、演算回路２等からの書き込みデータ(配列データ)は、ブロックサイズＭ＝１６要素、配列データの要素数Ｎ＝１２８として説明する。
【００３６】
図５に示されるように、一実施例のメモリ制御装置において、動作順序は、全配列データの入力(処理［Ｐ１］)、配列データの基数ソート(処理［Ｐ２］〜処理［Ｐ４］)、および、配列データの更新(処理［Ｐ５］)となる。
【００３７】
ここで、処理Ｐ１〜処理Ｐ５は、それぞれ図６〜図１０を参照して説明する。なお、前述した図４との比較から明らかなように、図５並びに図６〜図１０において、退避メモリ装置３２は省略されている。また、書き込みバッファ１１'は、専用のバッファを設けずに、メモリ装置１におけるレジスタ１１を使用してもよいのは、前述した通りである。
【００３８】
まず、図６に示されるように、全配列データの入力処理［Ｐ１］において、書き込みソート回路３１は、全ての配列データ(書き込みデータ)を受け取って、基数ソートの０段目ソートバッファ(バッファ)３０aに格納する。なお、本例において、配列データは、１２個(ここで、図６のバッファ３０aにおける数字74，4，110，120，41，…は、書き込み先の配列データのインデクス(Index)を表す)となっている。
【００３９】
次に、図７に示されるように、配列データの基数ソート処理［Ｐ２］において、０段目バッファ３０aに格納されたデータを順次読み込んで、例えば、Indexが６４以上(Index≧６４)か否(Index＜６４)かで、１段目バッファ３０b1または３０b2に振り分ける。具体的に、図７の例では、６４≦Indexの６個の配列データ(Index 74，110，120，73，100，80)がバッファ３０b1に格納され、Index＜６４の６個の配列データ(Index 4，41，62，10，19，39)がバッファ３０b2に格納される。
【００４０】
さらに、図８に示されるように、配列データの基数ソート処理［Ｐ３］において、１段目バッファ３０b1に格納されたデータを順次読み込んで、例えば、インデックスが９６以上か否かで、２段目バッファ３０c1または３０c2に振り分ける。また、１段目バッファ３０b2に格納されたデータを順次読み込んで、例えば、インデックスが３２以上か否かで、２段目バッファ３０c3または３０c4に振り分ける。
【００４１】
具体的に、図８の例では、９６≦Indexの３個の配列データ(Index 110，120，100)がバッファ３０c1に格納され、６４≦Index＜９６の３個の配列データ(Index 74，73，80)がバッファ３０c2に格納される。また、３２≦Index＜６４の３個の配列データ(Index 41，62，39)がバッファ３０c3に格納され、Index＜３２の３個の配列データ(Index 4，10，19)がバッファ３０c4に格納される。
【００４２】
さらに、図９に示されるように、配列データの基数ソート処理［Ｐ４］において、２段目バッファ３０c1に格納されたデータを順次読み込んで、例えば、インデックスが１１２以上か否かで、３段目バッファ３０d1または３０d2に振り分ける。また、２段目バッファ３０c2に格納されたデータを順次読み込んで、例えば、インデックスが８０以上か否かで、３段目バッファ３０d3または３０d4に振り分ける。
【００４３】
さらに、２段目バッファ３０c3に格納されたデータを順次読み込んで、例えば、インデックスが４８以上か否かで、３段目バッファ３０d5または３０d6に振り分ける。また、２段目バッファ３０c4に格納されたデータを順次読み込んで、例えば、インデックスが１６以上か否かで、３段目バッファ３０d7または３０d8に振り分ける。なお、本例において、例えば、ｌｏｇ2(Ｎ／Ｍ)＝ｌｏｇ2(１２８／１６)＝３より、基数ソートは、３段目の処理［Ｐ４］で終了する。
【００４４】
具体的に、図９の例では、１１２≦Indexの１個の配列データ(Index 120)がバッファ３０d1に格納され、９６≦Index＜１１２の２個の配列データ(Index 110，100)がバッファ３０d2に格納される。また、８０≦Index＜９６の１個の配列データ(Index 80)がバッファ３０d3に格納され、６４≦Index＜８０の２個の配列データ(Index 74，73)がバッファ３０d4に格納される。
【００４５】
さらに、４８≦Index＜６４の１個の配列データ(Index 62)がバッファ３０d5に格納され、３２≦Index＜４８の２個の配列データ(Index 41，39)がバッファ３０d6に格納される。そして、１６≦Index＜３２の１個の配列データ(Index 19)がバッファ３０d7に格納され、Index＜１６の２個の配列データ(Index 4，10)がバッファ３０d8に格納される。
【００４６】
そして、図１０に示されるように、配列データの更新処理［Ｐ５］において、３段目のソートバッファ３０d(３０d1〜３０d8)内の配列データを、書き込みバッファ１１'(１１１〜１１８)に反映させる。すなわち、バッファ３０d1〜３０d8にソートされた配列データ(書き込みデータ)は、書き込みバッファ(レジスタ)１１１〜１１８を介し、ブロックアクセス機能を使用して、メモリ装置１の配列データ１０が一括して書き換えられる。
【００４７】
なお、例えば、同じインデクスに対して複数の配列データがあれば、ここで処理する。例えば、配列更新の方式が上書きモードならば、何れか１つの書き込み値を選び、また、積算モードならば、全ての書き込み値の合計を求めるといった処理が行われる。
【００４８】
図１１は、図５に示す一実施例のメモリ制御装置における振り分け処理の一例を説明するための図である。図１１および前述した図４に示されるように、一実施例のメモリ制御装置３は、書き込みソート回路３１および退避メモリ装置３２を含む。
【００４９】
なお、図１１は、基数ソートにおいて、例えば、１つのバッファ(ソートバッファ)から２つのバッファに振り分ける場合の処理を示す。これは、例えば、図７を参照して説明した処理［Ｐ２］において、１つの０段目バッファ(入力ソートバッファ)３０aに格納されたデータを、２つの１段目バッファ(出力ソートバッファ)３０b1，３０b2に振り分ける場合に相当する。このとき、閾値Ｌは、インデックス６４になる。
【００５０】
また、図８を参照して説明した処理［Ｐ３］において、１つの１段目バッファ３０b1に格納されたデータを２つの２段目バッファ３０c1，３０c2に振り分ける場合に相当し、このとき、閾値Ｌは、インデックス９６になる。さらに、処理［Ｐ３］において、１つの１段目バッファ３０b2に格納されたデータを２つの２段目バッファ３０c3，３０c4に振り分ける場合に相当し、このとき、閾値Ｌは、インデックス３２になる。これは、図９を参照して説明した処理［Ｐ４］においても同様である。
【００５１】
このように、基数ソートにおいて、１つの入力ソートバッファ(例えば、３０a)から書き込みデータ(配列データ)を取り出し、インデックスがＬ(例えば、６４)以上か否かにより、２つの出力ソートバッファ(例えば、３０b1，３０b2)のどちらかに格納する。
【００５２】
ここで、データ量がバッファの容量を超える場合、例えば、図１１におけるＰ21，Ｐ22に示されるように、その超えたデータを退避ブロックとしてリスト化して退避メモリ装置３２に退避させる。なお、退避メモリ装置３２としては、例えば、ＤＲＡＭ(ＳＤＲＡＭ)を適用することができる。
【００５３】
そして、例えば、バッファ３０aに空きができたら(例えば、バッファ３０aが空になったら)、リストを辿って退避ブロックを退避メモリ装置３２から読み出し、バッファ３０aに対してブロックアクセスにより回復(補充：図１１におけるＰ２０)する。このように、書き込みソート回路３１は、データの振り分け回路としての機能も有し、例えば、出力ソートバッファ(３０b1，３０b2)が満杯になったら、溢れたデータを退避メモリ装置３２に対してブロックアクセスにより退避させ、リストに挿入する。
【００５４】
このように、メモリ装置１に格納された配列データ１０の更新は、同一ブロック内の複数要素を、ブロックアクセス機能を用いて行う(書き込む)ことができるため、ランダムアクセスの場合よりも大幅に時間を短縮することが可能となる。なお、例えば、メモリ装置１に書き込む配列データの容量が所定の閾値以上のときは、メモリ装置１に対して上述したブロックアクセスにより書き込みを行い、所定の閾値よりも小さいときは、ランダムアクセスによりで書き込みを行うことも可能である。
【００５５】
また、基数ソートの各段のバッファに対する振り分け処理は、例えば、図５〜図１０を参照して説明した例の場合、３つのソートバッファ、すなわち、１つの入力ソートバッファおよび２つの出力ソートバッファにより実行できる。さらに、例えば、ソートバッファ(バッファ)をＦＩＦＯ(First In First Out)レジスタで形成し、ＦＩＦＯレジスタから溢れたデータを退避メモリ装置３２に退避することで、データ数の制限は実質的に無いことになる。また、退避メモリ装置３２に対するデータの退避(回復)にブロックアクセスを用いることにより、後に詳述するように、基数ソートに要する時間が問題となることはない。
【００５６】
図１２および図１３は、一実施例のメモリ制御装置による効果を説明するための図である。図１２に示されるように、例えば、図５〜図１０を参照して説明した例の場合、ブロックアクセスは、基数ソートの各段での書き込みデータ(配列データ)の退避および回復と、書き込みバッファ１１'からメモリ装置１の配列データ１０への書き込みとなる。
【００５７】
ここで、ランダムアクセスおよびブロックアクセスのスループットを、各々６４ｋ要素／ｓおよび６４Ｍ要素／ｓとし、ブロックサイズＭ＝２５６要素数としたとき、配列の全データをＫ回更新するのに要するメモリの容量と処理時間を見積もる。
【００５８】
上述した一実施形態のメモリ制御装置では、基数ソートの各段で、最悪でＫ×Ｎの書き込みデータを退避メモリ装置３２へ退避(回復)することになるため、記憶容量は、２×Ｋ×Ｎ要素分だけ設ける。この記憶容量は、高々、要素数Ｎの定数倍で抑えられる。さらに、メモリ装置に対するアクセス回数は、基数ソートの各段で最悪の場合、２×Ｋ×Ｎ回、また、最終段ではブロック毎に１回ずつの配列データ１０への書き込みを生じる。
【００５９】
メモリアクセスは、いずれもブロックアクセスにより実現でき、基数ソートの段数がｌｏｇ2(Ｎ／Ｍ)であるため、上述した一実施形態のメモリ制御装置による総時間は、次のようになる。
本実施形態の総時間＝(1/64,000,000)×｛(2×K×N)×log2(N/M)＋N｝
≒(1/32,000000)×log2(N/256)×(K×N)
【００６０】
これに対して、例えば、ランダムアクセスの場合を行うメモリ制御装置を考えると、Ｋ×Ｎ回の更新を行うことになるため、総時間は、次のようになる。
ランダムアクセスの総時間＝(1/64,000)×(K×N)
【００６１】
従って、本実施形態のメモリ制御装置による総時間｛(1/32,000000)×log2(N/256)×(K×N)｝は、ランダムアクセスの総時間｛(1/64,000)×(K×N)｝よりも、ブロックアクセスにより、Ｎに対する係数が非常に小さくなり、高速化が可能なのが分かる。
【００６２】
例えば、配列の全データを６回更新する(メモリ装置１における配列データ１０を６回書き換える)場合、Ｋ＝６となる。また、本実施形態のスループットを「６４Ｍ要素／ｓ」とし、ランダムアクセスのスループットを「６４ｋ要素／ｓ」とする。なお、これらの値は、一般的に想定し得る値である。
【００６３】
さらに、ブロックサイズをＭ＝２５６要素とし、更新回数をＫ＝６とすると、図１３のようになる。また、図１３において、参照符合ＣＬ１は、本実施形態のメモリ制御装置による特性曲線を示し、ＣＬ２は、ランダムアクセスによる特性曲線を示す。
【００６４】
図１３における特性曲線ＣＬ１とＣＬ２の比較から明らかなように、例えば、Ｋ＝６の場合、本実施形態のメモリ制御装置による特性曲線ＣＬ１は、ランダムアクセスによる特性曲線ＣＬ２よりも２桁近く高速化できることが分かる。
【００６５】
以上、実施形態を説明したが、ここに記載したすべての例や条件は、発明および技術に適用する発明の概念の理解を助ける目的で記載されたものであり、特に記載された例や条件は発明の範囲を制限することを意図するものではなく、明細書のそのような例の構成は発明の利点および欠点を示すものではない。発明の実施形態を詳細に記載したが、各種の変更、置き換え、変形が発明の精神および範囲を逸脱することなく行えることが理解されるべきである。
【符号の説明】
【００６６】
１    メモリ装置
２    演算回路
３    メモリ制御装置
１０    メモリ装置に格納された配列データ
１１，１１'    書き込みレジスタ(レジスタ，バッファ)
１２    メモリセル
３０，３０a〜３０d    ソートバッファ(バッファ)
３１    書き込みソート回路
３２    退避メモリ装置
【図１】
2017179176.tif 000003
【図２】
2017179176.tif 000004
【図３】
2017179176.tif 000005
【図４】
2017179176.tif 000006
【図５】
2017179176.tif 000007
【図６】
2017179176.tif 000008
【図７】
2017179176.tif 000009
【図８】
2017179176.tif 000010
【図９】
2017179176.tif 000011
【図１０】
2017179176.tif 000012
【図１１】
2017179176.tif 000013
【図１２】
2017179176.tif 000014
【図１３】
2017179176.tif 000015
【国際調査報告】
2017179176.tif 000016
2017179176.tif 000017
2017179176.tif 000018