<p>here are my answers to your questions.</p>

<p>1) In general, you can not come up with efficient schemes for scaling down the number of processor from $n$ to $p &lt; n$. Why ? Because, even without taking into account additional issues such as caches etc, the problem is strictly related to how you map tasks to processors, which is known to be an NP-complete problem. In particular, this is almost always application dependent, so you have to carefully evaluate this each time you want to scale down your parallel algorithm. The good news here is that, starting from a work-efficient algorithm you can obtain a scaled-down work-efficient algorithm, thus preserving its efficiency.</p>

<p>2) To the best of my knowledge there are no strong connections with parameterized complexity, at least I am not aware of any significant published paper discussing this relation. I may be wrong of course.</p>

CC BY-SA 3.0
2012-02-21T17:32:21.600Z
2012-02-21T17:32:21.600Z
Massimo Cafaro
<p>In section 2 of chapter 4 of <a href="http://www.amazon.co.uk/Introduction-Parallel-Computing-Ananth-Grama/dp/0201648652" rel="nofollow">Kumar</a> the idea of scaling down is discussed. 
It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "shifting" it from the  number of processors to time.</p>

<p>Two things are on my mind with respect to this question.</p>

<ol>
<li><p>I'm sure it is interesting to come up with efficient schemes for such conversion for dedicated hardware solutions (say , given the architecture of CUDA , one can implement efficient algorithms based on the size of the different cache levels etc.)
Is it interesting from the theory point of view? Can I say something about it without relating to a particular hardware solution? (Say , general schemes for work efficient preserving conversions)</p></li>
<li><p>I'm starting to see some possible connections to parameterized complexity. Is there any known work on the area? So far , Iv'e seen two popular papers and <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.7458" rel="nofollow">that</a> </p></li>
</ol>

<p>Any leads?</p>

<dc.parallel-comp><parameterized-complexity>
Is conversion of PRAM to parameter number of processors trivial
noy rotbart
# Is conversion of PRAM to parameter number of processors trivial

(Asked by: username_0 on 2012-02-20)

In section 2 of chapter 4 of [Kumar](http://www.amazon.co.uk/Introduction-Parallel-Computing-Ananth-Grama/dp/0201648652) the idea of scaling down is discussed.
It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "shifting" it from the number of processors to time.

Two things are on my mind with respect to this question.

1. I'm sure it is interesting to come up with efficient schemes for such conversion for dedicated hardware solutions (say , given the architecture of CUDA , one can implement efficient algorithms based on the size of the different cache levels etc.)
   Is it interesting from the theory point of view? Can I say something about it without relating to a particular hardware solution? (Say , general schemes for work efficient preserving conversions)
2. I'm starting to see some possible connections to parameterized complexity. Is there any known work on the area? So far , Iv'e seen two popular papers and [that](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.7458)

Any leads?

**Tags:** dc.parallel-comp, parameterized-complexity

---

## 1 answers

### Answer by username_1 on 2012-02-21. Score: 3

here are my answers to your questions.

1) In general, you can not come up with efficient schemes for scaling down the number of processor from $n$ to $p < n$. Why ? Because, even without taking into account additional issues such as caches etc, the problem is strictly related to how you map tasks to processors, which is known to be an NP-complete problem. In particular, this is almost always application dependent, so you have to carefully evaluate this each time you want to scale down your parallel algorithm. The good news here is that, starting from a work-efficient algorithm you can obtain a scaled-down work-efficient algorithm, thus preserving its efficiency.

2) To the best of my knowledge there are no strong connections with parameterized complexity, at least I am not aware of any significant published paper discussing this relation. I may be wrong of course.


---

