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

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

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 ...


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 $...


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

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

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

Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...? The History of Parallel Computing goes back far in the past, where the current interest in GPU computing was not yet predictable. Some important concepts date back to that time, with lots of theoretical activity between 1980 ...


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 ...


7

The Concurrent Logical Framework is one interesting area including its descendants, like Linear Meld and LolliMon. This is based on intuitionistic linear logic. Classical linear logic has connections to the Linear Chemical Abstract Machine (CHAM) as described by e.g. A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine which ...


7

Bitonic sequence is defined for example for parallel sort, as non-decreasing and then non-increasing sequence, to allow duplicates. See here: Bitonic sequence. Also Wikipedia article about Bitonic sorter shows the same definition which is, afaik, the common one.


6

To the best of my knowledge, it may be the Queuing Shared Memory (QSM) model, even though hierarchical parallelism of threads is not taken into account. However, accesses to local memory and global memory (different bandwidth), and bulk synchrony (in which threads can work asynchronously beetween barrier synchronizations) are considered.


6

Given any language $L$ in NL decided by some machine $T$, you can decide whether $x \in L$ by considering the configuration graph of $T$ when run on $x$. This is why PATH is NL-complete. Given any length $n$ of the input, the configuration graph is a fixed polynomial-size graph which doesn't depend on $x$. Only the starting vertex depends on $x$. We can ...


6

If two different processors share one memory, each having individual cache, they can end up having two different values in the same address. Imagine each of two processors has private caches L1 and L2. The cache L3 is shared between both processors. Assume the processor A reads data from address X in L3 to L1 and the processor B reads the same data from the ...


6

The answer is actually that they could, but there is a desire not to. Fibers are used because they let you control how scheduling occurs. Accordingly, it is much simpler to design some algorithms using fibers because the programmer has say in which fiber is being executed at any one time. However, if you want two fibers to be executed on two different ...


6

When you are using two processors, not every task your GPU's encounter is parallel by nature. There are a certain portion of tasks which are strictly serial, and can be processed by only one processor at a given time. If a set of tasks were to be 100% parallel your dual GPU set up should give double the speed (in theory). A little mathematics for you: ...


6

The terms can mean almost anything, but I will try to present here one way in which the terms "parallel algorithms" and "distributed algorithms" are understood. Here we interpret "distributed algorithms" from the perspective of "network computing" (think: algorithms that keep the Internet running). I will use as a ...


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