In section 2 of chapter 4 of Kumar 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

Any leads?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.