Cache-Conscious Scheduling of Streaming Applications

This paper considers the problem of scheduling streaming applications on uniprocessors in order to minimize the num-ber of cache-misses. Streaming applications are represented as a directed graph (or multigraph), where nodes are com-putation modules and edges are channels. When a mod-ule fires, it consumes some data-items from its input chan-nels and produces some items on its output channels. In addition, each module may have some state (either code or data) which represents the memory locations that must be loaded into cache in order to execute the module. We con-sider synchronous dataflow graphs where the input and output rates of modules are known in advance and do not change during execution. We also assume that the state size of modules is known in advance