Границі Продуктивності і Толерантність Дефекту в

Паралельних обчисленнях.

Kamilla Klonowska

Блекінжський технологічний інститут

Серія Докторських дисертацій

№ 2007:18

ISSN 1653-2090

ISBN 978-91-7295-126-6

Департамент по системам та прикладному програмному забезпеченню.

Школа розробки

Блекінжський технологічний інститут

ШВЕЦІЯ

 

 

© 2007 Камілла Клоновська

Департамент по системам та прикладному програмному забезпеченню

Школа розробки

Видавець: Блекінжський технологічний інститут

Надруковано: Друкарня Карлскрона, Швеція 2007

ISBN 978-91-7295-126-6

 

На згадку про мого Батька

Тадеуша Клоновскього

Дисертація представляється в Блекінжському Технологічному інституті на Технологічному факультеті для часткового задоволення вимог для отримання ступеня Доктора Філософії в Розробці Обчислювальних Систем.

 

Контактна інформація:

Камілла Клоновська

Департамент по системам та прикладному програмному забезпеченню

Школа Розробки, Блекінжський технологічний інститут

А/я 520

SE-372 25 Роннебі

Швеція

Електронна пошта: [e-mail]

Анотація

Ця дисертація складається з двох частин: Границі продуктивності для алгоритмів планування для паралельних програм в мультипроцессорних системах, і «Толерантність похибок» при схемах відновлення розподілених систем, коли один або більше комп'ютерів виходять з ладу (збоять).

 

У першій частині ми покажемо щільні межі в діапазоні для мінімального часу паралельного виконання программ на прикладі двох сценаріїв.

Сценарій №1 Діапазон мінімального часу завершення обчислення, коли процеси можуть бути перерозподілені у порівнянні із тим, коли вони не можуть бути перерозподілені до інших процесорів впродовж їх тривалості виконання.

Сценарій №2 Коли графік випереджуючий, а діапазон для мінімального часу завершення операції стоїть в межах, коли використовуються два різних типи переривань

 

Друга частина обговорює задачу перерозподілу навантаження серед запущених комп'ютерів в паралельній системі.

Мета - знайти схему перерозподілу, яка підтримує високу продуктивність навіть, коли один або більше комп'ютери йдуть з ладу. Тут ми показуємо чотири різні алгоритми перерозподілу навантаження.

У обох частинах ми використовуємо теоретичні техніки, що призводять до явно найгірше працюючих програм і сценаріїв. Коректність заснована на математичних доказах.

Підтвердження

 

Ця дисертація доктора філософії, можливо, ніколи б не зявилась без моїх наглядачів, колег, друзів і членів родини.

Спасибі. Я особливо дякую своїм наглядачам Професорові Ларсу Ландбергу і Доц. Хакану Лендерстаду за їх вклад в розділи, коментарі, ідеї, і заохочення впродовж цієї роботи;

Ларсу за його терпіння і Хакану за численні діалоги і обговорення проблем життя і математики.

Я також дякую членам моєї дослідницької групи: Чарлі Сванбергу за відповіді на усі мої питання і його вклад в Голомбо-series частинах, Девіту Менгісту за численні обговорення складності життя і планування, Саймону Канґстрону за допомогу мені у усвідомленні побудови/збірки, а також інших незрозумілих моментах, Пітер Троґеру за поглиблені обговорення про дефекти, помилки і збої, а такожі за підтримку моєї сім'ї впродовж останнього, найбільше напруженого вихідного, Мії Перссон за обговорення НП-складності, Ґорану Фріізу за те, що був моїм сусідом впродовж моїх звершень для досягнення ступеня Доктора філософії, Бенту Абсфаллу, Хакану Грану і Магнусу Бробергу, екс-члену цього докладу у першій частині.

Я також захотів би дякувати моїм колегам у департаменті, особливо Лінді Рамстерд

Джоанні Торнквіст, Лоренсу Геннесі, Дженні Люндберг, Ніні Дзамашвіллі - Фогельшторм, Гоха Баі, Маделіні Петерссон, Моніці Нільссон, Мей-Луїзі Андерссон, Петеру Нільссену.

Нарешті, я хочу принести мою вдячність до моєї сім'ї за їх підтримку і заохочення впродовж важких часів. Особливе спасибі до Яцеку і Віктору, моїй Мамі, тітці Вірі, Басі і тітці Льодзі, Івонці і Кжиштофу за те що вони були зі мною впродовж цього часу.

І моїм друзям: Радеку і Госі Шиманеку, Єві і Жонті Андерссон, Магдалені Урбанській, Віолі і

Томеку Маравчи, Каріні Стаховяк і Рафалу Ленці.

Список Літератури

Література що вклчена в цей доклад.

I “Comparing the Optimal Продуктивність of Parallel Architectures”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad, Magnus Broberg

The Computer Journal, Vol. 47, No. 5, 2004

II “The Maximum Gain of Increasing the Number of Preemptions in

Multiprocessor Scheduling”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad

submitted for publication

III “Using Голомбо Rulers for Optimal Recovery Schemes in Fault Tolerant

Distributed Computing”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad

Proceedings of the 17th International Parallel & Distributed Processing Symposium

IPDPS 2003, Nice, France, April 2003

IV “Using Modulo Rulers for Optimal Recovery Schemes in Distributed

Computing”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad, Charlie Svahnberg

Proceedings of the 10th International Symposium PRDC 2004, Papeete, Tahiti,

French Polynesia, March 2004

V “Extended Голомбо Rulers as the New Recovery Schemes in Distributed

Dependable Computing”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad, Charlie Svahnberg

Proceedings of the 19th IEEE International Parallel and Distributed Processing

Symposium (IPDPS'05), Denver, Colorado, April 2005

VI “Optimal Recovery Schemes in Fault Tolerant Distributed Computing”

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad, Charlie Svahnberg

Acta Informatica, 41(6), 2005

Publications that are related but not included in this thesis:

VII “Using Optimal Голомбо Rulers for Minimizing Collisions in Closed Hashing”

Lars Lundberg, Hakan Lennerstad, Kamilla Klonowska, Goran Gustafsson

Proceedings of Advances in Computer Science - ASIAN 2004, Higher-Level

Decision Making, 9th Asian Computing Science Conference, Thailand, December

2004; Lecture Notes in Computer Science, 3321 Springer 2004, ISBN 3-

540-24087-X

VIII “Bounding the Minimal Completion Time in High Продуктивність Parallel

Processing”

Lars Lundberg, Magnus Broberg, Kamilla Klonowska

International Journal of High Продуктивність Computing and Networking, Vol. 2,

No. 1, 2004

IX “Comparing the Optimal Продуктивність of Multiprocessor Architectures”

Lars Lundberg, Kamilla Klonowska, Magnus Broberg, Hakan Lennerstad

Proceedings of the twenty-first IASTED International Multi-Conference Applied

Informatics AI 2003, Innsbruck, Austria, February 2003

X “Recovery Schemes for High Availability and High Продуктивність Distributed

Real-Time Computing”

Lars Lundberg, Daniel Haggander, Kamilla Klonowska, Charlie Svahnberg

Proceedings of the 17th International Parallel & Distributed Processing Symposium

IPDPS 2003, Nice, France, April 2003

XI “Evaluating Heuristic Scheduling Algorithms for High Продуктивність Parallel

Processing”

Lars Lundberg, Magnus Broberg, Kamilla Klonowska

Proceedings of the fifth International Symposium on High Продуктивність Computing

ISHPC-V 2003, Tokyo, Japan, October 2003

XII “A Method for Bounding the Minimal Completion Time in Multiprocessors”

Magnus Broberg, Lars Lundberg, Kamilla Klonowska

Technical Report, Blekinge Institute of Technology, 2002

XIII “Optimal Продуктивність Comparisons of Massively Parallel Multiprocessors”

Hakan Lennerstad, Lars Lundberg, Kamilla Klonowska

 

Підписано для публікації.

Зміст