Skip to main content

Distance: a New Metric for Controlling Granularity for Parallel Execution

Shen, Kish and Costa, Vitor Santos and King, Andy (1998) Distance: a New Metric for Controlling Granularity for Parallel Execution. In: Jaffar, Joxan, ed. Proceedings of the 1998 Joint International Conference and Symposium on Logic Programming. Logic Programming . MIT Press, Cambridge, Massachusetts, USA, pp. 85-99. ISBN 0-262-60031-5. (KAR id:21639)

Language: English
Download (156kB) Preview
Official URL


Granularity control is a method to improve parallel execution performance by limiting excessive parallelism. The general idea is that if the gain obtained by executing a task in parallel is less than the overheads required to support parallel execution, then the task is better executed sequentially. Traditionally, in logic programming, task size is estimated as the sequential time-complexity of evaluating the task. Tasks are only executed in parallel if task size exceeds a pre-determined threshold. We argue in this paper that the estimation of task complexity, on its own, is not an ideal metric for improving the performance of parallel programs through granularity control. We present a new metric for measuring granularity, based on a notion of emphdistance. We present some initial results with two very simple methods of using this metric for granularity control. We then discuss how more sophisticated granularity control methods can be devised using the new metric.

Item Type: Book section
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Sciences > School of Computing > Theoretical Computing Group
Depositing User: Andy King
Date Deposited: 22 Aug 2009 20:22 UTC
Last Modified: 15 Feb 2020 04:02 UTC
Resource URI: (The current URI for this page, for reference purposes)
King, Andy:
  • Depositors only (login required):


Downloads per month over past year