********************************************************************** セッションS2-c テーマ：今更聞けないマルチコアプログラミングの基礎講師：高田広章氏（名古屋大学）日時：2012/8/31 9:00〜10:20 参加人数：34名 ********************************************************************** ・講義の内容　マルチコアプロセッサ上でプログラムを作成する上で知っておくべきハードウェア知識について解説　特に，マルチコアプロセッサを生で使う場合に必要な知識を中心にする・最初にアンケート　以下の概念について知っているか？　　SMP 　　MESIプロトコル　　Load-Linked/Store-Conditional命令　　メモリオーダリングモデル　　TOPPERS/FMPカーネル　　OpenMP 　いずれについても用語は知っているが詳しくは知らないという参加者が多数 ------------------------------ ・マルチコアプロセッサの必要性　組み込みシステムにおける従来のマルチプロセッサ利用　　高性能な大規模組み込みシステム　　用件が異なるサブシステム　　別々に開発されたサブシステムの統合　　部品に含まれている　当時はコストがあがるのでなるべく避けなければならなかった　マルチコアプロセッサ（チップマルチプロセッサ）の登場により，低コスト化が可能になった　よってマルチコアプロセッサの重要性が増加した・マルチコアプロセッサの必要性その２　何故クロックを上げないのか？　　消費電力が上がり，高速に動くとそれだけエネルギーが必要になる　　2GHzのプロセッサ1つより400MHzのプロセッサを5つ動かす方が消費電力が小さい・マルチプロセッサ利用の課題　組み込みシステムでは大きい粒度での自然な並列性がある程度は存在する　並列性がプロセス，タスク，スレッドの形で実現されていれば，対応は比較的容易である　しかしソフトウェアでは実装されてない場合が多い・ハードウェア視点でのマルチプロセッサの分類　プロセッサの種類　　ホモジニアス，ヘテロジニアス，同時マルチスレッディング　プロセッサ間通信の方式　　共有メモリ　　　対称共有メモリ（UMA)，分散共有メモリ（NUMA) 　　メッセージ交換・ソフトウェア視点でのマルチプロセッサの分類　共有メモリ　　対称型マルチプロセッサ（SMP）- 負荷分散　　　各プロセッサの役割が同じ　　機能分散マルチプロセッサ　　　プロセッサごとの役割が異なる・対称型マルチプロセッサ（SMP）について　定義　　ハードウェア的には対称なリソース，同時アクセス可能な構成　　ソフトウェア的には役割をしばらない構成　SMPの例：ARMのMPCore 　利点　　PC用の汎用性プロセッサによい　　OSでの負荷分散　　チップの汎用性が高い（作り込む必要性がない）　問題点　　共有リソースが多くなるため，解析で求まる最大実行時間が大きくなり、リアルタイム性保証が難しい　　コヒーレンシとバス共有などの複雑な回路が必須・機能分散マルチプロセッサ（FDMP）について　定義：役割を固定したプロセッサ　例：東芝MeP 　　全コアがそれぞれ特殊なアクセラレータを持っている　ハードウェア構成的にも非対称マルチプロセッサ（AMP）になることも多い　　メモリや周辺デバイスがローカルバスでつながっている　例2：TIのOMAP1710(ARM926+TMC320) 　　ヘテロジニアスなマルチプロセッサ　利点　　共有リソースが限られているため解析が容易　　コヒーレンシなどがなくてもよい　問題　　作りこまなければならない（設計コスト高い）　　動的な負荷分散の実現は面倒　　チップの汎用性が低い　つまり，ハードリアルタイムでは有利・その他　疎統合マルチプロセッサが軽く紹介される　例：CELLプロセッサ ------------------------------------ ・以下コヒーレントキャッシュについて・マルチプロセッサにおけるキャッシュ　共有キャッシュ　　組み込みではL2が限界と言われている　コヒーレンスの問題　　問題の発生状況　　　複数のキャッシュで同じ番地のデータがキャッシュされた場合に発生　　　あるコアがその番地を書き換えた場合、他のコアは古いデータを持ち続ける　　どのような問題　　　同じ番地を読んでもコアによって異なる値になる　問題解決にはハードウェアでの一貫性を保つ仕組みが必要・キャッシュコヒーレンシ機構　スヌープ方式　　ライトアクセスを監視し、書き込まれた場合に自分のキャッシュを無効化　　　無効化のかわりに新しいデータを取り込むなどのバリエーションが存在　　共有バスがある場合にしか適用できないのでNoCでは適用不可　ディレクトリ方式　　どの番地がどのコア毎のキャッシュに格納されているかをディレクトリで一元管理・キャッシュコヒーレンシモデルのバリエーション　MESIプロトコル　　４状態で管理　　Modified, Exclusive, Shared, Invalid 　　MESIでも細かいバリエーションがある　他にはMSI,MOSI,MOESIなど　ソフトウェア開発者視点では関係ない話である ------------------------------------------ ・以下アトミック命令とスピンロックについて・アトミック命令の必要性　アトミック命令とは？　　不可分操作のこと　　一連のメモリアクセスを他のコアに邪魔されずに行うための命令　アトミック命令の必要性　　コア間でデータを共有する場合には必須・アトミック命令の種類と典型的な命令　Read-Modify-Write命令　　test-and-set(addr) 　　　addrを読み１を書き込みaddrの元の値を返す　　　最も基本的な命令　　他にはfetch-and-addやswap compare-and-swap 　CASとリトライループがあれば任意のRead-Modify-Write命令を模擬できる強力な命令　　　擬陽性の問題があるので注意が必要　　問題点　　　バスを占有してしまうため，性能低下の原因になってしまう　Load-Linked/Store-Conditional命令　　Load-Linked命令　　　そのアドレスのアクセスを監視　　Store-Conditional命令　　　条件付きストアで誰かが書き換えてなければストアが可能　　非常に強力な命令で擬陽性の問題がない　　細かな振る舞いには実装によってバリエーションがある　　他のバストランザクションを行えるため，バス使用効率が高い・実際のプロセッサのアトミック命令　古いプロセッサではRead-Modify-Write命令を持っているものが多い　　IA32のLockプリフィックス，xchg命令　　SH4のTAS命令　新しいプロセッサでは、LL/SC命令を持っているものが多くなっている・スピンロック　スピンロックとは？　　ビジーウェイトによる排他制御機構　　OSを実現するうえで必須である　test-and-set命令によるTest&Setロックの実現　　ロック変数取得で実現される　LL/SC命令によるTest&Setロックの実現　　ロック取得コードを0から1に書き換えることで成功する　test&Setロックの問題点　　コア数が3個以上の場合にロックの取得順がランダムになる　　スタベーションが発生する可能性がある　　スピン中は無駄な負荷がかかってしまう　　　test&test&setロックだと少し改善する・ロック取得順序を制御できるスピンロック　チケットロック　　fetch-and-add命令で番号札をとり、自分の番号になったらロックがとれる　　しかし，ロック取得を途中でやめることが出来ない　キューイングロック　　キューを用いてロックの受け渡しを管理・ロックフリー同期、ウェイトフリー同期　ロックフリー同期　　ロックを使わずに共有データにアクセス可能なアルゴリズム　　1つのプロセッサが死んでも動作可能　ウェイトフリー同期　　ロック取得に上限時間があるアルゴリズム　理論的には両方実現可能だが，複雑なシステムでは効率が悪い -------------------------------------- ・以下メモリオーダリングモデルについて・ストアバッファ　リードが遅延してしまうと後続命令を実行できないが、ライトは遅延しても問題ない　そこで，ライトを遅延させ，先にリードをするためのライト用の格納バッファがストアバッファ・ストアバッファの振る舞い　シングルプロセッサでは問題ないが，マルチプロセッサでは問題がある　問題：順序逆転によって同時実行の条件分で問題が発生する場合がある・メモリオーダリングモデル　アウトオブオーダ実行を行うプロセッサではメモリアクセスの順序を緩めると高速化できる可能性がある　メモリオードリアングモデルとはメモリアクセスの順序を入れ替える　種類　　Sequential Consistency(Strong Ordering) Total Store Ordering Partial Store Ordering Weak Ordering 　実際のプロセッサ　　SH-4AはSCを採用　　ARMはWOを採用　　IA32ではTSOに類似のものを採用　　PowerPCはWOを採用・メモリバリア命令　メモリアクセス順序が入れ替わると困る場合に入れ替えないようにするための命令　ARMでは2種類　　DSB, DMB 　ロック時にはメモリバリア命令が必要となる ---------------------------------- ・以下RTOSと並列コンパイラについて　時間も少なかったため急ぎ足で説明された・RTOSと並列プログラミングの位置づけ　RTOSとは一つまたは複数のコアで、複数の処理を並列実行するOS 　並列プログラミングと並列コンパイラ　　一つの処理を複数のコアで動作するようにプログラムを作成すること・Toppers/FMPカーネル　タスクを移動させ，負荷分散が可能・並列コンパイラ　ポインタがあるとコンパイルが不可能・並列プログラミング環境　OpenMP コンパイラでは判断が難しいものを手動でヒントを与えて並列化・最後にマルチコア研究開発へのお誘い　マルチコアプログラミングはますます重要になっていることを本日説明した　　低消費エネルギー化などが注目されている ---------- ○質疑応答＜質問者＞メモリオーダリングモデルにおいてマルチコア環境に限らずシングルコア環境でもプリエンプションによって命令入れ替えによる問題が起こるのではないか？＜回答＞通常は数命令での入れ替えなので，タスク間で命令入れ替えが起こることはない． -------- ■まとめ　まず，マルチコアプロセッサの必要性や種類の説明から行われ，コヒーレントキャッシュ，アトミック命令，スピンロックといったマルチコアプロセッサ上でプログラムを作成する上で知っておくべきハードウェア知識について解説された．　プログラミングなどのソフトウェア知識は今回時間が無かったためRTOSや並列コンパイラなどの軽い紹介に止まった。