C LANGUAGE TECHNOLOGY

【C言語】マルチコアプロセッサ向け並行ソートアルゴリズム【並列ソート】

2022年6月19日

悩んでいる人

C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

C言語でマルチコアプロセッサ向けソートアルゴリズム

C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを紹介します.

※並列ソートと言及されることが多いですが,並行ソートは並列ソートを含みます.

並行と並列の違いは以下の記事で詳しく解説されています.

並行ソートにより,ユニプロセッサのソートアルゴリズムを限界突破する方法がわかります.

まずはユニプロセッサ向けソートアルゴリズムを知りたいあなたはこちらからどうぞ.

C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを実装する場合,主に以下の方法があります.

本記事ではpthreadの実装を紹介します.

まずはpthreadを知りたいあなたはこちらからどうぞ.

C11規格のスレッドはこちらの記事で解説しています.

並行マージソート

並行マージソートは,マージソートの並行実行です.

並行マージソートのコードは以下になります.

実行結果の例は以下になります.

並行クイックソート

並行クイックソートは,クイックソートの並行実行です.

並行クイックソートのコードは以下になります.

実行結果の例は以下になります.

また,並行クイックソートを一般化した「サンプルソート」があります.

サンプルソートの実装例は以下になります.

並行分布数えソート

並行分布数えソートは,分布数えソートの並行実行です.

並行分布数えソートのコードは以下になります.(入力は0~MAXの整数を仮定しています.)

実行結果の例は以下になります.

バイトニックソート

バイトニックソートは,ソーティングネットワークの並行ソートアルゴリズムです.

バイトニックソートのコードは以下になります.

実行結果の例は以下になります.

バッチャー奇偶マージソート

バッチャー奇偶マージソートは,ケン・バッチャーにより提案されたソーティングネットワークの並行ソートアルゴリズムです.

バッチャー奇偶マージソートのコードは以下になります.

シェアソート

シェアソートは,データを長方形に並べた上で,各行/各列ごとにソートを行う並行ソートアルゴリズムです.

シェアソートのコードは以下になります.

実行結果の例は以下になります.

まとめ

C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを紹介しました.

並行ソートアルゴリズムを利用する際に参考にして下さい.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,