The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [parallel-computing]

Questions about algorithms or programs that compute on multiple processing units simultaneously. Not to be confused with concurrent or distributed computing!

Filter by
Sorted by
Tagged with
22
votes
5answers
2k views

P-Completeness and Parallel Computation

I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is ...
19
votes
2answers
433 views

How to scale down parallel complexity results to constantly many cores?

I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC: NC is the class of problems that can be solved by a ...
59
votes
6answers
65k views

Distributed vs parallel computing

I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
0
votes
1answer
170 views

What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm
67
votes
4answers
16k views

What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is ...
42
votes
4answers
46k views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
13
votes
1answer
5k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
23
votes
3answers
5k views

Which algorithms can not be parallelized?

Is there any algorithm which is very difficult to parallelize or the research is still active? I wanted to know about any algorithm or any research field in parallel computing. Anything, I searched ...
5
votes
3answers
2k views

Why doesn't parallelism necessarily imply non-determinism?

I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out. I understand the difference between ...
19
votes
3answers
891 views

Are today's massive parallel processing units able to run cellular automata efficiently?

I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or ...
4
votes
6answers
2k views

Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
2
votes
1answer
243 views

What can distributed computing do besides parallel computing?

I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing? If I understand correctly, parallel ...
2
votes
1answer
63 views

What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? [closed]

I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use ...
4
votes
2answers
885 views

Parallel Computing: Past Vs Present

Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on ...
2
votes
0answers
72 views

EXPTIME and parallel computing

Can we solve an EXPTIME-complete problem in polynomial time given 2^N processors?(N is the size of input).
1
vote
0answers
83 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
1
vote
1answer
48 views

Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
0
votes
1answer
100 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $...