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!
259
questions
1
vote
1answer
38 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 ...
-1
votes
0answers
12 views
what is usage example of SIMD , MISD , MIMD?
i need example of use SIMD , MISD , MIMD
like SIMD Used For Vector SuperComputer
but i can't know anther ( MISD , MIMD ) uses example
only i know about them it's Definition only
-1
votes
0answers
15 views
Mapping d-mesh to 2^d hupercube
What is the function that maps a d-dimensional grid to a 2^d dimensional hybercube?
Thanks in advance!
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
12 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
46 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
54 views
How much can matrix multiplication algorithm be parallelized?
You all may know that simple Matrix Multiplication algorithm:
...
0
votes
0answers
15 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
19 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
48 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
41 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
16 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
24 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
46 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
36 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
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
26 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
276 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
171 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
87 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
43 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
64 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
388 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
230 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
575 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
45 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
36 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
78 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
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
1answer
58 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 ...
0
votes
0answers
87 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
718 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
77 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
27 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
62 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
52 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
60 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
138 views
1
vote
0answers
28 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
47 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
42 views
Is it possible to implement 64-bit cmpxchg from 32-bit cmpxchg?
Question
Given a 32-bit cmpxchg operation as a primitive:
...
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 ...
