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