Систолни низ

У паралелној рачунарској архитектури, систолни низ је хомогена мрежа чврста у спрези обраде података јединица (ДПУ) зване ћелије или чворови. Сваки чвор или ДПУ независно израчунава делимичан резултат у функцији података добијених од својих суседа узводно, чува резултате у себи и прослеђује их низводно. Систоличке низове су измислили Рихард П. Брент и Х. Т. Кунг који су их развили да израчунају највеће заједничке делиоце целих бројева и полинома.^[1] Они су понекад класификовани као вишеструке инструкције једног податка ( МИСД ) архитектуре под флиновом поделом, али ова класификација је под знаком питања, јер јак аргумент може бити да се разликују систолни низове од било којег од Флинове четири категорије : СИСД , СИМД , МИСД , МИМД, као што је објашњено касније у овом чланку .

Паралелни унос података протиче кроз мрежу каблом чворова процесора, подсећа на људски мозак који комбинују , процес, спајање или сортирање улазних података у изведеним резултатима. Зато што простирање таласа налик подацима кроз систолни низ подсећа на пулс система крвотока људи, име систолни је сковано из медицинске терминологије. Име је изведено из систоле ( медицина) као аналогија са редовним пумпањем крви путем срца.

Апликације[уреди | уреди извор]

Систолички низови су често тешко-прикључени за конкретне операције , као што су " умножавање и акумулирање" , да изврше масовну паралелну интеграцију, конволуција, корелацију, множење матрица или сортирања задатака података.

Архитектура[уреди | уреди извор]

Систолни низ обично се састоји од велике монолитне мреже примитивних рачунарских чворова који могу бити фиксирана или конфигурисаног софтвера за одређену апликацију. Чворови су обично фиксни и идентични , док се веза може програмирати . Општији таласни фронт процесори , с друге стране, користе софистициране и појединачно програмиране чворове који могу или не могу бити монолитни , у зависности од величине низа параметара и дизајна. Друга разлика је да се систолни низови ослањају на синхрони пренос података, док таласни фронт имају тенденцију да раде асинхроно.

За разлику од више заједничке фон Нојманове архитектуре , где извршење програма следи сценарио инструкција који се чувају у заједничкој меморији, адресирано и секвенцирано под контролом централне процесорске јединице програмског бројача ( ПС ) , појединачни чворови унутар систолног низа се активирају доласком нових података и увек обрађују податке на потпуно исти начин. Стварна обрада у сваком чвору може бити тешко снадбевена жицом или блокирани микропрограм, у том случају заједнички чвор личности може бити блок програмирања.

Систолни низ парадигма са токовима података вођеним бројачем података, је пандан фон Нојманове архитектуре са упутством тока којим је управљао програмски борјач. Јер систоличко поље обично шаље и прима вишеструке токове података , и више бројача података је потребно за производњу ових токова података , који подржавају паралелизам података.

Стварни чворови могу бити једноставни и фиксирани или се састојати од више софистицираних јединица користећи микро код, што може бити блок програмирања.

Циљеви и предности[уреди | уреди извор]

Највећа корист од систолних низова је да су сви подаци операнд и делимични резултати чувају у ( пролазе кроз ) низу процесора . Нема потребе да приступите спољним аутобусима , главна меморија или унутрашњи кеш током сваке операције као што је то случај са фон Нојманом или харвардским узастопним машинама . Консекутивна ограничења у паралелном перформансу диктира Амдалов закон и не примењују на исти начин , јер подаци зависе од имплицитног управљања програмабилних повезаних чворова и не постоје узастопни кораци у управљању високог паралелног протока података .

Систолички низови су стога изузетно добри у вештачкој интелигенцији, обради слика, препознавању облика, компјутерској визији и другим пословима које животињски мозгови раде тако посебно добро. Бејфронт процесори генерално могу бити веома добри у машинском учењу применом неуронске мреже конфигурисане у хардверу.

Класификација контроверзе[уреди | уреди извор]

Док систолни низови су званично класификовани као МИСД , њихова класификација је донекле проблематична. Пошто је улаз обично вектор независних вредности , систолни низ дефинитивно није СИСД. Од ове улазне вредности су спојени и комбинују резултат (е) и не одржавају своју независност као што би у СИМД векторским процесорским јединицама, низ не може класификовати као такав. Сходно томе, низ се не може класификовати као МИМД , јер МИМД се може посматрати као прикупљање мањих СИСД и СИМД машина .

На крају , јер се рој података који је трансформисан док пролази кроз низ од чвора до чвора, вишеструки чворови нису у функцији на истим подацима, што чини МИСД класификацију погрешном. Други разлог зашто систолички низ не треба квалификовати као МИСД је исти као и онај који га дисквалификује из категорије СИСД : Улазни податак је обично вектор ниједна појединачна вредност података, иако би се могло тврдити да било који дати улазни вектор је један скуп података.

Све горе наведено не одолева, систолни низови често нуде као класичан пример МИСД архитектуру у уџбеницима паралелних обрада у инжењерској класи. Ако се низ споља посматра као атомски можда би требало класификовати као SFMuDMeR = једну функцију , вишеструких података , спојених резултата.

Детаљан опис[уреди | уреди извор]

Систолно поље се састоји од матрице попут редова обраде јединица података званих ћелије. Обраде података јединице ( ДПУ ) су сличне централним јединицама за обраду ( ЦПУ) , ( осим уобичајеног недостатка ИП процесора ^[2], од када је операција превоза активирана, односно од доласка објекта података ) . Свака ћелија дели информације са својим суседима одмах након обраде . Систолно поље је често правоугаоног облика , где проток података преко низа између комшија ДПУ, често са различитим подацима тече у различитим правцима. Потоци података улазе и излазе из низова портова који су генерисани од стране ауто секвенционираних меморијских јединица, АСМС. Сваки АСМ садржи бројач података. У уграђеним системима подаци струја могу такође бити улаз из и/или излаз на спољни извор .

Пример систолног алгоритма може бити дизајниран за матрицу мултипликације. Једна матрица се доводи у низ у времену од врха низа и спушта се доле низ низ , друга матрица се доводи у колону у времену са леве стране низа и пролази слева надесно. Лажне вредности су затим прошле све док сваки процесор није видео један цео ред и једну целу колону. У овом тренутку , резултат множења се чува у низу и сада могу да се емитују ред или колона истовремено, течећи доле или преко низа.^[3]

Систолички низови су низови ДПУ који су повезани са малим бројем најближих суседа ДПУ у мрежама попут топологије . ДПУс обавља низ операција на подацима који течу између њих. Зато што су традиционалне методе синтезе систоличког низа практиковане алгебарским алгоритмима, само јединствени низови са само линеарним цевима се могу добити , тако да су архитектуре исте у свим ДПУ. Последица је , да само апликације са редовним зависностиma података се спроводи на класичним систолним низовима . Као СИМД машина , која ради систолне низове израчунавањем у " закључаном-кораку" са сваким процесором предузима алтернативно рачунарство | комунициране фазе . Али систолни низови са асинхроним руковања између ДПУ се зове таласни фронт низови. Један познати систолички низ је иВарп процесор, који је произведена од стране компаније Интел . ИВарп систем има процесор са линеарним низом повезан са подацима аутобуса који иду у оба смера.

Историја[уреди | уреди извор]

Систоличка поља ( <wavefront процесори ) , први пут су их описали Х. Т. Кунг и Чарлс Е. Леисерсон , који је објавио први папир који описује систолна поља 1978. Међутим , прва машина позната да је користила сличну технику је била Колос Марк II 1944. године .

Пример примене[уреди | уреди извор]

Пример апликације-евалуација полинома

Хорнерово правило за оцењивање полинома је :

Линеарно систоличко поље у којем су процесори распоређени у паровима : један умножава свој улаз са х и доноси резултат надесно , следећи додаје а_ј и доноси резултат надесно :

Предности и мане[уреди | уреди извор]

Предности

Брже
Скалабилније

Против

Скупо
Високоспецијализован, обичај хардвер је потребна често специфична апликација.
Није широко имплементиран
Ограничен број база програма и алгоритама

Имплементација[уреди | уреди извор]

Циско пхф процесор мреже је интерно организован као систолни низ.^[4]

Види још[уреди | уреди извор]

МИСД -Вишеструко Упутство Слободног податка , на пример: Систоличка поља
иВарп -Систоличко поље рачунара , ВЛСИ , Интел/ЦМУ
ВАРП(систолички поље)- Систоличко поље рачунара ГЕ/ЦМУ

Напомене[уреди | уреди извор]

H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979
S. Y. Kung: VLSI Array Processors; Prentice-Hall, Inc., 1988
N. Petkov: Systolic Parallel Processing; North Holland Publishing Co, 1992