Stack Exchange Network

Stack Exchange network consists of 174 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
votes
0answers
12 views

RAM or SSD to improve the performance of Parallel Computing Toolbox Matlab [on hold]

My laptop model is Omen Bang & Olufsen with 4GB RAM and 1TB HDD. When I run programs (47927632 no. of arrays) in Matlab Parallel Computing Toolbox, the laptop freezes and I was forced to hit the ...
1
vote
0answers
27 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
31 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
5 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
22 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
25 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
39 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 ...
5
votes
1answer
64 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
0answers
28 views

Are there any problems that are hard to solve in parallel and whose solutions are easily verifiable?

It is easy to come up with problems that are either hard to solve in parallel or that are easily verifiable, but I don't know of any that are both. Example hard to solve in parallel but NOT easily ...
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
37 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
36 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
65 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
16 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
17 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
31 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
52 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
39 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
28 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
33 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
67 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
38 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
73 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
318 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
134 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
64 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
233 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
103 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
2k 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
100 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
45 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
255 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
97 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
374 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
35 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
73 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, ...
5
votes
1answer
642 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
34 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
55 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
395 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
30 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
98 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
398 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 ...