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!

68 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
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
492 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
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 ...
4
votes
0answers
44 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
43 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
154 views

Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
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
70 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
31 views

When concatenating two sequences, can evaluations of two input sequences be in parallel with each other?

In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf), 37.3 Multiple Fork-Join So far we have confined attention to binary fork/join parallelism ...
2
votes
0answers
29 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
52 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
77 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 ...
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 ...
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
398 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 ...
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
344 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
82 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
73 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
60 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
90 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
27 views

How fast can 10 integer multiplications be executed?

This is self study, but not homework. I am reviewing some slides I found online and have come across the following question. Question: If the latency of integer multiply is $3$ and the cycles/issue ...
1
vote
0answers
17 views

What is inner kernel in context of BLAS libraries

I was reading about BLAS (Basic linear algebra subsystem) and I frequently encountered the term "inner kernel". What does it mean by "inner kernel"?
1
vote
3answers
87 views

How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
1
vote
0answers
25 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?...
1
vote
0answers
24 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
22 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
30 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
9 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
61 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
30 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
213 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
295 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
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, ...
1
vote
0answers
80 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
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
60 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
184 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
179 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
452 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
68 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
312 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
13 views

what is the relationship between increasing the number of cores and scalability?

Whenever I increase the number of cores the speedup will increase. with this increasing can I consider the system as scalable? I mean based on the speedup obtained for a different number of cores e....
0
votes
0answers
20 views

How can I find the max degree of concurrency and the critical path of task dependency graph?

I'm studying Parallel Processing, and I get stuck in how to calculate the maximum degree of concurrency for the task dependency graph. I know that the max degree of concurrency is the largest number ...
0
votes
0answers
25 views

How do I calculate the work for a parallel algorithm?

I have problem (for HW) which asks to find a sequential and parallel algorithm to check if a given set of cubes is stacked on top of each other or not. The conditions provided are that the stacks must ...
0
votes
0answers
24 views

Broken Parallel Prefix Sum Algorithm

The following is pseudocode for a cost-optimal prefix sum parallel algorithm, where n = problem size (16), p = number of processors (4), and log is base 2: ...
0
votes
0answers
13 views

What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?

Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and ...
0
votes
0answers
16 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 ...