FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors
FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors
复制标题
FAST：一种低复杂度算法，用于在并行处理器上高效调度 DAG
DOI：
10.1109/icpp.1996.537394
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Gu
中科院分区：
文献类型：
--
作者：
Yu;I. Ahmad;J. Gu
DAG调度问题是一个丰富的研究领域，文献中已经报道了大量的算法来解决这个问题。然而，设计一个低复杂度的调度算法，而不牺牲性能仍然是一个具有挑战性的障碍，从实用的角度来看。在本文中，我们提出了一个本地搜索为基础的调度算法，试图满足这一挑战。该算法被称为快速分配使用搜索技术（FAST）。它的总时间复杂度仅为O（e），其中e是DAG中的边数。该算法首先生成初始解，然后使用局部邻域搜索对其进行细化。该算法优于许多以前的算法，同时采取显着更少的执行时间。我们的研究的显着特点是，性能评估是不使用模拟进行，而是我们已经测试了我们提出的算法，并将其与其他算法使用并行编译器与英特尔Paragon上的真实的应用程序进行比较。
The DAG scheduling problem is a rich land of research and a plethora of algorithms for solving this problem have been reported in the literature. However, designing a scheduling algorithm of low complexity without sacrificing performance remains a challenging obstacle from a practical perspective. In this paper, we present a local search-based scheduling algorithm that attempts to meet this challenge. The proposed algorithm is called Fast Assignment using Search Technique (FAST). Its overall time complexity is only O(e) where e is the number of edges in the DAG. The algorithm works by first generating an initial solution and then refining it using local neighborhood search. The algorithm outperforms numerous previous algorithms while taking dramatically smaller execution times. The distinctive feature of our research is that the performance evaluation is not carried out using simulation, rather we have tested our proposed algorithm and compared it with other algorithms using a parallel compiler with real applications on the Intel Paragon.