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
261 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, ...
2
votes
1answer
500 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, ...
2
votes
3answers
666 views

Good motivation for parallel data structures and algorithms [closed]

I have a more general question for you. I'm working in Parallel Data Structures and Parallel Algorithms. That is a nice topic with a lot of interesting challenges. However, I have some problem to ...
2
votes
1answer
78 views

What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? [closed]

I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use ...
2
votes
1answer
107 views

What information needs to be saved in a Lamport clock system to deduce message causality?

By using Lamport timestamps, we can determine the causality of messages. It is however unclear to me how one would deduce this simply from the lamport timestamp of the message. Take the following ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
76 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 ...
2
votes
2answers
163 views

Is automatic multicore support at the hardware or compiler level possible?

Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance. However, multicore ...
2
votes
1answer
390 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 ...
2
votes
1answer
68 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
217 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 ...
2
votes
1answer
66 views

Studies of file access patterns in embedded systems

I am considering what elements an operating system for Network On Chip systems might have and the issue of file systems looms large. NoCs have an embedded heritage, and their domain of use (at least ...
2
votes
0answers
31 views

When concatenating two sequences, can evaluations of two input sequences be in parallel with each other?

In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf), 37.3 Multiple Fork-Join So far we have confined attention to binary fork/join parallelism ...
2
votes
0answers
29 views

What does it mean by “consistent view of memory” in lock-free dequeue implementation?

I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation. ...
2
votes
1answer
54 views

Question regarding terminology used to describe Benes networks

I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes....
2
votes
0answers
78 views

Stochastic Computing: What is “Bundle Processing”?

I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says: Bundle Processing involves sending a fixed number of bits instead of a stream. One of the ...
2
votes
0answers
2k views

Why weak scaling is easier to achieve than strong scaling?

When we parallelize tasks and measure the perforamnce,two common measures of parallel scaling are Strong Scaling: Time for fixed problem size as number of processor is increased Weak Scaling: Time ...
2
votes
0answers
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 ...
2
votes
0answers
429 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 ...
2
votes
0answers
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 ...
2
votes
0answers
350 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,...
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
0answers
86 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 ...
2
votes
0answers
73 views

EXPTIME and parallel computing

Can we solve an EXPTIME-complete problem in polynomial time given 2^N processors?(N is the size of input).
2
votes
0answers
60 views

Stream processor definition

I'm looking for an actual definition of a stream processing unit (SPU), preferably sourced. The context is not specifically graphics cards. I can find many, many articles explaining what they contain,...
2
votes
1answer
2k views

Which of the common sorting algorithms can be parallelized? [closed]

I want to know that whether which of the following algorithm can be parallelized? Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Quick Sort, Merge Sort, Radix Sort. Those which can't be, ...
2
votes
0answers
91 views

Determine interference factors in parallel computing

Parallel processes interfere with each other in many ways, by competing for shared resources such as shared caches, memory, disks, etc. Would it be possible to determine latent factors just with a ...
1
vote
2answers
433 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 ...
1
vote
1answer
584 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 ...
1
vote
2answers
86 views

Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?

I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one ...
1
vote
2answers
281 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.
1
vote
1answer
112 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-...
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 $...
1
vote
1answer
115 views

Parallelization of an iterative function application

What I have An iterative process based on the application of a very simple function to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th ...
1
vote
2answers
105 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....
1
vote
1answer
173 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 ...
1
vote
2answers
132 views

Are self-stabilizing algorithms guaranteed to work in parallel?

Self-stabilizing algorithms are extremely useful in distributed systems, but can the algorithm be applied concurrently to each computational node? My instinct is to say yes, but I can't help but ...
1
vote
1answer
45 views

Estimating P in Amdahl's Law theoretically and in practice

In parallel computing, Amdahl's law is mainly used to predict the theoretical maximum speedup for program processing using multiple processors. If we denote the speed up by S then Amdahl’s law is ...
1
vote
1answer
45 views

How do I use message passing to find the maximum of all values in a grid?

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
1
vote
1answer
88 views

Finding minimum in PRAM model

Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.
1
vote
1answer
716 views

Calculate execution time from linear speedup

Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores? (Assuming Gustafson's law, or in other words, $t(\infty)=0$) My ideas: I ...
1
vote
1answer
105 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 ...
1
vote
1answer
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 ...
1
vote
1answer
108 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
1answer
452 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 ...
1
vote
1answer
273 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 ...
1
vote
1answer
11k views

MapReduce Pseudocode [closed]

Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents: ...
1
vote
1answer
1k views

About hardware multithreading

I'm reading Multithreading (computer architecture) - Wiki, aka hardware threading, and I'm trying to understand the second paragraph: (p2): Where multiprocessing systems include multiple complete ...
1
vote
1answer
42 views

deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

Thanks a lot for your help. I want to understand what really causes what I suppose to be a deadlock: I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t ...