Analytical derivation of traffic patterns in shared memory architectures from Task Graphs

Task Graphs is a commonly used application model in research in computer-aided design tools for design space exploration of embedded systems, including system synthesis, scheduling and application mapping. These design tools need an estimate of the actual communication in the target system caused by the application modelled by the task graph. In this paper, we present a method for analytically deriving the worst-case traffic pattern when a task graph is mapped to a multiprocessor system-on-chip with a shared memory architecture. We describe the additionally needed information besides the dependencies in the task graph in order to derive the traffic pattern. Finally, we construct a simulator that we use to find the actual traffic pattern in a system and compare this to the derived pattern. Results show that our worst-case derivation overestimates the bandwidth by 9% for systems with small caches and between 32% and 52% for systems with large caches.