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 ...
Evil's user avatar
  • 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 ...
vonbrand's user avatar
  • 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 ...
David Richerby's user avatar
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 ...
Thomas Klimpel's user avatar
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.'s user avatar
  • 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: ...
Jukka Suomela's user avatar
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 ...
Derek Elkins left SE's user avatar
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 ...
Evil's user avatar
  • 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 ...
jmite's user avatar
  • 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 &...
Jukka Suomela's user avatar
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 ...
Gilles 'SO- stop being evil''s user avatar
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 ...
sdcvvc's user avatar
  • 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 ...
Massimo Cafaro's user avatar
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-...
John Wickerson's user avatar
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, ...
Raphael's user avatar
  • 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, ...
nbubis's user avatar
  • 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^...
gnasher729's user avatar
  • 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 ...
Wandering Logic's user avatar
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 ...
vonbrand's user avatar
  • 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 ...
Nat's user avatar
  • 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 ...
wabbit's user avatar
  • 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 ...
Kurt Mueller's user avatar
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 ...
Thomas Klimpel's user avatar
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. ...
fmontesi's user avatar
  • 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 ...
David Richerby's user avatar
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 ...
gnasher729's user avatar
  • 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 ...
chi's user avatar
  • 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) ...
ryan's user avatar
  • 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 ...
Yuval Filmus's user avatar
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....
Bulat's user avatar
  • 1,845

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