CODEWITHSUNDEEP
algorithmcomplexity-theorytime-complexity
ysap
ysap

Reputation: 8115

What algorithms have high time complexity, to help "burn" more CPU cycles?

I am trying to write a demo for an embedded processor, which is a multicore architecture and is very fast in floating point calculations. The problem is that the current hardware I have is the processor connected through an evaluation board where the DRAM to chip rate is somewhat limited, and the board to PC rate is very slow and inefficient.

Thus, when demonstrating big matrix multiplication, I can do, say, 128x128 matrices in a couple of milliseconds, but the I/O takes (lots of) seconds kills the demo.

So, I am looking for some kind of a calculation with higher complexity than n^3, the more the better (but preferably easy to program and to explain/understand) to make the computation part more dominant in the time budget, where the dataset is preferably bound to about 16KB per thread (core).

Any suggestion?

PS: I think it is very similar to this question in its essence.

Upvotes: 1

Views: 1874

Answers (6)

Patrick87
Patrick87

Reputation: 28312

Another idea might be to compute a fractal map. Basically, choose a grid of whatever dimensionality you want. Then, for each grid point, do the fractal iteration to get the value. Some points might require only a few iterations; I believe some will iterate forever (chaos; of course, this can't really happen when you have a finite number of floating-point numbers, but still). The ones that don't stop you'll have to "cut off" after a certain number of iterations... just make this preposterously high, and you should be able to demonstrate a high-quality fractal map.

Another benefit of this is that grid cells are processed completely independently, so you will never need to do communication (not even at boundaries, as in stencil computations, and definitely not O(pairwise) as in direct N-body simulations). You can usefully use O(gridcells) number of processors to parallelize this, although in practice you can probably get better utilization by using gridcells/factor processors and dynamically scheduling grid points to processors on an as-ready basis. The computation is basically all floating-point math.

Mandelbrot/Julia and Lyupanov come to mind as potential candidates, but any should do.

Upvotes: 0

dmuir
dmuir

Reputation: 644

You could do a least trimmed squares fit. One use of this is to identify outliers in a data set. For example you could generate samples from some smooth function (a polynomial say) and add (large) noise to some of the samples, and then the problem is to find a subset H of the samples of a given size that minimises the sum of the squares of the residuals (for the polynomial fitted to the samples in H). Since there are a large number of such subsets, you have a lot of fits to do! There are approximate algorithms for this, for example here.

Upvotes: 1

RBarryYoung
RBarryYoung

Reputation: 56755

Well one way to go would be to implement brute-force solver for the Traveling Salesman problem in some M-space (with M > 1).

The brute-force solution is to just try every possible permutation and then calculate the total distance for each permutation, without any optimizations (including no dynamic programming tricks like memoization).

For N points, there are (N!) permutations (with a redundancy factor of at least (N-1), but remember, no optimizations). Each pair of points requires (M) subtractions, (M) multiplications and one square root operation to determine their pythagorean distance apart. Each permutation has (N-1) pairs of points to calculate and add to the total distance.

So order of computation is O(M((N+1)!)), whereas storage space is only O(N).

Also, this should not be either too hard, nor too intensive to parallelize across the cores, though it does take some overhead. (I can demonstrate, if needed).

Upvotes: 0

phs
phs

Reputation: 11061

PageRank may be a good fit. Articulated as a linear algebra problem, one repeatedly squares a certain floating-point matrix of controllable size until convergence. In the graphical metaphor, one "ripples" change coming into each node onto the other edges. Both treatments can be made parallel.

Upvotes: 1

Jarred
Jarred

Reputation: 391

You could generate large (256-bit) numbers and factor them; that's commonly used in "stress-test" tools. If you specifically want to exercise floating point computation, you can build a basic n-body simulator with a Runge-Kutta integrator and run that.

Upvotes: 3

parapura rajkumar
parapura rajkumar

Reputation: 24413

What you can do is

  1. Declare a std::vector of int
  2. populate it with N-1 to 0
  3. Now keep using std::next_permutation repeatedly until they are sorted again i..e..next_permutation returns false.

With N integers this will need O(N !) calculations and also deterministic

Upvotes: 1

Related Questions