Дипломная работа: Распараллеливание многоблочных задач для SMP-кластера

Введем некоторые понятия:

· Эффективность алгоритма A: R_A (L) = A(L)/OPT(L), где A(L) – нужное количество контейнеров когда применяем алгоритм A на список объектов L, OPT(L) – оптимальное количество контейнеров для данного списка объектов.

· R называется асимптотической эффективностью в худшем случае, если

R = inf{r>=1: для некоторых N>0, R_A (L)<=r для всех L где OPT(L)>=N}

· Алгоритм А называется алгоритмом без лишнего разбиения если:

a) Разбивает объект только тогда, когда его размер больше размера контейнера

б) Разбивает объект на два фрагмента так, чтобы первый фрагмент вместится полностью в одном из контейнеров

в) Открывает новый контейнер только тогда, когда в уже открытых контейнерах нельзя упаковать новый фрагмент.

Известно, что для всех алгоритмов упаковки в контейнеры без лишнего разбиения:

R <= U/(U-2), U>2

Теперь рассмотрим алгоритмы NF, NFD_, NFI, FFD-I

· NF - Next-Fit

На каждом шаге открываем только один контейнер, упаковываем объекты по очереди, если размер объекта больше размера свободной части контейнера – разобьем на две части так, чтобы первая часть заполнила контейнер. После этого открываем новый контейнер и вторую часть туда упаковываем. Это очень простой алгоритм и имеет плохую эффективность

R_NF =U/(U-2), U>=6

· NFD, NFI (Next-Fit с ранее отсортированным списком объектов по размеру в убывающем/возрастающем порядке)

R_NFD >= U/(U-2) если U=2n, n>=3

R_NFD >= (U+1)/(U-1) если U=2n+1, n>=2

Но это только нижняя оценка, мы вполне сможем подобрать пример, когда NFD и NFI работают тоже плохо, как и NF.

· FFD-I и FFI-I (Iterative First-Fit Decreasing/Increasing with Item fragmentation)

Попробуем упаковать все объекты списка L в фиксированное количество m контейнеров. Сортируем список объектов по размеру в невозрастающем порядке. Каждый объект будем упаковывать в первый подходящий контейнер, если такого нет, разобьем объект на две части. Первая часть должна заполнить первый свободный контейнер, а вторую часть положим в отсортированный список объектов. Если не удалось упаковать все объекты в m контейнеров, увеличиваем m и повторяем.

Пусть s(L) – сумма всех объектов в списке L.

1) Взять m=[s(L)/U]

2) FFD()

3) Если успешно, останавливаем

4) Иначе m=m+1 и goto 2)

Для алгоритма FFD-I:

R_{FFD - I} <= U/(U-1) если U<=15

U/(U-1) < R_FFD-I < U/(U-2) если U>=16

Получаем, что FFD-I лучше NFD/NFI и NF.