Physics at the Terascale Helmholtz Gemeinschaft

Millepede II

Introduction

Millepede II is the successor of Millepede, a package for linear least squares fits with a large number of parameters. Both have been developed as experiment independent programs by Prof. V. Blobel. Documentation and source code of Millepede and of the first version of Millepede II are available on his web page (or mirror). Meanwhile, the Statistics Tools group of the Analysis Centre took over the maintenance of Millepede II.

The first Analysis Centre release, version V02-00-01, contains V. Blobel's 2009 development and small changes/fixes coming from CMS experience by G. Flucke. Further development, mainly by C. Kleinwort for usage in CMS, adds

  • auto-detection of bordered band matrices in the local fit to speed up processing if e.g. fed with tracks fitted using the broken lines technique (cf. NIM A566:14-17,2006 by V. Blobel and GeneralBrokenLines),
  • the possibility to ignore or compress rare off-diagonal elements of the global matrix (to reduce space requirements),
  • shared-memory parallelisation of most parts of the code (track fits, MINRES, inversion) using OpenMP™,
  • the possibility to read gzipped C/C++ binaries,
  • further fixes/improvements not only from CMS experience.

Using these features allows CMS silicon tracker alignment to determine 200 000 parameters in one go fitting more than 20 million tracks, including 3.6 million cosmic ray tracks and about 375 thousand muon pairs from Z decays reparametrised as one fit object with a vertex constraint and adding a virtual Z mass measurement (cf. CMS-CR-2011-323). The computing requirements on an Intel™ Xeon™ L5520 with 2.27 GHz using eight threads are 44.5 h CPU (but only 10 h wall clock time) and less than 32 GB of RAM.

Availability

The project has been migrated to GitLab at DESY (code and wiki).

The source code of Millepede II is provided by DESY under the terms of the LGPLv2 license and is maintained in a publicly accessible subversion repository at DESY that can be browsed via viewvc or WebSVN.

The recommended version is publicly available via the subversion command line:

svn checkout http://svnsrv.desy.de/public/MillepedeII/tags/V04-10-01 MillepedeII

For development, please check out the trunk:

svn checkout https://svnsrv.desy.de/desy/MillepedeII/trunk MillepedeII

You could replace /desy/ by /svn/ or /basic/ for other authenticiation methods, see subversion server access info. To be allowed to commit, please contact the mailing list, mentioned below.

In addition tarballs can be found here.

  1. The software can be freely used for research and education. We expect that all publications describing work using this software quote at least one reference (see here or below).
  2. Disclaimer: This software is provided without any expressed or implied warranty. In particular there is no warranty of any kind concerning the fitness of this software for any particular purpose.

Compilation

Since V04-00-00 (fortran90)

The delivered Makefile foresees the compilation of a single pede executable with dynamic allocation of memory. Simple 'cd MillepedeII; make', compiles the executable. This requires gcc version 4.4 or higher. For larger problems (>8GB of memory) a 64bit system is necessary.

Before V04-00-00 (Fortran77)

The delivered Makefile foresees the compilation of pede executables with different amount of memory. Simple 'cd MillepedeII; make', compiles three executables: pede (400 MB memory), pede_1GB and pede_2GB (memory as the name indicates). If your problem requires more space due to a high number of parameters or a dense matrix, you need a 64-bit system and probably a special compiler flag, see the comments in the Makefile. The maximum memory possible is with 32 bit integers for internal (FORTRAN) memory management 2147483647 = (231 - 1) words, i.e. about 8.5 GB. With version V03-01-00 64 bit integers are available (FORTRAN95, gfortran) to overcome this limit.

The Makefile of the recent version is written for gcc 4.1.2 (the reference compiler is: gcc version 4.1.2 20080704 (Red Hat 4.1.2-50) ), but it works for later gcc relases until 4.4.X. See comments in the Makefile to make it work for gcc version 3.X.Y (64 bit integers not recommended) or gcc 4.5.X and 4.6.X. Please contact the mailing list about necessary fixes you know about to use other compilers.

The gcc 4.4.0 compiler is not recommended. When starting from perfect alignment, we noticed that it can happen that pede stops without finding a non-trivial minimum ("Function not decreasing..."). This is not understood, but since gcc 4.1.2 and gcc 4.3.4 behave like expected, i.e. finding small corrections, we guess that it is a gcc 4.4.0 problem. Update: Same seen also with gcc 4.5.1! Needs to be investigated...

Starting with gcc 4.4 the MINRES pre-conditioner for bandwidth zero (PRECON) is not compiled correctly. This problem is avoided with version V03-04-01 by rearranging some lines in the source code.

Documentation

Since version V04-00-00 documentation with doxygen is available in html format.

Version History and Features

Version V04-11-00 (Now on GitLab)

The project has been migrated to GitLab at DESY (code and wiki).

Version V04-10-01 (Last on SVN)

Fortran code modernized further (assumed-size array arguments replaced). Additional cases of out of range read access fixed.

Version V04-10-00

The code quality has been improved. Compilation with '-fcheck=all’ has been used to check for out of index range array access (few cases for read access found and fixed) and ancient Fortran statements have been replaced. For one user an EQUIVALENCE statement in the internal histogramming produced (with gcc10) memory corruption with NANs leading to an indefinite loop.

Version V04-09-05

Fixed uninitialized values in QL decomposition of constraints matrix (introduced in V04-09-04).

Version V04-09-04

Exploit sparsity and decomposition of constraints matrix into disjoint blocks for all solution methods (e.g. QL decomposition, MINRES preconditioner).

Version V04-09-03

Memory allocation for internal histograms is now dynamic in terms of number of binary files.

Version V04-09-02

The warning messages for severe warnings (exit code 2) have been improved.

Version V04-09-01

All indices for constraint matrices have been upgraded to 64 bit. Previously a segmentation fault happened for (number of parameters) * (number of constraints) >= 2^31.

Version V04-09-00

Optional usage of external linear algebra libraries to speed up solution. Implemented has been LAPACK and tested with the Intel MKL and the OpenBLAS library.

Two new solution methods based on matrix factorisation are available optionally: fullLAPACK and unpackedLAPACK. They differ in the LAPACK storage mode (packed vs unpacked).

Version V04-08-02

New command monitorprogress to monitor progress in operations on global and constraints matrices with additional printout into the log file.

Version V04-08-01

Fixing potential integer overflows for elimination of constraints. This happens for all solution methods except MINRES if the square of the number of (variable global) parameters is larger than 2^31.

Version V04-08-00

New solution method (Cholesky) decomposition added. It's faster than inversion but does not calculates parameter errors.

Version V04-07-04

Bug fix (integer overflow) and little speedup (~15%) for solution of large problems by inversion.

Version V04-07-03

The solution by inversion with Lagrange multipliers has been fixed. (It was broken since V04-06-00.)

Version V04-07-02

More robust sorting of constraints for splitting into disjoint blocks.

Version V04-07-01

The counting of the appearance of global parameters in the binary files can now be done on record (e.g. track) level instead of equation (e.g. measurement) level. This is enabled with the new command countrecords and makes the iteration of the first data loop (by iterateentries) obsolete.

Version V04-07-00

Implementation of parameter groups (sets of adjacent global parameters (labels) appearing in the binary files always together). Used to speed up construction of global matrix. Similarity operations are now aware of sparse (rectangular) matrices.

Solution with method sparseMINRES got considerably faster.

Version V04-06-01

Modifications for compilation with PGI compiler (make -f Makefile_pgi).

Version V04-06-00

Checking global parameters for disjoint blocks now. In case of solution by inversion (optionally with constraints handled by elimination) switch to block diagonal storage mode (to save memory and cpu time).

Version V04-05-04

Method sparseMINRES fine again.

Version V04-05-03 (bad)

Improved stability. The line search is now skipped in case the current solution is numerically too close to the minimum. Method sparseMINRES broken due to bad back port from development version.

Version V04-05-02

Two (very old) cases of access to arrays outside of the defined bounds (reported by gcc9) have been fixed.

Version V04-05-01

Fix for modified text parser (concerning leading blanks in lines with only numbers).

Version V04-05-00

Update of (approximate) string matching for keyword detection. Matching is now symmetric in pattern and text. Previously e.g. a binary file with the letters from 'Cfiles' in the name in that order was treated as that keyword and not as a binary file.

Version V04-04-01

Cleanup of operations (open, close, rewind) on binary files. New command closeandreopen to enable closing and reopening of binary files to limit the number of concurrently open files. The modification dates of the files are monitored to ensure data integrity.

Version V04-04-00

Constraints are now sorted and split into disjoint blocks to speed up calculation of rank and QL decomposition by block matrix algebra. This works best if the label sets of the involved alignable objects are disjoint too.

Version V04-03-10

Some minor fixes, additional level of detail (appearance range of global parameters in binary files) for checkinput mode.

Version V04-03-09

Fixes for special data blocks and not decreasing function value.

Version V04-03-08

More debug output in case of problems reading the binary Cfiles.

Version V04-03-07

Fix for downweighting correction (Cauchy) of global chi2.

Version V04-03-06

Fix for abort on singular QL decomposition of constraints matrix.

Version V04-03-05

Monitoring of pulls (monitorpulls) and scaling of measurement errors (scaleerrors) from binary files added. Abort now in case of singular QL decomposition of constraints matrix (solution by elimination).

Version V04-03-04

Bug fix for monitoring of residuals.

Version V04-03-03

Contains few fixes, mainly improved response to numerical problem leading before to "Function not decreasing".

Version V04-03-02

The monitoring of the residuals per local fit cycle has been implemented and is selected by monitorresiduals. The normalized residuals are grouped by the first global label and the median and the RMS (from the median of the absolute deviations) per group are written to the new text file millepede.mon.

Version V04-03-01

Contains fixes and improvements for MINRES preconditioning:

  • Preconditioning with a band matrix works now for solution by elimination of constraints too.
  • Preconditioning with a skyline matrix added to avoid the potential rank deficits of a band matrix (by reduction to the diagonal).

Version V04-03-00

Contains some new features:

  • Solution by elimination for problems with linear equality constraints has been implemented (as default, new command withelimination) in addition to the Lagrange multiplier method (new command withmultipliers).
  • The skipping of empty constraints (without any variable parameters) can be enabled with the new command skipemptycons.
  • With new command checkinput detailed checks of input data (binary files, constraints) are performed, but no solution will be determined. Some input statistics is available in the output file millepede.res.
  • The iteration of the entries cut has been implemented with the new command iterateentries. In the second iteration measurements with any parameters fixed by the previous entries cut are skipped. Useful if for some measurements different parameters have different number of entries.

Version V04-02-03

Contains some new features:

  • Dynamic entries check added. Due to rejected local fits degrees of freedoms may get lost. The entries from accepted local fits are counted and checked for each internal iteration.
  • Weighted constraints implemented with new option weightedcons.

Version V04-02-02

Contains some new features:

Printout of global parameter counts from binary files added to result file with new option printcounts.
Aborting in case of (C) read errors.
Storage of values read from text files as doubles implemented.

Version V04-02-01

Integer overflow in auto detection of bordered band matrices for local fits with huge number of parameters fixed.

Version V04-02-00

The reading of records from C binary files containing doubles (indicated by negative record length) instead of floats has been implemented. The complete local fit is now in double precision.

Version V04-01-04

Integer overflow in auto detection of bordered band matrices for local fits with huge number of parameters fixed.

Version V04-01-03

Fixed V04-01-02.

Version V04-01-02

Has bug, crashing with gcc-4.8.

Contains some minor fixes, e.g:

  • Matrix inversion for local fit uses tolerance as specified by compiler instead of fixed value.
  • Python script (tools/readMilleBinary.py) to print binary files accepts now command line arguments (file name, number of records).

Version V04-01-01

The exit code and message of the pede executable are written to the file millepede.end :

  • -1: Still running or crashed
  • 00: Ended normally
  • 01: Ended with warnings (bad measurements)
  • 02: Ended with severe warnings (bad global matrix)
  • 10-17: Aborted, problem with steering
  • 20-26: Aborted, problem with binary data
  • 30-34: Aborted, internal problem

Version V04-01-00

Solution method MINRES-QLP added. This advanced MINRES version is selected by 'method sparseMINRES-QLP ..' or 'method fullMINRES-QLP ..'.

Version V04-00-04

Fixes for integrity check of binary files (program abort) and reading of MINRES tolerance parameter (mrestol set to zero).

Version V04-00-03

Added checks of integrity of binary files. The integers are checked for the consistency of labels and markers (zeros) and the floats for NaNs (not a number).

Version V04-00-02

Allow parallel make and other minor changes to Makefile, e.g.remove option for LARGE integers to be INTEGER*4 to allow compilation on 32-bit systems (but medium size problem now require a bit more memory).

Version V04-00-01

The line search to optimize the solution is now configurable. The new option linesearch allows to select the iterations (solutions) with line search: >2: all, =2: all with (next) Chi2 cut scaling factor =1., =1: last, <1: none. The default value is '2', the previous behaviour corresponds to '3'.

Minor fixes. Option 'maxrecord' working again with OpenMP.

Version V04-00-00

First "fortran90" version. The source code has been transformed from fixed form (punch card image) Fortran77 to free form fortran90. Major changes:

  • Use of dynamic memory allocation in fortran90 instead of fixed size COMMON block for dynamic data structures (matrices, vectors). Only one Pede executable is sufficient for all application sizes. This requires gcc version 4.4 or higher.
  • Documentation with doxygen. This includes the draft manual from V. Blobel (2007), the major changes with respect to that and the list of Pede options and commands. It is available in html format.

Version V03-04-05

Bug fixes:

  • Linesearch: Use proper size of vectors (NVGB instead of NAGB).
  • Measurements defined in steering files: Label not replaced anymore by index during construction of sparsity structure of global matrix.

Version V03-04-04

  • Adjustments/comments to Makefile for more recent gcc (e.g. 4.6.X).
  • New option 'memorydebug' (1: just printing, >1: more debug).
  • Little bugfix, cleanup of algebra routines.
  • Add plot "<ndf> vs file".

Version V03-04-03

Minor bug fix to tools/readPedeHists.C to read pede histogram output.

Version V03-04-02

Bug fixes: (global matrix) update cache buffer overrun from rejected records; integer overflow for final rejection ratio.

Version V03-04-01

Compilation problem for gcc version 4.4/4.5 avoided for MINRES pre-conditioner. New features:

  • Method MINRES makes use of pre-conditioners for error calculation (option 'errlabels') too.
  • Method INVERSION calculates global correlations for option 'globalcorr'.

Version V03-04-00

New features:

  • Methods INVERSION and fullMINRES parallelized.
  • Interfaced to GeneralBrokenLines (external track seed).
  • For insufficient constraints switch to SUBITO (-s) mode to avoid dead loops (unless option FORCE (-f) specified).

Version V03-03-00

Cleanup of printout and new features:

  • For method MINRES new option 'errlabels <lab1> .. <labn>' to define up to 100 global parameters for which errors are calculated.
  • More parts of the code (like the local fit) are parallelized with OpenMP. With 'threads <nproc> <nread>' the number of threads for processing (nproc) and reading binary files (nread) in parallel can be specified.
  • With Makefile option 'SUPPORT_ZLIB = yes' gzipped binary files can be read directly.
  • Weights have been implemented for the records. They are defined per binary file with the file name '<filename> -- <weight>'.

Version V03-02-02

Methods inversion and diagonalization working again!

Version V03-02-01 (MINRES only)

Methods inversion and diagonalization broken!

  • Bug fix: nsingle=2n-1 now possible for option 'pairentries'.
  • New option 'maxrecord <record>' to set record limit for input from binary files.
  • New option 'matmoni <record>' to monitor construction of sparse global matrix. Every <record> records the number of off-diagonal elements, the compression ratio and the memory consumption is printed.
  • Cleanup: For OpenMP the maximal number of threads is set at run time. For the final Chi2/ndf the number of degrees of freedom (ndf) is corrected for the number of global parameters.

Version V03-02-00 (MINRES only)

Methods inversion and diagonalization broken!

  • Optimization of memory usage for sparse storage of global matrix. With option 'compress' the sparsity information is compressed and off-diagonal elements with single entries are stored in single precision (lossless as input from binary file is single precision only). With 'pairentries <ncut> <nhist> <nsingle>' off-diagonals with up to <nsingle> entries are stored in single precision (unintended feature: for nsingle=2n-1 and nhist<=nsingle all off-diagonals are in single precision).
  • Parallel processing for solution with 'method sparseMINRES'. Most time is spent in AVPROD (multiplication of global matrix with vector). This has been parallelized with OpenMP™. The number of threads are specified with 'threads <nthread>'.
  • The default of the internal convergence parameter RTOL for MINRES has been changed from 10-8 to 10-6. It can be set by 'mrestol <rtol>'.

Version V03-01-00

Large Integers are used for internal (FORTRAN) memory management. The Makefile allows to select 32 bit (LARGE_SIZE=4) or 64 bit (LARGE_SIZE=8) integers.

Version V03-00-02 (Last 32 bit recommended version)

  • (V04-00-02 should work on 32-bit systems as well)
  • several bug fixes
  • cut 'pairentries <ncut> <nhist>' implemented. Rare global parameter pairs (off-diagonal elements of global matrix) with less than <ncut> entries are neglected. Optional <nhist> defines upper bound for histogramming.

Version V03-00-01

  • fix that additional text steering files stated after the first binary file are silently ignored (bug present since V02-00-00)
  • small fix for auto detection of bordered band matrices
  • 'chisqcut f1 f2' with f1<1.0 will disable Chi2 cut (including Huge) in FIRST iteration
  • 'subito' option reimplemented (lost since V02-00-00)
  • 'entries n' checks for n>0 (n=max(1,n))
  • for 'debug' some more statistics for fixed parameters is calculated (fraction of equations, records with fixed parameters)

Version V03-00-00

  • local (track) fit improvements:
    • fast methods for band matrix structure coming from broken lines track fit
    • fix single precision leak in local fit
    • reject fits with rank deficit
  • new inline simulation
    • simple silicon strip tracker
    • multiple scattering in detector material
    • track models with different accounting of multiple scattering (-t=SL0/SLE/BP/BRLC/BRLF, details in mptst2.F)
  • resurrected Eigenvalue output lost in V02-00-00
  • histogram output:
    • separate residuals for measurements with and without global parameters (e.g. for multipe scattering treatment via pseudo measurements)
    • add histograms for pulls of measurements
  • detect NAN to avoid endless loops
  • tool readMilleBinary.py to deal also with Fortran binaries
  • improved some text output

Version V02-00-01

  • Fix histogram output (histograms partly empty due to bug introduced when cleaning compiler warnings).
  • Moved macro readPedeHists.C to new 'tools' subdirectory, added python script readMilleBinary.py to dump binary files.

Version V02-00-00

Recent development has been presented at the 3rd LHC Detector Alignment Workshop in June 2009 by Prof. Blobel. The main new features/changes are:

  • Solution methods:
    • iterative solution method named correctly MINRES, not GMRES,
    • remaining methods are 'sparseMINRES', 'fullMINRES', 'inversion' and 'diagonalisation', others have been removed.
  • New preconditioning for MINRES method:
    • not limiting the number of parameters to 46340,
    • preconditioning always applied (except if 'bandwidth 0' specified),
    • recommendation: do not specify bandwidth option (uses bandwith 1),
    • if bandwith option explicitely requested, another method will be used.
  • Fix problem in hash values for label pairs that was limiting to 46340 parameters.
  • The line search algorithm that is applied after calculating the step direction in a millepede iteration looks for slope = 0, not a function value minimum. This achieves better stability with outlier rejection.
  • Speed up of LOOP2 for sparse matrix storage.
  • Further new options:
    • 'matiter <number>': Force re-calculation of the matrix in the first <number> iterations - slower, but more robust in case of large number of rejects due to too many outliers.
    • 'presigma <number>': Assign pre-sigma <number> to all labels where no explicit presigma is set.
    • 'regularisation <number>': Regularisation with τ = <number>, i.e. add τ ∙ ‖x‖ to the minimised function where x is the vector of alignment parameters, weighted with the inverse of their individual presigma; this should reduce the influence of weak modes, but needs careful studies.
    • 'regularisation <number1> <number2>': Same as having both 'regularisation <number1>' and 'presigma <number2>'.
    • 'hugecut <number>': to determine huge outlier rejection cut that is always active, irrespective of chisqcut settings, default stays at 50, minimum value is 1.0.
  • Steering files now must end with '.txt'.
  • The subversion repository includes the macro readPedeHists.C to convert the pede histogram file millepede.his into ROOT format and/or produce a postscript file from it.

The manual still needs to be updated.

Hardcoded Limits

Since V04-00-00 (fortran90)

For the input to pede the resources (memory, handles for C binary files, ..) are allocated dynamically and may be limited by the system. The are no explicit limits on the number of global parameters or number of (C) binary files.

For the internal monitoring some arrays still have fixed size:

  • Maximum number of points for xy-scatter data (e.g. used for <χ2/ndf> per file plots): 200 (500 since rev92) (JFLC(5,IG) = 200 in 'mphistab.F', take care that NARR = NUMGXY * "desiredValue" - if more points requested, points are averaged).

For the steering text files the maximal length of a line is 1024 characters. This limits the length of file names too.

Before V04-00-00 (Fortran77)

Since pede is Fortran77, several array lengths have a fixed size, e.g.

  • Maximum number of files (binary and text files): 500 (PARAMETER (MFILES=500) in 'mpinds.inc'), maximum number of C-binaries is 490 (#define MAXNUMFILES 490 in 'readc.c')
  • Maximum number of characters of file names: 500 (CHARACTER*500 TFD(MFILES) in 'mpinds.inc')
  • Maximum number of points for xy-scatter data (e.g. used for <χ2/ndf> per file plots): 200 (500 since rev92) (JFLC(5,IG) = 200 in 'mphistab.F', take care that NARR = NUMGXY * "desiredValue" - if more points requested, points are averaged).

The given values refer to version 90 of the trunk (i.e. tag V03-04-04) .

User Requests

Following user requests will be considered for future releases. Please contact the mailing list (see below) for bug reports or user requests.

  • Configuration of a global scaling factor for the residual errors.
  • Get rid of remaining gcc 4.X.Y compiler warnings.
  • For calculation of the ratio of variable parameters with pre − σ, do not add those parameters failing the 'entries' cut to the numerator.
  • Update the manual:
    • document new features and steering options
    • add a simple step-by-step example, probably explaining the setups simulated with the '-t' options, including an explanation of the generated constraints.

Mailing List

Your are welcome to join the mailing list that will be used for announcements, but should also serve for user questions and discussions. You are also allowed to post questions without subscribing, though subscription is preferred.

Collection of Users

This list is probably incomplete - you are very welcome to add yourself!

CMS

CMS has been the main user driving the developments during LHC run 1.

  • Alignment of the CMS tracker with LHC and cosmic ray data, CMS collaboration, 2014 JINST 9 P06009
  • Alignment of the CMS silicon tracker during commissioning with cosmic rays, 2010 JINST 5 T03009
  • Alignment of the CMS silicon strip tracker during stand-alone commissioning, W. Adam et al., 2009 JINST 4 T07001
  • CMS silicon tracker alignment strategy with the Millepede II algorithm, G. Flucke, P. Schleper, G. Steinbrück, M. Stoye et al., 2008 JINST 3 P09002

ALICE

ATLAS

Belle

Belle II

CBM

  • Track based alignment procedure for the CBM silicon tracking detector, S. Das and H. R. Schmidt, Journal of Physics: Conference Series 1390(2019) 012122, doi:10.1088/1742-6596/1390/1/012122

Hades

MEG

PHENIX

References

  • A New Method for the High-Precision Alignment of Track Detectors, Volker Blobel and Claus Kleinwort, Proceedings of the Conference on Adcanced Statistical Techniques in Particle Physics, Durham, 18 - 22 March 2002, Report DESY 02-077 (June 2002) and hep-ex/0208021
  • Alignment Algorithms, V. Blobel, Proceedings of the LHC Detector Alignment Workshop, September 4 - 6 2006, CERN
  • Software alignment for Tracking Detectors, V. Blobel, NIM A, 566 (2006), pp. 5-13, doi:10.1016/j.nima.2006.05.157

 

 
top