(57)【要約】【課題】プログラム内に含まれる３重ループによってアクセスするメモリを効率的にアクセスする方法および装置を提供する。【解決手段】プログラム内の３重ループによってメモリをアクセスするコードからａ、ｂ、ｃを獲得する段階（ａは３重ループの最内ループ変数が有し得る値の個数であり、ｂは３重ループの中間ループ変数が有し得る値の個数であり、ｃは３重ループの最外ループ変数が有し得る値の個数である）と、３重ループによってアクセスされるメモリの開始アドレスを獲得する段階と、開始アドレスおよび式を用いて３重ループによってアクセスされるメモリのａ×ｂ×ｃ個のアドレスを獲得する段階とを含むメモリアクセス方法を提供する。【選択図】図９
2008204428.tif 000002
【特許請求の範囲】
【請求項１】
プログラム内の３重ループによってメモリをアクセスするコードからａ、ｂ、ｃを獲得する段階（前記ａは前記３重ループの最内ループ変数が有し得る値の個数であり、前記ｂは前記３重ループの中間ループ変数が有し得る値の個数であり、前記ｃは前記３重ループの最外ループ変数が有し得る値の個数である）と、
前記３重ループによってアクセスされる前記メモリの開始アドレスを獲得する段階と、
前記開始アドレスおよび式を用いて、前記３重ループによってアクセスされる前記メモリのａ×ｂ×ｃ個のアドレスを獲得する段階と、
を含むことを特徴とするメモリアクセス方法。
【請求項２】
前記メモリの線形アドレスａｄｄｒを３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階をさらに含むことを特徴とする請求項１に記載のメモリアクセス方法。
【請求項３】
前記メモリの線形アドレスａｄｄｒを３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階は、
前記メモリの前記線形アドレスａｄｄｒを２次元アドレス（ｍ、ｎ）にマッピングする段階と、
前記２次元アドレス（ｍ、ｎ）を前記３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階と、
を含むことを特徴とする請求項２に記載のメモリアクセス方法。
【請求項４】
ｍ＝（ａｄｄｒ／Ｌ）の指数、
ｎ＝（ａｄｄｒ／Ｌ）の残り、
ａｄｄｒは前記メモリの前記線形アドレス、
Ｌは前記メモリの走査ラインの長さ、
であることを特徴とする請求項３に記載のメモリアクセス方法。
【請求項５】
ｘ＝ｍ、
ｙ＝（ｎ／ａ）の指数、
ｚ＝（ｎ／ａ）の残り、
であることを特徴とする請求項３に記載のメモリアクセス方法。
【請求項６】
前記３次元アドレス（ｘ、ｙ、ｚ）を３次元モジュール（ｐ、ｑ、ｒ）にマッピングする段階、
をさらに含むことを特徴とする請求項２に記載のメモリアクセス方法。
【請求項７】
ｐ＝ｘ  ｍｏｄ  ａ、
ｑ＝ｙ  ｍｏｄ  ｂ、
ｒ＝ｚ  ｍｏｄ  ｃ、
であることを特徴とする請求項６に記載のメモリアクセス方法。
【請求項８】
前記３次元モジュール（ｐ、ｑ、ｒ）にマッピングされるアドレスを順次に整列した３次元モジュール配列（ｐ、ｑ、ｒ）を生成する段階、
をさらに含むことを特徴とする請求項６に記載のメモリアクセス方法。
【請求項９】
前記数式は、
【数１】
2008204428.tif 000004
（ここで、（ｘ１、ｙ１、ｚ１）はａ×ｂ×ｃブロックの開始３次元アドレス）であり、
Ａｐ、ｑ、ｒ（ｘ１、ｙ１、ｚ１）は、開始アドレスの３次元アドレスが（ｘ１、ｙ１、ｚ１）であるａ×ｂ×ｃブロックで３次元モジュール（ｐ、ｑ、ｒ）にマッピングされたアドレスが、前記３次元モジュール配列（ｐ、ｑ、ｒ）で何番目であるかの値であることを特徴とするメモリ請求項８に記載のメモリアクセス方法。
【請求項１０】
前記３重ループによってアクセスされる前記メモリのａ×ｂ×ｃ個のアドレスを獲得する前記段階は、
前記メモリの前記開始アドレスにマッピングされる３次元アドレス（ｘ１、ｙ１、ｚ１）を獲得する段階と、
０＜＝ｐ＜ｃ、０＜＝ｑ＜ｂ、０＜＝ｒ＜ｃであるすべてのｐ、ｑ、ｒの組み合わせに対して、前記式を用いて３次元アドレス（ｘ１、ｙ１、ｚ１）を開始アドレスとするａ×ｂ×ｃブロックに含まれるメモリのアドレスを獲得する段階と、
を含むことを特徴とする請求項９に記載のメモリアクセス方法。
【請求項１１】
メモリの線形アドレスａｄｄｒを２次元アドレス（ｍ、ｎ）にマッピングする段階と、
前記２次元アドレス（ｍ、ｎ）を３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階と、
を含み、
Ａｄｄｒは前記メモリの前記線形アドレス、
Ｌは前記メモリの走査ラインの長さ、
前記ｍ＝（ａｄｄｒ／Ｌ）の指数、
前記ｎ＝（ａｄｄｒ／Ｌ）の残り、
ｘ＝ｍ、ｙ＝（ｎ／ａ）の指数、
ｚ＝（ｎ／ａ）の残り、
ａは最内ループ変数が有し得る値の個数、
であることを特徴とする３次元アドレスマッピング方法。
【請求項１２】
請求項１〜１１のいずれか一項の方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメモリシステムに関し、より詳細には、３次元アドレスマッピングを用いて線形アドレスメモリ（LAM：linear addressable memory）を効率的にアクセスする方法および装置に関する。
【背景技術】
【０００２】
図１は、関連技術によってメモリブロックをアクセスする場合を説明するための図である。プログラム内に２×２の２重ループ（double loop）を有している場合、この２重ループによってアクセスするメモリのアドレスは連続的でない。図１に示すように、アクセスするブロック（block to access）１２０に含まれたデータは４つである。この場合、線形アドレスメモリは、最大４回のメモリアクセスを必要とする。このようなメモリアクセスを減らすために、ブロックアクセス（block access）が用いられる。例えば、１回のメモリアクセスで４つの整列したブロック（aligned block）を読み取るのである。しかし、この場合にも、読み取ろうとするデータがすべて１つの整列したブロックに含まれていなければ、従来のように何回もメモリアクセスを要求するようになる。図１の場合、アクセスするブロック１２０に含まれたデータは、すべて異なる整列したブロックに含まれている。例えば、アクセスするブロック１２０のアドレス２３は、整列したブロック１１０に含まれている。この場合、アクセスするブロック１２０に含まれたデータをすべてアクセスするためには、４回のメモリアクセスが要求される。
【０００３】
一方、プログラム上では２重、３重ループが多く登場し、特に映像処理を行うプログラムの場合には、３重ループが多く用いられる。したがって、このような３重ループを介してアクセスするメモリを効率的にアクセスできる方法および装置が求められている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、プログラム内に含まれる３重ループ（triple loop）によってアクセスするメモリを効率的にアクセスする方法および装置を提供することを目的とする。
【０００５】
また、本発明は、線形アドレスを３重ループによってアクセスするメモリのアドレス計算に適合した３次元アドレスで効率的にマッピングする方法および装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一側に係るメモリアクセス方法は、プログラム内の３重ループによってメモリをアクセスするコードからａ、ｂ、ｃを獲得する段階（前記ａは前記３重ループの最内ループ変数が有し得る値の個数であり、前記ｂは前記３重ループの中間ループ変数が有し得る値の個数であり、前記ｃは前記３重ループの最外ループ変数が有し得る値の個数である）と、前記３重ループによってアクセスされる前記メモリの開始アドレスを獲得する段階と、前記開始アドレスおよび式を用いて前記３重ループによってアクセスされる前記メモリのａ×ｂ×ｃ個のアドレスを獲得する段階とを含む。
【０００７】
本発明のさらに他の観点によれば、前記メモリアクセス方法は、前記メモリの前記線形アドレス「ａｄｄｒ」を２次元アドレス（ｍ、ｎ）にマッピングする段階と、前記２次元アドレス（ｍ、ｎ）を前記３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階と、前記３次元アドレス（ｘ、ｙ、ｚ）を３次元モジュール（ｐ、ｑ、ｒ）にマッピングする段階と、前記３次元モジュール（ｐ、ｑ、ｒ）にマッピングされるアドレスを順に整列した３次元モジュール配列（ｐ、ｑ、ｒ）を生成する段階とをさらに含む。
【０００８】
本発明のさらに他の一側によれば、３次元アドレスマッピング方法は、メモリの線形アドレス「ａｄｄｒ」を２次元アドレス（ｍ、ｎ）にマッピングする段階（Ｌは前記メモリの走査ラインの長さであり、前記ｍ＝（ａｄｄｒ／Ｌ）の指数、前記ｎ＝（ａｄｄｒ／Ｌ）の残りである）と、前記２次元アドレス（ｍ、ｎ）を３次元アドレス（ｘ、ｙ、ｚ）にマッピングする段階（ａは最内ループ変数が有し得る値の個数であり、ｘ＝ｍ、ｙ＝（ｎ／ａ）の指数、ｚ＝（ｎ／ａ）の残りである）とを含む。
【発明の効果】
【０００９】
本発明によれば、プログラム内に含まれる３重ループによってアクセスするメモリを効率的にアクセスする方法および装置を提供することができる。
【００１０】
また、本発明によれば、線形アドレスを３重ループによってアクセスするメモリのアドレス計算に適合した３次元アドレスに効率的にマッピングする方法および装置を提供することができる。
【００１１】
また、本発明によれば、メモリのアライメントと関係なく、３重ループによってアクセスされるメモリをブロック単位でアクセスすることができる。
【発明を実施するための最良の形態】
【００１２】
以下、添付の図面に基づき、本発明の好適な実施の形態を詳細に説明するが、本発明がこれらの実施形態によって制限または限定されることはない。図中、同じ参照符号は同じ部材を示す。
【００１３】
図２は、本発明の説明のための３重ループを含んだプログラムの一例を示した図である。
【００１４】
ｍｐｅｇ（Moving Picture Experts Group）、H.264などのビデオコーデック（video codec）には、図２に示すようなfullsearch（）関数が多く用いられる。図２に示すように、fullsearch（）関数は３重ループを有する。図２に示すように、最内ループ２１０でメモリを参照するときは、１次元パターンを有する。しかし、中間ループ２２０まで含んで２重ループを行う場合、メモリを参照するときは２次元パターンを有する。また、最外ループ２３０を含んで３重ループを行なう場合、メモリを参照するときは３次元パターン２４０を有する。このようなfullsearch（）関数の他にも、ビデオ処理プログラムは３重ループを多く有している。
【００１５】
１次元パターンでメモリをアクセスするときは連続的な位置のメモリをアクセスするようになるが、２次元パターンや３次元パターンでメモリをアクセスするときは、離れているメモリの位置をアクセスしなければならない。図２で、「ａ［ｋ］［ｊ］［ｉ］」は３重ループにアクセスされるため、互いに離れているメモリの位置をアクセスしなければならない。本発明では、このような３重ループで参照されるメモリを効率的にアクセスするために、仮想的にマッチングされた３次元アドレスを用いている。
【００１６】
図２において、３重ループのうち最内ループ変数は「ｉ」であり、この変数「ｉ」が有し得る値の個数は「８」である。また、図２において、３重ループのうち中間ループ変数は「ｊ」であり、この変数「ｊ」が有し得る値の個数は「８」である。同様に、図２において、３重ループのうち最外ループ変数は「ｋ」であり、この変数「ｋ」が有し得る値の個数は「２」である。
【００１７】
図３は、本発明によってメモリの線形アドレスを２次元アドレスにマッピングする動作を説明するための図である。
【００１８】
本発明は、まず、メモリの線形アドレス「ａｄｄｒ」を２次元アドレス（ｍ、ｎ）にマッピングする。マッピング方法は下記の数式１の通りとなる。
【００１９】
（数式１）
ａｄｄｒ→（ｍ、ｎ）
（ここで、ｍ＝（ａｄｄｒ／Ｌ）の指数、ｎ＝（ａｄｄｒ／Ｌ）の残り、Ｌはメモリの走査ラインの長さである）
【００２０】
Ｌは、メモリの走査ラインの長さ（scan line length）であり、メモリを読み取るときの幅（width）を意味する。図３において、走査ラインの長さは「１６」である。１次元アドレス（線形アドレス）で表示されたメモリ３１０を仮想的に２次元アドレスに変換し、２次元アドレスで表示したメモリ３２０が図３に示されている。
【００２１】
本発明の実施形態において、３重ループのうち最内ループの変数は「ｉ」であり、この変数「ｉ」が有し得る値の個数は「ａ」である。例えば、最内ループが「ｆｏｒ（ｉ＝０；ｉ＜２；ｉ＋＋）」であれば、最内ループ変数は「ｉ」であり、「ｉ」が有し得る値は０、１の２つであるため、「ａ」は「２」となる。同様に、３重ループのうち中間ループの変数は「ｊ」であり、この変数「ｊ」が有し得る値の個数は「ｂ」である。また、３重ループのうち最外ループの変数は「ｋ」であり、この変数「ｋ」が有し得る値の個数は「ｃ」である。図２の実施形態では、ａ、ｂすべてが「２」である場合を説明する。図２において、内側の２重ループによってアクセスされるメモリ位置をメモリ３２０に整列して表示した。最外ループ変数が１番目の値を有するとき、内側２重ループによってアクセスされるメモリは（０、０）、（０、１）、（１、０）、（１、１）となる。また、最外ループ変数が２番目の値を有するとき、内側２重ループによってアクセスされるメモリは（０、２）、（０、３）、（１、２）、（１、３）となる。
【００２２】
図４は、本発明によってメモリの２次元アドレスを３次元アドレスにマッピングする動作を説明するための図である。
【００２３】
本発明は、線形アドレス「ａｄｄｒ」からマッピングされた２次元アドレス（ｍ、ｎ）を仮想的に３次元アドレス（ｘ、ｙ、ｚ）にマッピングする。したがって、結果的には、線形アドレス「ａｄｄｒ」は３次元アドレス（ｘ、ｙ、ｚ）にマッピングされる。２次元アドレスを３次元アドレスにマッピングする方法は、下記の数式２の通りとなる。
【００２４】
（数式２）
（ｍ、ｎ）→（ｘ、ｙ、ｚ）
（ここで、ｘ＝ｍ、ｙ＝（ｎ／ａ）の指数、ｚ＝（ｎ／ａ）の残り、ａは３重ループの最内ループ変数が有し得る値の数）
【００２５】
２次元アドレスで表示されたメモリ４１０を仮想的に３次元アドレスに変換し、３次元アドレスで表示したメモリ４２０が図４に示されている。図４の実施形態は、３重ループのうち最内ループ変数が有し得る値の数「ａ」が「２」である場合である。したがって、２次元アドレス（０、６）は３次元アドレス（０、３、０）にマッピングされ、２次元アドレス（２、１０）は３次元アドレス（２、５、０）にマッピングされる。
【００２６】
図５は、本発明によって３次元アドレスを３次元モジュールにマッピングする動作を説明するための図である。
【００２７】
本発明は、３次元アドレス（ｘ、ｙ、ｚ）を３次元モジュール（ｐ、ｑ、ｒ）にマッピングする。３次元アドレスを３次元モジュールにマッピングする方法は、下記の数式３の通りである。
【００２８】
（数式３）
（ｘ、ｙ、ｚ）→（ｐ、ｑ、ｒ）
（ここで、ｐ＝ｘ  ｍｏｄ  ｃ、ｑ＝ｙ  ｍｏｄ  ｂ、ｒ＝ｚ  ｍｏｄ  ａ、ａは３重ループの最内ループ変数が有し得る値の数、ｂは３重ループの中間ループ変数が有し得る値の数、ｃは３重ループの最外ループ変数が有し得る値の数）
【００２９】
３次元アドレスで表示されたメモリ５１０を３次元モジュールにマッピングして３次元モジュールで表示したメモリ５２０が、図５に示されている。図５の実施形態において、３重ループのうち最内ループ変数が有し得る値の数「ａ」は「２」である。また、３重ループのうち中間ループ変数が有し得る値の数「ｂ」は「２」であり、３重ループの最外ループ変数が有し得る値の数「ｃ」も「２」である。したがって、図５において、３次元アドレス（０、２、０）は３次元モジュール（０、０、０）にマッピングされ、３次元アドレス（３、４、０）は３次元モジュール（１、０、０）にマッピングされる。
【００３０】
図６ａおよび図６ｂは、本発明によって３次元モジュール配列（3-D module array）を生成する動作を説明するための図である。
【００３１】
本発明では、生成された３次元モジュール（ｐ、ｑ、ｒ）を用いて、３次元モジュール（ｐ、ｑ、ｒ）にマッピングされるアドレスを順に整列した３次元モジュール配列（ｐ、ｑ、ｒ）を生成する。図６ａおよび図６ｂは、図５でマッピングされた３次元モジュールを用いて生成された３次元モジュール配列の一部を示したものである。
【００３２】
図６ａは、３次元モジュール配列（０、０、０）を示したものである。３次元モジュール配列（０、０、０）は、３次元モジュール（０、０、０）にマッピングされるアドレスを順に整列したものである。このアドレスは線形アドレス（１次元アドレス）であっても良いし、２次元アドレスまたは３次元アドレスであっても良い。図６ａでは、アドレスが３次元アドレスである場合を示している。図５に示すように、３次元モジュール（０、０、０）にマッピングされる３次元アドレスは、（０、０、０）、（０、２、０）、（０、４、０）、（０、６、０）などの順序となる。仮に、２次元アドレスで表示すれば、３次元モジュール（０、０、０）にマッピングされる２次元アドレスは、（０、０）、（０、４）、（０、８）、（０、１２）などである。仮に、１次元アドレスで表示すれば、３次元モジュール（０、０、０）にマッピングされる１次元アドレスは、０、４、８、１２などである。
【００３３】
図６ｂは、３次元モジュール配列（０、１、１）を示したものである。３次元モジュール配列（０、１、１）は、３次元モジュール（０、１、１）にマッピングされるアドレスを順に整列したものである。図５に示すように、３次元モジュール（０、１、１）にマッピングされる３次元アドレスは、（０、１、１）、（０、３、１）、（０、５、１）、（０、７、１）などの順となる。
【００３４】
図７は、本発明によって３重ループによってアクセスされるメモリブロックのアドレスを得る動作を説明するための図である。
【００３５】
まず、３重ループによってアクセスされるメモリの開始アドレスを３次元アドレスにマッピングする。３重ループによってアクセスされるメモリの開始アドレスは線形アドレスであるため、この線形アドレスを３次元アドレスにマッピングする動作は数式１および数式２を用いて行われる。例えば、図３〜４において、３重ループによってアクセスされるメモリの開始アドレスが「２３」であれば、１次元アドレス「２３」は数式１および数式２によって３次元アドレス（１、３、１）にマッピングされる。
【００３６】
その後、下記の数式４を用いて、ａ×ｂ×ｃブロックをアクセスする。ここで、「ａ」は３重ループの最内ループ変数が有し得る値の個数であり、「ｂ」は３重ループの中間ループ変数が有し得る値の個数であり、「ｃ」は３重ループの最外ループ変数が有し得る値の個数である。Ｌは、メモリの走査ラインの長さである。
【００３７】
【数１】
2008204428.tif 000003
（ここで、（ｘ１、ｙ１、ｚ１）はａ×ｂ×ｃブロックの開始３次元アドレス）
【００３８】
これにより、Ａｐ、ｑ、ｒ（ｘ１、ｙ１、ｚ１）は、開始アドレスの３次元アドレスが（ｘ１、ｙ１、ｚ１）であるａ×ｂ×ｃブロックで３次元モジュール（ｐ、ｑ、ｒ）にマッピングされたアドレスが、この３次元モジュール配列（ｐ、ｑ、ｒ）で何番目に対応するのかの値を示す。より具体的には、Ａｐ、ｑ、ｒ（ｘ１、ｙ１、ｚ１）が「ｆ」の値を有していれば、開始アドレスの３次元アドレスが（ｘ１、ｙ１、ｚ１）であるａ×ｂ×ｃブロックで３次元モジュール（ｐ、ｑ、ｒ）にマッピングされたアドレスは、この３次元モジュール配列（ｐ、ｑ、ｒ）で「ｆ＋１」番目の値となる。
【００３９】
図７の実施形態において、プログラム上の３重ループに含まれた最内ループ変数、中間ループ変数および最外ループ変数が有し得る値の個数はすべて「２」である。また、ａ×ｂ×ｃブロックの開始３次元アドレスは、３重ループによってアクセスされるメモリの開始アドレスである「２３」にマッピングされる３次元アドレス（１、３、１）として仮定する。これにより、開始アドレス「２３」（３次元アドレスにマッピングすれば（１、３、１））で始まる２×２×２ブロックにマッピングされるメモリは、（ｐ、ｑ、ｒ）に（０、０、０）、（０、０、１）、（０、１、０）、（０、１、１）、（１、０、０）、（１、０、１）、（１、１、０）、（１、１、１）の値を入れて計算されるＡｐ、ｑ、ｒ（ｘ１、ｙ１、ｚ１）を介して知ることができる。
【００４０】
例えば、図７において、アクセスするブロック７１０の開始アドレスの３次元アドレス（ｘ１、ｙ１、ｚ１）が（１、３、１）である場合を説明する。本実施形態において、プログラム上の３重ループに含まれた最内ループ変数が有し得る値の個数ａ、中間ループ変数が有し得る値の個数ｂおよび最外ループ変数が有し得る値の個数ｃはすべて「２」である。Ｌはメモリの走査ラインの長さであり、図７の実施形態では「１６」である。本発明によれば、数式１を用いて（ｐ、ｑ、ｒ）に（０、１、１）を入れれば、Ａ０、１、１（１、３、１）＝（０＋１）×４＋１＋０＋０＝５となる。すなわち、開始アドレスの３次元アドレスが（１、３、１）である２×２×２ブロックで３次元モジュール（０、１、１）にマッピングされたアドレスは、３次元モジュール配列（０、１、１）で６（＝５＋１）番目となる。図６ｂに示すように、３次元モジュール配列（０、１、１）で６番目は、３次元アドレスが（２、３、１）であるメモリである。
【００４１】
同様に、数式１を用いて（ｐ、ｑ、ｒ）に（０、０、０）を入れれば、Ａ０、０、０（１、３、１）＝（０＋１）×４＋１＋１＋０＝６となる。すなわち、開始アドレスの３次元アドレスが（１、３、１）である２×２×２ブロックで３次元モジュール（０、０、０）にマッピングされたアドレスは、３次元モジュール配列（０、０、０）で７（＝６＋１）番目となる。図６ａに示すように、３次元モジュール配列（０、０、０）で７番目は、３次元アドレスが（２、４、０）であるメモリである。
【００４２】
特に、図７において、アクセスするブロック７１０を整列していないが、本発明によれば１つのブロックにアクセスするように構成できる。すなわち、本発明によれば、メモリのアライメント（alignment）と関係なく、３重ループによってアクセスされるメモリをブロック単位でアクセスすることができる。
【００４３】
図８は、本発明によって３重ループによってアクセスするメモリのアドレスを獲得する順序を示したフローチャートである。
【００４４】
本発明は、まず、段階８１０で、プログラム内の３重ループによってメモリをアクセスするコードを識別する。例えば、図２に示すように、図２のプログラムからループ２３０、ループ２２０およびループ２１０の３重ループによってメモリにアクセスするコードを識別する。その次に、この３重ループから３重ループの最内ループ変数が有し得る値の個数ａ、３重ループの中間ループ変数が有し得る値の個数ｂ、３重ループの最外ループ変数が有し得る値の個数ｃを獲得する。図２のプログラムに示すように、ループ２１０、２２０、２３０で成された３重ループのうち最内ループ変数は「ｉ」であり、この変数「ｉ」が有し得る値の個数は「８」である。また、図２において、３重ループのうち中間ループ変数は「ｊ」であり、この変数「ｊ」が有し得る値の個数は「８」である。同様に、図２において、３つのループのうち最外ループ変数は「ｋ」であり、この変数「ｋ」が有し得る値の個数は「２」である。仮に、最内側ループが「ｆｏｒ（ｉ＝０；ｉ＜８；ｉ＝ｉ＋３）」として与えられれば、ｉは０、３、６の値を有するため、変数「ｉ」が有し得る値の個数は「３」である。
【００４５】
段階８２０で、本発明は、３重ループによってアクセスされるメモリの開始アドレスを獲得する。図２のプログラムにおいて、３重ループによってアクセスされるメモリの開始アドレスは「ａ［０］［０］［０］」に該当するアドレスとなる。
【００４６】
段階８３０で、本発明は、開始アドレスおよび式を用いて、３重ループによってアクセスされるメモリのａ×ｂ×ｃ個のアドレスを獲得する。このためには、メモリの線形アドレスを３次元アドレスにマッピングし、３次元アドレスに基づいて３次元モジュールアレイを計算する。これに関しては、図３〜６で詳しく説明した通りである。そして、開始アドレスから開始アドレスにマッピングされる３次元アドレス（ｘ１、ｙ１、ｚ１）を求める。さらに、０＜＝ｐ＜ｃ、０＜＝ｑ＜ｂ、０＜＝ｒ＜ｃであるすべてのｐ、ｑ、ｒの組み合わせに対して、数式４を用いて３次元アドレス（ｘ１、ｙ１、ｚ１）を開始アドレスとするａ×ｂ×ｃブロックに含まれるメモリのアドレスを獲得する。
【００４７】
図９は、本発明によって線形アドレスメモリを仮想的に３−ＤＡＭ（3-D addressable memory）にマッピングする順序を示したフローチャートである。
【００４８】
段階９１０で、メモリの線形アドレス「ａｄｄｒ」は、２次元アドレス（ｍ、ｎ）にマッピングされる。マッピング方法は、数式１の通りである。これに関しては、図３に詳しく説明されている。
【００４９】
段階９２０で、２次元アドレス（ｍ、ｎ）は、３次元アドレス（ｘ、ｙ、ｚ）にマッピングされる。したがって、結果的には、線形アドレス「ａｄｄｒ」は３次元アドレス（ｘ、ｙ、ｚ）にマッピングされる。２次元アドレスを３次元アドレスにマッピングする方法は、数式２の通りである。これに関しては、図４に詳しく説明されている。
【００５０】
段階９３０で、３次元アドレス（ｘ、ｙ、ｚ）は、３次元モジュール（ｐ、ｑ、ｒ）にマッピングされる。３次元アドレスを３次元モジュールにマッピングする方法は、数式３の通りである。これに関しては、図５に詳しく説明されている。
【００５１】
段階９４０で、生成された３次元モジュール（ｐ、ｑ、ｒ）を用いて、３次元モジュール（ｐ、ｑ、ｒ）にマッピングされるアドレスを順に整列した３次元モジュール配列（ｐ、ｑ、ｒ）が生成される。これに関しては、図６に詳しく説明されている。
【００５２】
前述したように本発明の実施形態は、コンピュータにより具現される多様な動作を実行するためのプログラム命令を含むコンピュータ読み取り可能な媒体を含む。この媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせた構成を含むこともできる。このような媒体およびプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知であり使用可能なものであってもよい。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フレキシブルディスクおよび磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれる。前述した媒体は、プログラム命令、データ構造などを保存する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体でもある。プログラム命令の例としては、コンパイラによって生成されるもののような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００５３】
図１０は、本発明の仮想３次元アドレスマッピングを用いて線形アドレスメモリにアクセスする３ＤＡＭＣ（3-Dimensional Accessible Memory Controller）の動作を説明するための図である。
【００５４】
本発明の動作を実行する３ＤＭＡＣ１０２０は、ハードウェアで具現される。この場合、３ＤＭＡＣ１０２０は、プロセッシング装置１０３０と線形アクセスメモリ１０１０との間に位置し、３重ループによってアクセスされるコードに対して、本発明の３次元アドレスマッピングを用いてブロック単位でメモリにアクセスすることができる。３ＤＭＡＣ１０２０によって実行される動作は、図８〜９で説明された動作の全部または一部となり得る。
【００５５】
以上、３重ループの場合に対してのみ説明したが、本発明は４重ループ以上にも適用することができる。この場合、内側３重ループに対して本発明を適用することで、４重ループ以上でも効率的にメモリアクセスを行えるようになる。
【００５６】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野において熟練した当業者にとっては、特許請求の範囲に記載された本発明の思想および領域から逸脱しない範囲内で、本発明を多様に修正および変更きることを理解することが可能であろう。すなわち、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により制限されるものではない。
【図面の簡単な説明】
【００５７】
【図１】関連技術によってメモリブロックをアクセスする場合を説明するための図である。
【図２】本発明の説明のための３重ループを含んだプログラムの一例を示した図である。
【図３】本発明によってメモリの線形アドレスを２次元アドレスにマッピングする動作を説明するための図である。
【図４】本発明によってメモリの２次元アドレスを３次元アドレスにマッピングする動作を説明するための図である。
【図５】本発明によって３次元アドレスを３次元モジュールにマッピングする動作を説明するための図である。
【図６ａ】本発明によって３次元モジュール配列を生成する動作を説明するための図である。
【図６ｂ】本発明によって３次元モジュール配列を生成する動作を説明するための図である。
【図７】本発明によってａ×ｂ×ｃ個のデータで構成されたブロックのアドレスを得る動作を説明するための図である。
【図８】本発明によって３重ループによってアクセスするメモリのアドレスを獲得する順序を示したフローチャートである。
【図９】本発明によって線形アドレスメモリを仮想的に３ＤＡＭにマッピングする順序を示したフローチャートである。
【図１０】本発明の仮想３次元アドレスマッピングを用いて線形アドレスメモリにアクセスする３ＤＡＭＣの動作を説明するための図である。
【図８】
2008204428.tif 000005
【図９】
2008204428.tif 000006
【図１】
2008204428.tif 000007
【図２】
2008204428.tif 000008
【図３】
2008204428.tif 000009
【図４】
2008204428.tif 000010
【図５】
2008204428.tif 000011
【図６ａ】
2008204428.tif 000012
【図６ｂ】
2008204428.tif 000013
【図７】
2008204428.tif 000014
【図１０】
2008204428.tif 000015