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
0 votes
1 answer
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 ??
2 votes
0 answers
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 ...
-1 votes
0 answers
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 ...
0 votes
3 answers
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 ''...
0 votes
1 answer
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 ...
-1 votes
2 answers
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
1 answer
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
0 answers
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 ...
2 votes
0 answers
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 ...
0 votes
1 answer
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 ...
3 votes
1 answer
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 ...
0 votes
0 answers
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 ...
0 votes
1 answer
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 ...
0 votes
1 answer
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: ...
0 votes
1 answer
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 ...
2 votes
1 answer
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 ...
2 votes
1 answer
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
0 answers
45 views

Multithreaded Regex?

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 ...
0 votes
0 answers
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)
3 votes
0 answers
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, ...
9 votes
2 answers
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
0 answers
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 ...
8 votes
2 answers
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 ...
2 votes
0 answers
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
1 answer
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
2 answers
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 ...
2 votes
2 answers
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 ...
0 votes
0 answers
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 ...
0 votes
0 answers
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
0 answers
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
1 answer
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 ...
0 votes
1 answer
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-...
2 votes
0 answers
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 ...
0 votes
0 answers
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 ...
0 votes
0 answers
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 ...
0 votes
2 answers
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 ...
2 votes
1 answer
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 ...
3 votes
2 answers
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
0 answers
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
1 answer
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
1 answer
142 views

GroupBy key a sequence of ordered key values

I have a sorted (by key) sequence of key value pairs: ...
0 votes
1 answer
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....
0 votes
0 answers
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
1 answer
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
3 answers
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 ...
2 votes
0 answers
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
1 answer
282 views

Parallel algorithm for finding the maximum in $O(\log \log n)$ time

With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is: If $...
1 vote
1 answer
219 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 ...
1 vote
1 answer
32 views

Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can ...
0 votes
1 answer
109 views

Analyzing parallel performance question

I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer: We have a system to which ...

1
2 3 4 5
7