Scheduling programs with conditional branches for look-ahead dynamically reconfigurable systems

The paper presents an extension of task scheduling algorithms for dynamically look-ahead reconfigurable multi-processor systems to account for conditional branches in programs. The target architecture assumes preparing link connections in advance in redundant connection switches in parallel with program execution. It provides time transparency of inter-processor connection setting at program run-time. Application programs are partitioned into sections, which execute using fixed look-ahead prepared connections. Programs are represented by a new graph representation - branching task graph (BTG), which composed including macro-dataflow and control-flow paradigms. The BTG enables extending known up-to-now scheduling algorithms of program graphs with fully static control towards scheduling of graphs data dependent control. The new scheduling algorithm includes branch handling techniques based on detection of mutually-exclusive paths in the graphs and scheduling paths in branches according to their probabilities. The program partitioning into sections uses modified iterative clustering heuristics. An example shows advantages of the proposed method.