KLICにおけるゴール・スケジューリング最適化 （コンパイル技術および一般）

• Item type: SIG Technical Reports(1)
• 公開日: 1996-10-31
• タイトル: KLICにおけるゴール・スケジューリング最適化 （コンパイル技術および一般）
• タイトル / 言語: en
• タイトル: The Optimization of Goal Scheduling on KLIC
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学大学院工学研究科
• 著者所属: 京都大学大学院工学研究科
• 著者所属: 京都大学大学院工学研究科
• 著者所属: 京都大学大学院工学研究科
• 著者所属: 京都大学大学院工学研究科
• 著者所属: 京都大学大学院工学研究科
• 著者名: 伊川, 雅彦; 大野, 和彦; 五島, 正裕; 森, 眞一郎; 中島, 浩; 富田, 眞治
• 著者名(英): Masahiko, Ikawa; Kazuhiko, Ohno; Masahiro, Goshima; Shin-Ichiro, Mori; Hiroshi, Nakashima; Shinji, Tomita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 並列論理型言語KL1では、一つ一つのゴールが並行実行の単位であるため、その細粒度の並行性制御に伴うオーバヘッドが速度低下を引き起こしている。そこで本研究では、逐次実行が最適であるようなシーケンスを並行実行の単位とする最適化手法を提案する。本手法では、KL1プログラムを静的に解析し、半順序の依存関係がなりたつゴールの集合を求める。これを用いて、プログラムをスレッドと呼ぶ逐次実行が最適なゴール系列に分割する。スレッド内は逐次実行を行うように静的にスケジューリングされ、各々のスレッドは並行実行の単位として動的にスケジュールされる。一方、実行時の並列性の低下を最小限にとどめるため、要求されたデータを生成するスレッドを優先的にスケジュールするような動的なスケジューリング機構を導入する。この最適化をICOTで開発されたKLl処理系KLIC上に実装し、簡単なプログラムで性能評価を行ったところ、実行速度で約1．7倍の速度向上が達成された。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the conventional run-time system for the parallel logic programming language KL1, its fine-grained concurrency control frequently casues unnecessary goal switching which degrades its execution perfromance. We propose an optimization method to reduce the number of goal switching. In this method, we analyse the data dependency among goals to find a group of goals, named thread. A thread consists of the goals which are executed in a predefined order and are free from deadlock caused by mutual data dependency. Thus this threading reduces not only the number of goal switching but also the overhead on the switching owing to the static scheduling. On the dynamic scheduling of threads, we give a priority to each thread so that a generator thread of a request data is scheduled prior to other threads. Evaluation results show that we achieved l.7 fold speedup by this optimization.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1996, 号 107(1996-PRO-010), p. 43-48, 発行日 1996-10-31
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会