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
1
vote
1answer
30 views

Analyze Speed Up in A Dispatcher-Woker Model

In a Dispatcher-Worker model of parallel computation, we have $N$ worker machines simultaneously working on the task (for example, computing the checksum of network packets). There is no ...
1
vote
1answer
466 views

Why does the map function in MapReduce take two parameters?

I am playing around with MapReduce and wanted to ask why the map function takes two inputs (key, value)? Why not just pass along ...
1
vote
1answer
1k views

What is Pointer Jumping ?

Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?
1
vote
1answer
541 views

A question about parallel algorithm complexity

When in a Parallel algorithm we say: "This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $...
1
vote
1answer
167 views

Using Loop Dependence analysis for vectorization

How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?
1
vote
0answers
9 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
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....
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 ...
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 ...
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 ...
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 ...
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?
1
vote
0answers
59 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 ...
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:...
1
vote
1answer
71 views

Efficiently compute parallel matrix-vector product for block vectors with FFTs?

Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product $$w = (E\otimes I_N)v$$ ...
1
vote
1answer
49 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 ...
1
vote
0answers
148 views

'if' and 'while' statements within a SIMD architecture and its memory architecture

I am doing some past exam papers and I found two interesting questions which I cannot answer due to them not being extensively covered in the lecture notes given to me by my lecturer. The questions ...
1
vote
0answers
91 views

Design considerations for a language to support automatic parallelization [closed]

Automatic parallelization isn't a new thing by any means, and lots of questions have been asked about whether Java or C or C++ or a host of other languages or specific compilers (gcc 5 v 6, clang, ...
1
vote
0answers
286 views

Matrix Vector Multiplication Parallel

CLRS book has the following algorithm for parallel for matrix vector multiplication My problem is, can't we use a simple approach like this, ...
1
vote
0answers
44 views

Largest parallelization speedup for multiplication of very large numbers

I have recently come across the following papers: S. Baktir and E. Savas. Highly-parallel Montgomery multiplication for multi-core general-purpose microprocessors. In E. Gelenbe and R. Lent, editors, ...
1
vote
1answer
82 views

What information needs to be saved in a Lamport clock system to deduce message causality?

By using Lamport timestamps, we can determine the causality of messages. It is however unclear to me how one would deduce this simply from the lamport timestamp of the message. Take the following ...
1
vote
0answers
131 views

Broadcast Problem Algorithm In Parallel Computing In Mesh, Complete Tree and Hypercube Structures [closed]

Can anyone please help me design an algorithm to solve the broadcast problem in parallel for the structures mentioned?
1
vote
0answers
73 views

Parallel algorithm for Chinese remainder theorem

What is the most efficient (in terms of running time) algorithm that solves the Chinese remainder theorem (CRT) on a set of integer residues. That is, given a set of moduli $\{m_i\}_{i=1}^{r}$ and set ...
1
vote
0answers
1k views

Scheduling a dependency graph for parallel computing

Background: I have a dependency graph, i.e. a directed graph where the nodes are tasks and the edges are dependency relations. Moreover, nodes are assigned a weight since they take different amount ...
1
vote
0answers
59 views

Communication senario: A sends to B or B sends to A

Consider processes A and B and the situation where either A will send a message to B or B will send a message to A. Is there a standard algorithm for this scenario that makes sure that exactly one of ...
1
vote
0answers
52 views

How to partition a digraph for later parallel computation? [duplicate]

I have a directed graph where all the nodes represent some task that needs to be computed. I need to compute the order of these tasks and also detect any cycles. Running Tarjan's algorithm on the ...
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
0answers
617 views

Why does response time increase with throughput? [closed]

I'm seeing this pattern that the response time increases as throughput increases, and that the throughput has a peak after the response time starts rising. This seems counter-intuitive. It seems like ...
1
vote
0answers
173 views

Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the ...
1
vote
0answers
171 views

Understanding the correctness of the Euler Tour Technique

I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia: Given an undirected tree presented as a set of edges, the Euler tour ...
1
vote
1answer
127 views

How does “do in parallel” work

currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense ...
1
vote
1answer
2k views

Parallel algorithm for LU-decomposition

I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets. So, could you, please, recommend me some parallel algorithms ...
1
vote
0answers
445 views

Parallel single source shortest path algorithm

Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ (i.e.,...
1
vote
1answer
82 views

Heterogenous and Asymmetric Computing's differences

The definition of the both architecture looks pretty same. They are parallel computing architecture with different type of cores. What distinguish their definition, actually?
1
vote
0answers
68 views

fastest way to compute scalar product of an ensemble of vectors

I have an ensemble of points in 3D space, represented by their coordinates $\mathbf{c_i}\equiv(x_i,y_i,z_i)^\top$ . I need to calculate the distance between all these points: $\quad\forall i,j\quad ...
1
vote
0answers
304 views

What makes neuromorphic computing architecture more efficient than von Neumann

What makes neuromorphic architectures more efficient (less heat and power consumption) than von Neumann architecture for complex tasks? Except inspiration from biological systems, what are some formal ...
1
vote
0answers
64 views

Vectorizing and Array Notation?

I'm really trying to wrap my head around vectorization but I can't seem to understand it. I don't know if I don't understand how to vectorize, or if I don't understand the array notation that's being ...
0
votes
1answer
211 views

Does Amdahl's law apply to modern multi-code processors?

I was reading about Amdahl's law and it state that value of Amdahl's law always lies between 0 and 1. My question is, is it still true in today's case/scenario? When we have system like core i7?
0
votes
1answer
270 views

Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched ...
0
votes
1answer
39 views

Can I assume that a percentage of the time can be parallelized?

I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and ...
0
votes
2answers
960 views

Understanding Gustafson's Law

Wikipedia says about Gustafsons's law that: It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases. I'm not understanding how $\alpha$ can ever change ...
0
votes
1answer
133 views

Amdahl law and parallelism

I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and ...
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
2answers
882 views

What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
0
votes
1answer
85 views

What would be the over all speed-up achieved?

Suppose we are using a dual core processor and we run 2 applications (1 with 80% resource requirements and the other with 20% resource requirements).Now the first program is parallelizable for 40% and ...
0
votes
2answers
489 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
0
votes
1answer
118 views

What are current approaches to auto-parallelisation?

I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.
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
1answer
565 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 ...
0
votes
1answer
46 views

How can I take advantage of the capabilities of a cluster [closed]

I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that ...