Theoretical questions in Parallel Computing
-1
votes
1answer
54 views
Consensus impossibility for arbitrary graph $G$
I know the proof of impossibility of achieving deterministic algorithm for consensus (the basic synchronous model) for 2 processes.
What is the proof for an arbitrary graph?
9
votes
1answer
364 views
Is there a quantum NC algorithm for computing GCD?
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
9
votes
2answers
315 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$ ...
1
vote
2answers
90 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 ...
1
vote
0answers
121 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)$ ...
8
votes
1answer
184 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
83 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
0answers
72 views
What are the parts of consistency model playing in hardware, operating system, and programming language?
In multiprocessor programming, consistency model is the key concept to express the correctness(or safety) of concurrent objects ranging from simple shared variable to concurrent data structures like ...
1
vote
3answers
291 views
Does mathematical model for conccurent computations exist?
Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?
If yes, how are the concurrent computations ...
5
votes
1answer
124 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
111 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 ...
6
votes
2answers
208 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 ...
2
votes
1answer
73 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
176 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 ...
3
votes
1answer
173 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
118 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 ...
3
votes
5answers
323 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
151 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
432 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 ...
6
votes
0answers
107 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
442 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, ...
15
votes
1answer
520 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
121 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
89 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
187 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 ...
9
votes
3answers
281 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
192 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 ...
10
votes
0answers
205 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 ...
3
votes
1answer
282 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 ...
5
votes
3answers
245 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 ...
2
votes
2answers
299 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
0answers
93 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 ...
7
votes
1answer
331 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 ...
5
votes
1answer
187 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
201 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
743 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
167 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 ...
16
votes
2answers
337 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 ...
11
votes
3answers
346 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 ...
27
votes
10answers
843 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 ...
5
votes
2answers
279 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 ...
5
votes
3answers
994 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
243 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 ...
5
votes
1answer
320 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 ...
7
votes
1answer
237 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
170 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 ...
-1
votes
1answer
242 views
one parallel algorithm [closed]
please help me to find any parallel algorithm with any topological architecture to find k-th largest number in array in log(N) which N is the number of element in array
3
votes
2answers
383 views
Is there parallel algorithm for 3SAT
Is there any parallel algorithms or approximation algorithms for 3SAT?
6
votes
2answers
372 views
Dijkstra parallelization
I'd like to know what is the best method to parallelize the Dijkstra algorithm.
Thanks.
1
vote
1answer
239 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, ...
