Communication contention in APN list scheduling algorithm

Xiaoyong Tang, Kenli Li, Divid Padua

Research output: Contribution to journalArticlepeer-review


Task scheduling is an essential aspect of parallel process system. This NP-hard problem assumes fully connected homogeneous processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. This paper investigates the incorporation of contention awareness into task scheduling. The innovation is the idea of dynamically scheduling edges to links, for which we use the earliest finish communication time search algorithm based on shortest-path search method. The other novel idea proposed in this paper is scheduling priority based on recursive rank computation on heterogeneous arbitrary processor network. In the end, to reduce time complexity of algorithm, a parallel algorithm is proposed and speedup O(PPE) is achieved. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm significantly surpasses classic and static communication contention awareness algorithm, especially for high data transmission rate parallel application.

Original languageEnglish (US)
Pages (from-to)59-69
Number of pages11
JournalScience in China, Series F: Information Sciences
Issue number1
StatePublished - Jan 2009


  • Arbitrary processor network
  • Communication contention
  • DAG
  • List scheduling
  • Parallel algorithm

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Communication contention in APN list scheduling algorithm'. Together they form a unique fingerprint.

Cite this