Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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!

1
vote
0answers
20 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 ...
1
vote
2answers
33 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
117 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
276 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
23 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
20 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
28 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
37 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
26 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
35 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
182 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
71 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
22 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
41 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
41 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
55 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
87 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
1
vote
0answers
20 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
22 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 ...
0
votes
0answers
19 views

Generalization of Parallel Computing Architectures, Multi-Agent Architectures, and Cellular Automata

This question is for resource or explanation generalizing or simplifying the ideas of parallel computers, cellular automata, and multi-agent architectures. I am interested in the requirements for ...
4
votes
0answers
32 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
55 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 ...
4
votes
0answers
40 views

Symbolic Math Systems As Speculative Optimization For Numerical Software?

Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations? Real world ...
1
vote
1answer
35 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
31 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
34 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
68 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
42 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
39 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
99 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
389 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
142 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
72 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
292 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
120 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
3k 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
121 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
49 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
43 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
265 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
99 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
32 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
430 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
38 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
82 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
688 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
43 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
56 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 ...