# 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!

258 questions
Filter by
Sorted by
Tagged with
39 views

### deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

Thanks a lot for your help. I want to understand what really causes what I suppose to be a deadlock: I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t ...
46 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 ...
36 views

### Is there a name for “yield first result parallel map”?

Context In randomized algorithms two schemes of computation are common: Las Vegas algorithms with random running time Randomized algorithms that have a probability of success, and have to be ...
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$$ ...
50 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 ...
46 views

### Loop Transforms to Increase Parallelism

I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm: ...
177 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 ...
585 views

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 ...
163 views

### Is there a generic way to parallelize algorithms?

Take: An algorithm $A$ that is analytically nice in some way, say, for some class of inputs of length $n$ it runs at $O(f(n))$ on some Turing machine. $k+2$ independent, identical such machines. Is ...
95 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, ...
435 views

### What are thin-core and fat-core processors

I am reading a paper called Back to Thin-Core Massively Parallel Processors by Ami Marowka (Computer, 44(12):49–54, 2011; IEEE Xplore). However I have a question about the title of the article: ...
186 views

### Understanding commutativity and associativity for primitive types

In Elements of Programming Interviews, authors talk about a tip for understanding how to use primitive types (int, double, etc). ...
5k views

### How do I calculate the speedup properly?

I am trying to calculate the speedup of this, but I am getting the wrong answer: Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
230 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?
65 views

### What's the practical use of pack/unpack and gather/scatter?

In parallel programming, what is the practical use for pack/unpack and gather/scatter? I searched for practical examples and didn't find any use of those.
51 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....
292 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, ...
116 views

### How well is Moore's law (and it's cousins) holding up?

I came across a set of articles back from the 2000s that stated Intel was planning a 10Gz CPU by 2011. Obviously, this didn't pan out. But how well are Moore's law and it's cousins holding up in terms ...
34 views

### What's a good method to decide wheter distributed or parallel computing?

I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
624 views

### Calculate execution time from linear speedup

Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores? (Assuming Gustafson's law, or in other words, $t(\infty)=0$) My ideas: I ...
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, ...
102 views

### Are there parallel algorithms that give more than linear speedup?

I'm wondering if there are any parallel algorithms whose runtime is not linearly dependent on processor count. (Assuming the problem-size remains constant for different processor counts) For example, ...
1k views

### What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
94 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 ...
74 views

### Stochastic Computing: What is “Bundle Processing”?

I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says: Bundle Processing involves sending a fixed number of bits instead of a stream. One of the ...
598 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 ...
33 views

### Comprehend parallel programming

I'm asking the question on the behalf of my classmates. We have a trouble about parallel programming that we can't comprehend threads, semaphores, forks and etc. We have been taking third time the ...
105 views

### Parallel or efficient computation of value with momentum

I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that: $$A'_{i,j} = \alpha A'_{i,j-1} + (1 - \alpha) A_{i,j} \\ 1 \leq i \leq M, 1 \leq j \leq N, \alpha \in [0, 1]$$ ...
582 views

### Conway's Game Of Life Problem Parallel (OpenMP)

I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course. The problem is a little bit different form the original, in the sense that instead of ...
211 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 ...
47 views

### Gate/transistor number and program length measures of computational complexity?

Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity? For example, problems are characterized by O(.) measures ...
131 views

4k views

### how can i find the Maximum Degree of Concurrency?

i'm studying Parallel Processing , and i'm confused how can i calculate the max number of concurrency in a given dependency graph ? i know that the maximum number of concurrency is the largest ...
596 views

### How on-chip multithreading prevents cache misses from stalling a processor pipeline?

On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids ...
2k views

### Why weak scaling is easier to achieve than strong scaling?

When we parallelize tasks and measure the perforamnce,two common measures of parallel scaling are Strong Scaling: Time for fixed problem size as number of processor is increased Weak Scaling: Time ...
794 views

### How to “convert” nested loops into code taking advantage of parallel computing?

Let's say that an algorithm uses several nested loops to accomplish it's task, for instance : An algorithm treating voxels on several frames, so there would be four dimensions : t (for time), x, y ...
407 views

### How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?

I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for ...
76 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 ...
876 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 ...
262 views

### How does data travel in a butterfly network?

I'm trying to learn how communication works in a butterfly network. The following is a butterfly network of order 3. I'm given the following description: Each processor is connected to an output ...
29 views

### About models for parallel algorithms

Is there a difference between an execution model and a computation model? Or the two terms refers to the same things? Thanks in advance.
549 views

### Designing a parallel algorithm to find the second largest item in an array

Using pseudocode, I need to design a parallel algorithm that, when given k keys, a, a, a,... a[k-1] stored in an unsorted array a, would find the second largest key in it. I'm new to ...
2k 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 ...
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 ...
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 ...
46 views

### Implications of the class of problems with parallel solutions being not P-complete for optimization of matrices

I am not a specialist on computational complexity theory. I do work on optimization and I am currently researching about the implications of the class of problems with parallel solutions (NC) being ...
99 views

### Complexity class for concurrent algorithms

We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way? Motivation: A sequential algorithm may be O(n7) but its parallel ...
532 views

### Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...