ESTIMATING THE EXECUTION TIME OF PARALLEL DATA MINING ALGORITHMS USING BLOCK MODELS AND PETRI NETS

This paper presents a method for estimating the execution time of parallel data mining algorithms by jointly accounting for computation, data transfer, synchronization, and resource waiting. The algorithm is first decomposed into sequential, conditional, iterative, and parallel blocks, which are then represented by interconnected parts of a timed Petri net. Reserving a resource token at transition start and returning it only upon completion captures the limited capacity of worker nodes. Procedures are described for calibrating computation-stage durations and allocating workload in proportion to the performance of heterogeneous nodes. The method is examined using a numerical scenario with assumed parameters corresponding to one K-means iteration. Among the six configurations considered, the minimum time was 27.90 seconds with 16 workers, with a speedup of 4.73. Changing the allocation across four heterogeneous nodes reduced the modeled time from 44.40 to 34.40 seconds. Analytical estimates agreed with event-driven simulation. These values are not measurements from a real cluster; they demonstrate the model’s internal consistency and sensitivity to allocation decisions. Finally, a protocol is proposed for validating model accuracy against independent experimental data. Keywords: parallel computing, data mining, block model, timed Petri net, execution time, K-means, load balancing, heterogeneous node, synchronization