It is a well known fact that scientific programs spend most of their running time in executing loops operating on arrays. The polyhedral model is a mathematical framework which was designed to optimize this process. Its use in automatic paralyzation of nested loops goes back to the work of Kuck (1978), who showed that the domain of nested loop with affine lower and upper bounds can be described in terms of a polyhedron, and the seminal work of Karp, Miller and Winograd (1967) on scheduling systems of uniform recurrence equations. For a long period of time Graphite (it is part of the GNU Compiler Collection) was relying on CLooG library to produce SSA intermediate representation from the polyhedral model. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. That is why the following goal was chosen: Creation of SSA generator based on Integer Set Library. Master's thesis

Research output: ThesisMaster's ThesisResearch

Abstract

It is a well known fact that scientific programs spend most of their running time in executing loops operating on arrays. The polyhedral model is a mathematical framework which was designed to optimize this process. Its use in automatic paralyzation of nested loops goes back to the work of Kuck (1978), who showed that the domain of nested loop with affine lower and upper bounds can be described in terms of a polyhedron, and the seminal work of Karp, Miller and Winograd (1967) on scheduling systems of uniform recurrence equations. For a long period of time Graphite (it is part of the GNU Compiler Collection) was relying on CLooG library to produce SSA intermediate representation from the polyhedral model. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. That is why the following goal was chosen: Creation of SSA generator based on Integer Set Library.
Translated title of the contributionIt is a well known fact that scientific programs spend most of their running time in executing loops operating on arrays. The polyhedral model is a mathematical framework which was designed to optimize this process. Its use in automatic paralyzation of nested loops goes back to the work of Kuck (1978), who showed that the domain of nested loop with affine lower and upper bounds can be described in terms of a polyhedron, and the seminal work of Karp, Miller and Winograd (1967) on scheduling systems of uniform recurrence equations. For a long period of time Graphite (it is part of the GNU Compiler Collection) was relying on CLooG library to produce SSA intermediate representation from the polyhedral model. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. That is why the following goal was chosen: Creation of SSA generator based on Integer Set Library.: Master's thesis
Original languageRussian
Supervisors/Advisors
  • Корнев, Дмитрий Васильевич, Supervisor
Publication statusPublished - 2015

Fingerprint

Graphite
Scheduling
Code generation

Keywords

    Cite this

    @phdthesis{2533c181a8cd4aee804c228e5d5c7516,
    title = "Реализация генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU: магистерская диссертация",
    abstract = "Как известно, большая часть времени исполнения программ, связанных с научными расчетами, тратится на выполнение циклов и взаимодействие с массивами. С целью оптимизации этого процесса был разработан математический фреймворк — полиэдральная модель. Первые её применения можно встретить в работах Дэвида Кука и Ричарда Карпа от 1978 и 1967 соответственно. С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Такими примерами служат библиотеки CLooG и ISL. В отличие от библиотеки CLooG, специализированной для генерации кода из поэлидарльной модели, библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева. В рамках магистерской работы была поставлена следующая цель: Cоздание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.",
    keywords = "Математика и компьютерные науки",
    author = "Гареев, {Р. А.}",
    note = "Гареев Р. А. Реализация генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU : магистерская диссертация / Р. А. Гареев ; Уральский федеральный университет имени первого Президента России Б. Н. Ельцина, Институт математики и компьютерных наук, Департамент математики, механики и компьютерных наук, Кафедра вычислительной математики. — Екатеринбург, 2015. — 78 с. — Библиогр.: с. 76-78 (29 назв.).",
    year = "2015",
    language = "Русский",

    }

    TY - THES

    T1 - Реализация генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU

    T2 - магистерская диссертация

    AU - Гареев, Р. А.

    N1 - Гареев Р. А. Реализация генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU : магистерская диссертация / Р. А. Гареев ; Уральский федеральный университет имени первого Президента России Б. Н. Ельцина, Институт математики и компьютерных наук, Департамент математики, механики и компьютерных наук, Кафедра вычислительной математики. — Екатеринбург, 2015. — 78 с. — Библиогр.: с. 76-78 (29 назв.).

    PY - 2015

    Y1 - 2015

    N2 - Как известно, большая часть времени исполнения программ, связанных с научными расчетами, тратится на выполнение циклов и взаимодействие с массивами. С целью оптимизации этого процесса был разработан математический фреймворк — полиэдральная модель. Первые её применения можно встретить в работах Дэвида Кука и Ричарда Карпа от 1978 и 1967 соответственно. С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Такими примерами служат библиотеки CLooG и ISL. В отличие от библиотеки CLooG, специализированной для генерации кода из поэлидарльной модели, библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева. В рамках магистерской работы была поставлена следующая цель: Cоздание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.

    AB - Как известно, большая часть времени исполнения программ, связанных с научными расчетами, тратится на выполнение циклов и взаимодействие с массивами. С целью оптимизации этого процесса был разработан математический фреймворк — полиэдральная модель. Первые её применения можно встретить в работах Дэвида Кука и Ричарда Карпа от 1978 и 1967 соответственно. С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Такими примерами служат библиотеки CLooG и ISL. В отличие от библиотеки CLooG, специализированной для генерации кода из поэлидарльной модели, библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева. В рамках магистерской работы была поставлена следующая цель: Cоздание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.

    KW - Математика и компьютерные науки

    M3 - Магистерская диссертация

    ER -