Questions tagged [dc.parallel-comp]

Theoretical questions in Parallel Computing

Filter by
Sorted by
Tagged with
17
votes
2answers
876 views

Status on circuit lower bounds for polylog-bounded depth circuits

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
7
votes
2answers
238 views

Are there [good/optimal] parallel comparison sorts?

Comparing each pair of elements and sorting according to [[number less than] minus [number greater than]] is a parallel comparison sorting algorithm with a depth of $1$ comparison and $O\left(n^2\...
1
vote
2answers
183 views

Classic parallel clustering algorithms

I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering....
1
vote
0answers
209 views

Big-Theta extension of Brent's Theorem?

Is there an extension or translation of Brent's theorem into asymptotics aside from big-$O$? Brent's Theorem: source Running time of a parallel algorithm with $p$ processors (say, $f(n,p)$), $W(n)$ ...
10
votes
1answer
254 views

Is deterministic pseudorandomness possibly stronger than randomness in parallel?

Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
0
votes
0answers
156 views

Sequential Consistency, cannot find a sufficient explanation

I am having a hard time understanding the SC memory model properly. The sentence "the result of any execution is the same as if the operations of all the processors were executed in some sequential ...
2
votes
1answer
148 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 ...
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 ...
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
1answer
133 views

Can we do joins in NC?

Suppose we want to join two relations on a predicate. Is this in NC? I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
5
votes
0answers
134 views

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions. Since $\mathsf{...
4
votes
1answer
213 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 "...
1
vote
1answer
832 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 ...
2
votes
1answer
84 views

Lower bounds on batched query search

I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
3
votes
0answers
236 views

$NC^i \subseteq DSPACE[\log^i{n}]$?

The containment $NC^1 \subseteq DSPACE[\log{n}]$ is simple and well-known (assuming a reasonable notion of uniformity for $NC^1$) and follows by: start with an $O(\log{n})$-depth polynomial sized ...
4
votes
5answers
406 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
202 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 ...
7
votes
0answers
132 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, ...
1
vote
1answer
264 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
133 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 ...
4
votes
1answer
332 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 ...
1
vote
1answer
231 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 ...
1
vote
0answers
197 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
340 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 ...
3
votes
0answers
346 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 ...
2
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 ...
6
votes
3answers
291 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 ...
7
votes
0answers
123 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
2k 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
309 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
343 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 ...
3
votes
1answer
245 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 ...
21
votes
2answers
913 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$...
6
votes
1answer
500 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 ...
11
votes
3answers
551 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 ...
6
votes
2answers
524 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 ...
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 ...
3
votes
2answers
539 views
9
votes
6answers
553 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?...
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, ...
13
votes
2answers
426 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
321 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
237 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 ...
24
votes
2answers
548 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 ...
10
votes
3answers
474 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 ...
14
votes
3answers
921 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-...
5
votes
0answers
253 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?

1
2