区間グラフの最大長指定分割問題について

• Item type: SIG Technical Reports(1)
• 公開日: 2016-06-17
• タイトル: 区間グラフの最大長指定分割問題について
• タイトル / 言語: en
• タイトル: On the Decomposition Problem of Interval Graphs with Maximum Length Constraint
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 金沢工業高等専門学校
• 著者所属: 北陸先端科学技術大学院大学
• 著者名: 井上, 恵介; 金子, 峰雄
• 著者名(英): Keisuke, Inoue; Mineo, Kaneko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では耐放射線性を有するアプリケーション特化型集積回路 (ASIC) の高位設計の研究過程で生じた最適化問題について議論する．自然界に存在する放射線の中で半導体メーカーが問題とする放射線は，アルファ線と中性子線である．これらの放射線はシリコンダイが維持している電位を破壊する．その結果，レジスタが記憶していた論理値が反転し ASIC が誤動作することがある．この問題の対策手法の一つとしてデータスクラビング (data scrubbing) がある．データスクラビングでは，レジスタを検査アクセスした際，訂正可能な 1 ビットエラーのデータが見つかると，訂正回路によって正しいデータに訂正しレジスタに書き戻す．この設計の基礎問題として，演算スケジュール済のデータフローグラフが回路仕様として与えられたとき，どのタイミングでどのレジスタにデータスクラビングを適用すれば訂正回路数最小を保証する耐放射線 ASIC が合成可能であるかという問題があり，区間の最大長指定分割問題として定式化可能である．この問題の入力は複数の区間の集合と最大区間長であり，出力はどの区間をいつ分割するかという分割指定である．最適化目標は，各時刻での分割数の最大値の最小化であり，これはデータスクラビングを実装するハードウェアコストの最小化と等しい．本稿ではこの問題を紹介するとともに，判明しているいくつかの事実について紹介する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-158, 号 19, p. 1-1, 発行日 2016-06-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会