We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [dc.parallel-comp]

Theoretical questions in Parallel Computing

Filter by
Sorted by
Tagged with
4
votes
1answer
212 views

Is conversion of PRAM to parameter number of processors trivial

In section 2 of chapter 4 of Kumar the idea of scaling down is discussed. It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just "...
2
votes
1answer
144 views

Parallel algorithms to find the optimum of polynomials

Are there any non-trivial parallel algorithms to find the optimum (local or global) of polynomials? By trivial, I mean something which is an obvious application of a serial algorithm. For example, one ...
4
votes
5answers
402 views

Advantages and specific applications of massively parallel programming thesis idea

I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications. I'm searching for an application ...
1
vote
1answer
200 views

How is the iteration space of a nested for-loop containing two sequential nested loops represented?

In a general for loop of the form: for (i = 0, i <= n, i++) { for (j = i, j <= n, j++) ... for (k = i, k <= n, k++) ... } What ...
1
vote
1answer
825 views

What do people mean by capabilities and capacities?

Someone made a casual remark to me about the terminology of capabilities and capacities, in the context of threads, processors and runtime systems, particularly their theoretical modelling. For ...
7
votes
0answers
130 views

Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices ...
3
votes
3answers
1k views

parallelizable fast matrix in-place transposition

what is the current state of the art in fast and parallel matrix in-place transposition? I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, ...
19
votes
1answer
764 views

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear ...
1
vote
1answer
263 views

Most optimal parallel method for calculating the integral of a 2D function

I posted already this question to SO but got no answer so I try it now here: In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
1
vote
0answers
130 views

Optimal parallel algorithm for finding roots of a function [closed]

In some problem I need to find the zeroes (multiple real solutions) of some functions in 1D and 2D. I wonder which is the best parallel algorithm for this, which can provide the highest accuracy and ...
1
vote
0answers
196 views

Algorithm for permuting elements using constant work space

I'm searching for an algorithm to do the following: A 1->3 B 2->6 C 4->5 D 5->2 E 6->4 F 3->7 G 8->9 H 10->11 Elements A-H are stored on ...
10
votes
3answers
320 views

Introductory notes on parallelization, in particular patterns of problems and algorithms

I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science. My focus is ...
2
votes
0answers
333 views

Recursive parallel topological sorting in linear time

While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
13
votes
1answer
434 views

Parallel algorithms for reachability in directed planar graphs

Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for st-connectivity ...
4
votes
1answer
328 views

Parallel sorting: introduction and state of research

there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic. So, do you know a good summary or introduction into parallel sorting algorithms? In ...
6
votes
3answers
290 views

Best algorithm for calculating lists of neighbours

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
3
votes
2answers
1k views

Flynn's taxonomy, and “task parallelism and data parallelism”

Quoted from http://en.wikipedia.org/wiki/Task_parallelism: Task parallelism (also known as function parallelism and control parallelism) is a form of parallelization of computer code across ...
7
votes
0answers
121 views

Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients

Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time $(d\log{...
10
votes
1answer
1k views

A practical multi-word compare-and-swap operation

In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the ...
7
votes
1answer
290 views

Parallel algorithms to color interval graphs

Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and ...
5
votes
1answer
326 views

Definition of a hereditary relation

Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307: Given a tree $S$, define … $\#$ is ...
20
votes
6answers
1k views

Parallel pseudorandom number generators

This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it. Put simply, I have a Monte Carlo ...
1
vote
1answer
225 views

Selection algorithm on depth-$\text{O}(\log n)$ sorting network

Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic? Remark: I've already asked a related question in a different context. Although the two questions are ...
21
votes
2answers
722 views

What is the big version of NC?

$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
11
votes
3answers
458 views

Is the MapReduce framework a type of BSP?

Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what ...
30
votes
10answers
1k views

Current parallel models for computation

The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s. Are these areas still active in terms of ...
6
votes
2answers
503 views

What algorithm on a PRAM computes the connected components of a graph with least time complexity?

The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on ...
8
votes
3answers
6k views

Difference between Strict Consistency and Sequential Consistency

I understand strict and sequential consistency independently fairly well. Strict C basically enforces the actual order in which the instructions ran on the global clock. Sequential Consistency ...
2
votes
0answers
251 views

Is there a problem which is provably not parallelizable? [duplicate]

Possible Duplicate: Limits to Parallel Computing A friend just asked me, if for every problem that takes time t on one processor, solving it on two processors will take t/2. Obviously, this is ...
6
votes
1answer
429 views

Parallel solution of recurrence equation

One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the ...
10
votes
1answer
317 views

What machine learning classifiers are the most parallelizeable?

What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try? ...
3
votes
1answer
232 views

No Fair Merge via Nondeterminstic Data Flow Streams

While reading Wikipedia, I ran across a proof given on Unbounded Nondeterminism that I do not understand. The proof is given as, An example of the role of fair or unbounded nondeterminism in the ...
3
votes
2answers
497 views

Is there parallel algorithm for 3SAT

Is there any parallel algorithms or approximation algorithms for 3SAT?
8
votes
2answers
472 views

Dijkstra parallelization

I'd like to know what is the best method to parallelize the Dijkstra algorithm. Thanks.
1
vote
1answer
249 views

Parallel programming languages which look deterministic? [closed]

Are there any programming languages where the system parallelizes the program without any noticeable differences for the programmer? That is, the programmer writes a linear, deterministic program, ...
20
votes
5answers
1k views

Deterministic Parallel algorithm for perfect matching in general graphs?

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. ...
13
votes
2answers
371 views

When a process spawns another process

My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time). ...
14
votes
0answers
319 views

Linear PRAM vs Arithmetic Linear PRAM

A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the ...
20
votes
3answers
1k views

Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
-2
votes
1answer
235 views

Approach to implementing an STM for a student [closed]

A student has implemented a scheme interpreter in scheme and then in C, and a scheme compiler in scheme. That student is now interested in implementing a STM (Software Transactional Memory) system ...
11
votes
3answers
440 views

Which algorithms can be expressed using a total functional language with data parallel operators?

Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are ...
13
votes
3answers
838 views

Parallel algorithms for directed st-connectivity

Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-...
10
votes
6answers
497 views

Reducing complexity with parallelism

Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?...
24
votes
2answers
526 views

Parallel Dynamic Search

Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ? More generally, what's the best we can do ...
5
votes
0answers
251 views

When designing an explicitly parallel language, what built in functions should be parallelized? [closed]

As stated by the title. Some examples that I would include would be map and conditionals. What other functions should be built in already parallel for users to expand on it?