科学技術振興調整費
若手任期付研究員支援
組込みアーキテクチャ協調型実時間 OS
研究期間：平成１３年度～
平成 15 年 6 月
北陸先端科学技術大学院大学
田中 清史
中間成果報告書
研究計画の概要 p.1 研究成果の概要 p.3 研究成果の詳細報告 1. 動的スケジューリング方式に関する研究 p.5 2. μITRON 仕様の API の実装 p.7 3. 試作 LSI における OS 機能の検証 p.9 引用文献・成果の発表 p.11
研究計画の概要
■
研究の趣旨・目的
多くの組込みシステムにおいて、機械／機器を制御するという意味合いから、汎用システム以上にリアルタイム性が求め られる傾向にある。リアルタイム処理は基本ソフトウェア（OS）側のタスクスケジューリングに大きく依存するが、さらに制御 CPU が外部からの個々の要求へ高速なレスポンスを達成することにより、リアルタイム処理における制約時間に余裕を持た せることが可能となる。組込みシステムにおける制御 CPU は、機器／周辺回路からの割込みにより要求に応答するのが通 常であり、リアルタイム処理の実現のためにはこの割込みに対する高速な応答機構が求められる。 本研究では上記の要求に応えるべく、組込みシステムにおけるリアルタイム制御を支援するプロセッサアーキテクチャに 基づくプロセッサコアを開発してきた。本プロセッサコアは、割込みに対する高速な応答を実現するために、組込み用プロ セッサでは過去に例のないマルチコンテクストアーキテクチャを割込みコンテクストに応用し、また専用命令からの制御によ るキャッシュ一貫性機構を持つことにより低コスト方式でありながら高速な実行を達成する。本プロセッサコアは組込みプロ セッサとしての高速化機構を特別な命令の実行によって実現しているため、プログラマが機構を有効に利用するためには、 標準化されたインタフェースが必要不可欠である。本研究では、組込みシステムにおいて標準化された仕様であるμ ITRON4.0 に基づく実時間オペレーティングシステムを研究開発する。μITRON はハードウェアに対する過度の仮想化を 避け、リアルタイム性を実現するためにハードウェア性能を最大限発揮する実装を行うことを可能としている。このことから、 μITRON のインタフェース仕様に従うことで、システムプログラマの負担を増加させることなく新しいプロセッサアーキテクチ ャの導入が可能であり、本プロセッサアーキテクチャの高速化機構を十分に利用可能となる。 今後組込みシステムの用途が巨大化および複雑化していくに従い、低コスト／低消費電力の制約を満たしつつ十分な パフォーマンスを持った組込みシステムが必要不可欠であることから、組込みハードウェアの高速化機構を最大限に活用 するオペレーティングシステムを研究開発することが本研究の目的である。■
研究計画の概要
本研究ではまず、リアルタイム処理を達成するための鍵であるスケジューリング方式を検討し確立／実装してきた。さらに API によるリアルタイム処理支援機構の呼び出し方式を確立し、実時間オペレーティングシステムとして実装する。同時に 実際にリアルタイム処理支援型組込み用プロセッサを設計および LSI として試作し、それを用いた評価システムを開発し、 開発したオペレーティングシステムの評価を行う。各項目は以下の通りである。 １．動的スケジューリング方式に関する研究 従来の組込み OS では静的優先度のみでタスクの実行順序を決定していたのに対し、タスクの締切時刻までの残り 時間を考慮した動的優先度を計算し、それを利用したスケジューリング方式を確立する。また、マルチコンテクストア ーキテクチャの機能を活かしてタスク切替の高速化を図る。 ２．μITRON 仕様の API の実装 スケジューリング機能およびメッセージボックスやメッセージバッファ等の OS 機能を、プロセッサの機構を利用し、か つμITRON のインタフェースに従った API として実装する。 ３．LSI の試作および OS 機能の検証 軽量ハードウェアによる高速化機構を持つプロセッサを実際の LSI として実現し、開発した組込み OS を LSI 上で動 作させ、機能および有効性の検証を行う。■
研究実施計画及び所要経費
（単位：百万円） 所要経費 研究項目 １３年度 １４年度 合計 １．動的スケジューリング方式に 関する研究 (1)適応型動的スケジューリン グ法の提案と評価 ２．μITRON 仕様の API の実装 ３．試作LSI における OS 機能 の検証 (1)CPU コアの論理設計 (2)CPU コアの機能検証 (3)LSI 試作 (4)評価システム開発と検証 6.0 6.0 8.0 8.0 6.0 6.0 12.0 9.0 3.0 12.0 12.0 20.0 17.0 3.0 所要経費（合計） （間接経費を含む） １４ １８ ３２研究成果の概要
■
研究成果の概要
従来の組込み用リアルタイム OS ではシステム稼動前に決定された静的優先度あるいは最悪実行時間のみでスケジュー リングが行われていたのに対し、実行タスクの動的要因（予測実行時間、デッドラインまでの余裕時間）および周期タスクの 周期を考慮し、スケジューリングミス（デッドラインオーバー）タスクの数を削減する適応型動的スケジューリング方式を提案 した。本方式では、タスクの実行は実行回により実行パスの変化およびキャッシュミスなどの要因により所要時間が異なるこ とに着目し、実行毎に過去に使用した予測実行時間と最後に費やした実行時間との加重平均をとることにより、予測実行 時間を更新する。さらに、タスクには静的優先度が割り当てられるが、システム稼動時の各タスクのデッドラインまでの余裕 時間、すなわちデッドラインまでの時間から予測実行時間を引いた値を考慮して動的に実行優先度を変更する方式を提 案した。これらの方式を、本研究で購入したワークステーション上でタスクスケジューリングシミュレータを開発し、多種・多数 のタスクセットに対してシミュレーションを行った結果、予測実行時間と動的優先度の更新のための計算オーバヘッドを導 入した場合でも、従来の方式においてスケジューリングミスするタスクのうちの 83％～95％のタスクのミスを回避することがで きることを示した。 本研究がターゲットとしている組込みアーキテクチャを実現するプロセッサの論理設計をハードウェア記述言語（ＶＨＤ Ｌ）により行った。設計には本研究で購入したワークステーション、回路シミュレータ、および論理合成ツールを使用した。本 プロセッサは実行パイプライン、キャッシュ、MMU などの従来の組込み CPU が持つ機能を全て有し、さらに高速割込み応 答のためのマルチコンテクストアーキテクチャを実現している。また、ソフトウェア開発効率向上のため、既存の SPARC 命令 セットアーキテクチャにしたがった。14 年度までに回路の記述および論理シミュレーションによるバグ修正を行い、中規模の C 言語プログラムをコンパイルしたバイナリが論理シミュレーション上で正しく動作することを確認した。また、キャッシュを除 去した構成を FPGA を使用して実際に動作させ、正常動作を確認した。今後は動作周波数の向上のための回路の最適化 を行い、実際に試作 LSI として実現する予定である。■
波及効果、発展方向、改善点等
近年ハードウェアシステムの設計および開発において、設計 CAD ツールの発達に伴いシステムをモジュールに分割し て設計する傾向にある。この際、過去の設計によるモジュールの再利用がシステムの開発期間の短縮に有効である。本研 究は、組込みシステムにおいて最も共通化が期待できる制御用 CPU コアおよびその CPU 上で実行されるオペレーティン グシステムをターゲットとしたものであり、この部分をモジュール化することにより多種多様の組込みシステムへの適用が期 待できる。また、研究開発したコアおよび OS をオープンフリーにすることにより、これまで GNU や Linux などがソフトウェア の分野で達成してきたことと同じ効果を組込みシステム産業において達成することを目標とする。この際、コアの命令セット に既存の RISC アーキテクチャの命令セットを採用したのは、既存のコンパイラやアセンブラが使用可能となるため、これに よりスムーズな普及を期待できることに起因する。また、μITRON 仕様の採用についても同様に、世界の組込みシステム開 発をリードする日本国内で最も使用されていることが理由である。 将来は汎用システムにも部分的に FPGA などの再構成可能素子が組み込まれ、アプリケーションに特化したハードウェア 機構をユーザが組み込むことが可能となり、組込みシステムの用途が大きく広がることが予想される。このことから、本研究 の成果が将来の組込みシステムに向けた中心的な役割を果たすことが期待できる。 現状の設計では、CPU コアにおける内臓キャッシュなどのハードウェア資源のサイズは固定であり、改善点として将来的 にはこれを可変とすることで、開発するシステムの計算能力と消費電力・サイズとのトレードオフを図ることが挙げられる。ま た、OS の API 実装においてプログラムインタフェース部分とハードウェア制御コードとが混在しているため、これを切り離す ことにより、OS 仕様のバージョンアップへ対応を容易にすることが挙げられる。■
研究成果の発表状況
（1） 研究発表件数 原著論文による発表 左記以外の誌上発表 口頭発表 合 計 国 内 0 件 3 件 0 件 3 件 国 際 0 件 0 件 0 件 0 件 合 計 0 件 3 件 0 件 3 件 （2） 特許等出願件数 合計 0 件 （うち国内 0 件、国外 0 件） （3）受賞等 0 件 （うち国内 0 件、国外 0 件） （4）主要雑誌への研究成果発表 Journal Impact Factor1. 動的スケジューリング方式に関する研究
北陸先端科学技術大学院大学 田中 清史■
要 約
従来のμITRON 等の組込み OS ではシステム稼動前に各タスクに対して設定された静的優先度のみに基づきタスクの 実行順序を決定していたのに対し、システム稼動時のタスクの締切時刻（デッドライン）までの残り時間と、周期タスクの周期 の値を考慮した動的優先度を計算し、それを利用したスケジューリング方式を確立する。ここでタスクの実行回毎に次回の 実行時のための予測実行時間を修正し、残り時間の算出時にこれを利用する。また、マルチコンテクストアーキテクチャの 機能を活かしてタスク切替えの高速化を図る。■
目 的
リアルタイム OS において、タスクスケジューリング方式の選択がリアルタイム処理の達成に大きく影響を及ぼす。従来の 静的優先度方式のスケジューリングでは、システム開発者あるいはアプリケーション開発者が指定した静的優先度を絶対 的な指標としてタスクの実行順序を決定するが、この場合優先度の低いタスクがデッドラインオーバーを起こす傾向がある。 システムの大局的な実行状況を見れば、静的優先度は低いがデッドラインが迫っているタスクを先行実行することにより、ト ータルのデッドラインミス数を減少させることが可能であることに着目し、各タスクのデッドラインまでの余裕時間（および周 期タスクの場合は周期）にしたがって修正した優先度（動的優先度）を使用したスケジューリング方式を確立することを目的 とした。また、タスク起動要求は割込み処理として発生するため、高速割込み応答が可能なマルチコンテクストプロセッサを ターゲットとし、タスクスケジューリングルーチンを高速化することを目的とした。■
研究方法
提案した動的優先度の計算手順として、1) 初回実行時のための予測実行時間の算出、2) 各実行回における予測実行 時間の更新、3) 予測実行時間を使用して余裕時間を求め、これにより動的優先度を計算することが挙げられる。1) につ いて、計算時間の短縮のために、従来の最悪実行時間の見積り方法とは異なり、プログラムの実行命令数とキャッシュの空 間的局所性のみを考慮した簡略化された過大見積り方法を提案し、実装した。この見積り方法の適用可能性の評価のた めに、シミュレーションにより実際の実行に要するサイクル数と比較した。2) について、各実行回終了時に、前回までの予 測実行時間と当該実行回の所用時間との加重平均をとり、これを次回の予測実行時間とする。この加重平均に関して様々 な係数を設定し、シミュレーションによりデッドラインオーバー回避の効果を測定した。3) について、余裕時間の逆数に係 数を掛けたもの（同様に周期の逆数に係数を掛けたもの）を静的優先度に加算することにより動的優先度を算出する方法 をとるが、様々な係数を設定しシミュレーションにより効果を評価した。マルチコンテクストアーキテクチャの利用による高速 化については、今後スケジューリングルーチンをマルチコンテクストアーキテクチャ用に拡張し、拡張しないものとスケジュ ーリング実行時間を比較することにより評価を行う。■
研究成果
上記 1) に関して、シミュレーションにより簡略化された過大見積り方式が実際の所要時間に対して平均して 2 倍弱となる精度であると判断した。2) に関して、加重平均の係数として 0.6～0.8 程度（前回までの予測実行時間の割合）が最もデッド ラインオーバーを削減することがシミュレーションにより確認された。3) に関しては、スケジューリング時に実際に逆数を計 算するのはオーバヘッドが大きいため、余裕時間をインデックスとする優先度更新幅の表を参照する方式を提案した。シミ ュレーションにより、最大更新幅を 16 とする表を構成することにより、デッドラインオーバーを十分に削減可能であることが確 認された。以上の方式を組み合わせることにより、多種・多数のタスクセットに対してシミュレーションを行った結果、従来の 静的優先度方式においてデッドラインオーバーするタスクのうちの 83％～95％のタスクのデッドラインオーバーを回避する ことができることを示した。
■
考 察
シミュレーション結果から、静的優先度による実行順序を動的要因により変更することにより、大多数のデッドラインオー バーを回避することが可能であり、またデッドラインオーバーしたタスクの優先度の平均を調べた結果、静的優先度法に対 してほぼ変わらない結果となった。これは、実行順序を変更したことによってより静的優先度の高い、すなわちより重要なタ スクの実行が失敗する傾向がないことを示している。以上から、本方式は十分に適用可能性があると考えられる。 本評価では予測実行時間と動的優先度の更新のための計算オーバヘッドを大雑把に設定したが、今後は実際のスケジ ューリングルーチンを解析し、オーバヘッドの見積りの改善を行う予定である。2. μITRON 仕様の API の実装
北陸先端科学技術大学院大学 田中 清史■
要 約
標準化されたインタフェースであるμITRON 仕様 API に従ったオペレーティングシステムを研究開発する。本研究にお ける実装では、μITRON の実装依存な部分に対して独自の組込み CPU アーキテクチャの高速化機構をサービスコールレ ベルで利用する。すなわち各種サービスコール内で、キャッシュロック機構、マルチコンテクスト間データ移動命令、データ キャッシュ明示的（DMA 高速化）制御機構、データプリフェッチ機構、割込みレベル制御命令を利用して高速実行を支援 する。API 実装としはて 15 年度以降に行う予定である。■
目 的
組込みシステム開発分野において、プログラミングの容易性を考慮すると、標準化されたインタフェースに従ったオペレ ーティングシステムを提供することが重要である。この観点から本研究で研究開発する OS は現在国内で最も多く使用され ていると言われているμITRON 標準仕様を採用する。既に多数存在するμITRON 実装の OS と異なる点としては、本研究 における実装は独自の組込み CPU アーキテクチャの高速化機構をサービスコールレベルで利用する点である。すなわち 実装依存の各種サービスコール内で、キャッシュロック機構、マルチコンテクスト間データ移動命令、データキャッシュ明示 的（DMA 高速化）制御機構、データプリフェッチ機構、および割込みレベル制御命令を利用して高速実行を支援する。■
研究方法
スケジューリング機能およびメッセージボックス、メッセージバッファ等の OS 機能を、μITRON のインタフェースに従った API を持つルーチンとして実装する。プロセッサアーキテクチャの高速化機構のための命令を各サービスコールルーチン 内に埋め込む実装を行う。高速化の例として、割込みサービスルーチンを起動する際のオーバヘッドを軽減するために、 割込みハンドラの出入り口処理と割込みハンドラを一体化する方法や、割込みハンドラ内にサービスルーチンをインライン 展開する方法が挙げられる。実装するサービスコールのデバッグのために、簡略化されたルーチン実行シミュレータを作成 して、これを用いる。厳密な評価は、後述する試作 LSI と評価システムにより行う予定である。■
研究成果
成果としては 15 年度以降に行われるμITRON 仕様の API 実装および評価が待たれる。OS 実装時に主な特徴として使 用されるプロセッサの高速化機構としては、キャッシュロック機構、マルチコンテクスト間データ移動命令、データキャッシュ 明示的（DMA 高速化）制御機構、データプリフェッチ機構、割込みレベル制御命令を（後述する）ハードウェア回路として実 装した。このうち、評価プログラムの実行に対してデータキャッシュ明示的制御機構とデータプリフェッチ機構を組み合わせ た場合の効果を回路シミュレーションにより予備評価した結果、CPU サイクルで 141 サイクル削減可能なことが示された。
ある 141 サイクルの削減は、制御系の組込みシステムでは高速割込み応答が重要であることを考慮すると十分に貢献でき る機構であると考えられる。他の高速化機構と合わせて OS のサービスコールに組み込むことにより、高速組込みアーキテ クチャ協調型 OS が実現されることが期待できる。
3. 試作 LSI における OS 機能の検証
北陸先端科学技術大学院大学 田中 清史■
要 約
組込みシステム開発において、開発期間を短縮するために最も共通化した構成要素である CPU コアを研究開発し、オ ープンかつフリーとして配布することを目的とする。本 CPU コアは割込み処理のためのマルチコンテクストアーキテクチャを 採用し、かつリアルタイム処理を支援する高速化機構（キャッシュロック機構、マルチコンテクスト間データ移動命令、データ キャッシュ明示的（DMA 高速化）制御機構、データプリフェッチ機構、割込みレベル制御命令）を持つ。本 CPU コアを LSI と して試作し、併せて研究開発するリアルタイム OS の評価プラットフォームとして使用する。■
目 的
組込みシステムにおいて ASIC などのチップを設計・開発する際に、アプリケーションの機能を実現する回路および周辺回路を 独自設計し、その制御回路はベンダが提供する IP（知的所有権）などの既存の CPU チップあるいは CPU コアを使用することにより、 開発期間を短縮することが可能である。制御用 CPU は ASIC の設計で最も共通化した構成要素であり、インタフェースが柔軟で、 再利用可能なCPUコアがフリーかつオープンソースコードで利用可能であることが求められる。このことから、本研究ではオープン かつフリーのプロセッサコアを研究開発する。本 CPU コアは組込み用途としては前例のない割込み処理のためのマルチコンテク ストアーキテクチャを採用し、かつリアルタイム処理を支援する高速化機構（キャッシュロック機構、マルチコンテクスト間データ移 動命令、データキャッシュ明示的（DMA 高速化）制御機構、データプリフェッチ機構、割込みレベル制御命令）を持つ。
■
研究方法
本研究がターゲットとしている組込みアーキテクチャを実現するプロセッサコアの論理設計をハードウェア記述言語である ＶＨＤＬにより行った。設計には本研究で購入したワークステーション、回路シミュレーター、および論理合成ツールを使用し た。本プロセッサはソフトウェア開発効率のため、既存の SPARC 命令セットアーキテクチャにしたがった。また各種高速化機 構を起動する命令は SPARC の実装依存命令を利用しているため、プログラム開発は既存のコンパイラ・アセンブラにより可 能となっている。今後は動作周波数の向上のための回路の最適化を行い、実際に試作 LSI として実現する予定である。■
研究成果
成果としては 15 年度以降に行われる LSI の試作およびその上で実装される OS の評価が待たれる。14 年度までに主な 実行ユニットおよび、キャッシュロック機構、マルチコンテクスト間データ移動命令、データキャッシュ明示的（DMA 高速化） 制御機構、データプリフェッチ機構、割込みレベル制御命令の回路の記述および論理シミュレーションによるバグ修正を行 い、中規模の C 言語プログラムをコンパイルしたバイナリが正しく動作することを確認した。回路シミュレーションでマルチコ ンテクストアーキテクチャの予備評価を行った結果、多重割込み処理に対して 4 つのレジスタセットによるコンテクスト切替 えにより実行サイクルを 1775 サイクルから 856 サイクルへ削減した。■
考 察
15 年度以降の実装および評価により本研究の最終成果が示される。マルチコンテクストアーキテクチャの予備評価で得た結果 である 919 サイクルの削減は、前述の高速化機構の効果と同様、制御系の組込みシステムでは高速割込み応答が重要であること を考慮すると十分に貢献できるアーキテクチャであると考えられる。現在の回路記述の論理合成後の情報としては 0.25μm ルー ルで 100MHz 弱の動作周波数見積りであるため、更なる高速化の実現のために実行パイプラインの多段化を計画している。
