Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
1answer
88 views

Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph. Karloff [1, p.6] has given a map-reduce algorithm called "...
0
votes
1answer
60 views

Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size." I think that this may be missing a constraint....
0
votes
1answer
1k views

Hadoop MapReduce Word Counting Example [closed]

In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number of ...
0
votes
1answer
230 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
1answer
56 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
1answer
45 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: ...
0
votes
1answer
415 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: ...
0
votes
1answer
4k 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 ...
0
votes
1answer
250 views

How does data travel in a butterfly network?

I'm trying to learn how communication works in a butterfly network. The following is a butterfly network of order 3. I'm given the following description: Each processor is connected to an output ...
0
votes
1answer
527 views

Designing a parallel algorithm to find the second largest item in an array

Using pseudocode, I need to design a parallel algorithm that, when given k keys, a[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it. I'm new to ...
0
votes
1answer
96 views

Complexity class for concurrent algorithms

We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way? Motivation: A sequential algorithm may be O(n7) but its parallel ...
0
votes
1answer
52 views

Can any algorithm efficiently be implemented as a SIMT problem?

Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions. Excluding overhead due to hardware limitations (specifically, memory copy ...
0
votes
1answer
732 views

Possible results of two programs running on a symmetric multicore system

This question is from Patterson and Hennessy's Computer Organization and Design. Consider the following portions of two different programs running at the same time on four processors in a ...
0
votes
1answer
72 views

How is out-of-order instruction execution related to superscalar execution?

How is out-of-order instruction execution related to superscalar execution? How is data hazard detection and handling affected by superscalar execution?
0
votes
1answer
51 views

Register Transfer Activity

In a simple architecture(not considering parallel architecture) how exactly this can be performed in a single clock cycle: P:R1 <- R2, R2 <-R1 where R1 and R2 are registers and P is a control ...
0
votes
1answer
155 views

Parallel shortest path in directed acyclic graphs

Finding the shortest path in a DAG is extremely easy: See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf However, I cannot find a way of parallelising this code. Is ...
0
votes
1answer
100 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $...
0
votes
0answers
9 views

How can I study about GotoBLAS or OpenBLAS in detail? [on hold]

I want to study about GotoBLAS and OpenBLAS. Where can I find these libraries and on what languages do I need to have command to analyze these libraries?
0
votes
0answers
12 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
3answers
40 views

How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
0
votes
0answers
13 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
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
40 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
45 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
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
168 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
1answer
42 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 ...
0
votes
0answers
58 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
84 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
1answer
27 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
0answers
46 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
64 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.
0
votes
0answers
115 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
33 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). ...
0
votes
0answers
99 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, ...
0
votes
0answers
33 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 ...
0
votes
0answers
29 views

About models for parallel algorithms

Is there a difference between an execution model and a computation model? Or the two terms refers to the same things? Thanks in advance.
0
votes
0answers
60 views

Keywords for the science articles search (parallel computing)

Often, similar ideas or works have vastly different namings or covers. This is a hassle for searching in distant fields, especially in a non-native language. Idea. We mathematically model (Petri ...
0
votes
1answer
132 views

Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair

What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?
0
votes
0answers
27 views

What does it take to massively parallelize a flow matrix equation?

I'm not a scientist nor am I math savvy, but I'd like to know what the feasibility would be of solving a shallow water flow equation using massive parallelization. CUDA and stuff like that. Im ...
0
votes
1answer
96 views

Is it correct to say that CPU's only compute threads?

New to the world of parallel computation. Would it be correct to say that CPU's are actually thread calculators? My understanding currently: a ...
0
votes
1answer
442 views

Fine-Grain parallel algorithm for LU-decomposition

How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the min(i; j) - 1, because I have no idea, what ...
0
votes
0answers
327 views

Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
0
votes
0answers
70 views

Describing monitors and semaphores in terms of the three properties of critical section problem solutions

Solutions to the critical section problem exhibit three properties: mutual exclusion, progress, and bounded waiting. When do we say, or do we at least say, that operating system-implemented semaphores ...
0
votes
0answers
67 views

Is k-means parallelizable (other than the data parallelism of the distance function computation)

The k-means algorithm is known to be NP-hard. While the distance function computation in the algorithm loop is data parallel, the algorithm is iterative and may become exponential in the number of ...
0
votes
1answer
62 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 ...
0
votes
1answer
2k views

Preparing precedence graph from fork and join code

I was referring to this page which defines fork, join and precedence graph as follows: When the statement ...