9
$\begingroup$

I'm profiling the performance of PETSc's linear solvers. As I understand it,

$$\text{speedup}=\frac{\text{Sequential Time}}{\text{Parallel Time}}.$$

I know that running the parallel code on one processor can be used as a proxy for the sequential performance. However, I don't think it is a good measure of an equivalent sequential code due to the parallel overhead incurred. Often, the performance of a sequential code is faster than the parallel performance on a single processor. I suppose that I could search for numerical libraries that implement the same solver, but there is no guarantee that the algorithm is really equivalent.

As I understand it,

$\text{Parallel performance on one processor} = \text{Sequential Time} + \text{Parallel Overhead}$

Thus, if there is a way to quantify the parallel overhead, we could subtract it from the parallel time on one processor to get a better measure of the sequential time.

So, my questions then would be:

  1. Is there a way to compute the parallel overhead of a parallel code run on a single processor when no sequential code is available?
  2. Is it really necessary? Is the parallel performance on one processor good enough to approximate the sequential performance, in general?
Improve this question
$\endgroup$
9
  • $\begingroup$ Speedup is a relative measure and does not say much about absolute performance. Speedup can be measured either to a pure sequential implementation doing same useful work or a parallel implementation (with overhead as you indicate). In each case, the speedup can be quite different due to the parallel overhead and/or possible different execution paths in the instructions set of the application. Why do you want to estimate the parallel overhead? $\endgroup$
    – Allan P. Engsig-Karup
    Commented Jan 29, 2012 at 16:14
  • $\begingroup$ @AllanP.Engsig-Karup: I think my primary motivation just knowing how to get a reasonable estimate of the sequential code when all I have is parallel code. $\endgroup$
    – Paul
    Commented Jan 29, 2012 at 16:45
  • 1
    $\begingroup$ @Paul: I will try to give an actual answer later, but there are often tradeoffs in made in order to get a scalable algorithm. Speedup should really be measured relative to the best serial implementation that, given the same input, produces the same output (modulo small perturbations). $\endgroup$
    – Jack Poulson
    Commented Jan 29, 2012 at 17:36
  • $\begingroup$ @Jack: Agree. Also, in my opinion, relative speedups are not very useful unless absolute timings are given as well. $\endgroup$
    – Allan P. Engsig-Karup
    Commented Jan 29, 2012 at 17:50
  • 1
    $\begingroup$ @Jack: I disagree. The best serial implementation might not be yours. Speed up of a code should probably be measured against its own serial performance. Then, your implementation should be measured against other implementations in both relative and absolute terms. Using an unrelated serial implementation in the numerator is likely to be misleading. $\endgroup$
    – Bill Barth
    Commented Jan 29, 2012 at 19:53

2 Answers 2

Reset to default
5
$\begingroup$

I think that as long as you say what you measure speedup against, no one will fault you for using the time the parallel version of the code takes to run on one processor. If you also give the total time for one of your cases (say the uni-processor time), then people will be able to compare your implementation to others in the literature or to their own.

For some problems, no uni-processor result will even be possible to compute given the constraints of memory or time. Given that, most people understand when looking at speedup results, that the things are computed relative to the smallest number of processors available and that the uni-processor datum is the parallel code run on one processor.

There are no hard and fast rules, but you should be explicit about what you are doing and give your reader enough information to compute other quantities that might interest them.

Improve this answer
$\endgroup$
0
$\begingroup$

I am not familiar with PETSc internals (unlike other PETSc experts here) but imho there should be no parallel overhead with PETSc as long as you run your job as a single process (i.e., no partitioning etc).

Remember PETSc can also be installed without MPI meaning whatever small MPI overhead that might be there (assuming if at all any actual MPI calls are made when running on 1 core which I highly doubt) can also be discounted for.

This obviously is true when parallel overhead is mostly communication and not algorithmic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That may be true for petsc, but it is probably not true for parallel code in general. $\endgroup$
    – Paul
    Commented Jan 29, 2012 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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