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
4
votes
3answers
5k views

Differences and relations between high-performance/throughput computing and parallel computing?

I wonder if high-performance computing and parallel computing always mean the same? If not, what are the differences and relations between them? what are some examples of high-performance ...
2
votes
3answers
655 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
243 views

What can distributed computing do besides parallel computing?

I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing? If I understand correctly, parallel ...
44
votes
5answers
47k views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
24
votes
3answers
5k views

Which algorithms can not be parallelized?

Is there any algorithm which is very difficult to parallelize or the research is still active? I wanted to know about any algorithm or any research field in parallel computing. Anything, I searched ...
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 ...
18
votes
3answers
627 views

Parallelising random reads seems to work well — why?

Consider the following very simple computer program: for i = 1 to n: y[i] = x[p[i]] Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-...
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).
1
vote
0answers
68 views

fastest way to compute scalar product of an ensemble of vectors

I have an ensemble of points in 3D space, represented by their coordinates $\mathbf{c_i}\equiv(x_i,y_i,z_i)^\top$ . I need to calculate the distance between all these points: $\quad\forall i,j\quad ...
1
vote
0answers
311 views

What makes neuromorphic computing architecture more efficient than von Neumann

What makes neuromorphic architectures more efficient (less heat and power consumption) than von Neumann architecture for complex tasks? Except inspiration from biological systems, what are some formal ...
12
votes
3answers
372 views

Multicore SAT Solver

I am trying to solve a 25k clauses 5k variables SAT problem. As it has been running for an hour (precosat) and I'd like to solve bigger ones afterwards, I'm looking for a multi-core SAT-Solver. As ...
2
votes
0answers
59 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
337 views

Functional Programming and Parallelism

I have an option to learn a new language for parallel computing. As a parallel programmer what are the reasons one might want to invest time to learn functional programming for parallel computing?
4
votes
3answers
95 views

Reasons for decreasing the number of threads in a parallel implementation

What are the reasons for decreasing the number of threads in a parallel implementation ? Assume that we have two implementations, the first one with 4 threads, and a second one with 8 threads, and ...
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
469 views

Why does the map function in MapReduce take two parameters?

I am playing around with MapReduce and wanted to ask why the map function takes two inputs (key, value)? Why not just pass along ...
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, ...
6
votes
2answers
2k views

Why do you have to worry about cache coherence if you are using shared memory?

Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one ...
0
votes
1answer
85 views

What would be the over all speed-up achieved?

Suppose we are using a dual core processor and we run 2 applications (1 with 80% resource requirements and the other with 20% resource requirements).Now the first program is parallelizable for 40% and ...
5
votes
2answers
4k views

Reference book for Parallel Computing and Parallel algorithms.

Please suggest some books on Parallel Algorithms which teach efficient programming techniques like the ones taught in Udacity course(Introduction to Parallel Programming with CUDA). Also wanted to ...
0
votes
2answers
495 views

What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
4
votes
1answer
686 views

$\mathbf{NC}$ is closed under logspace reductions

I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a ...
5
votes
1answer
309 views

Largest reported speedup for a parallel computation?

A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel ...
2
votes
1answer
970 views

Does PETSc really give speedup?

I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and ...
1
vote
1answer
108 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 ...
3
votes
1answer
311 views

Amdahl's Law and Computer Science

I would like to learn more about Amdahl's Law and other similar topics. In what branch of computer science would one place Amdahl's law? Could someone point me to a textbook or further reading (...
8
votes
2answers
229 views

Which theoretical parallel model is closest to CUDA?

Which theoretical parallel model is closest to CUDA/OpenCL programming model? For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too ...
4
votes
2answers
912 views

Parallel Computing: Past Vs Present

Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on ...
6
votes
2answers
3k views

Best problems that are prone to parallelization?

What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can ...
1
vote
1answer
1k views

What is Pointer Jumping ?

Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?
5
votes
1answer
917 views

Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear. What I ...
2
votes
1answer
1k views

How to enumerate combinations in parallel

I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried ...
4
votes
1answer
2k views

Perfect shuffle in parallel processing

How is Perfect shuffle a better interconnect scheme for parallel processing? For example if we consider a problem of sum reduction, I want to understand how this scheme is useful when implementing sum ...
6
votes
1answer
433 views

Problem Solving in MapReduce Framework

I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is ...
1
vote
0answers
64 views

Vectorizing and Array Notation?

I'm really trying to wrap my head around vectorization but I can't seem to understand it. I don't know if I don't understand how to vectorize, or if I don't understand the array notation that's being ...
2
votes
1answer
65 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 ...
6
votes
1answer
809 views

An online parallel algorithm for finding top K elements

Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our ...
1
vote
1answer
565 views

A question about parallel algorithm complexity

When in a Parallel algorithm we say: "This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $...
4
votes
1answer
1k views

How partitioning in map-reduce work?

Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the ...
5
votes
2answers
3k views

how does the parallel radix sort work?

I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism. ...
3
votes
1answer
193 views

How do you go about designing a vector processor architecture for the sum of matrix products?

The following equation is a matrix expression where $B_i$ and $C_i^T$ are $n\times n$ matrices and k is a positive integer: $$P = \sum_{i=1}^k B_i C_i^T $$ So $P = B_1 C_1^T + B_2 C_2^T + \cdots +...
2
votes
0answers
90 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 ...
14
votes
2answers
594 views

Some questions on parallel computing and the class NC

I have a number of related questions about these two topics. First, most complexity texts only gloss over the class $\mathbb{NC}$. Is there a good resource that covers the research more in depth? ...
1
vote
1answer
167 views

Using Loop Dependence analysis for vectorization

How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?
0
votes
1answer
118 views

What are current approaches to auto-parallelisation?

I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.
4
votes
1answer
427 views

Batch processing in increase-key function using binary heap

Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one ...
3
votes
0answers
70 views

How is amorphous computing different from spatial computing?

Surely spatial computing and amorphous computing share similarities and overlap. Is spatial computing a subset of amorphous computing? How are the two different?
68
votes
4answers
16k views

What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is ...
13
votes
1answer
5k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
9
votes
1answer
5k views

Could an artificial neural network algorithm be expressed in terms of map-reduce operations?

Could an artificial neural network algorithm be expressed in terms of map-reduce operations? I am also interested more generally in methods of parallelization as applied to ANNs and their application ...