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!

258 questions
Filter by
Sorted by
Tagged with
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 "...
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....
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 ...
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
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 ...
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: ...
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: ...
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 ...
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 ...
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, a, a,... a[k-1] stored in an unsorted array a, would find the second largest key in it. I'm new to ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 \$...
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?
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 ...
40 views

### How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
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 ...
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?...
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 ...
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. ...
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 ...
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)
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
27 views

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 ...
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 ...
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.
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 ...
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). ...
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, ...
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 ...
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.
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...