Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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,465
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
8 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
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,465
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
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
  • 30.4k
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, ...
Nathaniel Bubis'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.5k
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

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,351
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
  • 30.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.6k
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,511
3 votes

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If by sequential you mean multiplying $m$ times, the $\log m$ solution of initially only calculating the relevant powers of $2$ (a.k.a Exponentiation by squaring) is clearly better for large $m$. ...
Nathaniel Bubis's user avatar
3 votes

Both shared-memory and distributed-memory

A couple of points, but in general the diagram doesn't provide enough information to make any real conclusions. First, this isn't the typical layout for shared memory architecture. Typically shared ...
theoneandonly2's user avatar
3 votes

Is the word problem of CFLs in NC?

The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete. Interestingly, Ullman ...
bardamu's user avatar
  • 31
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,873
3 votes

Designing a parallel algorithm to find the second largest item in an array

I'll sketch informally one obvious variant, assuming some model with shared memory and unbounded parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the ...
Anton Trunov's user avatar
  • 3,479
3 votes
Accepted

How on-chip multithreading prevents cache misses from stalling a processor pipeline?

It's called "out of order execution". When one instruction stalls, that doesn't mean the whole pipeline stalls. All instructions that don't depend on this one instruction can continue. Sometimes ...
gnasher729's user avatar
  • 30.4k
3 votes

Gate/transistor number and program length measures of computational complexity?

Two well-known books in this research area are: Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984 and F. Tom Leighton, Introduction to Parallel Algorithms and ...
Wandering Logic's user avatar
3 votes
Accepted

Is there a generic way to parallelize algorithms?

No, there cannot be such a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ with the requested properties. The basic problem is that the requested parallel algorithm only uses ...
Thomas Klimpel's user avatar

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