Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
Философия на алгоритмизирането: Постъпателни алгоритми (greedy алгоритми). Проблемът – оптимална диспечеризацияработи поетапно. На всеки етап се взима изглеждащото за най-добро решение, независимо от последиците. Т.е.локален оптимум. Или стратегията е “take what you can get now”.В края на алг.приемаме, че локал.съвпада с глобал.оптимум. Пр.за това е стратегията на връщане на монети: връща на всеки етап монета с мак. възможна ст-ст $17.61 1*$10 +1*$5 +2*$1 + 2*0.25(quarters) +1*0.1 (dime) + 1*0.01(penny). Този алгоритъм не работи във всички монетарни системи. Друг пример: авт. трафик. simple scheduling problemимаме дадени задачи j1 …jN с времена на изпълнение t1…tN и 1 процесор. Искаме разпределяне с цел мин. средно време на завъшване на задача (т.е. на коя мин. средно завършва задача). (няма прекъсване на задача). Първата завършва след 15, втората след 23, третата след 26, след 36 общо 100 мин/4 = 25 средно ще завършва задача. Друга подредба е показана по-долу:ср.време 17.75 Стратегията е най-късата задача – най-напред(тя участва най-много във формиране времената на следв.зад). Това винаги дава оптимално решение. Нека първата пусната задача е j i1…j iN с времена на завършване: t i1, t i1+t i2, t i1 +t i2 +t i3. Цената на разпределението става: . многопоцесорен вариантИмаме j1……jN; ti….tN и P процесора. Подрежд. първо на късите зад. Нека Р=3:
едно решение (започваме с къси задачи и циклим по процесори): Общо време на завършване 165. Средно 165/9 = 18.33. Друга стратегия (когато Р дели N точно) е: за всеки 0 <= I < N/P поставяме последоват. следващите Р задачи на различен процесор. I член не зависи от подредбата, а само втория (“к”). Ако предположим, че в подредба съществува x >y, такова че t ix минимизация на крайното време на завършване на всички задачи по-горе това е 40 или 38. Ето подредба с t = 34: очевидно тази подредба не може да се подобри, защото всички са заети през цялото време. Това обаче е друга стратегия – най-късо общо завършване. Изтегляне 1.47 Mb. Сподели с приятели:
|