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...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2007 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101825 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Extracting Synchronization-free Slices in Perfectly Nested Loops / W. Bielecki, K. Siedlecki // Электронное моделирование. — 2007. — Т. 29, № 6. — С. 61-76. — Бібліогр.: 28 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862631570643353600 |
|---|---|
| author | Bielecki, W. Siedlecki, K. |
| author_facet | Bielecki, W. Siedlecki, K. |
| citation_txt | Extracting Synchronization-free Slices in Perfectly Nested Loops / W. Bielecki, K. Siedlecki // Электронное моделирование. — 2007. — Т. 29, № 6. — С. 61-76. — Бібліогр.: 28 назв. — англ. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| 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м, і генерувати програму, яка перелічує джерела таких фрагментів та ітерацій у кожному фрагменті в лексикографічному порядку. Несинхронізовані фрагменти можуть виконуватися незалежно, зберігаючи лексикографічний порядок ітерацій у кожному фрагменті. Даний підхід потребує точного аналізу залежності і базується на операціях з відношенням та множинами. Для описування та реалізації алгоритмів обрано аналіз залежності за Пуго та Воннакотом, у якому знайдено залежності у формі відношень кортежа. Запропоновані алгоритми реалізовано і верифіковано за допомогою програмного пакета Омега. Наведено результати експериментів.
|
| first_indexed | 2025-11-30T11:31:29Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-101825 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | English |
| last_indexed | 2025-11-30T11:31:29Z |
| publishDate | 2007 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| 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 |
| spellingShingle | Extracting Synchronization-free Slices in Perfectly Nested Loops Bielecki, W. Siedlecki, K. Вычислительные процессы и системы |
| title | 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_short | Extracting Synchronization-free Slices in Perfectly Nested Loops |
| title_sort | extracting synchronization-free slices in perfectly nested loops |
| topic | Вычислительные процессы и системы |
| topic_facet | Вычислительные процессы и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101825 |
| work_keys_str_mv | AT bieleckiw extractingsynchronizationfreeslicesinperfectlynestedloops AT siedleckik extractingsynchronizationfreeslicesinperfectlynestedloops |