ЗНАЕТЕ ЛИ ВЫ?

Ощадливі Схеми Відновлення і Схеми Відновлення Голомбо



Зараз ми опишемо ощадливі схеми відновлення і схеми відновлення Голомбо. Ці схеми відновлення оптимальні для більшого ряду важливих випадків, але результати не роблять навантаження балансуючим, коли відбувається “обгорта по колу”.

Ми починаємо з визначення R0, тобто списку відновлень для процесу нуль : r(x) = min{j є N+}таке, що для усіх a1, a2, b1, b2, які виконують умови (1 ≤ a1b1x) і (1 ≤ a2b2x) і ((a1 ≠ a2) чи (b1 ≠ b2)) ми маємо .

Якщо , потім , інші R0(x) = min{j є N+ –{R0(1),…,R0(x− 1)}}. (n − ряд ідентичних комп'ютерів в кластері)

Усі інші списки відновлень виходять з R0, користуючись Ri(R0(x) + i) mod n.

У визначенні R0 ми користуємося вектор довжини кроку r. важлива властивість в ощадливsq схемs відновлення є, що усі суми послідовностей, є унікальний, тобто , коли (1 ≤ a1b1x) і (1 ≤ a2b2x) і ((a1a2) або (b1 ≠ b2)).

Від визначення вище ми бачимо, що для великих значень n (тобто n > 289), перші 16 елементів в R0 для ощадливої схеми відновлення є: 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147, 181, 203, 251, 289. Для n = 16, R0= {1, 3, 7, 12, 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15}.

У [6] ми довели, що ощадлива схема відновлення оптимальна, поки x комп'ютери чи менше вимкнулися, де x = max(i), таке, що R0(i)< m.

Окремий випадок ощадливої схеми відновлення − послідовність названа лінійкою Галом ба з n позначками, якиа визначається як послідовність додатніх цілих чисел 0 = d1< d2 <… <dn таких, що усі різниці dj di, з i < j чіткі. Найкоротша лінійка Голомбо для цього ряду позначок є під назвою Оптимальна Лінійка Голомбо (OGRs). Від схеми відновлення Голомбо для кластера з j комп'ютерами виходить список відновлень Голомбо, який містить дві частини. Перша частина складається з оптимальної Лінійки Голомбо з сумою менше або дорівнює j і з другої частини заповненлї номерами, що залишилися, аж до j−1.

Нехай GR0j є списком відновлень Голомбо для процесу нуль в кластері з j комп'ютерами. Це містить оптимальну лінійку Голомбо з сумою меншою ніж або рівною j і залишок − номери аж до j−1. Наприклад для процеса нуль в кластері з 12 комп'ютерів, які ми маємо: GR0, 12={1,4,9,11,2,3,5,6,7,8,10}. Усі інші списки відновлень виходять з GR0 j,використовуючи GRi, j(x) = (GR0, j(x) + i)mod(j + 1) для усіх i j.

Окремий випадок OGR − досконала лінійка Голомбо, яка існує, де там є точні відмінності (послідовні цілі числа від 1 до , з'являючись у будь−якому порядку).

Це означає, що немає ніякої "прогалини " в представленні трикутника. Галом ба взагалі. [1] доводять, що немає ніяких досконалих лінійок Голомбо, коли n > 4.

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

Модульна Схема Відновлення

Модульна−n послідовність − послідовність додатніх цілих чисел {аn}, де жодні дві чіткі пари {ai, aj}, {ak, al} для i > j і k > l номерів від послідовності мають той же модуль різниці n, для усіх, де l – довжина послідовності. Наприклад, для l = 4, {1,6,3,10}, {2,1,6,9} і {3,7,9,8} – приклади модульної послідовності−11. мал.. 4 показує з усіма різницями модуля. (перший нуль не враховується до довжини послідовності)

Модульна лослідовність використовується як перші значення в списку відновлення для комп'ютера номер нуль в кластері з n комп'ютерами. Інша частина списку відновлень заповнена номерами, що залишилися, аж до n−1.

0 1 6 3 10

1 5 8 7

6 2 4

3 9

Мал.. 4 модульна послідовність для l = 5 і n = 11 з усіма різницями.

Нехай MR0,n є модульним списком відновлень для процесу нуль в кластері з n комп'ютерами пронумерованого від нуля до n−1. Потім для n = 11 (і отже l = 4), який ми маємо: MR0, 11 ={1,6,3,10,2,4,5,7,8,9}, наприклад перша частина в MR0, 11 − модуль−11 послідовності для довжини 4 і інша частина MR0, 11 − номери, що залишилися, n−1. Це означає, що, якщо комп'ютер номер нуль зламаний, потім процес треба знову почати спочатку на комп'ютері один, завершено комп'ютером шість, завершено комп'ютером три, і так далі. Стрибки від пошкоджених комп'ютерів дорівнюють різницям від послідовності модуля. Схему відновлення модуля отримує модульний список відновлень для процесу i у кластері з n комп'ютерами: MRi, n = {(i + MR0, n(1)) mod n, (i+ MR0, n(2)) mod n, (i +MR0, n(3)) mod n,.,(i + MR0, n(n−1)) mod n}, де MR0, n(i) − i−ітий вхід в MR0, n. Наприклад, для n = 4, який ми маємо: MR0, n = {1,3,2}, MR1, n = {2,0,3}, MR2, n ={3,1,0}, і MR3, n = {0,2,1}.

Число комп'ютерів в кластері визначає яка схема різного модуля придатна для використання. Наприклад, для кластерві з 11, 12, 13, 14, 15, 16, 17 (z) комп'ютерів ми користуємося схемами модуля з довжиною 4 модуля 11. Відновлення складає список особливо для комп'ютерів − конструкція яких зазначена нижче: MRi, z = {(i + MR0, n(1)) специфікатор вирівнювання z, (i+ MR0, n(2)) mod z, (i +MR0, n(3)) mod z,.,(i + MR0, n(n−1)) mod z}, де MR0, n(i) − i−іте вхід в MR0, n. Наприклад, для z = 5, який ми маємо: MR0, z = {1,3,2}, MR1, z = {2,4,3}, MR2, z ={3,0,4}, MR3, z = {4,1,0}, і MR3, z = {0,2,1}.

Мал. 5 подає приклад списку відновлення в кластері з 11 комп'ютерів, коли комп'ютер нуль зламався.

 

Теорема 1: Модульна схема відновлення оптимальна, поки x комп'ютери або менше вимкнулися, де x = max(i), таке, що MR0, n(i)< n. У наступному доказі, усі модулі номерів n − будь-якиі з додатніх цілих чисел 0, 1,..., n − 1, означають комп'ютери, перераховані таким чином.

Доказ: Нехай y (0 ≤ y < n) є найюільш завантаженим комп'ютером, коли x комп'ютери вимкнулися, де x = max(i), таке, що M0, n(i)< n.

Мал. 5 Модуль−11 список відновлення для процесу нуль

Коли x комп'ютери вимкнулися, просес z (0 ≤ z < n) буде в i−ітому кроці закінчуються на комп'ютері . R(j) ми означаємо кроки від пошкодженого комп'ютера, які є різницями в послідовності модуля. Це означає, процес що закінчується на комп'ютері y після i кроків був спочатку розподілений для комп'ютера ; і цей процес передав перед тим, як він досяг комп'ютера y. Списки x показані нижче можливі послідовності комп'ютерів, яким треба виключитися для того, щоб додатковий процес закінчитився на комп'ютері y, тобто, якщо комп'ютер (y−r(1)) mod n у вимкнений один додатковий процес закінчиться на комп'ютері y, якщо mod комп'ютер (y−r(1) −r(2)) n і (y−r(2))mod n − додатковий процес закінчиться на комп'ютері y, і так далі.

1.

2.

3.

х.

Від визначення послідовності модуля ми знаємо, що усі суми послідовностей модуль n унікальні. Це означає, що ніякий комп'ютер не включається в більш ніж один з спискыв. Отже, найгірший випадок є ясно, коли комп'ютери в найкоротших списках мають ушкодження, наприклад для x = 3 найгырший випадок відбувається, коли комп'ютер: зламавля, а потім коли зламалися. Так само для x = 6 найгірший випадок відбувається, коли комп'ютер: вимкнулися, а потім коли комп’ютер вимкнулися, а потім коли комп’ютер вимкнулися.

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

 





Последнее изменение этой страницы: 2016-06-22; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.216.79.60 (0.008 с.)