We present a parallel algorithm for computing the correlation dimension (D2) from a time series generated by a dynamic system, using the method of correlation integrals, which essentially requires the computation of distances among a set of points in the state space.
The parallelization is suitable for coarse-grained multiprocessor systems with distributed memory and is carried out using a virtually shared memory model.
The algorithm simultaneously gives all the correlation integrals at various state space dimensions needed to estimate the D2. Two versions are discussed: the first computes all distances between points; the second computes only distances less than a fixed , and employs a boxassisted approach and linked lists for an efficient search of neighbouring points.
The algorithms, coded in Fortran 77, are tested on a heterogeneous network of workstations consisting of various DEC Alphas of different powers, interconnected by Ethernet; the Network Linda parallel environment is used. A detailed analysis of performance is carried out using the generalization of speed-up and efficiency for heterogeneous systems.
The algorithms are fully asynchronous and so intrinsically balanced. In almost all the situations they provide a unitary efficiency. The second version greatly reduces the computational work, thus making it possible to tackle D2 estimation even for medium and high-dimensional systems, where an extremely large number of points is involved.
The algorithms can also be employed in other applicative contexts requiring the efficient computation of distances among a large set of points. The method proposed for the analysis of performance can be applied to similar problems.