Транзакційна пам'ять
Транзакційна пам'ять — один з підходів у реалізації рівночасних обчислень, при якому деякі групи load-store інструкцій виконуються атомарно. Даний механізм схожий на транзакції у базах даних, але застосований до операцій у спільній пам'яті.
Системи транзакційної пам'яті реалізують високорівневу абстракцію, на противагу низькорівневим примітивам синхронізації потоків виконання. Така абстракція дозволяє координувати рівночасні записи і зчитування спільних даних у паралельних обчислювальних системах.[1]
Рівночасне програмування потребує синхронізації у випадку, коли паралельні потоки виконання намагаються отримати доступ до спільного ресурсу. Така синхронізація досягається за допомогою спеціальних примітивів (як правило, низькорівневих), які є «песимістичними»[уточнити], і не дозволяють потокам за межами критичної секції робити будь-які зміни. До того ж, процес заволодіння (acquire) і звільнення (release) примітивів може спричиняти додатковий overhead[уточнити], особливо у випадках, коли конфліктів між потоками відносно небагато. Транзакційна пам'ять забезпечує optimistic concurrency control[en], дозволяючи потокам паралельно виконуватися з мінімальною інтерференцією.[2]
Метою системи транзакційної пам'яті є прозора підтримка регіонів коду, відмічених як «транзакції», шляхом обов'язкового застосування атомарності, узгодженості та ізоляції.
Транзакція — це набір дій, що виконуються і записують зміни до того, як станеться конфлікт. У випадку виявлення конфлікту транзакція повертається до свого початкового стану (тобто до того стану, коли не було зроблено ніяких змін), і запускається повторно, аж допоки всі конфлікти не буде усунено. Перед тим, як завершено комміт[en], порядок операцій усередині транзакції є довільним — це контрастує з методом синхронізації, заснованому на примітивах lock/unlock, де операції відбуваються послідовно. Таким чином, якщо модифікація спільних ресурсів відбувається нечасто, транзакції уможливлюють додатковий паралелізм. У транзакційному підході програміст не повинен явно вказувати критичні секції — як наслідок, програми з застосуванням транзакційної пам'яті не можуть призвести до взаємного блокування.[2]
Транзакційна пам'ять спрощує паралельне програмування, виділяючи групи інструкцій у атомарні транзакції. Конкурентні потоки працюють паралельно, поки не починають змінювати одну і ту ж ділянку пам'яті. Лише останнім часом почали з'являтися апаратні реалізації транзакційної пам'яті.
Мікропроцесор Rock від компанії Sun Microsystems був першим мікропроцесором з апаратною підтримкою транзакційної пам'яті. 64-розрядний процесор архітектури SPARC v9 мав 16 ядер.
У 2007 компанія оголосила про підтримку технології. Для функціонування транзакційної пам'яті були додані дві нові інструкції chkpt і commit і один новий статусний регістр cps. Інструкція chkpt <fail_pc> використовувалася для початку транзакції, а інструкція commit для її завершення. При скасуванні транзакції відбувався перехід на <fail_pc>, в цей час можна було перевірити регістр cps для визначення причини скасування. Транзакції переривалися з причин конфліктів даних, промахів TLB, переривань, складних інструкцій. Тим не менш, у багатьох випадках використання транзакційної пам'яті в процесорі Rock давало переваги в синхронізації.
У 2008 інженери Sun представили інтерфейс транзакційної пам'яті і симулятор Adaptive Transactional Memory Test Platform. Після покупки компанії Sun корпорацією Oracle проект Rock був закритий: «Цей процесор мав дві приголомшливі властивості: він був неймовірно повільним і споживав величезну кількість енергії. Він був настільки гарячим, що їм довелося поставити зверху 12 дюймів охолоджуючих вентиляторів, щоб процесор не перегрівався. Було б божевіллям продовжувати цей проект.»
Суперкомп'ютер Sequoia з архітектурою BlueGene/Q став першою комерційною системою з апаратною підтримкою транзакційної пам'яті. Технологія працює в 32-мегабайтному кеші другого рівня процесора PowerPC A2 (PowerPC BQC 16C). Дані в кеші мають позначку "версія", і кеш здатний зберігати кілька версій одних і тих же даних.
Програма повідомляє процесору про початок транзакції, робить свою роботу і повідомляє, що потрібно завершити транзакцію (commit). У разі якщо інші потоки змінювали ті ж дані — створюючи версії — кеш відхиляє транзакцію і потік намагається провести її знову. Якщо інших версій даних не з'явилося, дані модифікуються і транзакція завершується успішно.
Технологія версійних міток в PowerPC A2 також використовується для спекулятивного виконання. Замість очікування нової версії потік даних може виконати обчислення з наявними даними, спекулятивно здійснюючи корисну роботу. Якщо дані були такими ж, як і після оновлення, потік завершує (commit) роботу з кешу. Продуктивність вища: потік виконав роботу до отримання фінального значення. В іншому випадку результати спекулятивної роботи відхиляються і потік виробляє обчислення з коректними значеннями.
Підтримка транзакційної пам'яті — в деякому роді логічне розширення можливості, давно присутня в процесорах PowerPC — "load-link/store-conditional", або LL/SC. LL/SC — примітивна операція, яка може використовуватися як будівельний блок для всіх потокобезпечних конструкцій. Перша частина LL/SC — load-link — використовується програмою для отримання даних з пам'яті. Далі потік змінює дані і записує їх назад в пам'ять з допомогою store-conditional. Команда завершується успішно, якщо дані не змінювались. В іншому випадку програма повторює дії з даними спочатку.
Транзакційна пам'ять — LL/SC на стероїдах: потоки виконують операції LL на безлічі різних областей пам'яті, а операція завершення транзакції атомарно змінює всі області пам'яті або скасовує транзакцію (SC).
Ruud Haring, який представив роботу IBM по транзакційній пам'яті на Hot Chips, зізнався, що при реалізації компанія зіткнулася з безліччю нетривіальних проблем. При всій складності, реалізація має обмеження: вона не надає міжпроцесорної підтримки транзакцій. Проблема не актуальна для Sequoia і в той же час дозволяє оцінити виграш від використання транзакційної пам'яті.
Контролери пам'яті Power 8 підтримують транзакційну пам'ять. Підтримка технології в ядрі Linux з'явилася починаючи з версії ядра 3.9.
У 2012 компанія Intel оголосила про введення розширень транзакційної синхронізації (Transactional Syncrhonization Extensions, TSX) в набір інструкцій x86. Розширення дозволяють програмістам позначати окремі ділянки коду як транзакції. У 2013 з виходом покоління процесорів Haswell апаратна підтримка транзакційної пам'яті вперше стає доступною на споживчому рівні.
Haswell управляє наборами читання і запису з гранулярністю лінії кешу, відстежуючи адреси кешу даних L1. Конфлікти визначаються за допомогою протоколу когерентності кешу. TSX складається з двох частин. Апаратне виключення блокувань (Hardware Lock Elision, HLE) надає просту конвертацію програм на основі блокувань в транзакційні програми, причому отримані програми будуть попередньо сумісні з існуючими процесорами. Обмежена транзакційна пам'ять (Restricted Transactional Memory, RTM) є більш повною реалізацією транзакційної пам'яті.
HLE злегка модифікує інструкції для зміни ділянки пам'яті. Технологія додає префікси — інструкції, не виробляють будь-яких дій, але змінюють інтерпретацію наступної інструкції — для модифікації інструкцій взяття та звільнення блокування (XACQUIRE і XRELEASE відповідно).
Між взяттям і звільненням блокування процесор відстежує ділянки пам'яті, які читають і записують потоки. У випадку конфлікту — якщо два потоки модифікують одні дані, або один потік читає дані, які інший записує — процесор скасовує транзакцію при звільненні блокування. В іншому випадку, виконання триває нормально.
Таким чином, HLE дозволяє загальноприйнятому коду на основі блокувань працювати оптимістично. Кожен потік буде вважати, що отримав блокування, в той час як інші потоки можуть працювати одночасно. До тих пір поки це безпечно, транзакції не скасовуються.
Технологія попередньо сумісна з процесорами без підтримки HTM. Операції з управління блокуванням залишаються, але зі спеціальним префіксом. Процесори Haswell будуть враховувати префікс і використовувати транзакційні виконання замість маніпуляцій з блокуваннями. Будь-який інший процесор буде ігнорувати префікс і просто керувати блокуванням, використовуючи традиційну поведінку на основі блокувань. Інструкції XACQUIRE і XRELEASE вже існують, але не несуть будь-якого сенсу, поки не використовуються зі специфічними інструкціями.
HLE дозволяє писати програми та операційні системи, які будуть використовувати транзакції на Haswell, підвищуючи рівень паралелізму без блокувань. Код буде працювати коректно на поточних процесорах. У результаті, введення нової можливості буде простим і безпечним.
RTM вимагає більших зусиль: він відходить від зворотної сумісності та запроваджує три нові інструкції. У той час як HLE неявно використовують транзакції, дозволяючи коду на основі блокувань працювати паралельно, RTM робить початок, завершення і переривання транзакцій явними. Потік починає транзакцію інструкцією XBEGIN, надаючи "запасну" функцію, яка запускається в разі переривання транзакції. Транзакція завершується інструкцією XEND, при цьому процесор проводить транзакцію якщо не було конфліктів або перериває її, переходячи в запасну функцію. Транзакції явно перериваються в програмі інструкцією XABORT. Завдяки явному використанні границь і "запасному виходу", RTM дозволяє контролювати транзакції повніше, ніж HLE. У довгостроковій перспективі RTM спростить реалізацію можливостей транзакцій.
- ↑ Harris, Tim; Larus, James; Rajwar, Ravi (2 червня 2010). Transactional Memory, 2nd edition. Synthesis Lectures on Computer Architecture (англ.). 5 (1): 1—263. doi:10.2200/S00272ED1V01Y201006CAC011. ISSN 1935-3235.
- ↑ а б Transactional Memory: History and Development. Kukuruku Hub (англ.). Процитовано 16 листопада 2016.
- Clojure STM — What? Why? How? [Архівовано 11 листопада 2016 у Wayback Machine.]
- Software transactional memory [Архівовано 30 червня 2016 у Wayback Machine.]
- Software Transactional Memory in GCC
- Sequoia — BlueGene/Q, Power BQC 16C 1.60 GHz, Custom [Архівовано 25 травня 2016 у Wayback Machine.]
- IBM’s new transactional memory: make-or-break time for multithreaded revolution [Архівовано 29 травня 2016 у Wayback Machine.]
- IBM Sequoia named world's fastest supercomputer
- Intel's Haswell brings transactional memory tech
- Transactional memory going mainstream with Intel Haswell [Архівовано 28 травня 2016 у Wayback Machine.]