Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У паралельних комп'ютерних архітектурах, систолічний масив є однорідною мережею щільно з'єднаних блоків обробки даних, які називаються клітинами або вузлами. Систолічні масиви були винайдені Річардом Брентом і Кунгом, який розробив їх для обчислення найбільших спільних дільників цілих чисел і поліномів. Вони іноді класифікуються як декілька команд одноядерних даних (MISD) архітектури з систематики Флінна, але ця класифікація залишається під питанням, бо існує вагомий аргумент, щоб відрізнити систолічний масив від будь-якої з чотирьох категорій Флінна: SISD, SIMD, MISD, MIMD, який буде зазначено далі в цій статті.
Паралельне введення даних проходить через мережу жорстких дротових процесорних вузлів, схожих на людський мозок, які поєднують в собі процес, злиття або сортування вхідних даних у похідний результат. Оскільки хвиля — як поширення даних через систолічний масив нагадує пульс системи кровообігу людини, назву систолічного масиву було взято з медичної термінології. Назва походить від систоли за аналогією зі звичайним прокачуванням крові до серця.
Область застосування
Систолічні масиви часто використовують для конкретних операцій, таких, як «поширення і накопичення», щоб виконати в широкому масштабі паралельну інтеграцію, згортку, кореляцію, множення матриць або сортування даних завдань. Вони також використовуються для динамічного програмування алгоритмів, використовуваних в ДНК і аналізу послідовності білку.
Особливості
Таким чином, систолічна структура — це однорідне обчислювальне середовище з процесорних елементів, що поєднує в собі властивості конвеєрної і матричної обробки і володіє наступними особливостями:
- Обчислювальний процес в систолічних структурах є безперервною і регулярною передачею даних від одного процесорного елементу (ПЕ) до іншого без запам'ятовування проміжних результатів обчислення;
- Кожен елемент вхідних даних вибирається з пам'яті одноразово і використовується стільки разів, скільки необхідно за алгоритмом, введення даних здійснюється в крайніх ПЕ матриці;
- Однотипні ПЕ утворюють систолічну структуру і кожен з них може бути менш універсальним, ніж процесори звичайних багатопроцесорних систем. Тип ПЕ вибирається відповідно до призначення систолічної матриці і структури просторових зв'язків (найбільш поширені процесорні елементи, орієнтовані на множення з накопиченням);
- Потоки даних і керуючих сигналів мають регулярність, що дозволяє об'єднувати ПЕ локальними зв'язками мінімальної довжини;
- Алгоритми функціонування дозволяють поєднати паралелізм з конвеєрною обробкою даних;
Продуктивність матриці можна поліпшити за рахунок додавання в неї певного числа ПЕ, причому коефіцієнт підвищення продуктивності при цьому лінійний.
В даний час досягнута продуктивність систолічних процесорів близько 1000 мільярдів операцій/с.
Архітектура
Систолічний масив, як правило, складається з великої монолітної мережі примітивних обчислювальних вузлів, які можуть бути зафіксованими або програмне забезпечення може бути налаштоване для конкретного додатку. Вузли, як правило, фіксовані і ідентичні, в той час як з'єднувальне обладнання програмується. Більш загальні хвильового фронту процесори, на відміну від цього, використовують складні і індивідуально програмовані вузли, які можуть або не можуть бути монолітними, в залежності від розміру масиву і параметрів конструкції. Інша відмінність полягає в тому, що систолічні масиви покладаються на синхронні передачі даних, в той час як хвильовий фронт, як правило, працює асинхронно.
На відміну від більш загальної архітектури фон Неймана, де виконання програми слідує сценарію інструкцій, що зберігаються в загальній пам'яті, адресовані і секвеновані під контролем лічильника програми процесора (PC), окремі вузли в межах систолічного масиву викликані прибуттям нових даних і завжди обробляють дані точно таким же чином. Фактична обробка всередині кожного вузла може бути зафіксована або блочно замікрокодована, і в цьому випадку загальна індивідуальність вузла може бути блочно запрограмованою.
Систолічна парадигма масиву даних-потоків, керованих даними лічильників, є аналогом архітектури фон Неймана з інструкцією-потоку запущеною лічильником програми. Оскільки систолічний масив зазвичай посилає і приймає безліч потоків даних, а також кілька лічильників даних необхідні для створення цих потоків даних, він підтримує паралелізм даних.
Фактичні вузли можуть бути простими і провідними (фіксованими), або складатися з більш складних одиниць за допомогою мікрокоду, який може бути блочно запрограмованим.
Цілі і переваги
Основною перевагою систолічних масивів є те, що всі дані операндів і часткові результати зберігаються в межах масиву процесора. У них немає необхідності доступу до зовнішніх шин, основної пам'яті або внутрішнього кешу під час кожної операції, як у випадку з машинами фон Неймана або гарвардськими послідовними машинами. Послідовні обмеження паралельного виконання, що диктуються законом Амдала, також не застосовуються таким же чином, так як дані залежності неявно обробляються програмованим вузлом з'єднального обладнання і не виникає ніяких послідовних кроків в процесі управління високо паралельного потоку даних.
Систолічні масиви тому надзвичайно практичні в області штучного інтелекту, обробки зображень, розпізнавання образів, комп'ютерного зору і інших задач. Процесори Wavefront в цілому також можуть бути дуже хорошими в машинному навчанні шляхом впровадження налаштування нейронних мереж на апаратному рівні.
Класифікаційна дискусія
У той час, як систолічні масиви офіційно класифікуються як MISD, ця класифікація дещо проблематична. Оскільки ввід даних зазвичай являє собою вектор незалежних значень, систолічний масив безумовно не SISD. Так як ці вхідні значення об'єднуються і комбінуються в результат (s) і не зберігають свою незалежність, на відміну від блоку векторної обробки SIMD, масив не може бути розцінений як такий. Отже, масив не може бути класифікований як MIMD, так як MIMD можна розглядати як просто колекцію менших SISD і SIMD машин.
Нарешті, оскільки дані рою трансформуються, коли вони проходять через масив від вузла до вузла, множинні вузли не працюють на одних і тих же даних, що робить визначення MISD класифікації некоректним. Інша причина, чому систолічний масив не повинен кваліфікуватись як MISD така, що відрізняє його від SISD категорії: Вхідні дані зазвичай представляють собою вектор не одного значення даних, хоча можна було б стверджувати, що будь-який вхідний вектор являє собою один набір даних.
Незважаючи на все вищесказане, систолічні масиви часто пропонуються як класичний приклад MISD архітектури як в підручниках по паралельних обчисленнях, так і в інженерному класі. Якщо масив розглядається з зовнішнього боку, як атомарна операція, то можливо його класифікувати як SFMuDMeR = Однофункціональні (Single Function), Багаторазові дані (Multiple Data), Об'єднані в результат (s) (Merged Result).
Детальний опис
Систолічний масив складається з матриць типу рядів блоків обробки даних, званих датчиками. Блоки обробки даних аналогічні центральним процесорам (CPU), (окрім для ситуації звичайної відсутності лічильника програми, коли операція транспортно-спрацьовує, тобто після прибуття об'єкта даних). Кожна клітинка ділиться інформацією зі своїми сусідами відразу після обробки. Систолічний масив часто прямокутної форми, де потік даних проходить через весь масив між сусідніми блоками обробки даних, часто з різним потоком даних в різних напрямках. Потоки даних, що надходять і виходять з портів масиву генеруються блоками пам'яті автоматичного секвенування, ASMs (auto-sequencing memory units). Кожен блок ASM включає в себе дані лічильника. У вбудованих системах потік даних може бути також введений і (або) виходити до зовнішнього джерела.
Прикладом систолічного алгоритму може бути матричне множення. Одна матриця подається в ряд з верхньої частини масиву і передається вниз по масиву, інша матриця подається в колонку, в цей же час, з лівого боку масиву і проходить зліва направо. Фіктивні значення потім передаються в процесор, поки кожен не побачив один цілий ряд і одну цілу колонку. На даний момент, результат множення зберігається в масиві, і в даний час можуть бути виведені рядок або стовпець.
Систолічні масиви це масиви блоків обробки даних, які підключені до кількох найближчих сусідів блоку обробки даних в сітчастій топології. Блоки обробки даних виконують послідовність операцій над даними, що передаються між ними. Так як традиційні методи синтезу систолічного масиву практикувалися алгебраїчними алгоритмами, можуть бути отримані тільки уніфіковані масиви з тільки лінійними трубами, так що архітектура однакова у всіх блоках обробки даних. Наслідком цього є те, що тільки програми з регулярною залежністю даних можуть бути реалізовані на класичних систолічних масивах. Як SIMD машини, систолічні масиви з тактовою частотою замкнуто-пошагово обчислюються з кожним процесором беручи альтернативні обчислювання | зв'язок фаз. Але систолічні масиви з асинхронним зв'язком між блоками обробки даних називаються масивами хвильового фронту. Один добре відомий систолічний масив це iWarp процесор Університету Карнегі — Меллон, який був виготовлений виробником Intel. Система iWarp має лінійний матричний процесор, з'єднаний з шинами даних, що йдуть в обох напрямках.
Історія
Систолічні масиви (< процесорів хвильового фронту), були вперше описані Кунгом і Лейзерсоном, які опублікували перший документ, що описує систолічні масиви в 1978 р. Проте перша машина, яка використовувала подібну техніку була Колос Mark II в 1944 році.
Приклад застосування
Поліноміальна оцінка:
Схема Горнера для обчислення багаточлена:
Лінійний систолічний масив, в якому процесори розташовані попарно: один примножує його вхід на х і передає результат вправо, наступний додає 
і передає результат далі.
Переваги та недоліки
Плюси:
- Швидкий;
- Масштабний;
Мінуси:
- Дорогий;
- Не широко застосовується;
- Обмежений базовий код програм і алгоритмів;
- Вузькоспеціалізований, часто виготовлений на замовлення обладнання конкретного додатка.
Реалізації
Cisco PXF — мережевий процесор внутрішньо організований як систолічний масив.
Див. також
- MISD — Multiple Instruction Single Data, Приклад: систолічний масив.
Список літератури
- Цилькер Б. Я. Організація ЭОМ та систем: Підручник для вузів / Б. Я. Цилькер, С. А. Орлов. — 2-е вид. — СПб.: Питер, 2011. — 688 с. — .
- Н. Петков: Систолічна паралельна обробка; Північна Голландія,1992.
Посилання
- Instruction Systolic Array (ISA)
- 'A VLSI Architecture for Image Registration in Real Time' (Based on systolic array), Vol. 15, September 2007
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U paralelnih komp yuternih arhitekturah sistolichnij masiv ye odnoridnoyu merezheyu shilno z yednanih blokiv obrobki danih yaki nazivayutsya klitinami abo vuzlami Sistolichni masivi buli vinajdeni Richardom Brentom i Kungom yakij rozrobiv yih dlya obchislennya najbilshih spilnih dilnikiv cilih chisel i polinomiv Voni inodi klasifikuyutsya yak dekilka komand odnoyadernih danih MISD arhitekturi z sistematiki Flinna ale cya klasifikaciya zalishayetsya pid pitannyam bo isnuye vagomij argument shob vidrizniti sistolichnij masiv vid bud yakoyi z chotiroh kategorij Flinna SISD SIMD MISD MIMD yakij bude zaznacheno dali v cij statti Sistolichnij masiv dlya peremnozhennya strichkovih matric Paralelne vvedennya danih prohodit cherez merezhu zhorstkih drotovih procesornih vuzliv shozhih na lyudskij mozok yaki poyednuyut v sobi proces zlittya abo sortuvannya vhidnih danih u pohidnij rezultat Oskilki hvilya yak poshirennya danih cherez sistolichnij masiv nagaduye puls sistemi krovoobigu lyudini nazvu sistolichnogo masivu bulo vzyato z medichnoyi terminologiyi Nazva pohodit vid sistoli za analogiyeyu zi zvichajnim prokachuvannyam krovi do sercya Oblast zastosuvannyaSistolichni masivi chasto vikoristovuyut dlya konkretnih operacij takih yak poshirennya i nakopichennya shob vikonati v shirokomu masshtabi paralelnu integraciyu zgortku korelyaciyu mnozhennya matric abo sortuvannya danih zavdan Voni takozh vikoristovuyutsya dlya dinamichnogo programuvannya algoritmiv vikoristovuvanih v DNK i analizu poslidovnosti bilku OsoblivostiTakim chinom sistolichna struktura ce odnoridne obchislyuvalne seredovishe z procesornih elementiv sho poyednuye v sobi vlastivosti konveyernoyi i matrichnoyi obrobki i volodiye nastupnimi osoblivostyami Obchislyuvalnij proces v sistolichnih strukturah ye bezperervnoyu i regulyarnoyu peredacheyu danih vid odnogo procesornogo elementu PE do inshogo bez zapam yatovuvannya promizhnih rezultativ obchislennya Kozhen element vhidnih danih vibirayetsya z pam yati odnorazovo i vikoristovuyetsya stilki raziv skilki neobhidno za algoritmom vvedennya danih zdijsnyuyetsya v krajnih PE matrici Odnotipni PE utvoryuyut sistolichnu strukturu i kozhen z nih mozhe buti mensh universalnim nizh procesori zvichajnih bagatoprocesornih sistem Tip PE vibirayetsya vidpovidno do priznachennya sistolichnoyi matrici i strukturi prostorovih zv yazkiv najbilsh poshireni procesorni elementi oriyentovani na mnozhennya z nakopichennyam Potoki danih i keruyuchih signaliv mayut regulyarnist sho dozvolyaye ob yednuvati PE lokalnimi zv yazkami minimalnoyi dovzhini Algoritmi funkcionuvannya dozvolyayut poyednati paralelizm z konveyernoyu obrobkoyu danih Produktivnist matrici mozhna polipshiti za rahunok dodavannya v neyi pevnogo chisla PE prichomu koeficiyent pidvishennya produktivnosti pri comu linijnij V danij chas dosyagnuta produktivnist sistolichnih procesoriv blizko 1000 milyardiv operacij s ArhitekturaSistolichnij masiv yak pravilo skladayetsya z velikoyi monolitnoyi merezhi primitivnih obchislyuvalnih vuzliv yaki mozhut buti zafiksovanimi abo programne zabezpechennya mozhe buti nalashtovane dlya konkretnogo dodatku Vuzli yak pravilo fiksovani i identichni v toj chas yak z yednuvalne obladnannya programuyetsya Bilsh zagalni hvilovogo frontu procesori na vidminu vid cogo vikoristovuyut skladni i individualno programovani vuzli yaki mozhut abo ne mozhut buti monolitnimi v zalezhnosti vid rozmiru masivu i parametriv konstrukciyi Insha vidminnist polyagaye v tomu sho sistolichni masivi pokladayutsya na sinhronni peredachi danih v toj chas yak hvilovij front yak pravilo pracyuye asinhronno Na vidminu vid bilsh zagalnoyi arhitekturi fon Nejmana de vikonannya programi sliduye scenariyu instrukcij sho zberigayutsya v zagalnij pam yati adresovani i sekvenovani pid kontrolem lichilnika programi procesora PC okremi vuzli v mezhah sistolichnogo masivu viklikani pributtyam novih danih i zavzhdi obroblyayut dani tochno takim zhe chinom Faktichna obrobka vseredini kozhnogo vuzla mozhe buti zafiksovana abo blochno zamikrokodovana i v comu vipadku zagalna individualnist vuzla mozhe buti blochno zaprogramovanoyu Sistolichna paradigma masivu danih potokiv kerovanih danimi lichilnikiv ye analogom arhitekturi fon Nejmana z instrukciyeyu potoku zapushenoyu lichilnikom programi Oskilki sistolichnij masiv zazvichaj posilaye i prijmaye bezlich potokiv danih a takozh kilka lichilnikiv danih neobhidni dlya stvorennya cih potokiv danih vin pidtrimuye paralelizm danih Faktichni vuzli mozhut buti prostimi i providnimi fiksovanimi abo skladatisya z bilsh skladnih odinic za dopomogoyu mikrokodu yakij mozhe buti blochno zaprogramovanim Cili i perevagiOsnovnoyu perevagoyu sistolichnih masiviv ye te sho vsi dani operandiv i chastkovi rezultati zberigayutsya v mezhah masivu procesora U nih nemaye neobhidnosti dostupu do zovnishnih shin osnovnoyi pam yati abo vnutrishnogo keshu pid chas kozhnoyi operaciyi yak u vipadku z mashinami fon Nejmana abo garvardskimi poslidovnimi mashinami Poslidovni obmezhennya paralelnogo vikonannya sho diktuyutsya zakonom Amdala takozh ne zastosovuyutsya takim zhe chinom tak yak dani zalezhnosti neyavno obroblyayutsya programovanim vuzlom z yednalnogo obladnannya i ne vinikaye niyakih poslidovnih krokiv v procesi upravlinnya visoko paralelnogo potoku danih Sistolichni masivi tomu nadzvichajno praktichni v oblasti shtuchnogo intelektu obrobki zobrazhen rozpiznavannya obraziv komp yuternogo zoru i inshih zadach Procesori Wavefront v cilomu takozh mozhut buti duzhe horoshimi v mashinnomu navchanni shlyahom vprovadzhennya nalashtuvannya nejronnih merezh na aparatnomu rivni Klasifikacijna diskusiyaU toj chas yak sistolichni masivi oficijno klasifikuyutsya yak MISD cya klasifikaciya desho problematichna Oskilki vvid danih zazvichaj yavlyaye soboyu vektor nezalezhnih znachen sistolichnij masiv bezumovno ne SISD Tak yak ci vhidni znachennya ob yednuyutsya i kombinuyutsya v rezultat s i ne zberigayut svoyu nezalezhnist na vidminu vid bloku vektornoyi obrobki SIMD masiv ne mozhe buti rozcinenij yak takij Otzhe masiv ne mozhe buti klasifikovanij yak MIMD tak yak MIMD mozhna rozglyadati yak prosto kolekciyu menshih SISD i SIMD mashin Nareshti oskilki dani royu transformuyutsya koli voni prohodyat cherez masiv vid vuzla do vuzla mnozhinni vuzli ne pracyuyut na odnih i tih zhe danih sho robit viznachennya MISD klasifikaciyi nekorektnim Insha prichina chomu sistolichnij masiv ne povinen kvalifikuvatis yak MISD taka sho vidriznyaye jogo vid SISD kategoriyi Vhidni dani zazvichaj predstavlyayut soboyu vektor ne odnogo znachennya danih hocha mozhna bulo b stverdzhuvati sho bud yakij vhidnij vektor yavlyaye soboyu odin nabir danih Nezvazhayuchi na vse visheskazane sistolichni masivi chasto proponuyutsya yak klasichnij priklad MISD arhitekturi yak v pidruchnikah po paralelnih obchislennyah tak i v inzhenernomu klasi Yaksho masiv rozglyadayetsya z zovnishnogo boku yak atomarna operaciya to mozhlivo jogo klasifikuvati yak SFMuDMeR Odnofunkcionalni Single Function Bagatorazovi dani Multiple Data Ob yednani v rezultat s Merged Result Detalnij opisSistolichnij masiv skladayetsya z matric tipu ryadiv blokiv obrobki danih zvanih datchikami Bloki obrobki danih analogichni centralnim procesoram CPU okrim dlya situaciyi zvichajnoyi vidsutnosti lichilnika programi koli operaciya transportno spracovuye tobto pislya pributtya ob yekta danih Kozhna klitinka dilitsya informaciyeyu zi svoyimi susidami vidrazu pislya obrobki Sistolichnij masiv chasto pryamokutnoyi formi de potik danih prohodit cherez ves masiv mizh susidnimi blokami obrobki danih chasto z riznim potokom danih v riznih napryamkah Potoki danih sho nadhodyat i vihodyat z portiv masivu generuyutsya blokami pam yati avtomatichnogo sekvenuvannya ASMs auto sequencing memory units Kozhen blok ASM vklyuchaye v sebe dani lichilnika U vbudovanih sistemah potik danih mozhe buti takozh vvedenij i abo vihoditi do zovnishnogo dzherela Prikladom sistolichnogo algoritmu mozhe buti matrichne mnozhennya Odna matricya podayetsya v ryad z verhnoyi chastini masivu i peredayetsya vniz po masivu insha matricya podayetsya v kolonku v cej zhe chas z livogo boku masivu i prohodit zliva napravo Fiktivni znachennya potim peredayutsya v procesor poki kozhen ne pobachiv odin cilij ryad i odnu cilu kolonku Na danij moment rezultat mnozhennya zberigayetsya v masivi i v danij chas mozhut buti vivedeni ryadok abo stovpec Sistolichni masivi ce masivi blokiv obrobki danih yaki pidklyucheni do kilkoh najblizhchih susidiv bloku obrobki danih v sitchastij topologiyi Bloki obrobki danih vikonuyut poslidovnist operacij nad danimi sho peredayutsya mizh nimi Tak yak tradicijni metodi sintezu sistolichnogo masivu praktikuvalisya algebrayichnimi algoritmami mozhut buti otrimani tilki unifikovani masivi z tilki linijnimi trubami tak sho arhitektura odnakova u vsih blokah obrobki danih Naslidkom cogo ye te sho tilki programi z regulyarnoyu zalezhnistyu danih mozhut buti realizovani na klasichnih sistolichnih masivah Yak SIMD mashini sistolichni masivi z taktovoyu chastotoyu zamknuto poshagovo obchislyuyutsya z kozhnim procesorom beruchi alternativni obchislyuvannya zv yazok faz Ale sistolichni masivi z asinhronnim zv yazkom mizh blokami obrobki danih nazivayutsya masivami hvilovogo frontu Odin dobre vidomij sistolichnij masiv ce iWarp procesor Universitetu Karnegi Mellon yakij buv vigotovlenij virobnikom Intel Sistema iWarp maye linijnij matrichnij procesor z yednanij z shinami danih sho jdut v oboh napryamkah IstoriyaSistolichni masivi lt procesoriv hvilovogo frontu buli vpershe opisani Kungom i Lejzersonom yaki opublikuvali pershij dokument sho opisuye sistolichni masivi v 1978 r Prote persha mashina yaka vikoristovuvala podibnu tehniku bula Kolos Mark II v 1944 roci Priklad zastosuvannyaPolinomialna ocinka Shema Gornera dlya obchislennya bagatochlena y a n x a n 1 x a n 2 x a n 3 x a 1 x a 0 displaystyle y a n cdot x a n 1 cdot x a n 2 cdot x a n 3 cdot x a 1 cdot x a 0 Linijnij sistolichnij masiv v yakomu procesori roztashovani poparno odin primnozhuye jogo vhid na h i peredaye rezultat vpravo nastupnij dodaye a j displaystyle a j i peredaye rezultat dali Perevagi ta nedolikiPlyusi Shvidkij Masshtabnij Minusi Dorogij Ne shiroko zastosovuyetsya Obmezhenij bazovij kod program i algoritmiv Vuzkospecializovanij chasto vigotovlenij na zamovlennya obladnannya konkretnogo dodatka RealizaciyiCisco PXF merezhevij procesor vnutrishno organizovanij yak sistolichnij masiv Div takozhMISD Multiple Instruction Single Data Priklad sistolichnij masiv Spisok literaturiCilker B Ya Organizaciya EOM ta sistem Pidruchnik dlya vuziv B Ya Cilker S A Orlov 2 e vid SPb Piter 2011 688 s ISBN 978 5 49807 862 5 N Petkov Sistolichna paralelna obrobka Pivnichna Gollandiya 1992 PosilannyaInstruction Systolic Array ISA A VLSI Architecture for Image Registration in Real Time Based on systolic array Vol 15 September 2007