Databases
StackOverflow2013
Postsdbo
POWhy does the speed of this SOR solver depend on the input?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does the speed of this SOR solver depend on the input?
    primarykey
    data
    text
    <p>Related to my <a href="https://stackoverflow.com/questions/2388196/how-to-speed-up-my-sparse-matrix-solver">other question</a>, I have now modified the sparse matrix solver to use the SOR (Successive Over-Relaxation) method. The code is now as follows:</p> <pre><code>void SORSolver::step() { float const omega = 1.0f; float const *b = &amp;d_b(1, 1), *w = &amp;d_w(1, 1), *e = &amp;d_e(1, 1), *s = &amp;d_s(1, 1), *n = &amp;d_n(1, 1), *xw = &amp;d_x(0, 1), *xe = &amp;d_x(2, 1), *xs = &amp;d_x(1, 0), *xn = &amp;d_x(1, 2); float *xc = &amp;d_x(1, 1); for (size_t y = 1; y &lt; d_ny - 1; ++y) { for (size_t x = 1; x &lt; d_nx - 1; ++x) { float diff = *b - *xc - *e * *xe - *s * *xs - *n * *xn - *w * *xw; *xc += omega * diff; ++b; ++w; ++e; ++s; ++n; ++xw; ++xe; ++xs; ++xn; ++xc; } b += 2; w += 2; e += 2; s += 2; n += 2; xw += 2; xe += 2; xs += 2; xn += 2; xc += 2; } } </code></pre> <p>Now the weird thing is: if I increase <code>omega</code> (the relaxation factor), the execution speed starts to depend <em>dramatically</em> on the values inside the various arrays!</p> <p>For <code>omega = 1.0f</code>, the execution time is more or less constant. For <code>omega = 1.8</code>, the first time, it will typically take, say, 5 milliseconds to execute this <code>step()</code> 10 times, but this will gradually increase to nearly 100 ms during the simulation. If I set <code>omega = 1.0001f</code>, I see an accordingly slight increase in execution time; the higher <code>omega</code> goes, the faster execution time will increase during the simulation.</p> <p>Since all this is embedded inside the fluid solver, it's hard to come up with a standalone example. But I have saved the initial state and rerun the solver on that state every time step, as well as solving for the actual time step. For the initial state it was fast, for the subsequent time steps incrementally slower. Since all else is equal, that proves that the execution speed of this code is dependent on the values in those six arrays.</p> <p>This is reproducible on Ubuntu with g++, as well as on 64-bit Windows 7 when compiling for 32-bits with VS2008.</p> <p>I heard that NaN and Inf values can be slower for floating point calculations, but no NaNs or Infs are present. Is it possible that the speed of float computations otherwise depends on the values of the input numbers?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USThomas
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAre you sure you do not measure some other codepaths that depend on the values of the calculations?
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. USebo
    2. COIf you continue to have performance issues, consider using a GPU for these calculations. GPU's are very good at sparse matrix work.
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. USMark
    3. CO@ebo: I used the real-time clock in Linux to measure just this call. So yes, I'm quite sure.
      singulars
      1. POWhy does the speed of this SOR solver depend on the input?
      1. USThomas
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload