زمان‌بندي بي‌درنگ چندپردازنده‌اي شبه‌افرازي در سيستمهاي مديريت جريان داده
محورهای موضوعی : مهندسی برق و کامپیوتر
مهدی عالمی
1
(دانشگاه شهید بهشتی)
مصطفی حق‌جو
2
(دانشگاه بین‌المللی پیام نور کیش)
کلید واژه: توزيع بار چندپردازنده زمان‌بندی بی‌درنگ افرازی بهره‌وری,
چکیده مقاله :
در سيستمهاي مديريت جريان داده، داده‌هاي جرياني وارد سيستم مي‌شوند و پرس و جوهاي ذخيره‌شده بر روي اين داده‌ها اجرا مي‌شوند. با توجه به بار کاري بالا نياز به ظرفيت پردازشي بالا است و استفاده از چندپردازنده بايد در نظر گرفته شود. همچنين در سيستمهاي بي‌درنگ پرس و جوها تحت مهلت مشخصي بايد کار خود را به اتمام برساند. از رويکردهای موجود در زمان‌بندی چندپردازنده‌ای بی‌درنگ رويکرد افرازي است که هر پرس و جو با توجه به بهره‌وري که نسبت زمان اجرا به دوره است به پردازنده‌ها انتساب داده مي‌شود و فقط در آن اجرا مي‌شود. براي نزديک‌شدن به جواب بهينه در اينجا پرس و جوهايي که در يک پردازنده جا نمي‌گيرند بر اساس بهره‌وري شکسته مي‌شوند و در بين پردازنده‌ها پخش مي‌شوند. اين سيستم با داده‌هاي واقعي شبکه تست شده است. مقايسه‌ها نشان مي‌دهد که رويکرد مورد نظر توانسته است نسبت به رويکرد افرازي ساده ميزان از دست رفتن مهلت‌ها را کاهش دهد و ميزان بهره‌وري سيستم را بالا ببرد.
In data stream management systems as long as streams of data arrive to the system, stored queries are executed on these data. Regarding high workload, high processing capacity is required, leading to consider multiple processors to cope with it. Partitioning approach, one of the main methods in multiprocessor real-time scheduling, bind each query to one of processors based on its utilization, ratio of estimated execution time to period, and instances of each query which should be completed under defined deadline can only be executed on specified processor. Each query which could not be assigned to any processor can be split based on utilization of processors and spread among them, causing to get closer to optimum result. This system has been examined with real network data, showing lower miss ratio and higher utilization in comparison to simple partitioning approach.
[1] A. Arasu, et al., "STREAM: the stanford stream data manager," in Proc. of ACM SIGMOD Int. Conf. on Management of Data, SIGMOD'03, p. 265, New York, USA, Jun. 2004.
[2] S. Babu and J. Widom, "Continuous queries over data streams," ACM SIGMOD Record, vol. 30, no. 3, pp. 109-120, 2001.
[3] Y. Wei, S. H. Son, and J. A. Stankovic, "RTSTREAM: real-time query processing for data streams," in Proc. 9th IEEE Int. Symp. On Object/Component/Service-Oriented Real-Time Distributed Computing, pp. 141-150, 2006.
[4] S. Sven, L. Thomas, S. Daniel, and L. Wolfgang, "Real-time scheduling for data stream management systems," in Proc. of the 17th Euromicro Conf. on Real-Time Systems, pp. 167-176, 6-8 Jul. 2005.
[5] L. Hennadiy, C. Samarjit, and H. A. James, "Multiprocessor extensions to real-time calculus," in Proc. 30th IEEE Real-Time Systems Symp., RTSS, pp. 410-421, 1-4 Dec. 2009.
[6] P. L. Holman, On the Implementation of Pfair - Scheduled Multiprocessor Systems, Ph. D Thesis, Chapel Hill, 2004.
[7] J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah, "A categorization of real - time multiprocessor scheduling problems and algorithms," Handbook on Scheduling Algorithms, Methods, and Models, vol. 30, pp. 1-19, 2004.
[8] A. A. Safaei, M. Alemi, M. Haghjoo, and S. Mohammadi, "Hybrid multiprocessor real-time scheduling approach," International Journal of Computer Science Issues, vol. 8, no. 2, pp. 171-178, Mar. 2011.
[9] D. Abadi, et al., "Aurora: a data stream management system," Proc. of ACM SIGMOD Int. Conf. on Management of Data, SIGMOD'03, p. 666, New York, USA, Jun. 2004.
[10] S. Schmidt, H. Berthold, and W. Lehner, "Qstream: deterministic querying of data streams," in Proc. of Int. Conf. on Very Large Data Bases, pp. 1365-1368, 2004.
[11] S. Schmidt, T. Legler, and W. Lehner, "Robust real-time query processing with QStream," in Proc. of the 31st Very Large Data Bases Conf., pp. 1299-1301, Trondheim, Norway, 2005.
[12] X. Li and H. Wang, "Adaptive real-time query scheduling over data streams," in Proc. Int. Conf. on Very Large Databases, PhD Workshop, Sep. 2007.
[13] A. A. Safaei and M. S. Haghjoo, "Parallel processing of continuous queries over data streams," Distributed and Parallel Databases, vol. 28, no. 2-3, pp. 93-118, Dec. 2010.
[14] A. A. Safaei and M. S. Haghjoo, "Dispatching of stream operators in parallel execution of continuous queries," J. of Scheduling, vol. 61, no. 3, pp. 619-641, 2010
[15] م. عالمي، م. حق‌جو و ع. صفايي، "زمان‌بندي بي‌درنگ چندپردازنده‌اي در سيستمهاي مديريت جريان داده بي‌درنگ،" سومين همايش ملي مهندسي کامپيوتر و فناوري اطلاعات، همدان، 1389.