1
$\begingroup$

I am comparing the performance several finite difference methods of solving an initial-boundary value problem. There are several dimensions to this comparison:

  • Number of cells
  • Number of timesteps
  • Solution Method:
    • Explicit (one sweep on a single thread, no iterations)
    • Alternating Direction Explicit (two sweeps on separate threads, no iterations)
    • Alternating Direction Implicit (two sweeps on one thread [TDMA] with three sub-timesteps, no iterations)
    • Fully Implicit (any number of threads, using an iterative BICGSTAB solver)

Question:

My question is this: What metric should I use to compare the relative performance for various combinations of number of cells, number of timesteps, and solution method?

There is some information on performance metrics on David J. Lilja's website. He seems to consider execution time (wall and CPU) as the best metric. But I'm wondering if there might be a more suitable metric for my application.

Here is what I've considered so far:

  • Wall time and CPU time: This is easy to measure, but the problem is that it is only representative for computer architecture where the program is executed. I'm doing most of my testing on a 24 core machine...which won't be representative of typical applications. It would be nice not to have to include a description of the machine's architecture every time I publish results. Are there meaningful ways to normalize measured time to avoid this problem?

  • Number of Operations:

    Sum of (N_iterations*N_sweeps*N_sub-timesteps*N_cells)/(N_threads) across all timesteps.

    This is repeatable and platform independent, but it doesn't include some of the overhead of setting up the initial-boundary value problem and creating matrices, etc. It also makes some simplifying assumptions about threading overhead.

It would also be nice to give a rough estimate of parallel and serial performance, so that someone could get a sense of what the speed up would be for a given number of processors (i.e., a way to extrapolate from the results on my 24 core machine).

|cite|improve this question
$\endgroup$
2
$\begingroup$

I agree with Bill Barth that "time to solution" is a decent metric, but I'm afraid it has a couple of downsides:

  • It's not portable: what's fast on one machine is not guaranteed to be fast on another (modern architectures differ not just in their floating point performance, but also in how their caches work or what their memory bandwidth is).
  • It's implementation specific: maybe algorithm A is just slower than algorithm B, because itwas implemented poorly, or because the compiler didn't optimize it well?
  • Also keep in mind that not every algorithm may scale equally well on every machine -- and that this scalability is again highly dependent on the implementation.

If you are interested in evaluating the methods themselves, rather than their implementation, then I'd suggest you to build an abstract, predictive performance model, based on the following characteristics:

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Two comments: 1. His number of operations measure doesn't measure operations, it counts one unit of something per cell per sub-timestep per sweep per iteration. Unless we know the per-cell work on a particular architecture, it doesn't really tell us much. 2. Algorithmic performance is also contingent. Differing orders of operations can, for example, lead to different numbers of Krylov iterations due non-associativity and/or higher-precision internal operations on some architectures (e.g. 80-bit internal representation on Intel x87 vs. pure 64-bit on AVX). Compiler options can change this, too. $\endgroup$ – Bill Barth Jun 1 '14 at 15:25
  • $\begingroup$ #1: yes, you'll need to count the number of operations per cell update, but if you know these, then you can compute (lightspeed) estimates for most architectures. There is quite a bit of literature on exactly this subject, including my own (linked above). #2: Interesting! I'd be interested in how strong these effects may become. Are you aware of any papers which have thoroughly reviewed this issue? $\endgroup$ – gentryx Jun 1 '14 at 19:27
  • $\begingroup$ There's a paper out there on using exact accumulators for CG, but I don't have the reference handy. You should be able to get an estimate from it. $\endgroup$ – Bill Barth Jun 1 '14 at 22:35
  • $\begingroup$ The machine/compiler dependence in this answer is overblown. If algorithm A is faster on one processor architecture than algorithm B, but the other way around on a different architecture (or using a different compiler), then they were likely already approximately equal to begin with. In that case, we don't care about their relative speed. What you need to do is to also investigate the run time as a function of problem size, because that is the metric that is most likely independent of processor architecture, compiler, etc. $\endgroup$ – Wolfgang Bangerth Jun 2 '14 at 15:29
  • $\begingroup$ @WolfgangBangerth: I disagree. Today's architectures have become incredibly diverse. An algorithm that works well on an NVIDIA GPU is not bound to perform equally well on an Intel Xeon (or even Xeon Phi). Example: 3D stencil codes. On a CPU I could use cache blocking to get around the limit imposed by the system's memory bandwidth. This works extraordinarily well with medium-sized problems, where I can hold multiple layers in L2 or L3. On GPUs there is no such possibility, as the caches are way too small (they tend to need large instances in order to hide main memory latency). $\endgroup$ – gentryx Jun 3 '14 at 18:42
1
$\begingroup$

Time to solution with (approximately) equal error is the best metric you have for comparing algorithms like this, but you need to do it across a range of mesh sizes and PDE coefficients. The explicit methods will have time step constraints that are $O(h^p)$ where $h$ is the mesh size and $p$ is related to the discretizations you use. This means that they will require more time steps on finer grids. The implicit methods won't have this problem, but if you use an iterative solver, then there may be a mesh dependence on the number of solver iterations required. This dependence could cancel out any benefit you have of taking arbitrary time steps, and you may not be able to take large timesteps if the physics requires small ones. There may be several points in parameter space where the methods switch their rank order due to these factors.

The relative rank of the methods should stay the same as you move from machine to machine, but it's not guaranteed. It's best to always run your simulation comparisons on the same architecture.

Parallel speedup is the standard way to measure and extrapolate parallel performance.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I am aware of what causes the difference in runtime between the different solution methods. My question is about finding a metric to compare performance that is architecture agnostic (if possible). Can you please comment on the merits of the options I have considered? $\endgroup$ – Neal Kruis May 30 '14 at 23:43
  • $\begingroup$ They're isn't one. Your number of operations metric doesn't measure the number of instructions that were executed and so it doesn't translate to what you should care about, which is how long it takes to solve the problem on the system you have. $\endgroup$ – Bill Barth May 31 '14 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.