Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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,465

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

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

### 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 ...
• 12.1k
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,465
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
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,247

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

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^... • 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, ... 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.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 ... • 17.8k 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,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 ... • 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,390 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.8k 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 ... • 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 ... • 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) ... • 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$. ... 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 ... 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 ... • 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.... • 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 ... • 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 ... • 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 ... • 17.8k 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 ...
• 5,390

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