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
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
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
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 ...
0
votes
1answer
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: ...
1
vote
0answers
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 ...
2
votes
1answer
585 views

Questions about Amdahl's law?

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 ...
3
votes
3answers
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 ...
1
vote
0answers
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, ...
0
votes
1answer
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: ...
1
vote
1answer
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). ...
-1
votes
1answer
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 ...
0
votes
1answer
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?
0
votes
0answers
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.
2
votes
1answer
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....
1
vote
0answers
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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). ...
1
vote
1answer
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 ...
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, ...
0
votes
0answers
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, ...
6
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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] $$ ...
1
vote
1answer
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 ...
9
votes
2answers
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 ...
3
votes
1answer
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 ...
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?
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
5
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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.
0
votes
1answer
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[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it. I'm new to ...
1
vote
0answers
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 ...
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
11
votes
3answers
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 ...
3
votes
1answer
648 views

Implement K-means clustering with Map-Reduce

Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around ...
0
votes
1answer
2k views

Preparing precedence graph from fork and join code

I was referring to this page which defines fork, join and precedence graph as follows: When the statement ...