Data Parallel and Scheduling Mechanism Based on Petri Nets

Abstract:

Data-parallel and task-parallel methods are the basic methods frequently used for algorithm design in parallel computing. Data-parallel method as name means is used for partition data to be processed into some small blocks considering storage and computing capacity such as memory size of a computation node, node number to take part in parallel computing and total data size, and etc. On the other hand, data dispensing strategy is an important problem carefully considered to increase the efficiency of computation. According to the characteristics of analysis of digital terrain, petri nets is introduced to describe the parallel relationships within data partitions based on data granularity model considering two kinds of computing modes, shared memory and distributed memory respectively, and corresponding scheduling algorithms are proposed for load balance. The experimental results show that our method is very usable to data partition and dispensation, in particular to distributed memory mode.

• Periodical: Applied Mechanics and Materials (Volumes 543-547)
• Pages: 3264-3267
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.543-547.3264
• Online since: March 2014
• Authors: Wan Feng Dou*, Jing Zhao, Kun Yang, Min Xu
• Keywords: Computing, Data Partition, Data-Parallel, Parallel Digital Terrain Analysis, Petri Net, Scheduling Strategy

References

[1] J.E. Mower: Data-parallel procedures for drainage basin analysis. Computer & Geosciences, Vol. 20 (1994), p.1365.

DOI: 10.1016/0098-3004(94)90060-4

[2] J.Y. Gong and J.B. Xie: Extraction of drainage networks from large terrain datasets using high throughout computing. Computers & Geosciences, Vol. 35(2009), p.337.

DOI: 10.1016/j.cageo.2008.09.002

[3] L.R.A. Ortega: Parallel drainage network computation on CUDA. Compute & Geosciences, Vol. 36(2010), p.171.

[4] X.H. Zhao, Q. Miao, Z.L. Fu et al. Research and realization in parallel algorithm of confluence analysis based on CUDA. Application Research of Computers, Vol. 27(2010), p.2447.

[5] K. Mills, G. Fox and R. Heimbach: Implementing an intervisibility analysis model on a parallel computing system. Computers & Geosciences, Vol. 18(1992), p.1047.

DOI: 10.1016/0098-3004(92)90020-r

[6] D.B. Kidner, P.J. Railings and J.A. Ware: Parallel processing for terrain analysis in GIS: visibility as a case study. Geoinformation, Vol. 1(1997), p.183.

[7] D. Germain, D. Laurendeau and G. Vézina: Visibility analysis on a massively data-parallel computer. Concurrency: Practice and Experience, Vol. 8 (1996), p.475.

DOI: 10.1002/(sici)1096-9128(199607)8:6<475::aid-cpe254>3.0.co;2-a

[8] A.Q. Zhang and Z.Y. Mao: A new scheduling algorithm for direct graph-based parallel computing, Chinese Journal of Computers, Vol. 32(2009), p.2178.

[9] J.C. Du, H. Huang, D.X. Chen and L. Xie: Optimum degree of parallelism-based task dependence graph scheduling scheme. Chinese Journal of Software, Vol. 10(1999), p.1038.

[10] S. Ichiro and L. Harngdar: Temporal Petri Nets and Their Application to Modeling and Analysis of a Handshake Daisy Chain Arbiter. IEEE Transactions on Computers, Vol. 38(1989), p.696.

DOI: 10.1109/12.24271