この記事の本題を論じる前に、一言申し上げなければならないことがあります。長すぎると思われる方は、「はじめに」の部分は読まずに飛ばしていただいて結構です。
1.序文
私がそれを奇想天外だと感じていないことは明らかです。まず最初に、私は哲学を学んだわけでも、老子の『道経』を詳しく学んだわけでもないことを申し添えておきますが、マルチアカウンティングの方法を考案する際に、『道経』の考え方に触発されたことは事実です。以下に2つの例を挙げます：
最初の例では、アルゴリズムを見つけるために、マルチ検証の設計では、当初、私はサブのルックアップ構造のマルチレベルのルックアップ構造としてAVLツリーを使用していた、その時点で、私はAVLツリーは確かに配列よりも良くなると思う挿入と効率の削除の少し大きな配列は非常に低いため、唯一の非常に小さなデータのテーブルで使用することができます、テーブルを管理するために大量のデータすることはできません。私は、ある日、偶然、私は小国の老子のアイデアについての話で見たテレビを見て覚えて、結び目によるルールの問題について話して、これに触発され、AVLツリーは、配列のアイデアよりも良い疑問を持って、その後、サブ構造を見つけることを試みる最も原始的な配列に変更された結果を達成するために発見した場合でも、テーブルのデータのサイズの数百万人は、全体的なパフォーマンスに対処するために、AVLツリーの使用よりも優れています。
2つ目の例は、マルチコアの分散メモリ管理アルゴリズムを設計する際に、メモリの割り当てと解放にロックが必要ないように「奪う」アプローチを採用したことです。これは、『道経』の「無為自然」の思想にも影響を受けており、メモリ管理アルゴリズムの開発において、「貪欲」「利己主義」「窃取」が最も重要な要素であることがわかっているからです。"貪欲"、"利己主義"、"盗み "などの人間の本能はアルゴリズムに広く使われています。"盗み "さえもマルチアカウント方式で使われているのですから、その双子の兄弟である "強盗 "もマルチアカウント方式で使えるはずです。マルチコアアルゴリズムでは「盗み」さえも使われるのですから、その双子の兄弟である「強奪」もマルチコアアルゴリズムで使えるはずです。 このような観点から、最終的に「強奪」のアイデアがマルチコアの分散メモリ管理アルゴリズムで使え、共有メモリの割り当てと解放の効率を大幅に改善できることが発見されました。
老子の『道経』には様々な解釈があります。その中には、理論的なレベルでしか解釈できないものもありますし、私がその思想の一部を具体的なマルチアカウンティングの手法に応用し、実際にコンピュータで実行できるプログラムにしたことで、その解釈が奇想天外なものになったのですから、そのような奇想天外な解釈は多ければ多いほどいいと思います。
それでは本題に戻り、「盗む」アプローチと「利己的」アプローチを使用したマルチコア分散キューの詳細な例についてお話しし、一見一般的なアイデアがどのように実用的なプログラムになるかを見ていきましょう。
2.分散待ち行列の基本概念
マルチコア・プログラミングにおける条件付き同期パターン」では、共有キューで使用されるロックの数を減らすための具体的な方法について述べており、これを基に効率的なキュー・プールを構築することができます。
あなたは、スレッドグループの競争モードをキュープールを実装するために使用する場合は、スレッドの各グループは、キュープール内のサブキューに対応し、ときに自分のサブキューの操作でスレッドは、サブキューが空ですが、キューのうち、その後、記事の "老人 "は、メソッドの使用を "盗む "と呼ばれるキューからサブキューに属するスレッドの他のグループからすることができます。これは、記事で説明されている "steal" メソッドの使用です。
同期やロックの使用をさらに減らす良い方法はないでしょうか？答えはイエスです。他人から盗むことは、常に自分のポケットを空にするよりも不便です。「盗む」必要があるのは、自分のポケットが空だからです。もし私たちが裕福で、ポケットが膨らんでいれば、当然、他人を「盗む」必要はありません。
もちろん、コンピュータでは、"リッチ "なアプローチは、各スレッドにプライベートキューを与えることであり、各スレッドが自分のプライベートキューでほとんどの時間を操作できるように、操作を同期させる必要はありません。これはまた、記事 "老子 "に記載されている "利己的な "メソッドの使用です。
steal "と "selfish "の2つの方式に基づき、マルチコア環境に適応した分散キューを設計することができます。分散キューでは、キューを操作する各スレッドがプライベートキューを持ち、プライベートキュー間の負荷分散問題を解決するために、データの負荷分散を維持するためのキュープールも必要となります。
分散キューのデータ構造を以下に模式的に示します：
図1：分散キュー・データ構造の概略図
上記のデータ構造図では、実装を2つのステップに分けることができます：
1、キュープールの実装
2、各スレッドにプライベートキューを与えます。
キュー・プールの実装は、ここでは詳しく説明しませんが、先に説明した方法を使用して実現することができます。
3.局地的なキューを導入するためのアイデア
ローカライズされたキューをスレッドに割り当てるには、まず作成されたキューを配列に配置し、次にスレッドに 0 から始まる番号を付けるのが一般的です。0 番目の番号が付けられたスレッドは、配列添え字の 0 番目の位置に格納されたキューに対応し、1 番目の番号が付けられたスレッドは、配列添え字の 1 番目の位置に格納されたキューに対応します...。
各スレッドが自分自身のローカライズされたキューを取得したい場合、まずスレッド番号を取得し、次にスレッド番号を通して対応するキューにアクセスすればよいのです。 各スレッドの番号は異なるため、各スレッドは異なるキューにアクセスします。つまり、各キューには1つのスレッドしかアクセスしないため、各スレッドのローカライズされたキューを実現することができるのです。
オペレーティングシステムはこの機能を直接提供していません。仮にオペレーティングシステムが0からスレッド番号を振る機能を提供していたとしても、すべてのスレッドが分散キューにアクセスするとは限らないため、意味がありません。例えば、8つのスレッドがあり、0、3、5、7と番号が振られたスレッドが分散キューにアクセスする場合、分散キューの作成時に8つのローカルキューを作成する必要があります。
その目的は、分散キューにアクセスする全てのスレッドに0から順番に番号を振ることです。例えば、分散キューにアクセスするスレッドがN個ある場合、これらN個のスレッドに0, 1, ...N-1のように連番を振る必要があります。
#p#
4.スレッド番号の付け方
オペレーティングシステムでは通常、スレッドローカルストレージAPIが提供されており、このAPIを使って各スレッドにデータを設定したり、現在のスレッドが設定したデータを取り出すことができます。例えば、スレッド A に整数 0 を設定した場合、スレッド A が実行されている場所ならどこでも、対応する API を呼び出して整数 0 を取得することができます。
Windows ファミリーのオペレーティング・システムでは、スレッド化されたローカル・ストレージ操作を実装するために、関数 Tls_Alloc()、Tls_SetValue()、Tls_GetValue()、および Tls_Free() が提供されています。
以下に、関数 TlsAlloc()、Tls_SetValue()、Tls_GetValue()、および Tls_Free() の基本的な使用法を示します。
DWORD g_dwTlsIndex;
LONG volatile g_dwThreadId = 0;
int GetId()
{
//現在の実行スレッドに対してTlsSetValue()で設定された値を取得する。
int nId = (int)TlsGetValue(g_dwTlsIndex);
return (nId-1);
}
void ThreadFunc(void *args)
{
LONG Id = AtomicIncrement (&g_dwThreadId); // _dwThreadIdアトミックな追加操作を行う
TlsSetValue(g_dwTlsIndex, (void *)Id); //現在実行中のスレッドに値を設定する
printf("ThreadFunc2: Thread Id = %ld/n", GetId());
}
int main(int argc, char* argv[])
{
g_dwTlsIndex = TlsAlloc(); //インデックスをローカルに格納するスレッドの割り当ては、スレッドを作成する前に実行する必要がある。
_beginthread(ThreadFunc, 0, NULL);
_beginthread(ThreadFunc, 0, NULL);
Sleep(100); //上記2つのスレッドの実行終了までの待ち時間
TlsFree(g_dwTlsIndex);
return 0;
}
これはWindowsオペレーティング・システムのInterlockedIncrement()関数に相当します。Widnowsシステムでは、AtomicIncrement()関数は以下のマクロ定義を使って実装できます：
#defineAtomicIncrement連動インクリメント
上記のプログラムは実行後、以下の結果を出力します：
ThreadFunc: スレッド ID = 0
ThreadFunc: スレッド ID = 1
上記のコードと実行結果から、ThreadFunc()関数内でGetValue()が実行されているにもかかわらず、2つのスレッドがGetValue()を実行したときに得られる値が異なっていることがわかります。一方は1で、もう一方は2です。
TlsGetValue()の戻り値は、失敗した場合は0なので、TlsSetValue()関数を使用する場合は1から設定し、GetId()関数では、TlsGetValue()の戻り値から1を引いた値を返すことに注意してください。
上記の方法を使用すると、スレッドIdの自動番号付けと関数を取得する分散キューを設計することができます。以下に詳細な実装コードを示します：
class CDistributedQueue {
private:
DWORD m_dwTlsIndex;
LONG volatile m_lThreadIdIndex;
public:
CDistributedQueue();
virtual ~CDistributedQueue();
LONG ThreadIdGet();
//他のメンバ関数を追加することもできる。
};
CDistributedQueue::CDistributedQueue()
{
m_dwTlsIndex = TlsAlloc();
m_lThreadIdIndex = 0;
}
CDistributedQueue::~CDistributedQueue()
{
TlsFree(m_dwTlsIndex);
}
LONG CDistributedQueue::ThreadIdGet()
{
LONG Id = (LONG )TlsGetValue(m_dwTlsIndex);
if ( Id == 0 )
{
Id = AtomicIncrement(&m_lThreadIdIndex);
TlsSetValue(Id);
}
return (Id - 1);
}
上記のコードでは、スレッド番号の設定または取得は ThreadIdGet() の 1 つのメンバ関数内で行われます。TlsSetValue()関数を呼び出すたびに、設定されたId値に順番に1が追加されるため、1、2、3、...というシーケンスが得られます。各スレッドが TlsSetValue()関数を呼び出した後、次に TlsGetValue()関数を呼び出すと、0 より大きい値が得られる必要があります。
そうでない場合は、スレッドが使用するローカル・キューの数が足りなくなり、 プログラム内でアウトオブバウンズなどの予期せぬ例外が発生する可能性があります。一般的な解決策は、ローカルキューの数を2倍にすることです。
分散キューにアクセスするスレッドには自動的に番号が振られ、分散キューを呼び出すスレッドには番号を気にする必要がないという点で、上記のスレッド番号の付け方は非常に便利です。
メソッド後のスレッドの自動採番により、キューイング、キューイングなどの分散キュー特有の操作を実装することができます。もちろん、コードの前に、特定の操作の実装では、キュー内の分散キューと操作のアウト方法を理解する必要があります。
#p#
5.キューイン・キューアウト操作
分散待ち行列の入出庫操作は、様々な運用戦略を持つ様々な種類のアプリケーションによって異なりますが、操作の種類に関わらず、基本的な考え方は、前提としてローカル待ち行列の操作を最大化することでなければなりません。以下は、分散キューで一般的に使用されるキューの入出庫操作の一覧です。
1) キュー外操作
アウトオブキューの操作は比較的簡単で、通常はまずローカルキューからデータを取得し、ローカルキューが空の場合は、共有キュープールからデータを取得します。
データが最初にローカルキューからフェッチされるため、ローカルキューのオペレーションを最大化するのに役立ちます。
キュー外操作のフローチャートを以下に示します：
図2：分散待ち行列の送信操作のフローチャート
2:チーム運営へ
インキュー操作はアウトキュー操作に比べて少し複雑で、よく使われる操作方法は2つあります：
戦略1：まずローカルキューが空かどうかを判断し、空であればデータをローカルキューに入れます。次に共有キュープールが満杯かどうかを判断し、満杯であればデータをローカルキューに入れ、そうでなければ共有キューに入れます。
キュー操作に入るこの戦略では、まずローカルキューの操作を考慮し、ローカルキューは少なくとも1つのデータを持っている必要があり、次に問題を負荷分散問題と考え、共有キュープールのデータは主にスレッド間のデータの負荷分散のために使用されます。共有キュープールのサイズは制限されなければなりません。そうでなければ、すべてのデータは共有キュープールに入り、ローカルキューは効果的に使用されません。
共有キュープールをどの程度の大きさに設定すれば、ローカルのキュー操作の最大化と負荷分散の問題との間で良いバランスが取れるかということは、現実的な検討事項であり、適切な値を得るためにはプログラムの性能をテストするのが最善です。
受信キューの運用戦略1の運用フローチャートは以下の通りです：
図3：分散待ち行列に対する待ち行列入力操作戦略1のフローチャート
戦略2：キューに入れるデータが複数ある場合、まずいくつかのデータをローカルキューに入れ、残りを共有キュープールに入れます。キュープールがいっぱいになっても、ローカルキューに入れます。
この戦略では、通常、キューにスレッドがすぐにキューからデータを取得するため、最初に自分のローカルキューにいくつかのデータを入れて、キューからデータを取得する次の時間がローカルキューからでなければならないことを確認するには、大幅にローカライズされたキュー操作の頻度を向上させることができます、効果的に同期操作を大幅に削減し、共有キュープールの操作を削減します。
受信キューの運用戦略2の運用フローチャートは以下の通りです：
図4：分散待ち行列に対する待ち行列入力操作戦略2のフローチャート
キュー内操作とキュー外操作の詳細なフローがあれば、分散キュー特有のコードを実装するのはずっと簡単です。
