Program Scheduling in Look-Ahead Reconfigurable Parallel Systems with Multiple Communication Resources

The paper presents new graph structuring algorithms for look-ahead reconfigurable multi-processor systems. This architectural model is based on preparation of inter-processor link connections in advance in redundant communication resources (i.e. crossbar switches) in parallel with program execution, which enables elimination of connection reconfiguration time overheads. Application programs are partitioned into sections, which are executed using connections prepared in redundant communication resources. Parallel program structuring for execution in such systems incorporates task scheduling and graph partitioning problems. Presented algorithms apply two-phase approach, in which program task scheduling is solved by modified ETF heuristics and, in a second phase, a new iterative clustering heuristics is used for graph partitioning. The experimental results are presented, which compare performance of several graph partitioning heuristics for such environment.