Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

18.05.2018 | Ausgabe 5-6/2019

International Journal of Parallel Programming 5-6/2019

An Analytical Evaluation of Data Dependence Analysis Techniques

Zeitschrift:
International Journal of Parallel Programming > Ausgabe 5-6/2019
Autoren:
David Niedzielski, Kleanthis Psarris, Theoharis Theoharis

Abstract

Optimizing compilers rely upon data dependence analysis to reveal the ordering constraints among statements in a program that need to be preserved in order to produce valid optimized and parallel code. Testing array references for data dependence is equivalent to determining whether a system of equalities and inequalities has an integer solution. A number of data dependence tests have been proposed in the literature. In each test there are different tradeoffs between accuracy and efficiency. In this paper we study the fundamental relationships between several data dependence tests. We consider the Banerjee Extreme Value test, Fourier Motzkin Variable Elimination (FMVE), the I-Test, and the Omega test, which are representative of the state of the art in data dependence analysis. The Banerjee Extreme Value test and FMVE can only determine the existence of real solutions to a system. Thus they can only disprove, but not prove, data dependence. The I-Test and the Omega test refine the Banerjee Extreme Value test and FMVE, respectively, to the integer domain and can prove data dependence. The Omega test is a more accurate data dependence test, but with worst case exponential time complexity. The I-Test is a polynomial time test, but it is not always conclusive. We first show that FMVE is equivalent to the Banerjee Extreme Value test. We then show that the Omega test’s technique to refine FMVE to integer solutions (dark shadow) is equivalent to the I-Test’s refinement of the Banerjee Extreme Value test to integer solutions (the accuracy condition). We prove that the I-Test returns an inconclusive (“maybe”) answer if and only if the Omega test requires an exponential time exhaustive search to produce an exact answer (the so-called “Omega Test Nightmare”).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 5-6/2019

International Journal of Parallel Programming 5-6/2019 Zur Ausgabe

Premium Partner

    Bildnachweise