ENTROPY OF ALGORITHMS AND POTENTIAL PARALLELISM

We consider analogies between statistic mechanical approach and computational algorithm description. The notion of algorithm entropy is introduced to characterize measure of potential parallelism and compare algorithms. The value of entropy for some couple of algorithms is evaluated (ordinary block matrix multiplication and Strassen's algorithm, LU decomposition and QIF, particle-particle and particle-mesh algorithms). We discuss thermodynamical approach to the algorithm description in the frame of which one can discover self-organization phenomenon in massively parallel algorithms.