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!

62 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
2answers
2k views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
6
votes
0answers
485 views

Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
6
votes
1answer
808 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 ...
4
votes
0answers
37 views

Is it possible to implement 64-bit cmpxchg from 32-bit cmpxchg?

Question Given a 32-bit cmpxchg operation as a primitive: ...
4
votes
0answers
42 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 ...
3
votes
0answers
125 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
3
votes
0answers
347 views

Vectorized Algorithm for finding the Shortest Path in a Graph

I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken ...
3
votes
0answers
1k views

“Data-race free” programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all histories $H$ ...
3
votes
0answers
69 views

How is amorphous computing different from spatial computing?

Surely spatial computing and amorphous computing share similarities and overlap. Is spatial computing a subset of amorphous computing? How are the two different?
2
votes
0answers
28 views

What does it mean by “consistent view of memory” in lock-free dequeue implementation?

I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation. ...
2
votes
1answer
49 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....
2
votes
0answers
1k 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 ...
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 ...
2
votes
0answers
45 views

A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
2
votes
0answers
334 views

Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably close,...
2
votes
0answers
72 views

Why is this execution happens-before consistent?

In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency. The trace is shown in the figure in which $A$ and $B$ are ...
2
votes
0answers
71 views

EXPTIME and parallel computing

Can we solve an EXPTIME-complete problem in polynomial time given 2^N processors?(N is the size of input).
2
votes
0answers
57 views

Stream processor definition

I'm looking for an actual definition of a stream processing unit (SPU), preferably sourced. The context is not specifically graphics cards. I can find many, many articles explaining what they contain,...
2
votes
0answers
88 views

Determine interference factors in parallel computing

Parallel processes interfere with each other in many ways, by competing for shared resources such as shared caches, memory, disks, etc. Would it be possible to determine latent factors just with a ...
1
vote
0answers
23 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
15 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
23 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
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
27 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
0answers
136 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
284 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
43 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
0answers
63 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 ...
1
vote
0answers
72 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
58 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
169 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
164 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
0answers
441 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
0answers
64 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
301 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
0answers
11 views

APSP on GPGPU with paths reconstruction

There is a huge number of works on efficient solution of all-pairs shortest paths (APSP) by using GPGPU. But the main goal of these works is to compute the length of the shortest path. Are there exist ...
0
votes
0answers
15 views

Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
0
votes
0answers
47 views

What is the complexity class of exponential parallelism?

Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel. How does one capture that in a proper formalism? Is there some ...
0
votes
0answers
37 views

Proof of lemma from Hong's article about multi-threaded max flow algorithm

I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem. Lemma 3. Any trace ...
0
votes
0answers
40 views

Construction of Omega Network

I understand that we could draw N * N Omega Network, But can we draw an Omega Network to connect 6 CPUs to 4 memories? (The number of CPUs does not equal the number of memories)
0
votes
1answer
125 views

All-to-All Broadcast on a Balanced Binary tree

Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree? Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages ...
0
votes
0answers
47 views

Parallel algorithms with desired sequential workload

Could you share any known algorithm which leans on following patterns? These patterns have both multithreaded and sequential workload. Those algorithms need to be joined to complete some sequential ...
0
votes
0answers
25 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 ...
0
votes
0answers
71 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 ...
0
votes
0answers
36 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
62 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.