# 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!

264 questions
Filter by
Sorted by
Tagged with
53 views

### How to partition a digraph for later parallel computation? [duplicate]

I have a directed graph where all the nodes represent some task that needs to be computed. I need to compute the order of these tasks and also detect any cycles. Running Tarjan's algorithm on the ...
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 ...
103 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 ...
567 views

### Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...
664 views

### Implement K-means clustering with Map-Reduce

Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around ...
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 ...
62 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 ...
255 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, ...
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 ...
397 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 ...
609 views

### Both shared-memory and distributed-memory

As you see in the following picture its a shared-memory architecture which has been modeled in a form of complete graph. Why we can consider the following architecture (which is a complete graph) both ...
92 views

### Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
299 views

### Supercomputer Configuration

I think I understand how supercomputers work in general, but I would like to know how they are configured. It seems to me that supercomputers have a separate computers at each node, each with it's ...
107 views

### How do I find the intersection of subgraphs in a directed acyclic graph efficiently?

I have a directory structure in which each directory can have multiple parents (IOW, a cd .. is ambiguous). AFAICS this means this is equivalent to a directed ...
423 views

### How to simulate a parallel computer (with certain number of processors) on a serial computer

I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example,...
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 ...
2k views

### CPU and GPU differences

What is the difference between a single processing unit of CPU and single processing unit of GPU?  Most places I've come along on the internet cover the high level differences between the two. I want ...
102 views

### PRAM with no bit operations and P vs NC

I was reading up on something called the PRAM model without bit operations. What exactly does it mean that this PRAM model cannot do bit operations? I can't find a straightforward definition anywhere....
652 views

### Converting Boolean circuit to Boolean formula in parallel

Let t be a fixed constant. I would like to convert a Boolean circuit C of depth t on n inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula F on the same n inputs, in ...
8k 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 ...
154 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 ...
846 views

### Computing the intersection of N sets over an M-element universe

Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$. 1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$? 2.) I am also looking for a good parallel and a good ...
49 views

### Communication allowed in the NC^i model?

I want to verify if I am correct in my interpretation of the $\mathrm{NC}^i$ model. In this model the input is given to at most $O(n^k)$ processors and each processor takes at most $O(\log^i n)$ time ...
115 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 ...
87 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 ...
102 views

### Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
3k views

### Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
809 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?
12 views

### How do balancers work in the context of counting and balancing networks?

I was learning what balancing networks are and at some point the art of multicore programming talks about balancers. The text book says: A balancer is a simple switch with two input wires and two ...
48 views

### What does it mean to have tokens at a state in a balancing network?

I was assigned as homework: Suppose we have a width-w balancing network of depth $d$ in a quiescent state $s$ called $B$. Let $n = 2^d$. Prove that if n tokens enter the network on the same ...
43 views

### Why is the step property in a balancing network defined as it is?

I was trying to understand why the equation $y_i = \left( \frac{n}{w} \right) + (i \pmod w)$ describes the step property in a balancing network? First, recall $x_i$ to be the number of tokens a ...
310 views

### Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
290 views

### Is “flops” a reliable measure of deciding computational capacity?

Is "flops" a reliable measure of deciding computational capacity? If we do matrix multiplication and matrix addition of the same size of matrix, do the flops remain the same? Referring to question ...
517 views

### Can every program be parallelized infinitely and automatically?

In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible. And as I have read ...
92 views

### Algorithm for executing a command against a million hosts

Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the ...
96 views

### Complexity of calculating average across distributed network?

What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over ...
375 views

### What is a swap-with-memory instruction?

I am reading an article on algorithms for parallel computing and came across the following sentence. What do they mean by a swap-with-memory instruction? Our algorithm provides reasonable latency ...
47 views

### How can I take advantage of the capabilities of a cluster [closed]

I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that ...
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 ...
573 views

### Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched ...
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 "...
228 views

### Are there any non-naive parallel sparse matrix multiplication algorithms?

I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
83 views

### Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
437 views

### solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
173 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 ...
73 views

### Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear. Given the following ...