Communication Strategies for Shared-Bus Embedded Multiprocessors

This paper explores the problem of efficiently ordering inter-processor communication operations in both statically and dynamically-scheduled multiprocessors for iterative dataflow graphs with probabilistic execution times. In most digital signal processing applications, the throughput of the system is significantly affected by communication costs. We explic-itly model these costs within an effective graph-theoretic analysis framework. We show that ordered transaction sched-ules can significantly outperform both self-timed schedules and dynamic schedules for moderate task execution time variability. As the task execution time variability increases, we show that first self-timed and then dynamic scheduling policies are preferred. We perform an extensive experimen-tal comparison on both real and simulated benchmarks to gauge the effect of synchronization and communication over-head costs on these crossover points