Task Interaction Graph Data Set and Heuristics

(Last updated: 23 Feb, 2012)

This page contains the data set and some of the results and heuristics of the papers

  1. Kamer Kaya and Bora Uçar, Exact algorithms for a task assignment problem, Parallel Processing Letters, Vol. 19, pp.451--465, 2009 (abstract, also available as LIP research report RR-2009-14, data and results).
  2. Bora Uçar, Cevdet Aykanat, Kamer Kaya, and Murat Ikinci, Task assignment in heterogeneous computing systems, Journal of Parallel and Distributed Computing, Vol. 66, No. 1, pp.32--46, 2006 (abstract, paper, code)


1. Exact algorithms and the data files

These data are produced from a set of sparse matrices from the DWT collection, available at the Matrix Market.

See the codes to create the data.

The data files are named according to the following convention: t[T]p[P]r[rho]ETC[X].I where

Data file format:

P T E %First line: procs, num tasks, tot number of edges (2*num_comm)). etc(t1, p1) etc(t2, p1) ... etc(tT, p1) etc(t1, p2) etc(t2, p2) ... etc(tT, p2) ... ... ... ... etc(t1, pP) etc(t2, pP) ... etc(tT, pP) vi comm(1,i) vj comm(1,j) ... %The neighbors of task 1. Here vi and vj are its neighbors with communication amout next to the id of the neighbor. vk comm(2,k) vl comm(2,l) ... %The neighbors of task 2. ... vy comm(T,y) vz comm(T,z) ...%The neighbors of task T.


Distances between processors (for P=2,3,4,8 processors, the PxP principal submatrix is used):

0 1 3 2 5 5 4 3 1 0 2 1 4 4 3 2 3 2 0 1 4 4 3 2 2 1 1 0 3 3 2 1 5 4 4 3 0 2 1 2 5 4 4 3 2 0 1 2 4 3 3 2 1 1 0 1 3 2 2 1 2 2 1 0


Some benchmark solutions using the A* algorithm

Optimal Cost
Data file Homogeneous Comm. Heterogeneous Comm.
t59p8r1.4ETC3.1 5243 (sol) 5915 (sol)
t72p8r1.0ETC3.1 2508 (sol) 2850 (sol)
t87p4r1.4ETC3.1 11756 (sol) 12275 (sol)
t162p3r1.0ETC3.2 22674 (sol) 22674 (sol)
(Yes the same cost, the same assigment; but different number of nodes explored in A*)

2. TIG assignment

You can find the codes of the heuristics discussed in the paper "Bora Uçar, Cevdet Aykanat, Kamer Kaya, and Murat Ikinci, Task assignment in heterogeneous computing systems, Journal of Parallel and Distributed Computing, Vol. 66, No. 1, pp.32--46, 2006," here. This tgz file also includes the necessary codes to create the data files (see also above).

There are two files and five directories:

Each directory contains a suitable Makefile.