The paper describes the parallelization of a method, algorithm and software called RINCCAS (Rotation-Invariant NCC for 2D Color Matching of Arbitrary Shaped Fragments of a Fresco), closely related to a well-known problem of the preservation of national and world cultural heritage, namely—virtual reconstruction of frescoes from their ruins. Developed in MATLAB for participation in a computer competition on the problem, RINCCAS, improves on the classic Normalized Cross-Correlation (NCC) method, but inherits the relatively high cubic complexity. The achieved high accuracy of the positioning (rectangular coordinates and angles of rotation) of the provided images of the fragments also allows effective recognition of the spurious fragments accidentally fallen among in the fresco ruins. To improve the speed and due to the importance of the application, RINCCAS is implemented on a high-performance computing (HPC) system. The tests are done on the supercomputer Avitohol at IICT-BAS. The paper focuses on an Optimal Resource Planning (ORP) for a single Avitohol node that can later be extended to more nodes. The theoretical set-up as well as an analysis of the experiments are presented. In conclusion, the proposed ORP method is summarized for class of algorithms structurally similar to RINCCAS and directions for future work are given.