Complexity Analysis of New Task Allocation Problem Using Network Flow Method on Multicore Clusters
المؤلف
المصدر
Mathematical Problems in Engineering
العدد
المجلد 2014، العدد 2014 (31 ديسمبر/كانون الأول 2014)، ص ص. 1-7، 7ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2014-01-02
دولة النشر
مصر
عدد الصفحات
7
التخصصات الرئيسية
الملخص EN
The task allocation problem (TAP) generally aims to minimize total execution cost and internode communication cost in traditional parallel computing systems.
New TAP (NTAP) considering additive intranode communication cost in emerging multicore cluster systems is investigated in this paper.
We analyze the complexity of NTAP with network flow method and conclude that the intranode communication cost is a key to the complexity of NTAP, and prove that (1) the NTAP can be cast as a generalized linear network minimum cost flow problem and can be solved in O(m2n4) time if the intranode communication cost equals the internode communication cost, and (2) the NTAP can be cast as a generalized convex cost network minimum cost flow problem and can be solved in polynomial time if the intranode communication cost is more than the internode communication cost.
More in particular, the uniform cost NTAP can be cast as a convex cost flow problem and can be solved in O(m2n2log(m+n)) time.
Furthermore, solutions to the NTAP are also discussed.
Our work extends currently known theoretical results and the theorems and conclusions presented in this paper can provide theoretical basis for task allocating strategies on multicore clusters.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Yang, Jixiang. 2014. Complexity Analysis of New Task Allocation Problem Using Network Flow Method on Multicore Clusters. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-493441
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Yang, Jixiang. Complexity Analysis of New Task Allocation Problem Using Network Flow Method on Multicore Clusters. Mathematical Problems in Engineering No. 2014 (2014), pp.1-7.
https://search.emarefa.net/detail/BIM-493441
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Yang, Jixiang. Complexity Analysis of New Task Allocation Problem Using Network Flow Method on Multicore Clusters. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-493441
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-493441
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر