動的リコンフィギャラブルプロセッサへの時間制約付き機能モジュール群分割アルゴリズムの検討  [in Japanese] A Context Assignment Algorithm for Functional Modules with Timing Constraints on Dynamic Reconfigurable Processor  [in Japanese]

Search this Article

Author(s)

    • 木谷 友哉 KITANI Tomoya
    • 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology
    • 中橋 亮 NAKAHASHI Ryo
    • 大阪大学 大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University
    • 安本 慶一 YASUMOTO Keiichi
    • 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology

Abstract

本稿では,マルチコンテキスト型動的再構成可能プロセッサへ時間制約を持つ実時間システムの機能モジュール群を分割し割り当てるためのアルゴリズムについて述べる.対象とするシステムを,時間制約を持つタスクグラフで表現し,それぞれのタスクをコンテキストに割り当てることでシステムの分割を実現する.本間題をコンテキストの最大サイズを最小化する整数線形計画問題(ILP)として定式化を行った.その際,解の品質を落とすことなくILP問題にするための様々な制約を考案した.また,大規模なタスク割当問題に対処できるよう,二段階のヒューリスティックアルゴリズムを考案し,いくつかの例題に適応した結果,最適解の1.1から1.3倍程度のサイズの分割結果を比較的短時間で導出できることが分かった.

In this paper, we formally define a task decomposition problem for multiple functional modules with timing constraints on a multi-context dynamic reconfigurable processor. We model a real-time system as a set of task graphs with timing constraints, and decompose their tasks by assigning each task to a suitable context of the processor. We formulate the task decomposition problem as an integer linear programming problem. In order to treat large sized decomposition problems, we propose a heuristic algorithm. We show that the proposed heuristic algorithm derives quasi-optical decomposition results for large sized examples in short time.

Journal

  • IEICE technical report

    IEICE technical report 106(604), 1-6, 2007-03-16

    The Institute of Electronics, Information and Communication Engineers

References:  7

Codes

  • NII Article ID (NAID)
    110006249928
  • NII NACSIS-CAT ID (NCID)
    AA11645397
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    8703889
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top