Асоціативні процесори.
Пристрій
Керування
Регістр
Даних
Регістр
Маски
Пам’ять
Регістри
результату
поушуку
Регістри
вибірки
слів
Пристрій
обробки
логічних
„і/або”
ариф. оп
Пристрій
дозволу
множиних
відліків
Ввід/Вивід
Це процесор який визначається як пристрій обробки даних у якому дані зберігаються, зчитуються та обробляються без точної адресації їх розташування у пам’яті.





Цей ОКМД процесор побудований на базі асоціативного пристрою пам’яті. Пристрій пам’яті створений з асоціативних комірок пам’яті. Дані можуть бути співставлені по деяким критеріям (= ,<=,>=) з інформацією яка зберігається в пам’яті. Для цього використовуються наступні дії:
запис даних в регістр даних
виділення розрядів які підлягають порівнянні з використанням регістру маски.
запис бітового набору, який описує підмножину даних у файлі, що відшукуються в регістр вибірки слів.
Результатом порівняння буде бітовий набір у регістрі результатів пошуку, який забезпечений покажчиком (вказівником) на перше слово, яке відгукнулося. Цей покажчик називається пристрій дозволу множинних відліків. Він вказує на саме „верхнє слово” яке задовольняє критерій пошуку. Тобто на самий верхній біт регістру результату пошуку.
Комірка асоціативної пам’яті є основним елементом на основі якого будується система. При необхідності АП може бути створена без використання спеціалізованих пристроїв. Але за виконання функцій АП буде знижена швидкодія.
Процесорне обладнання, яке забезпечує відповідну апаратурну підтримку повинен залучати, як мінімум, один повний послідовний арифметичний пристрій на кожне слово асоціативної пам’яті.
Дві основні відміни асоціативного процесора від звичайних паралельних містяться у звичайних типів пам’яті та у відсутності проц. зв.
Якщо розглядати асоціативний пристрій пам’яті, як пам’ять для збереження даних то АП мона буде назвати паралельним процесором. Але так, як і властивість асоціативності є дуже важливою, то АП розглядається як самостійний клас машин з ОКМД архітектурою.
Асоціативна обробка.
Концепція асоціативності не є нова. Асоціація може розглядатися як встановлення відповідності між об’єктами.
У своїй праці „О пам’яти и воспоминаниє” Арістотель визначив 3 види асоціацій:
За схожістю
За контрастом
За близькістю
Доповнення:
Асоціації ідеї
Асоціації по причині та наслідку
Найбільш загальні типи організації асоціативних процесів.
Загальна структура асоціативного процесора.
Ця архітектура має 4 регістри:
Даних
Маски
Результату пошуку
Вибірки слів
Також є пристрій:
Дозволу множинних збігів
Масиво-асоціативної пам’яті
Апаратних засобів обробки слів
Важливо виділити відсутність будь – яких пристроїв перетворення адреси.
Адресування даних у процесорі здійснюється за місцем або за будь – яким параметром пов’язаним із їх місцем.
Кожне слово пам’яті розбиті на розрядні групи змінної довжини, яке має назву поля. Поля не обов’язково мусять бути утворені з послідовно розміщених розрядів. Регістри даних і маски містять ту саму кількість розрядів, яку мають слова пам’яті. Регістри результату пошуку та вибірки слів містять по одному розряду на кожне слово пам’яті.
Бітовий зріз уявляє собою бітовий вектор, який утворений із і-го розряду з усіх вибраних слів, який не залежить від інших слів.
Приклади операцій АП які здійснюють:
Маскований пошук.
Різні види послідовно порозрядних операцій пошуку на нерівність.
Послідовно – порозрядні арифметичні операції над полями.
Послідовно – порозрядний пошук максимума/мінімума який дозволяє знаходити (максимальне/мінімальне) слово.
У асоціативних процесорів, орієнтованих на спеціалізованому застосуванні, окремі елементи базової архітектури представлені не явно. У механічній та у віртуальній пам’яті може бути відсутній регістр вибирання слів. Кожне слово пам’яті може знадобитися у будь – який момент часу.
Регістр маски може використовуватись за замовчуванням. Поля пошуку можуть бути відомі і передбачені заздалегідь. В деяких системах обробки даних, може бути введена більша кількість регістрів. У системах управління існують 3 регістра, які вказують напрямок пошуку слів (x,y,z).
Пристрій управління може бути як простим так і складним. В складному варіанті пристрій керування залучає в комп’ютері мікросеквенсор це пристрій, який визначає порядок виконання операцій на рівні розрядів.
Асоціативний процесор працює з 8 – ма словами та 4 – ма 3 – ох бітовими полями.
В регістр даних записуємо слово, яке необхідно порівняти із змістом пам’яті. Регістр маски вказує ті розряди шуканих слів, які повинні бути залучені у операції пошуку. У регістр результатів записаний результат пошуку. Регістр вибирання слів вибирає слово, яке приймає участь у пошуку.
У даному нашому прикладі слово 7, яке необхідно порівняти, як показує вміст регістру вибірки слів не увійшло в число тих, що вибрали. Вміст регістру маски показує, що у пошуку приймає участь вміст першого поля регістру даних.
У процесі виконання операції АП, а саме пошуку на рівність буде виконане порівняння першого пошуку із вмісту відповідних полів, що вибрані. З таких слів, тільки слова 3 та 6 задовільняють умові пошуку, ці слова після завершення пошуку відмічені 1 в регістрі результату. Слово 7 також повинно було задовільнити умову пошуку. Але вміст регістру вибірки слів показує, що воно не увійшло у набір слів для участі операції порівняння .
У багатьох АП за операцією пошуку повинна слідувати операція зчитування. Слова, що ідентифікуються, зчитуються послідовно. Існують інші операції пошуку. Вміст регістра результатів може бути переписаний у регістр вибірки слів, для того, щоб результат можна було використати в якості нового вмісту регістру вибірки слів. Може бути вміщена серія результатів пошуку, результат яких логічно об’єднаний, тобто дані які знаходяться в регістрі результатів пошуку логічно перемножуються із вмістом регістру вибірки слів, що формують новий вміст останнього.
Число вбудованих логічних функцій може бути великою. У системі АП присутній пристрій дозволу множинних збігів, або спів падань. На мал..АП він показаний стрілкою.
Якщо результат пошуку отримали відгуки від декількох слів, то ДМЗ вказує на 1-ий відлік, або на інакше на саме верхнє слово для якого виконується умова пошуку.
Для АП розробляються багато режимні пристрої пам’яті.
МАТРИЧНІ ПРОЦЕСОРИ.
Загальні властивості матричних процесорів.
Матричні процесори є ЕОМ типу ОКМД (SIMD) з одним потоком команд та множиною даних. Всі вони мають ряд загальних властивостей:
Організація на принципах архітектури ОКМД.
Високо синхронізація виконання.
Наявність великого числа простих процесорів, та з’єднувальної мережі.
Вимога високої швидкодії обміну даних.
Базова матрична архітектура типу ОКМД.
Типовий матричний процесор складається із скалярної послідовної частини і паралельного масиву процесорних елементів.
Для більшості задач зустрічаються дані скалярного типу (аргументи та параметри), та данні паралельного типу (вектори,матриці,таблиці,файли записів, які містять елементи з однаковими форматами. ) Природньо, що данні скалярного типу розміщуються та обробляються у послідовній частині процесора а дані паралельного типу у паралельному масиві процесора.
Послідовна частина процесора керує усією машиною, оскільки вміщує програму і узгоджує виконання скалярнихта векторних обчислень. Частина процесора, яка містить послідовний пристрій керування є посуті звичайною ЕОМ. При послідовному керуванні мусить існуваити або відрізнятися три множини команд:
Множина команд керування послідовною частиною процесора
Множина команд керування паралельними ПЕ
Множина команд керування потоком команд даних між обома компонентами матричного процесора
Перші 2 множини містять звичайні команди послідовної ЕРМ (зчитування запис регістра, порівняння та інші)
Перша множина містить також звичайні команди керування такіяк умовні та без умовні переходи.
Друга множина не містить команд переходів, які здатні внести зміни у порядок виконання команд, напроти, умовне виконання 2 м-ни команд керуються локально кожним процесорним елементом матриці процесора в залежності від стану його данних.
Пристрій послідовного керування видає команду, визначає її приналежність до тої чи іншої множини команд, якою займається і якщо команда є послідовною то виконує її. У випадку, якщо команда є матричною то послідовний пристрій керування передає її всім ПЕ, що виконують її паралельно.
Для команд 3-го типу пристрій послідовного керування та матричний процесор узгоджує виконання команд.
Множина команд 3-го типу керує обміном даними між скалярними та векторними частинами процесора. Вона містить команди, які змінюють потік видачі команд у послідовній частині в залежності від результату отриманих в паралельних частинах.
В 3 частині містяться команди, що дозволяють виділити окремі процесорні елементи і переносити їх вміст у послідовну частину.
Таким чином якщо багато ПЕ і тільки один потік команд, то у кожен момент часу можливі обмін лише 1-го процесорного елемента з пристроєм керування. З іншого боку за допомогою однієї послідовності команд можна представити загальні дані усім ПЕ паралельно. Важливо особливий режим роботи МП є виконання умовних переходіву залежності від стану усіх процесорів.
В загальному випадку послідовний контролер посилає послідовність команд в паралельний процесор, а логічний результат кожної окремої взятої операції яка обчислює на паралельному процесорі розміщення у спеціальні регістри, які є у кожному ПЕ.
Спеціальні команди з множини команд керування потоком та аппаратура дають можливість зчитувати(опитування) спеціальні регістри. Це опитування (зчитування) виконується паралельно. Отримуємо ознаки готовності. Ці ознаки можуть далі аналізуватися. Такі команди забезпечують послідовність керування з можливістю одного опитування усіх ПЕ. У результаті пошук виконуються за квазі постійний час.
Нехай c- постійний час; n-число елементів даних; p-число ПЕ;
Тоді час пошуку n елементів дорівнює c при n<=p
2c p<n<=2p; n*c при(m-1)p < n<=m*p
Оскільки р достатньо величина у порівнянні з n (числом елементарн даних), то для пошуку потрібн олише декілька операцій причому, пошук буде дуже ефективний.
Якщо навпаки n>>pnj то дані можна розбити на впорядковані купи причому в кожному вузлі дані є не впорядкован, а обмін даних між вузлами впорядкований за купами.
Шляхом такоїорганізації даних можна здійснювати ефективний пошук у випадку дуже великого обсягу даних.
Крім команд відкриту за запитаннями в деякій МП маємо спеціал ком, що дозволяє вибрати ПЕ з декількох які відкликаються за один крок . Після такого вибору відкрив доступ до пам’яті відповідного ПЕ і є можливі переходи відносно даних у послідовному контролері.
Після виконання переносу ПЕ звільняється і можна вибирати наступний ПЕ. У результаті досягнуто можливі формувачі ітерац. цикл не за допомогою лічильника або індексації а за допомогою окремих даних, що обробляється. При паралельній обробці великих обсягів імовірна ситуація, коли не надусіма елементами мусять виконуватися однакові операці.
В цьому режимі послідовний пристрій керування передається по суті програмі повністю усім ПЕ.
Окремі ПЕ обслуговують всю програму для своїх даних вибірки виконання послідовних команд.
Якщо регістр маски або контекстний регістр у ПЕ знаходяться в стані 1, то команда виконується, а якщо в стані 0 то ігнорує.
ПЕ виконує декілька команд керування незалежно від стану регістра маски.
ПЕ можуть встановлювати стани регістра маски в залежності від своїх локальних даних. Таким чином виконання на рівні ПЕ може повністю визначатися даними.
Слід відзначити, що більшість МП має додаткові рівні керування, наприклад, якщо послідовне керування здійснюється за допомогою стандартної ЕОМ, то це звичайно не дозвол модифікацій для виконання команд 2-го і 3-го типу.
Синхронні операції.
Розпаралелення в матричному процесорі здійснюється на мікрорівні, тому шо для організації його роботи потрібна жорстка синхронізація виконання операцій. Інтерфейс між послідовним керуванням та мтричнимпроцесором має бути синхронним прийнаймні до рівня операцій другого типу. Це означає що після видачі команди послідовний пристрій на матричний процесор посилає пристр. Кер. Запит і може працювати лише після отримання відплвіді.
На практиці в деяких схемах забезпечується буферизація між послідовним керуванням і операціями на мтричному процесорі.
В цьому випадку після передачі команди на матричний процесор послідовний пристрій може не зупиняти роботи, а знаходи параметри і адреси для наступних параметрів команд.
Але можливість такого паралельного режиму роботи послідовного пристрою керування і МП дуже обмежена, бо ПК потрібні значення деякого параметру, що познач. МП, тому для продовження роботи він змушений чекати завкршення попередньої виданої матр. ком.
У середині матричного процесору мусить бути строга покрокова синхронізація. Матричний контролер передає сигнали керування синхронізації усім паралельним процесорам. Цей рівень синхронізації використовується для забезпечення високої швидкодії.
Широко використовується метод розгалуження процесорів у вигляді одно або дво-вимірної сітки, і наступного з’єднання з найвищих процесорних елементів.
Завдяки паралельності та високого ступеня синхронізації обміну такі сітки є дуже ефективними. Наприклад, на МП команди перересилки даних ”вліво” всім процесорам передають команди пересилки даним наліво. Це призводить до одночасної пересилки данних ПЕ на ліво тпа отримання ними данних справ.
Регулярність та синхронність комутаційної мережі призводить до відсутності непродуктивних розходів на зв’язок. Не потрібно обчислювати шляхи в мережі та адреси, приймаючи ПЕ.
Процес комутації зводиться до 3 операцій:
Отримання даних в пам’яті.
Пересилання даних сусідньому ПЕ і від сусіднього ПЕ з іншої сторони.
Розміщення даних в пам’яті.
Треба підкреслити, що високі швидкодії обміну даних можливі лише між сусідніми ПЕ. На передачу між віддаленими ПЕ вимагається більше часу.
Але є один загальний для всіх конфігурацій режим (між процесорної комутації) і зветься він механізм циркулярної передачі через послідовний контролер. Якщо вимагається переслати значення змінної з одного ПЕ на більше число інших ПЕ, або на декількох випадково розподілених і достатньо віддалених ПЕ то іноді буває ефективніше передати сигнал на послідовний контроль, а потім прислати його звідси на всі ПЕ. На відповідні ПЕ встановлені також регістри маски, а на всі інші ПЕ маски відключаються.
Кутовий поворот
Порозрядне виконання команд на ПЕ призводить до ускладнення формату представлення даних, по скільки домінують звичайні послідовні ЕОМ, то ми програмуємо з врахуванням послідовної ідеології, тобто послідовні алгоритми. Це означає, що більша частина даних поступає в послідовній формі з паралельними розрядами. А для роботи з порозрядними процесорами вимагається організація даних у порозрядному представлені з паралельними словами. Процес перетворення таких форматів називаємо кутовим поворотом.
Двох вимірний кутовий поворот:
Послідовний. Послідовне уявлення з паралельними розрядами.
Порозрядний. Порозрядна організація даних з паралельними словами, яка необхідна для роботи порозрядних асоціативних процесорів.
Суміщений. Приклад перекриття цих двох видів орг. і зберігання даних.
У всіх матричних процесорах, ця реорганізація даних виконується схемними засобами, типовими організаціями перетворення з послідовними операціями в порозрядних з операціями зчитування n (на прикладі 2048 слів) по m (на пр 3 розрядів) з посл ЕОМ і з допомогою паралельно послідовного доступу з наступним записом записом m n для порозрядного доступу.
Маємо і зворотню операцію, яка перетворює порозрядне представлення у послідовне представлення.

Закон АМДАЛЯ:
Продуктивність КС, яка складається із зв’язаних між собою пристроїв в загальноиу випадку визначається як найбільш непродуктивним.
Нехай КС створена із S однакових простих універсальних пристроїв. Нехай припустимо, що при виконанні паралельної частини алгоритму всі S пристроїв завантажені повністю. Тоді максимально можливе прискорення EMBED Equation.3 ,де EMBED Equation.3 – коефіцієнт, тобто частка послідовних обчислень.
Припустимо, що по якихось причинах n-викон послідовно, N загальна кількість
операцій.
Нехай система створена із простих однакових універсальних пристроїв, при будь-якому режимі роботи її прискорення не може перебільшувати зворотньої величини часткі послідовних обчислень.
Якщо послідовно виконуються m операцій, то число ярусів будь-якої паралельної форми алгоритму, не може бути менше n.
В дослідженнях по закону Амдаля не конкретизується зміст операцій. В загальному випадку вони можуть бути як елементарними так і дуже складними, які уявлябть алгоритм розв’язку достатньо складних задач. КС із великою кількісттю процесорів мусять бути завантажені достатньо богато, в іншому випадку немає смислу їх створювати. Дослідження показали, що в паралельних системах доля послідовних операцій мусять бути порядка десятих і сотих процента.
Системи класу МКМД.
В системі МКМД є два класи:
Комп’ютери із загальною пам’яттю.(Мультипроцесорні системи)
Комп’ютер із розподіленою пам’яттю.(Багатомашинні системи)
Ці два класи мають свої переваги, які плавно переходять в недоліки.
Для Кс з загальною пам’яттю легше створити паралельні програми, але їхня максимальна продуктивність дуже обмежена з невеликою кількістю.
Для того щоб об’єднати досягнення цих двох класів є проектування комп’ютерів з архітектурою NUMA – Non Uniform Memory Access (нерівномірний доступ до пам’яті).
Ця архітектура є досить розповсюдженою і на її шляху досить неочікувано з’явилась перепона. Кеш-пам’ять, яка дозволяє значно прискорити роботу окремих процесорів, для багато прцесорних систем, створило складності. В перших комп’ютерах NUMA не жуло кеш-пам’яті і не було подібної проблеми. Але в сучасних комп’ютерах з’явився кеш-пам’ять.
Нехай процесор Р1 зберігає значення х в комірці U а далі процесор Р2 хоче прочитати зміст тої самої комірки U. Що буде в Р2?
Нам треба знайти Х, але які Р2 отримав Х, якщо Х попав в кеш Р1 процесора.
Ця проблема має назву – “проблема узгодження змісту кеш-пам’яті” (Cashe cogerence problem)
CcNUMA
Для вирішення даної проблеми була розроблена спеціальна модифікація NUMA архітектура сс NUMA. На основі цієї архітектури поширюються можливості традиційних комп’ютерів загальної пам’яті. Причому, якщо конфігурація SMP сервер має 16-32-64 процесори, то сс NUMA дає можливість об’єднати 256 та більше процесорів.
В цих системах крім декількох процесорів в одному примірнику: 1 пам’ять, 1 ОС, 1 система інтерфейсу вводу виводу. Слово симетричний означає, що кожен процесор може робити все те, що може інша.
В ссNUMA арх. пам’ять всього комп’ютера фізично розподілена, що значно підвищує потенціал його масштабованості, але пам’ять логічно залишиться загальною, це дає можливість використання всіх технологій та методів програмування SMP. Зміст кеш-пам’яті на рівні процесорів узгоджується з ОП.
Значно збільшується число процесорів у порівнянні з класом архітектури. В цій архітектурі час звертання до пам’яті залежить від того чи є це звертання до локальної або віддаленої пам’яті.
Процес написання програми залишається тим самим і фізично розподіл пам’яті у програмі не бачить. На базі Київ стар стоїть суперкомп’ютер HP Superdome 2000р.
В стандартній конфігурації об’єднуються від двох до 64-х процесорів з можливим подальшим розширенням системи. Всі процесори мають доступ до загальної пам’яті орг. Відповідно в системі це означає що:
Всі процесори можуть працювати в єдиному адресному просторі адресуючи будь-який байт в пам’яті за допомогою звичайних операцій читання \ запису.
Доступ до локальної пам’яті буде іти трохи швидше ніж доступ до віддаленої пам’яті.
Проблеми з можливою невідповідністю даних викликаються на рівні..
Максимальні конфігурації може мати 256 Гбайт ОП.
Найближчі плани HP нарощувати оперативну пам’ять до одного Тбайт.
Основною архітектурою HP SUPERDOME являє собою обчислювальні комірки (сells), пов’язана ієрархічно системою перемикачів. Кожна комірка є симетричним мульти процесором, який реалізований на одній платі (мікропроцесорів до 4-х штук, ОП до 16Гбайт, контролер комірки, перетворення живлення, система вводу\виводу).
Архітектура комп’ютера спроектована так що в неї може використовуватись декілька типів мікропроцесорів. Система повністю підготовлена для використання процесорів наступного покоління. При заміні існуючих процесорів Itanium гарантується двійкова система додатків на системному рівні.
Центральне місце в архітектурі комірки HPSuperDome це контролер комірки. Контролер комірки це дуже складний пристрій, який має 24млн транзисторів. Для кожного процесора комірки є свій власний порт контролера. Обмінним данним є 2 Гб/сек Пам’ять комірки має ємність від 2 до 16 Гбайт. Конструктивно вона поділена на два банки, кожен з яких має свій порт в контролері комірки. З’єднання контролера комірки з контролером пристрою вводу\виводу встановлюється оптимально. Один порт контролера комірки завжди пов’язаний з зовнішнім комутатором. Зовнішній комутатор потрібний для обміну даних з іншими процесорами. Швидкість роботи порта 8Гбайт\с.
Контролер комірки виконує інтерфейс функції між процесором і пам’яттю, який крім цього відповідає і за когерентність кеш-пам’яті.
Комірка – це базовий 4-х процесорний блок. В 64 процесорах конфігурації SuperDome має дві стойки, в кожні з яких 32 процесора. Кожна стойка має по два 8-ми портових комутатора. Всі порти комутаторів процесора мають швидкість 8Гбайт\с. До кожного комутатора підключають 4 комірки: 3-порти комутатора задіяні для зв’язку з іншими комутаційними системами, і 1-що знаходиться в тій самій стойці, і 2- в іншій стойці. Останній порт зарезервований для зв’язку з іншими системами комп’ютера.
В комп’ютері можливі три види затримок, при звертанні процесора до пам’яті. Це є плата за високу маштабованість системи:
Процесор і пам’ять є в одній комірці
Процесор і пам’ять є в різних комірках, але ці комірки під’єнані до одного комутатора.
Процесор і пам’ять є в різних комірках, але обидві комірки під’днані до різних комутаторів.
Величина затримки залежить від к-сті прцесорів, а також від числа одночасно працюючих процесорів
В даному варіанті зявляються додаткові варіанти необхідні для підтримання когерентності кешу-памяті
В багато гілкових варіантах з’являються додаткові витрати необхідні для підтримки когерентності кеш-пам’яті. Коефіцієнт збільшення затримки при переході від 4-х до 64-х процесорних конфігурацій – збільшується в 1.6 рази. 4 арифметичних операцій за один такт виконує PA8700 (750Mhz).
Той процесор PA8700 має суперскалярну архітектуру. Процесор має 10 функціональних пристроїв : 4-з цілочисельною арифметикою і логікою, 4- для роботи з іншим варіантом арифметики, і 2 пристрої для операцій читання\запис.
На кожному такті пристрій вибірки комірки комп’ютера може зчитувати до 4 комірок із кожної кеш-пам’яті.
Об’єм пам’яті 2.25Мбайти з яких 1.5Мб кеш даних, 0.75 Мб –кеш команд. Вся кеш має 4 канали. Якщо в програмі 20% всіх операцій виконується строго послідовно, то прискорення більше ніж 5 отримати неможливо, незалежно від того яке число швидкості процесора.