I am wondering if the data-parallel model is theoretically less powerful than other imperative-style models of parallel computation. Are there, for instance, some problems that simply cannot be solved solely under this model as efficiently as others (i.e. the solution under the data-parallel model exists in a higher asymptotic class)? I ask because I know that for purely functional data structures/algorithms there are established lower bounds on some operations that are worse than in imperative models (middle of page 2 in provided link).
grose
Well, I believe all functional languages are ultimately run in an imperative language (assembly or the like)... so, they cannot do better than an imperative language.
I am wondering if the data-parallel model is theoretically less powerful than other imperative-style models of parallel computation. Are there, for instance, some problems that simply cannot be solved solely under this model as efficiently as others (i.e. the solution under the data-parallel model exists in a higher asymptotic class)? I ask because I know that for purely functional data structures/algorithms there are established lower bounds on some operations that are worse than in imperative models (middle of page 2 in provided link).
Well, I believe all functional languages are ultimately run in an imperative language (assembly or the like)... so, they cannot do better than an imperative language.