Extracting Synchronization-free Slices in Perfectly Nested Loops

Extracting Synchronization-free Slices in Perfectly Nested Loops

An algorithm, permitting us to extract iterations belonging to synchronization-free slices and to generate code enumerating sources of such slices and iterations of each slice in lexicographical order is presented. Synchronization-free slices can be executed independently preserving the lexicographi...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Электронное моделирование
Datum:2007
Hauptverfasser: Bielecki, W., Siedlecki, K.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2007
Schlagworte:
Вычислительные процессы и системы
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/101825
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Extracting Synchronization-free Slices in Perfectly Nested Loops / W. Bielecki, K. Siedlecki // Электронное моделирование. — 2007. — Т. 29, № 6. — С. 61-76. — Бібліогр.: 28 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-101825
record_format dspace
spelling Bielecki, W.
Siedlecki, K.
2016-06-07T16:35:04Z
2016-06-07T16:35:04Z
2007
Extracting Synchronization-free Slices in Perfectly Nested Loops / W. Bielecki, K. Siedlecki // Электронное моделирование. — 2007. — Т. 29, № 6. — С. 61-76. — Бібліогр.: 28 назв. — англ.
0204-3572
https://nasplib.isofts.kiev.ua/handle/123456789/101825
519.872
An algorithm, permitting us to extract iterations belonging to synchronization-free slices and to generate code enumerating sources of such slices and iterations of each slice in lexicographical order is presented. Synchronization-free slices can be executed independently preserving the lexicographic order of iterations in each slice. Our approach requires exact dependence analysis and based on operations on relations and sets. To describe and implement the algorithms, the dependence analysis by Pugh and Wonnacott was chosen where dependences are found in the form of tuple relations. The proposed algorithms have been implemented and verified by means of the Omega project software. Presburger arithmetic limitations are discussed. Results of experiments are presented. Tasks for future research are outlined.
Представлен алгоритм, позволяющий выделить итерации, принадлежащие несинхронизированным фрагментам, и генерировать программу, перечисляющую источники таких фрагментов и итераций в каждом фрагменте в лексикографическом порядке. Несинхронизированные фрагменты могут выполняться независимо, сохраняя лексикографический порядок итераций в каждом фрагменте. Данный подход требует точного анализа зависимости и основан на операциях с отношениями и множествами. Для описания и реализации алгоритмов, выбран анализ зависимости по Пугу и Воннакоту, в котором найдены зависимости в форме отношений кортежа. Предложенные алгоритмы реализованы и верифицированы посредством программного пакета Омега. Представлены результаты экспериментов.
Наведено алгоритм, що дозволяє виділити ітерації, які належать несинхронізованим фрагментaм, і генерувати програму, яка перелічує джерела таких фрагментів та ітерацій у кожному фрагменті в лексикографічному порядку. Несинхронізовані фрагменти можуть виконуватися незалежно, зберігаючи лексикографічний порядок ітерацій у кожному фрагменті. Даний підхід потребує точного аналізу залежності і базується на операціях з відношенням та множинами. Для описування та реалізації алгоритмів обрано аналіз залежності за Пуго та Воннакотом, у якому знайдено залежності у формі відношень кортежа. Запропоновані алгоритми реалізовано і верифіковано за допомогою програмного пакета Омега. Наведено результати експериментів.
en
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Электронное моделирование
Вычислительные процессы и системы
Extracting Synchronization-free Slices in Perfectly Nested Loops
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Extracting Synchronization-free Slices in Perfectly Nested Loops
spellingShingle Extracting Synchronization-free Slices in Perfectly Nested Loops
Bielecki, W.
Siedlecki, K.
Вычислительные процессы и системы
title_short Extracting Synchronization-free Slices in Perfectly Nested Loops
title_full Extracting Synchronization-free Slices in Perfectly Nested Loops
title_fullStr Extracting Synchronization-free Slices in Perfectly Nested Loops
title_full_unstemmed Extracting Synchronization-free Slices in Perfectly Nested Loops
title_sort extracting synchronization-free slices in perfectly nested loops
author Bielecki, W.
Siedlecki, K.
author_facet Bielecki, W.
Siedlecki, K.
topic Вычислительные процессы и системы
topic_facet Вычислительные процессы и системы
publishDate 2007
language English
container_title Электронное моделирование
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
format Article
description An algorithm, permitting us to extract iterations belonging to synchronization-free slices and to generate code enumerating sources of such slices and iterations of each slice in lexicographical order is presented. Synchronization-free slices can be executed independently preserving the lexicographic order of iterations in each slice. Our approach requires exact dependence analysis and based on operations on relations and sets. To describe and implement the algorithms, the dependence analysis by Pugh and Wonnacott was chosen where dependences are found in the form of tuple relations. The proposed algorithms have been implemented and verified by means of the Omega project software. Presburger arithmetic limitations are discussed. Results of experiments are presented. Tasks for future research are outlined. Представлен алгоритм, позволяющий выделить итерации, принадлежащие несинхронизированным фрагментам, и генерировать программу, перечисляющую источники таких фрагментов и итераций в каждом фрагменте в лексикографическом порядке. Несинхронизированные фрагменты могут выполняться независимо, сохраняя лексикографический порядок итераций в каждом фрагменте. Данный подход требует точного анализа зависимости и основан на операциях с отношениями и множествами. Для описания и реализации алгоритмов, выбран анализ зависимости по Пугу и Воннакоту, в котором найдены зависимости в форме отношений кортежа. Предложенные алгоритмы реализованы и верифицированы посредством программного пакета Омега. Представлены результаты экспериментов. Наведено алгоритм, що дозволяє виділити ітерації, які належать несинхронізованим фрагментaм, і генерувати програму, яка перелічує джерела таких фрагментів та ітерацій у кожному фрагменті в лексикографічному порядку. Несинхронізовані фрагменти можуть виконуватися незалежно, зберігаючи лексикографічний порядок ітерацій у кожному фрагменті. Даний підхід потребує точного аналізу залежності і базується на операціях з відношенням та множинами. Для описування та реалізації алгоритмів обрано аналіз залежності за Пуго та Воннакотом, у якому знайдено залежності у формі відношень кортежа. Запропоновані алгоритми реалізовано і верифіковано за допомогою програмного пакета Омега. Наведено результати експериментів.
issn 0204-3572
url https://nasplib.isofts.kiev.ua/handle/123456789/101825
citation_txt Extracting Synchronization-free Slices in Perfectly Nested Loops / W. Bielecki, K. Siedlecki // Электронное моделирование. — 2007. — Т. 29, № 6. — С. 61-76. — Бібліогр.: 28 назв. — англ.
work_keys_str_mv AT bieleckiw extractingsynchronizationfreeslicesinperfectlynestedloops
AT siedleckik extractingsynchronizationfreeslicesinperfectlynestedloops
first_indexed 2025-11-30T11:31:29Z
last_indexed 2025-11-30T11:31:29Z
_version_ 1850857575529054208

Ähnliche Einträge