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

learn more… | top users | synonyms

-2
votes
0answers
20 views

Mesh and Torus (Degree, Diameter, Bandwidth, edges)

What are the following properties of $M_r,_{{p\over r}}$ Mesh and Torus of p-processor architecture? Degree Diameter Bandwidth Edges number for example, the diameter of a p-processor square Mesh ...
3
votes
1answer
43 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 ...
-1
votes
1answer
30 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 ...
1
vote
1answer
22 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 ...
0
votes
0answers
11 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 ...
0
votes
0answers
34 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 ...
3
votes
0answers
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 ...
5
votes
3answers
137 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 ...
1
vote
1answer
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 ...
1
vote
1answer
42 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 ...
2
votes
1answer
60 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 ...
0
votes
1answer
45 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
17 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
3answers
35 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 ...
2
votes
1answer
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 ...
0
votes
1answer
37 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
25 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 ...
1
vote
1answer
42 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 ...
0
votes
0answers
22 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? ...
3
votes
6answers
318 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 ...
0
votes
0answers
48 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
42 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?
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
66 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, ...
3
votes
1answer
62 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 ...
4
votes
3answers
204 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 ...
3
votes
1answer
60 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 ...
1
vote
1answer
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 ...
1
vote
2answers
61 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 ...
0
votes
1answer
29 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 ...
0
votes
1answer
28 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
67 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 ...
0
votes
1answer
74 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 ...
6
votes
1answer
103 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 ...
1
vote
0answers
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?
4
votes
1answer
65 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 ...
0
votes
1answer
55 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 ...
2
votes
1answer
44 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 ...
0
votes
0answers
274 views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
-1
votes
2answers
290 views

Computer Architecture, specifically Amdahl's Law

I am currently enrolled in a computer organization and design class, which I am struggling mightily with, and I have a final homework in my class that I need to get a perfect score on. The question I ...
2
votes
1answer
109 views

Is multiprocessing possible on a turing machine?

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
1
vote
2answers
68 views

Instruction level parallelism

Can we distinguish instruction level parallelism and SIMD instructions (SSE, 3D now...) ? Or is SIMD instructions one of the multiple ILP techniques ? Thank you.
4
votes
3answers
198 views

Why doesn't parallelism necessarily imply non-determinism?

I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out. I understand the difference between ...
1
vote
1answer
50 views

Is automatic multicore support at the processor level possible?

In the current world, multicore support has to be done by hand as far as I know, with a result being that many processor intensive games and simulations (such as DCS) depend extremely heavily on one ...
1
vote
0answers
170 views

Why does response time increase with throughput? [closed]

I'm seeing this pattern that the response time increases as throughput increases, and that the throughput has a peak after the response time starts rising. This seems counter-intuitive. It seems like ...
7
votes
2answers
409 views

Why can't fibers utilize multiple processors?

It seems that the distinction between fibers and threads is that fibers are cooperatively scheduled, whereas threads are preemptively scheduled. The point of the scheduler seems like a way to make an ...
2
votes
1answer
54 views

Disabeling interrupts to solve critical section issue on multiprocessor system

Assume I have a multicore system and a critical section. I understand how disableling interrupts on a single core systems solves the critical section problem. So assume I could disable interrupts on ...
-1
votes
2answers
537 views

Amdahl's law or gustafson's law

I am a little confused which of the two laws above i should use: Suppose I have a computer program that can be parallelized by 70%. 30% cannot be parallelized. Every single data (100% of data) will ...