DCS task mapper

DCS task mapper is a design space exploration tool for placing tasks (processes) onto a multiprocessor system.

The tool optimizes task mapping (placement) and scheduling of applications with various algorithms. The optimizer tries to look for a mapping that minimizes a given cost function. Usually the cost function is the execution time of the application. Applications are modeled as task graphs. Tasks execute on a processing element (PE), e.g. a processor, HW accelerator etc.

Figures below shows a system that has tasks (T) that are mapped onto processing elements (PE), and communication between tasks uses a communication network.

Figure below shows the optimization process. Problem space is the set of all problems for the task mapper. Allocation defines the HW system (PEs and communication network) that executes tasks and communication. The implementation phase does mapping (task placement) and scheduling (relative priorities of tasks competing for the same execution resources). System evaluation computes the objective measures (the objective function value is computed by simulation) to assess the goodness of a given mapping/scheduling solution.

Task mapper has following features:

• Optimizes an application presented as a task graph to minimize an arbitrary cost function
  • Usually the cost is the execution time of the application
• Provides several mapping algorithms:
  • Simulated Annealing algorithms (stochastic)
  • Genetic algorithms (stochastic)
  • Random mapping (stochastic (Monte Carlo))
  • Group migration (deteministic, greedy)
  • Brute force (optimal solution, exponential time)
  • Optimal subset mapping (fast semi-greedy algorithm)
• Several application types are supported:
  • Directed acyclic graphs (DAGs)
  • Kahn process networks: http://en.wikipedia.org/wiki/Kahn_Process_Network
• Virtual time schedule simulator to test algorithms
• Provides several scheduling algorithms
  • DAGs: Critical path first
  • KPNs: FIFO, static priority task scheduling

The tool works as a command line filter that reads input from standard input and produces results on the standard output.

Supported platforms

The tool has no other external dependencies but the C library, some system calls and /dev/urandom random number source. If a need arises, the urandom requirement can be relaxed by using a random generator from C library.

Supported platforms:

• Linux and UNIX-like systems
• Cygwin
• MinGW? status is unknown

Download

• DCS task mapper 1.0.2: dcs-task-mapper-1.0.2.tar.bz2 (78 KiB?)
• DCS task mapper 1.0.1: dcs-task-mapper-1.0.1.tar.bz2 (76 KiB?)

The latest development version of DCS task mapper can obtained by using git version control tool:

git clone git://zakalwe.fi/dcs-task-mapper

Author

DCS task mapper was designed and written by Heikki Orsila <heikki.orsila@tut.fi> for the DACI research group at Digital and Computer Systems Department.

Experimental data

• SA and GA experiment data from doctoral thesis of Heikki Orsila: https://wiki.tut.fi/pub/DACI/DCSTaskMapper/orsila-thesis-experiment-2011-03-25.tar.bz2

Related publications

• Heikki Orsila, "Optimizing Algorithms for Task Graph Mapping on Multiprocessor System on Chip", PhD Thesis, 2011. http://zakalwe.fi/~shd/publications/optimizing-algorithms-for-task-graph-mapping-on-multiprocessor-system-on-chip-2011-orsila.pdf
• Heikki Orsila, Erno Salminen, Timo D. Hämäläinen, "Parameterizing Simulated Annealing for Distributing Kahn Process Networks on Multiprocessor SoCs", SoC 2009, October 5-7, 2009. http://daci.digitalsystems.cs.tut.fi:8180/pubfs/fileservlet?download=true&filedir=dacifs&freal=Orsila_-_Parameterizing_Simulated__1.pdf&id=93830
• Heikki Orsila, Tero Kangas, Erno Salminen, Timo D. Hämäläinen, "Parameterizing Simulated Annealing for Distributing Task Graphs on Multiprocessor SoCs", International Symposium on System-on-Chip 2006, Tampere, Finland, November 14-16, 2006, pp. 73-76. http://daci.digitalsystems.cs.tut.fi:8180/pubfs/fileservlet?download=true&filedir=dacifs&freal=Orsila_-_Parameterizing_Simulated_.pdf&id=78983
• Heikki Orsila, Erno Salminen, Marko Hännikäinen, Timo D. Hämäläinen, "Optimal Subset Mapping And Convergence Evaluation of Mapping Algorithms for Distributing Task Graphs on Multiprocessor SoC", International Symposium on System-on-Chip, Tampere, Finland, November 19-21, 2007, 6 pages. http://daci.digitalsystems.cs.tut.fi:8180/pubfs/fileservlet?download=true&filedir=dacifs&freal=Orsila_-_Optimal_Subset_Mapping_An.pdf&id=87669
• Heikki Orsila, Tero Kangas, Erno Salminen, Timo D. Hämäläinen, Marko Hännikäinen, "Automated Memory-Aware Application Distribution for Multi-Processor System-On-Chips", Journal of Systems Architecture (in press, corrected proof), November 14, 2007, Vol.54, Issue 11, pp. 795-815, Elsevier. http://daci.digitalsystems.cs.tut.fi:8180/pubfs/fileservlet?download=true&filedir=dacifs&freal=Orsila_-_Automated_Memory-Aware_Ap.pdf&id=75145
• Heikki Orsila, Erno Salminen, Marko Hännikäinen, Timo D. Hämäläinen, "Evaluation of Heterogeneous Multiprocessor Architectures by Energy and Performance Optimization", International Symposium on System-on-Chip 2008, November 4-6, 2008, pp. 157-162. http://daci.digitalsystems.cs.tut.fi:8180/pubfs/fileservlet?download=true&filedir=dacifs&freal=Orsila_-_Evaluation_of_Heterogeneo.pdf&id=93123

-- HeikkiOrsila - 14 Dec 2010

• SW components (application tasks) are mapped to HW components. T denotes an application task, and PE denotes a processing element.:
  

• Design space exploration process. Boxes indicate data and ellipses are operations.:
  

• dcs-task-mapper-1.0.1.tar.bz2: DCS task mapper 1.0.1

• orsila-thesis-experiment-2011-03-25.tar.bz2: SA and GA experiment data from doctoral thesis of Heikki Orsila