Parallelism studies programs that execute simultaneously on multiple processors

learn more… | top users | synonyms

0
votes
0answers
26 views

Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
0
votes
1answer
31 views

Hadoop MapReduce Word Counting Example [closed]

In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number ...
-1
votes
0answers
36 views

Parallel CREW algoritm for sorting n numbers between 0 and logn-1

We are given n integers in the range [0,..,log(n)-1]. How can we sort the numbers? The algorithm doesn't have to be work-efficient.
-1
votes
1answer
12 views

Cocurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...
2
votes
1answer
38 views

Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
0
votes
0answers
36 views

Solution Patterns Involving Semaphores

There are a lot of synchronization problems that can be solved using semaphores. Some of these include the Producer-Consumer Problem, Readers-Writers Problem and the Dining Savages Problem. I see a ...
2
votes
1answer
52 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, ...
0
votes
0answers
30 views

Describing monitors and semaphores in terms of the three properties of critical section problem solutions

Solutions to the critical section problem exhibit three properties: mutual exclusion, progress, and bounded waiting. When do we say, or do we at least say, that operating system-implemented semaphores ...
7
votes
0answers
52 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
1
vote
1answer
56 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 ...
2
votes
2answers
80 views

BNF and Simultaneous Parsing

Let's say we have the following grammar expr1 ::= ... // Actual definition doesn't matter expr2 ::= ... // expr3 ;:= ... // foo ::= expr1 | expr2 | expr3 ...
3
votes
1answer
80 views

Why use SIMD if we have GPGPU?

I thought this question is better served in the CS part of Stack Exchange. Now that we have GPGPUs with languages like CUDA and OpenCL, do the multimedia SIMD extensions (SSE/AVX/NEON) still serve a ...
0
votes
0answers
21 views

Is k-means parallelizable (other than the data parallelism of the distance function computation)

The k-means algorithm is known to be NP-hard. While the distance function computation in the algorithm loop is data parallel, the algorithm is iterative and may become exponential in the number of ...
4
votes
3answers
111 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
1
vote
1answer
142 views

Can/Do multiple processes run simultaneously on a multi-core system?

I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run ...
1
vote
0answers
73 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 ...
1
vote
0answers
71 views

Parallel single source shortest path algorithm

Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ ...
0
votes
1answer
29 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 ...
2
votes
0answers
22 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
1answer
91 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, ...
1
vote
1answer
46 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 ...
0
votes
1answer
39 views

Amdahl law and parallelism

I know after some reading Amdahl law is a embarrassingly parallel programming model. Embarrassingly parallel means there is no communication and tasks work independently. Am I to assume a parallel and ...
0
votes
1answer
65 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
1answer
35 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
13 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
33 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
100 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
48 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 ...
4
votes
2answers
195 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
38 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
23 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
125 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$ ...
7
votes
1answer
687 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
205 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
121 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
62 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
2k 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
475 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
2answers
60 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
394 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
46 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
30 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
137 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
156 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
33 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 ...
3
votes
1answer
64 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
70 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
1k 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
107 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
311 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, ...