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,425
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.9k
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 ...
- 81.4k
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,382
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.♦
- 156k
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,996
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 ...
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,425
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.7k
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,996
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,491
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,132
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
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, ...
- 72.1k
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^...
- 28.4k
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.7k
4
votes
Is "flops" a reliable measure of deciding computational capacity?
Much computing is shuffling data around, from memory to CPU(s) and viceversa, from disk to memory, and so on. Performance could well be determined by non-processing needs. If there are several CPUs ...
- 13.9k
4
votes
How to simulate a parallel computer (with certain number of processors) on a serial computer
The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard. Genetic algorithms can get a good solution more ...
- 1,341
4
votes
How to find min or max in constant time using infinite # processors?
I managed to solve this so hoping it's alright to answer your own question.
Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number ...
- 170
4
votes
Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can ...
- 743
4
votes
Accepted
NP with a parallelism model?
Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead ...
- 5,382
4
votes
What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?
For concurrency in general, there is a very active line of research, which I tried to summarise in this reply: https://cs.stackexchange.com/a/102711/98901
I add here a comment on parallelism, below.
...
- 171
4
votes
Accepted
Does Amdahl's law apply to modern multi-code processors?
Yes, it's still true. The speedup can't be less than zero (if parallelizing your code makes it slower, just run the serial version) or more than 100% (because saving more than 100% of the runtime ...
- 81.4k
4
votes
Accepted
Can I assume that a percentage of the time can be parallelized?
You can never assume anything.
There are plenty of cases where your work, or a percentage of your work, can be split up into k independent tasks. If you have k processors, then each one can handle ...
- 28.4k
4
votes
Accepted
What should be the minimum value when the two threads are executed concurrently
Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared ...
- 14.4k
4
votes
Accepted
Response time of scheduling a DAG where each vertex is a task
Found it! This problem is NP-complete when the goal is to minimize total execution time.
The scheduling problem (P1) is the following. We are given
(1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs,
(2) ...
- 4,431
3
votes
Why is the step property in a balancing network defined as it is?
The formula is wrong. The correct formula is
$$
y_i = \lfloor \frac{n}{w} \rfloor + [i < (n \mod{w})],
$$
where $[C]$ equals 1 if $C$ holds, and 0 otherwise.
Sometimes books contain mistakes. When ...
- 275k
3
votes
how does the parallel radix sort work?
There are many ways to do it. The following approach allows to fairly split work between many cores. I believe that it's used even in GPU implementations of radix sort, such as ones provided by Boost....
- 1,845
Only top scored, non community-wiki answers of a minimum length are eligible