Speedup оценява. право и Густафсон Amdahl му - BARSIS
По-рано получена оценка на времето за решаване на проблема, когато се използват р процесори. Приема се, че проблемът може да бъде разделена на модули, определяне на зависимостта графиката, който определя реда на възможно извикване модули. От интерес е случаят, когато задачата може да бъде разделена на две части, едната част от който се изисква да се изпълняват последователно, а вторите могат да бъдат напълно паралелизирано. закон Amdahl и Густафсон - BARSIS позволи да получат оценки за ускорението в зависимост от дела на последователни изчисления в общото време за решаване на проблема. Закони се различават само по начина, по който се определя от съотношението на последователни изчисления.
Право на Amdahl
Нека решаването на проблема с един процесор, времето може да се представи като сума от момента на решението и на последователно част, което позволява паралелното:
Разделяйки двете страни от, преминете към акциите на време:
Докато решаването на проблема с п процесори също присъства в две части:
Последователно дял не може да се намали чрез увеличаване на броя на процесори, така че. Паралелно страна съществува оценка, така че връзката:
Що се отнася до ускорението, получаваме:
Връзка (30) се нарича Закон Amdahl му. Той казва, че ускорението е ограничена по-горе с количество в зависимост от съотношението на последователни изчисления. Ако, например, последователни изчисления заемат 10% от общото време за изчисление, за сметка на паралелното не може да се постигне с повече от десет пъти работно време ускорение, колко щеше да донесе процесори.
Право Песимистичен Amdahl може да се заглади, ако си спомняте, че всички характеристики да се счита, като функция на п - параметър, характеризиращ обема на данните, използвани. В този случай, правото на Amdahl е, както следва:
На практика, това често се случва, че последователно е част от проблема е постоянна и не зависи от размера на данните. В този случай, р (п) - намаляваща функция, а след това за голяма п може да се постигне добро ускорение, без да влизат в конфликт със закона Amdahl.
Право Густафсон -Barsisa
Пишем оптималното време за работа при използване на р процесори като сумата от времената на две части - паралелен и сериен:
Предвид факта, че последователно част от р процесори се извършва толкова дълго, колкото един процесор, както и времето на успоредната част в оптимален случай може да бъде намален до р пъти, получаваме:
Разделяйки двете страни от, преминете към акциите на време:
Помислете сега отношението:
Два начина за паралелизация
Говорейки за паралелното, има два основни начина, които дават възможност за паралелни изчисления, - паралелното и паралелно извършване на задачите на данните.
Моделът се счита по-горе, съответстват на случая с parallelizing задачи. В този модел, различни модули на една програма могат да се изпълняват паралелно.
Помислете сега алтернативната ситуация, в която паралелно извършване на данни. В този случай, множество от данни, за да бъдат обработени с една единица.
паралелното Според
Да предположим, че искаме да се реши проблема с D на ограничен набор данни. Често, ефективно последователен алгоритъм може да получи решение на този проблем, ако е възможно да се намали решаването на първоначалния проблем за решаване подзадачи K - където всеки под-задача е решаването на проблема, но оригиналната Г. подмножество на данните. Това е най-ефективна, когато всички подзадачи са със същия размер.
Сравнително проста, но много важна в теорията на алгоритмите
Ако задача D на (X) може да бъде намалена към разтвора на същите измерение к подзадачи и линеен времето на вземане под к може да се получи общ разтвор на оригиналния проблема, сложността време за решаване на първоначалния проблем Т (п) се получава от:
Свързани статии