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

Main Article Content

Sh.Y.Isroilov1, E.D.Umarov 2, M.Y.Mamirov3, J.Isayev4

Abstract

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.


 

Article Details

Section
Articles

References

Murata T. Petri nets: Properties, analysis and applications. Proceedings of the IEEE. 1989. Vol. 77, No. 4. P. 541–580. https://doi.org/10.1109/5.24143

Ramchandani C. Analysis of Asynchronous Concurrent Systems by Timed Petri Nets. Project MAC, Massachusetts Institute of Technology. Technical Report MAC-TR-120, 1974. https://hdl.handle.net/1721.1/149425

Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters. Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI ’04). USENIX, 2004. P. 137–150. https://www.usenix.org/conference/osdi-04/mapreduce-simplified-data-processing-large-clusters

Zaharia M., Chowdhury M., Das T. et al. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’12). 2012. P. 15–28. https://www.usenix.org/conference/nsdi12/technical-sessions/presentation/zaharia

Amdahl G. M. Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Spring Joint Computer Conference. 1967. P. 483–485. https://doi.org/10.1145/1465482.1465560