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.

system.png

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.

mapping.png

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:
  • 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

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

Related publications

-- HeikkiOrsila - 14 Dec 2010
  • SW components (application tasks) are mapped to HW components. T denotes an application task, and PE denotes a processing element.:
    system.png

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

Topic attachments
I Attachment Action Size Date Who Comment
dcs-task-mapper-1.0.1.tar.bz2bz2 dcs-task-mapper-1.0.1.tar.bz2 manage 75.9 K 20 Dec 2010 - 14:04 UnknownUser DCS task mapper 1.0.1
dcs-task-mapper-1.0.2.tar.bz2bz2 dcs-task-mapper-1.0.2.tar.bz2 manage 77.6 K 02 Feb 2011 - 18:22 UnknownUser DCS task mapper 1.0.2
mapping.pngpng mapping.png manage 48.0 K 14 Dec 2010 - 16:15 UnknownUser Design space exploration process. Boxes indicate data and ellipses are operations.
orsila-thesis-experiment-2011-03-25.tar.bz2bz2 orsila-thesis-experiment-2011-03-25.tar.bz2 manage 30.5 K 25 Mar 2011 - 20:46 UnknownUser SA and GA experiment data from doctoral thesis of Heikki Orsila
system.pngpng system.png manage 32.8 K 14 Dec 2010 - 16:12 UnknownUser SW components (application tasks) are mapped to HW components. T denotes an application task, and PE denotes a processing element.

This topic: DACI > SoCTools > DCSTaskMapper
Topic revision: r25 - 12 May 2011 - 16:12:33 - ShibbolethUserMapping_heikki@tut.fi
 
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback