کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875717 | 1441982 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Scheduling series-parallel task graphs to minimize peak memory
ترجمه فارسی عنوان
برنامه ریزی نمودار نمودارهای موازی سریال برای به حداقل رساندن حافظه پیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای سریال موازی، برنامه ریزی، کاهش حداکثر حافظه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and we are asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum. In our variant, the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut. There is a known, polynomial time algorithm (Liu, 1987 [17]) for the cases where the input graph is a rooted tree. We focus on the instances where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm, thus expanding the class of graphs for which a polynomial time algorithm is known. Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application. Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 707, 10 January 2018, Pages 1-23
Journal: Theoretical Computer Science - Volume 707, 10 January 2018, Pages 1-23
نویسندگان
Enver Kayaaslan, Thomas Lambert, Loris Marchal, Bora Uçar,