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!
347 questions
2
votes
1
answer
93
views
can Strassen's matrix multiplication algorithm be parallelized?
Just want to check when you parallize Strassen's algorithm you get a time complexity of $O(\log n )$ because you divide and conquer $\log n$ times in parallel and a space complexity of $ O( n^{\...
- 21
1
vote
0
answers
91
views
merge three ordered sequences with compare-exchange elements
I have been revisiting selection networks with compare-exchange elements (CEs), in particular with K. Cong et al.: "Revisiting Oblivious Top-𝑘 Selection with Applications to Secure 𝑘-NN ...
- 1,194
0
votes
0
answers
48
views
How can we include the missing values in our computation?
Please refer to the paper Migacz, S., et al. (2019). Parallel implementation of a sequential Markov chain in Monte Carlo simulations of physical systems with pairwise interactions. Journal of Chemical ...
- 49
0
votes
0
answers
47
views
Static two-issue RISC-V pipeline: how is this sd and blt data hazard handled?
I was following through this example (From the subheading Simple Multiple-Issue Code Scheduling in chapter 4.10 of
Computer Organization and Design RISC-V Edition by
Hennesy, Patterson), an example ...
- 1
0
votes
0
answers
85
views
Is checking GCD in NC or strongly P?
Given two integers $m$ and $n$ computing $\mathsf{GCD}(m,n)$ is not known to be either in $NC$ or in strongly Polynomial time.
Given three integers $m$, $n$ and $g$, is testing $g=\mathsf{GCD}(m,n)$ ...
- 2,957
0
votes
1
answer
88
views
Need a book recommentation for converting a sequential program into a parallel
Suppose I have a sequential program of biological, physical, or chemical simulation.
I need a step-by-step algorithm for translating that sequential program into a parallel program.
Can you recommend ...
- 49
0
votes
1
answer
74
views
Find the minimum number of send/recv actions in directed communication graph
Given p processes and n packages. Every process contains k = n / p distinct packages. Now, I ...
- 101
1
vote
1
answer
108
views
Are WAR and WAW hazards only possible if we have parallel computing
I was reading on WAW and WAR data hazards and I think that these can only happen if we have parallel computing ,in contrast with RAW data hazard which can happen even if we dont have parallel ...
- 141
0
votes
1
answer
244
views
How is possible to the computer make multiple downloads at same time
My intuition is that the computer is receiving parts a little part of every download, so if I am download three files i receive like , part 1 file one , part 1 file two , part 2 file one ...
This ...
- 5
0
votes
1
answer
87
views
Complexity of Scheduling n Tasks on m Machines with Identical Execution Times, Dependencies, and Time Lags
This is a scheduling problem with $n$ tasks across $m$ machines. Tasks have dependencies (DAG) and can be divided into two types: A) need resources $R$ and have an identical execution time. B) do not ...
- 1
0
votes
2
answers
117
views
Calculating the Maximum Speedup for a Program with Sequential and Parallel Components
A program $P$ consists of two methods: one sequential, which takes $ n + 15050 $ seconds to execute, and another that can be parallelized with full efficiency, taking $\frac{n^2}{100p}$ seconds, where ...
- 1
1
vote
2
answers
146
views
Can multi-threading help improve an IO-bound process perforamance?
I am trying to understand the difference between CPU Bound vs IO Bound process. ChatGPT suggested that multi-threading/parallel processing can help CPU bound process; However, I think that having ...
- 149
3
votes
1
answer
127
views
Parallel prefix sum/scan on trees
Let $T$ be a rooted, finitely branching tree, with values from $A$ in its nodes; $T(j)$ is the value of a node called $j$. $A$ is a commutative monoid. The "bottom-up scan tree" of $T$ is a ...
0
votes
1
answer
424
views
Cumulative sum algorithm that worked on parallel computing
Compared to "vectors addition" which can naturally work independently for the summation of each of its corresponding elements, it allows parallel work by processors. Example:
...
2
votes
2
answers
318
views
Why bisection width of star connected network is 1?
This may seem like a simple question, but I can neither find the answer on the internet nor AI tools can give a proper answer. I was reading a book about static networks and I saw that the bisection ...
- 21