Tagged Questions

Questions about algorithms or programs that compute on multiple processing units simultaneously. Not to be confused with concurrent or distributed computing!

7 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 ...
54 views

How do i proceed with writing the algorithm? What will be the run time of the algorithm?

Given an n x n matrix which is to be multiplied with a vector of size 1 x n, write a algorithm for the purpose with 1-D partitioning of the input matrix along with one element of the vector per ...
11 views

Difference between RMW and Atomic registers

I am trying to understand the difference between Atomic and RMW Registers! What is the main difference? I know that operations read and write on atomic registers happens in a point in time! But I ...
32 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 ...
89 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, ...
58 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 ...
18 views

Self Stabilization - Digital Clock Sync

I'm trying to understand the correctness of the following algorithm, taken from this Self Stabilization book: ...
26 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 ...
43 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 ...
48 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 ...
33 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 ...
26 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 ...
13 views

Parallell modeling with limited time

I have a NP-problem with a parameter of difficult called s. When s grows the difficulty of solve the problem grows exponentially. I have a supercomputer of N nodes and I want to get the speedups when ...
36 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,...
30 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 ...
155 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 ...
36 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....
50 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 ...
81 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 ...
46 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?
18 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 ...
39 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 ...
43 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 ...
40 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 ...
26 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 ...
43 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 ...
23 views

Who said: you need to send few messages over the network and they need to be as small as possible so that a distributed application scales up?

I wonder if there is a well known law or scientific article to cite for this. I am writing a manuscript and I am looking for the right reference. Is there something like the Amdahl's law saying that? ...
368 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 ...
70 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 ...
43 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?
7 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 ...
37 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 ...
29 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 ...
70 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, ...
77 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 ...
211 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 ...
65 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 ...
41 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 ...
68 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 ...
31 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 ...
29 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 ...
70 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 ...
75 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 "...
105 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 ...
62 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?
69 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 ...
56 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 ...
47 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 ...