Об'єднання товстих і тонких частин

Об'єднання товстої частини з тонкою частиною це сумма функцій g (A, n, k, q) і r (A, n, k, t), з важливою мірою деталізації, z. Отже, ми отримємо функцію H (A, n, k, q, t, z) = g (A, n, k, q)+ zr (A, n, k, t).

Отже, в програмі з високим z (тобто високою частотою синхронізації) тонкий шлях має більшу дію, ніж в програмі з низьким z. із попередніх результатів ми знаємо, що товста частина оптимальна, коли процеси порівну розподілені між процесорами, тоді як тонка частина оптимальна, коли усі процеси постійно виконуються на одному процесорі. На алгоритмі для виявлення мінімального розміщення А засновано

знання про оптимальне розміщення для товстої і тонкої частини відповідно.

Знахідка оптимального розміщення, що користується класами розміщення

Основна ідея - створити класи розміщення, і оцінити їх. Клас розміщення складається з розміщень і відокремлених розміщення. Відокремлені розміщення визначені, як слідує:

• Безліч процесорів із загальним розміщенням як для товщини, так і тонких частин. Це описано в зменшенні замовлення. Це означає, що число призначених процесів процесор i має бути більшим, ніж або дорівнюють до числа призначених процесів процесор i + 1.

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

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

Отже відокремлене розміщення - не розміщення, тобто це не поява в мінімізацію H (A, n, k, q, t, z). Ділиться на 2 частини: одна, для якого звичайна товста і тонка частина, і одна, де ми користуємося оптимальними розміщеннями для товстої і тонкої частини окремо. З цього слідує, що відокремлене розміщення дає краще виконання, ніж будь-яке розміщення, яке не має ніякої частини, ідентичної загальній частині відокремленого розміщення. Це спостереження фундаментальне для гілково-граничного алгоритму.

Рис.15 Класи розміщення

Клас розміщення складається з усіх розміщень, які є в спорідненості з відокремленим розміщенням та містять його загальну частину. Отже будь-яке відокремлене розміщення визначає специфіку класу розміщень. Приклад відокремленого розміщення показується в рис. 15. Тут загальна частина складається з одного процесора, ми маємо n = 9 процеси і k = 4 процесори. Розглянемо наприклад рис 15(a). Тут перша частина - загальне розміщення, у верхній частині товсте розміщення для залишившихся 3х процесорів і нижча частина є тонкою розміщення для залишку 3 процесорів. У Мал. 15(b) ми маємо повністю відокремлене розміщення, без загального розміщення взагалі. Мал. 15(c) показує усі можливі розміщення

класи, де розмір загальної частини один. Результат з відокремленими розміщеннями краще, ніж (чи дорівнюють) будь-якому розміщення в межах цього класу. Ми беремо мінімальне значення з усіх відокремлених розміщень в Мал. 15(c) для вище-оптимального розміщення, і розгортаємо дерево від цього покажчика. Ця процедура описується в наступній частині.

Гілково-граничний алгоритм

Алгоритм для виявлення оптимального розміщення - класичний Гілково-граничний

алгоритм [1]. Ми починаємо з повністю відокремленого розміщення (Мал. 15(b)). Ми переміщаємо один

процесор в загальну частину, а отже створюємо новий підклас відокремлених розміщень (Мал. 15(c))., який ми потім мінімізуємо над цими відокремленими розміщеннями. Припустимо, що в приклад Мал. 15c клас з 5 процесорами в загальному розміщенні є мінімальним. Новий підклас показується в Мал. 15(d). Усі відокремлені розміщення дають вищі (чи рівні) значення, ніж відокремлене розміщення, яке є батьківським до нового класу. Класи організовані в деревовидній структурі. Мінімум зараз обчислюється над усім листки в дереві, у тому числі листки на переходах, які заздалегідь були розгорнуті.

Якщо ми припускаємо, що класи в Мал. 15(e) і (f) дають мінімальні значення, ми досягли оптимального розміщення. Обчислюючи клас, ми користуємося загальним розміщенням, складеним з товщиною розміщення як введення для функції g (Athick) і, r (Athin, t) де - Athick загальне розміщення конкатенувало з товстим розміщенням і - загальне розміщення складено з тонким розміщенням Athin. Додаючи результати (зважено z) двох функцій, ми набуваємо значення цього листка (g (Athick)+ zr (Athin, t)). Практичне випробування показало, що багато різних видів розміщень, можливо, оптимальні залежно від цінностей n, k, q, t і z. Це знаходиться в контрасті з попередніми застосуваннями, що представляється в [9,10,11], (подивіться частину 9).

Твердження

Результати в цій статті засновані на теоретичному доказі, що веде до програми для яких коефіцієнт Ts (P, k, t)⁄ Td (P, q) максимальний. Ця частина результату не може бути перевірена на правильність

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

В любому випадку це не можливо побачити, якщо програма, виявляється, перевищенням

(погано працюючої програми) для параметрів n, q, і z дійсно призводить до значення близько до H (n, k, q, t, z) коли виконується в реальному багатопроцесорному середовищі. Ми зробили ряд перевірок на багатопроцесорних середовищах Сан/Solaris. Ми уперше перевіряли товсті програми, визначені трьома параметрами: число потоків (n), число активні потоки в кожному відрізку (q) часу і кількості роботи, що виконується в кожному відрізку часу (w); w означає число повторень над вектором довжини 1024 (кожен таке повторення іде приблизно 0.1 ms)., Користуючись Сан-ентерпрайз 4000, з 8 процесорами, ці програми виконуються, користуючись двома алгоритмами планування. Спершу ми використовували стандартний Solaris плануючи, де ніякі потоки не пов'язані до процесорів, а потім число потоків i є обмежене процесора ми (i мод k). Це означає, що, якщо число процесорів (k) – вісім і число потоків (n) складає 20, потім потоки 0, 8 і 16 пов'язане до процесорами рівне нулю. Як описано в частині 5, ми знаємо, що це оптимальний шлях зв'язати потоки. Коефіцієнт часу завершення, користуючись межею, панування на k процесорах, у порівнянні до непов’язаного пданування на q процесорах означають - h (n, k, q, w), що, для програми з n

потоками, потоки q дійсного стану в кожному слоті, і довжина слота w.

Ми розглядаємо випадки, коли q = k, 1 ≤ k ≤ 8, k ≤ n ≤ 20 і w = 100, 1000 і 10000 (рис. 16)., Ці значення h (n, q, k, w) порівнюються з теоретичними межами g (n,k,q,t= 0 ,z) в рис. 16. Таблиці показують, що, коли w = 1000, n = 18 і k = q = 8, час завершення, користуючись межею, планвання, - 1.93 разів час завершення

користування стандартним вільним плануванням Solaris. таблиці також показують, що h (n, k, k, w) ніколи

не перевищує H (n, k, k, t= 0, z). Тобто, виміри вказують, що H (n, k, k, t= 0, z) є дійсно дійсна верхня межа. Коли w зростання, h (n, k, k, w) прибуває ближче в H (n, k, k, t= 0, z), і вибираючи досить великий w, який ми можемо отримати довільно близько до H (n, k, k, t= 0, z). Тому H (n, k, k, t= 0, z) - оптимальна верхня межа, коли великий w, тобто H (n, k, k, t= 0, z) є оптимальною верхнььою межею, коли маленький z (отже, скорочуючи дію тонкої частини).

Ми також зробили виміри для тонких програм. Тобто, програми, що полягають у ланцюжку потоків, які синхронізуются. Випробування розглядало випадок, де n = 8 і довжина ланцюжка синхронізації складає 100000. Ланцюжок виконувався на двох інший середовища: Сан-Ентерпрайз 4000, з вісьмома процесорами (середня затримка синхронізації нуля в нашій моделі) і випадку, коли вісім програм виконуються на восьми ідентичних комп'ютерах з'єднаних мережею. На SMP ми здійснювали синхронізації з семафорами і в розподілених системах, які ми послали однобайтові повідомлення UDP між комп'ютерами.

Ці виміри, показують, що коефіцієнт між тривалістю виконання поширюється у середовищі і SMP тривалість виконання складає 1/200, тобто 0.5%. У нашій моделі ми припускаємо, що цей коефіцієнт нульовий (відколи ми припускаємо, що SMP тривалість виконання цієї частини нульова)., Це означає, що наша модель має помилку 0.5% для тонкої частини програми порівнюючи ці два середовища. Відколи тонка частина не бере нульовий час, щоб виконуватися на SMP, межа все ще дійсна але не зовсім оптимальна, тобто в цьому випадку там є різниця 0.5%. Якщо час синхронізації в розподіленій системі зростає (тобто, якщо t росте), різниця стає меншою. Ми можемо зробити два висновки від тверджень:

• Спершу, межа, здається, дійсна для усіх програм. Це означає, що немає такої програми P, для якої коефіцієнт Ts (P, k, t)⁄ Td (P, q) перевищує межу.

• По-друге, межа оптимальна для грубих подрібнених програм. Тому, у товстій подрібнений програми P (тобто програми з маленький z), раціон Ts (P, k, t)⁄ Td (P, q) дорівнює межі. Межа також оптимальна для систем з дуже довгим часом (тобто для великого t) очікування синхронізації.

Тому, модель правильна для товстої частини (відколи ми можемо зробити цю частину довільно

товстою), і різниця для тонкої частини невелика для реалістичних врегулювань. Наші твердження обмежені середовищем Сан/Solaris, але ми вважаємо, що ці два укладення також триматимуть за інші середовища.

Обговорення

рис. 17 показує три графи, що відповідають H (n, k, k, 0,10), H (n, k, k, 0.0025,10), і H (n, k, k, 0.005,10) для діапазону 1 n, k 50, тобто q = k у графів. Ми знаємо тільки що програми t і z впливають на g, тобто H (n, k, q, t /2, z) = H (n, k, q, t, z /2). Програмно пов'язані параметри (тобто n і z) можуть легко бути отримані від простих копіювальних інструментів. Якщо ми маємо програму з 50 процесами і, в середньому, одна синхронізація кожен 400 часових проміжків

Рис 16, Валідація «товстої» частини програми

(z = 1/400 = 0.0025) часу і хочуть порівняти оптимальним приростом продуктивності користуючись системою з 10 процесорами, перерозподіл під час виконання процесів і фактично немає комунікації з системою з 10 процесорами, немає перерозподілу і затримка комунікації 10 одиниць часу, ми можемо подивитися на середню графу в рис. 17 (tz = 0.025). значення, що відповідає n = 50 і k = q = 10, складає 2.7. Мається на увазі вигода користування системою з перерозподілом може бути у більшості чинником 2.7. Це тривіально щоб бачити, що максимальна вигода користування системою без перерозподілу нульова, тобто

мінімальний коефіцієнт один.

Можливо порівняти системи з різними номерами процесів, наприклад мультипроцесор з 10 процесорами, перерозподіл під час виконання процесів і фактично немає комунікації з системою з 20 процесорами, немає перерозподілу і затримка комунікації 5 одиниць часу. Максимальна вигода користування більш маленькою системою з перерозподілом для програми з 50 процесами і однією синхронізацією кожен 400 одиниць часу визначається g (50,20,10,5,0.0025) = 2.03. Максимальна вигода

користування системою з 20 процесорами порівняло з системою з 10 процесорами є тривіальню.

Експерименти, використовують реальнимі програмами, або наборами програм що відповідають реальним програм [20] не можуть фіксувати критичні випадки. Тому, така техніка не може відповісти

вид продуктивність порівнянь, що обговорюються вище. Параметр t, робить можливим розгляд значень продуктивності міжпроцессорної синхронізації. Проте, ми не розглядаємо значення комунікацій що відбуваються в середині процессора. Це змогло привести до недооцінки тривалості виконання для розподіленої системи, тобто система без перерозподілу під час виконання процесів. У багато застосувань, комунікація відбувається передусім в покажчиках синхронізації, і у тих випадках один може збільшити значення t, щоб включати також додаткове витрачання між комунікацією процесу. Тому, t потім включав би перевищуючу синхронізацію і (середня величина) перевищуючу комунікацію.

Висновки

Ми показали межу вигоди користування системою з q процесорами і під час виконання обробки перерозподілу, у порівняннні з користуванням системою з k процесорами. Немає затримки комунікації t, бо програма з n обробок має міру деталізації z. Ця межа - H (n, k, q, t, z) заснована на нашій мультипроцесорній моделі (визначається k, q і t), межа оптимальна в сенсі, що як мінімум одна програма з n обробками і мірою деталізації z, для якої вигода - точно H (n, k, q, t, z). Ми також перевірили правильність їх результатів, користуючись мультипроцесором і розподілом САН/Solaris системи. Заключення від тверджень є, що межа дійсна для усіх програм і архітекрур і межа стає в дійсності оптимальною коли т – більше а z – оптимальне.

Функція H (n, k, q, t, z) не тривіальна, тоді як максимальна вигода користування k процесорами та

ніякий перерозподіл і комунікація не затримують t, порівнянний з системою з q процесорами

і перерозподіл під час виконання тривіальний (k/q). Переглядаючи умову H (n, k, q, t, z) (наприклад умови подібно ті в Мал. 17), комп'ютерні системм можуть отримати відповідні передчуття щодо фундаментальних проблем розробки їх дизайну і побудови.

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

Ми показали перетворення, які допускають, що ми відділяємо виконання і синхронізацію. Аналізуючи частини окремо і порівнюючи їх, ми знайшли формулу що проводить мінімальний час завершення. Був використаний Гілково-Межовий алгоритм щоб знайти оптимальний результат.

Аргумент призводить до суми H (A, n, k, q, t, z) = g (A, n, k, q)+ zr (A, n, k, t).

Тут товста частина, представлена g (A, n, k, q), відповідає попереднім результатам.

Функція опукла в сенсі, що зменшує значення, якщо завантаження зростає для «непрацюючих програм» які розподілені між декількома компютерами. Проте тонка частина, представлена r (A, n, k, t) увігнутою. Ця кількість зростає, якщо завантаження на найгіршу програму - поширюватиметься більш рівномірно. Це робить мінімізацію суми H більш делікатно. Вид оптимального розміщення,, залежить строго від значення tz. того, Якщо tz – маленьке, то виконання очолює розділи, що представляють навіть поширення однорідних розділів.

 

 

 

Є проміжний домен цінностей того, де є різні види розділів які оптимальні.

"більш погано працюючою" - те, що те ж в усіх сценаріях було присутнім в 9. до 11. у тому числі відображає один: повні програми. Оптимальні розміщення, проте, відрізняються застосуванням У застосуваннях паралельного виконання, однорідні розміщення оптимальні. У застосуванні кеш-пам'яті, оптимальні розміщення містить одно довільну множину розмір, і інші множини поширюються як можна рівніше. Ці

властивості залежать від опуклості функції завантаження. У застосуванні кеш-пам'яті функція завантаження не опукла.

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

1. Geist, A., Beguelin, A., Dongстрa, J., Jiang, W., Manchek, R., and Sunderam, V.,

PVM: Parallel Virtual Machine, MIT press, Boston, 1994

2. MPI Forum, MPI: A message-passing interface standards, International Journal of

Supercomputer Application, 8 (3/4), 1994, pp. 164-416

3. Hagersten, E. and Koster, M., WildFire: A Scalable Path for SMPs, in Proceedings

of 5th International Symposium on High Performance Computer Architecture,

IEEE Computer Society, Los Alamitos, Orlando, FL, USA, 9-13 January, 1999, pp.

172-181

4. Laudon, J. and Lenoski, D., The SGI Origin: A ccNUMA Highly Scalable Server, in

Proceedings of 24th Annual International Symposium on Computer Architecture,

ACM, Denver, CO, USA, 2-4 June, 1997, pp. 241-251

5. Lovett, T. and Clapp, R., STiNG: A cc-NUMA Computer System for the Commercial

Marketplace, in Proceedings of 24th Annual International Symposium on Computer

Architecture, ACM, Philadelphia, PA, USA, 22-24 May, 1996, pp. 308-317

6. Garey, M.R. and Johnson, D.S., Computers and Intractability - A Guide to the Theory

of NP-Completeness, W. H. Freeman and Company, New York, 1979

7. Hou, E.S.H., Hong, R., and Ansari, N., Efficient multiprocessor scheduling based

on genetic algorithms, in Proceedings of 16th Annual Conference of the IEEE

Industrial Electronics Society - IECON'90, IEEE, Vol II, Pacific Grove, CA, USA,

27-30 November, 1990, pp. 1239-1243

8. Nanda, A.K., DeGroot, D. and Stenger, D.L., Scheduling directed task graphs on

multiprocessors using simulated annealing, in Proceedings of IEEE 12th International

Conference on Distributed Computing Systems, IEEE Computer Society,

Yokohama, Japan, 9-12 June, 1992, pp. 20-27

9. Lennerstad, H. and Lundberg, L., An Optimal Execution Time Estimate of Static versus

Dynamic Allocation in Multiprocessor Systems, SIAM Journal of Computing,

24 (4), 1995, pp. 751-764

10. Lennerstad, H. and Lundberg, L., Optimal Combinatorial Functions Comparing

Multiprocess Allocation Performance in Multiprocessor Systems, SIAM Journal of

Computing, 29 (6), 2000, pp. 1816-1838

11. Lundberg, L. and Lennerstad, H., Using Recorded Values for Bounding the Minimum

Completion Time in Multiprocessors, IEEE Transactions on Parallel and Distributed

Systems, 9 (4), 1998, pp. 346-358

12. Lennerstad, H. and Lundberg, L., Optimal worst case formulas comparing cache

memory associativity, SIAM Journal of Computing, 30 (3), 2000, pp. 872-905

13. Lundberg, L. and Lennerstad, H., Bounding the maximum gain of changing the

number of memory modules in multiprocessor computers, Nordic Journal on Computing,

4, 1997, pp. 233-258

14. Lundberg, L. and Lennerstad, H., Optimal Bound on the Gain of Permitting

Dynamical Allocation of Communication Channels in Distributed Processing,

Acta Informatica, 36 (6), 1999, pp. 425-446

15. Lennerstad, H. and Lundberg, L., Optimal Scheduling Results for Parallel Computing,

SIAM News, 27 (7), 1994

16. Lennerstad, H. and Lundberg, L., Combinatorics for Multiprocessor Scheduling

Optimization and Other Contexts in Computer Architecture, Proceedings of the

Conference of Combinatorics and Computer Science (LNCS 1120), Springer Verlag,

Brest, France, 15-18 July, 1995, pp. 341-347

17. Lennerstad, H. and Lundberg, L., Combinatorial Formulas for Optimal Cache

Memory Efficiency, SIAM News, 29 (6), 1996

18. Lundberg, L., Broberg, M. and Klonowska. K., Evaluating Heuristic Scheduling

Algorithms for High Performance Parallel Processing, in Proceedings of 5th International

Symposium on High Performance Computing (LNCS 2858), Springer-

Verlag, Tokyo-Odaiba, Japan, 20-22 October, 2003, pp. 160-173

19. Graham, R.L., Bounds on Multiprocessing Anomalies, SIAM Journal of Applied

Mathematics, 17 (2), 1969, pp. 416-429

20. Woo, S., Ohara, M., Torrie, E., Singh, J. and Gupta, A., The SPLASH-2 Programs:

Characterization and Methodological Considerations, in Proceedings of 22nd

International Symposium on Computer Architecture, ACM, Santa Margherita Ligure,

Italy, 22-24 June, 1995, pp. 24-36

 

СТАТТЯ 2

Стаття 2

«Максимальна Вигода Збільшення Числа пріоритетних Переривань у Багатопроцесорному Плануванні»

 

Kamilla Klonowska, Lars Lundberg, Hakan Lennerstad

Продовження Комп'ютерного Журналу, том. 47, Номер 5, 2004

 

Опис

Ця Статтяі узагальнює 4/3-припущення. Ми розглядаємо оптимальний робочий інтервал з довільнї множина P незалежних робіт плануючи з i пріоритетними перериваннями на мультипроцесорі з м процесорами. Ми оптимально порівнюємо робочий інтервал для i і j пріоритетних перериванняде i < j, найгіршому випадку, тобто ми обчислюємо формулу найгіршого випадку коефіцієнт G (m, i, j) визначив, як, де максимум узятий над усім множини P незалежних робіт.

Ключові слова: паралельне планування процесора, пріоритетне планування, i-перериване планування, аналіз найгіршого випадку, оптимізація, дерево Stern-Brocot

1. Введення до роботи

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

Із-за ефектів кеша і інших форм накладних витрат, є вартість для пріоритетних переривань

а потім пізніше повторно запускаючи роботу. Тому, ми захотіли б обмежити число пріоритетних переривань

для того, щоб не страждати надто багато від таких накладних витрат. мається на увазі компроміс; з одного боку нам потрібні пріоритетні переривання для того, щоб отримати балансне завантаження, однак, з іншого боку ми захотіли б обмежити число пріоритетних переривань в замовленні щоб мінімізувати накладні витрати. Оптимальне рішення до цієї проблеми – компроміс, що залежить від ряду параметрів, як наприклад вартість для вивантаження а потім пізніше повторний запуск роботи. Одним з критичних повідомленнь для ухвалення добре інформованого рішення компромісу є скільки ми придбаємо збільшуючи число пріоритетних переривань, переймаючи на себе накладні витрати. Це говоритиме нам, скільки ми можемо здійснити представляючи більш пріоритетні переривання. Тут ми зацікавлені в паралельних програмах, що складаються із числа паралельних задач. Програма завершила своє завдання, коли усі роботи закінчилися, і ми зацікавлені в зменшенні робочого інтервалу паралельної програми.

Ясно, що продуктивність та вигода, тобто зниження робочого інтервалу і збільшення числа пріоритетних переривань, залежать від ряду параметрів (навіть, ігноруючи накладні витрати). Трьома очевидними параметрами є: число процесорів в мультипроцесорі, число пріоритетних переривань перед зростанням і числом пріоритетних переривань після зростання. Також ясно, що вигода залежатиме від паралельної програми, наприклад, немає очевидно ніякої вигоди у збільшенні числа пріоритетних переривань програми, що складається з 5 незалежних робіт, користуючись мультипроцесором з 5 або більше процесорами.

У цій Статті ми обчислюємо, наскільки великим може бути коефіцієнт мінімального робочого інтервалу при використанні i і j пріоритетних переривань, якщо користуватись ідентичними м процесорами. Пріоритетне переривання контролюється, якщо обробка роботи перервана і пізніше відновлена, можливо на іншому процесорі. Цей коефіцієнт має, тривіальні нижню мнжу, це 1.

Ця проблема і її попередники має довгу історію. У 1972, Liu [13] здогадався що для будь-якої безлічі завдань і обмежень переваги серед них, працюючи на двох процесорах найменший робочий інтервал, досяжний непріоритетним графіком, - не більше ніж i < j найменший робочий інтервал, досяжний пріоритетним графіком. Здогадку було доведено в 1993 Coffman і Garey [3]. Тут автори узагальнюють результати для номерів 4/3, 3/2, 8/5,... тобто до номерів 2 k ⁄(k + 1) для чогось. номер k ≥ 2 залежить від відносного числа пріоритетних доступних переривань. Є також фундаментальний пов'язано Graham від 1969 [7], який відповідає довільній кількості незалежних робіт. Це заявляє, що оптимальний графік без пріоритетних переривань має у більшості подвійний робочий інтервал у порівнянні з робочим інтервалом з безмежним числом пріоритетних переривань, користуючись оптимальними графіками. Факт що, 2 k ⁄(k + 1)→ 2 від нижче за те, як k → ∞.

Braun і Schmidt довели в 2003 формулу, яка прирівнює пріоритетний графік з i пріоритетними перериваннями до графіку з безмежним числом пріоритетних переривань в найгіршому випадку, користуючись мультипроцесором з м процесорами [2]. За встановленими правилами McNaughton, не більше ніж пріоритетні переривання потрібні у безмежному випадку. Вони узагальнили межу 4/3 до формули 2–2⁄(m ⁄(i + 1)+ 1), яка, також можливо, записана, як 2 m ⁄(m + i +1)

У цій статті ми узагальнюємо результати Braun і Schmidt. Ми порівнюємо i пріоритетні переривання з j пріоритетними перериваннями найгіршого випадку, припускаючи. i < j, що Ми дозволяємо j від, i + 1 m – 1 поки проблема вирішила в [2] відповідає j = m – 1. В випадку m ≥ i + j +1, який не співпадає за винятком j = m – 1, ми отримуємо оптимальну межу 2(j ⁄(i + 1) + 1)⁄(j ⁄(i + 1) + 2). Наприклад, виключаючи одне пріоритетне переривання не ніколи може зменшимо робочий інтервал більш ніж чинник 4/3 але, можливо, робить так. Цей аргумент не може бути ітерований, відколи різна кількість найгіршої роботи залежно від параметрів i і j. В цьому випадку m < i + j +1 ми подарували формулу і алгоритм що базується на дереві Stern-Brocot.

Ця стаття організовна як зазначено нижче. У Секції 2 ми представили формулювання завдання

зображення знаками, і основні результати. Результати доводяться в частині 3. Укладення є подано в в частині 4.