# Tag Info

### 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 ...
• 17.3k
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,325

### 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 ...
• 80.1k
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.3k

### 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.6k

### 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,312
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.3k

### 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,955

### 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 ...
• 140k
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.8k
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,325

### 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,025
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 ...
• 864

### 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.1k

### 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,955
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 ...
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,461
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 ...
• 3,959

### 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-...
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, ...
• 140k

### 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 ...
• 1,049

### 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 ...
• 11k

### 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 ...
• 269k
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.3k
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,179
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.3k
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 ...
• 269k

### 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, ...
• 70.8k

### 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
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^...