(57)【要約】【課題】Ｎ次元テンソルにアクセスするための命令を処理するための装置を含む、方法、システムおよび装置を提供する。【解決手段】当該装置は、複数のテンソルインデックス要素と、複数の次元乗数要素とを含み、次元乗数要素の各々は、対応するテンソルインデックス要素を有する。当該装置は、１つ以上のプロセッサを含み、当該１つ以上のプロセッサは、Ｎ次元テンソルの特定の要素にアクセスするための命令を取得するように構成され、Ｎ次元テンソルは、Ｎ個の次元の各々にわたって配置された複数の要素を有し、Ｎは、１以上の整数であり、当該１つ以上のプロセッサはさらに、複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、特定の要素のアドレスを決定するように構成され、Ｎ次元テンソルの特定の要素にアクセスするための決定されたアドレスを示すデータを出力するように構成される。【選択図】図１
2017138964.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次元テンソルにアクセスするための命令を処理するための装置であって、
複数のテンソルインデックス要素と、
複数の次元乗数要素とを備え、前記次元乗数要素の各々は、対応するテンソルインデックス要素を有し、前記装置はさらに、
１つ以上のプロセッサを備え、前記１つ以上のプロセッサは、
Ｎ次元テンソルの特定の要素にアクセスするための命令を取得するように構成され、前記Ｎ次元テンソルは、Ｎ個の次元の各々にわたって配置された複数の要素を有し、Ｎは、１以上の整数であり、前記１つ以上のプロセッサはさらに、
前記複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および前記複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、前記特定の要素のアドレスを決定するように構成され、
前記Ｎ次元テンソルの前記特定の要素にアクセスするための前記決定されたアドレスを示すデータを出力するように構成される、装置。
【請求項２】
前記特定の要素の前記アドレスは、前記Ｎ次元テンソルの別の要素からのアドレスオフセットであり、
前記特定の要素の前記アドレスを決定することは、
前記１つ以上のテンソルインデックス要素の各テンソルインデックス要素ごとに、それぞれのテンソルインデックス要素に記憶された値と前記１つ以上の複数のテンソルインデックス要素の前記対応するテンソルインデックス要素に記憶された値とを乗算して、それぞれの乗算された値を生成することと、
前記乗算された値の合計を求めることによって前記アドレスオフセットを決定することとを備える、請求項１に記載の装置。
【請求項３】
前記複数のテンソルインデックス要素は、テンソルインデックス要素のＭ個のグループに配置され、Ｍは、１よりも大きな正の整数であり、
テンソルインデックス要素の各グループは、別個の異なる多次元テンソルに割り当てられる、請求項１に記載の装置。
【請求項４】
複数のテンソル境界要素をさらに備え、前記複数のテンソル境界要素の各々は、前記複数のテンソルインデックス要素における対応するテンソルインデックス要素を有する、請求項１に記載の装置。
【請求項５】
前記命令は、第１のループと前記第１のループの外側ループである第２のループとを含む入れ子ループを処理するための命令を表わし、前記第１のループは、第１のインデックス変数を用いて反復され、前記第２のループは、第２のインデックス変数を用いて反復される、請求項４に記載の装置。
【請求項６】
前記１つ以上のプロセッサはさらに、
前記複数のテンソルインデックス要素、前記複数の次元乗数要素および前記複数のテンソル境界要素に記憶された値を初期化値に設定するように構成される、請求項５に記載の装置。
【請求項７】
前記１つ以上のプロセッサはさらに、
前記複数のテンソル境界要素の第１のテンソル境界要素に記憶された値を、前記第１のループを反復するための前記第１のインデックス変数の上限値に設定するように構成され、
前記複数のテンソル境界要素の第２のテンソル境界要素に記憶された値を、前記第２のループを反復するための前記第２のインデックス変数の上限値に設定するように構成され、
前記複数の次元乗数要素の第１の次元乗数要素に記憶された値を、予め定められた値に設定するように構成され、
前記複数の次元乗数要素の第２の次元乗数要素に記憶された値を、前記第１のインデックス変数の前記上限値に設定するように構成される、請求項５に記載の装置。
【請求項８】
前記Ｎ次元テンソルの前記要素の前記アドレスを決定することは、
前記複数のテンソルインデックス要素の第１のテンソルインデックス要素に記憶された値を、前記第１のインデックス変数の現在の値に設定することと、
前記複数のテンソルインデックス要素の第２のテンソルインデックス要素に記憶された値を、前記第２のインデックス変数の現在の値に設定することと、
前記第１の次元乗数要素に記憶された前記値と前記第１のテンソルインデックス要素に記憶された前記値とを乗算して、第１の乗算された値を取得することと、
前記第２の次元乗数要素に記憶された前記値と前記第２のテンソルインデックス要素に記憶された前記値とを乗算して、第２の乗算された値を取得することと、
前記第１の乗算された値および前記第２の乗算された値を少なくとも合計することによって前記アドレスを決定することとを備える、請求項７に記載の装置。
【請求項９】
前記１つ以上のプロセッサはさらに、
前記第１のテンソルインデックス要素に記憶された前記値を更新するための命令を受取るように構成され、
前記第１のテンソルインデックス要素に記憶された前記値を更新するための前記命令を受取った後、前記第１のテンソルインデックス要素に記憶された前記値と前記第１のテンソル境界要素に記憶された前記値との間の差が閾値を満たすことを判断するように構成され、
前記第１のテンソルインデックス要素に記憶された前記値と前記第１のテンソル境界要素に記憶された前記値との間の前記差が前記閾値を満たすと判断したことに応答して、前記第１のテンソルインデックス要素に記憶された前記値を更新するように構成される、請求項８に記載の装置。
【請求項１０】
前記第１のインデックス変数は、前記第１のループが完了するたびに第１のインクリメント値だけインクリメントされ、
前記第１のテンソルインデックス要素に記憶された前記値を更新することは、前記第１のテンソルインデックス要素に記憶された前記値を前記第１のインクリメント値だけインクリメントすることを備える、請求項９に記載の装置。
【請求項１１】
前記１つ以上のプロセッサはさらに、
前記第１のテンソルインデックス要素に記憶された前記値を更新するための命令を受取るように構成され、
前記第１のテンソルインデックス要素に記憶された前記値を更新するための前記命令を受取った後、前記第１のテンソルインデックス要素に記憶された前記値と前記第１のテンソル境界要素に記憶された前記値との間の差が閾値を満たさないことを判断するように構成され、
前記第１のテンソルインデックス要素に記憶された前記値と前記第１のテンソル境界要素に記憶された前記値との間の前記差が前記閾値を満たさないと判断したことに応答して、
前記第１のテンソルインデックス要素に記憶された前記値をリセットするように構成され、
前記第２のテンソルインデックス要素に記憶された前記値を更新するように構成される、請求項８に記載の装置。
【請求項１２】
前記第２のインデックス変数は、前記第２のループが完了するたびに第２のインクリメント値だけインクリメントされ、
前記第２のテンソルインデックス要素に記憶された前記値を更新することは、前記第２のテンソルインデックス要素に記憶された前記値を前記第２のインクリメント値だけインクリメントすることを備える、請求項１１に記載の装置。
【請求項１３】
前記１つ以上のプロセッサは、１つ以上の演算論理ユニットを含む、請求項１に記載の装置。
【請求項１４】
前記テンソルインデックス要素および前記次元乗数要素の各々は、レジスタである、請求項１に記載の装置。
【請求項１５】
複数の分岐先要素をさらに備え、前記複数の分岐先要素の各々は、前記複数のテンソルインデックス要素における対応するテンソルインデックス要素を有し、前記複数の分岐先要素の各々は、それぞれの分岐先要素に対応するループの反復が完了すると実行される命令のためのアドレスを記憶するように構成される、請求項１に記載の装置。
【請求項１６】
システムであって、
Ｎ次元テンソル上で線形代数演算を実行するように構成された１つ以上のプロセッサを備え、前記Ｎ次元テンソルは、Ｎ個の次元の各々にわたって配置された複数の要素を有し、Ｎは、１以上の整数であり、前記システムはさらに、
複数のテンソルインデックス要素と、
複数の次元乗数要素とを備え、前記次元乗数要素の各々は、対応するテンソルインデックス要素を有し、前記システムはさらに、
回路を備え、前記回路は、
前記Ｎ次元テンソルの特定の要素にアクセスするための命令を取得するように構成され、
前記複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および前記複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、前記特定の要素のアドレスを決定するように構成され、
前記Ｎ次元テンソルの前記特定の要素にアクセスするための前記決定されたアドレスを示すデータを前記１つ以上のプロセッサに出力するように構成される、システム。
【請求項１７】
前記特定の要素の前記アドレスは、前記Ｎ次元テンソルの別の要素からのアドレスオフセットであり、
前記特定の要素の前記アドレスを決定することは、
前記１つ以上のテンソルインデックス要素の各テンソルインデックス要素ごとに、それぞれのテンソルインデックス要素に記憶された値と前記１つ以上の複数のテンソルインデックス要素の前記対応するテンソルインデックス要素に記憶された値とを乗算して、それぞれの乗算された値を生成することと、
前記乗算された値の合計を求めることによって前記アドレスオフセットを決定することとを備える、請求項１６に記載のシステム。
【請求項１８】
コンピュータによって実行される方法であって、
Ｎ次元テンソルの特定の要素にアクセスするための命令を取得するステップを備え、前記Ｎ次元テンソルは、Ｎ個の次元の各々にわたって配置された複数の要素を有し、Ｎは、１以上の整数であり、前記方法はさらに、
複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、前記特定の要素のアドレスを決定するステップと、
前記Ｎ次元テンソルの前記特定の要素にアクセスするための前記決定されたアドレスを示すデータを出力するステップとを備える、方法。
【請求項１９】
前記特定の要素の前記アドレスは、前記Ｎ次元テンソルの別の要素からのアドレスオフセットであり、
前記特定の要素の前記アドレスを決定するステップは、
前記１つ以上のテンソルインデックス要素の各テンソルインデックス要素ごとに、それぞれのテンソルインデックス要素に記憶された値と前記１つ以上の複数のテンソルインデックス要素の対応するテンソルインデックス要素に記憶された値とを乗算して、それぞれの乗算された値を生成するステップと、
前記乗算された値の合計を求めることによって前記アドレスオフセットを決定するステップとを備える、請求項１８に記載の方法。
【請求項２０】
前記命令は、第１のループと前記第１のループの外側ループである第２のループとを含む入れ子ループを処理するための命令を表わし、前記第１のループは、第１のインデックス変数を用いて反復され、前記第２のループは、第２のインデックス変数を用いて反復される、請求項１８に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
発明の詳細な説明
背景
本明細書は、一般に、メモリアドレス値を計算するためのレジスタの使用に関する。レジスタは、分岐条件の処理に使用され得る。
【発明の概要】
【課題を解決するための手段】
【０００２】
概要
本明細書に記載されている主題の１つの革新的な側面によれば、レジスタは、入れ子ループ構造を反復し、対応するメモリアドレスを計算し、プログラマがループ境界条件を処理することを可能にすることに使用できる。一般に、レジスタは、ループ境界値、各ループにおける現在のループインデックス変数、メモリアドレス値を計算するための次元乗数、および分岐ループ境界を処理するためのプログラムカウンタ値を含むアーキテクチャステータスのいくつかのセットを維持するように配置され得る。当該配置は、１つ以上の多次元データ構造の処理にとって有効であり得る。これらのアーキテクチャステータスセットにより、プロセッサは、インデックス変数を新たな位置に移動させ、メモリアドレス値を検索し、新たな分岐先にジャンプするための命令を実行し得る。
【０００３】
一般に、本明細書に記載されている主題の１つの革新的な側面は、Ｎ次元テンソルにアクセスするための命令を処理するための装置で具体化できる。上記装置は、複数のテンソルインデックス要素と、複数の次元乗数要素とを含み、上記次元乗数要素の各々は、対応するテンソルインデックス要素を有する。上記装置は、１つ以上のプロセッサを含み、上記１つ以上のプロセッサは、Ｎ次元テンソルの特定の要素にアクセスするための命令を取得するように構成され、上記Ｎ次元テンソルは、Ｎ個の次元の各々にわたって配置された複数の要素を有し、Ｎは、１以上の整数であり、上記１つ以上のプロセッサはさらに、上記複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および上記複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、上記特定の要素のアドレスを決定するように構成され、上記Ｎ次元テンソルの上記特定の要素にアクセスするための上記決定されたアドレスを示すデータを出力するように構成される。
【０００４】
これらのおよび他の実現例は、各々が任意に以下の特徴のうちの１つ以上を含み得る。例えば、上記特定の要素の上記アドレスは、上記Ｎ次元テンソルの別の要素からのアドレスオフセットであり得る。上記特定の要素の上記アドレスを決定するために、上記１つ以上のテンソルインデックス要素の各テンソルインデックス要素ごとに、それぞれのテンソルインデックス要素に記憶された値と上記１つ以上の複数のテンソルインデックス要素の上記対応するテンソルインデックス要素に記憶された値とが乗算されて、それぞれの乗算された値を生成し得る。上記アドレスオフセットは、上記乗算された値の合計を求めることによって決定され得る。
【０００５】
上記複数のテンソルインデックス要素は、テンソルインデックス要素のＭ個のグループに配置され得て、Ｍは、１よりも大きな正の整数である。テンソルインデックス要素の各グループは、別個の異なる多次元テンソルに割り当てられ得る。
【０００６】
上記装置は、複数のテンソル境界要素を含み得て、上記複数のテンソル境界要素の各々は、上記複数のテンソルインデックス要素における対応するテンソルインデックス要素を有し得る。上記命令は、第１のループと上記第１のループの外側ループである第２のループとを含む入れ子ループを処理するための命令を表わし得て、上記第１のループは、第１のインデックス変数を用いて反復され、上記第２のループは、第２のインデックス変数を用いて反復される。
【０００７】
上記１つ以上のプロセッサは、上記複数のテンソルインデックス要素、上記複数の次元乗数要素および上記複数のテンソル境界要素に記憶された値を初期化値に設定するように構成され得る。上記１つ以上のプロセッサは、上記複数のテンソル境界要素の第１のテンソル境界要素に記憶された値を、上記第１のループを反復するための上記第１のインデックス変数の上限値に設定するように構成され、上記複数のテンソル境界要素の第２のテンソル境界要素に記憶された値を、上記第２のループを反復するための上記第２のインデックス変数の上限値に設定するように構成され、上記複数の次元乗数要素の第１の次元乗数要素に記憶された値を、予め定められた値に設定するように構成され、上記複数の次元乗数要素の第２の次元乗数要素に記憶された値を、上記第１のインデックス変数の上記上限値に設定するように構成され得る。
【０００８】
上記Ｎ次元テンソルの上記要素の上記アドレスを決定するために、上記１つ以上のプロセッサは、上記複数のテンソルインデックス要素の第１のテンソルインデックス要素に記憶された値を、上記第１のインデックス変数の現在の値に設定するように構成され、上記複数のテンソルインデックス要素の第２のテンソルインデックス要素に記憶された値を、上記第２のインデックス変数の現在の値に設定するように構成され、上記第１の次元乗数要素に記憶された上記値と上記第１のテンソルインデックス要素に記憶された上記値とを乗算して、第１の乗算された値を取得するように構成され、上記第２の次元乗数要素に記憶された上記値と上記第２のテンソルインデックス要素に記憶された上記値とを乗算して、第２の乗算された値を取得するように構成され、上記第１の乗算された値および上記第２の乗算された値を少なくとも合計することによって上記アドレスを決定するように構成され得る。
【０００９】
上記１つ以上のプロセッサは、上記第１のテンソルインデックス要素に記憶された上記値を更新するための命令を受取るように構成され、上記第１のテンソルインデックス要素に記憶された上記値を更新するための上記命令を受取った後、上記第１のテンソルインデックス要素に記憶された上記値と上記第１のテンソル境界要素に記憶された上記値との間の差が閾値を満たすことを判断するように構成され、上記第１のテンソルインデックス要素に記憶された上記値と上記第１のテンソル境界要素に記憶された上記値との間の上記差が上記閾値を満たすと判断したことに応答して、上記第１のテンソルインデックス要素に記憶された上記値を更新するように構成され得る。上記第１のインデックス変数は、上記第１のループが完了するたびに第１のインクリメント値だけインクリメントされ得る。上記第１のテンソルインデックス要素に記憶された上記値を更新するために、上記第１のテンソルインデックス要素に記憶された上記値は、上記第１のインクリメント値だけインクリメントされ得る。
【００１０】
上記１つ以上のプロセッサは、上記第１のテンソルインデックス要素に記憶された上記値を更新するための命令を受取るように構成され、上記第１のテンソルインデックス要素に記憶された上記値を更新するための上記命令を受取った後、上記第１のテンソルインデックス要素に記憶された上記値と上記第１のテンソル境界要素に記憶された上記値との間の差が閾値を満たさないことを判断するように構成され得る。上記第１のテンソルインデックス要素に記憶された上記値と上記第１のテンソル境界要素に記憶された上記値との間の上記差が上記閾値を満たさないと判断したことに応答して、上記１つ以上のプロセッサは、上記第１のテンソルインデックス要素に記憶された上記値をリセットするように構成され、上記第２のテンソルインデックス要素に記憶された上記値を更新するように構成され得る。上記第２のインデックス変数は、上記第２のループが完了するたびに第２のインクリメント値だけインクリメントされ得る。上記第２のテンソルインデックス要素に記憶された上記値を更新するために、上記第２のテンソルインデックス要素に記憶された上記値は、上記第２のインクリメント値だけインクリメントされ得る。
【００１１】
上記１つ以上のプロセッサは、１つ以上の演算論理ユニットを含み得る。上記テンソルインデックス要素および上記次元乗数要素の各々は、レジスタであり得る。上記装置は、複数の分岐先要素を含み得て、上記複数の分岐先要素の各々は、上記複数のテンソルインデックス要素における対応するテンソルインデックス要素を有し、上記複数の分岐先要素の各々は、上記それぞれの分岐先要素に対応するループの反復が完了すると実行される命令のためのアドレスを記憶するように構成される。
【００１２】
本明細書に記載されている主題は、以下の利点のうちの１つ以上を達成するように特定の実施例で実現可能である。レジスタを用いてメモリアドレス値を追跡することにより、プログラムは、１つの命令で、深く入れ子にされたループを反復することができる。メモリアドレス値は、レジスタに記憶された値に基づいて単純な演算計算を適用することによって迅速に決定可能である。演算論理ユニットを用いてメモリアドレス値を決定することにより、プロセッサにおける計算サイクルの数を減少させることができ、他の計算タスクのためのプロセッサの帯域幅が増加する。命令の数を減少させた状態で、テンソルをトラバース（traverse）することができる。二次元レジスタアーキテクチャにより、各々が異なる次元を有する多次元テンソルを同時に追跡することができる。分岐先テーブルを有することによって、分岐命令関連のオーバーヘッドを減少させることができる。
【００１３】
このおよび他の側面の他の実現例は、コンピュータ記憶装置に符号化された方法の動作を実行するように構成された対応するシステム、装置およびコンピュータプログラムを含む。１つ以上のコンピュータのシステムは、動作時にシステムに動作を実行させる、システムにインストールされたソフトウェア、ファームウェア、ハードウェア、またはそれらの組み合わせによってそのように構成され得る。１つ以上のコンピュータプログラムは、データ処理装置によって実行されたときに装置に動作を実行させる命令を有することによってそのように構成され得る。
【００１４】
本明細書に記載されている主題の１つ以上の実現例の詳細は、添付の図面および以下の説明に記載されている。主題の他の考えられる特徴、側面および利点は、明細書、図面および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１５】
【図１】例示的な計算システムのブロック図である。
【図２Ａ】例示的なテンソルトラバースユニットを示す。
【図２Ｂ】例示的なテンソルトラバースユニットを示す。
【図２Ｃ】例示的なテンソルトラバースユニットを示す。
【図２Ｄ】例示的なテンソルトラバースユニットを示す。
【図２Ｅ】例示的なテンソルトラバースユニットを示す。
【図２Ｆ】例示的なテンソルトラバースユニットを示す。
【図２Ｇ】例示的なテンソルトラバースユニットを示す。
【図２Ｈ】例示的なテンソルトラバースユニットを示す。
【図３】例示的なテンソルトラバースユニットを示す。
【図４】多次元テンソル変数のアドレスを決定するためのプロセスの一例を示すフロー図である。
【発明を実施するための形態】
【００１６】
さまざまな図の中の同様の参照番号および名称は、同様の要素を示す。
詳細な説明
一般に、ソフトウェアアルゴリズムがＮ次元テンソルを処理する際には、入れ子ループが使用され得て、各ループは、Ｎ次元テンソルの各次元をトラバースする役割を果たしている。多次元テンソルは、マトリクスまたは多次元マトリクスであってもよい。Ｎ次元テンソルの各次元は、１つ以上の要素を含み得て、各要素は、それぞれのデータ値を記憶し得る。例えば、テンソルは、プログラムにおける変数であってもよく、当該変数は、３つの次元を有し得る。第１の次元は、３００個の要素の長さを有し得て、第２の次元は、１０００個の要素の長さを有し得て、第３の次元は、２０個の要素の長さを有し得る。入れ子ループにおいてテンソルをトラバースするには、要素の対応するデータ値をロードまたは記憶するために当該要素のメモリアドレス値の計算を必要とする。例えば、ｆｏｒループは入れ子ループであり、３つのループインデックス変数によって追跡される３つのループは、三次元テンソルをトラバースするように入れ子にされることができる。場合によっては、プロセッサは、外側ループインデックス変数により内側ループのループ境界を設定するなどのループ境界条件を実行する必要があるかもしれない。例えば、入れ子ループの最も内側のループを出るか否かを判断する際に、プログラムは、入れ子ループの最も内側のループのループインデックス変数の現在の値と、入れ子ループの最も外側のループのループインデックス変数の現在の値とを比較し得る。
【００１７】
これらのタスクは、分岐命令および整数演算命令などの相当な数の命令を必要とし得る。各ループ境界が小さく、ループの数が多い場合、計算は、実行時間全体の相当な部分を占めてパフォーマンス全体を著しく劣化させる恐れがある。例えば、プロセッサは、Ｎ次元テンソル入力を処理するように設計され得る。プロセッサは、二次元アーキテクチャ上で実現され得て、ソフトウェアによって処置されるべき（Ｎ−２）個の次元を残す。Ｎが大きい場合には、Ｎ−２個の次元の処理は、プロセッサにとって計算的に重い可能性がある。なぜなら、計算は非常に高いスカラ計算帯域幅を必要とするからである。プロセッサのためのハードウェアテンソルトラバースユニット（tensor traversal unit）は、テンソルをトラバースする際にプロセッサが処理しなければならない次元の数を減少させることによってプロセッサの計算帯域幅を増加させ得る。
【００１８】
図１は、テンソルをトラバースするための例示的な計算システム１００のブロック図を示す。一般に、計算システム１００は、入力１０４を処理して、出力１１６を生成する。計算システム１００は、線形代数計算を実行するように構成され得る。入力１０４は、計算システム１００によって処理されることができる任意の好適なデータであり得る。計算システム１００は、処理ユニット１０２と、記憶媒体１０４と、テンソルトラバースユニット１０６とを含む。
【００１９】
一般に、処理ユニット１０２がテンソルの特定の要素にアクセスするための命令を実行すると、テンソルトラバースユニット１０６は、当該テンソルの特定の要素のアドレスを決定し、その結果、処理ユニット１０２は、記憶媒体１０４にアクセスして、当該特定の要素の値を表わすデータ１１４を読取ることができる。例えば、プログラムは、入れ子ループを含み得て、処理ユニット１０２は、入れ子ループに関連付けられる現在のインデックス変数値に従って、入れ子ループ内の二次元配列変数の要素にアクセスするための命令を実行し得る。入れ子ループに関連付けられる現在のインデックス変数値に基づいて、テンソルトラバースユニット１０６は、二次元配列変数の第１の要素からのオフセットを表わすオフセット値を決定し得る。次いで、当該オフセット値を用いて、記憶媒体から、処理ユニット１０２は、二次元配列変数の特定の要素にアクセスし得る。
【００２０】
処理ユニット１０２は、記憶媒体１０４に記憶される命令１１２または別の記憶装置に記憶される他の命令を含む、計算システム１００内での実行のための命令を処理するように構成される。処理ユニット１０２は、１つ以上のプロセッサを含み得る。記憶媒体１０４は、計算システム１００内の情報を記憶する。いくつかの実現例では、記憶媒体１０４は、揮発性メモリユニットである。いくつかの他の実現例では、記憶媒体１０４は、不揮発性メモリユニットである。また、記憶媒体１０４は、フロッピー（登録商標）ディスクデバイス、ハードディスクデバイス、光ディスクデバイス、またはテープデバイス、フラッシュメモリもしくは他の同様のソリッドステートメモリデバイス、またはストレージエリアネットワークもしくは他の構成におけるデバイスを含むデバイスの配列などの、別の形態のコンピュータ読取可能な媒体であってもよい。命令は、処理ユニット１０２によって実行されたときに、処理ユニット１０２に１つ以上のタスクを実行させる。
【００２１】
テンソルトラバースユニット１０６は、１つ以上のテンソルに関連付けられるステータスを決定するように構成される。当該ステータスは、ループ境界値、現在のループインデックス変数値、メモリアドレス値を計算するための次元乗数、および／または、分岐ループ境界を処理するためのプログラムカウンタ値を含み得る。テンソルトラバースユニット１０６は、テンソルステータス要素１２２と、演算論理ユニット１２４とを含む。テンソルステータス要素１２２の各々は、記憶要素、例えばレジスタまたはその他の好適な記憶回路であってもよい。いくつかの実現例では、テンソルステータス要素１２２は、図２Ａ〜図２Ｈおよび図３Ａ〜図３Ｂを参照して以下でより詳細に説明するように、異なるグループに物理的または論理的に配置され得る。いくつかの実現例では、テンソルステータス要素１２２のグループは、多次元配列に物理的または論理的に配置され得る。例えば、テンソルステータス要素１２２の各グループは、二次元配列に物理的または論理的に配置されてもよい。演算論理ユニット１２４は、演算および論理オペレーションを実行するように構成された１つ以上の演算論理ユニット（arithmetic logic unit：ＡＬＵ）を含む。例えば、演算論理ユニット１２４は、加算、減算、乗算、除算、論理積、論理和、またはその他の好適な演算および論理オペレーションを実行するように構成されたデジタル回路を含んでもよい。
【００２２】
図２Ａは、テンソルトラバースユニットのテンソルステータス要素２００の例示的なセットを示す。テンソルステータス要素２００は、テンソルトラバースユニット１０６のテンソルステータス要素１２２に対応し得る。テンソルトラバースユニット２００は、テンソルインデックス要素２０２のグループと、テンソル境界要素２０４のグループと、次元乗数要素２０６のグループとを含む。テンソルインデックス要素２０２は、Ｍ個の行およびＮ個の列を有する二次元配列として物理的または論理的に配置され得て、ＭおよびＮは１以上の整数である。いくつかの実現例では、テンソルインデックス要素２０２の各行は、テンソルのためのテンソルインデックス情報を表わし得る。例えば、プログラムが２つの配列変数Ｖ１およびＶ２を規定する場合、テンソルトラバースユニットは、配列変数Ｖ１およびＶ２のためのテンソルインデックス情報をそれぞれ追跡するために行２０２ａおよび２０２ｂを割り当ててもよい。いくつかの実現例では、テンソルインデックス要素２０２の各列は、テンソルに関連付けられる入れ子ループインデックス変数値のためのテンソルインデックス情報を表わし得る。例えば、プログラムが変数Ｖ１にアクセスするための３つのループを有する入れ子ループを規定し、入れ子ループの各ループが入れ子ループインデックス変数ｉ、ｊおよびｋによって指標付けされる場合、テンソルトラバースユニットは、入れ子ループインデックス変数ｉ、ｊおよびｋをそれぞれ追跡するためにテンソルインデックス要素Ｘ１，１、Ｘ１，２およびＸ１，３を割り当ててもよい。テンソルインデックス情報については、以下の図２Ｄ〜図２Ｈを参照して以下でより詳細に説明する。
【００２３】
テンソル境界要素２０４は、テンソルインデックス要素２０２と同一の次元を有する二次元配列として物理的または論理的に配置され得て、テンソル境界要素２０４の各要素は、テンソルインデックス要素２０２における対応する要素を有する。いくつかの実現例では、テンソル境界要素２０４の各行は、テンソルのためのテンソル境界情報を表わし得る。例えば、プログラムが２つの配列変数Ｖ１およびＶ２を規定する場合、テンソルトラバースユニットは、配列変数Ｖ１およびＶ２のためのテンソル境界情報をそれぞれ追跡するために行２０４ａおよび２０４ｂを割り当ててもよい。いくつかの実現例では、テンソル境界要素２０４の各列は、テンソルに関連付けられる入れ子ループインデックス変数値のためのテンソル境界情報を表わし得る。例えば、プログラムが変数Ｖ１にアクセスするための３つのループを有する入れ子ループを規定し、入れ子ループの各ループが入れ子ループインデックス変数ｉ、ｊおよびｋによって指標付けされる場合、テンソルトラバースユニットは、入れ子ループインデックス変数ｉ、ｊおよびｋにそれぞれ関連付けられるテンソル境界情報を追跡するためにテンソル境界要素Ｙ１，１、Ｙ１，２およびＹ１，３を割り当ててもよい。テンソル境界情報については、以下の図２Ｃを参照して以下でより詳細に説明する。
【００２４】
次元乗数要素２０６は、テンソルインデックス要素２０２と同一の次元を有する二次元配列として物理的または論理的に配置され得て、次元乗数要素２０６の各要素は、テンソルインデックス要素２０２における対応する要素を有する。いくつかの実現例では、次元乗数要素２０６の各行は、テンソルのための次元乗数情報を表わし得る。例えば、プログラムが２つの配列変数Ｖ１およびＶ２を規定する場合、テンソルトラバースユニットは、配列変数Ｖ１およびＶ２のための次元乗数情報をそれぞれ追跡するために行２０６ａおよび２０６ｂを割り当ててもよい。いくつかの実現例では、次元乗数要素２０６の各列は、テンソルに関連付けられる入れ子ループインデックス変数値のための次元乗数情報を表わし得る。例えば、プログラムが変数Ｖ１にアクセスするための３つのループを有する入れ子ループを規定し、入れ子ループの各ループが入れ子ループインデックス変数ｉ、ｊおよびｋによって指標付けされる場合、テンソルトラバースユニットは、入れ子ループインデックス変数ｉ、ｊおよびｋにそれぞれ関連付けられる次元乗数情報を追跡するために次元乗数要素Ｚ１，１、Ｚ１，２およびＺ１，３を割り当ててもよい。次元乗数情報については、以下の図２Ｄを参照して以下でより詳細に説明する。
【００２５】
図２Ｂ〜図２Ｈは、テンソルステータス要素２００が、テンソルを処理するためにテンソルトラバースユニットによっていかに使用され得るかの一例を示す。図２Ｂを参照して、プログラム２１２は、記憶媒体１０４または処理ユニット１０２によって実行可能な別の記憶媒体に記憶され得る。プログラム２１２は、４という第１の次元と２という第２の次元とを有する文字配列変数Ｖを指定する。プログラム２１２は、変数Ｖをトラバースするための入れ子ｆｏｒループを指定し、ｆｏｒループは、入れ子ループインデックス変数ｉによって追跡される外側ループにおけるＶの第１の次元をトラバースし、入れ子ループインデックス変数ｊによって追跡される内側ループにおけるＶの第２の次元をトラバースする。いくつかの実現例では、テンソルステータス要素２００は、プログラムの開始時に初期化され得る。例えば、プロセッサは、テンソルステータス要素２００を初期化する命令「InitializeElements」を実行してもよい。当該命令は、プロセッサによって実行可能な命令セットのハードウェア命令であってもよい。いくつかの実現例では、初期化後、テンソルステータス要素２００の各要素は、予め定められた値に設定される。ここでは、初期化後、テンソルステータス要素２００の各要素は、ゼロに設定され得る。
【００２６】
図２Ｃは、プログラム２１２に従ったテンソル境界要素２０４におけるテンソル境界情報の設定を示す。例えば、プロセッサは、テンソル境界要素２０４におけるテンソル境界情報を設定する命令「SetTensorBound」を実行してもよい。いくつかの実現例では、テンソル境界情報は、対応する入れ子ループインデックス変数の上限を表わす。ここでは、内側入れ子ループインデックス変数ｉは４という上限を有し、外側入れ子ループインデックス変数ｊは２という上限を有する。テンソル境界要素２０４におけるテンソル境界情報を設定した後、要素２１４（すなわちＹ１，２）は４に設定され、要素２１６（すなわちＹ１，１）は２に設定される。
【００２７】
図２Ｄは、プログラム２１２に従った次元乗数要素２０６における次元乗数情報の設定を示す。例えば、プロセッサは、次元乗数要素２０６における次元乗数情報を設定する命令「SetDimensionMultiplier」を実行してもよい。いくつかの実現例では、次元乗数情報は、テンソルインデックス要素２０２における対応する要素が乗算され得る乗数を表わす。ここでは、文字変数Ｖは、４という第１の次元と、２という第２の次元とを有する。要素Ｖ［０］［０］がベースメモリアドレスＰに記憶され、要素Ｖ［０］［１］がメモリアドレスＰ＋１に記憶される場合、要素Ｖ［１］［０］はメモリアドレスＰ＋２に記憶される。したがって、要素Ｖ［ｉ］［ｊ］のための対応するメモリアドレスは、Ｐ＋（ｉ×２）＋（ｊ×１）である。したがって、外側ループのための次元乗数情報は２であり、内側ループのための次元乗数情報は１である。次元乗数要素２０６における次元乗数情報を設定した後、要素２２２（すなわちＺ１，２）は２に設定され、要素２２４（すなわちＺ１，１）は１に設定される。
【００２８】
図２Ｅは、プログラム２１２に従った要素Ｖ［０］［０］へのアクセスを示す。例えば、プロセッサは、アクセスされている要素に対応するメモリアドレスの位置を突き止める命令「LocateTensor」を実行してもよい。いくつかの実現例では、当該命令は、ベースメモリアドレスを含み得る。例えば、命令「LocateTensor」は、変数Ｖの第１の要素である要素Ｖ［０］［０］のメモリアドレスを含み得る。いくつかの実現例では、当該命令は、アクセスされるべきテンソルに対応する行番号を含み得る。例えば、命令「LocateTensor」は、変数Ｖに対応する行番号を含んでもよい。ここでは、行番号は１である。
【００２９】
いくつかの実現例では、命令を受取ったことに応答して、演算論理ユニット（例えば演算論理ユニット１０６）は、テンソルインデックス要素２０２の各々に記憶された値と対応する次元乗数要素２０６に記憶された値との間の乗算結果の合計を計算することによって、メモリアドレスオフセットを決定する。ここでは、演算論理ユニットは、要素Ｘ１，Ｎに記憶された値と要素Ｚ１，Ｎに記憶された値とを乗算し、要素Ｘ１，Ｎ−１に記憶された値と要素Ｚ１，Ｎ−１に記憶された値とを乗算し、...要素Ｘ１，２に記憶された値と要素Ｚ１，２に記憶された値とを乗算し、要素Ｘ１，１に記憶された値と要素Ｚ１，１に記憶された値とを乗算する。次いで、演算論理ユニットは、全ての乗算結果を合計して、アクセスされている要素に対応するメモリアドレスを決定する。テンソルインデックス要素２０２における全ての値がゼロであるので、ボックス２３０によって示されるようにメモリアドレスオフセットはゼロである。次いで、プロセッサは、ベースメモリアドレス（すなわちＰ）をメモリアドレスオフセット（すなわち０）に加算してメモリアドレスを決定し、決定されたメモリアドレスに基づいて記憶媒体に記憶されたデータにアクセスすることによって、要素Ｖ［０］［０］にアクセスすることができる。
【００３０】
図２Ｆは、プログラム２１２に従った要素Ｖ［０］［１］へのアクセスを示す。例えば、プログラムが第１の内側ループを反復した後、入れ子ループインデックス変数は更新され（すなわちｉ＝０およびｊ＝０）、プロセッサは、プログラムが第２の内側ループに入ったときにテンソルインデックス要素２０２を更新する（すなわちｉ＝０およびｊ＝１）命令「IterateTensor」を実行してもよい。いくつかの実現例では、テンソルトラバースユニットは、最低のインデックスを有するテンソルインデックス要素を予め定められた値だけインクリメントすることによってテンソルインデックス要素２０２を更新する。例えば、図２Ｆを参照して、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１,１）を１だけインクリメントしてもよい。いくつかの他の実現例では、テンソルトラバースユニットは、最低のインデックスを有するテンソルインデックス要素を予め定められた値だけデクリメントすることによってテンソルインデックス要素２０２を更新してもよい。
【００３１】
いくつかの実現例では、テンソルトラバースユニットは、テンソルインデックス要素２０２における更新された値とテンソル境界要素２０４における値とを比較し、閾値が満たされたか否かを判断する。例えば、テンソルトラバースユニットは、テンソルインデックス要素２２８における更新された値（すなわち１）とテンソル境界要素２１６における値（すなわち２）とを比較し、テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さいか否かを判断してもよい。ここでは、テンソルインデックス要素２２８における更新された値は、テンソル境界要素２１６における値よりも小さく、テンソルインデックス要素２２８における更新された値は１のままである。
【００３２】
次いで、プロセッサは、Ｖ［０］［１］に対応するメモリアドレスの位置を突き止めるための命令「LocateTensor」を実行することによって要素Ｖ［０］［１］にアクセスすることができる。図２Ｆを参照して、テンソルインデックス要素２２８以外のテンソルインデックス要素２０２における全ての値は、ゼロである。テンソルインデックス要素２２８は１という値を有し、演算論理ユニットは、ボックス２３２によって示されるようにメモリアドレスオフセットが１であると判断し得る。次いで、プロセッサは、ベースメモリアドレス（すなわちＰ）をメモリアドレスオフセット（すなわち１）に加算してメモリアドレスを決定し、決定されたメモリアドレスに基づいて記憶媒体に記憶されたデータにアクセスすることによって、要素Ｖ［０］［１］にアクセスすることができる。
【００３３】
図２Ｇは、プログラム２１２に従った要素Ｖ［１］［０］へのアクセスを示す。例えば、プログラムが二度目に内側ループを反復した後、入れ子ループインデックス変数は更新され（すなわちｉ＝１およびｊ＝０）、プロセッサは、テンソルインデックス要素２０２を更新する命令「IterateTensor」を実行してもよい。例えば、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１，１）を１だけインクリメントしてもよい。テンソルトラバースユニットは、テンソルインデックス要素２２８における更新された値（すなわち２）とテンソル境界要素２１６における値（すなわち２）とを比較し、テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないと判断し得る。いくつかの実現例では、閾値が満たされていないと判断したことに応答して、テンソルトラバースユニットは、更新された値を次のテンソルインデックス要素に繰り越して、現在のテンソルインデックス要素をリセットし得る。例えば、テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないので、テンソルトラバースユニットは、テンソルインデックス要素２２６を１だけインクリメントし、テンソルインデックス要素２２８をゼロにリセットしてもよい。
【００３４】
次いで、プロセッサは、Ｖ［１］［０］に対応するメモリアドレスの位置を突き止めるための命令「LocateTensor」を実行することによって要素Ｖ［１］［０］にアクセスすることができる。図２Ｇを参照して、テンソルインデックス要素２２６以外のテンソルインデックス要素２０２における全ての値は、ゼロである。テンソルインデックス要素２２６は１という値を有し、演算論理ユニットは、ボックス２３４によって示されるようにメモリアドレスオフセットが２であると判断し得る。次いで、プロセッサは、ベースメモリアドレス（すなわちＰ）をメモリアドレスオフセット（すなわち２）に加算してメモリアドレスを決定し、決定されたメモリアドレスに基づいて記憶媒体に記憶されたデータにアクセスすることによって、要素Ｖ［１］［０］にアクセスすることができる。
【００３５】
図２Ｈは、プログラム２１２に従った要素Ｖ［３］［１］へのアクセスを示す。例えば、プログラムは、入れ子ループインデックス変数がそれらの上限にくる（すなわちｉ＝３およびｊ＝１）まで内側ループおよび外側ループを反復し続けてもよい。プロセッサは、Ｖ［３］［１］に対応するメモリアドレスの位置を突き止めるための命令「LocateTensor」を実行することによって要素Ｖ［３］［１］にアクセスすることができる。図２Ｈを参照して、テンソルインデックス要素２２６および２２８以外のテンソルインデックス要素２０２における全ての値は、ゼロである。テンソルインデックス要素２２６は３という値を有し、テンソルインデックス要素２２８は１という値を有する。演算論理ユニットは、ボックス２３６によって示されるようにメモリアドレスオフセットが７であると判断し得る。次いで、プロセッサは、ベースメモリアドレス（すなわちＰ）をメモリアドレスオフセット（すなわち７）に加算してメモリアドレスを決定し、決定されたメモリアドレスに基づいて記憶媒体に記憶されたデータにアクセスすることによって、要素Ｖ［３］［１］にアクセスすることができる。
【００３６】
次いで、プロセッサは、テンソルインデックス要素２０２を更新する命令「IterateTensor」を実行し得る。例えば、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１，１）を１だけインクリメントしてもよい。テンソルトラバースユニットは、テンソルインデックス要素２２８における更新された値（すなわち２）とテンソル境界要素２１６における値（すなわち２）とを比較し、テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないと判断し得る。テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないので、テンソルトラバースユニットは、テンソルインデックス要素２２６を１だけインクリメントし、テンソルインデックス要素２２８をゼロにリセットし得る。テンソルトラバースユニットは、テンソルインデックス要素２２６における更新された値（すなわち３＋１＝４）とテンソル境界要素２１４における値（すなわち４）とを比較し、テンソルインデックス要素２２６における更新された値がテンソル境界要素２１４における値よりも小さくないと判断し得る。テンソルインデックス要素２２８における更新された値がテンソル境界要素２１４における値よりも小さくないので、テンソルトラバースユニットは、次のテンソルインデックス要素（すなわちＸ１，３）を１だけインクリメントし、テンソルインデックス要素２２６をゼロにリセットし得る。しかし、対応するテンソル境界要素（すなわちＹ１，３）がゼロであるので、閾値は満たされない。テンソルトラバースユニットは、第１の行における全てのテンソルインデックス要素がゼロにリセットされるまでテンソルインデックス要素２０２の第１の行をリセットし続けるであろう。
【００３７】
図２Ｂ〜図２Ｈを参照して上記した例では、要素Ｖのためのテンソルトラバースの順序は、Ｖ［０］［０］、Ｖ［０］［１］、Ｖ［１］［０］、Ｖ［１］［１］、Ｖ［２］［０］、Ｖ［２］［１］、Ｖ［３］［０］およびＶ［３］［１］である。いくつかの実現例では、プログラムは、要素２１４（すなわちＹ１，２）におけるテンソル境界情報を２に設定し、要素２１６（すなわちＹ１，１）におけるテンソル境界情報を４に設定し、要素２２２（すなわちＺ１，２）における次元乗数情報を１に設定し、要素２２４（すなわちＺ１，１）における次元乗数情報を２に設定することによって、Ｖ［０］［０］、Ｖ［１］［０］、Ｖ［２］［０］、Ｖ［３］［０］、Ｖ［０］［１］、Ｖ［１］［１］、Ｖ［２］［１］およびＶ［３］［１］の順序で要素Ｖをトラバースし得る。
【００３８】
図３は、テンソルトラバースユニットのテンソルステータス要素３００の例示的なセットを示す。テンソルステータス要素３００は、テンソルトラバースユニット１０６のテンソルステータス要素１２２またはテンソルステータス要素２００に対応し得る。テンソルトラバースユニット３００は、テンソルインデックス要素３０２のグループと、テンソル境界要素３０４のグループと、次元乗数要素３０６のグループと、分岐先要素３０８のグループとを含む。分岐先要素３０８は、二次元配列として物理的または論理的に配置され得て、分岐先要素３０８の各要素は、テンソルインデックス要素３０２における対応する要素を有する。いくつかの実現例では、分岐先要素３０８の各行は、テンソルのための分岐先情報を表わし得る。いくつかの実現例では、分岐先要素３０８の各列は、テンソルに関連付けられる入れ子ループインデックス変数値のための分岐先情報を表わし得る。いくつかの実現例では、テンソルインデックス要素３０２、テンソル境界要素３０４および次元乗数要素３０６のためにＮ個の列が存在するＮ次元テンソルでは、対応する分岐先３０８のＮ＋１個の列が存在し得る。なぜなら、境界閾値を満たすためのＮ＋１個の場合があるからである。
【００３９】
いくつかの実現例では、分岐先情報は、入れ子ループでのループ反復が完了するとプロセッサによって実行される命令のメモリアドレスを含み得る。例えば、テンソルインデックス要素における値が更新されると、プロセッサは、対応する分岐先要素に記憶されたメモリアドレスに従って命令を実行してもよい。図３を参照して、プログラム３１２は、記憶媒体１０４または処理ユニット１０２によって実行可能な別の記憶媒体に記憶され得る。プログラム３１２は、４という第１の次元と２という第２の次元とを有する文字配列変数Ｖを指定する。プログラム３１２は、変数Ｖをトラバースするための入れ子ｆｏｒループを指定し、ｆｏｒループは、入れ子ループインデックス変数ｉによって追跡される外側ループにおけるＶの第１の次元をトラバースし、入れ子ループインデックス変数ｊによって追跡される内側ループにおけるＶの第２の次元をトラバースする。また、プログラム３１２は、プロセッサが入れ子ループインデックス変数ｉの現在の値と数２とを比較するための最小値関数命令を実行することを必要とする、内側ループを出るための条件を指定する。いくつかの実現例では、最小値関数命令のメモリアドレスは、分岐先要素３２４に記憶され得て、その結果、テンソルインデックス要素３２６からテンソルインデックス要素３２８への繰り越しがある場合には、最小値関数命令は、内側ループのための分岐条件を決定して内側ループのためのテンソル境界情報を設定するようにプロセッサによって実行されるであろう。同様に、異なる命令のメモリアドレスは、分岐先要素３２２に記憶され得て、その結果、テンソルインデックス要素３２８への繰り越しを有することなくテンソルインデックス要素３２６においてインクリメントがある場合には、当該異なる命令がプロセッサによって実行されるであろう。
【００４０】
図４は、多次元テンソル変数のアドレスを決定するためのプロセス４００の一例を示すフロー図である。プロセス４００は、１つ以上のコンピュータのシステム、例えば計算システム１００によって実行され得る。当該システムは、複数のテンソルインデックス要素と複数の次元乗数要素とを有するテンソルトラバースユニットを含み、次元乗数要素の各々は、対応するテンソルインデックス要素を有する。いくつかの実現例では、当該システムは、複数のテンソル境界要素を含み得て、複数のテンソル境界要素の各々は、複数のテンソルインデックス要素における対応するテンソルインデックス要素を有し得る。いくつかの実現例では、当該システムは、１つ以上の演算論理ユニットを含む。
【００４１】
当該システムは、Ｎ次元テンソルの特定の要素にアクセスするための命令を取得し、Ｎ次元テンソルは、Ｎ次元の各々にわたって配置された複数の要素を有し、Ｎは１以上の整数である（４０２）。例えば、処理ユニット１０２は、テンソルの特定の要素にアクセスするための命令を実行してもよい。
【００４２】
いくつかの実現例では、当該命令は、第１のループと第１のループの外側ループである第２のループとを含む入れ子ループを処理するための命令を表わし得て、第１のループは、第１のインデックス変数を用いて反復され、第２のループは、第２のインデックス変数を用いて反復される。例えば、プログラム２１２は、記憶媒体１０４または処理ユニット１０２によって実行可能な別の記憶媒体に記憶されてもよい。プログラム２１２は、４という第１の次元と２という第２の次元とを有する文字配列変数Ｖを指定し得る。プログラム２１２は、変数Ｖをトラバースするための入れ子ｆｏｒループを指定し得て、ｆｏｒループは、入れ子ループインデックス変数ｉによって追跡される外側ループにおけるＶの第１の次元をトラバースし、入れ子ループインデックス変数ｊによって追跡される内側ループにおけるＶの第２の次元をトラバースする。
【００４３】
当該システムは、複数のテンソルインデックス要素のうちの１つ以上のテンソルインデックス要素および複数の次元乗数要素のうちの１つ以上の次元乗数要素を用いて、特定の要素のアドレスを決定する（４０４）。いくつかの実現例では、特定の要素のアドレスは、Ｎ次元テンソルの別の要素からのアドレスオフセットであってもよい。１つ以上のテンソルインデックス要素の各テンソルインデックス要素ごとに、当該システムは、それぞれのテンソルインデックス要素に記憶された値と、１つ以上の複数のテンソルインデックス要素の対応するテンソルインデックス要素に記憶された値とを乗算して、それぞれの乗算された値を生成し得る。当該システムは、乗算された値の合計を求めることによってアドレスオフセットを決定し得る。例えば、演算論理ユニット（例えば演算論理ユニット１０６）は、テンソルインデックス要素２０２の各々に記憶された値と対応する次元乗数要素２０６に記憶された値との間の乗法積の合計を計算することによって、メモリアドレスオフセットを決定してもよい。
【００４４】
いくつかの実現例では、当該システムは、複数のテンソルインデックス要素、複数の次元乗数要素および複数のテンソル境界要素に記憶された値を初期化値に設定し得る。例えば、プロセッサは、テンソルステータス要素２００を初期化する命令「InitializeElements」を実行してもよい。初期化後、テンソルステータス要素２００の各要素は、ゼロに設定され得る。
【００４５】
いくつかの実現例では、当該システムは、複数のテンソル境界要素の第１のテンソル境界要素に記憶された値を、第１のループを反復するための第１のインデックス変数の上限値に設定し得る。当該システムは、複数のテンソル境界要素の第２のテンソル境界要素に記憶された値を、第２のループを反復するための第２のインデックス変数の上限値に設定し得る。例えば、プロセッサは、テンソルステータス要素２００を初期化する命令「InitializeElements」を実行してもよい。初期化後、テンソルステータス要素２００の各要素は、ゼロに設定され得る。当該システムは、複数の次元乗数要素の第１の次元乗数要素に記憶された値を予め定められた値に設定し得る。当該システムは、複数の次元乗数要素の第２の次元乗数要素に記憶された値を第１のインデックス変数の上限値に設定し得る。例えば、プロセッサは、テンソル境界要素２０４におけるテンソル境界情報を設定する命令「SetTensorBound」を実行してもよい。テンソル境界要素２０４におけるテンソル境界情報を設定した後、要素２１４（すなわちＹ１，２）は４に設定され、要素２１６（すなわちＹ１，１）は２に設定される。
【００４６】
いくつかの実現例では、当該システムは、複数のテンソルインデックス要素の第１のテンソルインデックス要素に記憶された値を第１のインデックス変数の現在の値に設定し得る。当該システムは、複数のテンソルインデックス要素の第２のテンソルインデックス要素に記憶された値を第２のインデックス変数の現在の値に設定し得る。当該システムは、第１の次元乗数要素に記憶された値と、第１のテンソルインデックス要素に記憶された値とを乗算して、第１の乗算された値を取得し得る。当該システムは、第２の次元乗数要素に記憶された値と、第２のテンソルインデックス要素に記憶された値とを乗算して、第２の乗算された値を取得し得る。当該システムは、第１の乗算された値と第２の乗算された値とを少なくとも合計することによってアドレスを決定し得る。例えば、演算論理ユニットは、要素Ｘ１，Ｎに記憶された値と要素Ｚ１，Ｎに記憶された値とを乗算し、要素Ｘ１，Ｎ−１に記憶された値と要素Ｚ１，Ｎ−１に記憶された値とを乗算し、...要素Ｘ１，２に記憶された値と要素Ｚ１，２に記憶された値とを乗算し、要素Ｘ１，１に記憶された値と要素Ｚ１，１に記憶された値とを乗算する。次いで、演算論理ユニットは、全ての乗算された積を合計して、アクセスされている要素に対応するメモリアドレスを決定する。
【００４７】
いくつかの実現例では、当該システムは、第１のテンソルインデックス要素に記憶された値を更新するための命令を受取り得る。例えば、プロセッサは、テンソルインデックス要素２０２を更新する命令「IterateTensor」を実行してもよい。第１のテンソルインデックス要素に記憶された値を更新するための命令を受取った後、当該システムは、第１のテンソルインデックス要素に記憶された値と第１のテンソル境界要素に記憶された値との間の差が閾値を満たすと判断し得る。第１のテンソルインデックス要素に記憶された値と第１のテンソル境界要素に記憶された値との間の差が閾値を満たすと判断したことに応答して、当該システムは、第１のテンソルインデックス要素に記憶された値を更新し得る。例えば、図２Ｆを参照して、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１，１）を１だけインクリメントしてもよい。テンソルインデックス要素２２８における更新された値は、テンソル境界要素２１６における値よりも小さく、テンソルインデックス要素２２８における更新された値は、１のままである。
【００４８】
いくつかの実現例では、第１のインデックス変数は、第１のループが完了するたびに第１のインクリメント値だけインクリメントされ得る。当該システムは、第１のテンソルインデックス要素に記憶された値を第１のインクリメント値だけインクリメントし得る。例えば、プログラムが第２の内側ループに入った（すなわちｉ＝０およびｊ＝１）後、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１，１）を１だけインクリメントしてもよい。
【００４９】
いくつかの実現例では、当該システムは、第１のテンソルインデックス要素に記憶された値を更新するための命令を受取り得る。例えば、プロセッサは、テンソルインデックス要素２０２を更新する命令「IterateTensor」を実行してもよい。第１のテンソルインデックス要素に記憶された値を更新するための命令を受取った後、当該システムは、第１のテンソルインデックス要素に記憶された値と第１のテンソル境界要素に記憶された値との間の差が閾値を満たさないと判断し得る。第１のテンソルインデックス要素に記憶された値と第１のテンソル境界要素に記憶された値との間の差が閾値を満たさないと判断したことに応答して、当該システムは、第１のテンソルインデックス要素に記憶された値をリセットし、第２のテンソルインデックス要素に記憶された値を更新し得る。例えば、テンソルトラバースユニットは、テンソルインデックス要素２２８（すなわちＸ１，１）を１だけインクリメントしてもよい。テンソルトラバースユニットは、テンソルインデックス要素２２８における更新された値（すなわち２）とテンソル境界要素２１６における値（すなわち２）とを比較し、テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないと判断し得る。テンソルインデックス要素２２８における更新された値がテンソル境界要素２１６における値よりも小さくないので、テンソルトラバースユニットは、テンソルインデックス要素２２６を１だけインクリメントし、テンソルインデックス要素２２８をゼロにリセットし得る。
【００５０】
いくつかの実現例では、第２のインデックス変数は、第２のループが完了するたびに第２のインクリメント値だけインクリメントされ得る。当該システムは、第２のテンソルインデックス要素に記憶された値を第２のインクリメント値だけインクリメントし得る。例えば、プログラムが外側ループの次のループに入った（すなわちｉ＝１およびｊ＝０）後、テンソルトラバースユニットは、テンソルインデックス要素２２６（すなわちＸ１，２）を１だけインクリメントしてもよい。
【００５１】
当該システムは、Ｎ次元テンソルの特定の要素にアクセスするための決定されたアドレスを示すデータを出力する（４０６）。例えば、処理ユニット１０２は、メモリアドレスオフセット値を用いて、記憶媒体におけるＮ次元配列変数の特定の要素にアクセスしてもよい。
【００５２】
いくつかの実現例では、当該システムは、複数の分岐先要素を含み、複数の分岐先要素の各々は、複数のテンソルインデックス要素における対応するテンソルインデックス要素を有し、複数の分岐先要素の各々は、それぞれの分岐先要素に対応するループの反復が完了すると実行される命令のためのアドレスを記憶するように構成される。例えば、テンソルトラバースユニット３００は、分岐先情報を記憶する分岐先要素３０８のグループを含む。分岐先情報は、入れ子ループのループ反復が完了するとプロセッサによって実行される命令のメモリアドレスを含み得る。
【００５３】
本明細書に記載されている主題および機能的オペレーションの実施例は、デジタル電子回路、有形に具体化されたコンピュータソフトウェアもしくはファームウェア、本明細書に開示された構造およびそれらの構造的等価物を含むコンピュータハードウェア、またはそれらのうちの１つ以上の組み合わせで実現可能である。本明細書に記載されている主題の実施例は、１つ以上のコンピュータプログラムとして、すなわち有形の非一時的なプログラムキャリア上で符号化されてデータ処理装置によって実行されるかまたはデータ処理装置のオペレーションを制御するためのコンピュータプログラム命令の１つ以上のモジュールとして実現可能である。代替的にまたは加えて、プログラム命令は、情報を符号化して好適な受信機装置に送信してデータ処理装置によって実行されるように生成される人為的に生成された伝搬信号、例えばマシンによって生成される電気信号、光信号または電磁信号上で符号化されてもよい。コンピュータ記憶媒体は、マシン読取可能な記憶装置、マシン読取可能な記憶基板、ランダムもしくはシリアルアクセスメモリデバイス、またはそれらのうちの１つ以上の組み合わせであってもよい。
【００５４】
「データ処理装置」という用語は、データを処理するための全ての種類の装置、デバイスおよびマシンを包含し、一例としてプログラム可能なプロセッサ、コンピュータ、または複数のプロセッサもしくはコンピュータを含む。当該装置は、特殊用途論理回路、例えばＦＰＧＡ（フィールドプログラマブルゲートアレイ）またはＡＳＩＣ（特定用途向け集積回路）を含んでもよい。また、当該装置は、ハードウェアに加えて、対象のコンピュータプログラムのための実行環境を作り出すコード、例えばプロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの１つ以上の組み合わせを構成するコードを含んでもよい。
【００５５】
コンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、モジュール、ソフトウェアモジュール、スクリプト、またはコードとも称され、そのようなものとしても記載され得る）は、コンパイラ型言語もしくはインタープリタ型言語、または宣言型言語または手続き型言語を含む任意の形態のプログラミング言語で書込まれてもよく、スタンドアロン型プログラムまたはモジュール、コンポーネント、サブルーチンもしくは計算環境での使用に好適な他のユニットを含む任意の形態で配備されてもよい。コンピュータプログラムは、ファイルシステムにおけるファイルに対応してもよいが、対応する必要はない。プログラムは、他のプログラムもしくはデータを保持するファイルの一部、例えばマークアップ言語ドキュメントに記憶された１つ以上のスクリプトに記憶されてもよく、対象のプログラムに専用の単一のファイルに記憶されてもよく、または複数の調整されたファイル、例えば１つ以上のモジュール、サブプログラムもしくはコードの一部を記憶するファイルに記憶されてもよい。コンピュータプログラムは、１つのコンピュータで実行されるように配備されてもよく、または１箇所に位置するかもしくは複数の箇所に分散されて通信ネットワークよって相互接続されている複数のコンピュータで実行されるように配備されてもよい。
【００５６】
本明細書に記載されているプロセスおよび論理フローは、入力データ上で動作して出力を生成することによって機能を実行するように１つ以上のコンピュータプログラムを実行する１つ以上のプログラム可能なコンピュータによって実行されてもよい。また、当該プロセスおよび論理フローは、特殊用途論理回路、例えばＦＰＧＡ（フィールドプログラマブルゲートアレイ）、ＡＳＩＣ（特定用途向け集積回路）またはＧＰＧＰＵ（汎用グラフィックス処理ユニット）によって実行されてもよく、そのようなものとして装置が実現されてもよい。
【００５７】
コンピュータプログラムの実行に好適なコンピュータは、一例として、汎用マイクロプロセッサもしくは特殊用途マイクロプロセッサに基づいてもよく、またはそれら両方に基づいてもよく、またはその他の種類の中央処理装置に基づいてもよい。一般に、中央処理装置は、リードオンリメモリまたはランダムアクセスメモリまたはそれら両方から命令およびデータを受取るであろう。コンピュータの不可欠な要素は、命令を実施または実行するための中央処理装置と、命令およびデータを記憶するための１つ以上のメモリデバイスとである。一般に、コンピュータは、データを記憶するための１つ以上の大容量記憶装置、例えば磁気ディスク、光磁気ディスクまたは光ディスクも含み、または当該１つ以上の大容量記憶装置からデータを受取るか当該１つ以上の大容量記憶装置にデータを転送するように、もしくはデータの受取りも転送も行うように作動的に結合されるであろう。しかし、コンピュータは、このような装置を有する必要はない。さらに、コンピュータは、別の装置、例えば数例を挙げると、携帯電話、パーソナルデジタルアシスタント（personal digital assistant：ＰＤＡ）、携帯型オーディオもしくはビデオプレーヤ、ゲーム機、グローバルポジショニングシステム（Global Positioning System：ＧＰＳ）受信機、または携帯記憶装置、例えばユニバーサルシリアルバス（universal serial bus：ＵＳＢ）フラッシュドライブに組み込まれてもよい。
【００５８】
コンピュータプログラム命令およびデータの記憶に好適なコンピュータ読取可能な媒体は、全ての形態の不揮発性メモリ、媒体およびメモリデバイスを含み、一例として、例えばＥＰＲＯＭ、ＥＥＰＲＯＭおよびフラッシュメモリデバイスといった半導体メモリデバイス、例えば内部ハードディスクまたはリムーバブルディスクといった磁気ディスク、光磁気ディスク、ならびにＣＤ  ＲＯＭおよびＤＶＤ−ＲＯＭディスクを含む。プロセッサおよびメモリは、特殊用途論理回路によって補完されてもよく、または特殊用途論理回路に組み入れられてもよい。
【００５９】
ユーザとの対話を提供するために、本明細書に記載されている主題の実施例は、情報をユーザに表示するためのディスプレイ装置、例えばＣＲＴ（陰極線管）またはＬＣＤ（液晶ディスプレイ）モニタと、キーボードと、ユーザが入力をコンピュータに提供することができるポインティング装置、例えばマウスまたはトラックボールとを有するコンピュータ上で実現可能である。ユーザとの対話を提供するために他の種類の装置も使用可能である。例えば、ユーザに提供されるフィードバックは、任意の形態の感覚フィードバック、例えば視覚的フィードバック、聴覚的フィードバックまたは触知可能なフィードバックであってもよく、ユーザからの入力は、音響入力、音声入力または触知可能な入力を含む任意の形態で受取られてもよい。また、コンピュータは、ユーザによって使用される装置にドキュメントを送信し、当該装置からドキュメントを受信することによって、例えばユーザのクライアント装置上のウェブブラウザから受取られた要求に応答して当該ウェブブラウザにウェブページを送信することによって、ユーザと対話してもよい。
【００６０】
本明細書に記載されている主題の実施例は、バックエンドコンポーネントを含む計算システムにおいて、例えばデータサーバとして実現されてもよく、またはミドルウェアコンポーネント、例えばアプリケーションサーバを含む計算システムにおいて実現されてもよく、フロントエンドコンポーネント、例えばユーザが本明細書に記載されている主題の実現例と対話することができるグラフィカルユーザインターフェイスもしくはウェブブラウザを有するクライアントコンピュータを含む計算システムにおいて実現されてもよく、または１つ以上のこのようなバックエンド、ミドルウェアまたはフロントエンドコンポーネントの任意の組み合わせを含む計算システムで実現されてもよい。システムのコンポーネントは、デジタルデータ通信、例えば通信ネットワークの任意の形態または媒体によって相互接続されてもよい。通信ネットワークの例としては、ローカルエリアネットワーク（「ＬＡＮ」）および広域ネットワーク（「ＷＡＮ」）、例えばインターネットが挙げられる。
【００６１】
計算システムは、クライアントとサーバとを含み得る。クライアントおよびサーバは、一般に、互いに離れており、典型的には通信ネットワークを介して対話する。クライアントとサーバとの関係は、それぞれのコンピュータで実行されて互いに対するクライアントとサーバとの関係を有するコンピュータプログラムによって生じる。
【００６２】
本明細書は多くの具体的な実現例の詳細を含むが、これらは、いかなる発明の範囲も限定するものとして解釈されるべきではなく、またはクレームされ得るものの範囲を限定するものとして解釈されるべきではなく、特定の発明の特定の実施例に特有であり得る特徴の説明として解釈されるべきである。別々の実施例の文脈で本明細書に記載されている特定の特徴は、単一の実施例において組み合わせて実現されてもよい。逆に、単一の実施例の文脈で記載されているさまざまな特徴は、複数の実施例で別々に実現されてもよく、または任意の好適なサブコンピネーションで実現されてもよい。さらに、特徴は、特定の組み合わせで作動するものとして、さらにはそのように最初にクレームされたものとして上記され得るが、クレームされている組み合わせからの１つ以上の特徴は、場合によっては、当該組み合わせから削除されてもよく、クレームされている組み合わせは、サブコンビネーションまたはサブコンビネーションの変形例に向けられてもよい。
【００６３】
同様に、オペレーションは特定の順序で図面に示されているが、これは、このようなオペレーションが、望ましい結果を達成するために、示されている特定の順序またはシーケンシャルな順序で実行されなければならないものとして理解されるべきではなく、または、望ましい結果を達成するために全ての示されているオペレーションが実行されなければならないものとして理解されるべきではない。特定の状況では、マルチタスクおよび並列処理が有利であろう。さらに、上記の実施例におけるさまざまなシステムモジュールおよびコンポーネントの分離は、全ての実施例においてこのような分離が必要であるものとして理解されるべきではなく、記載されているプログラムコンポーネントおよびシステムは、一般に、単一のソフトウェア製品に統合されてもよく、または複数のソフトウェア製品にパッケージングされてもよい、ということが理解されるべきである。
【００６４】
主題の特定の実施例について説明してきた。他の実施例も以下の特許請求の範囲の範囲内である。例えば、特許請求の範囲に記載されている動作は、異なる順序で実行されても、依然として望ましい結果を達成することができる。一例として、添付の図面に示されているプロセスは、望ましい結果を達成するために、示されている特定の順序またはシーケンシャルな順序を必ずしも必要としない。特定の実現例では、マルチタスクおよび並列処理が有利であろう。
【符号の説明】
【００６５】
１００  計算システム；１０２  処理ユニット；１０４  記憶媒体；１０４  入力；１０６  テンソルトラバースユニット；１１２  命令；１１４  データ；１１６  出力；１２２  テンソルステータス要素；１２４  演算論理ユニット；２０２、３０２  テンソルインデックス要素；２０４、３０４  テンソル境界要素；２０６、３０６  次元乗数要素；３０８  分岐先要素。
【図１】
2017138964.tif 000003
【図２Ａ】
2017138964.tif 000004
【図２Ｂ】
2017138964.tif 000005
【図２Ｃ】
2017138964.tif 000006
【図２Ｄ】
2017138964.tif 000007
【図２Ｅ】
2017138964.tif 000008
【図２Ｆ】
2017138964.tif 000009
【図２Ｇ】
2017138964.tif 000010
【図２Ｈ】
2017138964.tif 000011
【図３】
2017138964.tif 000012
【図４】
2017138964.tif 000013
【外国語明細書】
2017138964000001.pdf