59

This is partly a matter of terminology, and as such, only requires that you and the person you're talking to clarify it beforehand. However, there are different topics that are more strongly associated with parallelism, concurrency, or distributed systems. Parallelism is generally concerned with accomplishing a particular computation as fast as possible, ...


48

I can not help but think: this is divide & conquer, plain and simple! M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input. It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations. ...


22

EDIT (March 2014) I should say that I have since worked more on algorithms for MapReduce-type models of computation, and I feel like I was being overly negative. The Divide-Compress-Conquer technique I talk about below is surprisingly versatile, and can be the basis of algorithms which I think are non-trivial and interesting. Let me offer an answer that ...


21

In addition to Nish's answer, let me recommend Simon Marlow's book on Parallel and Concurrent Programming in Haskell or his shorter tutorial. They answer your first question from Haskell's perspective, so they could be better suited for theoretically inclined readers (Haskell is a purely functional, lazy programming language that is much closer to ...


21

Conurrency and parallelism differ in the problems they solve and cause, but they are not independent. Concurrency Executing two tasks concurrently means that individual steps of both tasks are executed in an interleaved fashion. If you disregard parallelism, you can assume that only one statement is executed at any point in time, but you have (a priori) no ...


17

I assume that an edge $(u,v)$ means that $u$ has to be executed before $v$. If this is not the case, turn around all edges. I furthermore assume that you are less interested in paths (those are already given by the DAG) than in a good execution strategy given the dependencies. You can easily adapt the topological sort procedure: instead of appending, merge ...


17

As pointed out by @Raphael, Distributed Computing is a subset of Parallel Computing; in turn, Parallel Computing is a subset of Concurrent Computing. Concurrency refers to the sharing of resources in the same time frame. For instance, several processes share the same CPU (or CPU cores) or share memory or an I/O device. Operating systems manage shared ...


17

Nothing is free. GPGPUs are SIMD. The SIMD instructions on GPGPUs tend to be wider than the SIMD instructions on CPUs. GPGPUs tend to be fine-grained multi-threaded (and have many more hardware contexts than CPUs). GPGPUs are optimized for streaming. They tend to devote a greater percentage of area to floating point units, a lower percentage of area to ...


13

If you assume that the number of processors is bounded by a constant, then you are right that a problem being in NC does not mean much in practice. Since any algorithm on a PRAM with k processors and t parallel time can be simulated with a single-processor RAM in O(kt) time, the parallel time and the sequential time can differ only by a constant factor if k ...


12

Yes it can, and has been. In the paper Map-Reduce for Machine Learning on Multicore they discuss using the Map-Reduce paradigm for several common ML algorithms including ANNs.


12

This article gives a number of problems that are easy to solve sequentially but difficult to parallelise: http://en.wikipedia.org/wiki/P-complete The circuit value problem ("given a Boolean circuit + its input, tell what it outputs") is a good starting point — easy to understand, easy to solve with sequential algorithms, and nobody knows if it can be ...


12

this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms. in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $...


12

With equation: not really. Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the bottleneck). For example, you have serial algorithm that takes $1t$ to execute. You have $1024$ cores, so naive speedup is $1024x$, or it takes $t/1024$, but it ...


11

The words "increasing" and "decreasing" are used in inconsistent ways. Probably, you're assuming one definition while the author of the text that's confusing you is using the other. Say that the sequence $a_1, \dots, a_n$ is type A if $a_1\leq a_2\leq \dots\leq a_n$; type B if $a_1<a_2<\dots<a_n$. The problem is that some people refer ...


10

I agree with you that $NC$ is not the best way to characterize efficient parallel algorithms. Indeed, by definition NC also includes lots of problems which are not efficiently parallelizable. A common example is parallel binary search. The problem arises because parallel binary search has polylogarithmic time complexity even for $p = 1$. Any sequential ...


10

GPUs are SIMD architectures. In SIMD architectures every instruction needs to be executed for every element that you process. (There's an exception to this rule, but it rarely helps). So in your MinMax routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement ...


10

An algorithm is parallel if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference results by others freely (low cost). An algorithm is distributed if it is parallel and the tasks run on separate machines (separate address spaces), one task has no ...


9

Third, since $\sf{L} \subseteq \sf{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $t(n)$-time TM $M$, that an oblivious TM $M'$ (i.e. a TM whose head movement is independent of its input $x$) can construct a circuit $C_n$ to compute $M(x)$ where $|x| = n$. The ...


9

Forget for a moment all of the issues related to the access to main memory and level 3 cache. From a parallel perspective, ignoring these issues, the program parallelize perfectly when using $p$ processors (or cores), owing to the fact that, once you partition the work to be done through domain decomposition, each core must process either $\left\lfloor {\...


9

Divide your original array into $n/\log n$ blocks of length $\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time $\log n$. We now need to compute the maximum of an array of length $n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it $\log ...


9

The main distinction, as you point out in your question, is whether or not the scheduler will ever preempt a thread. The way a programmer thinks about sharing data structures or about synchronizing between "threads" is very different in preemptive and cooperative systems. In a cooperative system (which goes by many names, cooperative multi-tasking, ...


8

Tasks that are easily parallelizable are sometimes called embarassingly parallel. Straightforward examples are computing fractals like Julia or Mandelbrot sets (since all points are independent of each other) or brute-force searches. You can find many other examples on the wikipedia page.


8

John Gustafson observed and reported speedups in excess of 1024 on early 80's supercomputers; this led him to the concept of scaled speedup (Gustafson-Barsis law), in contrast to the pessimistic Amdahl-Ware law. Right now, in the era of multicore parallel supercomputers equipped with hundreds of thousands or millions of cores, performances are more ...


8

Have a look at the results from this years SAT 2013 competition. Based on these results, definitely give Lingeling a try. Plingeling is the parallel variant of it. If you don't need to prove unsatisfiability (perhaps you know the instance is satisfiable, and you just need to know an assignment making it SAT), you could try local search methods, too.


8

From a practical-oriented perspective, you are asking about inherently-sequential algorithms. There are many candidates, such as hash-chaining, which is believed to be very difficult to parallelize. Hash-chaining is widely used in cryptography. For instance, the password-hashing scheme bcrypt was designed to try to make it difficult to speed up the hash ...


7

I'm not sure I understand the question. The distinction between parallel and distributed processing is still there. The fact that you can take advantage of both in the same computation doesn't change what the concepts mean. And I don't know what news are you following, but I'm quite sure parallel processing is not stagnating, especially since I think it's ...


7

Here is a recent paper that is worth reading: Michel Raynal: "Parallel Computing vs. Distributed Computing: A Great Confusion?", Proc. Euro-Par 2015, doi:10.1007/978-3-319-27308-2_4 Abstract: This short position paper discusses the fact that, from a teaching point of view, parallelism and distributed computing are often confused, while, when looking at ...


7

You misread the text. The authors of PETSc are just telling you that you can't avoid Amdahl's law. They have done their best to parallelize every aspect of the linear solver. But a real program is not just a call to a linear solver. First you generate a matrix and then you pass the matrix to the linear solver. If your matrix generator is slow, your ...


7

One important quantitative distinction is that communication often costs more in distributed computing than in parallel computing. An important qualitative distinction is that distributed algorithms often must deal with failure (e.g., one machine crashes, one machine starts misbehaving and sending spurious messages, or messages get lost or corrupted). In ...


Only top voted, non community-wiki answers of a minimum length are eligible