ON THE COMPLEXITY OF THE MAPPING PROBLEM FOR MASSIVELY PARALLEL ARCHITECTURES

Publisher Website
Google Scholar
Abstract
The mapping problem arises when a concurrent program is executed on a parallel architecture. The goal is to devise an allocation of processes onto physical processing nodes which optimizes a global measure of system performance. In this work we analyze the complexity and the approximability of both the mapping problem in its general formulation and some of its subproblems that are interesting for massively parallel systems. Unfortunately, it turns out that all the problems introduced are NP-Hard. Moreover, they can be solved only with approximate algorithms for which the distance between the exact and the approximate solution is not bounded.

This publication has 0 references indexed in Scilit: