Eryk Laskowski

Critical reconfiguration points heuristic in system with redundant communication resources

939

Abstract

Look-ahead dynamic inter-processor connection reconfiguration is a multi-processor architectural model, which has been proposed to eliminate connection reconfiguration time overheads. It consists in preparing link connections in advance in parallel with program execution in some redundant communication resources. An application program is partitioned into sections and link connections are prepared for the next program sections while previous sections are executed. Parallel program structuring in such a kind of environment incorporates task scheduling and graph partitioning problem. This paper presents scheduling algorithm in look-ahead dynamically reconfigurable multi-processor systems and the new fast heuristics of program graph partitioning into sections. The presented graph partitioning algorithm is supported by critical reconfiguration points heuristic, which is based on the links reconfiguration precedence analysis.

Keywords : task scheduling, links reconfiguration, graph partitioning.