Code scheduling for optimizing parallelism and data locality

Taylan Yemliha, Mahmut Kandemir, Ozcan Ozturk, Emre Kultursay, Sai Prashanth Muralidhara

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


As chip multiprocessors proliferate, programming support for these devices is likely to receive a lot of attention in the near future. Parallelism and data locality are two critical issues in a chip multiprocessor environment. Unfortunately, most of the published work in the literature focuses only on one of these problems, and this can prevent one from achieving the best possible performance. The main goal of this paper is to propose and evaluate a compiler-directed code parallelization scheme, which considers both parallelism and data locality at the same time. Our compiler captures the inherent parallelism and data reuse in the application code being analyzed using a novel representation called the locality-parallelism graph (LPG). Our partitioning/scheduling algorithm assigns the nodes of this graph to the processors in the architecture and schedules them for execution. We implemented this algorithm and evaluated its effectiveness using a set of benchmark codes. The results collected so far indicate that our approach improves overall execution latency significantly. In this paper, we also introduce an ILP (Integer Linear Programming) based formulation of the problem, and implement the schedule obtained by the ILP solver. The results indicate that our approach gets within 4% of the ILP solution.

Original languageEnglish (US)
Title of host publicationEuro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings
Number of pages13
EditionPART 1
StatePublished - 2010
Event16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010 - Ischia, Italy
Duration: Aug 31 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6271 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Code scheduling for optimizing parallelism and data locality'. Together they form a unique fingerprint.

Cite this