Heurystyczna strukturalizacja programów metodą punktów krytycznych rekonfiguracji dla systemów z redundancją zasobów komunikacyjnych

• Autorzy: Laskowski, E.

Warianty tytułu

EN

Critical reconfiguration points heuristic in system with redundant communication resources

• Języki publikacji: PL

Abstrakty

PL

Dynamicznie rekonfigurowalne systemy wieloprocesorowe, działajace w oparciu o łącza komutowane i przesyłanie komunikatów, stanowią interesującą alternatywę dla powszechnie obecnie stosowanych systemó ze statyczną topologią połączeń. Z uwagi na fakt, że rekonfiguracja połączeń w takich systemach pociąga za sobą narzuty czasowe, zaproponowano nowy paradygmat wykonywania programó: rekonfigurację z wyprzedzeniem. Ogólna zasada działania systemu wykorzystującego ten paradygmat sprowadza się do tworzenia połączeń dla przyszłych komunikacji równolegle do bieżącego wykonywania programu, z wykorzystaniem istniejących w systemie redundancyjnych zasobów komunikacyjnych. W pracy opisano algorytmy strukturalizacji grafu programu w systemie rekonfigurowalnym z wyprzedzeniem z redundancją zasobó komunikacyjnych. Strukturalizacja programu w takim systemie obejmuje dwa procesy: szeregowanie zadań oraz podział grafu programu na sekcje. Zaprezentowany algorytm podziału grafu jest wspomagany metodą punktów krytycznych rekonfiguracji.

EN

Look-ahead dynamic inter-processor connection reconfiguration is a multi-processor architectural model, which has been proposed to eliminate connection reconfiguration time overheads. It consists in preparing link connections in advance in parallel with program execution in some redundant communication resources. An application program is partitioned into sections and link connections are prepared for the next program sections while previous sections are executed. Parallel program structuring in such a kind of environment incorporates task scheduling and graph partitioning problem. This paper presents scheduling algorithm in look-ahead dynamically reconfigurable multi-processor systems and the new fast heuristics of program graph partitioning into sections. The presented graph partitioning algorithm is supported by critical reconfiguration point heuristic, which is based on the links reconfiguration precedence analysis.

Słowa kluczowe

PL

szeregowanie zadań; rekonfiguracja połączeń; podział grafu

EN

task scheduling; links reconfiguration; graph partitioning

• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2001
• Tom: Nr 939
• Strony: 1-22

Twórcy

autor

Laskowski, E.

• Instytut Podstaw Informatyki PAN ul. Ordona 21 01-237 Warszawa