Теоретичен въпрос, може би е очевиден:
Възможно ли е алгоритъм, след като бъде внедрен по паралелен начин с N нишки, да бъде изпълнен повече от N пъти по-бързо от оригиналния, еднонишков алгоритъм? С други думи, може ли печалбата да бъде по-добра от линейната с брой нишки?
Не е често срещано, но със сигурност е възможно.
Помислете например за изграждане на софтуерен тръбопровод, където всяка стъпка в тръбопровода прави сравнително малко количество изчисления, но изисква достатъчно статични данни, за да запълни приблизително целия кеш с данни - но всяка стъпка използва различни статични данни.
В случай като този серийното изчисление на един процесор обикновено ще бъде ограничено основно от честотната лента към основната памет. Ако приемем, че имате (поне) толкова процесори/ядра (всеки със собствен кеш за данни), колкото стъпките на тръбопровода, можете да заредите всеки кеш за данни веднъж и да обработвате един пакет данни след друг, запазвайки едни и същи статични данни за всички тях. Сега вашето изчисление може да продължи със скоростта на процесора, вместо да бъде ограничено от честотната лента към основната памет, така че подобрението на скоростта може лесно да бъде 10 пъти по-голямо от броя на нишките.
Теоретично бихте могли да постигнете същото с един процесор, който просто имаше наистина огромен кеш. От практическа гледна точка обаче изборът на процесори и размери на кеша е доста ограничен, така че ако искате да използвате повече кеш, трябва да използвате повече процесори -- и начина, по който повечето системи предлагат, за да постигнете това е с множество нишки.
да
Видях алгоритъм за преместване на ръка на робот чрез сложни маневри, който основно се разделя на N нишки и всяка нишка се движи повече или по-малко произволно през пространството на решението. (Това не беше практичен алгоритъм.) Статистиката ясно показа суперлинейно ускоряване на една нишка. Очевидно вероятността за постигане на решение с течение на времето е нараснала сравнително бързо и след това е изравнена до известна степен, така че предимството беше в многото първоначални опити.
Законът на Амдал (паралелизиране) ни казва, че това не е възможно за общия случай. В най-добрия случай можем идеално да разделим работата по N. Причината за това е, че без серийна част, формулата на Amdahl за ускоряване става:
Ускоряване = 1/(1/N)
където N е броят на процесорите. Това разбира се намалява само до N.
