aCorrs-OTF

C++ library with python interface to compute autocorrelations on the fly. Targets many-cores workstation for near-realtime processing of very large data acquisition.

Description

• common.hpp/cpp contains general includes and functions to set mpreal precision and handle lots of threads on Windows.
• acorrs.hpp/cpp provide class templates to compute the autocorrelation of a signal for the k first lags/delays using direct products.
• acorrsFFT.hpp/cpp is an optimised version of acorrs.hpp/cpp using FFT convolutions.
• acorrs_wrapper.cpp is a pybind11 binding of acorrs/acorrsFFT.
• acorrs_otf.py provides the ACorrUpTo factory for convenience of use.

Features:

• Supports Windows 10 and Linux.
• Supports 8 and 16 bit data both signed and unsigned
• Uses MPFR C++ for precision when handling huge numbers
• Uses OpenMP to take advantage of workstation hardware
  • Handles thread affinity on Windows for system with over 64 logical cores
• Uses direct multiplications for small number of autocorrelations and convolutions with FFTW for large numbers.
  • Same results regardless of algorithm (corrects for the inter-fft_buffers correlations up to machine precision)
• Can be fed blocks of data successively and compute the results afterwards (correlations across blocks are ignored)
• Refactored for better structure and compilation times.

Algorithm and optimisation

The algorithm used is the following:

where is the autocorrelation with lag , is the point of the signal, is the signal length, and is its partial mean computed on through with condition .

We re-express it as :

,

with

,

in order to speed up calculations with simple parallelizable forms for and and correcting for the induced errors using the relatively simple and .

In the case, it falls back on the variance and the corrections vanish.

Example:

from numpy import fromfile, uint16
from aCorrs_OTF import ACorrUpTo

x = fromfile("/path/to/potentially/huge/file", uint16)
a = ACorrUpTo(500, x, fft=True, fftchunk=8192) # Initialising and accumulating data

print a.res

Output:

[  3.63332284e+08   7.98651587e+06   7.81700302e+06   7.61148771e+06
   7.56474479e+06   7.58548592e+06   7.60689215e+06   7.66726265e+06
                                  ...
   6.30917894e+06   6.24041607e+06   6.24923766e+06   6.25858389e+06
   6.27447189e+06   6.23658121e+06   6.22335777e+06   6.24173146e+06]

Benchmark example:

from pylab import *
from acorrs_otf import ACorrUpTo
x = randint(-2**15, 2**15-1, 1*2**30, int16)
%timeit a = ACorrUpTo(129, x, phi=8, fft=False)
%timeit a = ACorrUpTo(65, x, phi=0, fft=True)

Compiling

Simply execute make all.