# 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
353 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 ...
4k 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 ...
176 views

### Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the ...
178 views

### Understanding the correctness of the Euler Tour Technique

I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia: Given an undirected tree presented as a set of edges, the Euler tour ...
154 views

### Parallel algorithms on a fixed number of processors

Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$. This is great from a theoric point of view, but strange from a practical ...
487 views

### Why are comparisons so expensive on a GPU?

While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the ...
61 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....
170 views

### Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
490 views

### Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
1k views

### Understanding Gustafson's Law

Wikipedia says about Gustafsons's law that: It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases. I'm not understanding how $\alpha$ can ever change ...
449 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 ...
67 views

### Prefix computation used for lexical analysis?

I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms. Several lists of ...
3k views

### Understanding the definition of SPMD

From Wikipedia SPMD (single program, multiple data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. Tasks are split up and run simultaneously on multiple processors ...
937 views

### What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
215 views

### Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
689 views

### How do I calculate response time of a multiple core cpu when given certain information?

On my homework the question asks: A program executes serially in 200 seconds. If it is parallelized, 7 seconds of overhead are required for synchronization, locking, and communication. Compute ...
129 views

### How does “do in parallel” work

currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense ...
2k views

### Parallel algorithm for LU-decomposition

I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets. So, could you, please, recommend me some parallel algorithms ...
376 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 ...
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

### Concurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...
264 views

### Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
254 views

### How do we analyze Algorithms with parallelism features

As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, ...
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 ...
139 views

### Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
450 views

### Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine [closed]

The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part ...
138 views

### BNF and Simultaneous Parsing

Let's say we have the following grammar expr1 ::= ... // Actual definition doesn't matter expr2 ::= ... // expr3 ;:= ... // foo ::= expr1 | expr2 | expr3 ...
2k views

### Why use SIMD if we have GPGPU?

I thought this question is better served in the CS part of Stack Exchange. Now that we have GPGPUs with languages like CUDA and OpenCL, do the multimedia SIMD extensions (SSE/AVX/NEON) still serve a ...
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 ...
854 views

### Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
15k views

### Can/Do multiple processes run simultaneously on a multi-core system?

I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run ...
337 views

### Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably close,...
448 views

### Parallel single source shortest path algorithm

Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ (i.e.,...
266 views

### Emulation, interpreters and parallel execution

I'm interested in how software emulators of old game consoles work. These must consist of an interpreter for the machine language of the emulated processor. If I have understood correctly an ...
1k views

### Is running AES NI in parallel possible (one encryption per core/thread)?

AES NI seems to perform AES operations much faster than doing in software. However, if I have a machine with a large number of cores (say 32 cores), can I perform 32 AES encryptions using AES NI ...
24 views

### How can I find data to compare with my work's results? [duplicate]

My Masters thesis is on task graph scheduling for multi core processors. I have developed a new task clustering and scheduling algorithm. I wanted to know about how can I find data to compare it with ...
492 views

### Superscalar processors and complex instructions

I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia. How do such redundant units work? Is a complex instruction (for accelerating heavy process, ...
110 views

I'm doing a course in Computational Number Theory and am currently looking at algorithms such as Euclid's algorithm, Square-roots modulo a prime, LLL reduction algorithm, McKee's method, Pollard's $p-... 1answer 134 views ### Amdahl law and parallelism I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and ... 1answer 170 views ### Is the way an OS schedule threads related to parallel computing? From Wikipedia: Operating systems schedule threads in one of two ways: Preemptive multitasking is generally considered the superior approach, as it allows the operating system to determine ... 1answer 52 views ### If a thread containing main terminates, can another thread do anything? I'm studying threads in C and I have this theoretical question in mind that is driving me crazy. Assume the following code: ... 1answer 30 views ### Analyze Speed Up in A Dispatcher-Woker Model In a Dispatcher-Worker model of parallel computation, we have$N$worker machines simultaneously working on the task (for example, computing the checksum of network packets). There is no ... 1answer 83 views ### Heterogenous and Asymmetric Computing's differences The definition of the both architecture looks pretty same. They are parallel computing architecture with different type of cores. What distinguish their definition, actually? 1answer 251 views ### How to compare algorithms in class NC time complexity with other classes? I know these relations : \begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i \... 1answer 102 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$...
I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2}$. This matrix $X$ is ...