xSTreamC filters mapping to execution resources


An xSTreamC program describe an application as a set of filters, in order to run such an application onto a target plaform composed of a number of interconnected execution units (or Processing Elements), a mapping specification or policy must be applied.

Naively the mapping consist of the processes of selecting what logical execution entity (filter) should execute on a given physical execution context. As the xSTreamC language allow high level program transformation such as filter fusion, this phase also has to select which filters should be merged (fuxed) to make a better use of both the communication infrastructure and the execution resources.

You can find here the an internal brainstorming on ways to specify a mapping that lead to the current model supported by the compiler.

Definitions and concepts


We termed a node, the physical (or simulated) processing element couled with its communication channels, and a filter the logical program entity that can be assigned to it (more that one filter could be assigned to a single node for certain target platofms, e.g. the ones supporting multithreading). The goal of a mapping phase is to assign a node for each filter.

If this is not possible (for any reason), the mapping is invalid.

A node is not necessarily a processor. It can be only a hardware (maybe software in the future) thread of a processor, or a hardware block (in the latter the filter needs to be described as a black-box, whose filter high-level code provides only the behavior).

Merging (filter fusion)

If a mapping attributes the same node to several filters, a merge between them will be attempted. If this merge fails, the mapping is invalid.

A merge is the process of fusing together the control flow graphs of the two (or more) filters to prodice a single one. It has the notion of a producer filter and a consumer filter. The producer is the first node, producing (push) data, that the comsumer will consume (by pop, peek and drop).

At the moment only consecutive filters can be merged together. If a merge is attempted on any two filters not connected by a queue, the mapping is invalid.

FIXME: For now, only one to one merges are allowed, that is merges between a producer having one output queue, and a consumer having one input queue.

The filter fusion algorithm was developed by Giuseppe Desoli as an extension of the one developed by Proebsting and Watterson


The topology is a topological description of the target platform.

It can describe the processors, hardware blocks and DMA units, as well as the nodes (an abstraction of the previous ones with threads or other multi-execution schemes), and the communication infrastructure (the NoC channels for instance).

The xSTreamC compiler has a default topology that you can override with the relevant option

Mapping options

The mapping hints are specified using an XML file which content is described by the mapping.dtd DTD file.

The xSTreamC compiler is able to execute the mapping from a given XML file, or to save a mapping to a file.

Specifying and input mapping

You can specify an option to the compiler to read a mapping file, through the –mapsrc or -ms option.

xSTreamC myapplication.xc --mapsrc mymapping.xml
xSTreamC myapplication.xc -ms mymapping.xml

:!: If you don’t have a XML mapping file already, a convenient way to obtain one for your application is generate a default one, through the save_mapping option  and customize it.

Save a Mapping

Inversely, you can save the mapping executed by xSTreamC into a file.

xSTreamC myapplication.xc --mapdst mymapping.xml
xSTreamC myapplication.xc -md mymapping.xml

:!: Even if a mapping fails by lack of nodes, the generation of the file will be performed. The non mapped nodes will result without destination node, but the squeleton will allow you to specify your mapping, so that you can run xSTreamC compiler again for a succesful mapping.

Specifying topology

The machine topology is specified using an XML file whose content is described in the a DTD file (machine.dtd)

You can replace the default topology description (located in the xml directory of the xSTreamC installation) with a custom one. This allows you to increase the number of nodes, the communication, and the number of threads per node.

To specify a machine description file use the –desc option

xSTreamC ... --desc newtopology.xml

Incomplete mapping files

If a mapping file is given with an incomplete mapping, it will be automatically completed with the according to the default mapping policy, assuming the input file pecifications as strict mapping constraints.

Mapping algorithms

Dummy mapping

For now, this is the only available default mapping policy supported in xSTreamC.

The dummy mapping, for a given list of filters and a given list of nodes, associates one filter to a node.

There’s no guarantee that the mapping will be successful depening on the number of nodes really available on the target platform, plus no consideration whatsover is given to performance.