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!

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
-1
votes
2answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
6
votes
1answer
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 ...
10
votes
1answer
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 ...
0
votes
1answer
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....
8
votes
1answer
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 ...
6
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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" ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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. ...
2
votes
1answer
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?
2
votes
1answer
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, ...
0
votes
0answers
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 ...
8
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
13
votes
1answer
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 ...
0
votes
0answers
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 ...
4
votes
3answers
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 ...
4
votes
3answers
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 ...
2
votes
0answers
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,...
1
vote
0answers
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.,...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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, ...
1
vote
1answer
110 views

Running algorithms in parallel [closed]

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-...
0
votes
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 ...
1
vote
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 ...
2
votes
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: ...
1
vote
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 ...
1
vote
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?
5
votes
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 \...
0
votes
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 $...
4
votes
2answers
572 views

Suboptimal Solution for a combinatorial problem

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 ...
1
vote
1answer
178 views

parallelizing $k$-means

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just $...
2
votes
0answers
78 views

Why is this execution happens-before consistent?

In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency. The trace is shown in the figure in which $A$ and $B$ are ...
3
votes
0answers
1k views

“Data-race free” programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all histories $H$ ...
11
votes
1answer
7k views

Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors

We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers. The algorithm was: Given an array A of length n: ...