Maker.io Staff | 2022年5月9日
アルゴリズムやプログラムの中には、終了までに時間がかかるものがあり、並列化の恩恵を受けられる可能性があります。しかし、並列プログラムを書くのは簡単なことではなく、実践と特別なテクニックが必要です。プログラマは、プログラムがどのように並列データアクセスと複数のスレッドのライフサイクルを管理するかに細心の注意を払う必要があります。そこで、この記事では、C言語におけるPOSIXスレッドの簡単な概要を紹介し、C言語プログラムで長時間実行されるアルゴリズムを高速化するために並列化を活用する方法を紹介します。
マルチスレッドプログラムとは何ですか？
コンピュータのアプリケーションに並列処理を導入するために、スレッドやプロセスを採用することができます。プロセスを使用する場合、各プロセスは、同じ物理マシン上または分散したコンピュータのネットワーク上で他のプロセスから独立して実行されます。ここでは、プロセスは、リモートプロシージャコール、計算結果および同期メッセージなどのデータを含むメッセージを交換する必要があります。もう1つの方法は、1つのコンピュータがより複雑なプログラムの一部として実行するスレッドを利用するものです。
どちらの方法にもさまざまなメリット/デメリットがあり、一概にどちらがよいとは言えません。しかし、一般にスレッドはプロセスと比較してより軽いユニットです。各スレッドはメモリ上に独自のスタック領域を持ち、他のスレッドとは独立してコードを実行します。しかし、スレッドは完全に分離された単位ではありません。分離されていないため、プロセス内のすべてのスレッドは同じヒープ領域を共有するので、プロセスのすべてのスレッドは同じグローバル変数とファイルハンドルにアクセスできます。
この図は、同じプロセスの複数のスレッドの関係を示しています。
最後に、スレッドをスケジュールし、CPU上でいつ実行してもよいかを決定するのは、コンピュータのオペレーティングシステムであることを忘れてはなりません。スレッドはプロセスの小さな部分であるため、OSはプロセスを交換するよりも速くスレッド間を切り替えることができます。しかし、OSのスケジューラがスレッドを特定の順番で実行させる保証はなく、実際に並列に実行される保証もないことを念頭に置いておく必要があります。
また、マルチコアCPUでなければ真の並列性は得られないということも忘れてはいけません。しかし、シングルスレッドシステムがスレッドの恩恵を受けられないということではありません。
プログラムでマルチスレッドを使用するメリット
多くのコンピュータプログラムは、外部のデータ、例えばハードディスクやクラウドストレージサーバ上のファイルにアクセスします。数秒かかるかもしれないし、厳密に非並列なプログラムではこの時点でブロックされてしまいます。しかし、プログラムがファイルの読み込みに別のスレッドを使用する場合、プログラムの残りの部分（グラフィカルUIなど）はユーザー入力に応答し続けることができます。
また、並列化が容易なプログラムでは、大幅な高速化を達成できることが少なくありません。すべてのアルゴリズムが並列化の恩恵を受けるわけではなく、不必要な並列化を行うと、時にはプログラムの速度が低下することもあります。スレッドとプロセスの切り替えには時間がかかりますし、スレッドが多すぎるとOSのオーバーヘッドが大きくなる可能性があります。しかし、スレッドは、例えばマージソートなど、簡単に並列化できるアルゴリズムには最適です。この場合、各スレッドはプログラムがソートしなければならない配列の単一部だけを操作することができ、スレッドが互いに邪魔になることはありません。スレッドが同じデータセットを操作するときは常に注意が必要です。他のスレッドが書き込んだデータを簡単に上書きしたり破損させたりすることがあるからです。
スレッドがなければ、現代のコンピューティングは成り立たない
スレッドは、プログラムがファイルアクセス操作のようなブロッキングコールを行う場合でも、アプリケーションが応答し続けることを保証する優れた方法です。また、複数のクライアントからのリクエストを同時に処理するウェブサーバもその一例です。スレッドがなければ、サーバは一度に1つのリクエストにしか応答できません。ユーザーがウェブページにアクセスするたびに、サーバは必要なタスクをすべて実行し、ユーザーに返信する必要があります。ウェブサイトの複雑さによっては、この作業に数秒かかることがあります。この間、サーバは他の受信要求をすべてキューに入れ、後で処理する必要があります。
もしサーバが一度に1つのリクエストしか処理できなかったら、人気のあるウェブサイトではそのキューがどれだけ長くなり、ウェブサイトの読み込みにどれだけ待たされるか想像してみてください。しかし、サーバは受信するリクエストごとに新しいスレッドを生成したり、プールから既存のスレッドを再利用したりして、すべてのユーザーに同時にサービスを提供することができます。
POSIXスレッドによる簡単なHello Worldプログラムの作成
前述のとおり、この記事では、Unix系OSで使用できるPOSIXスレッドについてのみ解説しています。しかし、基本的な原則は、すべてのスレッド実装、プログラミング言語およびオペレー ティングシステムに適用されます。次のような例を考えてみましょう。
/* Include statements omitted */
#define NUM_THREADS 8
#define MAX_LENGTH 40000
#define CHUNK_SIZE (MAX_LENGTH / NUM_THREADS) * 2
/* Function prototypes and struct definition omitted */
void* createThread(void *args)
{
struct arg_struct *vals = args;
longRunningTask(vals->start, vals->end, MAX_LENGTH / NUM_THREADS);
pthread_exit(NULL);
}
void longRunningTask(unsigned start, unsigned end, unsigned chunk)
{
unsigned* matrix = malloc(chunk * chunk * sizeof(unsigned));
if(matrix == NULL)
return;
int index = 0;
for(int i = start; i < end; i++)
{
for(int u = start; u < end; u++)
matrix[index++] = i * u;
}
free(matrix);
}
int main(int argc, char* argv[])
{
/* Print statements and time measurement omitted */
/* Sequential execution */
longRunningTask(0, MAX_LENGTH, MAX_LENGTH * MAX_LENGTH);
/* Parallel execution */
pthread_t threads[NUM_THREADS];
for(int i = 0; i < NUM_THREADS; i++)
{
int start = i * CHUNK_SIZE;
int end = (start + CHUNK_SIZE) - 1;
struct arg_struct thread_args;
thread_args.start = start;
thread_args.end = end;
thread_args.threadID = i;
int rc = pthread_create(&threads[i], NULL, createThread, (void*)&thread_args);
if (rc)
{
return -1;
}
}
for(int i = 0; i < NUM_THREADS; i++)
{
pthread_join(threads[i], NULL);
}
return 0;
}
上記のコードでは、符号なし整数値の大きな行列を構築しています。今回の構成では、行列は16億エントリを含んでいます。longRunningTask機能は、行列の構築手順を実装しています。行列全体を作成する場合、この方法はまず、行列の全要素を格納するのに十分なメモリを確保します。そして、すべてのエントリを繰り返し処理し、単純な乗算を行います。この関数は、その結果を行列に格納します。この方法には、並列スレッドが行列計算をより小さな計算チャンクに分解するのに役立つ3つのパラメータが含まれていることに注意してください。
逐次タスクでは40,000 × 40,000の計算を行うので、時間がかかります。一方、並列に実行される各スレッドは、
20,000 × 20,000の計算を行うだけでよいのです。スレッドは、1スレッドあたりの完成すべき作業が少ないだけ
でなく、並列で行うことになります。
メイン関数は、逐次計算と並列スレッドの両方を開始し、時間を計るものです。逐次アプローチでは、行列をより小さなサブ行列に分割することはありません。そのため、インデックス0から始まり、定義された最大のエントリ数で終了します。しかし、逐次計算がreturnで戻ると、次にメイン関数は複数のスレッド（この例では8つ）を生成します。メイン関数内の最初のforループは、新しいスレッドを作成します。ここでは、まず各スレッドのサブ行列がどこで始まり、どこで終わるかを定義します。スレッドは、巨大なマトリックスを、より扱いやすい小さな部分に分割します。次に、各スレッドがcreateThread関数を実行し、独自の開始/終了パラメータを指定してlongRunningTaskメソッドを呼び出します。longRunningTaskからスレッドが戻ると、createThread関数の最後の行でそのスレッドを破棄します。
最後に、メイン内の2番目のforループに注目してください。このループにより、メインプログラムはすべてのスレッドが終了するのを待ってからプログラムを停止します。さらに、このプログラムはすべての計算結果を破棄することに注意してください。現実の世界では、正しい結果を得るためには、サブ行列をより大きな行列に組み立てる必要があります。このプログラムを私のパソコンで実行すると、並列実行と逐次実行で実行時間が劇的に異なります。
この画像は、上記のサンプルプログラムの出力です。逐次計算では約4秒かかるのに対し、マルチスレッド
では2.5秒強で終了することに注目してください。
まとめ
スレッドは今日のソフトウェア開発において非常に有用であり、長時間実行されるタスクであってもシステムの応答性を維持するのに役立ちます。マルチタスクには、共有CPU上でタスクをスケジューリングできるOSが必要です。スレッドはプロセスよりも軽く、OSはスレッドの生成、破棄および切り替えを高速に行うことができます。プロセス内の各スレッドは、独自のコード、スタックおよびレジスタを使用します。しかし、1つのプロセスのすべてのスレッドは、同じヒープ領域とファイルハンドルなどのデータを共有します。
すべてのアルゴリズムやユースケースでマルチスレッドや並列化が有効なわけではないことに注意してください。しかし、多くのアルゴリズムを複数のスレッドで機能するように変換することはできます。ここでは、同期とロックに細心の注意を払う必要があります。これは、スレッドが他のスレッドによって作成されたデータを簡単に上書きしてしまう可能性があるためです。さらに、メインアプリケーションは、結果の処理をさらに進めるには、すべてのスレッドが終了するまで待機する必要があります。