Program Graph Scheduling for SMP Clusters with Communication on-the-Fly Based on Extended DS Approach

This paper deals with a problem of program graph scheduling for a parallel with dynamic processor switching and data transfers on the fly. The architecture of such system is based on a concept of SMP clusters implemented in network-on-chip (NoC) modules, which connect processors to shared memory modules. Processors can by dynamically switched between clusters at runtime, allowing dynamic distribution of computation and communication between processor clusters. The collective communication capabilities of an intra-cluster communication network allow using data reads on the fly for effective intra-cluster data transfers. It consists in parallel readings of data which are written or read to/from a memory module through an internal data exchange network by many processors in this cluster. The paper presents a two-level scheduling algorithm based on Extended Dominant Sequence. The higher-level part of the algorithm defines distribution of program graph nodes between NoC modules. The lower-level part determines the scheduling of the program graph for a given distribution of program nodes on processors and SMP clusters.