Toward first complete performance analysis for Parareal

[tlunet]

Hi @JensHahne,

tooks me a bit more time to implement the block operators manipulations, but it's done and works at least for Parareal (see testing.py). I did reorganize the code tho, and made some few changes, in particular there is two matrices to represent a block operator now instead of one as before (see doc in the README file).

Two things now :

• I used block operators without matrices in main.py : it allows to represent the algorithm and do the performance analysis with Block Operator containing only cost. There is still some bug in the representation with the two other block iteration I added (which represent Approximate Block Jacobi and Approximate Block Gauss-Seidel, but in the same representation as Parareal using F and G).
• Could you implement a method speedUp(N,K) for the BlockIteration class, that would eventually use functionalities implemented in run.py or graph.py ? Once we have that, I could combine it with the error analysis implemented in some getNIter(tolerance) that would return the number of iterations required to reach a given error tolerance (linked to the solved problem).

And last but not least : we didn't set a next meeting, but how is Thursday 17 Nov. at 17h30 (EU time) for you ? I will be traveling on Friday the same time (our usual spot ...).

[JensHahne]

Hi @tlunet

looks good!

1. I fixed the bug. The translation expression -> tasks is a bit tricky and currently depends on if/else, so it's quite error prone. I'll probably rewrite this at some point when I have a good idea how to make it better.
2. Done, at least partially. The function exists and calculates the lower bound on the runtime based on the graph. The speedup would additionally require the cost of time stepping, which we can't currently calculate in a BlockIteration. We need to consider if this is another parameter, or if BlockIteration somehow knows how to calculate the runtime.

I also changed the way the graph is plotted a bit. Instead of instantiating a PintRun object with a BlockIteration, we can now call a plotGraph(N,K) function of a BlockIteration to plot the graph. I think this makes more sense, and the PintRun class is used completely internally, making it a bit easier for a user.

One thing that still confuses me a bit in the code is that we use the BlockOperator class for both a BlockOperator and a BlockCoefficent. On the one hand I understand why, on the other hand it makes the wording in the code a little watery sometimes. But it's probably okay.

Thursday 17 Nov 17:30 eu time works for me.

[tlunet]

Perfect, then Thursday 17 Nov. 17:30 set in my calendar

[tlunet]

Thanks for the implementations ! About the confusion BlockOperator / BlockCoefficients, maybe the term BlockCoefficient should not be used itself : we didn't use it in the GFM paper, and this was introduced only by us when trying to implement object representing everything. It appears almost naturally at the end that we don't need it, so maybe we should stick to the term BlockOperator when talking about this ? After all, this is in fact matrices, and arithmetic operations between matrices produce matrices ... also, the $B_i^j$ are simply block operators of the block iteration then ... 😅

Then for how the Block iteration compute runtime, it depends on the BlockProblems : the latter defines the fine block propagator, from which the cost can be extracted. So if a BlockIteration is linked to a block problem, then we can implement the runtime computation through the BlockProblem. But since the block problem also defines everything else (block discretization, time scheme, ...) we may want to have BlockIteration that does not depend on all of that, to allow analysis where we know the cost of each block operators (measured on cluster, for instance). There are many ways to do that:

• add an other parameter to the BlockIteration that provides the formula for the fine block propagator
• use the consistency condition (assumed True) to determine the formula of the fine block propagator
• use a convention that defines either the fine propagator as $F$ (explicit formulation) or $\phi^{-1}\chi$ (implicit formulation), and add a parameter to BlockIteration which choose between both

Not so sure about what's best for now, working on it ...

[tlunet]

@JensHahne : I think I found a solution to get the sequential runtime from the BlockIteration, without defining a problem. One just have to provide a formula for the fine propagator, that will be evaluated as a BlockOperator object. This should actually be the same as for the predictor, with the only difference being that predictor is still optional.

Since it need some major modifications on the whole code, I will start implementing this in a separate branch, and merge everything when it's fully proofed.

[tlunet]

Done. I've also made some corrections in the extractTasksFromRule method from PintRun in the meantime ...

[JensHahne]

That makes sense, I tried something similar in the beginning. But what happens if we have an inexact timestepper, such as typically in PFASST? For that we would have to create a new BlockIteration, right?

[tlunet]

That's the approximate $\phi_\Delta$ block operator, defined for PFASST on fine and coarse level. But the fine block operator $\phi$ still considers collocation as the fine reference method (since PFASST is supposed to converge toward the collocation solution, from the way it is built).

[tlunet]

Two additional points :

1. the first element of the K parameter in speedup and plotGraph method will always be 0, right (since it is for the initial solution, that won't be updated). Maybe it's better to hardcode it ?
2. not sure yet why Approx. Block Jacobi (ABJ) and Approx. Block Gauss-Seidel (ABGS) have the same theoretical speedup ... iteration of ABJ is fully parallel, while the ABGS does have a sequential part in it, a bit like Parareal (see the graphs ...). Should ABJ does not benefit a bit from this ?

[JensHahne]

1. Sure, i think we should allow different variations to pass the number of iterations (list of length n, list of length n+1 or just an int?). All these variations should be handled internally, I will do that.

2. This is the tricky part about this theoretical speedup, it is sometimes hard to understand and assumes infinite processes. You can plot an optimal schedule by adding, for example, self.pintGraph.computeOptimalSchedule(plot=True) to the getMinimalRuntime function of run.py. It will show you an appropriate schedule to achieve this minimum runtime. In this case, the 'trick' is to use 5 processes instead of 4, which would normally be the case and I think would meet your expectations.
   This is also one thing I need to do. I will find and implement a static scheduling algorithm that allows to find a near perfect schedule for a given number of processes.

[tlunet]

1. Sure, i think we should allow different variations to pass the number of iterations (list of length n, list of length n+1 or just an int?). All these variations should be handled internally, I will do that.

Probably int or list of lenght N would be enough. We are not suppose to iterate for $u_0$ anyway, so why bother considering this option ?

[JensHahne]

Done

[JensHahne]

I added a new scheduler file to handle different schedulers in the future. This moves this part out of the graph, which makes more sense. Currently, we have two working schedulers, an "optimal" scheduler that accepts infinite processes, and a block-by-block scheduler that can be used to simulate typical PinT scheduling. I also want to implement a window strategy scheduler soon, but that's a bit more complicated. In addition to these typical schedulers, I'd like to look at some strategies for scheduling the task graph for a given number of processes.

The speedup now also depends on the schedule, and both the results for a given schedule and the results of an "optimal" schedule are given.

Also, I have started the documentation, but there is still a lot for me to do.