文献

J-GLOBAL ID：201702243851150495   整理番号：17A0257419

時間制約付き実時間タスクグラフモデルにおけるスケジュール可能性解析アルゴリズムの研究【JST・京大機械翻訳】

The Digraph Real-Time Task Model with Timing Constraints: Schedulability Analysis Revisited

著者 (3件)： Sun Jinghao (School of Information Science and Engineering,Northeastern University) ,  Guan Nan (School of Information Science and Engineering,Northeastern University) ,  Deng Qingxu (School of Information Science and Engineering,Northeastern University)
資料名： Jisuanji Xuebao  (Jisuanji Xuebao)
巻： 39  号： 12  ページ： 2481-2493  発行年： 2016年 
JST資料番号： C2531A  ISSN： 0254-4164  CODEN： JIXUDT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 時間制約付きの実時間タスクグラフ(TCDRT)モデルは時間オートマトンに近い豊富な発現を持っているが,その関連のスケジュール可能性解析(SA)問題は強いNP困難である。現在の研究では,一つの制約の数が定数Kである簡単なモデルに注目している。K-TCDRTは,SA問題におけるグラフ変換の解法に制限される。この間接的方は問題の計算複雑度を制約幅の数倍に増加させる。本論文では,TCDRTモデルにおけるスケジュール可能性解析問題の直接解法を研究し,2つのサブプロセス問題のための新しい理論的結果を提示した。第一に,需要の上限関数(DBF)の計算問題を解決するために,時間制約を考慮した経路要求構造を提案し,新しいアルゴリズムを提案し,その時間複雑性は制約幅に依存しない。第二に,スケジューリング可能性上界Tの限定問題に関して,本論文は,この問題が多項式の時間分解可能解であり,計算複雑度がK指数と関連しないことを証明し,このアルゴリズムの性能が既存の結果と比較して指数関数的に向上することを示した。さらに,この方法は,新しい種類のTCDRTモデルを含んでいる。この種のモデルは,制約数が定数の限界であることを突破し,その解析の困難さもK-TCDRTよりも数倍減少した。Data from the ScienceChina, LCAS. Translated by JST【JST・京大機械翻訳】

シソーラス用語： NP困難 ,  *アルゴリズム ,  多項式 ,  指数関数 ,  計算量 ,  スケジューリング ,  *制約条件
準シソーラス用語： 上界 ,  複雑性 ,  グラフ変換 ,  時間付きオートマトン ,  *タスクグラフ ,  *解析アルゴリズム ,  *実時間 ,  *時間制約 , 【Automatic Indexing@JST】

著者キーワード (5件)： timing constraints ,  digraph real-time tasks ,  schedulability analysis ,  demand bound function ,  dynamic programming

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (8件)： 制約 ,  実時間 ,  タスクグラフ ,  モデル ,  スケジュール ,  可能性 ,  解析アルゴリズム ,  研究