(57)【要約】パターンを認識するように装置を訓練する方法システムは、機械学習プロセスの複数のステップを実行するホストプロセッサをその装置に設けるステップと、少なくとも２つのプロセッサを有するアクセラレータをその装置に設けるステップと、訓練パターンデータをホストプロセッサに入力するステップと、訓練パターンデータを使用してホストプロセッサによる機械学習プロセスにおける係数変化を求めるステップと、訓練データをアクセラレータに転送するステップと、訓練データを使用してアクセラレータの少なくとも２つのプロセッサによってカーネルの複数のドット積を求めるステップと、ドット積をホストプロセッサに転送して戻すステップと、を有する。
2011524049.tif 000002
【特許請求の範囲】
【請求項１】
パターンを認識するように装置を訓練する方法であって、
機械学習プロセスの複数のステップを実行するホストプロセッサを前記装置に設けるステップと、
少なくとも２つのプロセッサを有するアクセラレータを前記装置に設けるステップと、
訓練パターンデータを前記ホストプロセッサに入力するステップと、
前記訓練データを前記アクセラレータに転送するステップと、
前記訓練パターンデータを使用して前記ホストプロセッサによる前記機械学習プロセスにおける係数変化を求めるステップと、
１つまたは２つ以上の訓練ベクトルに関する指標を前記アクセラレータに転送するステップと、
前記訓練データを使用して前記アクセラレータの前記少なくとも２つのプロセッサによってカーネルの複数のドット積を求めるステップと、
前記ドット積を前記ホストプロセッサに転送して戻すステップと、
を有する方法。
【請求項２】
前記カーネルの複数のドット積を使用して、前記ホストプロセッサによる前記機械学習プロセスの複数のカーネルを求めるステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記カーネルを使用して、前記ホストプロセッサによる前記機械学習プロセスの勾配を求めるステップをさらに有する、請求項２に記載の方法。
【請求項４】
前記訓練データを前記アクセラレータに転送する前記ステップの前に、前記ホストプロセッサによって前記訓練データの精度を低下させるステップをさらに有する、請求項１に記載の方法。
【請求項５】
前記ドット積を前記ホストプロセッサに転送して戻す前記ステップの前に、前記アクセラレータによって前記ドット積の精度を低下させるステップをさらに有する、請求項４に記載の方法。
【請求項６】
前記ドット積を前記ホストプロセッサに転送して戻す前記ステップの前に、前記アクセラレータによって、前記カーネルのドット積の精度を低下させるステップをさらに有する、請求項１に記載の方法。
【請求項７】
前記アクセラレータは前記少なくとも２つのプロセッサの各々に対応付けられているメモリバンクをさらに有し、前記カーネルのドット積を前記ホストプロセッサに転送して戻すステップの前に、前記精度が低下させられたカーネルのドット積を複数のグループに分割し、前記カーネルのドット積の複数のグループの各々を前記複数のメモリバンクの１つに格納するステップをさらに有する、請求項６に記載の方法。
【請求項８】
前記カーネルの複数のドット積は、前記アクセラレータの前記少なくとも２つのプロセッサを使用して、並列に求められる、請求項１に記載の方法。
【請求項９】
前記カーネルの複数のドット積は、独立した別個の複数のチャンク内で決定される、請求項１に記載の方法。
【請求項１０】
前記アクセラレータは前記少なくとも２つのプロセッサの各々に対応付けられているメモリバンクをさらに有し、前記カーネルのドット積を前記ホストプロセッサに転送して戻すステップの前に、前記カーネルのドット積を複数のグループに分割し、前記カーネルのドット積の複数のグループの各々を前記複数のメモリバンクの１つに格納するステップをさらに有する、請求項１に記載の方法。
【請求項１１】
パターンを認識するように装置を訓練するシステムであって、
入力された訓練データから、機械学習プロセスの係数変化を求める、前記装置のホストプロセッサと、
前記訓練データを使用してカーネルの複数のドット積を求める少なくとも２つのプロセッサを有するアクセラレータと、
前記訓練データを前記ホストプロセッサから前記アクセラレータまで転送し、かつ前記カーネルのドット積を前記アクセラレータから前記ホストプロセッサまで転送する少なくとも１つの伝達路と、
を有するシステム。
【請求項１２】
前記ホストプロセッサは、前記機械学習プロセスの複数のカーネルを求めるために前記カーネルのドット積を使用する、請求項１１に記載のシステム。
【請求項１３】
前記ホストプロセッサは、前記機械学習プロセスの勾配を求めるために前記カーネルを使用する、請求項１２に記載のシステム。
【請求項１４】
前記ホストプロセッサは、前記アクセラレータへの転送前に、前記訓練データの精度を低下させる、請求項１１に記載のシステム。
【請求項１５】
前記アクセラレータは、前記ホストプロセッサへの転送前に、前記カーネルのドット積の精度を低下させる、請求項１４に記載のシステム。
【請求項１６】
前記アクセラレータは、前記ホストプロセッサへの転送前に、前記カーネルのドット積の精度を低下させる、請求項１１に記載のシステム。
【請求項１７】
前記アクセラレータは、前記少なくとも２つのプロセッサの各々に対応付けられているメモリバンクをさらに有し、前記ホストプロセッサへの転送前に、前記カーネルのドット積は複数のグループに分割されて前記カーネルのドット積の前記複数のグループの各々が前記複数のメモリバンクの１つに格納される、請求項１６に記載のシステム。
【請求項１８】
前記カーネルの複数のドット積は、前記アクセラレータの前記少なくとも２つのプロセッサを使用して、並列に求められる、請求項１１に記載のシステム。
【請求項１９】
前記カーネルの複数のドット積は、独立した別個の複数のチャンク内で求められる、請求項１１に記載のシステム。
【請求項２０】
前記アクセラレータは、前記少なくとも２つのプロセッサの各々に対応付けられているメモリバンクをさらに有し、前記ホストプロセッサへの転送前に、前記カーネルのドット積は複数のグループに分割されて前記カーネルのドット積の前記複数のグループの各々は前記複数のメモリバンクの１つに格納される、請求項１１に記載のシステム。
【請求項２１】
パターンを認識する方法であって、
サポートベクターマシンの学習プロセスのステップを実行するホストプロセッサを準備するステップと、
少なくとも２つのプロセッサと前記少なくとも２つのプロセッサの各々に対応しているメモリバンクとを有するアクセラレータを準備するステップと、
複数のサポートベクトルを前記アクセラレータの前記メモリバンクに格納するステップと、
ラベル付けされていないパターンデータの精度を前記ホストプロセッサによって低下させるステップと、
ラベル付けされていないパターンデータを前記ホストプロセッサから前記アクセラレータに転送するステップと、
前記アクセラレータの前記メモリバンクに保存されている前記サポートベクトルを使用して、前記アクセラレータの前記少なくとも２つのプロセッサによって、前記ラベル付けされていないパターンデータに対するラベルを計算するステップと、
前記ラベル付けされたパターンデータを前記ホストプロセッサに転送して戻すステップと、
を有する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械学習(machine learing)に関し、特に、機械学習と分類とを並列化し高速化するシステムと方法とに関する。
【背景技術】
【０００２】
超並列(massively parallel)アーキテクチャは、「認識(recognition)」、「マイニング(mining)」及び「合成(syntehsis)」の将来的なアプリケーションに必要な性能に到達するために必要である。超並列アクセラレータは、合成のアプリケーションのために、最大２５６個の処理エレメントを有するグラフィックプロセッサの形態で存在している。しかし、認識とマイニングのアプリケーションについては、同等のものは利用できない。計算要求量において機械学習が支配的であって、意味のある高速化であれば何でも並列機械学習に集中的に使用しなければならないようなアプリケーション領域が存在する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
サポートベクターマシン（ＳＶＭ；support vector machine）は、認識とマイニングのクラスに分類されるアルゴリズムである。ＳＶＭにおける性能のボトルネックは、カーネル(kernel)計算であって、これは、極めて多数のベクトルの乗算（つまりベクトルのドット積の計算）を伴う。これは、極めて大きなメモリ帯域幅要件を有するため、マルチコアプロセッサ上での並列化が容易ではない。
【０００４】
そのため、機械学習と分類の並列化と高速化のためのシステムと方法が必要である。
【課題を解決するための手段】
【０００５】
本明細書では、パターンを認識するように装置を訓練する方法が開示されている。この方法は、機械学習プロセスの複数のステップを実行するホストプロセッサを装置に設けるステップと、少なくとも２つのプロセッサを有するアクセラレータを装置に設けるステップと、訓練パターンデータをホストプロセッサに入力するステップと、訓練データをアクセラレータに転送するステップと、訓練パターンデータを使用してホストプロセッサによる機械学習プロセスにおける係数変化を求めるステップと、１つまたは２つ以上の訓練ベクトルに関する指標をアクセラレータに転送するステップと、訓練データを使用してアクセラレータの少なくとも２つのプロセッサによってカーネルの複数のドット積を求めるステップと、ドット積をホストプロセッサに転送して戻すステップと、を有する。
【０００６】
本明細書ではパターンを認識するように装置を訓練するシステムも開示されている。システムは、入力された訓練データから、機械学習プロセスの複数の係数変化を求める、その装置のホストプロセッサと、訓練データを使用してカーネルの複数のドット積を求める少なくとも２つのプロセッサを有するアクセラレータと、訓練データをホストプロセッサからアクセラレータまで転送し、かつカーネルのドット積をアクセラレータからホストプロセッサまで転送する少なくとも１つの伝達路と、を有する。
本明細書では、パターンを認識する方法がさらに開示されている。この方法は、サポートベクターマシンの学習プロセスのステップを実行するホストプロセッサを準備するステップと、少なくとも２つのプロセッサとこれら少なくとも２つのプロセッサの各々に対応しているメモリバンクとを有するアクセラレータを準備するステップと、複数のサポートベクトルをアクセラレータの複数のメモリバンクに格納するステップと、ラベル付けされていないパターンデータの精度をホストプロセッサによって低下させるステップと、ラベル付けされていないパターンデータをホストプロセッサからアクセラレータに転送するステップと、アクセラレータの複数のメモリバンクに保存されているサポートベクトルを使用して、アクセラレータの少なくとも２つのプロセッサによって、ラベル付けされていないパターンデータに対するラベルを計算するステップと、ラベル付けされたパターンデータをホストプロセッサに転送して戻すステップと、を有する。
【図面の簡単な説明】
【０００７】
【図１】本開示に基づく例示的な実施形態のホスト／ＦＰＧＡコプロセッサシステムのブロック図である。
【図２】本開示の例示的な実施形態に基づき、ホスト／ＦＰＧＡコプロセッサのハードウェア、データ及び計算がどのように分割されているのかを示している図である。
【図３】ＦＰＧＡ／ホストベースのコプロセッサシステムを使用してＳＭＯ−ＳＶＭアルゴリズムを訓練する方法の例示的な実施形態のフローチャートである。
【図４Ａ】本開示に基づく、訓練データをチャンク化する方法の例示的な実施形態のフローチャートである。
【図４Ｂ】図４Ｂの方法の模式図である。
【図５】本開示に基づくパッキング方法の例示的な実施形態の模式図である。
【図６】ホスト／ＦＰＧＡコプロセッサのアクセラレータでの低下した精度を使用してＳＶＭ分類（またはテスト）を実施する方法の例示的な実施形態のフローチャートである。
【発明を実施するための形態】
【０００８】
本明細書では、サポートベクターマシン（ＳＶＭ）と他の機械学習方法／アルゴリズムの訓練と動作を高速化するホスト／コプロセッサシステムと方法が開示されている。ＳＶＭは、自動音声認識、自動文字認識、自動画像認識、及び文章の自動意味分類などの機械パターン認識にしばしば使用される。ＳＶＭは、認識されたシーンや意味の分析などの、しかしこれらには限定されない、機械推論タスクにも使用される。ＳＶＭ訓練と分類との両方を高速化するシステム及び方法のいくつかの実施形態において、逐次最小最適化（ＳＭＯ；sequential minimal optimization）の方法／アルゴリズムを使用することができる。
【０００９】
コプロセッサベースのアクセラレータは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ；field-programmable gate array）、プログラマブルロジックデバイス（ＰＬＤ；programmble logic device）、または特定用途向け集積回路（ＡＳＩＣ；application-specific integrated circuit）を有していてもよい。例示的な一実施形態では、システムのコプロセッサベースのアクセラレータは、超並列ＦＰＧＡを有している（超(massively)という用語は、通常、少なくとも１６個の相互接続された処理ノードを指し、例示的な一実施形態においては、ＦＰＧＡは、分散メモリによって支援される１２８個の相互接続された処理ノードを有している）。ＦＰＧＡは、アプリケーションの大量のデータ並列性を利用する単一命令複数データ（ＳＩＭＤ；single-instruction multiple data）モードで動作する、つまり異なる処理ノードが異なるデータに対して同じ命令（プログラム）を実行する、複数のベクトル処理エレメント（ＶＰＥ；vector processing element）の複数のクラスタを有している。ＶＰＥは、ＦＰＧＡのマッピングされているデジタル信号プロセッサ（ＤＳＰ；digital signal processor）である。ＦＰＧＡのＤＳＰは、積和演算器、つまりＳＭＯ高速化ＳＶＭのコア計算に特化している機能ユニットとして使用される。ホスト／コプロセッサは、コプロセッサの動作によってハードウェア並列性を選択的に増加させるように、所望のレベルの低下した算術演算精度（例えば、低下したカーネル算術演算精度）を実装するように適合されている。低精度によって、機能ユニットごとに複数の演算が可能になり、また、複数のデータワードをコプロセッサのメモリバス上でパッキングすることによって、チップ外(off-chip)メモリへの並列ロード及びストア数も増加する。このシステム及び方法は、ＳＶＭ認識の正確さの所望のレベルに見合っている、低減された算術演算精度のレベルの選択を可能にする。
【００１０】
ＳＶＭ及び他の機械学習方法／アルゴリズムは、低精度を許容する密な計算(dense computation)によって特徴付けられる部分を有している。本開示において、この特徴は、計算をホストコンピュータとアクセラレータとの間で分割して、密な、精度に対する許容度の高い計算をコプロセッサのアクセラレータに移し、残りの計算をホストコンピュータに移すために使用される。
【００１１】
図１は、本開示による、精度低下に基づく分割及び並列化の方法を実行するホスト／ＦＰＧＡコプロセッサシステム１００の例示的な実施形態のブロック図である。システム１００は、概して、機械学習方法を実行するホストコンピュータ１０１とフィールドプログラマブルゲートアレイ（ＦＰＧＡ）アクセラレータ１０４とを有している。第１の伝達路(conduit)が、機械学習の訓練データ、サポートベクトル、及び／又はテストベクトルをアクセラレータ１０４に転送するために、ホストコンピュータ１０１とアクセラレータ１０４との間に設けられている。例示的な一実施形態においては、第１の伝達路１０２は、従来の周辺機器インターフェイス（ＰＣＩ；peripheral component interface）または同様のコンピュータバスであってもよい。第２の伝達路１０３は、アクセラレータ１０４からホストコンピュータ１０２に結果を転送するために、ホストコンピュータ１０２とアクセラレータ１０４との間に設けられていてもよい。結果には、ＳＶＭカーネルのドット積が含まれるが、これには限定されない。例示的な一実施形態においては、第２の伝達路１０３は、従来のＰＣＩまたは同様のコンピュータバスであってもよい。他の例示的な実施形態においては、機械学習の訓練データ、サポートベクトル、テストベクトル及び結果は、多重化されて、単一の伝達路（不図示）を通して転送されてもよい。
【００１２】
システム１００のホストコンピュータ１０１は、１つまたは２つ以上のメモリ媒体からの命令を実行する１つまたは２つ以上の制御処理装置（ＣＰＵ；control processing unit）を有するメインフレームコンピュータシステム、ワークステーション、パーソナルコンピュータ、携帯情報端末（ＰＤＡ；personal digital assistant）、分散コンピュータシステム、または他の装置あるいは機器を有することができるが、これらには限定されない。ホストコンピュータ１０１は、図１に示す例示的な実施形態において、中央処理ユニットつまりプロセッサ２０１と、本明細書に記載したＳＭＯ及びＳＶＭ方法を実施するために実行可能な１つまたは２つ以上のコンピュータプログラムあるいはソフトウェアコンポーネントを格納することができるメモリ媒体２０２と、を有している。メモリ媒体には、これらに限定されるものではないが、ＣＤ−ＲＯＭ、フレキシブルディスク、テープ装置、ランダムアクセスメモリ、不揮発性メモリ、及びこれらの組み合わせなどを含むことができる。ここでランダムアクセスメモリは、これらに限定されるものではないが、ＤＲＡＭ、ＳＲＡＭ、ＥＤＯ  ＲＡＭ及びＲａｍｂｕｓ  ＲＡＭなどのランダムアクセスメモリであり、不揮発性メモリは、これらに限定されるものではないが、ハードドライブ、光学ストレージ装置などの不揮発性メモリである。システム１００のアクセラレータ１０４は、従来の通信インターフェイス１０５（例えば直接メモリアクセス（ＤＭＡ；direct memory access）インターフェイスなど）、ＦＰＧＡ１０６、及びバンク構成されたメモリ１０７を有していてもよい。
【００１３】
ここで図２を参照すると、ＦＰＧＡ１０６は、バンク構成されたメモリ１０７によって定められている複数のメモリバンク２０４ａ〜２０４ｃと通信する複数の仮想処理エレメント（ＶＰＥ）２０３ａ〜２０３ｃのアレイを有していてもよい。メモリバンク２０４ａ〜２０４ｃは、低アクセスレイテンシを実現するように、ＶＰＥ２０３ａ〜２０３ｃの近くに設けられている。広帯域幅（たとえば秒（ｓ）あたり３〜５ギガバイト（ＧＢ））の通信経路１０８がＦＰＧＡ１０６とバンク構成されたメモリ１０７との間に設けられている。例示的な一実施形態において、通信経路１０８は、約１５ＧＢ／ｓの帯域幅を有している。
【００１４】
本開示の方法は、ＳＭＯ−ＳＶＭアルゴリズム（計算及びデータ）をシステム１００のホストコンピュータ１０１とアクセラレータ１０４との間で分割する。より具体的には、ホストコンピュータ１０１のＣＰＵ２０１は、ＳＭＯ−ＳＶＭアルゴリズムのある部分（精度に対する許容度が低い部分）を実行し、ＦＰＧＡ１０６のＶＰＥ１０３は、カーネルの複数のドット積、つまりＳＭＯ−ＳＶＭアルゴリズムでの密な、かつ精度に対する許容度の高い部分を計算する。訓練データとサポートベクトルは、インターフェイス１０５によって、基板上のメモリ１０７内に配置され、カーネルドット積は、繰り返しごとに、ホストコンピュータ１０１に戻される。
【００１５】
図２は、本開示の例示的な実施形態に基づく、ハードウェア、データ及び計算の分割をも示している。ハードウェアレベルでは、ホストコンピュータのＣＰＵ２０１とメモリ２０２とは、アクセラレータ１０４の複数のＶＰＥ２０３ａ〜２０３ｃ及びそれらＶＰＥに対応するメモリバンク２０４ａ〜２０４ｃから分離されている。データレベルでは、ＳＭＯ−ＳＶＭアルゴリズムのアルファ（α）及び勾配(gradient)２０５がホストコンピュータ上に存在するのに対し、訓練データ及びサポートベクトル２０６はアクセラレータ１０４上に存在する。計算レベルでは、ホストコンピュータは、ＳＭＯ−ＳＶＭアルゴリズムでの、アルファの更新と勾配の更新と作業セットの選択（次の作業セット）２０７とを計算し、アクセラレータ１０４は、ＳＭＯ−ＳＶＭアルゴリズムの複数のカーネルドット積２０８を計算する。
【００１６】
アクセラレータは、多数のドット積を計算することのボトルネックに対処する。各ドット積計算は、訓練／テストベクトルの精度を低下させた後、アクセラレータに向けてアンロードされる。アクセラレータによって生成された結果は、さらにその精度が低下させられて、コンピュータにアップロードされて戻される。精度を低くすることは、通常はチップ外メモリと処理エレメントとの間に存在する限定された帯域幅をより有効に利用できるようにするから、精度を低くすることによって、ドット積計算の並列演算可能性が増加する。Ｎ個の訓練ベクトルが与えられるとして、ＳＭＯ−ＳＶＭアルゴリズムの目標は、それ以降において任意のベクトルの分類に使用することができる、はるかに少ない数のサポートベクトルを求めることである。
【００１７】
図３は、ＦＰＧＡ／ホストベースのコプロセッサシステムを使用してＳＭＯ−ＳＶＭアルゴリズムを訓練する方法の例示的な実施形態のフローチャートである。この方法においてフローチャートのボックス３０１〜３１２及びボックス３０６〜３０９は、以下では「ホスト」と呼ぶホストコンピュータのプロセッサ上で実行される、ＳＭＯ−ＳＶＭアルゴリズムでの従来のステップを示している。ボックス３０５〜３１２は、ホスト上で実行されるアクセラレータに関する本方法のステップを示している。ボックス３１３〜３１６は、コプロセッサのアクセラレータ上で実行される本方法のステップである。本方法は、ＳＭＯ−ＳＶＭアルゴリズムの初期化を伴って、ホスト上のボックス３０１で始まる。それから、繰り返しのループごとに、ボックス３０２において、作業セットの２つの訓練ベクトルｉ，ｊが選択され、ボックス３０３において、アルゴリズムのアルファαｉ，αｊでの変化がホスト上で計算され、ボックス３０４において、訓練ベクトルの数が特定される。訓練ベクトルは、ホストに入力されたラベル付けされている訓練パターンデータ（例えば、音声データ、テキストデータ、画像データ及び意味文章データ(semantic textual data)）から得られる。ボックス３０５において、アクセラレータを使用するかどうかを決定する。この決定は、装置のユーザによって行われてもよいし、自動的に行われてもよい。例示的な一実施形態では、ボックス３０５の判断は、システム性能を監視するハードウェアプローブを使用して自動的に行うことができる。性能が特定のしきい値未満になると、アクセラレータが起動される。アクセラレータを使用しないという判断であれば、この方法は、ボックス３０６〜３０９へ移動する。すなわち、ボックス３０６において、全ての訓練ベクトルについてドット積ｘｉ，ｘｊがホスト上で計算され、ボックス３０７において、全てのｋ（指標；インデックス）についてホスト上でカーネルＫ(ｘｉ，ｘｋ)，Ｋ(ｘｊ，ｘｋ)が計算され、ボックス３０８において、各ｘｋに対して勾配Ｇｉｋ，Ｇｊｋが計算され、それから、ボックス３０９において、ホスト上において収束したかどうかが判断される。ボックス３０９での判定が「収束した」というものである場合、ホストは、誤分類エラーを最小にする（複数のサポートベクトルが決定される）クラス割り当てに収束し、それによってＳＶＭの訓練を完了する。ボックス３０９での判定が「収束していない」というものである場合、もう１回の繰り返しループを実行するために、この方法はボックス３０２に戻る。ボックス３０９での判断は、ＳＭＯ−ＳＶＭアルゴリズムの公知のＫＫＴ収束判断基準を使用して実施される。
【００１８】
ボックス３０５の判断が、アクセラレータを使用するという判断であれば、ホストによって訓練ベクトルの算術演算精度が低下させられ、低下したつまり低精度の訓練ベクトルと訓練ベクトルの指標ｉ，ｊ，ｌｏ及びｈｉ（ホストデータ）とが、ホストからアクセラレータに伝送路によって転送される（複数の訓練ベクトルがアクセラレータにいったん転送されると精度がさらに低下させられることはなく、また、このステップのさらなる繰り返しでは、訓練ベクトルの指標だけがアクセラレータに転送される）。例示的な一実施形態では、精度は、適切な数の最下位ビット（ＬＳＢ；least significant bit）を破棄することによって低下させられる。例えば、この例に限定されるものではないが、１６ビットの固定小数点の数は、４ビットで表すことが可能で、したがってＬＳＢつまり１２ビットを破棄する。ボックス３１３では、アクセラレータはホストデータを受信し、ボックス３１４では、アクセラレータがＳＭＯ−ＳＶＭドット積ｘｉ．ｘｋ，ｘｊ．ｘｋ（低精度訓練データに基づいているカーネルＫ(ｘｉ，ｘｋ)，Ｋ(ｘｊ，ｘｋ)の一部）を計算する。符号３１４の乗算によって、必要以上に高い分解能つまり精度を有している結果が得られる。例えば、この例に限定されるものではないが、８ビット×８ビットのドット積計算によって、１６ビットの分解能を有している結果が得られ、これは必要以上に高い分解能である可能性がある。そこでボックス３１５では、アクセラレータは、ボックス３１４で計算されたドット積ｘｉ．ｘｋ，ｘｊ．ｘｋの算術演算精度を低下させ、それらをアクセラレータの１つまたは２つ以上のメモリバンク２０４ａ〜２０４ｃ（図２）に格納する。例示的な一実施形態では、ドット積の精度の低下は、ｉ，ｊの各々についてｈｉ−ｌｏドット積を別個に計算すること（つまり、ドット積[ｉ] [ｋ]＝ｘ[ｉ]・ｘ[ｋ]およびドット積[ｊ] [ｋ]＝ｘ[ｊ]・ｘ[ｋ]）と適切な数の最下位ビット（ＬＳＢ）の破棄とによって実現される。例えば、この例に限定されるものではないが、１６ビットの固定小数点の数を有している結果は、４ビットで表すことが可能で、したがってＬＳＢつまり１２ビットを破棄するが、これには限定されない。ｈｉが１００万でｌｏが０の場合、２００万個のドット積が繰り返しごとに計算される。精度の低下の目標は、１）通信ボトルネックを減少させ、２）並列性を増加させることである。訓練データの精度を低下させることによって、アクセラレータ上で、より多くの機能ユニットが並列に動作することができるようになる。これは、単位時間ごとに、より多くの低精度ワードをメモリ（例えばメモリ２０４）からプロセッサ（例えばプロセッサ２０３）まで転送することができるからである。ドット積の精度を低下させることによって、アクセラレータ−ホスト間の伝達路をより有効に使用することができる。ボックス３１６では、アクセラレータは、アクセラレータの１つまたは２つ以上のメモリバンクから、精度が低下したＳＶＭ−ＳＭＯカーネルのドット積ｘｉ．ｘｊ，ｘｊ．ｘｋを検索して、それらを前述の伝達路または第２の伝達路を通してホストに転送して戻す。  ボックス３１１では、ホスト上に設けられているポーリング機構が、ＳＭＯ−ＳＶＭアルゴ���ズムの精度が低下しているカーネルドット積の計算をアクセラレータが完了しているかどうかを確認する。ポーリング機構は、デバイスドライバ（不図示）によってアクセラレータにマッピングされているホストのメモリ内の位置を監視することによって、この機能を実施することができる。具体的には、デバイスドライバとホストのオペレーティングシステムは、仮想メモリの何らかの部分をアクセラレータにマッピングする。そして、メモリのその部分に書き込まれたものはすべて、オペレーティングシステムによって、ハードウェアに関連していると解釈され、具体的な動作のためにデバイスドライバに中継されることになる。
【００１９】
ボックス３１２では、ホストは、低下した精度のＳＶＭ−ＳＭＯカーネルのドット積ｘｉ．ｘｊ，ｘｊ．ｘｋをアクセラレータの１つまたは２つ以上のメモリバンクから伝達路を通して受信する。低下した精度のＳＶＭ−ＳＭＯカーネルのドット積ｘｉ．ｘｊ，ｘｊ．ｘｋは、ダイレクトメモリアクセスによって、ホストのメモリ内に配置される。その後、本方法は、前述のようにボックス３０７〜３０９で継続する。具体的には、ボックス３０７において、精度の低下したカーネルドット積ｘｉ．ｘｊ，ｘｊ．ｘｋは、すべてのｋについてカーネルＫ(ｘｉ，ｘｊ)，Ｋ(ｘｊ，ｘｋ)の計算を完了するために、ホストによって使用される。ボックス３０８では、カーネルＫ(ｘｉ，ｘｊ)，Ｋ(ｘｊ，ｘｋ)は、ホストによって、各ｘｋについて勾配Ｇｉｋ，Ｇｊｋを計算するために使用される。ボックス３０９では、ホスト上において収束したかどうかが判断される。ボックス３０９における判断が「収束した」というものである場合、ホストは、前述のように、誤分類エラーを最小にする（複数のサポートベクトルが決定される）クラス割り当てに収束し、それによってＳＶＭの訓練を完了する。ボックス３０９での判定が「収束していない」というものである場合、もう１回の繰り返しループのために、この方法はボックス３０２に戻る。
【００２０】
図４Ａと図４Ｂを併せて参照すると、これらは、ホスト／コプロセッサシステムを使用してＳＭＯ−ＳＶＭを訓練する本方法の性能をさらに向上させるために使用可能な、チャンク化する(chunking)方法の例示的な実施形態を示している図である。このチャンク化する方法は、そのステップがアクセラレータからの支援を伴ってホストによって指定され実装されるものであって、ホストとアクセラレータとが並列化できるように、計算をより小さな独立している複数の部分に分割する。具体的には、ボックス４０１と４０３に示されるように、ホストによって指定されたデータの「チャンク(chunk)」に対してアクセラレータがドット積をいったん計算すると、ボックス４０４と４０７に示されるように、アクセラレータは、データのチャンクについてのドット積をホストに転送し、ホストは、ボックス４０５と４０８に示されるように、データのチャンクについてドット積を受信して、ボックス４０６と４０９に示されるように、カーネルＫの残りの部分を計算しなければならない。そのため、ボックス４０２に示されるように、ホストプロセスは、チャンクを使用しているアクセラレータプロセスと重畳することができる。図４Ｂに示される結果の列は、図４Ａのボックス４０３に示されるように、アクセラレータがチャンクを処理している間に、ボックス４０４において以前のチャンクがホストに転送され、ボックス４０５においてホストによって受信されるように、複数の「チャンク」に分割されている。これは、ホスト−アクセラレータの通信レイテンシに加え、チャンクについてのホストが実行するあらゆる処理を効果的に隠蔽している。
【００２１】
図５は、アクセラレータの１つまたは２つ以上のメモリバンク内に低精度ＳＶＭ訓練ベクトル及びサポートベクトルをパックする(packing)方法の例示的な実施形態を示しているブロック図である。パックする方法はホストによって実装され、チップ外メモリの限定された帯域幅を利用できるようにしている。ブロック５０１は、（図２に示される複数のＶＰＥ２０３ａ〜２０３ｃのうちの１つである）ベクトルプロセッサアレイ１のための、（図２に示される複数のメモリバンク２０４ａ〜２０４ｃのうちの１つである）チップ外メモリバンク１である。ブロック５０２は、（図２に示される複数のＶＰＥ２０３ａ〜２０３ｃのうちの他の１つである）ベクトルプロセッサアレイＭのための、（図２に示される複数のメモリバンク２０４ａ〜２０４ｃのうちの他の１つである）チップ外メモリバンクＭである。バンク５０３は、チップ外メモリバンク（図１のバンク構成されたメモリ１０７）とベクトルプロセッサクラスタ（図１のＦＰＧＡ１０６）との間の伝達路（図１の通信経路１０８）である。この幅はＮ×ｐビットであって、ここでＮはベクトルプロセッサアレイの大きさであり、ｐはビットで表した分解能（精度）である。ブロック５０４はベクトルプロセッサアレイ１である。ブロック５０５はベクトルプロセッサアレイＭである。ブロック５０６は、Ｎ個の訓練ベクトルまたはサポートベクトルの配列であって、各々が次元Ｄと精度ｐである。メモリ内の各行は、メモリフェッチの大きさを表している。最初のＮ個のベクトルは、この部分に位置している。ブロック５０７は、メモリバンク１内の次のＮ個のベクトル（ベクトルＭＮ＋１からベクトル(Ｍ＋１)Ｎ）の集合である。ブロック５０８は、メモリバンクＭ内のＮ個のベクトル（ベクトル(Ｍ−１)Ｎ＋１からベクトルＭＮ）の集合である。ブロック５０９は、メモリバンクＭ内のＮ個のベクトル（ベクトル(２Ｍ−１)Ｎ＋１からベクトル２ＭＮ）の集合である。
【００２２】
図６は、コプロセッサのアクセラレータ上で、低下した精度を使用してＳＶＭ分類（またはテスト）を実施する方法の例示的な実施形態のフローチャートである。サポートベクトルが図３の訓練方法によっていったん求められると、サポートベクトルを使用して、未知の、つまりラベル付けされていないクラスを有している「テストベクトル」を分類する、つまりラベル付けすることができる。この例に限定されるものではないが、例えば手書き数字の、ラベル付けされているパターンのデータベース用のサポートベクトルがいったん求められると、訓練データベース内にはない新規のラベル付けされていないパターン（例えば、ラベル付けされていない手書きの数字）用のテストベクトルを図６の方法を使用して求めることができる。
【００２３】
本方法は、ボックス６０１で開始され、そこでは訓練から得られた複数のサポートベクトルがアクセラレータのメモリ内にパックされる。ボックス６０２において、Ｔ個のテストベクトルがホストにおいて生成される。ボックス６０３において、ホストは、アクセラレータのハードウェア処理エレメントの精度に適合するように、Ｔ個のテストベクトルの精度を低下させる。精度を低下させたＴ個のテストベクトルは、ボックス６０４において、アクセラレータのバンク構成されたメモリ１０７（図１）に転送される。ボックス６０５において、ホストのポーリング機構が、アクセラレータがＴ個のテストベクトルの分類つまりラベル付けを完了したかどうかを確認する。アクセラレータが分類を完了していなければ、Ｔ個のテストベクトルに対応するＴ個の結果がホストに転送して戻されることはない。アクセラレータが分類を完了していれば、次にボックス６０６において、アクセラレータは、Ｔ個のテストベクトルに対応するＴ個の結果をホストに転送して戻す。ボックス６０７において、ホストは、全てのテストベクトルが分類されているかどうかを確認する。Ｔ個の全てのテストベクトルの分類が完了していない場合、本方法はループしてボックス６０２〜６０７のもう１回の繰り返しに戻る。Ｔ個の全てのテストベクトルが分類されている場合、ホストプロセッサは、分類の結果を任意の適切な形態によってユーザに対して通知する。例えば、この例に限られるものではないが、ホストプロセッサは、分類結果をシステムの表示モニタ（不図示）上にグラフィック表示させてもよい。
【００２４】
本発明に基づくシステムと方法とを例示的な実施形態に関して説明したが、本発明に基づくシステムと方法とはそれらには限定されない。むしろ、添付の特許請求の範囲は、当業者が発明に基づくシステムと方法との等価物の範囲から逸脱することなく構成可能な、本発明に基づくシステムと方法とのその他の変形例と実施形態とを含むように、広く解釈されるべきである。
【００２５】
［関連出願」
本出願は、２００８年６月４日に出願された米国仮出願第６１／０５８，８８７号と２００９年１月２２日に出願された米国仮出願第６１／１４６，４９８号とに基づく利益を主張し、これらの仮出願の開示の全体が参照によって本明細書に組み込まれる。
【図１】
2011524049.tif 000003
【図２】
2011524049.tif 000004
【図３】
2011524049.tif 000005
【図４Ａ】
2011524049.tif 000006
【図４Ｂ】
2011524049.tif 000007
【図５】
2011524049.tif 000008
【図６】
2011524049.tif 000009
【国際調査報告】
2011524049.tif 000010
2011524049.tif 000011