JP7611444B2 - マルチレベルマルチストライドを有するダイレクトメモリアクセスアーキテクチャ - Google Patents

Description

背景
ＤＭＡ（ダイレクトメモリアクセス）とは、デバイスやサブシステムが、処理装置とは独立してメモリにアクセスすることを可能にする機能である。これにより、処理装置は、データ転送に関わることから解放され、処理装置は、その他の操作を実行できるよう、利用可能になる。ＤＭＡを利用して、大容量のメモリ転送操作およびスキャッター／ギャザー操作など、処理装置が抱えるコストの高いメモリ操作の負担を軽減させることができる。

概要
本明細書は、たとえば１つのクロック周期の間に、マルチレベルマルチストライドを行うことと、複数のメモリアドレスを並列して決定することとが可能なＤＭＡアーキテクチャに関する技術について説明する。

概して、本明細書において説明する主題の１つの革新的な態様は、１つ以上のハードウェアＤＭＡスレッドを備えるＤＭＡ（ダイレクトメモリアクセス）システムに含めることができる。各ＤＭＡスレッドは、並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するように構成された要求生成部を含み、要求生成部は、Ｍ個のメモリアドレス部を含む。各メモリアドレス部は、多次元テンソルの次元ごとに（１）次元のステップインデックス値を生成し、ステップインデックス値に基づいて（２）次元のストライドオフセット値を生成するように構成されるステップ追跡部と、メモリアドレス計算要素とを含み、メモリアドレス計算要素は、並列メモリアドレス計算周期のたびに、ストライドオフセット値に基づいて、多次元テンソルのテンソル要素のメモリアドレスを生成し、メモリアドレスを用いてメモリ操作を行うよう求める要求を、メモリシステムに送るように構成され、Ｍは、１以上である。この態様のその他の実施態様は、対応する装置および方法を含む。

これらのおよびその他の実施態様は、各々、任意で下記の特徴のうち１つ以上を含み得る。いくつかの態様では、要求生成部は、１つのクロック周期の間にメモリアドレスを並列して生成するように構成され、各並列メモリ計算は、１つのクロック周期の間に行われる。クロック周期のたびに、各メモリアドレス部のメモリアドレス計算要素は、他のメモリアドレス部のメモリアドレス計算要素と同じまたは異なるテンソル要素のメモリアドレスを生成する。

いくつかの態様では、要求生成部は、多次元テンソルの記述子を受け取るように構成され、記述子は、次元ごとに、次元のストライド値のステップ数を規定する。要求生成部は、Ｍ個のレーンを含み得、Ｍ個のレーンは、各々、ステップ追跡部と、メモリアドレス計算要素とを含む。各レーンのステップ追跡部およびメモリアドレス計算要素は、対応するメモリアドレスを他のレーンと並列して計算する。ステップ追跡部は、ループネストに基づいて多次元テンソルのメモリアドレスを生成するように構成され得、ループネストは、多次元テンソルの次元ごとに、多次元テンソルの次元を横断するためのループを含む。各次元のストライド値当たりのステップ数は、次元のループのループ範囲を表し、各次元のステップインデックス値は、次元のループのループインデックスを表す。

いくつかの態様では、各ステップ追跡部は、クロック周期のたびに次元の各々のステップインデックス値を更新するように構成される。ステップ追跡部ごとのステップインデックス値の組合せは、他のステップ追跡部のステップインデックス値の組合せとは異なり得る。各ステップ追跡部は、複数のステップインクリメント部を含むステップインクリメントチェーンを含み得、複数のステップインクリメント部は、各々、次元の次元メモリアドレスオフセット値を決定するように構成される。ループネストの最も内側のループに対応するステップインクリメントチェーンの第１ステップインクリメント部は、予告量を受け取るように構成され得る。クロック周期のたびに次元のうち１つ以上の次元のステップインデックス値を更新することは、第１ステップインクリメント部が予告量に基づいて１つ以上の次元のステップインデックス値を更新することを含み得る。

いくつかの態様では、最も内側のループが入れ子になっているループに対応するステップインクリメントチェーンの１つ以上の第２ステップインクリメント部は、ステップインクリメントチェーンにある前のステップ追跡部からラップ量を受け取るように構成される。クロック周期のたびに次元のうち１つ以上の次元のステップインデックス値を更新することは、第２ステップインクリメント部がラップ量に基づいて１つ以上の次元のステップインデックス値を更新することを含み得る。

いくつかの態様は、応答並替え部と同期部とを含む進行状況追跡部を備え得る。応答並替え部は、テンソル要素のメモリ操作が行われたかどうかのステータスをテンソルごとに保持するように構成され得る。同期部は、複数の一部の最新情報をプロセッサコアに提供するように構成され得、複数の一部の最新情報は、各々、多次元テンソルのテンソル要素に対して行われたメモリ操作の全体的なステータスを明記する。

いくつかの態様では、各要求は、一意の識別子を含む。応答並替え部は、メモリシステムから応答を任意の順番に受け取るように構成され得る。各応答は、応答が提供される要求の一意の識別子を含み得る。応答並替え部は、少なくともしきい値数の連続した一意の識別子を応答で受け取った場合、一連の一意の識別子を、要求生成部が再利用できるよう、解放するように構成され得る。

概して、本明細書において説明する主題の別の革新的な態様は、１つ以上のプロセッサコアと、メモリシステムと、１つ以上のＤＭＡスレッドを含むＤＭＡエンジンとを備えるシステムに含めることができる。各ＤＭＡスレッドは、並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するように構成された要求生成部を含み得、要求生成部は、Ｍ個のメモリアドレス部を含み、Ｍは、１以上である。各メモリアドレス部は、多次元テンソルの次元ごとに（１）次元のステップインデックス値を生成し、ステップインデックス値に基づいて（２）次元のストライドオフセット値を生成するように構成されるステップ追跡部と、メモリアドレス計算要素とを含み得、メモリアドレス計算要素は、並列メモリアドレス計算周期のたびに、ストライドオフセット値に基づいて、多次元テンソルのテンソル要素のメモリアドレスを生成し、メモリアドレスを用いてメモリ操作を行うよう求める要求を、メモリシステムに送るように構成される。各ＤＭＡスレッドは、応答並替え部と、同期更新部とを含む進行状況追跡部を備え得、同期更新部は、ＤＭＡエンジンが管理するメモリ操作についての同期に関する一部の最新情報を１つ以上のプロセッサコアに提供するように構成される。この態様のその他の実施態様は、対応する装置および方法を含む。

これらのおよびその他の実施態様は、各々、任意で下記の特徴のうち１つ以上を含み得る。いくつかの態様では、要求生成部は、１つのクロック周期の間にメモリアドレスを並
列して生成するように構成され、各並列メモリ計算は、１つのクロック周期の間に行われる。

クロック周期のたびに、各メモリアドレス部のメモリアドレス計算要素は、他のメモリアドレス部のメモリアドレス計算要素と同じまたは異なるテンソル要素のメモリアドレスを生成し得る。要求生成部は、多次元テンソルの記述子を受け取るように構成され得、記述子は、次元ごとに、次元のストライド値のステップ数を規定する。要求生成部は、Ｍ個のレーンを含み得、Ｍ個のレーンは、各々、ステップ追跡部と、メモリアドレス計算要素とを含み、各レーンのステップ追跡部およびメモリアドレス計算要素は、対応するメモリアドレスを他のレーンと並列して計算する。

概して、本明細書において説明する主題の別の革新的な態様は、ＤＭＡシステムによって実行される方法に含めることができる。この方法は、要求生成部が、並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するステップを含み、要求生成部は、Ｍ個のメモリアドレス部を含み、Ｍは、１以上であり、各メモリアドレス部は、ステップ追跡部と、メモリアドレス計算部とを含み、方法は、さらに、ステップ追跡部が、多次元テンソルの次元ごとに（１）次元のステップインデックス値を生成し、ステップインデックス値に基づいて（２）次元のストライドオフセット値を生成するステップと、各メモリアドレス部のメモリアドレス計算要素が、並列メモリアドレス計算周期のたびに、ストライドオフセット値に基づいて、多次元テンソルのテンソル要素のメモリアドレスを生成するステップと、メモリアドレスを用いてメモリ操作を行うよう求める要求を、メモリシステムに送るステップとを含む。

本明細書において説明する主題は、以下の利点のうち１つ以上を実現するように特定の実施の形態で実現され得る。本明細書において説明するＤＭＡアーキテクチャにより、たとえばクロック周期当たり、多次元テンソルのメモリアドレスを並列して複数（Ｍ個）生成することが可能になる。これにより、メモリアドレスをより高速に生成でき、メモリ処理能力が向上する。ＤＭＡアーキテクチャは、複数のレーンを含み得、各レーンは、ステップ追跡部を含み、ステップ追跡部は、マルチストライド技術を実行して、多次元テンソルのループネストに基づいて複数のテンソル要素の複数のメモリアドレスを並列して計算する。ＤＭＡアーキテクチャの要求生成部が用いるこの技術により、複数のステップ追跡部が、テンソルの複数の次元にそれぞれ異なるステップインデックス値を用いて、並列して動作し、互いに独立して、クロック周期の間にそれぞれ異なるテンソル要素のアドレスを並列して生成することが可能になる。各ステップ追跡部は、次のテンソル要素のメモリアドレスを決定することに備えて、クロック周期のたびにそのステップインデックス値を更新し得る。

また、ＤＭＡアーキテクチャは、同期に関する一部の最新情報をプロセッサコアに提供する進行状況追跡部を備え得、プロセッサコアは、メモリの決定したメモリアドレスに格納されたデータを消費する。これにより、ＤＭＡのメモリトランザクションのすべてが完了する前にプロセッサコアがデータの消費を開始することが可能になり、メモリ転送によってプロセッサコアにかかっていた待ち時間が減り、処理装置の計算の全体的な効率が向上する。進行状況追跡部は、応答並替え部を含み得、応答並替え部は、メモリから一度に複数の応答を任意の順番で受け取ることができ、メモリは、生成された要求に対して、順不同で対処および応答できる。応答並替え部のサイズが限られているので、少なくともしきい値数の要求に対する応答が受け付けられた場合、応答並替え部は、要求の識別子を解放できる。これにより、要求生成部は、最大数の要求のすべてに対する応答を待たずに、
解放された識別子を利用してメモリ要求の発行を継続することが可能なり、メモリ転送の速度および効率が向上する。

上述した主題様々な特徴および利点について、図面を参照にしながら以下に説明する。その他の特徴および利点は、本明細書で説明する主題、および添付の特許請求の範囲から明らかである。

ＤＭＡスレッドがメモリ操作を生成してその進行状況を追跡する例示的な環境の図である。 例示的な要求生成部の図である。 メモリアドレスを決定するための例示的な擬似コードを示す図である。 例示的なステップ追跡部の図である。 例示的なステップインクリメントチェーンの図である。 例示的な進行状況追跡部の図である。 例示的な応答並替え部の図である。 メモリ操作を求める要求を生成するための例示的な処理を示すフロー図である。 メモリ操作の進行状況を追跡するための例示的な処理を示すフロー図である。

様々な図面における同じ参照番号および名称は、同じ要素を示す。
詳細な説明
概して、本明細書は、たとえば１つのクロック周期の間に、マルチレベルマルチストライドを行うことと、複数のメモリアドレスを並列して決定することとが可能なＤＭＡアーキテクチャについて説明する。チップは、チップのプロセッサコア（複数可）からのメモリ転送操作の負荷を軽減させる１つ以上のＤＭＡエンジンを含み得る。各ＤＭＡエンジンは、１つ以上のＤＭＡスレッドを含み得る。各ＤＭＡスレッドは、コア（複数可）に代わってＤＭＡトランザクションの実行を管理するハードウェアユニットである。クロック周期は、ＤＭＡエンジンまたはコアによる１つの操作の実行に必要な時間であり得る。

図１～図６に示し、以下で説明する例示的なＤＭＡアーキテクチャは、クロック周期当たり、最大で４つのテンソル次元ならびに最大で４つの読出し元メモリアドレスおよび最大で４つの宛先メモリアドレスをサポートできる設計を提供する。しかしながら、ＤＭＡアーキテクチャは、厳密にぴったりと周期当たり４つの次元または４つのアドレスに当てはまらない。周期当たりその他の数の次元およびその他の数のアドレスにも、同様のアーキテクチャが使用できる。これに加えて、周期当たりのアドレスの数は、アドレスが決定されるテンソルの次元の数とは異なり得る。たとえば、ＤＭＡスレッドは、周期当たり５つのアドレスを生成するために５つのレーンを含み得るが、ハードウェアは、最大で４つの次元、最大で１０個の次元、または別の最大数の次元を有するテンソルのアドレスを計算するように構成される。すなわち、アーキテクチャは、パラメータ化可能であり、設計のための面積／周波数の目標によって設定の選択が異なる。

図１は、ＤＭＡスレッド１２０がメモリ操作を生成してその進行状況を追跡する例示的な環境１００の図である。ＤＭＡスレッド１２０は、プロセッサコアに代わって要求されるトランザクションの一部としてメモリ操作を生成して、その進行状況を追跡し得る。ＤＭＡスレッド１２０は、ハードウェアユニットである。このハードウェアユニットは、ＤＭＡスレッド１２０と、１つ以上の他のＤＭＡスレッド（必須ではない）とを備えるＤＭＡエンジンの一部であり得る。ＤＭＡスレッド１２０は、スキャッター／ギャザー操作お
よびその他のメモリ転送操作など、コア１１０を含む１つ以上のプロセッサコアのＤＭＡトランザクションを管理し得る。たとえば、ＤＭＡスレッド１２０は、コア１１０とＤＭＡスレッド１２０とを備えるチップ上のメモリシステムの、異なるメモリ間での多次元テンソルの転送を指揮し得る。ＤＭＡスレッド１２０は、メモリシステムに要求（コマンド）を送ることによりデータの移動を指揮し、トランザクションを要求したコアに進行状況を同期できるよう、これらの要求の完了を追跡する。メモリシステムは、読出／書込の要求／コマンドがメモリシステムに入ると、要求の順番に関係なく独立して各要求を満たす。ＤＭＡスレッド１２０は、要求／応答の順番、およびコアとの同期に対処する。ＤＭＡスレッド１２０にこれらのメモリ操作の負荷を肩代わりさせることで、たとえば、機械学習計算を行ったり、テンソルの形を変更したりするなどのその他のタスクのために、コア１１０上の計算周期が解放される。

コア１１０は、ＤＭＡスレッド１２０に記述子１１２を送ることによってＤＭＡトランザクションを要求し得る。各ＤＭＡトランザクションは、１つ以上のメモリ転送操作を含み得る。記述子１１２は、ＤＭＡトランザクションについての情報を含む。たとえば、記述子１１２は、データが読み出されるメモリシステム１５０の読出し元メモリ１５２（たとえば、読出し元メモリ１５２のメモリアドレス（複数可））を明記する情報、データが書き込まれる書出し先メモリ１５４（たとえば、書出し先メモリ１５４のメモリアドレス（複数可））を明記する情報、テンソル要素が読出し元メモリ１５２に格納されるソーステンソルのサイズおよび形（たとえば、次元）を明記する情報、ならびにテンソル要素が書出し先メモリ１５４に格納される宛先テンソルのサイズおよび形を明記する情報を含み得る。テンソル要素とは、テンソルにおける特定のインデックス化された位置に対応するテンソルが含むデータである。

ソーステンソルのサイズおよび形は、宛先テンソルのサイズおよび形と同じであってもよく、異なってもよい。たとえば、テンソルの形がコア１１０によって変更されている場合、サイズおよび形は、異なってもよい。記述子１１２は、テンソルの各次元のストライド当たりのステップ数の値を用いて、テンソルのサイズおよび形を規定し得る。ｆｏｒループでは、ステップサイズとは、ループのイテレーションごとのインクリメントの大きさであり、ストライド当たりのステップ数とは、ループがリセットされる前のステップの数、たとえばループのループ範囲である。

たとえば、１つのテンソルの１つの次元のストライド当たりのステップ数は、その次元全体のテンソル要素の数に等しくてもよい。特に、８×６×４×２の４次元テンソルでは、１つ目の次元のストライド当たりのステップ数が８であり、２つ目の次元のストライド当たりのステップ数が６であり、３つ目の次元のストライド当たりのステップ数が４であり、４つ目の次元のストライド当たりのステップ数が２であり得る。詳細については後述するが、ストライド当たりのステップ数を用いて、テンソルの各次元を横断（ｔｒａｖｅｒｓｅ）し、テンソル要素のメモリアドレスを計算できる。

また、記述子１１２は、各次元のストライド次元オフセット値を含み得る。後述するが、これらのストライド次元オフセット値（次元オフセット値とも称する）を使用して、テンソル要素のメモリアドレスを決定する。次元オフセットとは、ストライドの距離である。テンソル次元に沿った処理の各ステップにおいて、ＤＭＡスレッド１２０は、ストライド次元オフセット値だけメモリアドレスを「飛び越す（ｈｏｐ）」。記述子１１２は、ソーステンソルについて、ソーステンソルの各次元のストライド次元オフセット値を含み得る。また、記述子１１２は、宛先テンソルについて、宛先テンソルの各次元のストライド次元オフセット値を含み得る。

ＤＭＡスレッド１２０は、記述子１１２を格納する記述子キュー１２２を備える。たと
えば、ＤＭＡスレッド１２０は、受け取って記述子キュー１２２に格納した記述子１１２に基づいて、複数のＤＭＡスレッドを逐次実行し得る。いくつかの実施態様では、記述子キュー１２２は、ＦＩＦＯ（Ｆｉｒｓｔ－Ｉｎ，Ｆｉｒｓｔ－Ｏｕｔ）キューであり、ＤＭＡトランザクションの記述子１１２が受け取られる順番にＤＭＡスレッド１２０がＤＭＡトランザクションを実行できる。ＤＭＡトランザクションの実行は、完全にパイプライン化されており、順不同な操作を行うように実装され得るが、処理装置には、プログラム順に実行しているように見える。

また、ＤＭＡスレッド１２０は、記述子スプリッター１２４を含む。記述子スプリッター１２４は、ソースサブスレッド１３０が利用する情報および宛先サブスレッド１４０が利用する情報を記述子１１２から取り出して、各サブスレッド１３０および１４０に適切な情報を提供し得る。

一般に、ソースサブスレッド１３０は、読出し元メモリ１５２からデータを読み出すための読出要求を生成してメモリシステム１５０に送り、読出動作の進行状況を追跡して、読出動作の進行状況にコア１１０を同期させる。同様に、宛先スレッド１４０は、書出し先メモリ１５４にデータを書き込むための書込要求を生成してメモリシステム１５０に送り、書込動作の進行状況を追跡して、書込動作の進行状況にコア１１０を同期させる。メモリシステム１５０は、コア１１０またはコア１１０を備えるチップの主メモリ、たとえば、コア１１０またはチップのＲＡＭ（ランダムアクセスメモリ）であり得る。メモリシステムは、読出し元メモリ読出要求ごとに読み出されるデータが書出し先メモリへの書込要求と対になるよう、実際のメモリの配線を実装する。データがＤＭＡスレッドを通過することはない（要求アドレスは送り出され、応答は受け取られるが、これらの応答および要求は、メモリデータを保持しない）。

ソースサブスレッド１３０は、記述子１１２に基づいて読出要求を生成する要求生成部１３２を含む。詳細については後述するが、要求生成部１３２は、たとえばクロック周期当たり複数のメモリアドレスを並列して生成し、メモリアドレスごとに読出要求を生成し得る。たとえば、要求生成部１３２は、コア１１０の１つのクロック周期の間に、多次元テンソルを横断しながら複数のテンソル要素の各々のメモリアドレスを生成し得る。各読出要求は、要求識別子（「要求ＩＤ」）と、データが読み出されるメモリアドレスと、メモリオペコードとを含み得る。後述するが、応答は順不同に受け取られ得るので、要求ＩＤは、要求を応答と対応付けるために使われるシーケンス番号またはタグであり得る。メモリオペコードは、メモリ操作、たとえば、要求が読出操作であるのか、書込操作であるのか、ｍｅｍｓｅｔ操作であるのか、または要求のメモリアドレスをターゲットにした別の操作であるのかを示す。

また、ソースサブスレッド１３０は、読出要求が明記する読出動作の進行状況を追跡する進行状況追跡部１３４を含む。たとえば、メモリシステム１５０は、読出動作が完了したことを知らせる読出応答を進行状況追跡部１３４に送り得る。各読出応答は、応答が送られた読出要求の要求ＩＤを含み得る。こうすることで、進行状況追跡部１３４は、要求ＩＤを使用して、ＤＭＡトランザクションの進行状況を追跡できる。

宛先サブスレッド１４０は、記述子１１２に基づいて書込要求を生成する要求生成部１４２を含む。詳細については後述するが、要求生成部１４２は、たとえばクロック周期当たり複数のメモリアドレスを並列して生成し、メモリアドレスごとに書込要求を生成し得る。たとえば、要求生成部１４２は、コア１１０の１つのクロック周期の間に、多次元テンソルを横断しながら複数のテンソル要素の各々のメモリアドレスを生成し得る。各書込要求は、要求ＩＤを含み得、データが書き込まれるメモリアドレスを明記し得る。

また、宛先サブスレッド１４０は、書込要求が明記する書込動作の進行状況を追跡する進行状況追跡部１３４を含む。たとえば、メモリシステム１５０は、書込動作が完了したことを知らせる書込応答を進行状況追跡部１４４に送り得る。各書込応答は、応答が送られた書込要求の要求ＩＤを含み得る。こうすることで、進行状況追跡部１４４は、要求ＩＤを使用して、ＤＭＡトランザクションの進行状況を追跡できる。

進行状況追跡部１３４および１４４は、それぞれ同期メッセージ１１５および１１６をコア１１０に送り、記述子１１２に対応するＤＭＡトランザクションの進行状況についての最新情報をコア１１０に提供し得る。同期メッセージ１１５および１１６は、完了度合い（たとえば、完了したメモリ操作の割合もしくは数）および／または応答が受け取られた要求ＩＤを明記し得る。

後述するが、進行状況追跡部１３４および１４４は、ＤＭＡトランザクションの進行状況についての一部のまたは不完全な最新情報を提供する同期メッセージ１１５および１１６を送り得る。たとえば、各進行状況追跡部１３４および１４４は、ＤＭＡトランザクションに対する指定された数、たとえば、しきい値数の応答が受け取られるたびに同期メッセージ１１５および１１６を送るように構成され得る。特定の例では、各進行状況追跡部１３４および１４４は、連続した一続きの少なくともしきい値数の要求ＩＤに対する応答が受け取られるたびに同期メッセージ１１５および１１６を送るように構成され得る。メモリ操作が行われる順番（よって、テンソル要素が移動されている順番）をコア１１０は知り得るので、コア１１０は、すべての一連のＤＭＡトランザクションが完了するのを待たずに、これらの一部の最新情報に基づいて、転送済みのデータの処理を開始し得る。

読出操作と書込動作に別個のサブスレッドを用いることで、処理能力を向上させることが可能になる。たとえば、各サブスレッド１３０および１４０が、クロック周期当たり特定の数の要求、たとえば、クロック周期当たり４つの要求を並列して生成できる場合、２つのサブスレッド１３０および１４０によって生成される要求の数は、当該特定の数の２倍、たとえば、８個の要求になる。

場合によっては、複数のＤＭＡスレッドを使用してＤＭＡトランザクションが行われ得る。たとえば、メモリのバンド幅が、１つのＤＭＡスレッドが生成し得る要求よりも多くの要求をクロック周期当たりに対処するのに十分である場合、複数のＤＭＡスレッドを使用して要求が生成され得る。多次元テンソルのデータを転送するために複数のＤＭＡスレッドが使用される場合、各ＤＭＡスレッドは、多次元テンソルの一部、たとえば、テンソルの１つのスライスの記述子を受け取り得る。この記述子は、フルテンソルの記述子と同様に、テンソルのスライスのサイズおよび形と、メモリアドレスとを明記し得る。

図２Ａは、例示的な要求生成部２００の図である。要求生成部２００は、図１の要求生成部１３２および１４２の各々を実装するために用いられ得る。この例では、要求生成部２００は、最大で４つのテンソル次元があり、クロック周期当たり最大で４つのメモリアドレスが生成され得る実装向けに構成される。

一般に、要求再生成部２００は、多次元テンソルまたはその他の多次元データ構造（本明細書では、説明が煩雑になるのを防ぐために、テンソルと称す）におけるテンソル要素のメモリアドレスを決定し得る。要求生成部２００は、テンソルのデータがメモリから読み出されるおよび／またはメモリに書き込めるよう、メモリアドレスを決定し得る。要求生成部２００は、テンソル内でのテンソル要素の位置を定める当該テンソル要素のステップインデックス値に基づいて、テンソル要素のメモリアドレスを計算し得る。例示的な要求生成部２００は、５段階設計を用いて、隣接する段階の間にパイプラインレジスタ２２０、２３０、２４０、２６０、および２７０を配置させた状態に実装される。

メモリアドレスを決定するために、要求生成部２００は、各次元の各ステップインデックス値を１つずつ進むことにより、各次元を横断し得る。たとえば、１つの次元が１０個の要素を含む場合、要求生成部２００は、ステップインデックス値を１から１０の順番に１つずつ進み得る。概念的に、これは、テンソルの次元ごとに１つのループを含んだループネストを使用して行われ得る。このような例では、そのループに含まれる要素の数にループ範囲が等しくなるまでループのイテレーションごとに当該ループのステップインデックス値をインクリメントすることによって、テンソルの１つ次元がループを用いて横断され得る。ループ範囲に達すると、次の外側のループがインクリメントされ、現在のループは、次元が含む最初の要素に対応する最初のステップインデックス値にリセットされる。最も内側のループは、ループネストに含まれる４つのループのステップインデックス値に対応するテンソル内の位置にあるテンソル要素のメモリアドレスを決定するためのメモリアドレス計算を含み得る。４つのループを使用してメモリアドレスを決定するための例示的な擬似コード２８０を図２Ｂに示す。

図２Ｂを参照すると、擬似コード２８０は、１つのテンソルの４つの次元を横断するために使われる４つのループ２８１～２８４を含む。図示した擬似コード２８０には、トランザクションの半分が記述されている（ソース側が読み込むか、宛先側が書き出すかのいずれか）。完全なトランザクションにするために、同じまたは同様の擬似コードが別個に２回インスタンス化され得る。擬似コード２８０では、各次元のループ範囲（ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ）は、転送のソース側と宛先側とで同じであるが、ストライドオフセット値（ｓｔｒｉｄｅ＿ｄｉｍｅｎｓｉｏｎ＿ｏｆｆｓｅｔ＿ｖａｌｕｅ＿ｉ）は異なり得る。すなわち、擬似コードにおけるｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿０はソース側と宛先側とで同じであるが、ソース側の擬似コードにおけるｓｔｒｉｄｅ＿ｄｉｍｅｎｓｉｏｎ＿ｏｆｆｓｅｔ＿ｖａｌｕｅ＿０は、宛先擬似コードにおけるｓｔｒｉｄｅ＿ｄｉｍｅｎｓｉｏｎ＿ｏｆｆｓｅｔ＿ｖａｌｕｅ＿０とは異なり得る。

最も外側のループ２８１は、複数ある次元のうち１つに対応し、ステップインデックス値ｉ_０と、ループ範囲ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿０とを含む。ループ範囲ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿０は、最も外側のループに対応する次元２８１に含まれる要素の数に等しくてもよい。同様に、ループ２８２は、複数ある次元のうち１つに対応し、ステップインデックス値ｉ_１と、ループ範囲ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿１（ループ２８２に対応する次元に含まれる要素の数に等しくてもよい）とを含み、ループ２８３は、複数ある次元のうち１つに対応し、ステップインデックス値ｉ_２と、ループ範囲ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿２（ループ２８３に対応する次元に含まれる要素の数に等しくてもよい）とを含む。

最も内側のループ２８４もまた、複数ある次元のうち１つに対応し、ステップインデックス値ｉ_３と、ループ範囲ｓｔｅｐｓ＿ｐｅｒ＿ｓｔｒｉｄｅ＿３（最も内側のループ２８４に対応する次元に含まれる要素の数に等しくてもよい）とを含む。最も内側のループのイテレーションごとに、関数２８５を使用して、テンソルの各次元の次元メモリアドレスオフセット値が計算され、これらの次元メモリアドレスオフセット値を用いて、関数２８６を使用して、ステップインデックス値ｉ_０～ｉ_３に対応するテンソル要素のメモリアドレスが決定される。最も外側のループ２８１に対応する次元の次元メモリアドレスオフセット値（ｄｅｓｔｉｎａｔｉｏｎ＿ｍｅｍｏｒｙ＿ａｄｄｒｅｓｓ＿ｏｆｆｓｅｔ＿０）は、ループのステップインデックス値ｉ_０と次元のストライド次元オフセット値（ｓｔｒｉｄｅ＿ｄｉｍｅｎｓｉｏｎ＿ｏｆｆｓｅｔ＿ｖａｌｕｅ＿０）との積に等しい。その他の次元ごとの次元メモリアドレスオフセット値も、図２Ｂに示すように、同様に決定される。上述したように、次元のストライド次元オフセット値は、記述子に含まれ得る。

その後、テンソル要素のメモリアドレスは、ベースメモリアドレス、およびテンソルの各次元の次元メモリアドレスオフセット値に基づいて計算され得る。たとえば、テンソル要素のメモリアドレスは、図２Ｂに示すように、ベースメモリアドレスと、それぞれの次元の次元メモリアドレスオフセット値との和に基づき得る、たとえば、ベースメモリアドレスと、それぞれの次元の次元メモリアドレスオフセット値との和に等しい。

図２Ａに戻ると、要求生成部２００は、実際にループを繰り返さずに、類似したメモリアドレス計算を並列して行い得る。この例では、要求生成部２００は、たとえば１つのクロック周期内で４つのメモリアドレスを並列して計算するための４つのレーン２０１～２０４を含む。その他の例では、たとえば３つのメモリアドレスには３つのレーン、５つのメモリアドレスには５つのレーンなど、２つ以上のレーンを使用して２つ以上のメモリアドレスが並列して計算され得る。すなわち、要求生成部２００は、Ｍ個のメモリアドレスを並列して計算するためにＭ個のレーンを含み得る。ここで、Ｍは、１以上である。要求生成部２００は、並列メモリアドレス計算周期の間に、Ｍ個のメモリアドレスを計算し得る。並列メモリアドレス計算周期の長さは、１つのクロック周期以下の長さである。

レーンの数は、テンソルの次元の数と同じであってもよく、異なってもよい。たとえば、要求生成部２００を用いて、記述子１１２に含まれる情報に基づいて、次元の数が異なるテンソルのメモリアドレスを計算し得る。たとえば、４つのレーンを有する要求生成部２００は、最大で４つのレーンのすべてを使用して、３次元テンソルのメモリアドレスを周期当たり最大で４つ計算し得る。また、同じ要求生成部２００は、最大で４つのレーンすべてを使用して、１次元テンソル、２次元テンソル、または４次元テンソルのアドレスを周期当たり最大で４つ計算し得る。

各レーン２０１～２０４は、互いに異なるテンソル要素のメモリアドレスを計算しなければならず、各レーンが互いに独立して動作するので、マルチレベルマルチストライド（この例では、４レベルマルチストライド）に基づいてこのような計算を並列して行うことは、難しいであろう。各レーン２０１～２０４が並列して、たとえば同時にメモリアドレスを計算するので、一方のレーンが、他方のレーンが完了するのを待ってから、１つ以上のループを繰り返して次のテンソル要素のメモリアドレスを決定することはできない。その代わりに、各レーンが、別のレーンを待たずに、次のテンソル要素（たとえば、次のテンソル要素のステップインデックス値）を決定し、そのテンソル要素のメモリアドレスを決定できるようになければならない。

要求生成部２００は、それぞれのレーン２０１～２０４に（よって、それぞれの並列メモリアドレス計算のために）メモリアドレス部２４２～２４８を含む。各メモリアドレス部２４２～２４８は、それぞれステップ追跡部２２２～２２８と、それぞれメモリアドレス計算要素２５２～２５８とを含む。一般に、ステップ追跡部２２２～２２８は、テンソルのテンソル要素を１つずつ進んで、テンソル要素の次元メモリアドレスオフセット値を決定するように構成される。メモリアドレス計算要素２５２～２５８は、ステップ追跡部２２２～２２８から受け取る次元メモリアドレスオフセット値を用いて、テンソル要素のメモリアドレスを決定するように構成される。

要求生成部２００は、ステップ追跡部２２２～２２８のために値を事前に計算する計算要素２１０を備える。たとえば、計算要素２１０は、メモリアドレスが決定される次のテンソル要素の次のステップインデックス値を決定するためにステップ追跡部２２２～２２８が使用できる様々なステップ比較値を事前に計算し得る。後述するが、現在のステップインデックス値とステップ比較値との比較は、次のステップインデックス値を決定するためのその他の条件とともに使用され得る。計算要素２１０は、テンソルの各次元のステップ比較値を事前に計算し得る。要求生成部２００がメモリアドレスを生成して要求を送っ
ている現在の記述子１１２のテンソルの次元の数によっては、これらのステップ比較値は、たとえば、次元のストライド当たりのステップ数から１を減算した値、次元のストライド当たりのステップ数から２を減算した値、次元のストライド当たりのステップ数から３を減算した値などであり得る。計算要素２１０は、必須ではなく、事前に計算された値も必須ではない。値を事前に計算することは、次のクロック周期上でのクリティカルパスタイミングを改善するのに役立ち得る。

計算要素２１０は、ステップ比較値を事前に計算してレジスタ２２０（またはその他の適切なデータ記憶素子）に格納する一連のハードウェア加算器を備え得る。計算要素２１０は、記述子で受け取ったストライド当たりのステップ数の値に基づいて、比較オフセット値を計算し得る。この記述子は、次元のうち１つ以上の次元のストライド当たりのステップ数の値を含み得る。この例では、記述子は、次元１～３（ｓｐｓ＿１～ｓｐｓ＿３）のストライド当たりのステップ数の値を含み売るが、次元０（たとえば、最も外側のループに対応する次元）のストライド当たりのステップ数の値は含まない。たとえば、ストライド当たりのステップ変数が３２ビットの符号付き整数で表される場合、次元０のストライド当たりのステップ数の値は、最大整数値、たとえば、符号付き３２ビットの整数で格納できる最大整数値である、と暗に示され得る。別の例では、ストライド当たりのステップ数の値は、記述子に含まれ得るが、図２Ａには示していない。

ストライド当たりのステップ数の値がテンソルのサイズおよび形に基づいて異なり得るので、計算要素２１０は、記述子ごとにステップ比較値を事前に計算し、レジスタ２２０に格納し得る。また、記述子は、レジスタ２２０に格納され得る。

また、要求生成部２００は、ＦＳＭ（有限ステートマシン）２３２を備える。ＦＳＭ２３２は、記述子１１２からの情報に基づいてステップ追跡部２２２～２２８を初期化および制御し得る。たとえば、ＦＳＭ２３２は、レジスタ２３０から記述子情報を取得して、記述子情報に基づいて、記述子が規定するＤＭＡトランザクションを求めて送る要求の数を決定し得る。この数は、テンソルに含まれるテンソル要素の数であり得る。ＦＳＭ２３２は、送る残りの要求の数を追跡し、この残りの要求の数に基づく予告量（advance amount）を各ステップ追跡部２２２～２２４に送り得る。予告量は、メモリアドレス計算要素２５２～２５８が行うメモリアドレス計算の次の周期の間に計算されるメモリアドレスの数を定める。

たとえば、４つのレーン２０１～２０４のすべてを使用してＤＭＡトランザクションを実行する過程で、予告量は、４に等しくてもよい。しかしながら、このＤＭＡトランザクションについて計算されるメモリアドレスの数が４つ未満である場合、最後の周期の予告量は、４よりも小さい値になる。たとえば、メモリアドレスの数が１８である場合、ＦＳＭ２３２は、最初の４つの周期については４という予告量を各ステップ追跡部２２２～２２８に提供し、その後、最後の周期については２という予告量を提供する。

また、ＦＳＭ２３２は、ステップ追跡部２３２をストールし得る。たとえば、後述するが、進行状況追跡部１３４および１４４は、１度に特定の数の要求の進行状況を追跡すればよい。要求生成部２００は、割り当てられた要求ＩＤを使い切ると、要求生成部２００は、要求生成部２００自体、たとえば、ステップ追跡部２３２をストールし得る。要求ＩＤが解放されて再割り当てされ得る場合、たとえば、後述するが、少なくともしきい値数の連続した要求ＩＤに対する応答が受け取られると、進行状況追跡部１３４および１４４は、要求ＩＤクレジットを返し得る。

また、要求生成部１３２および１４２は、外部接続バックプレッシャー（external interconnect backpressure）により、ストールし得る（すなわち、メモリシステムは、新し
い要求をまだ受け付けられない）。いくつかの実施態様では、各ＤＭＡスレッド１２０は、ソフトウェアによって構成可能なハードウェアＦＳＭを用いて、独立して速度が絞られ得る。ソフトウェアは、構成可能なサンプリング期間にわたる目標要求生成バンド幅をＤＭＡスレッド１２０ごとに設定し得、ＤＭＡスレッド１２０は、割り当てられたバンド幅に達すると自動的にそのパイプラインをストールする。よって、ＤＭＡスレッド１２０は、（１）メモリシステムネットワークバックプレッシャー、（２）要求バンド幅が絞られる、（３）要求ＩＤ割り当てを使い果たす（進行状況追跡部がクレジットを返すのを待つ）という３つの異なる状況でストールし得る。

各ステップ追跡部２２２～２２８は、ＦＳＭ２３２から受け取った予告量と、テンソルの各次元の現在のステップインデックス値と、各次元のストライド当たりのステップ数の値とを用いて、各次元の次のステップインデックス値を決定する。また、各ステップ追跡部２２２～２２８は、各次元の次元メモリアドレスオフセット値を、当該次元の次のステップインデックス値と、当該次元のストライド次元オフセット値とに基づいて決定する。各ステップ追跡部２２２～２２８は、決定した次元メモリアドレスオフセット値を、それぞれの対応するメモリアドレス計算要素２５２～２５８にレジスタ２４０を介して出力する。後述するが、メモリアドレス計算要素２５２～２５８は、受け取った次元メモリアドレスオフセット値に基づいてテンソル要素のメモリアドレスを決定する。

ステップ追跡部２２２～２２８は、互いに異なるテンソル要素の次元メモリアドレスオフセット値を決定する。たとえば、全部で１６個のテンソル要素を含む２×２×２×２のテンソル（またはその他の形のテンソル）について考える。４つのレーン２０１～２０４が周期ごとに４つの要求を生成するので、各ステップ追跡部２２２～２２８は、１６個のテンソル要素のうち、全部で４つのテンソル要素の次元メモリアドレスオフセット値を決定する。たとえば、ステップ追跡部２２２が最初のテンソル要素、５番目のテンソル要素、８番目のテンソル要素、および１３番目のテンソル要素の次元メモリアドレスオフセット値を決定し得、ステップ追跡部２２４が２番目のテンソル要素、６番目のテンソル要素、１０番目のテンソル要素、および１４番目のテンソル要素の次元メモリアドレスオフセット値を決定するなどである。

ステップ追跡部２２２～２２８は、それぞれの次元メモリアドレスオフセット値を、互いに独立して、並列して決定し得る。すなわち、いくつかの実施態様では、ステップ追跡部２２２～２２８は、その他のステップ追跡部２２２～２２８とはデータを通信しない。その代わりに、詳細については後述するが、各ステップ追跡部２２２～２２８は、ステップ追跡部２２２～２２８の初期化およびＦＳＭ２３２から受け取った予告量に基づいて、次のテンソル要素（たとえば、次のテンソル要素のステップインデックス値）を決定するように構成され得る。このように、いずれのステップ追跡部２２２～２２８も他のステップ追跡部２２２～２２８を待たなくてよく、この並列計算は、すべてのステップ追跡部２２２～２２８によって１つのクロック周期で完了され得る。ステップ追跡部の例示的なアーキテクチャ、および次元メモリアドレスオフセット値を決定するための技術について、図３、図４、および図７に示し、以下に説明する。

メモリアドレス計算要素２５２～２５８は、第１加算要素２６２Ａ～２６８Ａと、第２加算要素２６２Ｂ～２６８Ｂとをそれぞれ含む。第１加算要素２６２Ａ～２６８Ａは、並列メモリアドレス計算周期ごとにそれぞれのステップ追跡部２２２～２２８から受け取った次元メモリアドレスオフセット値の和を求め得る。たとえば、加算要素２６２Ａは、ステップ追跡部２２２が生成した特定のテンソル要素についての４つの次元メモリアドレスオフセット値の合計を求め得る。第１加算要素２６２Ａ～２６８Ａは、ハードウェア加算器として実現され得る。

第２加算要素２６２Ｂ～２６８Ｂ（これらもハードウェア加算器としても実現され得る）は、それぞれの対応する第１加算要素２６２Ａ～２６８Ａが計算した次元メモリアドレスオフセット値の和と、基底アドレスとに基づいて、テンソル要素のメモリアドレスを決定し得る。たとえば、加算要素２６２Ｂは、ステップ追跡部２２２が生成した特定のテンソル要素についての４つの次元メモリアドレスオフセット値の和に基底アドレスを加算することによって、当該特定のテンソル要素のメモリアドレスを決定し得る。

第２加算要素２６２Ｂ～２６８Ｂは、それぞれのメモリアドレスをレジスタ２７０に出力し得る。要求送信部２９０は、各メモリアドレスを求める要求を生成して、メモリシステム、たとえば、図１のメモリシステム１５０に送り得る。要求は、要求ＩＤと、メモリアドレスとを含み得る。要求ＩＤは、要求に順番に割り当てられ得る。たとえば、ＤＭＡスレッドが一度に５００個の未処理の要求を有するように構成された場合、要求ＩＤは、０または１から始まり、それぞれ最大で４９９または５００までになる。０～４９９が用いられた場合、最初の要求の要求ＩＤは０であり得、２番目の要求の要求ＩＤは１であり得るなどである。要求送信部２９９は、各要求の要求ＩＤを決定するカウンタを備え得る。

４つのレーン２０１～２０４は、各々、１つのクロック周期の間に、テンソル要素のメモリアドレスを並列して生成し得る。ＦＳＭ２３２は、レーン２０１～２０４のステップ追跡部２２２～２２８を制御して、テンソルに含まれる各テンソル要素のメモリアドレスが計算されるまで、テンソルの各テンソル要素を反復処理する。記述子を求める要求を発行し終わると、ＦＳＭ２３２は、次の記述子に取り掛かり得る。しかしながら、ＦＳＭ２３２は、すべての要求に対する応答が受け取られるのを待つ必要はない。少なくともしきい値数の連続した（たとえば、応答が受け取られた）要求ＩＤが利用可能であれば、進行状況追跡部１３２または１３４は、要求生成部２００がこれらの利用可能な要求ＩＤを用いて次の記述子を求める要求を発行できるよう、要求生成部２００に通知を行い得る。これにより、ＤＭＡスレッドの処理能力および効率性がさらに向上する。

上述したように、ＤＭＡサブスレッド１３２および１３４の要求生成部１３２および１３４は、要求生成部２００を用いて実装され得る。この例では、各サブスレッド１３２および１３４は、クロック周期当たり４つの要求を送ることが可能になる。

図３は、例示的なステップ追跡部３００の図である。ステップ追跡部３００は、図２Ａのステップ追跡部２２２～２２８の各々を実装するために用いられ得る。この例では、ステップ追跡部３００は、２つのインクリメントチェーン３２２および３２４を備える。インクリメントチェーン３２２および３２４は、同じまたは同様の関数を実行して、テンソル要素のステップインデックス値および次元メモリアドレスオフセット値を生成し得る。これにより、ステップインクリメントチェーンのうち一方は、ＤＭＡスレッドが処理を開始する現在の記述子の次元メモリアドレスオフセット値を積極的に決定できるようになり、他方のステップインクリメントチェーンは、ＤＭＡスレッドが処理する次の記述子のために初期化される。

たとえば、ステップインクリメントチェーン３２４が現在の記述子の次元メモリアドレスオフセット値を積極的に決定し得る。ステップインクリメントチェーン３２４は、ＦＳＭから受け取った予告量、たとえば、図２のＦＳＭ２３２、および（記述子が規定する）ストライドパラメータを用いて、現在の記述子の次元メモリアドレスオフセット値を決定し得る。図４を参照して後述するが、ステップインクリメントチェーン３２４がアクティブである間、ＦＳＭは、ステップインクリメントチェーン３２２を初期化し得る。

現在の記述子の最後の周期のメモリアドレスが要求されている間に、ＦＳＭは、初期化
されたステップインクリメントチェーン３２２に切り替えて、ステップインクリメントチェーン３２２に初期化量を送り得る。ステップインクリメントチェーン３２４が次元メモリアドレスオフセット値の最後の一式を決定したクロック周期の直後のクロック周期に、ステップインクリメントチェーン３２２は、次元メモリアドレスオフセット値の最初の一式を生成し得る。２つのステップインクリメントチェーンをこのように利用することで、特に、テンソルが小さい場合にＤＭＡスレッドの処理能力および効率性が大幅に改善し得る。たとえば、このテンソルのメモリアドレスのすべてを決定するために要求生成部が３つのクロック周期しか必要としない場合、１つのクロック周期を用いてテンソル間の１つのステップインクリメントチェーンを再度初期化すると、処理能力（たとえば、単位時間当たりに行われるメモリ操作の数）が２５％低下してしまう。

ステップインクリメントチェーン３２２と３２４とを切り替えるとき、ＦＳＭは、マルチプレクサ３３２～３３８の一式を制御して、レジスタ３４２を介してどのステップインクリメントチェーンの出力をメモリアドレス計算部に送るかを選択し得る。たとえば、ＦＳＭは、インクリメントチェーン３２２がアクティブである場合、各マルチプレクサ３３２～３３８の上段のレーンを選択し得、インクリメントチェーン３２４がアクティブである場合、各マルチプレクサ３３２～３３８の下段のレーンを選択し得る。

図２Ｂを参照して上述したが、各レーン２０１～２０４は、ステップ追跡部３００として実装され得るステップ追跡部を含む。この例では、ステップ追跡部３００は、レーン０のステップ追跡部であり、レーン０の４つの次元メモリアドレスオフセット値を出力する。

また、図示しないが、各ステップ追跡部３００は、次元メモリアドレスオフセット値を決定するために用いられる次のステップインデックス値を出力し得る。当該次のステップインデックス値は、後続のステップインデックス値および次元メモリアドレスオフセット値を決定する際に使用するために、ステップ追跡部３００に戻される。すなわち、ステップインクリメントチェーン３２４は、各次元のステップインデックス値を決定し得、各次元の次元メモリアドレスオフセット値を決定し得る。これらの値は、ステップインクリメントチェーン３２４に現在値として戻されて、次の値を決定する際に使用され得る。

また、ステップ追跡部３００は、ステップインデックス値用のマルチプレクサを備え得る。これらのマルチプレクサは、マルチプレクサ３２２～３３８がステップインクリメントチェーン３２２および３２４の両方から次元メモリアドレスオフセット値を受け取るのと同様に、ステップインクリメントチェーン３２２および３２４の両方から各次元のステップインデックス値を受け取る。これらのマルチプレクサの出力は、ステップインクリメントチェーン３２４に提供されて、後続のステップインデックス値を決定する際に使用される。

ステップインクリメントチェーン３２４が現在の記述子の次元メモリアドレスオフセット値を計算する一方、ステップインクリメントチェーン３２２は、初期化された状態を用いて、次の記述子のメモリアドレスの第１セットの次元メモリアドレスオフセット値を決定し得る。しかしながら、ＦＳＭは、マルチプレクサ３３２～３３８を制御して、ステップインクリメントチェーン３２４から受け取った次元メモリアドレスオフセット値を渡し得る。現在の記述子が完了すると、ＦＳＭは、マルチプレクサ３３２～３３８を制御して、１つ周期についてステップインクリメントチェーン３２２が計算した次元メモリアドレスオフセット値を渡し得る。次元メモリアドレスオフセット値は、次のテンソルの最初の４つのテンソル要素の値を含む。また、ＦＳＭは、ステップインデックス値に関してマルチプレクサを制御して、ステップインクリメント部３２２からステップインクリメントチェーン３２４にこの１つの周期のステップインデックス値を渡し得る。その後、ステップ
インクリメントチェーン３２４は、ステップインデックス値の現在の状態を有することとなり、この記述子に関連する残りの周期の次元メモリアドレスオフセット値を決定し得る。この記述子の最初の周期が完了した後、ＦＳＭは、マルチプレクサを制御して、ステップインクリメントチェーン３２４の出力を再び渡し得る。

図４は、例示的なステップインクリメントチェーン４００の図である。ステップインクリメントチェーン４００は、ＤＭＡスレッドが処理するように構成された最大テンソルの次元ごとに、ステップインクリメント部を備え得る。この例では、ステップインクリメントチェーン４００は、最大で４つの次元テンソルに対して４つのステップインクリメント部４１０～４４０を含む。図４に示すこの例示的なステップインクリメントチェーンは、キャリーリップル方式の加算回路と同様の形式で組合せ関数として実装される。

各ステップインクリメント部４１０～４４０は、パラメータのセットを受け取り得る。このステップインクリメント部４１０～４４０のパラメータのセットは、ステップインクリメント部４１０～４４０に対応する次元のストライド当たりのステップ数と、計算要素２１０が事前に計算した次元の各ステップ比較値とを含み得る。これらの値は、ＤＭＡトランザクションが行われているテンソルの含み得るサイズおよび形に基づいて変わり得るので、ステップインクリメント部４１０～４４０は、記述子ごとに初期化され得る。

また、各ステップインクリメント部４１０～４４０は、その次元のステップインデックス値と、当該次元の次元オフセット値とを受け取り得る。この次元のステップインデックス値は、（ステップインクリメントチェーン３２２への入力値によっても図示されているように）最初の周期で０に初期化され得る。最初の周期の後、ステップインクリメント部４１０～４４０に入力されるステップインデックス値は、ステップインクリメント部４１０～４４０によって出力される次のステップインデックス値になる。上述したように、次元の次元オフセット値は、ステップインデックス値によって乗算される値であり、次元メモリアドレスオフセット値を決定する。図２Ｂの擬似コード２８０の４つのループを使用することと比較すると、ステップインクリメント部４１０は、ループネストの最も内側のループと同様に機能する。しかしながら、ループのイテレーションごとにステップインデックスを１つインクリメントするのではなく、ステップインクリメント部４１０は、ＦＳＭから受け取った予告量に基づいて、そのステップインデックス値をインクリメントする。たとえば、予告量が４であった場合、ステップインクリメント部４１０は、その次元のステップインデックス値を４つずつインクリメントするであろう。このインクリメント数が次元のストライド当たりのステップ数を超えた場合、ステップインクリメント部は、ステップインデックス値を０に再度初期化して、４回インクリメントされるまでインクリメントを続け得る。これは、２回以上の再度初期化することを含み得る。たとえば、ストライド当たりのステップ数が３で予告量が４である場合、ステップインクリメント部４１０は、０から３にインクリメントし、０に再度初期化し、４回インクリメントした後に、０から１にインクリメントするであろう。

ステップインクリメント部４１０は、ステートフルなイテレーションを利用するのではなく、最適化された加算器のペアと同様に挙動する組合せ関数を利用し得る。加算器のように、ステップインクリメント部の一部は、２つのオペランド（「ステップ３ インデックス」および「ａｄｖａｎｃｅ＿ａｍｏｕｎｔ」）をとり、和（「ステップ３ 次のインデックス」）と、桁上がり（「ラップ量」）とを出す。この関数は、次の次元オフセットを計算する関数がラップ量の出力を出さないこと以外は、次元オフセットに対して同様である。

ステップインクリメント部４１０は、ステップインクリメント部４２０にラップ量を出力し得る。ラップ量は、受け取った予告量に基づいてステップインクリメント部４１０の
ステップインデックス値が現在の周期において再度初期化された回数に等しくてもよい。すなわち、ラップ量は、予告量に基づいて４つのループがラップアラウンドされる回数を反映している。

ステップインクリメント部４１０～４４０がその次元メモリアドレスオフセット値を計算する周期ごとに、たとえば、１つのクロック周期の間に、ステップインクリメント部４１０は、その次元の次のステップインデックス値と、ステップインクリメント部４２０のラップ量と、次元メモリアドレスオフセット値（たとえば、次のステップインデックス値と、次元の次元オフセット値との積）とを計算し得る。

ステップインクリメント部４２０がＦＳＭから受け取った予告量を利用した方法と同様の方法で、ステップインクリメント部４２０は、ステップインクリメント部４１０から受け取ったラップ量を利用する。すなわち、ラップ量は、ステップインクリメント部４２０に対応する次元のステップインデックス値がこの周期でインクリメントされる回数を表す。ステップインクリメント部４２０は、そのステップインデックス値を、ステップインクリメント部４１０から受け取ったラップ量を用いてインクリメントし、次のステップインデックス値を決定する。また、ステップインクリメント部４２０は、その次元メモリアドレスオフセット値を、次のステップインデックス値を用いて決定し得る（たとえば、次元の次のステップインデックス値とストライド次元オフセット値との積）。

ステップインクリメント部４１０と同様に、ステップインクリメント部４２０も、ラップ量を計算してステップインクリメント部４３０に出力し得る。ラップ量は、ステップインクリメント部４１０から受け取ったラップ量に基づいてステップインクリメント部４２０のステップインデックス値が現在の周期で再度初期化された回数と等しくてもよい。すなわち、ラップ量は、受け取ったラップ量に基づいて４つのループがラップアラウンドされる回数を反映している。

ステップインクリメント部４３０は、ステップインクリメント部４２０から受け取ったラップ量を同様に利用し得る。すなわち、ラップ量は、ステップインクリメント部４３０に対応する次元のステップインデックス値がこの周期でインクリメントされる回数を表す。ステップインクリメント部４３０は、そのステップインデックス値を、ステップインクリメント部４２０から受け取ったラップ量を用いてインクリメントし、次のステップインデックス値を決定し得る。また、ステップインクリメント部４３０は、その次元メモリアドレスオフセット値を、次のステップインデックス値を用いて決定し得る（たとえば、次元の次のステップインデックス値とストライド次元オフセット値との積）。

ステップインクリメント部４２０と同様に、ステップインクリメント部４３０もラップ量を計算してステップインクリメント部４４０に出力し得る。ラップ量は、ステップインクリメント部４３０のステップインデックス値が、ステップインクリメント部４２０から受け取ったラップ量に基づいて現在の周期で再度初期化された回数に等しくてもよい。すなわち、ラップ量は、受け取ったラップ量に基づいて４つのループがラップアラウンドされる回数を反映している。

ステップインクリメント部４４０は、ステップインクリメント部４３０から受け取ったラップ量を同様に利用し得る。すなわち、ラップ量は、ステップインクリメント部４４０に対応する次元のステップインデックス値がこの周期でインクリメントされる回数を表す。ステップインクリメント部４４０は、そのステップインデックス値を、ステップインクリメント部４３０から受け取ったラップ量を用いてインクリメントし、次のステップインデックス値を決定し得る。また、ステップインクリメント部４４０は、その次元メモリアドレスオフセット値を、次のステップインデックス値を用いて決定し得る（たとえば、次
元の次のステップインデックス値とストライド次元オフセット値との積）。

ステップインクリメント部４１０～４４０がその次元メモリアドレスオフセット値を計算する周期ごとに、たとえば、１つのクロック周期の間に、ステップインクリメント部４１０～４４０は、各々、その次元の次のステップインデックス値と、次のステップインクリメント部（該当する場合は）のラップ量と、次元メモリアドレスオフセット値（たとえば、次元の次のステップインデックス値とストライド次元オフセット値との積）とを計算し得る。

いくつかの実施態様では、各インクリメント部４１０～４４０は、その次元の次のステップインデックス値および／またはその次元のラップ量を決定する際に、一連の条件を使用し得る。この条件は、インクリメント量（たとえば、インクリメント部４１０に対する予告量、またはインクリメント部４２０～４４０に対するラップ量）を含み得る。また、この条件は、次元のストライド当たりのステップ数、および現在のステップインデックス値とステップ比較値との比較も含み得る。

たとえば、ルックアップテーブルが生成され得る。ルックアップテーブルは、たとえば、インクリメント量と、ストライド当たりのステップ数と、どのステップ比較値が現在のステップインデックス値と一致するのかとの特定の組合せごとに、次のステップインデックス値が何になるのか、およびラップ量が何になるのかを明記する。特定の組合せは、要求生成部がメモリアドレスを生成できるテンソルの次元の数に基づいて異なり得る。このように、各ステップインクリメント部４１０～４４０は、インクリメント量および現在のステップインデックス値をテーブルと単純に比較して、次のステップインデックス値とラップ量とが何になるかを判断し得る。

図５は、例示的な進行状況追跡部５００の図である。進行状況追跡部５００は、図２Ａの進行状況追跡部１３４および１４４の各々を実装するために使われ得る。進行状況追跡部５００は、進行状況追跡部のキュー５１０と、応答並替え部５２０と、同期部５３０とを備える。

進行状況追跡部のキュー５１０は、１つの記述子から複数の記述子（または、記述子のうち、応答と同期に対処するために必要な関連箇所）を受け取って格納し得る。後述するが、記述子により、同期部５３０は、記述子が規定するＤＭＡトランザクションの進行状況を特定することが可能になる。

応答並替え部５２０は、メモリシステム、たとえば、図１のメモリシステム１５０から応答を受け取り得る。各応答は、応答に対応する要求の要求ＩＤを明記し得る。すなわち、メモリシステムは、進行状況追跡部５００に対応する要求生成部から受け取った完了済みの各要求に対する応答を、進行状況追跡部５００に送り得る。

応答並替え部５２０は、任意の順序で応答を受け取って、それらの要求ＩＤに基づいて応答の順序を並び替え得る。メモリシステムは、要求が受け取られた順序とは異なる順序で要求を処理し得る。たとえば、メモリシステムは、バンド幅最適化技術を利用して、一部の要求をその他の要求よりも優先し得る。これに鑑みて、応答並替え部５２０は、応答を順不同に受け取って、その順序を並び替えて、メモリシステムによって完了されるメモリ操作の進行状況を追跡するように構成され得る。例示的な応答並替え部については図６に示し、詳細については後述する。

同期部５３０は、応答並替え部から進行状況データを受け取り、コア、たとえば、図１のコア１１０に同期メッセージを送り得る。たとえば、同期部５３０は、応答並替え部５
２０から、受け取った順序要求ＩＤの数を明記するデータを受け取り得る。同期部５３０は、記述子が規定する少なくともしきい値量（またはしきい値割合）のメモリ操作が完了するたびに、同期メッセージを送るように構成され得る。たとえば、同期部５３０は、現在の記述子に関連して行われるメモリ操作の回数（たとえば、読出操作または書込操作であるかは、サブスレッドによって異なる）を決定し得る。同期更新部５３０は、メモリ操作の少なくとも１０％が完了するたびにコアに同期メッセージを送るように構成され得る。上述したように、記述子が規定するメモリ操作のすべてが完了するまで待たずに、コアは、これらの一部の最新情報を使って、転送されたデータを消費し始め得る。

応答並替え部５２０および／または同期部５３０は、要求生成部が再利用できる一連の要求ＩＤを要求生成部に通知するように構成され得る。たとえば、少なくともしきい値数の順序要求ＩＤをメモリシステムから応答で受け取るたびに、これらの要求ＩＤは、応答生成部に解放されて再利用され得る。これにより、要求生成部は、進行状況追跡部５００が処理できる最大数の要求を要求生成部が送った後、すべての要求が完了する前に、要求の生成を継続することが可能になる。

たとえば、進行状況追跡部５００が１度に５００個のメモリ操作しか追跡できない応答並替えバッファを含み、要求ＩＤが０～４９９であると想定する。５００個のメモリ操作のすべてが要求で使われて、いずれの要求に対しても応答がなかった場合、要求生成部は、進行状況追跡部５００から利用可能な要求ＩＤを明記する通知を受け取るまでストールしなければならない。進行状況追跡部５００が０～１５の要求ＩＤに対する応答を受け取り（しかし、識別子のすべての応答ではない）、しきい値が１５未満である場合、進行状況追跡部５００は、５００個すべてのメモリ操作が完了するまで待たずに、要求生成部が０～１５の要求ＩＤを用いた要求の送信を再開できることを明記する通知（たとえば、要求ＩＤクレジットリターンメッセージ）を送り得る。

図６は、例示的な応答並替え部６００の図である。応答並替え部６００を用いて、図５応答並替え部５２０が実装され得る。応答並替え部６００は、応答ベクトル６１０と、並替えベクトル６３０とを含み、これらは各々、ビットベクトルレジスタを用いて実装され得る。応答ベクトル６１０および並替えベクトル６３０は、各々、要求生成部が発行できる要求ＩＤごとに１つのビットを含み得る。このビットは、要求ＩＤのステータスを示し得る。たとえば、ビットの値が０である場合、メモリ操作に対する応答は、未だ受け取っていない。ビットの値が１である場合、メモリ操作に対する応答はすでに受け取っている。応答ベクトル６１０、並替えベクトル６３０、およびポップベクトル（後述する）は、すべて同じサイズであってもよく、たとえば同じ数のビットを含み得る。

応答ベクトル６１０は、一度に複数の応答、たとえばこの例では最大で４つの応答を一度に受け取るように構成され得る。たとえば、応答ベクトル６１０は、対応する要求生成部のレーンの数に一致する数の応答を同時に受け取るように構成され得る。その他の例では、応答ベクトル６１０は、対応する要求生成部のレーンの数とは異なる数、たとえばレーンの数よりも多い数の応答を同時に受け取るように構成され得る。

並替えベクトル６３０に含まれるビットは、要求ＩＤの順番に配置され得る。並替えベクトル６３０の入力側には論理和ゲート６２４がある。論理和ゲート６２４は、並替えベクトル６３０のビットごとに論理和ゲートを備えるビットベクトル論理和ゲートであり得る。要求ＩＤごとに、要求ＩＤの応答ベクトルのビット、および論理積ゲート６２２（たとえば、ビットベクトル論理積ゲート）が出力する要求ＩＤのビットは、論理和ゲートへの入力となり得、並替えベクトル６３０に含まれる要求ＩＤのビットの値が決定される。

論理積ゲート６２２には、要求ＩＤごとに、したがって並替えベクトル６３０のビット
ごとに１対の入力がある。特定の要求ＩＤの場合、並替えベクトル６３０に含まれるビットの値、およびポップベクトルロジック６４０が保持するポップベクトルにある要求ＩＤのポップビットの値が両方とも１である場合、当該要求ＩＤに関する論理積ゲートの出力は、１である。後述するが、メモリアドレスのポップビットを１に設定して、たとえば、要求生成部が使用するために要求ＩＤが解放された場合に、ビットの値をクリアして０にし得る。すなわち、要求ＩＤに対する応答が受け取られていて要求ＩＤがまだ解放されていない場合、要求ＩＤに対応するビットの論理積ゲート６２２の出力は、１である。要求ＩＤが解放された場合、このビットについての論理積ゲート６２２の出力は、ポップベクトルからの入力が１になるので、０である。

また、応答並替え部６００は、先頭ポインタロジック６５０と、ポップベクトルロジック６４０と、内部ポップカウントロジック６６０とを備える。先頭ポインタロジック６５０は、並替えベクトル６３０に含まれる、応答が受け取られた最も数字が大きい順序要求ＩＤのビットの後ろの次のビットに、ポインタを維持し得る。順序要求ＩＤは、最初の要求ＩＤから応答がまだ受け取られていない要求ＩＤまでの、応答が受け取られた連続した要求ＩＤである。たとえば、要求ＩＤの値が０～４９９であり、０～８、１１、５６、および６１～７８に対する応答がすでに受け取られている場合、順序要求ＩＤの値は、０～８である。この例では、先頭ポインタは、要求ＩＤの値が９であるビットを指す。値が９および１０である要求ＩＤに対する応答が受け取られると、順序要求ＩＤの値は、０～１１となり、値が１２である要求ＩＤの応答はまだ受け取られていないと想定される。

また、先頭ポインタロジック６５０は、先頭ポインタに１を足したポインタ（たとえば、先頭ポインタが指しているビットの次のビット）、先頭ポインタに２を足したポインタなど、別の先頭ポインタを事前に計算し得る。こうすることで、ポップカウントロジック６６０は、１つのクロック周期の間に並替えベクトル６３０において２つ以上のビットをポップし得る。この機能は、必須ではなく、これを使って、特定のクロック周波数のタイミングに合わせることができる。ロジックは、周期当たりの応答が多い大きな並替えベクトルの場合、かなり複雑になる。この事前計算は、目標周波数が比較的高速である場合、または周期当たりの応答が多い（たとえば、レーンが多い）場合に用いられ得る。

内部ポップカウントロジック６６０は、並替えベクトル６３０に含まれるビットを監視して、先頭ポインタが移動したときに並替えベクトルのいくつのビットがポップ（たとえば、クリア）され得るかを決定し得る。たとえば、内部ポップカウントロジック６６０は、値が１のビット列をルックアヘッドし得る。１という値は、ビットに対応するメモリ操作に対する応答が受け取られたことを示す。先頭ポインタロジック６５０が別のビットに移動すると、先頭ポインタロジック６３０は、先頭ポインタの移動先（たとえば、ｈｅａｄ＿ｐｌｕｓ＿ｉ＿ｎｅｘｔ）（たとえば、ビット）を提供し得る。先頭ポインタの新しい位置および監視されているビットに基づいて、内部ポップカウントロジック６６０は、クロック周期当たりの、ポップし得るビットの数、たとえば、最大ポップ数までを決定し得る。たとえば、先頭ポインタがビット１０個分だけ上に移動し得る場合、最大ポップ数は、クロック周期当たりビット４つであり、内部ポップカウントロジック６６０は、ポップベクトルロジック６４０に、最初の周期で４つのビットをポップし、２回目の周期で４つのビットをポップし、２回目の周期で２つのビットをポップするよう指示し得る。先頭ポインタは、その周期の間にポップするエントリの数と同じ数だけインクリメントされるので、この例では、周期当たり最大でビット４つ分だけ進み得る。

ポップベクトルロジック６４０は、ポップするビットのポップベクトルを保持し、このポップベクトルを論理積ゲート６２２に入力として提供し得る。先頭ポインタおよび別の先頭ポインタ、ならびに内部ポップカウントロジック６６０から受け取ったポップするビットの数に基づいて、ポップベクトルロジック６４０は、どのビットがポップするかを決
定し得る。たとえば、ポップするビットが４つである場合、ポップベクトルロジック６４０は、現在の先頭ポインタから先頭ポインタに４を足した位置までのビットをポップし得る。先頭ポインタに４を足した値はすでに計算されているので、ポップベクトルロジック６４０は、ポップするビットの位置を、クロック周期を消費して決定する必要がない。

先頭ポインタロジック６５０も、ポップカウントロジックから、ポップするビットの数を受け取り得る。先頭ポインタロジック６５０は、先頭ポインタを更新し、ポップするビットの数に基づいて、別の先頭ポインタを事前に計算し得る。

また、応答並替え部６００は、順序アイテムレジスタ６７２と、計算要素６７０および６７４とを備える。順序アイテムレジスタ６７２は、要求生成部にまだ解放されていない、ポップした順序アイテムの数のカウントを保持し得る。そうするために、計算部６７０は、内部ポップカウントロジック６６０の出力に基づいて、ポップしたビットの数を集約する。

レジスタ６７２にある順序アイテムの数は、同期部５３０にも送られる。同期部５３０は、ポップした順序アイテムの数に基づいて、要求ＩＤを要求生成部に解放するタイミングを決定し得る。たとえば、同期部は、要求生成部が利用できる要求ＩＤの数（たとえば、要求ＩＤクレジットリターン）を明記するデータを送り得る。計算部６７４は、この数を、レジスタ６７２に現在ある順序アイテムの数から減算し、その結果（および内部ポップカウントロジック６６０からの新たにポップしたアイテム）を用いてレジスタを更新し得る。たとえば、レジスタ６７２が１５個の順序アイテムがポップしたと示し、同期部５３０が１０個を要求生成部に解放した場合、計算要素６７４は、１５個の要求ＩＤからこの１０個の解放された要求ＩＤを減算し、５つの要求ＩＤの値を格納して更新し得る。こうすることで、レジスタ２７２は、要求生成部に解放できる要求ＩＤの数の累計を格納する。

図７は、メモリ操作を求める要求を生成するための例示的な処理７００を説明するフロー図である。処理７００は、要求生成部、たとえば、図１の要求生成部１３２もしくは１４２、または図２の要求生成部２００によって実行され得る。

要求生成部は、１つ以上の記述子を受け取る（７０２）。各記述子は、ＤＭＡトランザクション、たとえば、一連のメモリ転送操作についての情報を含む。たとえば、記述子は、データが読み出される読出し元メモリを明記する情報と、データが書き込まれる書出し先メモリを明記する情報と、テンソル要素が読出し元メモリに格納されるソーステンソルのサイズおよび形（たとえば、次元）を明記する情報と、テンソル要素が書出し先メモリに格納される宛先テンソルのサイズおよび形を明記する情報と、各次元のストライド次元オフセット値を明記する情報とを含み得る。

要求生成部は、ステップ追跡部を初期化する（７０４）。上述したように、要求生成部は、たとえばクロック周期当たりのメモリアドレスを各々が並列して計算する複数のレーンを備え得る。各レーンは、ステップ追跡部と、メモリアドレス計算部とを含み得る。各ステップ追跡部は、ステップインクリメントチェーンを含み得る。ステップ追跡部を初期化することは、各ステップインクリメント部にステップパラメータを提供することと、ステップインクリメント部ごとにステップインデックス値を初期化することとを含む。

要求生成部は、メモリアドレスを生成する（７０６）。たとえば、要求生成部は、複数のレーンを使用して、たとえば１つのクロック周期の間に複数のメモリアドレスを並列して計算し得る。特に、クロック周期の間、各ステップ追跡部は、（テンソルに含まれる特定のテンソル要素に対応する）テンソルの各次元の次のステップインデックス値を計算し
、各次元の次元メモリアドレスオフセット値を、当該次元のストライド次元オフセット値と、次のステップインデックス値とを用いて計算し得る。そして、レーン上のステップ追跡部が出力した各次元の次元メモリアドレスオフセット値と、基底アドレスとに基づいて、各レーンのメモリアドレス計算部は、メモリアドレスを計算し得る。たとえば、レーンのメモリアドレス（よって、テンソル要素）は、基底アドレスと、次元メモリアドレスオフセット値との和であり得る。

要求生成部は、要求を生成してメモリシステムに送る（７０８）。要求は、読出要求であってもよく、書込要求であってもよい。各要求は、要求ＩＤと、この周期中に計算されたメモリアドレスとを明記し得る。すなわち、要求生成部は、コンピュータメモリアドレスごとに各要求を生成して送り得る。要求生成部は、メモリシステムに要求を送り得、メモリシステムは、要求に含まれているメモリアドレスを用いて読出動作または書込動作を行う。

要求生成部は、メモリアドレスを計算するテンソル要素がまだあるかどうかを判断する（７１０）。たとえば、上述したように、ＦＳＭは、記述子に関して生成する残りの要求の数を追跡し得る。テンソル要素がまだある場合、処理７００は、ステップ７０６に戻り、メモリアドレスをさらに生成する。

別のテンソル要素がない場合、要求生成部は、ＤＭＡトランザクションを行う別の記述子があるかどうかを判断する（７１４）。たとえば、要求生成部は、記述子キューを確認して、キューの中に別の記述子があるかどうかを判断し得る。別の記述子がない場合、処理は終了する。別の記述子がある場合、処理は、ステップ７０４に戻る。ステップ７０４では、次の記述子のためにステップ追跡部が初期化される。上述したように、ステップ追跡部は、前の記述子のＤＭＡトランザクションが完了する前に初期化され得る。

図８は、メモリ操作の進行状況を追跡するための例示的な処理８００を説明するフロー図である。処理８００は、進行状況追跡部、たとえば、図１の進行状況追跡部１３４もしくは１４４、または図５の進行状況追跡部５００によって行われ得る。

進行状況追跡部は、１つ以上の応答を受け取る（８０２）。たとえば、メモリシステムは、メモリ操作が完了したことに応答して追跡した進行状況に対する応答を送り得る。この応答は、完了したメモリ操作の要求ＩＤを明記し得る。

進行状況追跡部は、並替えベクトルを更新する（８０４）。進行状況追跡部は、並替えベクトルを更新して、要求ＩＤに対応するメモリ操作が完了したことを示し得る。たとえば、進行状況追跡部は、要求ＩＤのビットの値を０から１に更新して、要求ＩＤに対応するメモリ操作が完了したことを示し得る。

進行状況追跡部は、連続する要素（たとえば、要求ＩＤのビット）の数がしきい値以上であるかどうかを判断する（８０６）。しきい値以上である場合、進行状況追跡部は、要求ＩＤを解放して、要求生成部が再利用できるようにする（８０８）。しきい値以上でない場合、処理８００は、要求ＩＤを解放することなく、ステップ８１０に続く。

ステップ８１０では、進行状況追跡部は、受け取った応答の数がしきい値以上であるかどうかを判断する。この数は、メモリ操作が行われているコアに前回の同期メッセージが送られてから受け取った応答の数であり得る。別の例では、進行状況追跡部は、受け取る応答の数のうち、少なくともしきい値割合の応答を受け取ったかどうかを判断し得る。

いずれの例においても、しきい値以上になった場合、進行状況追跡部は、コアと同期し
得る（８１２）。たとえば、進行状況追跡部は、受け取った応答の数または割合を示す同期メッセージをコアに送り得る。別の例では、進行状況追跡部は、前回の同期メッセージがコアに送られてから受け取った応答の数を示す同期メッセージをコアに送り得る。

しきい値に達していない場合、処理８００は、ステップ８１４に続く。ステップ８１４では、進行状況追跡部は、記述子の応答をすべて受け取ったどうかを判断する。記述子のすべての応答を受け取っていない場合、処理８００は、ステップ８０２に戻る。ステップ８０２では、さらに多くの応答を受け取る。記述子のすべての応答を受け取っている場合、進行状況追跡部は、たとえば、記述子のメモリ操作のすべてが完了したことを示す同期メッセージを送ることによって、コアと同期し得る（８１６）。

本明細書は、多くの具体的な実施態様の詳細を含むが、これらは発明または特許請求の範囲の限定として解釈されるべきではなく、むしろ、特定の発明の特定の実施の形態に特有な特徴の説明であると解釈されるべきである。本明細書おいて別々の実施の形態として説明された特定の特徴も、組み合わせて１つの実施の形態で実現することができる。その逆に、１つの実施の形態として説明された様々な特徴を、別々の複数の実施の形態または任意の適した部分的な組み合わせで実現することもできる。また、特徴は、いくつかの特定の組み合わせで動作するものとして上述され、そのように当初クレームされてもよいが、クレームされた組合せからの１つ以上の特徴は、場合によっては、組み合わせから削除することができ、クレームされた組合せは、部分的な組み合わせまたは部分的な組み合わせの変形例を対象としてもよい。

同様に、図面に動作を特定の順番で示しているが、所望の結果を実現するためにこのような動作を図示された特定の順番または順序で実行する必要がある、または、図示した動作のすべてを実行する必要がある、と理解されるべきではない。特定の状況では、多重タスク処理および並列処理が有利である場合がある。また、上述の実施の形態における様々なシステムおよび構成要素を分離することは、このような分離がすべての実施の形態において必要であると理解されるべきではなく、説明したプログラムコンポーネントおよびシステムは、一般に、１つのソフトウェアプロダクトに一体化したり、複数のソフトウェアプロダクトにパッケージ化したりすることができると理解されるべきである。

よって、本発明の主題の特定の実施の形態を説明した。その他の実施の形態も、添付の特許請求の範囲に含まれる。場合によっては、請求項に記載された動作は、異なる順序で実行することができ、それでもなお所望の結果を実現することができる。これに加えて、添付の図面に示した処理は、所望の結果を実現するために必ずしも図示した特定の順番または一連の順序である必要はない。いくつかの実施態様において、多重タスク処理および並列処理が有利である場合がある。

Claims (20)

1. ＤＭＡ（ダイレクトメモリアクセス）システムであって、
   ＤＭＡハードウェアユニットを備え、前記ＤＭＡハードウェアユニットは、
   並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）前記多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するように構成された要求生成部を含み、前記要求生成部は、Ｍ個のメモリアドレス部を含み、各メモリアドレス部は、
   並列メモリアドレス計算周期のたびに、前記多次元テンソルのテンソル要素のメモリアドレスオフセット値を生成するように構成されたステップ追跡部と、
   メモリアドレス計算要素とを含み、前記メモリアドレス計算要素は、
   並列メモリアドレス計算周期のたびに、前記メモリアドレスオフセット値に基づいて、前記多次元テンソルの前記テンソル要素のメモリアドレスを生成し、
   前記メモリアドレスを用いて前記メモリ操作を行うよう求める前記要求を、前記メモリシステムに送るように構成され、前記ＤＭＡハードウェアユニットは、さらに、
   進行状況追跡部を備え、前記進行状況追跡部は、
   前記テンソル要素のメモリ操作が行われたかどうかのステータスをテンソル要素ごとに保持するように構成された応答並替え部と、
   複数の一部の最新情報をプロセッサコアに提供するように構成された同期更新部とを含み、前記複数の一部の最新情報は、各々、前記多次元テンソルの前記テンソル要素に対して行われたメモリ操作の全体的なステータスを明記し、
   前記Ｍ個のメモリアドレス部のステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素は、並列メモリアドレス計算周期のたびに前記Ｍ個のメモリアドレス部の残りのステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素とは異なり、
   前記Ｍは、２以上である、ＤＭＡシステム。
2. 前記ステップ追跡部は、前記多次元テンソルの次元ごとに（１）前記次元のステップインデックス値を決定し、前記ステップインデックス値に基づいて（２）前記次元のメモリアドレスオフセット値を決定することによって前記多次元テンソルの前記テンソル要素の前記メモリアドレスオフセット値を生成するように構成され、前記多次元テンソルの前記次元の前記ステップインデックス値は、前記多次元テンソル内での前記テンソル要素の位置に対応する、請求項１に記載のＤＭＡシステム。
3. 各要求は、一意の識別子を含み、
   前記応答並替え部は、
   前記メモリシステムから応答を任意の順番に受け取るように構成され、各応答は、前記応答が提供される前記要求の前記一意の識別子を含み、前記応答並替え部は、さらに、
   一連の一意の識別子を、前記要求生成部が再利用できるよう、解放するように構成される、請求項１または２に記載のＤＭＡシステム。
4. 前記応答並替え部は、少なくともしきい値数の連続した一意の識別子を前記応答で受け取った場合、前記一連の一意の識別子を解放するように構成される、請求項３に記載のＤＭＡシステム。
5. 前記要求生成部は、１つのクロック周期の間に前記メモリアドレスを並列して生成するように構成され、各並列メモリ計算は、１つのクロック周期の間に行われる、請求項１～４のいずれか１項に記載のＤＭＡシステム。
6. 前記要求生成部は、Ｍ個のレーンを含み、前記Ｍ個のレーンは、各々、ステップ追跡部と、メモリアドレス計算要素とを含み、各レーンの前記ステップ追跡部および前記メモリアドレス計算要素は、対応するメモリアドレスを他のレーンと並列して計算する、請求項１～５のいずれか１項に記載のＤＭＡシステム。
7. ステップ追跡部は、ループネストに基づいて前記多次元テンソルの前記メモリアドレスを生成するように構成され、前記ループネストは、前記多次元テンソルの次元ごとに、前記多次元テンソルの次元を横断するためのループを含み、
   各次元のストライド値当たりのステップ数は、前記次元の前記ループのループ範囲を表し、各次元の前記ステップインデックス値は、前記次元の前記ループのループインデックスを表す、請求項２に記載のＤＭＡシステム。
8. 各ステップ追跡部は、クロック周期のたびに前記次元の各々の前記ステップインデックス値を更新するように構成される、請求項７に記載のＤＭＡシステム。
9. ＤＭＡシステムによって実行される方法であって、
   要求生成部が、並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）前記多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するステップを含み、前記要求生成部は、Ｍ個のメモリアドレス部を含み、前記Ｍは、２以上であり、各メモリアドレス部は、ステップ追跡部と、メモリアドレス計算要素とを含み、前記方法は、さらに、
   各メモリアドレス部の前記ステップ追跡部が、並列メモリアドレス計算周期のたびに、前記多次元テンソルのテンソル要素のメモリアドレスオフセット値を生成するステップと、
   各メモリアドレス部の前記メモリアドレス計算要素が、並列メモリアドレス計算周期のたびに、前記多次元テンソルの前記テンソル要素の前記メモリアドレスオフセット値に基づいて、前記多次元テンソルのテンソル要素のメモリアドレスを生成するステップと、
   各メモリアドレス部の前記メモリアドレス計算要素が、前記メモリアドレスを用いて前記メモリ操作を行うよう求める前記要求を、前記メモリシステムに送るステップと、
   応答並替え部が、前記テンソル要素のメモリ操作が行われたかどうかのステータスをテンソル要素ごとに保持するステップと、
   同期更新部が、複数の一部の最新情報をプロセッサコアに提供するステップとを含み、前記複数の一部の最新情報は、各々、前記多次元テンソルの前記テンソル要素に対して行われたメモリ操作の全体的なステータスを明記し、
   前記Ｍ個のメモリアドレス部のステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素は、並列メモリアドレス計算周期のたびに前記Ｍ個のメモリアドレス部の残りのステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素とは異なる、方法。
10. 前記多次元テンソルの前記テンソル要素の前記メモリアドレスオフセット値を生成するステップは、前記多次元テンソルの次元ごとに（１）前記次元のステップインデックス値を決定し、前記ステップインデックス値に基づいて（２）前記次元のメモリアドレスオフセット値を決定するステップを含み、前記多次元テンソルの前記次元の前記ステップインデックス値は、前記多次元テンソル内での前記テンソル要素の位置に対応する、請求項９に記載の方法。
11. 各要求は、一意の識別子を含み、
    前記応答並替え部は、
    前記メモリシステムから応答を任意の順番に受け取るように構成され、各応答は、前記応答が提供される前記要求の前記一意の識別子を含み、前記応答並替え部は、さらに、
    一連の一意の識別子を、前記要求生成部が再利用できるよう、解放するように構成される、請求項９または１０に記載の方法。
12. 前記応答並替え部は、少なくともしきい値数の連続した一意の識別子を前記応答で受け取った場合、前記一連の一意の識別子を解放する、請求項１１に記載の方法。
13. 前記要求生成部は、１つのクロック周期の間に前記メモリアドレスを並列して生成し、各並列メモリ計算は、１つのクロック周期の間に行われる、請求項９～１２のいずれか１項に記載の方法。
14. 前記要求生成部は、Ｍ個のレーンを含み、前記Ｍ個のレーンは、各々、ステップ追跡部と、メモリアドレス計算要素とを含み、各レーンの前記ステップ追跡部および前記メモリアドレス計算要素は、対応するメモリアドレスを他のレーンと並列して計算する、請求項９～１３のいずれか１項に記載の方法。
15. ステップ追跡部は、ループネストに基づいて前記多次元テンソルの前記メモリアドレスを生成し、前記ループネストは、前記多次元テンソルの次元ごとに、前記多次元テンソルの次元を横断するためのループを含み、
    各次元のストライド値当たりのステップ数は、前記次元の前記ループのループ範囲を表し、各次元の前記ステップインデックス値は、前記次元の前記ループのループインデックスを表す、請求項１０に記載の方法。
16. 各ステップ追跡部は、クロック周期のたびに前記次元の各々の前記ステップインデックス値を更新する、請求項１５に記載の方法。
17. システムであって、
    １つ以上のプロセッサコアと、
    メモリシステムと、
    ＤＭＡハードウェアユニットとを備え、前記ＤＭＡハードウェアユニットは、
    並列メモリアドレス計算周期のたびに（１）多次元テンソルのためにＭ個のメモリアドレスを並列して生成し、メモリアドレスごとに（２）前記多次元テンソルに関するメモリ操作を行うようメモリシステムに求める要求を生成するように構成された要求生成部を含み、前記要求生成部は、Ｍ個のメモリアドレス部を含み、各メモリアドレス部は、
    並列メモリアドレス計算周期のたびに、前記多次元テンソルのテンソル要素のメモリアドレスオフセット値を生成するように構成されたステップ追跡部と、
    メモリアドレス計算要素とを含み、前記メモリアドレス計算要素は、
    並列メモリアドレス計算周期のたびに、前記メモリアドレスオフセット値に基づいて、前記多次元テンソルの前記テンソル要素のメモリアドレスを生成し、
    前記メモリアドレスを用いて前記メモリ操作を行うよう求める前記要求を、前記メモリシステムに送るように構成され、前記ＤＭＡハードウェアユニットは、さらに、
    進行状況追跡部を備え、前記進行状況追跡部は、
    前記テンソル要素のメモリ操作が行われたかどうかのステータスをテンソル要素ごとに保持するように構成された応答並替え部と、
    複数の一部の最新情報をプロセッサコアに提供するように構成された同期更新部とを含み、前記複数の一部の最新情報は、各々、前記多次元テンソルの前記テンソル要素に対して行われたメモリ操作の全体的なステータスを明記し、
    前記Ｍ個のメモリアドレス部のステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素は、並列メモリアドレス計算周期のたびに前記Ｍ個のメモリアドレス部の残りのステップ追跡部のうちの任意のステップ追跡部がメモリアドレスオフセット値を生成する前記テンソル要素とは異なり、
    前記Ｍは、２以上である、システム。
18. 前記ステップ追跡部は、前記多次元テンソルの次元ごとに（１）前記次元のステップインデックス値を決定し、前記ステップインデックス値に基づいて（２）前記次元のメモリアドレスオフセット値を決定することによって前記多次元テンソルの前記テンソル要素の前記メモリアドレスオフセット値を生成するように構成され、前記多次元テンソルの前記次元の前記ステップインデックス値は、前記多次元テンソル内での前記テンソル要素の位置に対応する、請求項１７に記載のシステム。
19. 各要求は、一意の識別子を含み、
    前記応答並替え部は、
    前記メモリシステムから応答を任意の順番に受け取るように構成され、各応答は、前記応答が提供される前記要求の前記一意の識別子を含み、前記応答並替え部は、さらに、
    一連の一意の識別子を、前記要求生成部が再利用できるよう、解放するように構成される、請求項１８に記載のシステム。
20. 前記応答並替え部は、少なくともしきい値数の連続した一意の識別子を前記応答で受け取った場合、前記一連の一意の識別子を解放するように構成される、請求項１９に記載のシステム。

Images