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!
260
questions
0
votes
0answers
16 views
How do i tell if a network is not sorting network? [duplicate]
For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?
0
votes
0answers
20 views
How do I calculate the work for a parallel algorithm?
I have problem (for HW) which asks to find a sequential and parallel algorithm to check if a given set of cubes is stacked on top of each other or not. The conditions provided are that the stacks must ...
0
votes
0answers
19 views
Broken Parallel Prefix Sum Algorithm
The following is pseudocode for a cost-optimal prefix sum parallel algorithm, where n = problem size (16), p = number of processors (4), and log is base 2:
...
3
votes
2answers
73 views
Why the most dominant programming languages didn't follow CSP thread model?
I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please ...
0
votes
1answer
50 views
Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?
So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
1
vote
1answer
41 views
How do I use message passing to find the maximum of all values in a grid?
I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
2
votes
0answers
31 views
When concatenating two sequences, can evaluations of two input sequences be in parallel with each other?
In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf),
37.3 Multiple Fork-Join
So far we have confined attention to binary fork/join parallelism ...
1
vote
0answers
16 views
What is inner kernel in context of BLAS libraries
I was reading about BLAS (Basic linear algebra subsystem) and I frequently encountered the term "inner kernel". What does it mean by "inner kernel"?
1
vote
1answer
68 views
Finding minimum in PRAM model
Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.
0
votes
0answers
12 views
What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?
Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and ...
1
vote
3answers
75 views
How much can matrix multiplication algorithm be parallelized?
You all may know that simple Matrix Multiplication algorithm:
...
0
votes
0answers
16 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 ...
1
vote
0answers
21 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?...
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
55 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. ...
0
votes
0answers
43 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
19 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
26 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
0answers
48 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)
0
votes
1answer
59 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 ...
2
votes
0answers
29 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
27 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 ...
0
votes
1answer
440 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 ...
0
votes
1answer
194 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 ...
2
votes
2answers
91 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 ...
0
votes
1answer
44 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
69 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 ...
3
votes
1answer
78 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 ...
2
votes
2answers
474 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
243 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
649 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 ...
2
votes
1answer
68 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 ...
1
vote
0answers
38 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 ...
3
votes
1answer
90 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 ...
1
vote
0answers
9 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
1answer
78 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
1answer
832 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
78 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 (...
0
votes
1answer
29 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
69 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 ...
2
votes
2answers
54 views
Why is the sequence, “1,3,2,4”, not a bitonic sequence?
A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.
According to the definition of a bitonic sequence, we know that a graph of a ...
3
votes
2answers
1k views
Why is the sequence “3,3,4,5,2” considered a bitonic sequence?
Why do we consider the sequence "3,3,4,5,2" a bitonic sequence?
In the sequence, "3,3,4,5,2", the sequence is
constant for "3,3",
increasing for "4,5", and
decreasing for "5,2".
1
vote
0answers
61 views
How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)
I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...
3
votes
0answers
148 views
1
vote
0answers
30 views
How to Simulate Nested Parallelism on a Sequential Machine
So I have sets of functions $A$, $B$, $C$, $D$, $E$, and $F$. I want to run them in a nested way. I also want to run some of them in parallel, and some of them in sequence. Here is how that might look:...
0
votes
0answers
49 views
Hierarchical Parallel Processing Machines
Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking ...
4
votes
0answers
44 views
Is it possible to implement 64-bit cmpxchg from 32-bit cmpxchg?
Question
Given a 32-bit cmpxchg operation as a primitive:
...
