KLICにおけるゴール・スケジューリング最適化  [in Japanese] The Optimization of Goal Scheduling on KLIC  [in Japanese]

Search this Article

Author(s)

Abstract

並列論理型言語KL1では、ーつ一つのゴールが並行実行の単位であるため、その細粒度の並行性制御に伴うオーバヘッドが速度低下を引き起こしている。そこで本研究では、逐次実行が最適であるようなシーケンスを並行実行の単位とする最適化手法を提案する。本手法では、KL1プログラムを静的に解析し、半順序の依存関係がなりたつゴールの集合を求める。これを用いて、プログラムをスレッドと呼ぶ逐次実行が最適なゴール系列に分割する。スレッド内は逐次実行を行うように静的にスケジューリングされ、各々のスレッドは並行実行の単位として動的にスケジュールされる。ー方、実行時の並列性の低下を最小限にとどめるため、要求されたデータを生成するスレッドを優先的にスケジュールするような動的なスケジューリング機構を導入する。この最適化をICOTで開発されたKL1処理系KLIC上に実装し、簡単なプログラムで性能評価を行ったところ、実行速度で約1.7倍の速度向上が達成された。

In the conventional run-time system for the parallel logic programming language KLl, its fine-grained concurrency control frequently casues unnecessary goal switching which degrades its execution performance. 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 1.7 fold speedup by this optimization.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 96(107), 43-48, 1996-10-31

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110002929559
  • NII NACSIS-CAT ID (NCID)
    AN10485570
  • Text Lang
    JPN
  • Data Source
    NII-ELS 
Page Top