# 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!

323 questions
Filter by
Sorted by
Tagged with
43 views

### Any ideas for Parallel Computing Project?

I have to make an application as my Parallel Computing university course project. The application should make use of parallel processing. Any ideas or examples for these kinds of applications ??
62 views

### Is there a way to parallelise find and inserts for a binary search tree?

Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism. I have implemented a ...
68 views

### How to find parallel efficiency for word count algorithm?

There're not a lot of books and explanations around this example topic, so I thought asking here would be appropriate for future learners including me as well. Background: Problem: Consider a very ...
69 views

### Super-linear parallelism or speedup in parallel matrix multiplication algorithms

I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T_1$, Span $T_\infty$ and Parallelism (ratio $T_1/T_\infty$). What is called ''...
68 views

### Why is it not a good idea to branch a thread outside of a parallel region while other threads are still executing?

Say I have $n$ threads executing in a parallel region and one of them leaves the parallel region when others are still continuing to execute in the parallel region. Why this is a $BAD$ idea? For ...
152 views

### Calculating speedup of this parallel program

I have a sequential program that has a cost of $(\sum_{n=1}^{N} Ti )$ Where Ti is the load time of the i-th element, so if consider $Tm = max({Ti})$ i can approximate the sequential cost as $N*Tm$ ...
1 vote
442 views

### How is this example sequentially consistent but not linearizable?

Background information that I know(But not understand with examples, I will be glad if you could explain it to me with examples) A replicated service is said to be linearizable if for any executin ...
1 vote
30 views

### What is the circuit depth of asymptotically fast multiplication algorithms?

I know the circuit depth (i.e. amount of sequential operations on the longest path) for long multiplication can easily be made $O(\log(n))$ (possibly at the cost of increasing the computational ...
36 views

### Parallel algorithm for Polynomial GCD

It is known that half-GCD (https://www.csd.uwo.ca/~mmorenom/CS424/Lectures/FastDivisionAndGcd.html/node6.html) is can be used to compute the GCD of two polynomials over a finite field. Is it possible ...
47 views

### Are single-dimentional arrays better than multi-dimentional in the GPU?

I'm making simulations like Ant colony simulation, boids, and cellular automata in Go (to learn Go), but I believe this can apply to most languages. From what I've read (this), using 1D arrays is ...
140 views

### How to use Parallel Semaphores for Dining Philosophers Problem

I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the ...
52 views

### Arithmetic intensity of matrix multiplication

Arithmetic intensity (AI) is the number of FLOPS divided by the number of byte accesses. For conventional matrix multiplication of matrices of sizes $m \times k$ and $k \times n$, the number of FLOPS ...
27 views

### How to represent mutually exclusive events in CSP

I am studying Communicating Sequential Processes (CSP), and I understand that an event can be "emmited" ($\overline{e}$) and an event can be "waited on" ($e$), so that an event ...
68 views

### Loop Transforms to Increase Parallelism

I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm: ...
540 views

### All-to-All Broadcast on a Balanced Binary tree

Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree? Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages ...
69 views

### Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph?

I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. I want a method to effectively parallelize these tasks. One way would be to topological sort them based ...
72 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....
1 vote
45 views

I once had an idea for a multithreaded regex engine. The first method that occured to me (there may be other ways to do it that I haven't thought of) was to split up the string being matched against ...
77 views

### Construction of Omega Network

I understand that we could draw N * N Omega Network, But can we draw an Omega Network to connect 6 CPUs to 4 memories? (The number of CPUs does not equal the number of memories)
22 views

### GPU compute parallel radix sort optimizations

I'm looking at this paper that describes a GPU parallel radix sort algorithm. They describe multiple optimizations but in section 3 where the whole algorithm is described some things elude me. First, ...
3k 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 vote
28 views

### How do I prove the following invariant of this program?

I have been studying different topics within the realm of concurrent programming and came across "Lamport's bakery algorithm" which is based on the original version of the bakery algorithm ...
2k views

### What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
53 views

### What is the etymology of "swizzle"?

The word swizzle can refer to an operation performed in GPU algorithms: [The] ability to compose vectors by arbitrarily rearranging and combining components of other vectors. Swizzle (computer ...
1 vote
21 views

### Sorting a list over rounds of binary comparisons

You have a list of $n$ items you want to sort over $r$ rounds using binary comparisons. In each round, you specify $k$ binary comparisons to be made in parallel. The objective is to fully sort the ...
1 vote
850 views

### How on-chip multithreading prevents cache misses from stalling a processor pipeline?

On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids ...
44 views

### Sorting from independently chosen comparisons

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from ...
37 views

### Split-Ordered Lists: Lock-Free Extensible Hash Tables

I am reading the research paper "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Nir Shavit and Ori Shalev. https://dl.acm.org/doi/10.1145/1147954.1147958 I was just wandering if ...
19 views

### Resources to self-study counting/sorting networks

I am reading The Art of Multiprocessor Programming. I was able to grasp almost everything up to Counting Networks in chapter 12 - Counting Sorting and Distributed Coordination. However I am having ...
1 vote
25 views

### (Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers

In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers. I am facing a related problem: In my Order Independent Transparency implementation, I would like to ...
1 vote
33 views

### Efficient Way To Compute Points Where Convolution Equals Zero

I want to model the following procedure. Given a shape $L\subseteq\mathbf{R}^2$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $K\subseteq\mathbf{R}^2$, I want ...
28 views

### Recursive decomposition if a sequence can be parsed in both directions

Given a sequence/string of values and an algorithm that can process said sequence in both directions and obtain the same result - does it follow that the problem can in fact be decomposed in a divide-...
19 views

### Minimum number of registers for mutual exclusion

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...
12 views

### What are the chances of fusing a quantum computer and a parallel computer and what potential dangers/ benefits does it bring?

From my EPQ research I came to know that quantum computers require certain conditions to function optimally such as: low temperature so that electrons do not get disturbed etc. I've also read a book ...
12 views

### Hierarchical exclusion acquisition order

In the context of parallel computing, it has been said (quote?) that acquiring exclusive locks in opposite order will eventually lead to deadlock conditions. It has been suggested (source?) that the ...
380 views

### concurrency in multiple core

I know the basic definition between parallelism and concurrency. But there is not much information about concurrency in multiple core. what is the difference between concurrency in single-core vs ...
202 views

### How does the TEPS benchmark work and why is it relevant to real world problems?

Graph500 is a competition for supercomputers that uses a different benchmark "Traversed Edges Per Second", which is supposed to measure some notion of the communication bandwidth ability of ...
80 views

### Books about data structures and algorithms but specifically focusing on parallel gpgpu programming

I'm looking for a book on the subject of algorithms and data structures, but I want to specifically learn about the parallel implementations. Books that teach CUDA and OpenCL usually have small ...
1 vote
42 views

### Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint

I recently went through a interview session for a SWE/CS role at a well known company. It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...
1 vote
32 views

### Fast software pipelining for stream processing

I have a pipelined stream processing situation, where a number of streams is linked in the computational process S0 -> S1 -> S2 -> .... You can understand &...
1 vote
142 views

### GroupBy key a sequence of ordered key values

I have a sorted (by key) sequence of key value pairs: ...
88 views

### what is the relationship between increasing the number of cores and scalability?

Whenever I increase the number of cores the speedup will increase. with this increasing can I consider the system as scalable? I mean based on the speedup obtained for a different number of cores e....
56 views

### Distributed Algorithm to get an ordered list of nodes in a bipartite graph

Given a weighted bipartite graph with nodes of type A and B, I want to output an (approximately) ordered list of type B nodes as defined by the following heuristic: For each node of type B, sum over ...
1 vote
149 views

### Give a parallel algorithm that finds the minimal element of an unsorted array

I need to give a parallel algorithm which finds the minimal element of an unsorted array. Moreover, I need to show that $T_1 = Θ(n)$ and $T_∞ = Θ(\log n)$. As I read $Θ(\log n)$, I thought about some ...
1 vote
113 views

### concurrency vs parallelism

I am so confused between concurrency vs parallelism in multi-core processors. If a concurrent process has many threads and if the processor is multi-core then can each thread run on multiple cores? If ...
40 views

### Comparing PRAM and Circuit Complexity, $NC^i$

I wondered about the following quote from NC (Wikipedia): $NC^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and ...
1 vote