پیوندهای مفید
آمار
| تعداد نشریات | 31 |
| تعداد شماره‌ها | 778 |
| تعداد مقالات | 7,449 |
| تعداد مشاهده مقاله | 19,591,557 |
| تعداد دریافت فایل اصل مقاله | 7,520,626 |
GiraDP: Enabling Large-Scale Optimization with Dynamic Programming | ||
| Computational Sciences and Engineering | ||
| مقاله 3، دوره 4، شماره 1، تیر 2024، صفحه 31-40 اصل مقاله (408.95 K) | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22124/cse.2025.29701.1091 | ||
| نویسندگان | ||
| Saeed Mirpour Marzuni1؛ Javad Vahidi* 2 | ||
| 1Department of Electrical and Computer Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran | ||
| 2Department of Computer Science, Iran University of Science and Technology, Tehran, Iran | ||
| چکیده | ||
| NP-hard optimization problems are computationally challenging tasks that require significant resources to solve, particularly as problem sizes increase. In this paper, we introduce a novel framework, GiraDP, which converts dynamic programming problems into graphs and solves these large-scale graphs efficiently. GiraDP addresses NP-hard optimization problems by leveraging advanced graph processing techniques. The framework utilizes Giraph and Hadoop in its architecture to manage extensive datasets and complex computations. It generates input data for Giraph and identifies active vertices that correspond to sub-problems within the larger problem. Our experiments include scenarios with 20, 40, and 60 items, across varying knapsack capacities. The results indicate that while the serial algorithm performs best at low capacities, it fails to handle larger instances due to memory limitations, resulting in heap space errors. In contrast, GiraDP demonstrates superior efficiency and scalability for high capacities and large item sets. The MPI-based approach also shows improved performance over the serial algorithm for larger problems, although it does not match the efficiency of GiraDP. These findings underscore the importance of distributed computing solutions for large-scale optimization problems | ||
| کلیدواژه‌ها | ||
| Giraph؛ Dynamic Programing؛ Hadoop؛ Knapsack Problem | ||
| مراجع | ||
|
[1] M.R. Garey, D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NPcompleteness, W.H. Freeman andCompany, San Francisco. [2] Itzkovitz, A., and Schuster, A. (1999). Distributed shared memory: Bridging the granularity gap. Technion-Israrl Institute of Technology, Faculty of Computer Science. [3] B. Murdock. (2014). Learning in a distributed memory model, in: Current issues in cognitive processes: The Tulane Flowerree symposium on cognition, pp. 69–106 [4] M. Redekopp, Y. Simmhan and V. K. Prasan. (2013). “Optimizations and Analysis of BSP Graph Processing Models on Public Clouds”, in Proceedings of the IEEE 27th International Symposium on Parallel & Distributed Processing (IPDPS’13), Boston, MA, USA [5] “Apache Giraph”, [Online]. Available: http://giraph.apache.org/ [6] “GraphX”, [Online]. Available: http://spark.apache.org/graphx/. [7] J. Gonzalez, Y. Low, A. Kyrola, C. Guestrin, D. Bickson, and M. Hellerstein. (2012). Distributed GraphLab: A Framework for Machine Learning in the Cloud. Proc. the VLDB Endowment, 5(8):716-727. [8] Committee on the Analysis of Massive, Committee on Applied and Theoretical Statistics, Board on Mathematical Sciences and Their Applications, Division on Engineering and Physical Sciences and National Research Council, Frontiers in Massive Data Analysis, The National Academies Press, 2013. [9] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser and G. Czajkowski. (2010). Pregel: A System for Large-Scale Graph Processing. Proceedings of The 2010 ACM SIGMOD International Conference on Management of Data. [10] L. G. Valiant. (1990) A bridging model for parallel computation. Communications of the ACM, vol. 33, no. 8, pp. 103-111. [11] L. Cao , GoldenOrb. (2011). [Online]. Available: https://github.com/jzachr/goldenorb. [Accessed 25 July 2015] [12] “Apache Hama”, [Online], Available: https://hama.apache.org/ [13] “Apache ZooKeeper” [Online]. Available: https://zookeeper.apache.org/ [14] A, Ching, (2013). Scaling Apache Giraph to a Trillion Edges. Availavle: https://www.facebook.com/notes/facebook-engineering/scaling-apache-giraph-to-atrillionedges/ 10151617006153920. [15] Gomez Canaval, S., Ordozgoiti Rubio, B., Mozo, A. (2015). NPEPE: Massive Natural Computing Engine for Optimally Solving NP-complete Problems in Big Data Scenarios. In: Morzy, T., Valduriez, P., Bellatreche, L. (eds) New Trends in Databases and Information Systems. ADBIS 2015. Communications in Computer and Information Science, vol 539. Springer, Cham. [16] Sandra Gomez Canaval, Jose Ramon Sanchez Couso, Meritxell Vinyals. (2016). Solving optimization problems by using networks of evolutionary processors with quantitative filtering, Journal of Computational Science, Volume 16. [17] A. Goldman, D. Trystram. (2004). An efficient parallel algorithm for solving the Knapsack problem on hypercubes, Journal of Parallel and Distributed Computing, Volume 64, Issue 11. | ||
|
آمار تعداد مشاهده مقاله: 84 تعداد دریافت فایل اصل مقاله: 26 |
||