Dear Michel
1) With the 2nd cut of refactoring we achieved another substantial performance improvement, about 25-30% for the basic KFover all models, i.e. the small- dll and exe- and the larger, sw_euro_3 using either inner loop dll or calling dll in the loop. The times for the larger model are now similar if not marginally better than those for the Matlab Dynare KF loops (i.e. 95.6 sec for new C++ comparing to 97.5 for Matlab KF loop), whilst those for the small are now significantly better.
The main change made in the 2nd cut was overloading member-by-member GeneralMatrix copy () (used by the constructor too) with a memcpy() version in the Dynare++ sylv/cc/GeneralMatrix.h and .cpp files. Together with Vector.h/.cpp and only 3 other (utility) headers from that directory they are also used by C++KF. I added that small subset of sylv files that are needed for KF to the new sylv/cc subdirectory of the mex/sources/kalman (see NOTE (*) below)
Note also, however, that the same performance improvement change may poss. be applied in the main Dynare++ sylv as well as to the (similar) mex/sources/gensylv versions of those files too!
2) I will start devising a method to compare subtask execution times as you suggested but that may be a bit tricky.
However, I would like to try few more things that can be done to improve the performance of the existing C++ code - that is - without major changes being implemented at this stage yet such as e.g. adding Andrea's quasi triangular matrix multiplication library.
As can be seen from the enclosed profile file taken from running the optimised executable with inner loop, the top 5 CPU time "spending" sub-tasks now are the productive gmemm, matrix constructor(still) and matrix inverter (i.e beside the main KalmanTask -filterNonDiffuse and _Unwind_SjLj_Register exception controller, two of which little can be done about).
_______________ NOTE: (*) I.e. There are few small differences between gensylv directory in Dynare mex and the sylv in Dynare ++ and those differences (e.g. missing GeneralMatrix.isZero() in gensylv, etc) are still affecting successful compilation of kalman filter using the gensylv. I would therefore need either to modify gensylv (and I am afraid to break it) or to keep a copy of the small required subset of Dynare++ sylv directory specially associated to the kalman filter. I would suggest the latter as few more changes may be needed for KF and a merge may then poss. be performed at a later stage. ______________
Best regards
George
----- Original Message ----- From: "Michel Juillard" michel.juillard@ens.fr To: "List for Dynare developers" dev@dynare.org Sent: Wednesday, June 10, 2009 8:13 AM Subject: Re: [DynareDev] Kalman Filter
Thanks George,
could you compare the execution time between C++ and Matlab subtask by subtask (almost line by line as far as Matlab is concerned)?
Best
Michel
G. Perendia wrote:
Dear Michel
After the first cut of refactoring, we have mixed results: there is
about
19% performance improvement and approx 30% reduction in use of copy constructor running small model as expected, though no significant performance improvement could be measured on the larger models (euro_sw3.mod) yet - I am looking into the other possible causes for
that
lack of improvement.
Best regards
George
----- Original Message ----- From: "Michel Juillard" michel.juillard@ens.fr To: "G. Perendia" george@perendia.orangehome.co.uk; "List for Dynare developers" dev@dynare.org Sent: Sunday, June 07, 2009 9:01 PM Subject: Re: [DynareDev] Kalman Filter
Thanks George,
very interesting. Please proceed with simplifying the KF code.
All the best,
Michel
G. Perendia wrote:
Dear Michel
I already have a stand-alone exe test I used last week (and uploaded
it
today too) and I run it through gprof earlier today (though, after
wasting
some time last week trying to use a reportedly sophisticated
profiler -
CodeAnalyst from AMD - which, so far, I could not make to work at
all).
The other profiling tool I initially used (and reported) last week
("Very
Sleepy") is an "external", not getting into the code details itself
but
could be run attached externally to either the stand-alone exe test or
the
Matlab running DLL thread too, and that reported for both spending a
lot
(~40%) time in ztrsv solver but, at one snapshot, also pointed to a
lot
of
time spent in dtrsv and GeneralMatrix copy - 50% each. On the
contrast,
gprof is more internal, higher resolution profiler and it puts the
load
weight (>10%) on housekeeping functions but does not even mention
calls
to
external library BLAS functions such as dtrsv and ztrsv.
The both profiling tools, however, seem to confirm what my early code inspection concluded too: a very high, use of (not very productive) General Matrix copy constructor -(e.g. the C++ kalman filter stores
copy
of
few of the main time variant system matrices: F, P and an
intermediate
L
for each step of the time series evaluation and also creates a copy of
the
input T, H and Z at each step as if they may be time invariant too
although
this would not be the case for a simple, no-diffuse KF without missing observations).
This then resulted in high % of time in GeneralMatrix copy() function, (which is called by the copy-constructor explicitly) - i.e. as
reported
by
the both profiling programs: Sleepy: up to 50% at one snapshot point
whilst
gprof gives it the 1st rank with 11% on its own or 27.3% of total with
its
children.
The copy() function is followed by the utility functions such as two varieties (const and non-const) of Vector indexing [] operator and by
the
const and variable varieties of GeneralMatrix::get() elements that
utilise
the previous Vector indexing[] operator and are themselves directly
called
from the heavily used GenaralMatrix copy function among the rest.
According to gprof, the above high burden of copy constructor and the related functions are only then followed by the productive functions
such as
PLUFact::multInvRight matrix multiplication with inversion (used for inversion of the F matrix), the GeneralMatrix constructors and the GeneralMatrix::gemm() - a general matrix multiplication(itself
calling
BLAS dgemm) with 4.7, 3.1 and 2.6 % of total time respectively
NOTE however that gprof profiler paints to an extent different picture
and
does not even mention external BLASS functions such as dtrsv and ztrsv solvers reported as heavy users by the VerySleepy "external" profiler.
All in all, it appears form the both profiler reports and my initial inspection that , for start (and as I initially already intended and suggested to), we should refactor the current heavy use of the
un-productive
General Matrix copy constructor and its current reliance on element-by-element get() function before we get into any further
performance
improvements of the productive functions and external libraries.
Best regards
George
----- Original Message ----- From: "Michel Juillard" michel.juillard@ens.fr To: "List for Dynare developers" dev@dynare.org Sent: Saturday, June 06, 2009 3:08 PM Subject: Re: [DynareDev] Kalman Filter
There are tools to do profiling in C++. All we need is an standalone executable calling the filter. Don't loose time adding timing
function
inside the code. It may be difficult to do profiling in Windows. In
that
case, just prepare the code and we will do the profiling in Linux.
Best
Michel
G. Perendia wrote:
Dear Michel
Yes, as agreed initially
these are the Matlab Dynare KF measures, mainly to show the
proportion
of inversion vs. pure update in Matlab KF. I have not yet done fine profiling for C++, so, not much to upload
either.
- I agree..
Best regards
George
----- Original Message ----- From: "Michel Juillard" michel.juillard@ens.fr To: "List for Dynare developers" dev@dynare.org Sent: Saturday, June 06, 2009 2:10 PM Subject: Re: [DynareDev] Kalman Filter
> Thanks George > > One of the first thing that we need to establish is whether
identical
> basic matrix operations take much longer in the C++ implementation >
than
> in Matlab and, if that it is the case, why. > > > > >> 2) Indeed, and as a significant part of the overall parcel of >>
updating
>> P,
>> one needs to invert the updated F too : >> >> 100000 loops of small model KF 4x4 F matrix inversion: iF = >> >> >> inv(F);
>> Fmx_inv_time = 2.2530 >> >> 100000 loops of the corresponding core KF 8x8 P matrix update: >> P1 = T*(P-K*P(mf,:))*transpose(T)+QQ; >> Pupdt_time = 3.4450 >> >> (and also, 100000 loops of the preceding K = P(:,mf)*iF; >> Kupdt_time = 0.5910) >> >> >> >> >> > How do these operations compare with Matlab on your machine? > > > > >> The convergence of P exploited in Matlab Dynare KFs (which does
not
>> >> >> require
>> further update of P and K and inversion of F ), can improve
greatly
>> performance >> of KF. >> >> e.g.: running Matlab Dynare KF with 57x57 system matrix in 1000
loop
>> 1000 of usual matlabKF_time = 337.1650 >> >> and then using P recursively in the loop with a modified >> >>
kalman_filter.m
>> which returns P too (therefore, utilising P convergence and
avoiding
>> >>
its
>> update for the most of the remaining 999 loops): >> 1000 of recursive: Matlab_rec_KF_time = 11.7060 >> >> >> >> 3) And, although the convergence of P in Matlab KF did not take >>
place
>> for
>> the large sw_euro model which had total run much closer to the
C++KF
>> >> >> (see 3
>> below), as today's check show, the convergence did however take >>
place
>> very
>> early in the Matlab KF running the small model I initially tested >>
(at
>> step
>> t=3!!!) so it >> certainly did affect and, judging from the above results, rather >> >> >> greatly
>> contribute to the very much faster KF loops we experienced
running
>> Matlab KF versus C++ KF in the initial tests with the same small >> >>
model
>> (C++ KF does yet not take >> advantage of convergence and the comparative results were even)!!! >> >> >> >> >> > OK, we forget the first comparison on the small model, because C++ >
and
> Matlab didn't use the same algorithm (no convergence monitorinig in > >
C++).
> Matlab is still faster by 45% on the medium size model. We should >
focus
> on explaining this difference and we don't need to bring monitoring >
the
> convegence of the filter for this particular example. > > Could you please upload on SVN the code that you use for profiling? > > Best > > Michel > > > > >> Best regards >> >> George >> >> >> >> >> > _______________________________________________ > Dev mailing list > Dev@dynare.org > http://www.dynare.org/cgi-bin/mailman/listinfo/dev > > > _______________________________________________ Dev mailing list Dev@dynare.org http://www.dynare.org/cgi-bin/mailman/listinfo/dev
Dev mailing list Dev@dynare.org http://www.dynare.org/cgi-bin/mailman/listinfo/dev
Dev mailing list Dev@dynare.org http://www.dynare.org/cgi-bin/mailman/listinfo/dev
Dev mailing list Dev@dynare.org http://www.dynare.org/cgi-bin/mailman/listinfo/dev
Dev mailing list Dev@dynare.org http://www.dynare.org/cgi-bin/mailman/listinfo/dev