Menu
Reconfigurable parallel computers provide a number of choices of algorithm or architecture configurations to execute a task. This paper introduces and discusses the problem of allocating configurations to nodes of a task precedence graph, where each node represents a subtask. Each subtask can be executed on one of a number of distinct configurations and one of these choices must be assigned to it. We are given the execution time on a configuration, and the reconfiguration time between any allocatable pair of configurations of related subtasks. The objective is to assign a configuration for each subtask such that the overall completion time of the entire task is minimized. This paper provides a graph theoretic formulation for this configuration assignment problem, and shows that it is NP-hard even if the maximum degree of the precedence graph is at most 3 and the number of choices for each subtask is at most 2. The problem is shown to be solvable when the maximum degree of the precedence graph is 2, thus closing the gap between the P and NP cases in terms of the degree of the graph. We then present efficient polynomial time algorithms to find the optimal assignment for two special cases of precedence graphs—(1) trees, and (2) series-parallel graphs.