14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06)
Scheduling Programs with Conditional Branches for Look-Ahead Dynamically Reconfigurable Systems
Montb?liard-Sochaux, France
February 15-February 17
ISBN: 0-7695-2513-X
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 interprocessor 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.
Citation:
Eryk Laskowski, Marek Tudruj, "Scheduling Programs with Conditional Branches for Look-Ahead Dynamically Reconfigurable Systems," pdp, pp.211-218, 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06), 2006