Makro dopravník

Makropotrubí je distribuovaný víceprocesorový systém , který má softwarovou a hardwarovou podporu pro organizování výpočtů podle principu makropotrubí. [1] Tento princip navrhl v roce 1978 sovětský matematik V. M. Glushkov . Jeho podstata spočívá v tom, že při rozdělování výpočetních úloh mezi procesory je každému procesoru v dalším kroku výpočtů zadán takový úkol, který jej dokáže zatížit prací po určitou dobu, aniž by interagoval s ostatními procesory. [1] :320 Sekvenční aplikace principu makro-pipeline vede k lineárnímu zrychlení v závislosti na počtu procesorů použitých k vyřešení problému.

Matematický popis

Předpokládejme, že potřebujeme vyřešit problém výpočtu funkce . Doba výpočtu závisí na počtu operací, které zase závisí na nějakém číselném parametru nebo souboru parametrů charakterizujících počáteční data . Nechť je čas vyjádřen závislostí . Parametr lze zvolit tak, aby funkce rostla s růstem . Je-li například řešením soustavy lineárních algebraických rovnic s maticí koeficientů a vektorem volných členů , které je vypočítáno některou z přímých metod, pak lze pořadí soustavy brát jako. Pokud je systém řešen iterační metodou , pak jako pořadí systému a počet iterací lze brát dvojici . $y=f(x)$ $n=(n_{1},n_{2},...)$ $X$ $t(n)$ $n$ $t(n)$ $n$ $y=f(x)=f(x_{1},x_{2})$ $x_{1}$ $x_{2}$ $n$ $n$

Předpokládejme, že je možné rozdělit výpočet funkce rovnoměrně mezi procesory tak, že každý z procesorů bude pracovat po určitou dobu . V reálném systému stojí za zvážení i režie spojená s výměnou informací mezi procesory. Představme si čas strávený na režii jako , zahrnuje skutečný čas potřebný pro přenos dat, čas pro synchronizaci. Doba řešení problému na systému procesorů bude označena jako , pak zrychlení při řešení problému s parametrem lze vyjádřit vzorcem: $y=f(x)$ $p$ $t_{p}(n)=t(n)/p$ $w_{p}(n)$ $p$ $T_{p}(n)$ $a_{p}=a_{p}(n)$ $n$

a_{p}(n)={\frac {T_{1}(n)}{T_{n}(n)))={\frac {t(n)}{t_{p}(n )+w_{p}(n)}}={\frac {1}{1+{\tfrac {w_{p}(n)}{t_{p}(n)))}}p=b_{p }(n)\cdot p.

Vzorec má smysl pouze v případě , že , kde je maximální počet procesorů, který umožňuje rozumné rozdělení výpočetní práce pro danou velikost úlohy. Jestliže pak při změně z 1 na roste produktivita ne pomaleji než lineárně s koeficientem účinnosti . Pokud čas strávený na výměně roste pomaleji než výpočetní čas, pak se s růstem koeficient účinnosti blíží 1. Výše uvedený vzorec nezohledňuje mnoho dalších faktorů, ale umožňuje hledat efektivní algoritmy pro řešení problémů na multiprocesoru distribuované systémy . $p<k(n)$ $k(n)$ $w_{p}(n)/t_{p}(n)<1$ $p$ $k(n)$ $b_{p}(n)>1/2$ $n$

Poznámky

↑ 1 2 Slovník kybernetiky / Edited by Akademik V. S. Mikhalevich . - 2. - Kyjev: Hlavní vydání Ukrajinské sovětské encyklopedie pojmenované po M. P. Bazhanovi, 1989. - 751 s. - (C48). — 50 000 výtisků. - ISBN 5-88500-008-5 .

Literatura

Glushkov VM, Pogrebinsky SB, Rabinovich ZL O vývoji struktur víceprocesorových počítačů interpretujících jazyky vysoké úrovně. — Řídicí systémy a stroje. 1978 č. 6 - str. 61-66.
Glushkov V. M. O architektuře vysoce výkonných strojů. - Předtisk Ústavu kybernetiky č. 78-65, Kyjev, 1978. - 41 s.
Mikhalevich VS, Kapitonova Yu. V., Letichevsky AA, Molchanov IN, Pogrebinsky SB Organizace výpočtů ve víceprocesorových počítačových systémech. Kybernetika. 1984 č. 3 - str. 1-10

Makro dopravník

Matematický popis

Poznámky

Literatura

Viz také