27. 組み込みシステム最適化に関する知識 I

シラバス: 

1. 科目の概要

 システムの性能を最適化するための方法としてのマルチプロセッサ導入や、リアルタイムシステムの特性を活かした最適化、ソフトウェア最適化や最適化のためのシステム評価方法など、組み込みシステムの最適化に関する様々な技術について解説する。

2. 習得ポイント

 本科目の学習により習得することが期待されるポイントは以下の通り。

3. IT知識体系との対応関係

「27.組み込みシステム最適化に関する知識Ⅰ」とIT知識体系との対応関係は以下の通り。

[シラバス:http://www.ipa.go.jp/software/open/ossc/download/Model_Curriculum_05_27.pdf]

<IT知識体系上の関連部分>

4. OSSモデルカリキュラム固有の知識

 OSSモデルカリキュラム固有の知識として、組み込みシステム開発におけるタスク設計手法と最適化のための評価方法がある。タスク設計の評価やMPUの評価など実践的な内容を扱う。

(網掛け部分はIT知識体系で学習できる知識を示し、それ以外はOSSモデルカリキュラム固有の知識を示している)

I-27-1. マルチプロセッサシステムの種類

マルチプロセッサシステムについて、その基本概念と特徴、利点などを示し、従来からの分類方法であるSISD/SIMD/MISD/MIMDといった種別や、新しい分類方法であるSMP (Symmetric Multi Processor)、クラスタ構成、MPP (Massively Parallel Processor)などを紹介する。

【学習の要点】

* マルチプロセッサシステムでは、処理を一つのCPUではなく、複数のCPUで並列して行う。これにより処理力の向上と耐故障性の向上とを実現する。

* マルチプロセッサの分類として、プロセッサの数とデータを並行処理する方式によるSISD/SIMD/MISD/MIMDの分類が従来から使われている。

* 対称的(Symmetric Multi Processor: SMP)、非対称的(Asymmetric Multi Processor: AMP)といった分類の他、超並列(Massively Parallel Processor:MPP)などの分類が使われる。

図I-27-1. SIMDとMIMD

 

【解説】

1) マルチプロセッサシステム

* マルチプロセッサの分類(Flynnの分類)

- SISD(Single Instruction stream Single Data stream:単一命令単一データフロー)

従来型のコンピュータの処理形式であり、1命令で1つのデータフローを処理する。

- SIMD(Single Instruction stream Multiple Data stream:単一命令複数データフロー)

1命令で1つの配列を処理する。代表例としてベクトルプロセッサがある。

- MISD(Multiple Instruction stream Single Data stream:複数命令単一データフロー)

複数のプロセッサで同じ1つのデータフローの処理を行う。冗長性があり、高度な信頼性を求められる場合にのみ使われる。

- MIMD(Multiple Instruction stream Multiple Data stream:複数命令複数データフロー)

複数の独立したプロセッサが、同時に異なるプログラムを処理する。

* 対称型・非対称型

- 対称マルチプロセッサ(SMP)はMIMDアーキテクチャの例である。一般にSMPでは、同一種類のプロセッサが用いられ、どのプロセッサも他のプロセッサと同じ計算ができる。

- 非対称マルチプロセッサ(AMP)では、複数種類のプロセッサが用いられる。各プロセッサが処理用途に応じた能力を持っている場合が多い。

* 超並列コンピュータ

- MPPでは、複数のマイクロプロセッサを用いて並列処理を行う。高性能な専用プロセッサを使うスーパーコンピュータよりも安価に高速化できる。

I-27-2. マルチプロセッサシステム活用上の留意点、構成例

タスクのスケジューリング、プロセッサ間の同期と通信、ハードウェアの制限など、マルチプロセッサシステムを活用する際に留意すべき事項を説明する。またマルチプロセッサシステムの具体的な構成例を紹介し、その特徴について説明する。

【学習の要点】

* タスクのスケジューリング、プロセッサ間の同期と通信、ハードウェアの制限など、マルチプロセッサシステムを活用する際に留意すべき事項を説明する。またマルチプロセッサシステムの具体的な構成例を紹介し、その特徴について説明する。

* マルチプロセッサシステムを用いることにより、複数事象の制御、タスクのスケジューリング、プロセッサ間の同期・通信について考慮する必要が生じる。

* マルチプロセッサシステムは、汎用CPU2個による小さな構成のものから、数万個のCPUを接続した超並列コンピュータまで幅広く存在する。

図I-27-2. マルチプロセッサの性能低下要因

 

【解説】

1) マルチプロセッサシステムの活用方法

* ロックと相互排除

- マルチプロセッサの環境では、ハードウェアロックが用いられる。

- プログラマは相互排除のため、明示的にロックを利用する必要がある。

* 対称・非対称マルチプロセッサでのプログラミング

- 対称プロセッサのプログラミングの方が非対称プロセッサの場合よりも容易とされる。

- プログラマが理解する必要のあるプロセッサの命令セットが1種類で済む、タスクをどのプロセッサに割り当てるか考慮せずに済む、などの理由による。

2) マルチプロセッサシステムの性能への障壁

直観的にはマルチプロセッサシステムの処理能力の方が、単一プロセッサアーキテクチャの能力よりも優る。しかし、N個のCPUにより処理をすることにより速度がN倍になるわけではない。性能の障壁となる要因は以下の3点が挙げられる。

* 通信

- プロセッサ間、メモリ、入出力間で生じる通信のオーバヘッドは無視できないものとなる。

* 協調

- プロセッサ間で協調して動作するための制御機構が必要になる。

* 競合

- 共有リソースへの同時アクセスによりタスクがアイドル状態にされる。これにより劇的な性能低下を招く。

I-27-3. マルチプロセッサによるシステムの最適化

性能の最適化方法、CPU高速化、入出力方法に関する工夫、低電力処理など、マルチプロセッサを使用したシステムを最適化する手順や配慮すべき項目ついて解説する。

【学習の要点】

* CPU性能の高速化のためにパイプライン処理を行われる。パイプライン処理により複数の命令が並列して処理されていく。

* ハードウェアによるパイプラインには、命令パイプラインとデータパイプラインがある。

* 並列処理、多段パイプライン、低電圧動作の組み合せによる低電力処理が行われてきた。

図I-27-3. パイプライン処理(命令パイプライン)

 

【解説】

1) パイプライン処理によるCPU 高速化の仕組み

RISCプロセッサでパイプライン処理を利用することにより、1クロックサイクルで命令フェッチ-実行サイクルの全てのステップを実行するのと同等の処理ができる。

* プロセッサが命令をフェッチし実行するサイクルに対してパイプライン処理を行う場合、一般に以下のモデルで説明される。

- 命令フェッチ

- オペコード解析

- オペランドフェッチ

- 命令実行

- 結果格納

* 命令を流れ作業のようにパイプラインを通して実行させることにより、常に5つの命令がパイプラインに含まれることとなる。

2) 低電力処理

* 動作電力は、デバイスの動作を通じて消費される電力のことで、周波数、電圧、負荷に依存する。

* 多段パイプラインによる並列処理でスループットを上げることにより、結果として消費電力を抑制できる。

* マルチプロセッサは動作領域を制限できるため平均消費電力を下げることができる。

I-27-4. リアルタイムシステムの設計と留意点

リアルタイムシステムの設計に必要な要素を解説する。具体的には、モジュール分割、処理分割による最適化、割り込み対応、処理時間・応答時間の見積り、処理待ちキュー設計、デバイスに対する高速応答処理の実装などについて触れる。

【学習の要点】

* リアルタイムシステムの設計手順としては、全体のシステムを複数のモジュールに分割した上で、個々のモジュールに対しタスクの分割をし、その上で共有資源(ファイル、セマフォ、など)の設計を行う。

* タスク分割の指針としては、システム全体で時間的に最も緊急度の高い処理(タイムクリティカル処理)に注目する。タイムクリティカルな処理を中心にタスク分割を進めていく。

図I-27-4. 設計手順の概略

 

【解説】

1) リアルタイムシステム設計

* 一般的なリアルタイムシステムの設計では、システムを実現する機能をタスクまで分割ていく。

- はじめに全体のシステムを複数のモジュールに分割する。それぞれのモジュールは機能に対応して分割される。

- 個々のモジュールの中身をタスクへと分割する。

- 共有リソース配分(ファイル、セマフォ、など)の設計を行う。

* タスク設計に関して絶対的な理論は存在しない。

* リアルタイム性を考慮する場合、割り込みハンドラなどを利用してタイムクリティカルな処理を中心にタスクの優先度を設定していく。

* タスクを起動するイベントは入出力のイベント、周期的なクロックイベント、他のタスクの処理によるイベントがある。こうした起動の要因ごとにタスクを分割することも指針として利用される。

2) デバイスプログラミング

* 割り込みハンドラの処理は、カーネルの設計によって異なる。割り込みが無い場合のみ高い性能を出せるカーネルや、割り込みがあっても極端に性能が落ちないカーネルなど様々である。

* また、カーネルインタフェースの設計によっては、割り込みハンドラからカーネルに対するシステムコールに制限をかける場合もある。

* デバイスドライバは入出力機能を実行する機能をタスクから独立する形で実装したソフトウェアである。

- 組み込み開発においてデバイスドライバを作成する機会はエンタプライズ系に比べて一般に多くなる。

- デバイスドライバはアプリケーションインターフェイスと割り込みハンドラのコンテキストから構成される。

I-27-5. タスク分割による性能向上

リアルタイムソフトウェアを利用したシステムの性能向上、最適化のためのソフトウェア作成方法を解説する。特に適切なタスク分割によるタスクの同期、並行動作の実現など、関連する話題を説明する。

【学習の要点】

* タスク設計の際には、入出力の速度差を解消すること、起動方式によってタスク分割を行うこと、割り込みハンドラとの処理分担を適切に行うことなども指針とされる。

* 入出力ポートの利用は、複数タスクから同時にはできない。そのため、あるタスクがポートを利用している間は、他のタスクからの入出力要求はキューで待機する。

* 並行処理を特定するためのガイドラインでは、「デバイス依存性の特定、イベント依存性の特定、時間依存性の特定(緊急度の度合い)、計算に特化したアクティビティの特定」(出典:Qing Li「リアルタイム組込みOS基礎講座」、翔泳社(2005))などの手順に従う。

図I-27-5. 並列処理を行うべき箇所を特定するガイドライン(出典:Qing Li「リアルタイム組込みOS基礎講座」、翔泳社(2005)に基づき三菱総合研究所が作成)

 

【解説】

1) タスク設計

タスクを適切に分割し、優先度を割り当てることでリアルタイム性を確保することがタスク設計の一つの重要な方針である。

* アウトサイド-インアプローチ

- アプリケーションの分解を行う手法であり、システムの入出力を特定することで、デバイスへのインターフェイスや入出力の関係を矢印で結んだコンテキスト図を記述する。

- コンテキスト図の入出力から潜在的なタスクを図に追加していく。この情報をもとにアプリケーションを分割していく。

- この手法のように、タスク設計の指針として入出力の単位ごとにタスク分割を行うことがしばしば行われる。入出力の速度差をキューによって解消でき効率の良いシステムを作ることができる。

* 並行処理を特定するためのガイドライン

アプリケーション内の処理の並行性を特定するために、定性的なタスク解析手順が存在する。

- デバイス依存性の特定

入出力割り込みの有無、同期非同期かによりタスクの独立性が決定される。

- イベント依存性の特定

イベントを適切に処理するタスク群が必要である。

- 時間依存性の特定(緊急度の度合い)

緊急度の高い順に処理を割り当てることが基本原則となる。

- 計算に特化したアクティビティの特定

入出力処理などCPU時間を多く取る処理がCPUを独占しないように優先度を下げる。

- 機能的な結合の特定

機能的に関係の高い処理を一つのタスクとしてまとめることにより同期と通信のオーバヘッドを避けることができる。

- 特定の目的を提供するタスクの特定

- 逐次的な結合の特定

I-27-6. タスク関連設計によるリアルタイムシステムの最適化

タスク関連設計を中心とした最適化のアプローチについて解説する。タスク関連設計の基本的な考え方と特徴について説明し、さらに、タスク関連図の作成方法、タスク優先順位の決定、起動タイミング、タスク間の同期、排他制御といった項目について説明する。

【学習の要点】

* リアルタイムシステムの最適化のために、タスク関連図を用いた最適化が行われる。

* タスク関連図作成時の留意点としては、タスクの起動関係とタイミング、タスク間の同期とその手段、タスク間のキュー、重要なフラグの更新と参照の関連が挙げられる。

図I-27-6. タスク関連図

 

【解説】

1) タスク関連図の作成

* 一般に、要件定義書を記述した後、外部設計書を記述する。この外部設計書の一部としてタスク関連図がしばしば利用される。

* タスク関連図はリアルタイムシステムの最適化に向いているとされ、詳細設計書への橋渡しとなる。

* 経済産業省の組み込み実態調査によると、米国の組み込み産業では30%程度が利用しているとされる。

* タスク関連図に記載する項目は以下の通り

- タスク番号と優先順位

- タスクの起動関係

- 起動タイミング

- タスク間のキュー

- タスク間の同期と排他制御

- 重要なフラグの更新と参照の関連

I-27-7. リアルタイム処理に対する評価項目と留意点

リアルタイムシステムの性能評価について、全体のパフォーマンス、処理のスループット、全体の優先順位、デバイスドライバの処理方法などの観点からみた評価項目と評価時の留意点を説明する。またタスク分割の設計評価についても解説する。

【学習の要点】

* リアルタイム処理の評価項目としてパフォーマンス、全体の優先順位、デバイスドライバの処理方式がある。

* タスク分割の設計評価として、キューの利用、排他制御、同期の利用に関する評価が考えられる。

図I-27-7. リアルタイム処理の評価項目

 

【解説】

1) 評価項目と留意点

* パフォーマンス

- 頻繁なコンテキストスイッチによるパフォーマンスの低下が起こらないかタスクの切り替え頻度を確認する。

- カーネルによる全体のスケジューリング方式と、アプリケーションの割り込みの頻度といった動作の特徴が合致しているかを確認する。

- パフォーマンス指標の一つとしてスループットが用いられる。スループットは、システムへの入力に対して生成できる出力の比率と定義される。スループットにより、ハードウェアやソフトウェアを含むシステム全体のパフォーマンスを計量することができる。

- システムコール単位でパフォーマンスを計測することもある。

* 全体の優先順位

- プリエンプションの発生タイミング、処理の遅廷などからタスクの優先度を決定し、リアルタイム性を優先した順位付けを行う。

* デバイスドライバの処理方式

- デバイスドライバの動作手順に着目し、シミュレーションモデルや実際の計測によりパフォーマンスを評価し、避けられるボトルネックなどを特定する。例えば割り込みに与える優先度などを検討する。

- デバイスドライバの動作手順は、処理要求待ち、入出力キューの作成、入出力の開始、割り込み処理に際してアプリケーションインターフェイスを起動、入出力の終了、と一般になっている。

2) タスク分割の設計評価

* スケジューラビリティによる分析が、タスクの設計評価の一つとして挙げられる。

* 使用するスケジューリングアルゴリズムに基づいて全てのタスクがリアルタイム性を維持し、かつ最適なプロセッサ利用率を達成できるかを分析する。

* レートモノトニック分析(Rate Monotonic Analysis: RMA)がリアルタイムシステムではよく使われる。

* また、キューイング、排他制御、同期に関してオーバヘッドの大きさを確認することも行われる。

I-27-8. CPUの性能指標と評価方法

CPI (Clock Cycles Per Instruction)、MIPS (Million Instructions Per Second)など、CPUの性能を評価する指標を紹介する。ただし様々なシステムの利用状況においては、これらの指標だけでは不十分であり個別の最適化手法を適用しなければならないことについても言及する。

【学習の要点】

* CPUの評価指標としては、CPU時間(CPI)、単位時間当たりの実行可能命令数(MIPS)、単位時間当たりの実行可能演算数(MFLOPS)、などが使われる。

* SPEC(Standard Performance Evaluation Corporation)の作成する整数演算の性能評価用のSPECintなどはCPUの性能評価ベンチマークとして使われている。

* 組み込みシステム向けのベンチマークとしては、EEMBC (EDN embedded microprocessor benchmark consortium)が有名である。

図I-27-8. CPUの評価手法とベンチマーク

 

【解説】

1) CPU の性能評価

* CPUの性能評価は2)に示す指標を用いて計測される。

2) CPU の性能を示す指標

1種類の測定法のみではCPU性能の1側面しか判断できないため、複数の指標が存在している。

* CPI (Clock cycles per instruction)

- 1クロックあたりに実行可能な命令数

* MIPS (Millions of instructions per second)

- 1秒間あたりの演算数(単位100万回)

* MFLOPS (Millions of floating-point operations per second)

- 単位時間あたりに実行可能な浮動小数点演算数(単位100万回)

3) 標準ベンチマーク

* 客観的な統一指標で性能を比較する必要から、ベンチマークが作られている。

* 1980年代に非営利法人のSPECが作成する標準ベンチマークが有名である。

- SPECベンチマークの結果はSPECmarkと呼ばれ、ベンダ非依存の性能として示される。

- SPECint/SPECfp

整数/浮動小数点演算の性能を調べるベンチマーク

* 組み込み機器向けのベンチマークとしてEEMBC (EDN embedded microprocessor benchmark consortium)がある。

- Automotive, Consumer

自動車、カメラ、携帯電話などの用途のマイクロプロセッサの性能評価

- Java, Networking

携帯電話やPDA用のJ2MEアプリケーションや、ルータなどのネットワーク製品用途のプロセッサの性能評価

4) CPUの性能に悪影響を及ぼすシステム

* 割り込みを多用するシステム

* 受付後に多数のレジスタの退避と復帰をハードウェアで行うシステム

* レジスタを命令で退避するシステム

I-27-9. ソースコード最適化によるシステム性能向上

ソフトウェア最適化によるシステムの性能向上について、基本的な概念と設計方針を解説する。ソフトウェア最適化の基本手段である冗長なコードの排除やループの展開、インライン化、変数のレジスタ割り当てなど個別の手法を紹介し、またソースコードレベルの最適化の手順についても説明する。

【学習の要点】

* ソフトウェア最適化の方法としては、冗長なコードの削除、アルゴリズムの改善、ループ内不変値のくくり出し、インライン化、などの手法が知られている。これらの手法により、メモリの利用効率と、スピードが向上する。

図I-27-9. ソースコード品質の改良によるソフトウェア最適化

 

【解説】

(1)ソフトウェア最適化の方法

ソフトウェアの実行効率を最適化する手法として、言語仕様の活用、プロセッサ特性の活用、コンパイラの拡張機能・最適化機構の利用、などが挙げられる。他にもリンケージエディタによる最適化などが考えられる。

* 冗長なコードの排除

- 冗長なコードは、仕様を変更する際に修正が複数個所に及び、手間がかかることに加え、実行効率に悪影響を及ぼしうる。

* ループ処理の最適化

- ループ内不変値のくくりだし

- ループのマージ

- ループ回数の削減

* 内部変数の最適化

- 関数内部で利用される内部変数(局所変数)で利用される型によって性能に大きな影響がある。

- プロセッサにとって高速に処理ができる型とそうでない型がある。

- 原始型(プリミティブ)の「整数型」「ポインタ型」は高速に処理できるが、「浮動小数点型」はFPU(Floating Point Unit)を搭載していないと高速には処理ができない。

- 集成型・派生型の実行は原始型に比べ遅くなる。

I-27-10. プログラムモジュール配置による最適化

プログラムモジュールの配置方法に係る最適化手法を解説する。プログラムモジュールのメモリへのローディング方法、リンク方式、常駐化など具体的な方法について説明する。

【学習の要点】

* 組み込みシステムの実行プログラムは単一リンクモデルとローディングモデルのどちらかを取る。

* 単一リンクモデルでは、すべてのプログラムをリンカによってひとつの実行可能形式プログラムとした後、ROM化し、実行する。

* ローディングモデルは、外部記憶装置やROMから実行に必要なデータを順次読みだすモデルである。

図I-27-10. 単一リンクモデルとローディングモデル

 

【解説】

1) プログラムと処理

* プログラムのリンク方式について、組み込みシステムの実行プログラムは単一リンクモデルとローディングモデルのどちらかを取る。

- 単一リンクモデルでは、すべてのプログラムをリンカによってひとつの実行可能形式プログラムとした後、ROM化し実行する。

- ローディングモデルは、外部記憶装置やROMから実行に必要なデータを順次読みだすモデルである。

* 常駐と非常駐

- プログラムをRAM上に配置しておく(常駐)ことで、プログラムの起動を高速化することができる。しかし、RAMの容量は無限では無いため、使用頻度の少ないプログラムは非常駐になるように動作させるべきである。

* リユーザブル化

- リユーザブル化とは、一度プログラムを実行した後に再度実行をしても正しく処理できるようにすることを指す。

- メモリに常駐するプログラムはその都度ローディングされる訳ではなく、リユーザブルを損なわない必要がある。この場合、初期値を書き換えないなどの対応が必要になる。