JP2022544842A - 同期プロセッサのためのシャーディング - Google Patents

Abstract

多数の同期タイルを有するデバイスのデータフローグラフをシャーディングするための、コンピュータ記憶媒体においてエンコーディングされるコンピュータプログラムを含む、方法、システム、および装置。方法のうちの1つは、複数の同期タイルを有するデバイスによって行われることになるそれぞれのマトリクス動作をそれぞれが表す複数のノードを含むデータフローグラフの表現を受信するステップを含む。複数の同期タイルの各タイルに対するデータフローグラフのそれぞれの部分の候補割当ては、デバイスの1つまたは複数のリソース制約に従って評価される。候補割当てのうちの1つは、各候補割当ての評価に基づいて選択される。

Description

本明細書は、集積回路アクセラレータのコンパイラ技法に関する。

同期集積回路アクセラレータは、高度に並列同期(parallel synchronous)の動作を行うように設計されている特定用途向け集積回路(ASIC)である。並列性は、同時に実行することができる数多くの異なる独立した処理要素を集積化することによって達成される。

そのようなデバイスは、たとえば独立した処理要素のそれぞれが、レイヤ入力の、重みとの異なる乗算または加算を行うニューラルネットワークを介して、推論パスを加速させるのによく適している。ニューラルネットワークは、多数の動作レイヤを用いて1つまたは複数の入力から1つまたは複数の出力を予測する機械学習モデルである。ニューラルネットワークは、通常、入力レイヤと出力レイヤとの間に位置する1つまたは複数の隠れレイヤを含む。各レイヤの出力は、ネットワーク内の別のレイヤ、たとえば次の隠れレイヤまたは出力レイヤへの入力として使用される。

アクセラレータは、多数の独立した処理タイルを使用することができる。本明細書においては、タイルは、マトリクスの一部分に対するコンピュータ計算を少なくとも部分的に並行して行うことができる、コンピュータ計算セルアレイを有する任意の適切なデバイスを示す。したがって、各セルは、セルが数学的または他のコンピュータ計算を行うことを可能にする回路機構を含む。通常のシナリオでは、タイルは入力ベクトルを受け取り、コンピュータ計算アレイを使用して入力ベクトルに重みのマトリクスを乗算し、出力ベクトルを生成する。

本明細書においては、タイルが同期しているとは、コンピュータ計算アレイによって行われる動作が、たとえば命令型プログラムのif/else文と同様に、分岐した実行を行わないことを意味する。むしろ、動作は、部分的または完全にのいずれかで事前にスケジューリングされ得る。たとえば、いくつかの同期プロセッサの動作は、個々のサイクルレベルに至るまでスケジューリングされ得、そのことは、あらゆる処理要素の動作ごとに、コンピュータ計算アレイが、一連の実行サイクルで特定のスロットに割り当てられることを意味する。

本明細書では、多数の同期プロセッサを有するシステム用に書かれたプログラムをコンパイルするための技法について説明する。上述したように、簡潔にするために、そのようなデバイスを本明細書においてはタイルと呼ぶ。

コンパイラは、サイクルレベルの精度を生かすことができ、その精度で、多数の同期プロセッサにわたって実行するプログラムの動作がスケジューリングされ得る。これにより、動作のきめ細かいシャーディング、ならびに他の性能の増強が可能になる。本明細書に説明する技法は、線形アレイにおける多数のタイルを動作させるシステムにおいて動作をスケジューリングするのに特に有用であり、ここでは、各タイルは、線形アレイ内のその隣接するタイルとしか通信しない。しかしながら、同じ技法を、このハードウェア構成を欠いているシステムにおいても使用することができる。

本明細書に説明する主題の特定の実施形態は、次の利点のうちの1つまたは複数を実現するために実装され得る。コンパイラは、様々なシャーディング技法を利用して、多数のコンピュートタイルを有するデバイスの性能を高めることができる。そのようなデバイスにおけるタスクの実行は、シャーディング技法を用いてデバイスの仕様/制約に適合し得る。コンパイラは、サブレイヤシャーディングを使用してデバイスの利用状況を高めることができる。コンパイラはまた、平行四辺形のタイムスライシングを使用して、タイルが何かの発生を待っているので仕事をまったく行わないというアイドルゾーンを低減する、またはなくすことができる。また、コンパイラは、オーバーシャーディングを使用して、タイル間のロードバランシングを改善し、コンパイル時に予測できないロードバランシング状況に対処することができる。コンパイラはまた、ジグザグシャーディングを使用して、タイル間のメモリ要件とコンピュータ計算要件とのバランスをとることもできる。

本明細書の主題の1つまたは複数の実施形態の詳細について、添付の図面および以下の説明で述べる。主題の他の特徴、態様、および利点は、本明細書、図面、および特許請求の範囲から明らかになるであろう。

多数のタイルを有するデバイスのマトリクス動作をシャーディングするための例示的な方法のフローチャートである。 サブレイヤシャーディングの一例を示す図である。 サブレイヤシャーディングの一例を示す図である。 平行四辺形のタイムスライシングの一例を示す図である。 平行四辺形のタイムスライシングの一例を示す図である。 平行四辺形のタイムスライシングの一例を示す図である。 平行四辺形のタイムスライシングの一例を示す図である。 オーバーシャーディングの一例を示す図である。 オーバーシャーディングの一例を示す図である。 オーバーシャーディングの一例を示す図である。 ジグザグシャーディングと呼ばれる別のバージョンのオーバーシャーディングの一例を示す図である。 ジグザグシャーディングと呼ばれる別のバージョンのオーバーシャーディングの一例を示す図である。 ジグザグシャーディングと呼ばれる別のバージョンのオーバーシャーディングの一例を示す図である。 多数の同期プロセッサを有するシステムにおける処理を実装するのに使用され得るタイルの一例を示す図である。

様々な図面における同様の参照数字および名称は、同様の要素を示す。

図1は、多数のタイルを有するデバイスのマトリクス動作をシャーディングするための例示的な方法のフローチャートである。上述したように、ターゲットデバイスでは、タイルを線形アレイで配置する、または線形アレイとして動作するように構成することができ、各タイルは、その隣接するタイルとしか通信しない。したがって、システムは、データフローグラフの受信に応答して、線形アレイ内のタイルの順序付けを考慮に入れる、グラフのノードとタイルとの間の割当てを生成することができる。便宜上、この例示的方法については、1つまたは複数の場所に位置し本明細書に従って適切にプログラミングされる、1つまたは複数のコンピュータからなるシステムによって行われると説明する。

システムは、複数のタイルを有するデバイスによって行われることになるマトリクス動作を指定するデータフローグラフの表現を受信する(110)。この文脈においては、マトリクス動作は、マトリクス動作またはベクトル動作を含むと理解すべきである。データフローグラフの各ノードは、そのノードに専用のマトリクスに対して行われることになるマトリクス動作を指定する。たとえば、グラフにおける各ノードは、ニューラルネットワークのレイヤを表すことができ、マトリクスは、そのレイヤについて使用されることになる重みおよび学習されることになる重みを記憶している。グラフの各エッジは、あるノードの出力が次のノードの入力になる、データの伝搬を表す。システムは、複数のタイルの各タイルに対するデータフローグラフの部分の複数の候補割当てを生成する(120)。シャーディングの問題は、複数の候補割当ての中からデバイスにおけるタイルに対するデータフローグラフの部分の最良の割当てを見つけるための検索問題として定式化され得る。評価されることになる候補の生成に関係する種々の技法については、より詳細に後述する。どの候補割当てが実際には最良であるかについては、データフローフグラフおよび特定のアプリケーションに大きく依存する。

システムは、デバイスの1つまたは複数のリソース制約に従って各候補割当てを評価する(130)。重要なリソース制約には、メモリ制約および帯域幅制約が含まれる。

機械学習アクセラレータについての1つの例示的なメモリ制約は、特定のタイルに割り当てられるすべてのマトリクスのすべての重みが、そのタイルに対してローカルであるスタティックランダムアクセスメモリ(SRAM)内に収まらなくてはならないことである。言い換えれば、各タイルは、集積化された常駐SRAM量を有することができ、それは、シャーディングを行うときのメモリ制約になる。この制約の理由には、速度および帯域幅が関係する。まず、機械学習アクセラレータは、可能な限り高速にモデルを介して推論パスを行うように設計されている。またいくつかのアプリケーションにとっては、ダイナミックランダムアクセスメモリ(DRAM)では、高速性が不十分である。加えて、マトリクスの重みは、大きく、そのため、動き回るのに困難な可能性がある。そのため、特定のタイルに割り当てられたすべてのマトリクスのすべての重みが、タイルのローカルSRAM内に収まることができるとき、タイルは、推論パス中または訓練更新中、重みの読取りおよび書込みに時間を費やす必要がない。

別の例示的なメモリ制約は、帯域幅制約である。帯域幅制約は、グラフのノード間をデータがいかに迅速に移動しなくてはならないかを指定する。提案された割当てが、グラフにおける特定のエッジの帯域幅閾値を超えることがあった場合、システムは、帯域幅制約に違反していることを決定することができる。

システムは、各候補割当ての評価に基づいて候補割当てのうちの1つを選択する(140)。1つの例として、システムは、レイヤシャーディングを行うことができ、ここでは、入力プログラムの異なるレイヤからの異なるマトリクスが、異なるそれぞれのタイルに割り当てられる。したがって、たとえば、8つのレイヤを有するニューラルネットワークでは、その重みマトリクスは8つのタイルにそれぞれ割り当てられていることができる。

1つまたは複数のリソース制約を満たす候補割当ての場合、システムは、どの割当てがデバイスにおけるタイルの利用状況を最良に最適化するかについて決定することができる。概して、これには、すべてのタイルにわたって最大のコンピュート時間量をコンピュータ計算すること、次いで、最小最大のコンピュート時間量を有する候補割当てを選択することが含まれる。サイクルレベルに至るまで事前にスケジューリング可能な同期タイルを有するデバイスの場合、これらの計算は、他の種類のデバイスについてのコンパイラ推定値よりもはるかにより正確である可能性がある。

システムは、候補割当てを選択した後、デバイスのタイルによって実行されることになるハードウェア命令を生成することによって、データフローグラフプログラムのさらなる引下げを行うことができる。次いで、システムは、ハードウェア命令をマトリクスの重みとともにデバイス上にロードし、デバイス上のハードウェア命令を実行して、データフローグラフによって表される動作を実施することができる。

図2A～図2Bは、サブレイヤシャーディングの例を示している。サブレイヤシャーディングは、データフローグラフにおける特定のノードの1つのマトリクスを分割し、異なる部分を異なるタイルに割り当てることを示す。図2Aは、マトリクス200の要素を対角線に沿って分割している1つの例示的な候補分割を示している。図2Bは、マトリクス200の要素が列間で分割されている別の例示的な候補分割を示している。代替としてまたは追加として、マトリクス200は、行間で分割することもできる。いくつかの実装形態においては、システムは、マトリクスがサイズの閾値を超えるときはいつでも、サブレイヤシャーディングを使用して候補割当てを生成する。

サブレイヤシャーディングのための候補割当てを生成するには、何らかのさらなる複雑さをデータフローグラフに加えることが要求される。具体的には、各レイヤのベクトル入力は、サブレイヤシャーディング結果の一部分を受信するあらゆるタイルに同報通信されなくてはならないことが多い。加えて、個々のタイルによって生成される部分和(partial sums)または部分アクティブ化(partial activations)は、同じタイルまたは異なるタイルのいずれかにおいて、後の段階で最終和または最終アクティブ化へとマージされなくてはならない。コンパイラは、サブレイヤシャーディングに関わる候補割当てを評価するとき、これらの追加的な複雑さを考慮に入れることができる。

図3A～図3Cは、平行四辺形のタイムスライシングの例を示している。平行四辺形タイムスライシングは、タイルが、異なる実行傾斜を有する異なるパスにおいて特定の動作を実行するときに有利な場合がある。実行傾斜は、シーケンス内のすべての動作をタイルがいかに迅速に完全に行うことができるかを示している。そのようなアプリケーションは、ニューラルネットワークでは一般的であり、たとえば、ここではすべてのタイルを介する単一のパスが、ネットワークを介する1つの推論パスを表すことができる。

図3Aは、異なる実行傾斜から生じるコンフリクト(conflict)を示している。図3Aにおいては、横軸は、時間を表している。図3Aにおけるタイルは、線形アレイ構造で配置され、それにより、各タイルは、そのすぐ隣の2つのタイルにしかデータを提供することができず、そのすぐ隣の2つのタイルからしかデータを受信することができない。いくつかの実装形態においては、線形アレイ構造は、たとえば、リング構造のように、巻き込んでおり、それにより、最後のタイルが、最初のタイルと通信することができ、その逆も同様である。

したがって、タイルは、まず、Pass AをTile0から始まってTile7まで順次に行う。Pass Aは、各タイルが前のタイルから出力を受信するまで実行を開始することができないという機械学習モデルの共通プロパティを有する。したがって、Tile1はTile0が終了するのを待たなくてはならない、Tile2はTile1が終了するのを待たなくてはならない、などである。

図3Aの破線は、この共通パターンがどのようにPass Aの平行四辺形を形成するのかを示している。

図3Aはまた、第2のパスPass Bも示している。Pass Bの動作は、Pass Aほど時間がかからず、そのため、Pass Bは、Pass Aよりも実行傾斜が急勾配である。

この例においては、Pass AおよびPass Bの実行傾斜が異なることにより、Tile5とTile6との間にコリジョン(collision)が生じる。このコリジョンは、Tile5がPass Bを終了する時までに、Tile6がその部分のPass Aをまだ終了していないという理由から発生する。そのため、ストール(stall)301および302を、コンパイラまたは実行時のいずれかによって導入しなくてはならず、それにより、Tile5は、Tile6がPass Aの動作を終了するまで、Pass Bの結果を提供するのを待つことになる。

図3Bは、異なる実行傾斜を管理するための代替の方策を示しており、この方策は、Pass Bがまだ開始しないうちに単一のストール303を導入し、それにより、Tile7におけるPass Bの最後の動作は、Pass Aの最後の動作の直後に実行することができるようにすることである。

これらの方策はともに、結果的に、タイルが作業をまったくせずにアイドル状態であるアイドルゾーン310および320をもたらす。アイドルゾーン310は、アイドルゾーン320よりも小さいが、多数のストールを導入することにより、図3Bにおける方策にはないコンパイル時または実行時の制御の複雑さが増すことになる。

図3Cは、実行傾斜の違いにより、追加のアイドルゾーンが実際にどのように導入され得るかを示している。図3Cにおいては、Pass Bの実行傾斜がより急勾配であることにより、結果的に第1のアイドルゾーン330が生じる。しかし、Pass AがPass Bの後に再び実行されることがあった場合、これにより、第2のアイドルゾーン340が導入される。

図3Dは、平行四辺形タイムスライシングを使用して、異なる実行傾斜をいかに管理するかを示している。異なる実行傾斜によって導入されるアイドルゾーンを減らすために、コンパイラは、すべてのパスに強制的に同じ実行傾斜を効果的にもたせるスケジュールを生成することができる。したがって、異なるパスは、効果的に一緒に収まって、アイドルゾーンがなくなる。

コンパイラは、ストールまたはバッファリングを使用して、より緩やかな実行傾斜を強制することができる。たとえば、図3Dに示されているように、Pass Bの実行傾斜は、異なるタイル間にバッファリングを導入することによって小さくされている。言い換えれば、Tile0がPass Bを完了した後、その結果はバッファ360に記憶される。次いで、すぐに、Tile0は、Pass Aの第2の反復の処理を開始することができる。代替としてまたは追加として、コンパイラは、Pass Bの終了とPass Aの第2の反復の開始との間にストールを挿入してもよい。この解決策は、図3Aに示されている手法よりも多くのストールを導入するが、アイドルゾーン全体は、実質的に、より小さいことに留意されたい。

緩やかな実行傾斜を強制すると、コンパイラが、候補割当てを評価するときに考慮に入れることができる制御の複雑さがさらにもたらされる。具体的には、緩やかな実行傾斜の強制は、特定のパスについてのタイミング制約をもたらす。たとえば、図3Dにおいては、タイミング制約は、Tile1におけるPass BはTile0におけるPass Bの直後に開始することができないことである。

図4A～図4Cは、オーバーシャーディングの例を示している。オーバーシャーディングは、ハードウェアが必要とするよりもより細かくマトリクスをシャーディングするための技法を示す。言い換えれば、コンピュータ計算は、単一のタイルによって行うことができることもあるが、マトリクスは、他の理由で何らかの形でシャーディングされる。それらの他の理由は、ロードバランシングに関係していることが多い。

図4Aは、8つのタイルにわたって9つのレイヤを有する単一のPass Aの実行を示している。したがって、この例における9番目のレイヤは、Tile0に完全に割り当てられている。Tile0は、9番目のレイヤのすべての動作を完全に行うための利用可能性およびメモリ容量を有するが、これにより、この時間中、残りのタイルはまったく占有されていない状態になる。

図4Bは、Pass Aの9番目のレイヤのオーバーシャーディングを示している。言い換えれば、たとえ単一のタイルが9番目のレイヤのすべての動作を行うことができることがあったとしても、9番目のレイヤは、他のタイルの8つすべてにわたってそれを分散するようにオーバーシャーディングされる。レイヤ内データの依存関係はあっても、またはなくてもよく、そのため、9番目のレイヤの異なる部分は、部分的に並行して実行されても、または完全に並行して実行されてもよい。

そのため、デバイスのロードバランシングは、1つのタイルのみが9番目のレイヤを行っている場合よりも優れている。このことは、デバイスが同様に他のコンピュータ計算も行っている場合、特に有利であり得る。

図4Cは、実行時ロードバランシングに対処するためのオーバーシャーディングの別のアプリケーションを示している。いくつかのアプリケーションでは、タイルに対する実行時ロードは、事前には知られていない。1つのそのような例は、デバイスが、異なる変換に向けて訓練されたいくつかの異なるモデルを使用して、自動機械変換を行うのに使用でき得ることである。たとえば、図4Cの左側に示されているように、Tile0がModel Aを実行するために割り当て可能である、Tile1がModel Bを実行するために割り当て可能である、などである。しかしながら、これらのモデルが使用される実際の順序は、特にデバイスが、受信側Internetトラフィックをサービスするバックエンドサーバで使用される場合、コンパイル時には知られていない。

そのため、Tile0が大部分の要求に対処し、他のタイルはまれにしか使用されないという場合もあり得る。

何らかの実行時ロードバランシングを行うために、コンパイラは、図4Cの右側に示されているように、モデルをオーバーシャーディングし、すべてのモデルをすべてのチップにわたって分散させることができる。

次に、実行時に、すべてのタイルの利用状況を、実行時ロードの実際の分散にかかわらず、実質的に等しくすることができる。

図5A～図5Cは、ジグザグシャーディングと呼ばれる別のバージョンのオーバーシャーディングの例を示している。ニューラルネットワークを含む多くの機械学習アプリケーションでは、レイヤのコンピュート複雑さは減少するが、メモリ要件は増加するという共通のパターンが現れる。

したがって、図5Aに示されているように、メモリパターンは、結果的に、各後続タイルがますます多くのメモリを要求することになり得る。また、図5Bに示されているように、コンピュータ計算パターンが要求するコンピュータ計算リソースは、ますます減少する。

コンパイラは、ジグザグシャーディングを使用して、すべてのタイルがメモリ割当てとコンピュータ計算割当てとのバランスをより多くとるようにすることができる。ジグザグシャーディングは、基本的に、異なる補完レイヤを、それらが同じタイルによって実行されるように一緒にペアリングする。したがって、たとえば、ジグザグシャーディングは、同じタイルが、1番目のレイヤと8番目のレイヤ、2番目のレイヤと7番目のレイヤ、3番目のレイヤと6番目のレイヤ、および4番目のレイヤと5番目のレイヤを確実に実行することになるようにすることができる。この割当ては、コンピュータ計算パターンがジグザグの形状をとる図5Cに示されている。

図5Cに示されているように、1番目のレイヤであるレイヤ1は、1番目のレイヤのコンピュータ計算の複雑さを分割するために、オーバーシャーディングされ、タイル0～3間に分散される。同様であるが補完的な形で、8番目のレイヤもまた、8番目のレイヤのメモリ要件を分割するために、分割され、同じタイル0～3間に分散される。

同様に、2番目のレイヤはつねに7番目のレイヤと同じタイルに割り当てられ、3番目のレイヤはつねに6番目のレイヤと同じタイルに割り当てられ、4番目のレイヤはつねに5番目のレイヤと同じタイルに割り当てられる。

図2～図4に関連して上述したシャーディング技法の例をそれぞれ、それぞれ単独か、または他のシャーディング技法のうちのいずれか1つもしくは複数との組合せかのいずれかで使用してもよい。

図6は、多数の同期プロセッサを有するシステムでの処理を実装するのに使用され得るタイル600の一例を示している。たとえば、タイル600は、線形のタイルアレイにおける1つのタイルとして、またはタイルが線形のタイルアレイとして動作するシステムにおいて使用することができる。

各タイル600は、ローカルメモリ602、およびメモリ602に結合されたコンピュータ計算アレイ604を含む。ローカルメモリ602は、コンピュータ計算アレイ604に近接して位置決めされた物理メモリを含む。コンピュータ計算アレイ604は、多数のセル606を含む。コンピュータ計算アレイ604の各セル606は、セル606へのアクティブ化入力および重み入力などのデータ入力に基づいてコンピュータ計算(たとえば、乗算および累積演算)を行うように構成された回路機構を含む。各セルは、クロック信号のサイクルでコンピュータ計算(たとえば、乗算および累積演算)を行うことができる。コンピュータ計算アレイ604は、行が列よりも多くても、列が行よりも多くても、または列と行の数が等しくてもよい。例として、図6にされている例においては、コンピュータ計算アレイ604は、8つの行と8つの列で構成された64個のセルを含む。他のコンピュータ計算アレイのサイズ、とりわけ16個のセル、32個のセル、128個のセル、または256個のセルを有するコンピュータ計算アレイなども可能である。各タイルは、同じ数のセルおよび/または同じサイズのコンピュータ計算アレイを含むことができる。

タイル600に含まれているメモリ602は、たとえば、SRAMなどのランダムアクセスメモリ(RAM)を含むことができる。各メモリ602は、多数のタイルを有するシステムのn個のタイル502に関連する総メモリのうちの(1/n)番目を記憶するように構成され得る。メモリ602は、単一のチップとして設けることも、または多数のチップで設けることもできる。たとえば、図6に示されているメモリ602は、4つの単一ポートSRAMとして設けられ、それらはそれぞれ、コンピュータ計算アレイ604に結合されている。あるいは、メモリ602は、他の構成の中でもとりわけ、2つの単一ポートSRAMまたは8つの単一ポートSRAMとして設けることもできる。メモリの結合容量は、誤り訂正コーディング後、たとえば、16kB、32kB、64kB、または128kBとすることができるが、これらに限定するものではない。物理メモリ602をコンピュータ計算アレイに対してローカルに設けることによって、配線の密度は、大幅に低減させることができる。

タイル600はまた、制御可能なバスラインを含む。制御可能なバスラインは、多数の異なるグループに分類されてもよい。たとえば、制御可能なバスラインは、各基本方位にタイル間でデータを転送するように構成された第1のグループの汎用の制御可能なバスライン610を含むことができる。つまり、第1のグループの制御可能なバスライン610は、格子状のタイルの第1の次元101に沿った第1の方位(図6では「東(East)」と呼ばれる)に向かってデータを転送するように構成されたバスライン610aと、格子状のタイルの第1の寸法101に沿った、第1の方位とは逆である第2の方位(図6では「西(West)」と呼ばれる)に向かってデータを転送するように構成されたバスライン610bと、格子状のタイルの第2の寸法103に沿った第3の方位(図6では「北(North)」と呼ばれる)に向かってデータを転送するように構成されたバスライン610cと、格子状のタイルの第2の寸法103に沿った、第3の方位とは逆である第4の方位(図6では「南(South)」と呼ばれる)に向かってデータを転送するように構成されたバスライン610dとを含む。汎用のバスライン610は、制御データ、アクティブ化入力データ、通信インターフェースからおよび/または通信インターフェースへのデータ、ベクトル処理ユニットからおよび/またはベクトル処理ユニットへのデータ、ならびにタイル600によって記憶および/または使用されることになるデータ(たとえば、重み入力)を運ぶように構成され得る。タイル600は、制御可能なバスラインを制御するための、したがって、タイル600へのおよび/もしくはタイル600からの、ならびに/またはメモリ602からのデータをルーティングするための1つまたは複数の制御要素621(たとえば、フリップフロップおよびマルチプレクサ)を含むことができる。

制御可能なバスラインはまた、本明細書でコンピュータ計算アレイ部分和バスライン(computational array partial sum bus line)620と呼ばれる、第2のグループの制御可能なバスラインを含むことができる。コンピュータ計算アレイ部分和バスライン620は、コンピュータ計算アレイ604によって行われるコンピュータ計算から出力されるデータを運ぶように構成され得る。たとえば、バスライン620は、図6に示されているように、コンピュータ計算アレイ604における行から得られる部分和データを運ぶように構成され得る。そのような場合においては、バスライン620の数は、アレイ604内の行の数と一致することになる。例として、8×8のコンピュータ計算アレイの場合、コンピュータ計算アレイ604における対応する行の出力部にそれぞれが結合されている8本の部分和バスライン620が存在することになる。コンピュータ計算アレイ出力バスライン620は、たとえば、タイルの線形アレイにおける隣接するタイルのコンピュータ計算アレイへの入力として、システム内で別のタイルに結合するようにさらに構成され得る。たとえば、タイル600のアレイ部分和バスライン620は、タイル600から少なくとも1つのタイル分だけ離れて位置する2番目のタイルのコンピュータ計算アレイの入力部(たとえば、部分和620a)を受け入れるように構成され得る。次いで、コンピュータ計算アレイ604の出力部が、部分和バスライン620に追加されて、新規の部分和620bを作り出し、それは、タイル600から出力され得る。次いで、部分和620bは、別のタイルに渡されても、または代替として、ベクトル処理ユニットに渡されてもよい。たとえば、各バスライン620は、ベクトル処理ユニットの対応する区分(図5における区分506など)に結合されてもよい。

本明細書に記載の主題の諸実施形態および機能動作は、本明細書に開示されている構造体およびそれらの構造的均等物を含む、デジタル電子回路機構において、有形具現化コンピュータソフトウェアまたはファームウェアにおいて、コンピュータハードウェアにおいて、あるいはそれらのうちの1つまたは複数の組合せにおいて実装され得る。本明細書に記載の主題の実施形態は、1つまたは複数のコンピュータプログラム、すなわち、データ処理装置によって実行されるように、またはデータ処理装置の動作を制御するように、有形の非一時的記憶媒体においてエンコーディングされるコンピュータプログラム命令の1つまたは複数のモジュールとして実装され得る。コンピュータ記憶媒体は、機械可読記憶デバイス、機械可読記憶基板、ランダムアクセスメモリデバイス、もしくはシリアルアクセスメモリデバイス、あるいはそれらのうちの1つまたは複数の組合せとすることができる。代替としてまたは追加として、プログラム命令は、データ処理装置によって実行されるのに適している受信器装置に送信される情報をエンコーディングするために生成される人工的に生成された伝搬信号、たとえば、機械生成された電気信号、光信号、または電磁信号においてエンコーディングされ得る。

「データ処理装置(data processing apparatus)」という用語は、データ処理ハードウェアを示し、例としてプログラマブルプロセッサ、コンピュータ、または多数のプロセッサもしくコンピュータを含む、データを処理するためのすべての種類の装置、デバイス、および機械を包含する。また、装置は、専用の論理回路機構、たとえば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)とすることも、またはそれらをさらに含むこともできる。装置は、ハードウェアに加えて、コンピュータプログラムの実行環境を創出するコード、たとえば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの1つまたは複数の組合せを構成するコードをオプションで含むことができる。

プログラム、ソフトウェア、ソフトウェアアプリケーション、アプリ、モジュール、ソフトウェアモジュール、スクリプト、またはコードとも呼ばれるまたは記述される場合もあるコンピュータプログラムは、コンパイル型言語もしくはインタープリタ型言語、または宣言型言語もしくは手続き型言語を含む、任意の形態のプログラミング言語で書くことができ、スタンドアロンプログラムとして、またはモジュール、コンポーネント、サブルーチン、もしくはコンピューティング環境において使用するのに適している他のユニットとしてを含む任意の形態で展開することができる。プログラムは、必要ではないが、ファイルシステム内のファイルに対応してもよい。プログラムは、他のプログラムまたはデータを保持するファイルの一部分、たとえばマークアップ言語文書内に記憶されている1つまたは複数のスクリプト内に、問題のプログラムに専用の単一のファイル内に、または多数の協調ファイル、たとえば1つまたは複数のモジュール、サブプログラム、もしくはコードの一部分を記憶するファイル内に記憶することができる。コンピュータプログラムは、1つのコンピュータにおいて実行されるように、または1つのサイトに位置する、もしくは多数のサイトにわたって分散され、データ通信ネットワークによって相互接続されている多数のコンピュータにおいて実行されるように展開することができる。

1つまたは複数のコンピュータからなるシステムが特定の動作またはアクションを行うように構成されているとは、システムが、動作に際して、システムに動作またはアクションを行わせるソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せをインストールしていることを意味する。1つまたは複数のコンピュータプログラムが特定の動作またはアクションを行うように構成されているとは、その1つまたは複数のプログラムが、データ処理デバイスによって実行されると、装置に動作またはアクションを行わせる命令を含むことを意味する。

本明細書において使用されるとき、「エンジン(engine)」または「ソフトウェアエンジン(software engine)」は、入力とは異なる出力を提供する、ソフトウェア実装入力/出力システムを示す。エンジンは、ライブラリ、プラットフォーム、ソフトウェア開発キット(「software development kit、SDK」)、オブジェクトなど、エンコーディングされた機能ブロックとすることができる。各エンジンは、1つまたは複数のプロセッサおよびコンピュータ可読媒体を含む、任意の適切なタイプのコンピュータ計算デバイス、たとえば、サーバ、モバイルフォン、タブレットコンピュータ、ノートブックコンピュータ、音楽プレーヤ、電子ブックリーダー、ラップトップコンピュータもしくはデスクトップコンピュータ、PDA、スマートフォン、または他の固定式もしくは携帯型デバイスにおいて実装され得る。加えて、エンジンのうちの2つ以上が、同じコンピュータ計算デバイスにおいて実装されも、または異なるコンピュータ計算デバイスにおいて実装されてもよい。

本明細書に記載の方法および論理フローは、入力データに対して動作し、出力を生成することによって機能を行うように1つまたは複数のコンピュータプログラムを実行する1つまたは複数のプログラマブルコンピュータによって行うことができる。方法および論理フローは、専用論理回路機構、たとえばFPGAもしくはASICによって、または専用論理回路機構と1つもしくは複数のプログラムされたコンピュータとの組合せによって行うこともできる。

コンピュータプログラムの実行に適しているコンピュータは、汎用のマイクロプロセッサもしくは専用のマイクロプロセッサまたはその両方、あるいは任意の他の種類の中央処理ユニットに基づくことができる。概して、中央処理ユニットは、読取り専用メモリもしくはランダムアクセスメモリまたはその両方から命令およびデータを受信することになる。コンピュータの必須要素は、命令を行うまたは実行するための中央処理ユニット、ならびに命令およびデータを記憶するための1つまたは複数のメモリデバイスである。中央処理ユニットおよびメモリは、専用論理回路機構によって補完されも、またはその中に組み込まれていてもよい。概して、コンピュータはまた、データを記憶するための1つまたは複数の大容量記憶デバイス、たとえば磁気ディスク、光磁気ディスク、または光ディスクも含むか、あるいはそれらからデータを受信する、もしくはそれらにデータを転送する、またはその両方を行うために動作可能に結合されることになる。しかしながら、コンピュータは、そのようなデバイスを有する必要はない。その上、コンピュータは、別のデバイス、たとえば、ほんの数例を挙げると、モバイル電話、パーソナルデジタルアシスタント(PDA)、モバイルオーディオもしくはビデオプレーヤ、ゲームコンソール、全地球測位システム(GPS)受信器、または携帯型記憶デバイス、たとえばユニバーサルシリアルバス(USB)フラッシュドライブ内に埋め込まれていてもよい。

コンピュータプログラム命令およびデータを記憶するのに適しているコンピュータ可読媒体は、例として半導体メモリデバイス、たとえばEPROM、EEPROM、およびフラッシュメモリデバイス;磁気ディスク、たとえば内部ハードディスクまたはリムーバブルディスク;光磁気ディスク;およびCD-ROMディスクおよびDVD-ROMディスクを含む、すべての形態の不揮発性メモリ、媒体、ならびにメモリデバイスを含む。

ユーザとの対話を提供するために、本明細書に記載の主題の実施形態は、情報をユーザに表示するためのディスプレイデバイス、たとえばCRT(陰極線管)またはLCD(液晶ディスプレイ)モニタと、ユーザがコンピュータに入力を提供することができるキーボードおよびポインティングデバイス、たとえばマウス、トラックボール、またはプレゼンスセンシティブディスプレイもしくは他のサーフェスを有するコンピュータにおいて実装することができる。ユーザとの対話を提供するために、他の種類のデバイスも同様に使用することができ、たとえばユーザに提供されるフィードバックは、任意の形態の感覚的フィードバック、たとえば視覚的フィードバック、聴覚的フィードバック、または触覚的フィードバックとすることができ、音響入力、音声入力、または触覚入力を含む、ユーザからの入力は、任意の形態で受信することができる。加えて、コンピュータは、ユーザによって使用されるデバイスに文書を送信し、デバイスから文書を受信することによって、たとえばユーザのデバイス上のウェブブラウザに、そのウェブブラウザから受信した要求に応答して、ウェブページを送信することによって、ユーザと対話することができる。また、コンピュータは、パーソナルデバイス、たとえばメッセージングアプリケーションを実行しているスマートフォンにテキストメッセージまたは他の形態のメッセージを送信し、引き換えにユーザから応答メッセージを受信することによってユーザと対話することができる。

本明細書に記載の主題の実施形態は、バックエンドコンポーネントを、たとえばデータサーバとして含む、またはミドルウェアコンポーネント、たとえばアプリケーションサーバを含む、またはフロントエンドコンポーネント、たとえばグラフィカルユーザインターフェース、ウェブブラウザ、もしくはユーザが、本明細書に記載の主題の実装形態と対話することができるアプリを有するクライアントコンピュータを含む、あるいは1つまたは複数のそのようなバックエンドコンポーネント、ミドルウェアコンポーネント、もしくはフロントエンドコンポーネントの任意の組合せを含むコンピューティングシステムにおいて実装することができる。システムのコンポーネントは、任意の形態または媒体のデジタルデータ通信、たとえば通信ネットワークによって相互接続することができる。通信ネットワークの例は、ローカルエリアネットワーク(LAN)および広域ネットワーク(WAN)、たとえばInternetを含む。

コンピューティングシステムは、クライアントとサーバとを含むことができる。クライアントとサーバは、概して互いに離れており、典型的には、通信ネットワークを介して対話する。クライアントとサーバの関係は、コンピュータプログラムがそれぞれのコンピュータにおいて動作し、互いにクライアント/サーバ関係を有するおかげで生じる。いくつかの実施形態においては、サーバは、たとえばクライアントとして動作するデバイスと対話するユーザにデータを表示し、ユーザからユーザ入力を受信する目的のために、データ、たとえばHTMLページをユーザデバイスに送信する。ユーザデバイスにおいて生成されたデータ、たとえばユーザ対話の結果は、デバイスからサーバにおいて受信することができる。

上述の実施形態に加えて、次の実施形態もまた革新的である:
実施形態1は、
複数の同期タイルを有するデバイスによって行われることになるそれぞれのマトリクス動作をそれぞれが表す複数のノードを含むデータフローグラフの表現を受信するステップと、
前記複数の同期タイルの各タイルに対する前記データフローグラフのそれぞれの部分の複数の候補割当てを生成するステップと、
前記デバイスの1つまたは複数のリソース制約に従って前記複数の候補割当ての各候補割当てを評価するステップと、
各候補割当ての評価に基づいて前記候補割当てのうちの1つを選択するステップと
を含む方法である。

実施形態2は、前記複数の同期タイルの各タイルが、独立した処理要素のコンピュータ計算アレイを含む、実施形態1に記載の方法である。

実施形態3は、1つまたは複数のリソース制約に従って前記複数の候補割当てを生成するステップが、SRAMメモリ制約に従って前記候補割当てを生成するステップを含み、前記SRAMメモリ制約は、前記関連する動作のすべての重みが、対応する同期タイルに対してローカルであるローカルSRAM内に収まらなくてはならないことを指定する、実施形態1または2に記載の方法である。

実施形態4は、各ローカルSRAMが、前記動作を行うことになる前記同じ同期タイルに集積化された常駐メモリである、実施形態3に記載の方法である。

実施形態5は、前記複数の候補割当てを生成するステップが、異なるそれぞれのタイルに対して異なるそれぞれのレイヤのマトリクスを割り当てるステップを含む、実施形態1～4のいずれか1つに記載の方法である。

実施形態6は、前記複数の候補割当てを生成するステップが、異なるそれぞれの同期タイルに対して前記マトリクスの異なるブロックを割り当てるステップを含む、プログラムにおける特定のノードについてのマトリクスに対してサブレイヤシャーディングを行うステップを含む、実施形態1～5のいずれか1つに記載の方法である。

実施形態7は、異なるそれぞれの同期タイルに対して前記マトリクスの異なるブロックを割り当てるステップが、前記マトリクスを行もしくは列に沿って分割するステップ、または前記マトリクスを対角線上に分割するステップを含む、実施形態6に記載の方法である。

実施形態8は、前記動作が、サイズ閾値を超える任意のマトリクスに対してサブレイヤシャーディングを行うステップをさらに含む、実施形態7に記載の方法である。

実施形態9は、前記複数の候補割当てを生成するステップは、初期には異なる実行傾斜を有する異なるパスが、実質的に同様の実行傾斜を有するように、平行四辺形タイムスライシングを行うステップを含む、実施形態1～8のいずれか1つに記載の方法である。

実施形態10は、平行四辺形タイムスライシングを行うステップが、
2つの異なるパスのそれぞれについてそれぞれの実行傾斜をコンピュータ計算するステップと、
第1のパスが、第2のパスよりも小さい実行傾斜を有することを決定するステップと、
それに応答して、前記第1のパスがより緩やかな実行傾斜を有するように前記候補割当てを修正するステップと
を含む、実施形態9に記載の方法である。

実施形態11は、前記候補割当てを修正するステップが、前記候補割当てにバッファリングまたはストールを挿入するステップを含む、実施形態10に記載の方法である。

実施形態12は、前記複数の候補割当てを生成するステップが、前記タイルのうちの1つによって全体的に行うことが可能になる前記データフローグラフのノードが多数の異なるタイル間で分割されるように、オーバーシャーディングを行うステップを含む、実施形態1～11のいずれか1つに記載の方法である。

実施形態13は、オーバーシャーディングを行うステップが、各タイルに対して1つのそれぞれのレイヤを割り当て、すべての前記タイル間で最後のレイヤを分割するステップを含む、実施形態12に記載の方法である。

実施形態14は、オーバーシャーディングを行うステップが、すべての前記タイルにわたって複数のマトリクスを分割するステップを含む、実施形態12に記載の方法である。

実施形態15は、前記複数の候補割当てを生成するステップが、異なるメモリおよびコンピュータ計算要件を有する異なるレイヤを一緒にペアリングすることによってジグザグシャーディングを行うステップを含む、実施形態1～14のいずれか1つに記載の方法である。

実施形態16は、異なるレイヤを一緒にペアリングすることが、最初のレイヤを最後のレイヤとペアリングして、同じタイルが前記最初のレイヤと前記最後のレイヤとの両方を実行するようにすることを含む、実施形態15に記載の方法である。

実施形態17は、前記最初のレイヤが、最も大きいコンピュータ計算要件を有し、前記最後のレイヤが、最も大きいメモリ要件を有する、実施形態16に記載の方法である。

実施形態18は、前記タイルが、線形アレイで配置され、それにより、各タイルが1つまたは2つの隣接タイルにしかデータを提供しないように構成されている、実施形態1～17のいずれか1つに記載の方法である。

実施形態19は、1つまたは複数のコンピュータと、前記1つまたは複数のコンピュータによって実行されると、前記1つまたは複数のコンピュータに実施形態1～18のいずれか1つに記載の方法を行わせるように動作可能な命令を記憶する1つまたは複数の記憶デバイスとを備えるシステムである。

実施形態20は、コンピュータプログラムによりエンコーディングされるコンピュータ記憶媒体であって、前記プログラムが、データ処理装置によって実行されると、前記データ処理装置に実施形態1～18のいずれか1つに記載の方法を行わせるように動作可能な命令を含む、コンピュータ記憶媒体である。

本明細書は、多くの具体的な実装形態の詳細を含んでいるが、これらは、いずれかの発明の範囲に対する限定、または特許請求され得ることの範囲に対する限定として解釈すべきではなく、むしろ、特定の発明の特定の実施形態に特有である場合がある特徴の説明として解釈すべきである。本明細書において別個の実施形態の文脈で説明されている特定の特徴は、単一の実施形態において組合せで実装することもできる。逆に、単一の実施形態の文脈で説明されている様々な特徴は、多数の実施形態において別個に、または任意の適切な副組合せで実装することもできる。その上、特徴は、特定の組合せで機能すると上述される場合があり、さらにはそのようなものとして当初は特許請求される場合もあるが、特許請求された組合せからの1つまたは複数の特徴は、場合によっては組合せから削除することができ、特許請求された組合せは、副組合せまたは副組合せの変形形態を対象としてもよい。

同様に、動作は、特定の順序で図面に描かれているが、このことは、望ましい結果を達成するために、そのような動作が示された特定の順序もしくは逐次的な順序で行われること、または示されたすべての動作が行われることを必要とするものと理解すべきではない。特定の状況では、マルチタスキングおよび並列処理が有利な場合がある。その上、上述した実施形態における様々なシステムモジュールおよびコンポーネントの分離は、すべての実施形態においてそのような分離を必要とするものと理解すべきではなく、説明したプログラムコンポーネントおよびシステムは、概して単一のソフトウェア製品において一緒に集積化することも、または多数のソフトウェア製品にパッケージ化することもできることを理解すべきである。

主題の特定の実施形態について説明してきた。他の実施形態は、添付の特許請求の範囲の範囲内にある。たとえば、特許請求の範囲内に列挙されたアクションは、異なる順序で行っても、望ましい結果を達成することができる。1つの例として、添付の図において描かれた方法には、望ましい結果を達成するために、示された特定の順序、または逐次的な順序が必ずしも必要ではない。ある種のいくつかの場合においては、マルチタスキングおよび並列処理が有利な場合がある。

101 第1の寸法
103 第2の寸法
200 マトリクス
301、302、303 ストール
310、320、330、340 アイドルゾーン
360 バッファ
502 タイル
506 区分
600 タイル
602 ローカルメモリ、物理メモリ
604 コンピュータ計算アレイ
606 セル
610 汎用の制御可能なバスライン
610a、610b、610c、610d バスライン
620 コンピュータ計算アレイ部分和バスライン
620a、620b 部分和
621 制御要素

Claims (20)

1つまたは複数のコンピュータと、前記1つまたは複数のコンピュータによって実行されると、前記1つまたは複数のコンピュータに動作を行わせるように動作可能な命令を記憶する1つまたは複数の記憶デバイスとを備えるシステムであって、前記動作が、
複数の同期タイルを有するデバイスによって行われることになるそれぞれのマトリクス動作をそれぞれが表す複数のノードを含むデータフローグラフの表現を受信することと、
前記複数の同期タイルの各タイルに対する前記データフローグラフのそれぞれの部分の複数の候補割当てを生成することと、
前記デバイスの1つまたは複数のリソース制約に従って前記複数の候補割当ての各候補割当てを評価することと、
各候補割当ての評価に基づいて前記候補割当てのうちの1つを選択することと
を含む、
システム。

前記複数の同期タイルの各タイルが、独立した処理要素のコンピュータ計算アレイを含む、請求項1に記載のシステム。

1つまたは複数のリソース制約に従って前記複数の候補割当てを生成することが、スタティックランダムアクセスメモリ(SRAM)メモリ制約に従って前記候補割当てを生成することを含み、前記SRAMメモリ制約は、関連する動作のすべての重みが、対応する同期タイルに対してローカルであるローカルSRAM内に収まらなくてはならないことを指定する、請求項1に記載のシステム。

各ローカルSRAMが、前記動作を行うことになる同じ同期タイルに集積化された常駐メモリである、請求項3に記載のシステム。

前記複数の候補割当てを生成することが、異なるそれぞれのタイルに対して異なるそれぞれのレイヤのマトリクスを割り当てることを含む、請求項1に記載のシステム。

前記複数の候補割当てを生成することが、プログラムにおける特定のノードについてのマトリクスに対してサブレイヤシャーディングを行うことを含み、前記サブレイヤシャーディングを行うことが、異なるそれぞれの同期タイルに対して前記マトリクスの異なるブロックを割り当てることを含む、請求項1に記載のシステム。

異なるそれぞれの同期タイルに対して前記マトリクスの異なるブロックを割り当てることが、前記マトリクスを行もしくは列に沿って分割すること、または前記マトリクスを対角線上に分割することを含む、請求項6に記載のシステム。

前記動作が、サイズ閾値を超える任意のマトリクスに対してサブレイヤシャーディングを行うことをさらに含む、請求項7に記載のシステム。

前記複数の候補割当てを生成することは、初期には異なる実行傾斜を有する異なるパスが、実質的に同様の実行傾斜を有するように、平行四辺形タイムスライシングを行うことを含む、請求項1に記載のシステム。

平行四辺形タイムスライシングを行うことが、
2つの異なるパスのそれぞれについてそれぞれの実行傾斜をコンピュータ計算することと、
第1のパスが、第2のパスよりも小さい実行傾斜を有することを決定することと、
それに応答して、前記第1のパスがより緩やかな実行傾斜を有するように前記候補割当てを修正することと
を含む、請求項9に記載のシステム。

前記候補割当てを修正することが、前記候補割当てにバッファリングまたはストールを挿入することを含む、請求項10に記載のシステム。

前記複数の候補割当てを生成することが、前記タイルのうちの1つによって全体的に行うことが可能になる前記データフローグラフのノードが多数の異なるタイル間で分割されるように、オーバーシャーディングを行うことを含む、請求項1に記載のシステム。

オーバーシャーディングを行うことが、各タイルに対して1つのそれぞれのレイヤを割り当て、すべての前記タイル間で最後のレイヤを分割することを含む、請求項12に記載のシステム。

オーバーシャーディングを行うことが、すべての前記タイルにわたって複数のマトリクスを分割することを含む、請求項12に記載のシステム。

前記複数の候補割当てを生成することが、異なるメモリおよびコンピュータ計算要件を有する異なるレイヤを一緒にペアリングすることによってジグザグシャーディングを行うことを含む、請求項1に記載のシステム。

異なるレイヤを一緒にペアリングすることが、最初のレイヤを最後のレイヤとペアリングして、同じタイルが前記最初のレイヤと前記最後のレイヤとの両方を実行するようにすることを含む、請求項15に記載のシステム。

前記最初のレイヤが、最も大きいコンピュータ計算要件を有し、前記最後のレイヤが、最も大きいメモリ要件を有する、請求項16に記載のシステム。

前記タイルが、線形アレイで配置され、それにより、各タイルが1つまたは2つの隣接タイルにしかデータを提供しないように構成されている、請求項1に記載のシステム。

請求項1から18のいずれか一項に記載の動作を行うステップを含む方法。

コンピュータプログラムによりエンコーディングされるコンピュータ記憶媒体であって、前記プログラムが、データ処理装置によって実行されると、前記データ処理装置に請求項1から18のいずれか一項に記載の方法を行わせるように動作可能な命令を含む、コンピュータ記憶媒体。

Images