18 votes

Why use SIMD if we have GPGPU?

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 ...
user avatar
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 ...
user avatar
  • 9,325
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 ...
user avatar
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 <...
user avatar
10 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 ...
user avatar
  • 13.6k
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 ...
user avatar
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 ...
user avatar
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: ...
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 ...
user avatar
  • 140k
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 ...
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 ...
user avatar
  • 9,325
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 ...
user avatar
  • 3,025
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 ...
user avatar
  • 864
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 ...
user avatar
  • 29.1k
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 &...
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 ...
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 ...
user avatar
  • 3,461
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 ...
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-...
user avatar
5 votes
Accepted

Suboptimal Solution for a combinatorial problem

Mixed-integer quadratic programming Given your updated question, this can be formulated as a mixed-integer quadratic programming problem. Let $y_1,\dots,y_n$ be $n$ zero-or-one integer variables, ...
user avatar
  • 140k
5 votes

Suboptimal Solution for a combinatorial problem

If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once. In a lot of practical situations I would expect ...
user avatar
  • 1,049
5 votes

BNF and Simultaneous Parsing

If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at ...
user avatar
  • 11k
5 votes

How to compare algorithms in class NC time complexity with other classes?

The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 9,179
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 ...
user avatar
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 ...
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, ...
user avatar
  • 70.8k
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, ...
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^...
user avatar
  • 24.9k

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