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
0
votes
0answers
19 views

How does a prefix sum with 8 elements can be computed with three processors?

I would like to know if someone can give me an example of how a prefix sum which contains 8 elements can be computed with just three processors. Prefix sum
63
votes
8answers
67k views

Distributed vs parallel computing

I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
0
votes
1answer
27 views

Thread - contention vs race

The terms contention and race are used interchangeably when it comes to thread's state(at critical section). Are they same?
0
votes
1answer
282 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 ...
1
vote
0answers
16 views

Sorting with high-latency compare

My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational ...
1
vote
0answers
17 views

How to predict the time complexity of matrix multiplication and inverse on a GPU?

Nvidia GPU can speed up the matrix manipulation greatly. I want to have a basic idea to predict the consumed time for matrix manipulation. How can I analyze the time complexity of matrix ...
2
votes
1answer
54 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
19 views

Estimating P in Amdahl's Law theoretically and in practice

In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is ...
1
vote
3answers
124 views
0
votes
0answers
57 views

Finding a parallel algorithm to transpose a matrix

Write a parallel algorithm which runs in $\Theta(n)$ time and transposes an $n \times n$ matrix on the $2D$ mesh SIMD Model with wraparound connections. Processing element $P(i, j)$ has local ...
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 ...
1
vote
0answers
30 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 ...
0
votes
0answers
14 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
26 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
1answer
49 views

Parallel programming models: Why do OpenMP and MPI dominate?

In a lecture on HPC parallel programming (for CPUs) we discussed various models available from Pthreads to OpenMP to MPI and others like Charm++, X10, UPC, Chapel…. The main focus was clearly on the ...
1
vote
2answers
75 views

Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?

I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one ...
0
votes
0answers
18 views

How do i tell if a network is not sorting network? [duplicate]

For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?
0
votes
0answers
28 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
26 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: ...
5
votes
2answers
263 views

is the problem of parallelising any program, NP-complete?

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, ...
3
votes
2answers
110 views

Why the most dominant programming languages didn't follow CSP thread model?

I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please ...
0
votes
1answer
78 views

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
1
vote
1answer
44 views

How do I use message passing to find the maximum of all values in a grid?

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
1
vote
1answer
85 views

Finding minimum in PRAM model

Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.
0
votes
1answer
5k 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
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 ...
1
vote
0answers
19 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"?
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 ...
44
votes
5answers
48k views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
2
votes
0answers
78 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 ...
3
votes
1answer
135 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 ...
0
votes
3answers
2k views

How to find min or max in constant time using infinite # processors?

Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ...
0
votes
0answers
18 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 ...
1
vote
0answers
28 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....
0
votes
0answers
66 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 ...
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 ...
0
votes
1answer
20 views

Are graphic cards using the Map-Reduce model when performing typical gaming rendering

I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. ...
9
votes
2answers
9k views

What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?

In parallel computing, I know the speed up equation is $$ \frac{1}{ s + \frac{1-s}{p} } $$ But what is meant by superlinear speed up? Is it something theoritical? Could you explain it with ...
0
votes
0answers
44 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 ...
1
vote
0answers
26 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 ...
2
votes
1answer
28 views

Parallelization of priority queue-based algorithms

There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-...
0
votes
1answer
92 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
0
votes
0answers
50 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)
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. ...
1
vote
0answers
31 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 ...
2
votes
2answers
159 views

Is automatic multicore support at the hardware or compiler level possible?

Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance. However, multicore ...
5
votes
2answers
3k views

how does the parallel radix sort work?

I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism. ...
3
votes
1answer
889 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
595 views

What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm

1
2 3 4 5 6