分散型マルコフ連鎖モンテカルロ
分散型マルコフ連鎖モンテカルロのための実施態様および技法の概要が開示されている。
【発明の詳細な説明】
【背景技術】
【０００１】
本明細書で特に指示しない限り、本項で説明する手法は、本出願における特許請求の範囲の先行技術ではなく、本項に含まれることにより先行技術であると認められるものではない。
【０００２】
マルコフ連鎖モンテカルロ法は、工学、物理学、天文学、生物学、金融、暗号法、統計学、社会科学、医学他を含む多くの分野において利用され得る。マルコフ連鎖モンテ・カルロ・アプリケーションは、多くの場合、相当量の処理能力を利用する可能性がある。その結果、マルコフ連鎖モンテ・カルロ・アプリケーションを、高性能コンピューティングシステム上で走らせることになり得る。
【発明の概要】
【課題を解決するための手段】
【０００３】
いくつかの方法、装置、およびシステムの例は、分散型マルコフ連鎖モンテカルロに関連したものである。そのような方法は、交換提案コアによる、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するステップを含み得る。交換提案のうちの１つまたは複数が第１の連鎖コアにより交換提案コアから受け取られ得る。複数の乱数が第１の連鎖コアによって生成され得る。分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復が、少なくとも一部は複数の乱数に基づいて、第１の連鎖コアによって処理され得る。第１の連鎖コアは、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。乱数の生成は、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでのそのような待機の間に、途切れることなく第１の連鎖コアによって続行され得る。
【０００４】
いくつかの例は複数のプロセッサコアを含むマルチコアプロセッサを含んでいてよく、マルチコアプロセッサは交換提案コアと第１の連鎖コアとを含む。交換提案コアは、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成され得る。第１の連鎖コアは、交換提案コアから交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は複数の乱数に基づいて分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成され得る。第２の連鎖コアは、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復を処理するように構成され得る。第１の連鎖コアは、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの待機の間に、途切れることなく乱数の生成を続行するようにさらに構成され得る。
【０００５】
いくつかの例は複数のプロセッサコアを含むコンピューティング機器を含んでいてよく、コンピューティング機器は、マルチコアプロセッサと、メモリバスと、メモリバスを介してマルチコアプロセッサと通信するように構成されたシステムメモリとを含み得る。マルチコアプロセッサは、交換提案コアと第１の連鎖コアとを含み得る。交換提案コアは、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成され得る。第１の連鎖コアは、交換提案コアから交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は複数の乱数に基づいて分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成され得る。第２の連鎖コアは、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復を処理するように構成され得る。第１の連鎖コアは、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの待機の間に、途切れることなく乱数の生成を続行するようにさらに構成され得る。
【０００６】
以上の概要は例示にすぎず、いかなる点においても限定が意図されるものではない。図面および以下の詳細な説明を参照すれば、前述の例示的態様、実施形態、および特徴に加えて、さらに別の態様、実施形態、および特徴も明らかになるであろう。
【０００７】
主題は、本明細書の結論部分において詳細に指し示し、明確に特許請求する。本開示の上記その他の特徴は、以下の説明および添付の特許請求の範囲を、添付の図面と併せて読めばより十分に明らかになるであろう。これらの図面は本開示によるいくつかの実施形態を示すものにすぎず、したがって、本開示の範囲を限定するものとみなすべきでないことを踏まえ、添付の図面を使用して、本開示をさらに具体的に詳細に説明する。
【図面の簡単な説明】
【０００８】
【図１】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサを含むコンピューティング機器の例を示す図である。
【図２】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサの動作についてのプロセス例を示す図である。
【図３】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサの動作についてのプロセス例を示す図である。
【図４】コンピュータプログラム製品の例を示す図である。
【図５】すべて本開示の少なくともいくつかの実施形態に従って構成されたコンピューティング機器の例を示すブロック図である。
【発明を実施するための形態】
【０００９】
以下の説明は、特許請求される主題の十分な理解を提供するために、様々な例を具体的詳細と共に示すものである。しかし、特許請求される主題は本明細書で開示する具体的詳細のうちの一部または多くがなくても実施され得ることが当業者には理解されるであろう。さらに、状況によっては、特許請求される主題を不必要に不明瞭にすることのないように、周知の方法、手順、システム、構成要素および／または回路が詳細に説明されない場合もある。以下の詳細な説明では、本出願の一部を形成する添付の図面を参照する。図面において、類似の記号は、文脈上別の意味に解すべき場合を除き、通常は類似の構成要素を識別する。詳細な説明、図面、および特許請求の範囲に記載される例示的実施形態限定のためのものではない。本出願で提示する主題の趣旨または範囲を逸脱することなく、別の実施形態が利用されてもよく、別の変更が加えられてもよい。本明細書で概説し、図に例示する本開示の態様は、多種多様な構成として配置し、置換し、結合し、設計することができ、そのすべてが明示的に企図されており、本開示の一部を構成するものである。
【００１０】
本開示は、とりわけ、分散型マルコフ連鎖モンテカルロ法を実施することに関連した方法、装置、およびシステムを対象とするものである。
【００１１】
以下でより詳細に説明するように、マルチコアプロセッサのための分散型マルコフ連鎖モンテカルロ法の改善された実施態様が提供され得る。本明細書で使用する場合、「分散型マルコフ連鎖モンテカルロ」という用語は、複数の並列実行スレッドをサポートする任意の数のマルコフ連鎖モンテカルロ法を指し得る。例えば、分散型マルコフ連鎖モンテカルロ法には、メトロポリス結合型（Ｍｅｔｒｏｐｏｌｉｓ−ｃｏｕｐｌｅｄ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法、投機的動き型（ｓｐｅｃｕｌａｔｉｖｅ−ｍｏｖｅ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法（例えば、「Ｊ．Ｍ．Ｒ．Ｂｙｒｄ，Ｓ．Ｊａｒｖｉｓ，Ａ．Ｂｈａｌｅｒａｏ“Ｒｅｄｕｃｉｎｇ ｔｈｅ ｒｕｎｔｉｍｅ ｏｆ ＭＣＭＣ ｐｒｏｇｒａｍｓ ｂｙ ｍｕｌｔｉｔｈｒｅａｄｉｎｇ ｏｎ ＳＭＰ ａｒｃｈｉｔｅｃｔｕｒｅｓ，”ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ ２００８ ＩＰＤＰＳ ２００８，Ａｐｒｉｌ ２００８」で論じられているものなど）、先取り型（ｐｒｅ−ｆｅｔｃｈｉｎｇ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法（例えば、「Ａ．Ｂｒｏｃｋｗｅｌｌ“Ｐａｒａｌｌｅｌ Ｍａｒｋｏｖ ｃｈａｉｎ Ｍｏｎｔｅ Ｃａｒｌｏ ｓｉｍｕｌａｔｉｏｎ ｂｙ ｐｒｅ−ｆｅｔｃｈｉｎｇ，”Ｊ．Ｃｏｍｐ．Ｇｒａｐｈ．Ｓｔａｔｓ，ｖｏｌ．１５，ｎｏ．１，２００６」で論じられているものなど）などが含まれ得る。
【００１２】
分散型マルコフ連鎖モンテカルロ法は複数の計算連鎖を走らせることができる。様々な連鎖が周期的に他の連鎖と状態を交換することを考慮し得る。連鎖のうちの少なくとも１つは「コールド」チェーンとすることができ、コールドチェーンは目標分布を提供し得る。状態の交換を使用することにより複雑な探索空間をカバーし得る見込みが向上する可能性がある。連鎖は、状態交換が同じ反復の連鎖間で行われるようにするためのある同期を想定して、並列に走らせてもよい。本開示において対処される１つの課題は、この同期によって維持が助長され得る分散型マルコフ連鎖モンテカルロ法のセマンティクスを維持しながら可能な限り多くの利用可能なコアを使用することである。
【００１３】
以下でより詳細に説明するように、方法、装置、およびシステムは、様々な連鎖が同時に同期させる必要が生じないように動作し得る。ある例では、専用の「交換」コアが、２つのスレッド、すなわち、交換提案生成スレッドと交換提案分配スレッドとをホストし得る。そのような交換提案コアは、交換提案を生成し、そのような交換提案情報を目標とする連鎖へ分配するように構成され得る。したがって、各連鎖がほとんど独立に走ることができ、その場合、特定の連鎖は、所与の反復においてそのための交換が提案されるときに停止され得る。
【００１４】
さらに、いくつかのマルコフ連鎖モンテカルロ法では、少なくとも２つの、場合によってはすべてのコアが、単一の交換が行われるべきであるかどうか判定するための情報を待ち、または状態データ自体の交換が終了するのを待つ間、遊休状態にあり、連鎖計算を停止し得る。以下でより詳細に説明するように、方法、装置、およびシステムは、待機中の連鎖を有するコアでさえも遊休状態に入らなくてもよいように動作し得る。代わりに、連鎖が待機している間、当該連鎖のコアは、後で使用するためのランダムビット生成に使用され得る。ある例では、個々の「連鎖」コアが、２つのスレッド、すなわち、乱数生成スレッドと連鎖スレッドとをホストし得る。乱数生成スレッドと連鎖スレッドとは切り離されているため、連鎖コアは乱数生成スレッドを処理し続けてよく、連鎖スレッドの動作を待つ必要がない。同様に、交換提案生成スレッドと交換提案分配スレッドも切り離されているため、交換提案コアは交換提案生成スレッドを処理し続けてよく、交換提案分配スレッドの動作を待つ必要がない。
【００１５】
図１は、本開示の少なくともいくつかの実施形態に従って構成されたマルチコアプロセッサ１００を含むコンピューティング機器の例を示す図である。マルチコアプロセッサ１００は、分散型マルコフ連鎖モンテカルロ法を実施するように構成され得る。図示の例において、マルチコアプロセッサ１００は、処理コア配列を有する単一の集積回路を含み得る。別の例では、マルチコアプロセッサ１００は、別個の集積チップ上にプロセッサコアを含み得る。マルチコアプロセッサ１００に加えて、またはその代わりに、分散コンピューティング環境システム（不図示）を利用して、マルチコアプロセッサ１００に関して本明細書で説明する機能の全部または一部が実施されてもよい。例えば、そのような分散コンピューティング環境システム（不図示）は、（例えば、デスクトップコンピュータ、ラップトップコンピュータ、ワークステーション、サーバ機器、記憶装置などといった）複数のコンピューティング機器を含んでいてよく、それらのコンピューティング機器はネットワークを介して相互に動作可能に結合され得る。
【００１６】
マルチコアプロセッサ１００は、ある数（Ｎ）の処理コア１０４（１）〜１０４（Ｎ）を含み得る。任意の適切な数の処理コア１０４が設けられ得る。例えば、マルチコアプロセッサ１００は、４個の処理コア１０４を有していてもよく、数十個の処理コア１０４を有していてもよく、数百個以上の処理コア１０４でさえも有していてよい。あるマルチコアプロセッサ１００はホモジニアスとすることができ、各処理コア１０４が単一の種類のコア設計を使用する。別のマルチコアプロセッサ１００はヘテロジニアスとすることができ、処理コア１０４のうちの１つまたは複数が他の処理コア１０４のうちの１つまたは複数と異なり、個々の処理コア１０４または処理コア１０４の一部がマルチコアプロセッサ１００における異なる役割のために設計され得る。
【００１７】
処理コア１０４は、（１つまたは複数の）非共用Ｌ１キャッシュおよび（１つまたは複数の）共用または非共用のＬ２キャッシュ、ならびに共用システムメモリを含み得る。個々の処理コア１０４は１つまたは複数のハードウェアスレッドをサポートし得る。処理コア１０４は、マルコフ連鎖モンテカルロ法の処理専用に利用されない場合もある。
【００１８】
図１は、マルチコアプロセッサの例示的概略図であり、図１に示される構成要素の物理的位置を例示するものではない。本明細書で説明するマルチコアプロセッサ１００は例示であり、具体例および改変も可能であることが理解される。設計選択は、例えば、ハードウェアサイズおよび複雑さ対性能、熱エネルギーと熱放散、プロセッサ速度、総スループットなどの考慮事項によって決定され得る。
【００１９】
図示の例では、マルチコアプロセッサ１００は、相互に通信し合うように構成された交換提案コア１０６と複数の連鎖コア１０８、１１０、１１２とを含む複数のプロセッサコア１０４を含み得る。任意の適切な数の連鎖コア１０８、１１０、１１２が設けられ得る。
【００２０】
ある例では、交換提案コア１０６は２つのスレッド、すなわち、交換提案生成スレッド１１４と交換提案分配スレッド１１６とをホストし得る。そのような交換提案コア１０６は、交換提案を生成し、そのような交換提案情報を連鎖コア１０８、１１０、１１２と関連付けられた目標とする連鎖へ分配するように構成され得る。交換提案生成スレッド１１４と交換提案分配スレッド１１６とは切り離されているため、交換提案コア１０６は交換提案生成スレッド１１４を処理し続けてよく、交換提案分配スレッド１１６の動作を待つ必要がない。
【００２１】
本明細書で使用する場合、「交換提案」という用語は、分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分、および分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報を指し得る。例えば、交換提案スレッド１１４は、（１つまたは複数の）ある指定された間隔で２つの連鎖間の交換提案を生成し得る。この交換提案データは、第１の連鎖ｊの状態が第２の連鎖ｋの状態と間隔ｉで交換され得ることを指定する交換提案の３つ組の列｛＜ｉ，ｊ，ｋ＞１，…｝として表すことができる。
【００２２】
そのような交換提案データ列を生成するために、交換提案コア１０６はランダムビットを生成し得る。例えば、交換提案生成スレッド１１４は、（連鎖間の）状態交換を決定する際に使用するためのランダムビット生成を行い得る。ランダムビット生成には、ハードウェアのランダムビット生成器と擬似ランダムのソフトウェアによるビット生成器のどちらも使用することができる。
【００２３】
ある例では、個々の連鎖コア１０８、１１０、１１２が、それぞれ、２つのスレッド、すなわち乱数生成スレッド１１８と連鎖スレッド１２０とをホストし得る。乱数生成スレッド１１８と連鎖スレッド１２０とを含むプロセスは、（例えばプロセッサ親和性や類似の指示などによって）その指定の連鎖コア１０８、１１０、１１２にピン留めされ得る。そのようなピン留めは、連鎖スレッド１２０が空間を探索する際のキャッシュ局所性の保持を助長し得る。
【００２４】
乱数生成スレッド１１８と連鎖スレッド１２０とは切り離されているため、連鎖コア１０８は、乱数生成スレッド１１８を処理し続けてよく、連鎖スレッド１２０の動作を待つ必要がない。乱数生成スレッド１１８は、（連鎖内）状態遷移を判定する際に使用するためのランダムビット生成を行い得る。ランダムビット生成には、ハードウェアのランダムビット生成器と擬似ランダムのソフトウェアによるビット生成器のどちらも使用することができる。
【００２５】
交換提案コア１０６は、交換提案生成待ち行列１２２を含み得る。交換提案生成待ち行列１２２は、交換提案生成スレッド１１４によって生成された交換提案のうちの１つまたは複数を記憶するように構成され得る。交換提案生成待ち行列１２２は、コア特有のバッファなどとして実装され得る。交換提案コア１０６は、交換提案分配スレッド１１６を介して交換提案生成待ち行列１２２から連鎖コア１０８、１１０、１１２へ交換提案のうちの１つまたは複数を分配するように構成され得る。
【００２６】
結果として得られる交換提案はそれらが作成された後でいつでも使用することができるため、交換提案コア１０６は、いつでも交換提案の生成を開始し、連続して、またはほぼ連続して交換提案生成待ち行列１２２に取り込み続けてよい。また交換提案コア１０６は、分配スレッド１１６も、連鎖スレッド１２０をホストする連鎖コア１０８、１１０、１１２へ交換提案を分配するように処理し得る。例えば、連鎖スレッド１２０からの要求に応じて、分配スレッド１１６が、当該連鎖スレッド１２０へ１つまたは複数の交換提案を分配し得る。分配スレッド１１６は、交換提案生成待ち行列１２２からの交換提案のデキューアとして動作し得る。
【００２７】
第１の連鎖コア１０８は交換提案分配待ち行列１２４を含み得る。交換提案分配待ち行列１２４は、第１の連鎖コア１０８によって受け取られた交換提案のうちの１つまたは複数を記憶するように構成され得る。交換提案分配待ち行列１２４は、コア特有のバッファなどとして実装され得る。個々の連鎖コア１０８と関連付けられた個々の連鎖スレッド１２０が、交換提案コア１０６から、少なくとも最も近い交換提案（例えば、現在の反復に関して最も近い交換提案など）を獲得し得る。例えば、連鎖スレッド１２０と関連付けられた交換提案分配待ち行列１２４は、第１の連鎖コア１０８と関連付けられた交換提案の待ち行列を有し得る。他の連鎖コア１１０、１１２と関連付けられた連鎖スレッドは、それぞれの交換提案分配待ち行列を一杯に保つ役割を果たし得る。例えば、第２の交換提案分配待ち行列１２６は第２の連鎖コア１１０と関連付けられ得る。第２の交換提案分配待ち行列１２６は、第２の連鎖コア１２６によって受け取られた交換提案のうちの１つまたは複数を記憶するように構成され得る。
【００２８】
第１の連鎖コア１０８はランダムビット待ち行列１２８を含み得る。ランダムビット待ち行列１２８は、乱数生成スレッド１１８によって生成された乱数のうちの１つまたは複数を記憶するように構成され得る。ランダムビット待ち行列１２８は、コア特有のバッファなどとして実装され得る。同様に、第２のランダムビット待ち行列１３０も第２の連鎖コア１１０と関連付けられ得る。ランダムビット待ち行列１３０は、第２の連鎖コア１１０と関連付けられた乱数生成スレッドによって生成された乱数のうちの１つまたは複数を記憶するように構成され得る。
【００２９】
乱数は、それらが生成された後でいつでも使用され得るため、乱数生成スレッド１１８は、任意のスケジュールで自由に走り、任意のスケジュールでランダムビット待ち行列１２８を満たしてよい。そのため、個々の連鎖コア１０８は、通常、関連付けられたランダムビット待ち行列１２８にアクセスし、関連付けられた連鎖スレッド１２０は、当該ランダムビット待ち行列１２８から乱数を除去し得る。
【００３０】
動作に際して、連鎖スレッド１２０が次の提案の交換の反復に到達する前には、関連付けられた連鎖コア１０８は連鎖スレッド１２０（および乱数生成スレッド１１８）を自由に処理し得る。連鎖コア１０８が指定の反復（例えば、受け取った交換提案と関連付けられた反復など）に到達した後で、連鎖スレッド１２０は、交換が行われるべきかどうか、および必要な場合には、状態を交換すべきかどうか判定するのに十分な情報を共有するために、提案された交換連鎖スレッド（例えば、第２の連鎖コア１１０と関連付けられた連鎖スレッドなど）を待機し得る。可能性のある交換に関する通信は、ポイントツーポイント通信（例えば連鎖スレッド対連鎖スレッドなど）とすることができる。乱数生成スレッド１１８によって生成され、ランダムビット待ち行列１２８に記憶された乱数は、交換が行われるべきかどうかの判定の間に消費され得る。ある例では、連鎖スレッド１２０は、可能性のある交換について提案されている別の連鎖スレッドを待機している間に１つまたは複数のさらに別の交換提案を要求し得る。その間、連鎖コア１０８は乱数生成スレッド１１８を処理し続けてよい。可能性のある交換を考慮している最中の連鎖コア（例えば第１の連鎖コア１０８や第２の連鎖コア１１０など）を除く、残りの連鎖コア（例えば連鎖コア１１２など）は、乱数生成スレッドも連鎖スレッドも自由に続行してよい。特定の交換提案の評価の間、または評価の後で、可能性のある交換を考慮している最中の連鎖コア（例えば第１の連鎖コア１０８や第２の連鎖コア１１０など）は、（例えば、それぞれの交換提案分配待ち行列１２４、１２６が空である場合などには）交換提案コア１０６から次の交換提案を受け取り得る。交換が完了した後で、連鎖コア１０８、１１０は、関連付けられた連鎖スレッド１２０の処理を再開し得る。上記のように仕事とポイントツーポイント同期とを分割すれば、高度な連鎖コア利用が、比較的少ないコア間通信で達成され得る。
【００３１】
図２は、本開示の少なくともいくつかの実施形態に従って構成された、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作についてのプロセス例２００を示す図である。図示の例において、プロセス２００、および本明細書で説明する他のプロセスは、ハードウェア、ソフトウェア、および／またはファームウェアのうちの１つまたは複数によって実施され得る、処理ステップ、機能動作、イベントおよび／または作用などとして説明され得る様々な機能ブロックまたは措置を示す。当業者は、本開示を考慮すれば、図２に示す機能ブロックの多くの代替が様々な実施態様において実施され得ることを理解するであろう。例えば、プロセス２００は、図２に示すように、特定の順序のブロックまたは措置を含むが、これらのブロックまたは措置が提示される順序は、必ずしも特許請求される主題を任意の特定の順序に限定するものであるとは限らない。同様に、特許請求される主題の範囲を逸脱することなく、図２に示されていない介在措置および／または図２に示されていないさらに別の措置が用いられてもよく、かつ／または図２に示す措置のうちのいくつかが除去されてもよい。プロセス２００は、動作２０２、動作２０４、動作２０６、動作２０８、および／または動作２１０のうちの１つまたは複数を含み得る。
【００３２】
図示のように、プロセス２００は、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作について実施され得る。処理は動作２０２、「交換提案を生成する」から開始することができ、そこで、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案が交換提案コア１０６（図１参照）によって生成され得る。例えば、交換提案コア１０６（図１参照）と関連付けられた交換提案スレッド１１４（図１参照）がそのような交換提案を生成し得る。
【００３３】
処理は動作２０２から動作２０４「交換提案を受け取る」へ進むことができ、そこで、交換提案のうちの１つまたは複数が、連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって、交換提案コア１０６（図１参照）から受け取られ得る。例えば、交換提案は、連鎖コア１０８、１１０、１１２のうちの１つまたは複数によって受け取られるように、交換提案生成待ち行列１２２（図１参照）から分配され得る。
【００３４】
動作２０６は、動作２０２〜動作２０４の後、その間、および／またはその前に行われ得る。動作２０６「乱数を生成する」では、乱数が連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって生成され得る。例えば、連鎖コア１０８（図１参照）と関連付けられた乱数生成スレッド１１８（図１参照）がそのような乱数を生成し得る。
【００３５】
処理は動作２０６から動作２０８「連鎖を処理する」へ進むことができ、そこで、分散型マルコフ連鎖モンテカルロ法の連鎖部分の現在の反復が、連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって処理され得る。そのような連鎖部分は、少なくとも一部は動作２０６で生成された乱数に基づいて処理され得る。例えば、連鎖コア１０８（図１参照）と関連付けられた連鎖スレッド１２０（図１参照）がそのような連鎖部分を処理し得る。
【００３６】
処理は動作２０８から動作２１０「待機する」へ進むことができ、そこで、連鎖スレッド１２０（図１参照）が、第２の連鎖コア（例えば図１の連鎖コア１１０など）と関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。そのような待機は、少なくとも一部は交換提案のうちの１つまたは複数に基づくものとすることができる。例えば、所与の交換提案は、分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報と、状態情報の交換のために提案される連鎖部分の特定の対（例えば連鎖コア１０８と関連付けられた連鎖部分および連鎖コア１１０と関連付けられた連鎖部分など）（図１参照）に関連した情報とを含み得る。
【００３７】
動作に際して、プロセス２００は、動作２２８での連鎖コア１０８の待機の間、途切れることなく、連鎖コア１０８によって乱数を生成し続けてよい。同様にプロセス２００は、動作２２８での連鎖コア１０８の待機の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。加えてプロセス２００は、動作２０４での交換提案分配スレッド１１６の分配の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。さらにプロセス２００は、分散型マルコフ連鎖モンテカルロ法の統計的性能も維持し得る。例えば、プロセス２００を利用しない結果と比較すると、プロセス２００を使用することにより分散型マルコフ連鎖モンテカルロ法の結果に対して統計的調整を行わなくて済む可能性もある。
【００３８】
図３は、本開示の少なくともいくつかの実施形態に従って構成された、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作についてのプロセス例３００を示す図である。図示の例において、プロセス３００、および本明細書で説明する他のプロセスは、ハードウェア、ソフトウェア、および／またはファームウェアのうちの１つまたは複数によって実施され得る、処理ステップ、機能動作、イベントおよび／または作用などとして説明され得る様々な機能ブロックまたは措置を示す。当業者は、本開示を考慮すれば、図３に示す機能ブロックの多くの代替が様々な実施態様において実施され得ることを理解するであろう。例えば、プロセス３００は、図３に示すように、特定の順序のブロックまたは措置を含むが、これらのブロックまたは措置が提示される順序は、必ずしも特許請求される主題を任意の特定の順序に限定するものであるとは限らない。同様に、特許請求される主題の範囲を逸脱することなく、図３に示されていない介在措置および／または図３に示されていないさらに別の措置が用いられてもよく、かつ／または図３に示す措置のうちのいくつかが除去されてもよい。プロセス３００は、動作３０２、動作３０４、動作３０６、動作３０８、動作３１０、動作３１２、動作３１４、動作３１６、動作３２２、動作３２４、動作３２６、動作３２８、動作３３０、動作３３２、動作３３４、動作３３６、動作３３８、動作３４０および／または動作３４２のうちの１つまたは複数を含み得る。
【００３９】
図示のように、プロセス３００は、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作について実施され得る。処理は動作３０２「交換提案を生成し、かつ／または記憶する」から開始することができ、そこで、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案が交換提案コア１０６によって生成され得る。例えば、交換提案コア１０６と関連付けられた交換提案スレッド１１４がそのような交換提案を生成し得る。加えて、そのような交換提案が記憶され得る。例えばそのような交換提案は、交換提案生成待ち行列１２２（図１参照）に記憶され得る。
【００４０】
処理は動作３０２から動作３０４「交換提案を分配する」へ進むことができ、そこで、交換提案のうちの１つまたは複数が、交換提案コア１０６によって、連鎖コア１０８、連鎖コア１１０、および／または連鎖コア１１２のうちの１つまたは複数へ分配され得る。例えば交換提案は、交換提案生成待ち行列１２２（図１参照）から分配され得る。
【００４１】
処理は動作３０４から動作３０６「交換提案を記憶する」へ進むことができ、そこで、そのような分配された交換提案が連鎖コア１０８によって受け取られ、おそらくは、後で使用するために記憶され得る。例えばそのような分配された交換提案は、交換提案分配待ち行列１２４（図１参照）によって記憶され得る。ある例では、同様の動作３０８と動作３１０とが、それぞれ、連鎖コア１１０と連鎖コア１１２とによって行われ得る。
【００４２】
動作３１２〜動作３１６は、動作３０２〜動作３０６の後、その間、および／またはその前に行われ得る。動作３１２「乱数を生成し、かつ／または記憶する」で、乱数が連鎖コア１０８によって生成され、後で使用するためにランダムビット待ち行列１２８（図１参照）によって記憶され得る。例えば、連鎖コア１０８と関連付けられた乱数生成スレッド１１８がそのような乱数を生成し、かつ／または記憶し得る。ある例では、同様の動作３１４と動作３１６とが、それぞれ、乱数生成スレッド３１８と乱数生成スレッド３１９とによって行われ得る。
【００４３】
処理は動作３０６から動作３２２「連鎖を処理する」へ進むことができ、そこで、分散型マルコフ連鎖モンテカルロ法の連鎖部分の現在の反復が連鎖コア１０８によって処理され得る。そのような連鎖部分は、少なくとも一部は、ランダムビット待ち行列１２８（図１参照）に記憶された乱数に基づいて処理され得る。例えば、連鎖コア１０８と関連付けられた連鎖スレッド１２０がそのような連鎖部分を処理し得る。ある例では、同様の動作３２４と動作３２６とが、それぞれ、連鎖スレッド３２０と連鎖スレッド３２１とによって行われ得る。
【００４４】
処理は動作３２２から動作３２８「待機する」へ進むことができ、そこで、連鎖スレッド１２０が、第２の連鎖コア（例えば連鎖コア１１０など）と関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。そのような待機は少なくとも一部は交換提案のうちの１つまたは複数に基づくものとすることができる。例えば、所与の交換提案は、分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報と、状態情報の交換のために提案される連鎖部分の特定の対（例えば連鎖コア１０８と関連付けられた連鎖部分および連鎖コア１１０と関連付けられた連鎖部分など）に関連した情報とを含み得る。
【００４５】
処理は動作３２８から動作３３０「情報を交換する」へ進むことができ、そこで、連鎖スレッド１２０は、交換が行われるべきかどうか判定するのに十分な情報を別の連鎖スレッド（例えば連鎖スレッド３２０）と交換し得る。
【００４６】
動作３３２〜動作３３６は、動作３２８〜動作３３０の後、その間、および／またはその前に行われ得る。動作３３２「交換提案を要求する」で、連鎖スレッド１２０は１つまたは複数のさらに別の交換提案を要求し得る。例えば、連鎖スレッド１２０は、可能性のある交換について提案されている別の連鎖スレッド（例えば連鎖スレッド３２０など）を待機している間に１つまたは複数のさらに別の交換提案を要求し得る。ある例では、同様の動作３３４が連鎖スレッド３２０によって行われ得る。処理は動作３３２または動作３３４から動作３３６「交換提案を分配する」へ進むことができ、そこで、１つまたは複数のさらに別の交換提案が、交換提案コア１０６によって、要求に応じて、連鎖コア１０８、連鎖コア１１０、および／または連鎖コア１１２のうちの１つまたは複数へ分配され得る。例えば、交換提案は、交換提案生成待ち行列１２２（図１参照）から分配され、連鎖コア１０８によって受け取られ、おそらくは、後で使用するために交換提案分配待ち行列１２４（図１参照）に記憶され得る。
【００４７】
処理は動作３３０から動作３３８「状態を交換することに決定する」へ進むことができ、そこで、状態を交換する、または交換しないという決定が行われ得る。例えば、第１の連鎖コア１０８および／または第２の連鎖コア１１０は、少なくとも一部は交換提案分配待ち行列１２４（図１参照）に記憶された交換提案のうちの１つまたは複数に基づく提案された交換に従い得る。連鎖コア（例えば第１の連鎖コア１０８および／または第２の連鎖コア１１０）のうちの１つが、提案された交換に従い、少なくとも一部は動作３３０の交換情報に基づいて交換を行うことに決定し得る。
【００４８】
処理は動作３３８から動作３４０「連鎖を処理する」へ進むことができ、そこで、第１の連鎖部分の後続の反復が連鎖コア１０８によって処理され得る。例えば、状態が交換されている場合には、第１の連鎖部分の後続の反復が、少なくとも一部は第２の連鎖からの交換された状態と、ランダムビット待ち行列１２８（図１参照）に記憶された乱数とに基づいて処理され得る。例えば、連鎖コア１０８と関連付けられた連鎖スレッド１２０は、少なくとも一部は、第２の連鎖コア１１０と関連付けられた第２の連鎖スレッド３２０からの交換された状態に基づいてそのような連鎖部分を処理し得る。ある例では、同様の動作３４２が連鎖スレッド３２０によって行われ得る。
【００４９】
動作に際して、プロセス３００は、動作３２８における連鎖コア１０８の待機の間、途切れることなく、連鎖コア１０８によって乱数を生成し続けてよい。同様にプロセス３００は、動作３２８における連鎖コア１０８の待機の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。加えてプロセス３００は、動作３０４および動作３３６における交換提案分配スレッド１１６の分配の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。さらにプロセス３００は、分散型マルコフ連鎖モンテカルロ法の統計的性能も維持し得る。例えば、プロセス３００を利用しない結果と比較すると、プロセス３００を使用することにより分散型マルコフ連鎖モンテカルロ法の結果に対して統計的調整を行わなくて済む可能性もある。
【００５０】
図４に、本開示の少なくともいくつかの実施形態に従って構成されたコンピュータプログラム製品の例４００を示す。コンピュータプログラム製品４００は、信号担持媒体４０２を含み得る。信号担持媒体４０２は、１つまたは複数のプロセッサによって実行されるときに、コンピューティング機器が、図１、図２および／または図３を参照して前述した機能を提供することを動作的に可能にし得るマルチコアプロセッサの複数のコリジョン・ドメイン・ネットワーク間の通信を円滑化するための１つまたは複数の機械可読命令４０４を含み得る。よって、例えば図１のシステムを参照すると、マルチコアプロセッサ１００は、媒体４０２によって伝えられる命令４０４に応答して、図２および／または図３に示す措置のうちの１つまたは複数に着手し得る。
【００５１】
ある実施態様では、信号担持媒体４０２は、それだけに限らないが、ハード・ディスク・ドライブ、コンパクトディスク（ＣＤ）、ディジタル多用途ディスク（ＤＶＤ）、ディジタルテープ、メモリなどといったコンピュータ可読媒体４０６を包含し得る。ある実施態様では、信号担持媒体４０２は、それだけに限らないが、メモリ、読取り／書込み（Ｒ／Ｗ）ＣＤ、Ｒ／Ｗ ＤＶＤなどといった書込み可能媒体４０８を包含し得る。ある実施態様では、信号担持媒体４０２は、それだけに限らないが、ディジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）といった通信媒体４１０を包含し得る。
【００５２】
図５は、本開示の少なくともいくつかの実施形態に従って構成された、コンピューティング機器の例５００を示すブロック図である。基本構成の一例５０１では、コンピューティング機器５００は、１つまたは複数のプロセッサ５１０とシステムメモリ５２０とを含み得る。プロセッサ５１０とシステムメモリ５２０との間の通信にはメモリバス５３０を使用することができる。
【００５３】
所望の構成に応じて、プロセッサ５１０は、それだけに限らないが、マイクロプロセッサ（μΡ）、マイクロコントローラ（μＣ）、ディジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせを含む任意の種類のものとすることができる。プロセッサ５１０は、レベル１キャッシュ５１１やレベル２キャッシュ５１２といった１つまたは複数のレベルのキャッシュ、プロセッサコア５１３、およびレジスタ５１４を含むことができる。プロセッサコア５１３は、算術論理演算装置（ＡＬＵ）、浮動小数点演算装置（ＦＰＵ）、ディジタル信号処理コア（ＤＳＰコア）、またはそれらの任意の組み合わせを含むことができる。またメモリコントローラ５１５をプロセッサ５１０と一緒に使用することもでき、ある実施態様では、メモリコントローラ５１５をプロセッサ５１０の内蔵部品とすることができる。
【００５４】
所望の構成に応じて、システムメモリ５２０は、それだけに限らないが、揮発性メモリ（ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、フラッシュメモリなど）、またはそれらの任意の組み合わせを含む任意の種類のものとすることができる。システムメモリ５２０は、オペレーティングシステム５２１、１つまたは複数のアプリケーション５２２、およびプログラムデータ５２４を含み得る。アプリケーション５２２は、図２のプロセス２００および／または図３のプロセス３００に関して説明した機能ブロックおよび／または動作を含む本明細書で説明した機能および／または動作を実施するように構成することができるコア使用維持アルゴリズム５２３を含み得る。プログラムデータ５２４は、コア使用維持アルゴリズム５２３と共に使用するための交換提案データ５２５を含み得る。ある例示的実施形態では、アプリケーション５２２は、コア使用維持の実施態様が本明細書で説明したように提供され得るようにオペレーティングシステム５２１上でプログラムデータ５２４と共に動作するように構成され得る。この説明した構成は、図５において、破線５０１内の構成要素によって示されている。
【００５５】
コンピューティング機器５００は、さらに別の機構または機能と、基本構成５０１と任意の必要な機器およびインターフェースとの間の通信を円滑化するためのさらに別のインターフェースとを有していてもよい。例えば、バス／インターフェースコントローラ５４０が、記憶インターフェースバス５４１を介した基本構成５０１と１つまたは複数のデータ記憶装置５５０との間の通信を円滑化するのに使用されてもよい。データ記憶装置５５０は、取り外し可能記憶装置５５１、取り外し不能記憶装置５５２、またはそれらの組み合わせとすることができる。取り外し可能記憶装置および取り外し不能記憶装置の例には、いくつか例をあげると、フレキシブル・ディスク・ドライブやハード・ディスク・ドライブ（ＨＤＤ）といった磁気ディスク装置、コンパクトディスク（ＣＤ）ドライブやディジタル多用途ディスク（ＤＶＤ）ドライブといった光ディスクドライブ、ソリッド・ステート・ドライブ（ＳＳＤ）、およびテープドライブが含まれる。コンピュータ記憶媒体の例には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータといった情報の記憶のための任意の方法または技術で実施された揮発性および不揮発性、取り外し可能および取り外し不能の媒体が含まれ得る。
【００５６】
システムメモリ５２０、取り外し可能記憶５５１および取り外し不能記憶５５２はすべてコンピュータ記憶媒体の例である。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶他の磁気記憶装置、または所望の情報を記憶するのに使用され、コンピューティング機器５００によってアクセスされ得る他の任意の媒体が含まれる。任意のそのようなコンピュータ記憶媒体を機器５００の一部とすることができる。
【００５７】
またコンピューティング機器５００は、様々なインターフェース機器（例えば、出力インターフェース、周辺インターフェース、通信インターフェースなど）からの、バス／インターフェースコントローラ５４０を介した基本構成５０１への通信を円滑化するためのインターフェースバス５４２も含み得る。出力インターフェース５６０の例にはグラフィックス・プロセッシング・ユニット５６１やオーディオ・プロセッシング・ユニット５６２が含まれ、これらは、１つまたは複数のＡ／Ｖポート５６３を介してディスプレイやスピーカといった様々な外部機器へ通信するように構成され得る。周辺インターフェース５７０の例には、シリアル・インターフェース・コントローラ５７１やパラレル・インターフェース・コントローラ５７２が含まれ、これらは、１つまたは複数のＩ／Ｏポート５７３を介して入力装置（例えば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置など）や、他の周辺機器（例えば、プリンタ、スキャナなど）といった外部機器と通信するように構成され得る。通信インターフェース５８０の例にはネットワークコントローラ５８１が含まれ、ネットワークコントローラ５８１は、１つまたは複数の通信ポート５８２を介した、ネットワーク通信上での１台または複数の他のコンピューティング機器５９０との通信を円滑化するように構成され得る。通信接続は通信媒体の一例である。通信媒体は、典型的には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータにより、搬送波や他の搬送機構といった変調データ信号において実現することができ、任意の情報配信媒体を含み得る。「変調データ信号」とは、その特性のうちの１つまたは複数が信号において情報を符号化するように設定または変更されている信号とすることができる。例をあげると、それだけに限らないが、通信媒体には、有線ネットワーク、直接配線接続といった有線媒体や、音響、無線周波数（ＲＦ）、赤外線（ＩＲ）、他の無線媒体といった無線媒体が含まれ得る。コンピュータ可読媒体という用語は、本明細書で使用する場合、記憶媒体と通信媒体の両方を含み得る。
【００５８】
コンピューティング機器５００は、携帯電話、携帯情報端末（ＰＤＡ）、パーソナル・メディア・プレーヤ、無線ウェブウォッチ機器、パーソナルヘッドセット機器、アプリケーション特有の機器、上記機能のいずれかを含むハイブリッド機器といったスモール・フォーム・ファクタの携帯用（またはモバイル）電子機器の一部として実施され得る。またコンピューティング機器５００は、ラップトップコンピュータ構成と非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとしても実施され得る。加えて、コンピューティング機器５００は、無線基地局または他の無線システムもしくは機器の一部としても実施され得る。
【００５９】
以上の詳細な説明のいくつかの部分は、コンピュータメモリといったコンピューティング・システム・メモリ内に記憶されたデータビットまたは２値ディジタル信号に対する動作のアルゴリズムまたは記号表現として提示されている。これらのアルゴリズム記述または表現は、データ処理技術において当業者により、その作業の内容を他の当業者に伝えるために使用される技法の例である。アルゴリズムは、この場合、また一般に、所望の結果に至る筋道の通った動作シーケンスまたは類似の処理であるとみなされる。このコンテキストにおいて、動作または処理は、物理量の物理的操作を伴う。必ずしもそうとは限らないが、典型的には、そのような量は、記憶され、転送され、結合され、比較され、または別の方法で操作されることの可能な電子信号または磁気信号の形をとり得る。場合によっては、主に一般に使用されているために、そのような信号を、ビット、データ、値、要素、記号、文字、項、番号、数値などと呼ぶのが好都合である。しかし、これらおよび類似の用語はすべて適切な物理量と関連付けられるべきであり、単なる便利な表示にすぎないことを理解すべきである。特に指示しない限り、以下の考察から明らかなように、本明細書全体を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「判定する（ｄｅｔｅｒｍｉｎｉｎｇ）」などといった用語を使用した考察は、コンピューティング機器のメモリ、レジスタ、もしくは他の情報記憶装置、伝送機器、または表示装置内の物理的な電子的量または磁気的量として表されるデータを操作し、または変換するコンピューティング機器の措置またはプロセスを指すことが理解される。
【００６０】
以上の詳細な説明では、ブロック図、流れ図、および／または例を使用して、機器および／またはプロセスの様々な実施形態を示した。そのようなブロック図、流れ図、および／または例が１つまたは複数の機能および／または動作を含む限りにおいて、そのようなブロック図、流れ図、または例に含まれる各機能および／または動作は、広範なハードウェア、ソフトウェア、ファームウェア、または事実上それらの任意の組み合わせによって、個別に、かつ／または一括して実施することができることが当業者には理解されるであろう。ある実施形態では、本明細書で説明する主題のいくつかの部分は、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、ディジタル信号プロセッサ（ＤＳＰ）、または他の集積形式によって実施され得る。しかし、本明細書で開示する実施形態のある態様は、集積回路において、その全部または一部を、１台または複数のコンピュータ上で走る１つまたは複数のコンピュータプログラムとして（例えば、１つまたは複数のコンピュータシステム上で走る１つまたは複数のプログラムとして）も、１つまたは複数のプロセッサ上で走る１つまたは複数のプログラムとして（例えば１つまたは複数のマイクロプロセッサ上で走る１つまたは複数のプログラムとして）も、ファームウェアとしても、事実上それらの任意の組み合わせとしても同等に実施することができること、ならびにソフトウェアおよび／またはファームウェアのための回路の設計および／またはコードの作成は、本開示を踏まえれば十分に当業者の技能範囲内となるはずであることを当業者は理解するであろう。加えて当業者は、本明細書で説明する主題の機構を様々な形態のプログラム製品として配布することができること、および本明細書で説明する主題の一例示的実施形態は、実際に配布を実行するのに使用される信号担持媒体の特定の種類にかかわらず適用できることも理解するであろう。信号担持媒体の例には、それだけに限らないが、フレキシブルディスク、ハード・ディスク・ドライブ（ＨＤＤ）、コンパクトディスク（ＣＤ）、ディジタル多用途ディスク（ＤＶＤ）、ディジタルテープ、コンピュータメモリなどといった書込み可能型媒体、ならびに、ディジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）といった伝送型媒体が含まれる。
【００６１】
本明細書で説明する主題は、場合によっては、別の異なる構成要素内に含まれる、または別の異なる構成要素と接続された異なる構成要素を示すことがある。そのように描かれるアーキテクチャは単なる例にすぎず、実際は、同じ機能を果たす他の多くのアーキテクチャを実施することができることを理解すべきである。概念的には、同じ機能を果たすための構成要素の任意の配置は、事実上、所望の機能が果たされるように「関連付けられている」。したがって、特定の機能を果たすように組み合わされた本明細書の任意の２つの構成要素は、アーキテクチャや介在する構成要素にかかわらず、所望の機能が果たされるように相互に「関連付けられた」ものとみなすことができる。同様に、そのように関連付けられた任意の２つの構成要素も、所望の機能を果たすように相互に「動作可能に接続され」、または「動作可能に結合され」ているものとみなすことができ、そのように関連付けることができる任意の２つの構成要素も、所望の機能を果たすように相互に「動作可能に結合可能である」ものとみなすことができる。動作可能に結合可能であるものの具体例には、それだけに限らないが、物理的に結合可能であり、かつ／もしくは物理的に相互作用する構成要素、および／または無線で相互作用可能であり、かつ／もしくは無線で相互作用する構成要素、および／または論理的に相互作用し、かつ／もしくは論理的に相互作用可能な構成要素が含まれる。
【００６２】
本明細書における実質的にいかなる複数形および／または単形数の用語の使用についても、当業者は、状況および／または用途に合わせてしかるべく、複数形から単数形に、かつ／または単数形から複数形に変換することができる。本明細書においては明確にするために様々な単数形／複数形の置換形が明示される場合がある。
【００６３】
一般に、本明細書において、特に添付の特許請求の範囲（例えば添付の特許請求の範囲の本文など）において使用される用語は、一般には、「非限定的な（ｏｐｅｎ）」用語として意図されている（例えば、「ｉｎｃｌｕｄｉｎｇ（〜を含み）」という用語は「それだけに限らないが〜を含み」と解釈すべきであり、「ｈａｖｉｎｇ（〜を有し）」という用語は「少なくとも〜を有し」と解釈すべきであり、「ｉｎｃｌｕｄｅｓ（〜を含む）」という用語は、「それだけに限らないが、〜を含む」と解釈すべきであるなど）ことが当業者には理解されるであろう。さらに、導入請求項記載の特定の数が意図される場合、そのような意図は当該請求項において明示的に記載され、そのような記載がない場合にはそのような意図が存在しないことも当業者には理解されるであろう。例えば理解の一助としてあげると、添付の特許請求の範囲は、請求項記載を導入するために、「少なくとも１つの（ａｔ ｌｅａｓｔ ｏｎｅ）」および「１つまたは複数の（ｏｎｅ ｏｒ ｍｏｒｅ）」という導入句の使用を含み得る。しかし、そのような句の使用は、同じ請求項が「１つまたは複数の」あるいは「少なくとも１つの」という導入句および「ａ」や「ａｎ」といった不定冠詞を含むときでさえも、不定冠詞「ａ」または「ａｎ」による請求項記載の導入が、そのような導入請求項記載を含む任意の特定の請求項を、ただ１つのそのような記載を含む発明だけに限定することを意味するものと解釈されるべきではない（例えば、「ａ」および／または「ａｎ」は、通常は、「少なくとも１つの」または「１つまたは複数の」を意味するものと解釈されるべきであるなど）。同じことが、請求項記載を導入するのに使用される定冠詞の使用についても当てはまる。加えて、導入請求項記載の特定の数が明示的に記載されている場合でさえも、そのような記載が、通常は、少なくとも記載される数を意味するものと解釈されるべきであることも当業者は理解するであろう（例えば、他の修飾語句を伴わない「２つの記載」という記載だけで、通常は、少なくとも２つの記載、または２つ以上の記載を意味するなど）。さらに、「Ａ、Ｂ、およびＣのうちの少なくとも１つなど」に類似した慣用表現が使用される場合、一般にそのような構造は、当業者が当該慣用表現を理解するはずの意味として意図されるものである（例えば、「Ａ、Ｂ、およびＣのうちの少なくとも１つを有するシステム」は、それだけに限らないが、Ａだけを、Ｂだけを、Ｃだけを、ＡとＢとを共に、ＡとＣとを共に、ＢとＣとを共に、かつ／またはＡ、Ｂ、およびＣを共に有するシステムを含むはずであるなど）。「Ａ、Ｂ、またはＣのうちの少なくとも１つなど」に類似した慣用表現が使用される場合、一般にそのような構造は、当業者が当該慣用表現を理解するはずの意味として意図されるものである（例えば、「Ａ、Ｂ、またはＣのうちの少なくとも１つを有するシステム」は、それだけに限らないが、Ａだけを、Ｂだけを、Ｃだけを、ＡとＢとを共に、ＡとＣとを共に、ＢとＣとを共に、かつ／またはＡ、Ｂ、およびＣを共に有するシステムを含むはずであるなど）。さらに、２つ以上の択一的項目を提示する事実上あらゆる選言的な語および／または句は、本明細書においてであれ、特許請求の範囲においてであれ、図面においてであれ、それらの項目のうちの１つ、それらの項目のうちのどちらか、またはそれらの項目の両方を含む可能性を企図するものと理解すべきであることも当業者には理解されるであろう。例えば、「ＡまたはＢ」という句は、「Ａ」または「Ｂ」または「ＡおよびＢ」の可能性を含むものと理解されるであろう。
【００６４】
本明細書では、様々な方法およびシステムを使用するいくつかの技法例を説明し、図示したが、特許請求される主題から逸脱することなく、様々な改変が加えられ得ること、および均等物で置換され得ることが当業者には理解されるはずである。加えて、本明細書で説明した中心概念から逸脱することなく、個々の状況を特許請求される主題の教示に適合させるための多くの改変も加えられ得る。したがって、特許請求される主題は開示の特定の例だけに限定されず、そのような特許請求される主題は、添付の特許請求の範囲内に含まれるすべての実施態様、およびその均等物も含み得ることが意図されている。
【背景技術】
【０００１】
本明細書で特に指示しない限り、本項で説明する手法は、本出願における特許請求の範囲の先行技術ではなく、本項に含まれることにより先行技術であると認められるものではない。
【０００２】
マルコフ連鎖モンテカルロ法は、工学、物理学、天文学、生物学、金融、暗号法、統計学、社会科学、医学他を含む多くの分野において利用され得る。マルコフ連鎖モンテ・カルロ・アプリケーションは、多くの場合、相当量の処理能力を利用する可能性がある。その結果、マルコフ連鎖モンテ・カルロ・アプリケーションを、高性能コンピューティングシステム上で走らせることになり得る。
【発明の概要】
【課題を解決するための手段】
【０００３】
いくつかの方法、装置、およびシステムの例は、分散型マルコフ連鎖モンテカルロに関連したものである。そのような方法は、交換提案コアによる、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するステップを含み得る。交換提案のうちの１つまたは複数が第１の連鎖コアにより交換提案コアから受け取られ得る。複数の乱数が第１の連鎖コアによって生成され得る。分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復が、少なくとも一部は複数の乱数に基づいて、第１の連鎖コアによって処理され得る。第１の連鎖コアは、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。乱数の生成は、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでのそのような待機の間に、途切れることなく第１の連鎖コアによって続行され得る。
【０００４】
いくつかの例は複数のプロセッサコアを含むマルチコアプロセッサを含んでいてよく、マルチコアプロセッサは交換提案コアと第１の連鎖コアとを含む。交換提案コアは、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成され得る。第１の連鎖コアは、交換提案コアから交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は複数の乱数に基づいて分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成され得る。第２の連鎖コアは、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復を処理するように構成され得る。第１の連鎖コアは、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの待機の間に、途切れることなく乱数の生成を続行するようにさらに構成され得る。
【０００５】
いくつかの例は複数のプロセッサコアを含むコンピューティング機器を含んでいてよく、コンピューティング機器は、マルチコアプロセッサと、メモリバスと、メモリバスを介してマルチコアプロセッサと通信するように構成されたシステムメモリとを含み得る。マルチコアプロセッサは、交換提案コアと第１の連鎖コアとを含み得る。交換提案コアは、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成され得る。第１の連鎖コアは、交換提案コアから交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は複数の乱数に基づいて分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成され得る。第２の連鎖コアは、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復を処理するように構成され得る。第１の連鎖コアは、第２の連鎖コアが分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの待機の間に、途切れることなく乱数の生成を続行するようにさらに構成され得る。
【０００６】
以上の概要は例示にすぎず、いかなる点においても限定が意図されるものではない。図面および以下の詳細な説明を参照すれば、前述の例示的態様、実施形態、および特徴に加えて、さらに別の態様、実施形態、および特徴も明らかになるであろう。
【０００７】
主題は、本明細書の結論部分において詳細に指し示し、明確に特許請求する。本開示の上記その他の特徴は、以下の説明および添付の特許請求の範囲を、添付の図面と併せて読めばより十分に明らかになるであろう。これらの図面は本開示によるいくつかの実施形態を示すものにすぎず、したがって、本開示の範囲を限定するものとみなすべきでないことを踏まえ、添付の図面を使用して、本開示をさらに具体的に詳細に説明する。
【図面の簡単な説明】
【０００８】
【図１】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサを含むコンピューティング機器の例を示す図である。
【図２】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサの動作についてのプロセス例を示す図である。
【図３】分散型マルコフ連鎖モンテカルロ法を実施するように構成されたマルチコアプロセッサの動作についてのプロセス例を示す図である。
【図４】コンピュータプログラム製品の例を示す図である。
【図５】すべて本開示の少なくともいくつかの実施形態に従って構成されたコンピューティング機器の例を示すブロック図である。
【発明を実施するための形態】
【０００９】
以下の説明は、特許請求される主題の十分な理解を提供するために、様々な例を具体的詳細と共に示すものである。しかし、特許請求される主題は本明細書で開示する具体的詳細のうちの一部または多くがなくても実施され得ることが当業者には理解されるであろう。さらに、状況によっては、特許請求される主題を不必要に不明瞭にすることのないように、周知の方法、手順、システム、構成要素および／または回路が詳細に説明されない場合もある。以下の詳細な説明では、本出願の一部を形成する添付の図面を参照する。図面において、類似の記号は、文脈上別の意味に解すべき場合を除き、通常は類似の構成要素を識別する。詳細な説明、図面、および特許請求の範囲に記載される例示的実施形態限定のためのものではない。本出願で提示する主題の趣旨または範囲を逸脱することなく、別の実施形態が利用されてもよく、別の変更が加えられてもよい。本明細書で概説し、図に例示する本開示の態様は、多種多様な構成として配置し、置換し、結合し、設計することができ、そのすべてが明示的に企図されており、本開示の一部を構成するものである。
【００１０】
本開示は、とりわけ、分散型マルコフ連鎖モンテカルロ法を実施することに関連した方法、装置、およびシステムを対象とするものである。
【００１１】
以下でより詳細に説明するように、マルチコアプロセッサのための分散型マルコフ連鎖モンテカルロ法の改善された実施態様が提供され得る。本明細書で使用する場合、「分散型マルコフ連鎖モンテカルロ」という用語は、複数の並列実行スレッドをサポートする任意の数のマルコフ連鎖モンテカルロ法を指し得る。例えば、分散型マルコフ連鎖モンテカルロ法には、メトロポリス結合型（Ｍｅｔｒｏｐｏｌｉｓ−ｃｏｕｐｌｅｄ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法、投機的動き型（ｓｐｅｃｕｌａｔｉｖｅ−ｍｏｖｅ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法（例えば、「Ｊ．Ｍ．Ｒ．Ｂｙｒｄ，Ｓ．Ｊａｒｖｉｓ，Ａ．Ｂｈａｌｅｒａｏ“Ｒｅｄｕｃｉｎｇ ｔｈｅ ｒｕｎｔｉｍｅ ｏｆ ＭＣＭＣ ｐｒｏｇｒａｍｓ ｂｙ ｍｕｌｔｉｔｈｒｅａｄｉｎｇ ｏｎ ＳＭＰ ａｒｃｈｉｔｅｃｔｕｒｅｓ，”ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ ２００８ ＩＰＤＰＳ ２００８，Ａｐｒｉｌ ２００８」で論じられているものなど）、先取り型（ｐｒｅ−ｆｅｔｃｈｉｎｇ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法（例えば、「Ａ．Ｂｒｏｃｋｗｅｌｌ“Ｐａｒａｌｌｅｌ Ｍａｒｋｏｖ ｃｈａｉｎ Ｍｏｎｔｅ Ｃａｒｌｏ ｓｉｍｕｌａｔｉｏｎ ｂｙ ｐｒｅ−ｆｅｔｃｈｉｎｇ，”Ｊ．Ｃｏｍｐ．Ｇｒａｐｈ．Ｓｔａｔｓ，ｖｏｌ．１５，ｎｏ．１，２００６」で論じられているものなど）などが含まれ得る。
【００１２】
分散型マルコフ連鎖モンテカルロ法は複数の計算連鎖を走らせることができる。様々な連鎖が周期的に他の連鎖と状態を交換することを考慮し得る。連鎖のうちの少なくとも１つは「コールド」チェーンとすることができ、コールドチェーンは目標分布を提供し得る。状態の交換を使用することにより複雑な探索空間をカバーし得る見込みが向上する可能性がある。連鎖は、状態交換が同じ反復の連鎖間で行われるようにするためのある同期を想定して、並列に走らせてもよい。本開示において対処される１つの課題は、この同期によって維持が助長され得る分散型マルコフ連鎖モンテカルロ法のセマンティクスを維持しながら可能な限り多くの利用可能なコアを使用することである。
【００１３】
以下でより詳細に説明するように、方法、装置、およびシステムは、様々な連鎖が同時に同期させる必要が生じないように動作し得る。ある例では、専用の「交換」コアが、２つのスレッド、すなわち、交換提案生成スレッドと交換提案分配スレッドとをホストし得る。そのような交換提案コアは、交換提案を生成し、そのような交換提案情報を目標とする連鎖へ分配するように構成され得る。したがって、各連鎖がほとんど独立に走ることができ、その場合、特定の連鎖は、所与の反復においてそのための交換が提案されるときに停止され得る。
【００１４】
さらに、いくつかのマルコフ連鎖モンテカルロ法では、少なくとも２つの、場合によってはすべてのコアが、単一の交換が行われるべきであるかどうか判定するための情報を待ち、または状態データ自体の交換が終了するのを待つ間、遊休状態にあり、連鎖計算を停止し得る。以下でより詳細に説明するように、方法、装置、およびシステムは、待機中の連鎖を有するコアでさえも遊休状態に入らなくてもよいように動作し得る。代わりに、連鎖が待機している間、当該連鎖のコアは、後で使用するためのランダムビット生成に使用され得る。ある例では、個々の「連鎖」コアが、２つのスレッド、すなわち、乱数生成スレッドと連鎖スレッドとをホストし得る。乱数生成スレッドと連鎖スレッドとは切り離されているため、連鎖コアは乱数生成スレッドを処理し続けてよく、連鎖スレッドの動作を待つ必要がない。同様に、交換提案生成スレッドと交換提案分配スレッドも切り離されているため、交換提案コアは交換提案生成スレッドを処理し続けてよく、交換提案分配スレッドの動作を待つ必要がない。
【００１５】
図１は、本開示の少なくともいくつかの実施形態に従って構成されたマルチコアプロセッサ１００を含むコンピューティング機器の例を示す図である。マルチコアプロセッサ１００は、分散型マルコフ連鎖モンテカルロ法を実施するように構成され得る。図示の例において、マルチコアプロセッサ１００は、処理コア配列を有する単一の集積回路を含み得る。別の例では、マルチコアプロセッサ１００は、別個の集積チップ上にプロセッサコアを含み得る。マルチコアプロセッサ１００に加えて、またはその代わりに、分散コンピューティング環境システム（不図示）を利用して、マルチコアプロセッサ１００に関して本明細書で説明する機能の全部または一部が実施されてもよい。例えば、そのような分散コンピューティング環境システム（不図示）は、（例えば、デスクトップコンピュータ、ラップトップコンピュータ、ワークステーション、サーバ機器、記憶装置などといった）複数のコンピューティング機器を含んでいてよく、それらのコンピューティング機器はネットワークを介して相互に動作可能に結合され得る。
【００１６】
マルチコアプロセッサ１００は、ある数（Ｎ）の処理コア１０４（１）〜１０４（Ｎ）を含み得る。任意の適切な数の処理コア１０４が設けられ得る。例えば、マルチコアプロセッサ１００は、４個の処理コア１０４を有していてもよく、数十個の処理コア１０４を有していてもよく、数百個以上の処理コア１０４でさえも有していてよい。あるマルチコアプロセッサ１００はホモジニアスとすることができ、各処理コア１０４が単一の種類のコア設計を使用する。別のマルチコアプロセッサ１００はヘテロジニアスとすることができ、処理コア１０４のうちの１つまたは複数が他の処理コア１０４のうちの１つまたは複数と異なり、個々の処理コア１０４または処理コア１０４の一部がマルチコアプロセッサ１００における異なる役割のために設計され得る。
【００１７】
処理コア１０４は、（１つまたは複数の）非共用Ｌ１キャッシュおよび（１つまたは複数の）共用または非共用のＬ２キャッシュ、ならびに共用システムメモリを含み得る。個々の処理コア１０４は１つまたは複数のハードウェアスレッドをサポートし得る。処理コア１０４は、マルコフ連鎖モンテカルロ法の処理専用に利用されない場合もある。
【００１８】
図１は、マルチコアプロセッサの例示的概略図であり、図１に示される構成要素の物理的位置を例示するものではない。本明細書で説明するマルチコアプロセッサ１００は例示であり、具体例および改変も可能であることが理解される。設計選択は、例えば、ハードウェアサイズおよび複雑さ対性能、熱エネルギーと熱放散、プロセッサ速度、総スループットなどの考慮事項によって決定され得る。
【００１９】
図示の例では、マルチコアプロセッサ１００は、相互に通信し合うように構成された交換提案コア１０６と複数の連鎖コア１０８、１１０、１１２とを含む複数のプロセッサコア１０４を含み得る。任意の適切な数の連鎖コア１０８、１１０、１１２が設けられ得る。
【００２０】
ある例では、交換提案コア１０６は２つのスレッド、すなわち、交換提案生成スレッド１１４と交換提案分配スレッド１１６とをホストし得る。そのような交換提案コア１０６は、交換提案を生成し、そのような交換提案情報を連鎖コア１０８、１１０、１１２と関連付けられた目標とする連鎖へ分配するように構成され得る。交換提案生成スレッド１１４と交換提案分配スレッド１１６とは切り離されているため、交換提案コア１０６は交換提案生成スレッド１１４を処理し続けてよく、交換提案分配スレッド１１６の動作を待つ必要がない。
【００２１】
本明細書で使用する場合、「交換提案」という用語は、分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分、分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分、および分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報を指し得る。例えば、交換提案スレッド１１４は、（１つまたは複数の）ある指定された間隔で２つの連鎖間の交換提案を生成し得る。この交換提案データは、第１の連鎖ｊの状態が第２の連鎖ｋの状態と間隔ｉで交換され得ることを指定する交換提案の３つ組の列｛＜ｉ，ｊ，ｋ＞１，…｝として表すことができる。
【００２２】
そのような交換提案データ列を生成するために、交換提案コア１０６はランダムビットを生成し得る。例えば、交換提案生成スレッド１１４は、（連鎖間の）状態交換を決定する際に使用するためのランダムビット生成を行い得る。ランダムビット生成には、ハードウェアのランダムビット生成器と擬似ランダムのソフトウェアによるビット生成器のどちらも使用することができる。
【００２３】
ある例では、個々の連鎖コア１０８、１１０、１１２が、それぞれ、２つのスレッド、すなわち乱数生成スレッド１１８と連鎖スレッド１２０とをホストし得る。乱数生成スレッド１１８と連鎖スレッド１２０とを含むプロセスは、（例えばプロセッサ親和性や類似の指示などによって）その指定の連鎖コア１０８、１１０、１１２にピン留めされ得る。そのようなピン留めは、連鎖スレッド１２０が空間を探索する際のキャッシュ局所性の保持を助長し得る。
【００２４】
乱数生成スレッド１１８と連鎖スレッド１２０とは切り離されているため、連鎖コア１０８は、乱数生成スレッド１１８を処理し続けてよく、連鎖スレッド１２０の動作を待つ必要がない。乱数生成スレッド１１８は、（連鎖内）状態遷移を判定する際に使用するためのランダムビット生成を行い得る。ランダムビット生成には、ハードウェアのランダムビット生成器と擬似ランダムのソフトウェアによるビット生成器のどちらも使用することができる。
【００２５】
交換提案コア１０６は、交換提案生成待ち行列１２２を含み得る。交換提案生成待ち行列１２２は、交換提案生成スレッド１１４によって生成された交換提案のうちの１つまたは複数を記憶するように構成され得る。交換提案生成待ち行列１２２は、コア特有のバッファなどとして実装され得る。交換提案コア１０６は、交換提案分配スレッド１１６を介して交換提案生成待ち行列１２２から連鎖コア１０８、１１０、１１２へ交換提案のうちの１つまたは複数を分配するように構成され得る。
【００２６】
結果として得られる交換提案はそれらが作成された後でいつでも使用することができるため、交換提案コア１０６は、いつでも交換提案の生成を開始し、連続して、またはほぼ連続して交換提案生成待ち行列１２２に取り込み続けてよい。また交換提案コア１０６は、分配スレッド１１６も、連鎖スレッド１２０をホストする連鎖コア１０８、１１０、１１２へ交換提案を分配するように処理し得る。例えば、連鎖スレッド１２０からの要求に応じて、分配スレッド１１６が、当該連鎖スレッド１２０へ１つまたは複数の交換提案を分配し得る。分配スレッド１１６は、交換提案生成待ち行列１２２からの交換提案のデキューアとして動作し得る。
【００２７】
第１の連鎖コア１０８は交換提案分配待ち行列１２４を含み得る。交換提案分配待ち行列１２４は、第１の連鎖コア１０８によって受け取られた交換提案のうちの１つまたは複数を記憶するように構成され得る。交換提案分配待ち行列１２４は、コア特有のバッファなどとして実装され得る。個々の連鎖コア１０８と関連付けられた個々の連鎖スレッド１２０が、交換提案コア１０６から、少なくとも最も近い交換提案（例えば、現在の反復に関して最も近い交換提案など）を獲得し得る。例えば、連鎖スレッド１２０と関連付けられた交換提案分配待ち行列１２４は、第１の連鎖コア１０８と関連付けられた交換提案の待ち行列を有し得る。他の連鎖コア１１０、１１２と関連付けられた連鎖スレッドは、それぞれの交換提案分配待ち行列を一杯に保つ役割を果たし得る。例えば、第２の交換提案分配待ち行列１２６は第２の連鎖コア１１０と関連付けられ得る。第２の交換提案分配待ち行列１２６は、第２の連鎖コア１２６によって受け取られた交換提案のうちの１つまたは複数を記憶するように構成され得る。
【００２８】
第１の連鎖コア１０８はランダムビット待ち行列１２８を含み得る。ランダムビット待ち行列１２８は、乱数生成スレッド１１８によって生成された乱数のうちの１つまたは複数を記憶するように構成され得る。ランダムビット待ち行列１２８は、コア特有のバッファなどとして実装され得る。同様に、第２のランダムビット待ち行列１３０も第２の連鎖コア１１０と関連付けられ得る。ランダムビット待ち行列１３０は、第２の連鎖コア１１０と関連付けられた乱数生成スレッドによって生成された乱数のうちの１つまたは複数を記憶するように構成され得る。
【００２９】
乱数は、それらが生成された後でいつでも使用され得るため、乱数生成スレッド１１８は、任意のスケジュールで自由に走り、任意のスケジュールでランダムビット待ち行列１２８を満たしてよい。そのため、個々の連鎖コア１０８は、通常、関連付けられたランダムビット待ち行列１２８にアクセスし、関連付けられた連鎖スレッド１２０は、当該ランダムビット待ち行列１２８から乱数を除去し得る。
【００３０】
動作に際して、連鎖スレッド１２０が次の提案の交換の反復に到達する前には、関連付けられた連鎖コア１０８は連鎖スレッド１２０（および乱数生成スレッド１１８）を自由に処理し得る。連鎖コア１０８が指定の反復（例えば、受け取った交換提案と関連付けられた反復など）に到達した後で、連鎖スレッド１２０は、交換が行われるべきかどうか、および必要な場合には、状態を交換すべきかどうか判定するのに十分な情報を共有するために、提案された交換連鎖スレッド（例えば、第２の連鎖コア１１０と関連付けられた連鎖スレッドなど）を待機し得る。可能性のある交換に関する通信は、ポイントツーポイント通信（例えば連鎖スレッド対連鎖スレッドなど）とすることができる。乱数生成スレッド１１８によって生成され、ランダムビット待ち行列１２８に記憶された乱数は、交換が行われるべきかどうかの判定の間に消費され得る。ある例では、連鎖スレッド１２０は、可能性のある交換について提案されている別の連鎖スレッドを待機している間に１つまたは複数のさらに別の交換提案を要求し得る。その間、連鎖コア１０８は乱数生成スレッド１１８を処理し続けてよい。可能性のある交換を考慮している最中の連鎖コア（例えば第１の連鎖コア１０８や第２の連鎖コア１１０など）を除く、残りの連鎖コア（例えば連鎖コア１１２など）は、乱数生成スレッドも連鎖スレッドも自由に続行してよい。特定の交換提案の評価の間、または評価の後で、可能性のある交換を考慮している最中の連鎖コア（例えば第１の連鎖コア１０８や第２の連鎖コア１１０など）は、（例えば、それぞれの交換提案分配待ち行列１２４、１２６が空である場合などには）交換提案コア１０６から次の交換提案を受け取り得る。交換が完了した後で、連鎖コア１０８、１１０は、関連付けられた連鎖スレッド１２０の処理を再開し得る。上記のように仕事とポイントツーポイント同期とを分割すれば、高度な連鎖コア利用が、比較的少ないコア間通信で達成され得る。
【００３１】
図２は、本開示の少なくともいくつかの実施形態に従って構成された、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作についてのプロセス例２００を示す図である。図示の例において、プロセス２００、および本明細書で説明する他のプロセスは、ハードウェア、ソフトウェア、および／またはファームウェアのうちの１つまたは複数によって実施され得る、処理ステップ、機能動作、イベントおよび／または作用などとして説明され得る様々な機能ブロックまたは措置を示す。当業者は、本開示を考慮すれば、図２に示す機能ブロックの多くの代替が様々な実施態様において実施され得ることを理解するであろう。例えば、プロセス２００は、図２に示すように、特定の順序のブロックまたは措置を含むが、これらのブロックまたは措置が提示される順序は、必ずしも特許請求される主題を任意の特定の順序に限定するものであるとは限らない。同様に、特許請求される主題の範囲を逸脱することなく、図２に示されていない介在措置および／または図２に示されていないさらに別の措置が用いられてもよく、かつ／または図２に示す措置のうちのいくつかが除去されてもよい。プロセス２００は、動作２０２、動作２０４、動作２０６、動作２０８、および／または動作２１０のうちの１つまたは複数を含み得る。
【００３２】
図示のように、プロセス２００は、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作について実施され得る。処理は動作２０２、「交換提案を生成する」から開始することができ、そこで、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案が交換提案コア１０６（図１参照）によって生成され得る。例えば、交換提案コア１０６（図１参照）と関連付けられた交換提案スレッド１１４（図１参照）がそのような交換提案を生成し得る。
【００３３】
処理は動作２０２から動作２０４「交換提案を受け取る」へ進むことができ、そこで、交換提案のうちの１つまたは複数が、連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって、交換提案コア１０６（図１参照）から受け取られ得る。例えば、交換提案は、連鎖コア１０８、１１０、１１２のうちの１つまたは複数によって受け取られるように、交換提案生成待ち行列１２２（図１参照）から分配され得る。
【００３４】
動作２０６は、動作２０２〜動作２０４の後、その間、および／またはその前に行われ得る。動作２０６「乱数を生成する」では、乱数が連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって生成され得る。例えば、連鎖コア１０８（図１参照）と関連付けられた乱数生成スレッド１１８（図１参照）がそのような乱数を生成し得る。
【００３５】
処理は動作２０６から動作２０８「連鎖を処理する」へ進むことができ、そこで、分散型マルコフ連鎖モンテカルロ法の連鎖部分の現在の反復が、連鎖コア１０８、１１０、１１２（図１参照）のうちの１つまたは複数によって処理され得る。そのような連鎖部分は、少なくとも一部は動作２０６で生成された乱数に基づいて処理され得る。例えば、連鎖コア１０８（図１参照）と関連付けられた連鎖スレッド１２０（図１参照）がそのような連鎖部分を処理し得る。
【００３６】
処理は動作２０８から動作２１０「待機する」へ進むことができ、そこで、連鎖スレッド１２０（図１参照）が、第２の連鎖コア（例えば図１の連鎖コア１１０など）と関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。そのような待機は、少なくとも一部は交換提案のうちの１つまたは複数に基づくものとすることができる。例えば、所与の交換提案は、分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報と、状態情報の交換のために提案される連鎖部分の特定の対（例えば連鎖コア１０８と関連付けられた連鎖部分および連鎖コア１１０と関連付けられた連鎖部分など）（図１参照）に関連した情報とを含み得る。
【００３７】
動作に際して、プロセス２００は、動作２２８での連鎖コア１０８の待機の間、途切れることなく、連鎖コア１０８によって乱数を生成し続けてよい。同様にプロセス２００は、動作２２８での連鎖コア１０８の待機の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。加えてプロセス２００は、動作２０４での交換提案分配スレッド１１６の分配の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。さらにプロセス２００は、分散型マルコフ連鎖モンテカルロ法の統計的性能も維持し得る。例えば、プロセス２００を利用しない結果と比較すると、プロセス２００を使用することにより分散型マルコフ連鎖モンテカルロ法の結果に対して統計的調整を行わなくて済む可能性もある。
【００３８】
図３は、本開示の少なくともいくつかの実施形態に従って構成された、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作についてのプロセス例３００を示す図である。図示の例において、プロセス３００、および本明細書で説明する他のプロセスは、ハードウェア、ソフトウェア、および／またはファームウェアのうちの１つまたは複数によって実施され得る、処理ステップ、機能動作、イベントおよび／または作用などとして説明され得る様々な機能ブロックまたは措置を示す。当業者は、本開示を考慮すれば、図３に示す機能ブロックの多くの代替が様々な実施態様において実施され得ることを理解するであろう。例えば、プロセス３００は、図３に示すように、特定の順序のブロックまたは措置を含むが、これらのブロックまたは措置が提示される順序は、必ずしも特許請求される主題を任意の特定の順序に限定するものであるとは限らない。同様に、特許請求される主題の範囲を逸脱することなく、図３に示されていない介在措置および／または図３に示されていないさらに別の措置が用いられてもよく、かつ／または図３に示す措置のうちのいくつかが除去されてもよい。プロセス３００は、動作３０２、動作３０４、動作３０６、動作３０８、動作３１０、動作３１２、動作３１４、動作３１６、動作３２２、動作３２４、動作３２６、動作３２８、動作３３０、動作３３２、動作３３４、動作３３６、動作３３８、動作３４０および／または動作３４２のうちの１つまたは複数を含み得る。
【００３９】
図示のように、プロセス３００は、分散型マルコフ連鎖モンテカルロ法を実施する間のコアの利用を維持するためのマルチコアプロセッサの動作について実施され得る。処理は動作３０２「交換提案を生成し、かつ／または記憶する」から開始することができ、そこで、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案が交換提案コア１０６によって生成され得る。例えば、交換提案コア１０６と関連付けられた交換提案スレッド１１４がそのような交換提案を生成し得る。加えて、そのような交換提案が記憶され得る。例えばそのような交換提案は、交換提案生成待ち行列１２２（図１参照）に記憶され得る。
【００４０】
処理は動作３０２から動作３０４「交換提案を分配する」へ進むことができ、そこで、交換提案のうちの１つまたは複数が、交換提案コア１０６によって、連鎖コア１０８、連鎖コア１１０、および／または連鎖コア１１２のうちの１つまたは複数へ分配され得る。例えば交換提案は、交換提案生成待ち行列１２２（図１参照）から分配され得る。
【００４１】
処理は動作３０４から動作３０６「交換提案を記憶する」へ進むことができ、そこで、そのような分配された交換提案が連鎖コア１０８によって受け取られ、おそらくは、後で使用するために記憶され得る。例えばそのような分配された交換提案は、交換提案分配待ち行列１２４（図１参照）によって記憶され得る。ある例では、同様の動作３０８と動作３１０とが、それぞれ、連鎖コア１１０と連鎖コア１１２とによって行われ得る。
【００４２】
動作３１２〜動作３１６は、動作３０２〜動作３０６の後、その間、および／またはその前に行われ得る。動作３１２「乱数を生成し、かつ／または記憶する」で、乱数が連鎖コア１０８によって生成され、後で使用するためにランダムビット待ち行列１２８（図１参照）によって記憶され得る。例えば、連鎖コア１０８と関連付けられた乱数生成スレッド１１８がそのような乱数を生成し、かつ／または記憶し得る。ある例では、同様の動作３１４と動作３１６とが、それぞれ、乱数生成スレッド３１８と乱数生成スレッド３１９とによって行われ得る。
【００４３】
処理は動作３０６から動作３２２「連鎖を処理する」へ進むことができ、そこで、分散型マルコフ連鎖モンテカルロ法の連鎖部分の現在の反復が連鎖コア１０８によって処理され得る。そのような連鎖部分は、少なくとも一部は、ランダムビット待ち行列１２８（図１参照）に記憶された乱数に基づいて処理され得る。例えば、連鎖コア１０８と関連付けられた連鎖スレッド１２０がそのような連鎖部分を処理し得る。ある例では、同様の動作３２４と動作３２６とが、それぞれ、連鎖スレッド３２０と連鎖スレッド３２１とによって行われ得る。
【００４４】
処理は動作３２２から動作３２８「待機する」へ進むことができ、そこで、連鎖スレッド１２０が、第２の連鎖コア（例えば連鎖コア１１０など）と関連付けられた分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し得る。そのような待機は少なくとも一部は交換提案のうちの１つまたは複数に基づくものとすることができる。例えば、所与の交換提案は、分散型マルコフ連鎖モンテカルロ法の特定の反復に関連した情報と、状態情報の交換のために提案される連鎖部分の特定の対（例えば連鎖コア１０８と関連付けられた連鎖部分および連鎖コア１１０と関連付けられた連鎖部分など）に関連した情報とを含み得る。
【００４５】
処理は動作３２８から動作３３０「情報を交換する」へ進むことができ、そこで、連鎖スレッド１２０は、交換が行われるべきかどうか判定するのに十分な情報を別の連鎖スレッド（例えば連鎖スレッド３２０）と交換し得る。
【００４６】
動作３３２〜動作３３６は、動作３２８〜動作３３０の後、その間、および／またはその前に行われ得る。動作３３２「交換提案を要求する」で、連鎖スレッド１２０は１つまたは複数のさらに別の交換提案を要求し得る。例えば、連鎖スレッド１２０は、可能性のある交換について提案されている別の連鎖スレッド（例えば連鎖スレッド３２０など）を待機している間に１つまたは複数のさらに別の交換提案を要求し得る。ある例では、同様の動作３３４が連鎖スレッド３２０によって行われ得る。処理は動作３３２または動作３３４から動作３３６「交換提案を分配する」へ進むことができ、そこで、１つまたは複数のさらに別の交換提案が、交換提案コア１０６によって、要求に応じて、連鎖コア１０８、連鎖コア１１０、および／または連鎖コア１１２のうちの１つまたは複数へ分配され得る。例えば、交換提案は、交換提案生成待ち行列１２２（図１参照）から分配され、連鎖コア１０８によって受け取られ、おそらくは、後で使用するために交換提案分配待ち行列１２４（図１参照）に記憶され得る。
【００４７】
処理は動作３３０から動作３３８「状態を交換することに決定する」へ進むことができ、そこで、状態を交換する、または交換しないという決定が行われ得る。例えば、第１の連鎖コア１０８および／または第２の連鎖コア１１０は、少なくとも一部は交換提案分配待ち行列１２４（図１参照）に記憶された交換提案のうちの１つまたは複数に基づく提案された交換に従い得る。連鎖コア（例えば第１の連鎖コア１０８および／または第２の連鎖コア１１０）のうちの１つが、提案された交換に従い、少なくとも一部は動作３３０の交換情報に基づいて交換を行うことに決定し得る。
【００４８】
処理は動作３３８から動作３４０「連鎖を処理する」へ進むことができ、そこで、第１の連鎖部分の後続の反復が連鎖コア１０８によって処理され得る。例えば、状態が交換されている場合には、第１の連鎖部分の後続の反復が、少なくとも一部は第２の連鎖からの交換された状態と、ランダムビット待ち行列１２８（図１参照）に記憶された乱数とに基づいて処理され得る。例えば、連鎖コア１０８と関連付けられた連鎖スレッド１２０は、少なくとも一部は、第２の連鎖コア１１０と関連付けられた第２の連鎖スレッド３２０からの交換された状態に基づいてそのような連鎖部分を処理し得る。ある例では、同様の動作３４２が連鎖スレッド３２０によって行われ得る。
【００４９】
動作に際して、プロセス３００は、動作３２８における連鎖コア１０８の待機の間、途切れることなく、連鎖コア１０８によって乱数を生成し続けてよい。同様にプロセス３００は、動作３２８における連鎖コア１０８の待機の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。加えてプロセス３００は、動作３０４および動作３３６における交換提案分配スレッド１１６の分配の間、途切れることなく、交換提案コア１０６によって交換提案を生成し続けてよい。さらにプロセス３００は、分散型マルコフ連鎖モンテカルロ法の統計的性能も維持し得る。例えば、プロセス３００を利用しない結果と比較すると、プロセス３００を使用することにより分散型マルコフ連鎖モンテカルロ法の結果に対して統計的調整を行わなくて済む可能性もある。
【００５０】
図４に、本開示の少なくともいくつかの実施形態に従って構成されたコンピュータプログラム製品の例４００を示す。コンピュータプログラム製品４００は、信号担持媒体４０２を含み得る。信号担持媒体４０２は、１つまたは複数のプロセッサによって実行されるときに、コンピューティング機器が、図１、図２および／または図３を参照して前述した機能を提供することを動作的に可能にし得るマルチコアプロセッサの複数のコリジョン・ドメイン・ネットワーク間の通信を円滑化するための１つまたは複数の機械可読命令４０４を含み得る。よって、例えば図１のシステムを参照すると、マルチコアプロセッサ１００は、媒体４０２によって伝えられる命令４０４に応答して、図２および／または図３に示す措置のうちの１つまたは複数に着手し得る。
【００５１】
ある実施態様では、信号担持媒体４０２は、それだけに限らないが、ハード・ディスク・ドライブ、コンパクトディスク（ＣＤ）、ディジタル多用途ディスク（ＤＶＤ）、ディジタルテープ、メモリなどといったコンピュータ可読媒体４０６を包含し得る。ある実施態様では、信号担持媒体４０２は、それだけに限らないが、メモリ、読取り／書込み（Ｒ／Ｗ）ＣＤ、Ｒ／Ｗ ＤＶＤなどといった書込み可能媒体４０８を包含し得る。ある実施態様では、信号担持媒体４０２は、それだけに限らないが、ディジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）といった通信媒体４１０を包含し得る。
【００５２】
図５は、本開示の少なくともいくつかの実施形態に従って構成された、コンピューティング機器の例５００を示すブロック図である。基本構成の一例５０１では、コンピューティング機器５００は、１つまたは複数のプロセッサ５１０とシステムメモリ５２０とを含み得る。プロセッサ５１０とシステムメモリ５２０との間の通信にはメモリバス５３０を使用することができる。
【００５３】
所望の構成に応じて、プロセッサ５１０は、それだけに限らないが、マイクロプロセッサ（μΡ）、マイクロコントローラ（μＣ）、ディジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせを含む任意の種類のものとすることができる。プロセッサ５１０は、レベル１キャッシュ５１１やレベル２キャッシュ５１２といった１つまたは複数のレベルのキャッシュ、プロセッサコア５１３、およびレジスタ５１４を含むことができる。プロセッサコア５１３は、算術論理演算装置（ＡＬＵ）、浮動小数点演算装置（ＦＰＵ）、ディジタル信号処理コア（ＤＳＰコア）、またはそれらの任意の組み合わせを含むことができる。またメモリコントローラ５１５をプロセッサ５１０と一緒に使用することもでき、ある実施態様では、メモリコントローラ５１５をプロセッサ５１０の内蔵部品とすることができる。
【００５４】
所望の構成に応じて、システムメモリ５２０は、それだけに限らないが、揮発性メモリ（ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、フラッシュメモリなど）、またはそれらの任意の組み合わせを含む任意の種類のものとすることができる。システムメモリ５２０は、オペレーティングシステム５２１、１つまたは複数のアプリケーション５２２、およびプログラムデータ５２４を含み得る。アプリケーション５２２は、図２のプロセス２００および／または図３のプロセス３００に関して説明した機能ブロックおよび／または動作を含む本明細書で説明した機能および／または動作を実施するように構成することができるコア使用維持アルゴリズム５２３を含み得る。プログラムデータ５２４は、コア使用維持アルゴリズム５２３と共に使用するための交換提案データ５２５を含み得る。ある例示的実施形態では、アプリケーション５２２は、コア使用維持の実施態様が本明細書で説明したように提供され得るようにオペレーティングシステム５２１上でプログラムデータ５２４と共に動作するように構成され得る。この説明した構成は、図５において、破線５０１内の構成要素によって示されている。
【００５５】
コンピューティング機器５００は、さらに別の機構または機能と、基本構成５０１と任意の必要な機器およびインターフェースとの間の通信を円滑化するためのさらに別のインターフェースとを有していてもよい。例えば、バス／インターフェースコントローラ５４０が、記憶インターフェースバス５４１を介した基本構成５０１と１つまたは複数のデータ記憶装置５５０との間の通信を円滑化するのに使用されてもよい。データ記憶装置５５０は、取り外し可能記憶装置５５１、取り外し不能記憶装置５５２、またはそれらの組み合わせとすることができる。取り外し可能記憶装置および取り外し不能記憶装置の例には、いくつか例をあげると、フレキシブル・ディスク・ドライブやハード・ディスク・ドライブ（ＨＤＤ）といった磁気ディスク装置、コンパクトディスク（ＣＤ）ドライブやディジタル多用途ディスク（ＤＶＤ）ドライブといった光ディスクドライブ、ソリッド・ステート・ドライブ（ＳＳＤ）、およびテープドライブが含まれる。コンピュータ記憶媒体の例には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータといった情報の記憶のための任意の方法または技術で実施された揮発性および不揮発性、取り外し可能および取り外し不能の媒体が含まれ得る。
【００５６】
システムメモリ５２０、取り外し可能記憶５５１および取り外し不能記憶５５２はすべてコンピュータ記憶媒体の例である。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶他の磁気記憶装置、または所望の情報を記憶するのに使用され、コンピューティング機器５００によってアクセスされ得る他の任意の媒体が含まれる。任意のそのようなコンピュータ記憶媒体を機器５００の一部とすることができる。
【００５７】
またコンピューティング機器５００は、様々なインターフェース機器（例えば、出力インターフェース、周辺インターフェース、通信インターフェースなど）からの、バス／インターフェースコントローラ５４０を介した基本構成５０１への通信を円滑化するためのインターフェースバス５４２も含み得る。出力インターフェース５６０の例にはグラフィックス・プロセッシング・ユニット５６１やオーディオ・プロセッシング・ユニット５６２が含まれ、これらは、１つまたは複数のＡ／Ｖポート５６３を介してディスプレイやスピーカといった様々な外部機器へ通信するように構成され得る。周辺インターフェース５７０の例には、シリアル・インターフェース・コントローラ５７１やパラレル・インターフェース・コントローラ５７２が含まれ、これらは、１つまたは複数のＩ／Ｏポート５７３を介して入力装置（例えば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置など）や、他の周辺機器（例えば、プリンタ、スキャナなど）といった外部機器と通信するように構成され得る。通信インターフェース５８０の例にはネットワークコントローラ５８１が含まれ、ネットワークコントローラ５８１は、１つまたは複数の通信ポート５８２を介した、ネットワーク通信上での１台または複数の他のコンピューティング機器５９０との通信を円滑化するように構成され得る。通信接続は通信媒体の一例である。通信媒体は、典型的には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータにより、搬送波や他の搬送機構といった変調データ信号において実現することができ、任意の情報配信媒体を含み得る。「変調データ信号」とは、その特性のうちの１つまたは複数が信号において情報を符号化するように設定または変更されている信号とすることができる。例をあげると、それだけに限らないが、通信媒体には、有線ネットワーク、直接配線接続といった有線媒体や、音響、無線周波数（ＲＦ）、赤外線（ＩＲ）、他の無線媒体といった無線媒体が含まれ得る。コンピュータ可読媒体という用語は、本明細書で使用する場合、記憶媒体と通信媒体の両方を含み得る。
【００５８】
コンピューティング機器５００は、携帯電話、携帯情報端末（ＰＤＡ）、パーソナル・メディア・プレーヤ、無線ウェブウォッチ機器、パーソナルヘッドセット機器、アプリケーション特有の機器、上記機能のいずれかを含むハイブリッド機器といったスモール・フォーム・ファクタの携帯用（またはモバイル）電子機器の一部として実施され得る。またコンピューティング機器５００は、ラップトップコンピュータ構成と非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとしても実施され得る。加えて、コンピューティング機器５００は、無線基地局または他の無線システムもしくは機器の一部としても実施され得る。
【００５９】
以上の詳細な説明のいくつかの部分は、コンピュータメモリといったコンピューティング・システム・メモリ内に記憶されたデータビットまたは２値ディジタル信号に対する動作のアルゴリズムまたは記号表現として提示されている。これらのアルゴリズム記述または表現は、データ処理技術において当業者により、その作業の内容を他の当業者に伝えるために使用される技法の例である。アルゴリズムは、この場合、また一般に、所望の結果に至る筋道の通った動作シーケンスまたは類似の処理であるとみなされる。このコンテキストにおいて、動作または処理は、物理量の物理的操作を伴う。必ずしもそうとは限らないが、典型的には、そのような量は、記憶され、転送され、結合され、比較され、または別の方法で操作されることの可能な電子信号または磁気信号の形をとり得る。場合によっては、主に一般に使用されているために、そのような信号を、ビット、データ、値、要素、記号、文字、項、番号、数値などと呼ぶのが好都合である。しかし、これらおよび類似の用語はすべて適切な物理量と関連付けられるべきであり、単なる便利な表示にすぎないことを理解すべきである。特に指示しない限り、以下の考察から明らかなように、本明細書全体を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「判定する（ｄｅｔｅｒｍｉｎｉｎｇ）」などといった用語を使用した考察は、コンピューティング機器のメモリ、レジスタ、もしくは他の情報記憶装置、伝送機器、または表示装置内の物理的な電子的量または磁気的量として表されるデータを操作し、または変換するコンピューティング機器の措置またはプロセスを指すことが理解される。
【００６０】
以上の詳細な説明では、ブロック図、流れ図、および／または例を使用して、機器および／またはプロセスの様々な実施形態を示した。そのようなブロック図、流れ図、および／または例が１つまたは複数の機能および／または動作を含む限りにおいて、そのようなブロック図、流れ図、または例に含まれる各機能および／または動作は、広範なハードウェア、ソフトウェア、ファームウェア、または事実上それらの任意の組み合わせによって、個別に、かつ／または一括して実施することができることが当業者には理解されるであろう。ある実施形態では、本明細書で説明する主題のいくつかの部分は、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、ディジタル信号プロセッサ（ＤＳＰ）、または他の集積形式によって実施され得る。しかし、本明細書で開示する実施形態のある態様は、集積回路において、その全部または一部を、１台または複数のコンピュータ上で走る１つまたは複数のコンピュータプログラムとして（例えば、１つまたは複数のコンピュータシステム上で走る１つまたは複数のプログラムとして）も、１つまたは複数のプロセッサ上で走る１つまたは複数のプログラムとして（例えば１つまたは複数のマイクロプロセッサ上で走る１つまたは複数のプログラムとして）も、ファームウェアとしても、事実上それらの任意の組み合わせとしても同等に実施することができること、ならびにソフトウェアおよび／またはファームウェアのための回路の設計および／またはコードの作成は、本開示を踏まえれば十分に当業者の技能範囲内となるはずであることを当業者は理解するであろう。加えて当業者は、本明細書で説明する主題の機構を様々な形態のプログラム製品として配布することができること、および本明細書で説明する主題の一例示的実施形態は、実際に配布を実行するのに使用される信号担持媒体の特定の種類にかかわらず適用できることも理解するであろう。信号担持媒体の例には、それだけに限らないが、フレキシブルディスク、ハード・ディスク・ドライブ（ＨＤＤ）、コンパクトディスク（ＣＤ）、ディジタル多用途ディスク（ＤＶＤ）、ディジタルテープ、コンピュータメモリなどといった書込み可能型媒体、ならびに、ディジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）といった伝送型媒体が含まれる。
【００６１】
本明細書で説明する主題は、場合によっては、別の異なる構成要素内に含まれる、または別の異なる構成要素と接続された異なる構成要素を示すことがある。そのように描かれるアーキテクチャは単なる例にすぎず、実際は、同じ機能を果たす他の多くのアーキテクチャを実施することができることを理解すべきである。概念的には、同じ機能を果たすための構成要素の任意の配置は、事実上、所望の機能が果たされるように「関連付けられている」。したがって、特定の機能を果たすように組み合わされた本明細書の任意の２つの構成要素は、アーキテクチャや介在する構成要素にかかわらず、所望の機能が果たされるように相互に「関連付けられた」ものとみなすことができる。同様に、そのように関連付けられた任意の２つの構成要素も、所望の機能を果たすように相互に「動作可能に接続され」、または「動作可能に結合され」ているものとみなすことができ、そのように関連付けることができる任意の２つの構成要素も、所望の機能を果たすように相互に「動作可能に結合可能である」ものとみなすことができる。動作可能に結合可能であるものの具体例には、それだけに限らないが、物理的に結合可能であり、かつ／もしくは物理的に相互作用する構成要素、および／または無線で相互作用可能であり、かつ／もしくは無線で相互作用する構成要素、および／または論理的に相互作用し、かつ／もしくは論理的に相互作用可能な構成要素が含まれる。
【００６２】
本明細書における実質的にいかなる複数形および／または単形数の用語の使用についても、当業者は、状況および／または用途に合わせてしかるべく、複数形から単数形に、かつ／または単数形から複数形に変換することができる。本明細書においては明確にするために様々な単数形／複数形の置換形が明示される場合がある。
【００６３】
一般に、本明細書において、特に添付の特許請求の範囲（例えば添付の特許請求の範囲の本文など）において使用される用語は、一般には、「非限定的な（ｏｐｅｎ）」用語として意図されている（例えば、「ｉｎｃｌｕｄｉｎｇ（〜を含み）」という用語は「それだけに限らないが〜を含み」と解釈すべきであり、「ｈａｖｉｎｇ（〜を有し）」という用語は「少なくとも〜を有し」と解釈すべきであり、「ｉｎｃｌｕｄｅｓ（〜を含む）」という用語は、「それだけに限らないが、〜を含む」と解釈すべきであるなど）ことが当業者には理解されるであろう。さらに、導入請求項記載の特定の数が意図される場合、そのような意図は当該請求項において明示的に記載され、そのような記載がない場合にはそのような意図が存在しないことも当業者には理解されるであろう。例えば理解の一助としてあげると、添付の特許請求の範囲は、請求項記載を導入するために、「少なくとも１つの（ａｔ ｌｅａｓｔ ｏｎｅ）」および「１つまたは複数の（ｏｎｅ ｏｒ ｍｏｒｅ）」という導入句の使用を含み得る。しかし、そのような句の使用は、同じ請求項が「１つまたは複数の」あるいは「少なくとも１つの」という導入句および「ａ」や「ａｎ」といった不定冠詞を含むときでさえも、不定冠詞「ａ」または「ａｎ」による請求項記載の導入が、そのような導入請求項記載を含む任意の特定の請求項を、ただ１つのそのような記載を含む発明だけに限定することを意味するものと解釈されるべきではない（例えば、「ａ」および／または「ａｎ」は、通常は、「少なくとも１つの」または「１つまたは複数の」を意味するものと解釈されるべきであるなど）。同じことが、請求項記載を導入するのに使用される定冠詞の使用についても当てはまる。加えて、導入請求項記載の特定の数が明示的に記載されている場合でさえも、そのような記載が、通常は、少なくとも記載される数を意味するものと解釈されるべきであることも当業者は理解するであろう（例えば、他の修飾語句を伴わない「２つの記載」という記載だけで、通常は、少なくとも２つの記載、または２つ以上の記載を意味するなど）。さらに、「Ａ、Ｂ、およびＣのうちの少なくとも１つなど」に類似した慣用表現が使用される場合、一般にそのような構造は、当業者が当該慣用表現を理解するはずの意味として意図されるものである（例えば、「Ａ、Ｂ、およびＣのうちの少なくとも１つを有するシステム」は、それだけに限らないが、Ａだけを、Ｂだけを、Ｃだけを、ＡとＢとを共に、ＡとＣとを共に、ＢとＣとを共に、かつ／またはＡ、Ｂ、およびＣを共に有するシステムを含むはずであるなど）。「Ａ、Ｂ、またはＣのうちの少なくとも１つなど」に類似した慣用表現が使用される場合、一般にそのような構造は、当業者が当該慣用表現を理解するはずの意味として意図されるものである（例えば、「Ａ、Ｂ、またはＣのうちの少なくとも１つを有するシステム」は、それだけに限らないが、Ａだけを、Ｂだけを、Ｃだけを、ＡとＢとを共に、ＡとＣとを共に、ＢとＣとを共に、かつ／またはＡ、Ｂ、およびＣを共に有するシステムを含むはずであるなど）。さらに、２つ以上の択一的項目を提示する事実上あらゆる選言的な語および／または句は、本明細書においてであれ、特許請求の範囲においてであれ、図面においてであれ、それらの項目のうちの１つ、それらの項目のうちのどちらか、またはそれらの項目の両方を含む可能性を企図するものと理解すべきであることも当業者には理解されるであろう。例えば、「ＡまたはＢ」という句は、「Ａ」または「Ｂ」または「ＡおよびＢ」の可能性を含むものと理解されるであろう。
【００６４】
本明細書では、様々な方法およびシステムを使用するいくつかの技法例を説明し、図示したが、特許請求される主題から逸脱することなく、様々な改変が加えられ得ること、および均等物で置換され得ることが当業者には理解されるはずである。加えて、本明細書で説明した中心概念から逸脱することなく、個々の状況を特許請求される主題の教示に適合させるための多くの改変も加えられ得る。したがって、特許請求される主題は開示の特定の例だけに限定されず、そのような特許請求される主題は、添付の特許請求の範囲内に含まれるすべての実施態様、およびその均等物も含み得ることが意図されている。
【特許請求の範囲】
【請求項１】
交換提案コアによる、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するステップと、
第１の連鎖コアによる、前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取るステップと、
前記第１の連鎖コアによる、複数の乱数を生成するステップと、
前記第１の連鎖コアによる、少なくとも一部は前記複数の乱数に基づいて、前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理するステップと、
前記第１の連鎖コアによる、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するステップと
を含み、
前記第１の連鎖コアによる前記乱数の生成が、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される方法。
【請求項２】
前記交換提案コアによる前記交換提案の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される請求項１に記載の方法。
【請求項３】
交換提案生成待ち行列による、前記交換提案のうちの１つまたは複数を記憶するステップと、
前記交換提案コアによる、前記交換提案のうちの１つまたは複数を前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するステップと
をさらに含む請求項１に記載の方法。
【請求項４】
交換提案分配待ち行列による、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するステップをさらに含み、前記交換提案分配待ち行列が前記第１の連鎖コアと関連付けられており、第２の交換提案分配待ち行列が前記第２の連鎖コアと関連付けられている請求項１に記載の方法。
【請求項５】
ランダムビット待ち行列による、前記複数の乱数のうちの１つまたは複数を記憶するステップをさらに含み、前記ランダムビット待ち行列が前記第１の連鎖コアと関連付けられており、第２のランダムビット待ち行列が前記第２の連鎖コアと関連付けられている請求項１に記載の方法。
【請求項６】
前記第１の連鎖コアによる、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の後に、
前記交換提案コアによる、前記第１の連鎖コアと前記第２の連鎖コアとへさらに別の交換提案を分配するステップと、
前記第１の連鎖コアおよび／または前記第２の連鎖コアによる、少なくとも一部は前記交換提案分配待ち行列に記憶された前記交換提案のうちの１つまたは複数に基づいて、前記第１の連鎖部分と関連付けられた状態を第２の連鎖部分と関連付けられた状態と交換することに決定するステップと、
前記第１の連鎖コアによる、少なくとも一部は、前記第２の連鎖からの交換された前記状態と、前記ランダムビット待ち行列によって記憶された前記複数の乱数とに基づいて、前記第１の連鎖部分の後続の反復を処理するステップと
をさらに含む請求項１に記載の方法。
【請求項７】
前記分散型マルコフ連鎖モンテカルロ法がメトロポリス結合型（Ｍｅｔｒｏｐｏｌｉｓ−ｃｏｕｐｌｅｄ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法を含む請求項１に記載の方法。
【請求項８】
特定の交換提案が、前記第１の連鎖部分と前記第２の連鎖部分と特定の反復とに関連した情報を含む請求項１に記載の方法。
【請求項９】
前記分散型マルコフ連鎖モンテカルロ法の統計的性能を維持するように適合されている請求項１に記載の方法。
【請求項１０】
複数のプロセッサコアを含むマルチコアプロセッサであって、
分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成されている交換提案コアと、
前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は前記複数の乱数に基づいて前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成された第１の連鎖コアと、
前記分散型マルコフ連鎖モンテカルロ法の前記第２の連鎖部分の現在の反復を処理するように構成された前記第２の連鎖コアと
を備え、
前記第１の連鎖コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく乱数の生成を続行するようにさらに構成されているマルチコアプロセッサ。
【請求項１１】
前記交換提案コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく前記交換提案の生成を続行するようにさらに構成されている請求項１０に記載のマルチコアプロセッサ。
【請求項１２】
前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案生成待ち行列をさらに備え、
前記交換提案コアが、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するようにさらに構成されている請求項１０に記載のマルチコアプロセッサ。
【請求項１３】
前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられている交換提案分配待ち行列と、
前記第２の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された、前記第２の連鎖コアと関連付けられている第２の交換提案分配待ち行列と
をさらに備える請求項１０に記載のマルチコアプロセッサ。
【請求項１４】
前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられているランダムビット待ち行列と、
前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第２の連鎖コアと関連付けられている第２のランダムビット待ち行列と
をさらに備える請求項１０に記載のマルチコアプロセッサ。
【請求項１５】
複数のプロセッサコアを含むコンピューティング機器であって、
分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成された交換提案コアと、
前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は前記複数の乱数に基づいて前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成された第１の連鎖コアと、
前記分散型マルコフ連鎖モンテカルロ法の前記第２の連鎖部分の現在の反復を処理するように構成された前記第２の連鎖コアと
を備え、
前記第１の連鎖コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく乱数の生成を続行するようにさらに構成されている
マルチコアプロセッサと、
メモリバスと、
前記メモリバスを介して前記マルチコアプロセッサと通信するように構成されたシステムメモリと
を備えるコンピューティング機器。
【請求項１６】
前記交換提案コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく交換提案の生成を続行するようにさらに構成されている請求項１５に記載のコンピューティング機器。
【請求項１７】
前記交換提案コアが、前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案生成待ち行列をさらに備え、前記交換提案コアが、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するようにさらに構成されている請求項１５に記載のコンピューティング機器。
【請求項１８】
前記マルチコアプロセッサが、
前記第１の連鎖コアが、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案分配待ち行列をさらに備えること、
前記第２の連鎖コアが、前記第２の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された第２の交換提案分配待ち行列をさらに備えること、
前記第１の連鎖コアが、前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられているランダムビット待ち行列をさらに備えること、および
前記第２の連鎖コアが、前記複数の乱数のうちの１つまたは複数を記憶するように構成された第２のランダムビット待ち行列をさらに備えること
をさらに備える請求項１５に記載のコンピューティング機器。
【請求項１９】
１つまたは複数のプロセッサによって実行された場合に、コンピューティング機器が、
交換提案コアにより、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成し、
第１の連鎖コアにより、前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、
前記第１の連鎖コアにより、複数の乱数を生成し、
前記第１の連鎖コアにより、少なくとも一部は前記複数の乱数に基づいて、前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、
前記第１の連鎖コアにより、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し、
前記第１の連鎖コアによる前記乱数の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行され、
前記交換提案コアによる前記交換提案の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される
ことを動作的に可能にする機械可読命令が記憶された信号担持媒体
を備える物品。
【請求項２０】
前記コンピューティング機器が、
交換提案生成待ち行列により、前記交換提案のうちの１つまたは複数を記憶し、
前記交換提案コアにより、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配し、
交換提案分配待ち行列により、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶し、
ランダムビット待ち行列により、前記複数の乱数のうちの１つまたは複数を記憶し、
前記交換提案分配待ち行列が前記第１の連鎖コアと関連付けられ、第２の交換提案分配待ち行列が前記第２の連鎖コアと関連付けられ、
前記ランダムビット待ち行列が前記第１の連鎖コアと関連付けられ、第２のランダムビット待ち行列が前記第２の連鎖コアと関連付けられる
ことをさらに動作的に可能にする請求項１９に記載の物品。
【請求項１】
交換提案コアによる、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するステップと、
第１の連鎖コアによる、前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取るステップと、
前記第１の連鎖コアによる、複数の乱数を生成するステップと、
前記第１の連鎖コアによる、少なくとも一部は前記複数の乱数に基づいて、前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理するステップと、
前記第１の連鎖コアによる、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するステップと
を含み、
前記第１の連鎖コアによる前記乱数の生成が、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される方法。
【請求項２】
前記交換提案コアによる前記交換提案の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される請求項１に記載の方法。
【請求項３】
交換提案生成待ち行列による、前記交換提案のうちの１つまたは複数を記憶するステップと、
前記交換提案コアによる、前記交換提案のうちの１つまたは複数を前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するステップと
をさらに含む請求項１に記載の方法。
【請求項４】
交換提案分配待ち行列による、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するステップをさらに含み、前記交換提案分配待ち行列が前記第１の連鎖コアと関連付けられており、第２の交換提案分配待ち行列が前記第２の連鎖コアと関連付けられている請求項１に記載の方法。
【請求項５】
ランダムビット待ち行列による、前記複数の乱数のうちの１つまたは複数を記憶するステップをさらに含み、前記ランダムビット待ち行列が前記第１の連鎖コアと関連付けられており、第２のランダムビット待ち行列が前記第２の連鎖コアと関連付けられている請求項１に記載の方法。
【請求項６】
前記第１の連鎖コアによる、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の後に、
前記交換提案コアによる、前記第１の連鎖コアと前記第２の連鎖コアとへさらに別の交換提案を分配するステップと、
前記第１の連鎖コアおよび／または前記第２の連鎖コアによる、少なくとも一部は前記交換提案分配待ち行列に記憶された前記交換提案のうちの１つまたは複数に基づいて、前記第１の連鎖部分と関連付けられた状態を第２の連鎖部分と関連付けられた状態と交換することに決定するステップと、
前記第１の連鎖コアによる、少なくとも一部は、前記第２の連鎖からの交換された前記状態と、前記ランダムビット待ち行列によって記憶された前記複数の乱数とに基づいて、前記第１の連鎖部分の後続の反復を処理するステップと
をさらに含む請求項１に記載の方法。
【請求項７】
前記分散型マルコフ連鎖モンテカルロ法がメトロポリス結合型（Ｍｅｔｒｏｐｏｌｉｓ−ｃｏｕｐｌｅｄ−ｔｙｐｅ）マルコフ連鎖モンテカルロ法を含む請求項１に記載の方法。
【請求項８】
特定の交換提案が、前記第１の連鎖部分と前記第２の連鎖部分と特定の反復とに関連した情報を含む請求項１に記載の方法。
【請求項９】
前記分散型マルコフ連鎖モンテカルロ法の統計的性能を維持するように適合されている請求項１に記載の方法。
【請求項１０】
複数のプロセッサコアを含むマルチコアプロセッサであって、
分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成されている交換提案コアと、
前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は前記複数の乱数に基づいて前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成された第１の連鎖コアと、
前記分散型マルコフ連鎖モンテカルロ法の前記第２の連鎖部分の現在の反復を処理するように構成された前記第２の連鎖コアと
を備え、
前記第１の連鎖コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく乱数の生成を続行するようにさらに構成されているマルチコアプロセッサ。
【請求項１１】
前記交換提案コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく前記交換提案の生成を続行するようにさらに構成されている請求項１０に記載のマルチコアプロセッサ。
【請求項１２】
前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案生成待ち行列をさらに備え、
前記交換提案コアが、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するようにさらに構成されている請求項１０に記載のマルチコアプロセッサ。
【請求項１３】
前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられている交換提案分配待ち行列と、
前記第２の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された、前記第２の連鎖コアと関連付けられている第２の交換提案分配待ち行列と
をさらに備える請求項１０に記載のマルチコアプロセッサ。
【請求項１４】
前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられているランダムビット待ち行列と、
前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第２の連鎖コアと関連付けられている第２のランダムビット待ち行列と
をさらに備える請求項１０に記載のマルチコアプロセッサ。
【請求項１５】
複数のプロセッサコアを含むコンピューティング機器であって、
分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成するように構成された交換提案コアと、
前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、複数の乱数を生成し、少なくとも一部は前記複数の乱数に基づいて前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機するように構成された第１の連鎖コアと、
前記分散型マルコフ連鎖モンテカルロ法の前記第２の連鎖部分の現在の反復を処理するように構成された前記第２の連鎖コアと
を備え、
前記第１の連鎖コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく乱数の生成を続行するようにさらに構成されている
マルチコアプロセッサと、
メモリバスと、
前記メモリバスを介して前記マルチコアプロセッサと通信するように構成されたシステムメモリと
を備えるコンピューティング機器。
【請求項１６】
前記交換提案コアが、前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に、途切れることなく交換提案の生成を続行するようにさらに構成されている請求項１５に記載のコンピューティング機器。
【請求項１７】
前記交換提案コアが、前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案生成待ち行列をさらに備え、前記交換提案コアが、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配するようにさらに構成されている請求項１５に記載のコンピューティング機器。
【請求項１８】
前記マルチコアプロセッサが、
前記第１の連鎖コアが、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された交換提案分配待ち行列をさらに備えること、
前記第２の連鎖コアが、前記第２の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶するように構成された第２の交換提案分配待ち行列をさらに備えること、
前記第１の連鎖コアが、前記複数の乱数のうちの１つまたは複数を記憶するように構成された、前記第１の連鎖コアと関連付けられているランダムビット待ち行列をさらに備えること、および
前記第２の連鎖コアが、前記複数の乱数のうちの１つまたは複数を記憶するように構成された第２のランダムビット待ち行列をさらに備えること
をさらに備える請求項１５に記載のコンピューティング機器。
【請求項１９】
１つまたは複数のプロセッサによって実行された場合に、コンピューティング機器が、
交換提案コアにより、分散型マルコフ連鎖モンテカルロ法と関連付けられた複数の交換提案を生成し、
第１の連鎖コアにより、前記交換提案コアから前記交換提案のうちの１つまたは複数を受け取り、
前記第１の連鎖コアにより、複数の乱数を生成し、
前記第１の連鎖コアにより、少なくとも一部は前記複数の乱数に基づいて、前記分散型マルコフ連鎖モンテカルロ法の第１の連鎖部分の現在の反復を処理し、
前記第１の連鎖コアにより、少なくとも一部は前記交換提案のうちの１つまたは複数に基づいて、第２の連鎖コアと関連付けられた前記分散型マルコフ連鎖モンテカルロ法の第２の連鎖部分の現在の反復が対応する反復に到達するまで待機し、
前記第１の連鎖コアによる前記乱数の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行され、
前記交換提案コアによる前記交換提案の生成が、前記第１の連鎖コアによる前記第２の連鎖コアが前記分散型マルコフ連鎖モンテカルロ法の対応する反復に到達するまでの前記待機の間に途切れることなく続行される
ことを動作的に可能にする機械可読命令が記憶された信号担持媒体
を備える物品。
【請求項２０】
前記コンピューティング機器が、
交換提案生成待ち行列により、前記交換提案のうちの１つまたは複数を記憶し、
前記交換提案コアにより、前記交換提案のうちの１つまたは複数を、前記交換提案生成待ち行列から前記第１の連鎖コアへ分配し、
交換提案分配待ち行列により、前記第１の連鎖コアによって受け取られた前記交換提案のうちの１つまたは複数を記憶し、
ランダムビット待ち行列により、前記複数の乱数のうちの１つまたは複数を記憶し、
前記交換提案分配待ち行列が前記第１の連鎖コアと関連付けられ、第２の交換提案分配待ち行列が前記第２の連鎖コアと関連付けられ、
前記ランダムビット待ち行列が前記第１の連鎖コアと関連付けられ、第２のランダムビット待ち行列が前記第２の連鎖コアと関連付けられる
ことをさらに動作的に可能にする請求項１９に記載の物品。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２０１３−５２１５４５（Ｐ２０１３−５２１５４５Ａ）
【公表日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１２−５５５０１４（Ｐ２０１２−５５５０１４）
【出願日】平成２３年１月３１日（２０１１．１．３１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２３２３６
【国際公開番号】ＷＯ２０１１／１０９１３１
【国際公開日】平成２３年９月９日（２０１１．９．９）
【出願人】（５０９３４８７８６）エンパイア テクノロジー ディベロップメント エルエルシー (117)
【Ｆターム（参考）】
【公表日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１月３１日（２０１１．１．３１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２３２３６
【国際公開番号】ＷＯ２０１１／１０９１３１
【国際公開日】平成２３年９月９日（２０１１．９．９）
【出願人】（５０９３４８７８６）エンパイア テクノロジー ディベロップメント エルエルシー (117)
【Ｆターム（参考）】
[ Back to top ]