Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2012

Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice

Résumé

We investigate the routing of communications in grid graphs, representing chip multiprocessors. We consider the $k$-MP and Max-MP models of Manhattan-path routing introduced by Benoit \emph{et al.}~(IPDPS 2012). In Max-MP, each of the communication requests can be split into arbitrarily many communication paths between the source and terminal node, while in $k$-MP, it can be split into at most $k$ such paths, where $k\geq 1$ is a parameter of the model. The power cost associated with activating a communication link at a transmission speed of $b$ bytes/second is proportional to $b^\alpha$, for some constant exponent $\alpha > 2$. Our first result is to establish a trade-off between the power cost of single source-sink $k$-MP routing, and the value of the model parameter $k$. Our results imply that above the threshold value of $k = \Theta (n^{1/(\alpha-1)})$, the optimal solution to $k$-MP for grids of dimensions $\Theta(n)$ is the same as that of Max-MP, up to a constant factor. We also show that this threshold is tight for the natural single-request instance, i.e., it is necessary to split such a request into $\Theta(n^{1/(\alpha-1)})$ paths to achieve asymptotically-optimal cost. Our analysis relies on new algorithmic schemes for $k$-MP routing in grids. Our second contribution is to provide efficient algorithms for solving $k$-MP. We point out that whereas the minimum-cost $k$-MP routing problem is NP-hard, there exist polynomial-time algorithms for $k$-MP routing which provides a constant approximation of the optimum cost. We close the paper by showing experimental evidence that for practical instances, our algorithm for $k$-MP achieves a power cost close to that of the optimal solution to Max-MP, starting from the above-discussed threshold value of $k$.
Fichier principal
Vignette du fichier
paper-hal.pdf (284.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00737611 , version 1 (02-10-2012)
hal-00737611 , version 2 (08-02-2013)
hal-00737611 , version 3 (01-06-2013)

Identifiants

  • HAL Id : hal-00737611 , version 1

Citer

Adrian Kosowski, Przemyslaw Uznanski. Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice. 2012. ⟨hal-00737611v1⟩
160 Consultations
177 Téléchargements

Partager

Gmail Facebook X LinkedIn More