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
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 ...
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
21 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 ...
1
vote
2answers
54 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
1answer
36 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 ...
0
votes
0answers
16 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
26 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: ...
3
votes
2answers
90 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
64 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
43 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 ...
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
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
1answer
78 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
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 ...
1
vote
3answers
88 views

How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
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 ...
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....
0
votes
0answers
60 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
19 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. ...
0
votes
0answers
43 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
23 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
27 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
0answers
49 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
78 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 ...
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 ...
0
votes
1answer
507 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
0
votes
0answers
14 views

What is the difference between parallel virtual machine and message passing interface. And how both works [duplicate]

I m learning beowulf system architecture and I encounter these terms many time. I know these are the library file and we use these to write parallel programing. But I do not know how these work and ...
0
votes
1answer
208 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 ...
2
votes
2answers
93 views

Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
0
votes
1answer
44 views

When do we use parallel algorithms for enumerating combinations?

I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used? Here is a famous example of parallel algorithms, Adaptive and ...
3
votes
1answer
78 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 ...
2
votes
2answers
558 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
254 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
669 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 ...
2
votes
1answer
79 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
38 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
109 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
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?
0
votes
1answer
87 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 ...
1
vote
1answer
902 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 ...
7
votes
1answer
151 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
29 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
72 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
57 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
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
2 3 4 5 6