13
votes
Accepted
What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?
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 ...
- 9,365
11
votes
Parallel vs Distributed Algorithms
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 ...
- 13.8k
11
votes
Why is the sequence "3,3,4,5,2" considered a bitonic sequence?
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 ...
- 81k
10
votes
Accepted
Why are comparisons so expensive on a GPU?
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 <...
- 17.5k
9
votes
Accepted
Why can't fibers utilize multiple processors?
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 ...
- 17.5k
9
votes
Reference book for Parallel Computing and Parallel algorithms.
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 ...
- 5,352
7
votes
Distributed vs parallel computing
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:
...
- 1,985
7
votes
Parallel vs Distributed Algorithms
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 ...
D.W.♦
- 150k
7
votes
Accepted
What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?
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 ...
- 11.9k
7
votes
Accepted
Why is the sequence "3,3,4,5,2" considered a bitonic sequence?
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 ...
- 9,365
6
votes
Why can't fibers utilize multiple processors?
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 ...
- 3,223
6
votes
Accepted
Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?
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 ...
- 874
6
votes
Can every program be parallelized infinitely and automatically?
If you're working in the strict lambda calculus, everything can be automatically parallelized. In particular, when evaluating a function application, the function and the argument can always be ...
- 29.4k
6
votes
Parallel vs Distributed Algorithms
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 &...
- 1,985
6
votes
Accepted
What is the difference between Consensus and Leader Election problems?
This is not a matter of terminology: they're related, but different concepts.
A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in ...
6
votes
Accepted
Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?
In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all ...
- 3,481
6
votes
Accepted
Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?
The reason is that Amdahl's law and Gustafson's law refer to two very different situations.
In particular, Amdahl's law applies to those cases in which the problem size is fixed, e.g. you need to ...
- 4,067
5
votes
Accepted
Parallel algorithms on a fixed number of processors
There are several models, widely used in practice, that might be of interest to you. Almost all of them could be viewed as generalizations of Amdahl's law. They take two parameters, $P$ (number of ...
- 17.5k
5
votes
Accepted
Understanding the definition of SPMD
You are taking these definitions too literally (as if they were mathematical definitions that could be used in a proof.) These terms all come from the "heroic" age of computer architecture ...
- 17.5k
5
votes
Accepted
Understanding Gustafson's Law
First I suggest you to read the original article "Reevaluating Amdahl's Law" (CACM'1988) by John L. Gustafson when you have difficulty with the wiki article. Notice that I will use the notations from ...
- 9,379
5
votes
Difference between Parallel and Concurrent programming?
A slightly idealised answer, perhaps...
Concurrency is a property of how a program is written. If a program is written using constructions like forks/joins, locks, transactions, atomic compare-and-...
- 151
5
votes
Accepted
Is multiprocessing possible on a turing machine?
You can consider two variants of this question.
Can a Turing machine simulate parallelism?
Can a Turing machine simulate parallelism efficiently?
The answer for the first question is a resounding ...
- 273k
5
votes
is the problem of parallelising any program, NP-complete?
It is not clear what exactly you want of that compiler, so let me explore several possibilities.
Optimize the parallelism
This is impossible. Optimizing even sequential runtime is not computable, ...
- 71.6k
5
votes
Implement K-means clustering with Map-Reduce
You can run a loop over $j\in\{1..k\}$:
Create a map that maps each point $x_i$ to itself if $x_i$ is nearest to the mean $m_j$, and to the zero vector otherwise:
$$x_i \rightarrow \begin{cases}(x_i, ...
- 398
5
votes
Accepted
Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:
Stage 1: Calculate $M^...
- 27.1k
5
votes
Accepted
Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?
There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance.
One of them is parallelism, as you point out.
A second technique trading off ...
- 17.5k
4
votes
P-Completeness and Parallel Computation
Be very mindful of who takes "efficient parallel algorithms" to mean what, exactly.
The older answers explain the perspective of complexity theory. There, "efficient"
usually means something vague ...
- 71.6k
4
votes
Distributed vs parallel computing
In the Introduction section of the book [1], the authors provide another perspective (different from the ones in other answers) on the comparison between distributed computing and parallel computing.
...
- 9,379
4
votes
Accepted
Why doesn't parallelism necessarily imply non-determinism?
The book is using the term non-deterministic in two different ways. In concurrent computations and parallel computations the order in which the computations occur is non-deterministic. The final ...
- 17.5k
4
votes
Instruction level parallelism
Instruction-level parallelism, data-level parallelism, loop-level parallelism, and task-level parallelism are not well defined terms. The definable concept is parallelism. Two operations can run ...
- 17.5k
Only top scored, non community-wiki answers of a minimum length are eligible