Parallelism studies programs that execute simultaneously on multiple processors

learn more… | top users | synonyms

-2
votes
0answers
12 views

'Working on Distributed Systems(Distributed Computing/Parallel Computing)" [on hold]

How should I start afresh in 'Working on Distributed Systems(Distributed Computing/Parallel Computing)"??? Actually, I want to be more specific in this. I want to code and build some change in the ...
0
votes
0answers
10 views

Can a thread not block if the lock it tries to lock is not available? [migrated]

In OpenMP, there is routine OMP_TEST_LOCK which, when called by a thread to attempt to set a lock, but the thread does not block if the lock is unavailable. I ...
1
vote
1answer
32 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
6 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 ...
0
votes
0answers
27 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
83 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
41 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 ...
3
votes
2answers
154 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
33 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
0answers
17 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
57 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$ ...
5
votes
1answer
194 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: ...
2
votes
2answers
83 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
69 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
42 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 ...
6
votes
3answers
248 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. ...
11
votes
3answers
308 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 ...
0
votes
1answer
43 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 ...
12
votes
3answers
357 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 ...
2
votes
0answers
40 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
26 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
87 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 ...
10
votes
3answers
139 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 ...
1
vote
0answers
65 views

Is parallel programming a need of future and worth investing time and money? [closed]

Given the problems of Dark Silicon, diminishing returns from multicore, and soon to die Moore's law, does that make sense to concentrate on parallel programming research and invest time and money in ...
1
vote
0answers
55 views

Masters in HPC (High Performance Computing) [closed]

Is there a master degree in HPC (High Performance Computing) in US? I am asking this question because in my early research I found no direct mentioning of HPC instead invidual courese in parallel ...
1
vote
0answers
31 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 ...
2
votes
1answer
48 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? ...
3
votes
3answers
67 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 ...
0
votes
1answer
465 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
66 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
216 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, ...
5
votes
2answers
233 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 ...
-1
votes
1answer
43 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 ...
3
votes
1answer
408 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
115 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
102 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 ...
6
votes
1answer
137 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
114 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
90 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
158 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
143 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 ...
3
votes
2answers
108 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 ...
3
votes
2answers
231 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
0answers
185 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 ?
4
votes
1answer
279 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
115 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
288 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
237 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
44 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
48 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 ...