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
3
votes
1answer
69 views

What should be the minimum value when the two threads are executed concurrently

int count=0; void *thfunc() { int ctr=0; for(ctr=0;ctr<100;ctr++) count++; } If *thfunc() is executed by two threads concurrently in a uniprocessor ...
0
votes
3answers
1k views

How to find min or max in constant time using infinite # processors?

Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ...
0
votes
1answer
128 views

All-to-All Broadcast on a Balanced Binary tree

Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree? Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages ...
0
votes
0answers
13 views

APSP on GPGPU with paths reconstruction

There is a huge number of works on efficient solution of all-pairs shortest paths (APSP) by using GPGPU. But the main goal of these works is to compute the length of the shortest path. Are there exist ...
2
votes
1answer
49 views

Question regarding terminology used to describe Benes networks

I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes....
0
votes
0answers
15 views

Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
7
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
1
vote
0answers
24 views

Parallel deletion and traversal in a lock free linked list

I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem....
0
votes
0answers
47 views

What is the complexity class of exponential parallelism?

Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel. How does one capture that in a proper formalism? Is there some ...
1
vote
0answers
12 views

Raters and subsampling

In order to select questions for an online contest, we get contributors to submit potential questions that they write themselves. Then, out of, say 100 submitted questions, we have to rate them and ...
0
votes
1answer
19 views

Are graphic cards using the Map-Reduce model when performing typical gaming rendering

I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. ...
7
votes
2answers
7k views

What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?

In parallel computing, I know the speed up equation is $$ \frac{1}{ s + \frac{1-s}{p} } $$ But what is meant by superlinear speed up? Is it something theoritical? Could you explain it with ...
0
votes
0answers
39 views

Proof of lemma from Hong's article about multi-threaded max flow algorithm

I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem. Lemma 3. Any trace ...
1
vote
0answers
15 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
2
votes
1answer
23 views

Parallelization of priority queue-based algorithms

There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-...
0
votes
1answer
33 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
0
votes
0answers
41 views

Construction of Omega Network

I understand that we could draw N * N Omega Network, But can we draw an Omega Network to connect 6 CPUs to 4 memories? (The number of CPUs does not equal the number of memories)
2
votes
0answers
28 views

What does it mean by “consistent view of memory” in lock-free dequeue implementation?

I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation. ...
1
vote
0answers
25 views

Routing a DAG through 5 consecutive butterfly networks

I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that Using standard packet-routing ...
2
votes
2answers
115 views

Is automatic multicore support at the hardware or compiler level possible?

Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance. However, multicore ...
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 ...
5
votes
2answers
3k views

how does the parallel radix sort work?

I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism. ...
3
votes
1answer
855 views

NP with a parallelism model?

Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality? From what I understand from the problem statement given by Stephen Cook, The ...
0
votes
1answer
169 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
0
votes
0answers
14 views

What is the difference between parallel virtual machine and message passing interface. And how both works [duplicate]

I m learning beowulf system architecture and I encounter these terms many time. I know these are the library file and we use these to write parallel programing. But I do not know how these work and ...
2
votes
2answers
86 views

Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
-1
votes
2answers
3k views

Amdahl's law or gustafson's law

I am a little confused which of the two laws above i should use: Suppose I have a computer program that can be parallelized by 70%. 30% cannot be parallelized. Every single data (100% of data) will ...
0
votes
1answer
42 views

When do we use parallel algorithms for enumerating combinations?

I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used? Here is a famous example of parallel algorithms, Adaptive and ...
0
votes
0answers
51 views

Parallel algorithms with desired sequential workload

Could you share any known algorithm which leans on following patterns? These patterns have both multithreaded and sequential workload. Those algorithms need to be joined to complete some sequential ...
1
vote
2answers
99 views

PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere....
3
votes
1answer
76 views

Global indexing of shared nodes in parallel

Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of ...
1
vote
2answers
285 views

What is the difference between Consensus and Leader Election problems?

According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'. Based on the above quote, my question is: What is the difference between ...
4
votes
1answer
223 views

Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle

On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $...
3
votes
1answer
476 views

Difference between sequential and parallel divide and conquer

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy In divide and conquer, we ...
0
votes
0answers
25 views

How would be a query where its operators are NOT worth to execute in parallel?

I would like to have an example of a query for database or a dataflow program in spark (or any stream processing system) that is not worth to parallelize at least one of its operators. The insigth ...
2
votes
1answer
35 views

Binary Tree Multithreaded Time Complexity

Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then ...
4
votes
3answers
14k views

Can/Do multiple processes run simultaneously on a multi-core system?

I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run ...
9
votes
2answers
206 views

What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?

In Girard's Proofs and Types we can read : From an algorithmic viewpoint, the sequent calculus has no Curry-Howard isomorphism, because of the multitude of ways of writing the same proof. This ...
0
votes
1answer
53 views

Parallel Algorithm for Data Averaging

I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
1
vote
0answers
35 views

How much of the x86 instruction set does blender use? [closed]

I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
0
votes
1answer
554 views

Amdahl's law of processors (infinite processors to test limits of speedup)

My processor noted that an infinite number of processors will allow me to test how much speedup I can achieve. I am not exactly sure how this applies. For instance, let's say I have a program that ...
3
votes
1answer
303 views

Amdahl's Law and Computer Science

I would like to learn more about Amdahl's Law and other similar topics. In what branch of computer science would one place Amdahl's law? Could someone point me to a textbook or further reading (...
2
votes
1answer
510 views

Questions about Amdahl's law?

Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly ...
1
vote
0answers
8 views

$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?

We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
0
votes
0answers
77 views

cache coherence: false sharing vs. memory coalescing CPU vs GPU

False sharing is defined on CPU as when atleast two cores write to the same cache line. If the two cores have their own private caches, one will invalidate the other's cache line when they write to ...
1
vote
1answer
591 views

About hardware multithreading

I'm reading Multithreading (computer architecture) - Wiki, aka hardware threading, and I'm trying to understand the second paragraph: (p2): Where multiprocessing systems include multiple complete ...
6
votes
1answer
76 views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”: decreased transistor size (...
5
votes
2answers
368 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
0
votes
1answer
25 views

Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?

I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement ...
0
votes
1answer
59 views

What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?

I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 ...