Оборотні обчислення

Оборотні обчислення - це модель обчислень, де обчислювальний процес певною мірою є оборотним у часі. У моделі обчислень, яка використовує детерміновані переходи від одного стану абстрактної машини до іншого, необхідною умовою оборотності є те, що відношення відображення з станів (з ненульовою імовірністю) до їх наступників має бути один до одного. Оборотні обчислення - це форма нетрадиційних обчислень.

Оборотність

Існують два основних, тісно пов’язаних типи оборотності, які представляють для інтерес: фізична оборотність та логічна оборотність.

Процес називається "фізично оборотним", якщо він не призводить до збільшення фізичної ентропії; тобто є ізоентропійним . Існує підхід до конструювання схеми, який ідеально демонструє цю властивість, яка називається логікою з відновленням заряду, адіабатичною схемою або адіабатичною обчислювальною технікою . Хоча на практиці жоден нестаціонарний фізичний процес не може бути точно фізично оборотним або ізоентропійним, не існує відомої межі близькості, з якою ми можемо наблизитися до ідеальної оборотності, в системах, які досить добре ізольовані від взаємодії з невідомим зовнішнім середовищем, і коли закони фізики, що описують еволюцію системи, точно відомі.

Ймовірно, найбільшою мотивацією для вивчення технологій, спрямованих на фактичну реалізацію оборотних обчислень, є те, що вони пропонують, як передбачається, єдиний потенційний спосіб поліпшити обчислювальну енергоефективність комп’ютерів за межі фундаментальної межі Неймана – Ландауера енергії kT ln (2), що розсіюється за незворотну бітову операцію. Хоча межа Ландауера була у мільйони разів нижче енергоспоживання комп’ютерів у 2000-х і в тисячі разів менше у 2010-х, прихильники реверсивних обчислень стверджують, що це може бути пов'язано здебільшого з архітектурними накладними витратами, які ефективно посилюють вплив межі Ландауера на практичні схеми конструкцій, так що може виявитись що практичним технологіям важко просуватись далеко за межі сучасних рівнів енергоефективності без використання принципів оборотних обчислень.

Відношення до термодинаміки

Як вперше аргументував Рольф Ландауер з IBM, для того, щоб обчислювальний процес був фізично оборотним, він також повинен бути логічно оборотним. Принцип Ландауера - це суворо обґрунтоване твердження, що беззмістовне стирання n бітів відомої інформації завжди повинно збільшити термодинамічну ентропію на ${\displaystyle nk_{B}T{\text{ln}}2}$. Дискретний, детермінований обчислювальний процес називається логічно оборотним, якщо перехідною функцією, яка відображає старі обчислювальні стани в нові, є функція "один до одного"; тобто вихідні логічні стани однозначно визначають вхідні логічні стани обчислювальної операції.

Для недетермінованих обчислювальних процесів (у тому сенсі, що вони імовірнісні чи випадкові), зв'язок між старими та новими станами не є однозначною функцією, і вимога, необхідна для отримання фізичної оборотності, стає дещо слабшою умовою, а саме, що розмір даного набору можливих початкових обчислювальних станів в середньому не зменшується поки обчислення рухаються вперед.

Фізична оборотність

Принцип Ландауера (і справді, сам другий закон термодинаміки) також можна розуміти як прямий логічний наслідок оборотності фізики, як це відображено в загальному формулюванні гамільтонової механіки, а більш конкретно в унітарному операторі еволюції часу квантової механіки.

Таким чином, реалізація оборотних обчислень зводиться до того, щоб навчитися характеризувати та контролювати фізичну динаміку механізмів для виконання бажаних обчислювальних операцій настільки точно, що для кожної логічної операції, яка виконується, ми можемо накопичити незначну загальну кількість невизначеності щодо повного фізичного стану механізму. Іншими словами, нам потрібно було точно відстежувати стан активної енергії, яка бере участь у виконанні обчислювальних операцій в машині, і проектувати машину таким чином, щоб більша частина цієї енергії відновлювалася в організованій формі, яка може використовувати повторно для наступних операцій, а не дозволяти цій енергії розсіюватися у вигляді тепла.

Незважаючи на те, що досягнення цієї мети представляє значну проблему для проектування, виготовлення та характеристики надточних нових фізичних механізмів для обчислювальної техніки, в даний час немає жодних фундаментальних підстав думати, що ця мета не може бути врешті досягнута, що дозволяє нам коли-небудь побудувати комп’ютери, які генерують фізичну ентропію набагато менше 1 біта (і розсіюють набагато менше, ніж ${\displaystyle k_{B}T{\text{ln}}2}$ енергії для нагрівання) на кожну внутрішню корисну логічну операцію.

Сьогодні наявна значна кількість академічної літератури. Фізиками, інженерами з електроніки і інформатиками були розроблені та проаналізовані різноманітні концепції оборотних пристроїв, логічні елементи, електронні схеми, архітектури процесорів, мови програмування та програмні алгоритми.

Ця галузь досліджень чекає детальної розробки високоякісної, економічно вигідної, майже оборотної технології логічних пристроїв, яка включає високоенергоефективні механізми живлення по тактам та синхронізації, або дозволяє уникнути потреби в них завдяки асинхронному проектуванню. Такого роду суттєвий інженерний прогрес знадобиться до того, як велика кількість теоретичних досліджень оборотних обчислень зможе знайти практичне застосування для того, щоб реальні комп’ютерні технології могли обійти різні найближчі бар’єри на шляху її енергоефективності, включаючи межу фон Неймана – Ландауера. Її по причині другого закону термодинаміки можна обійти лише використанням логічно оборотних обчислень.

Логічна оборотність

Для реалізації оборотного обчислення, оцінки його вартості та судження про його межі його можна формалізувати в плані схем рівня логічного вентиля. Спрощена модель таких схем - це та, в якій приймаються входи (однак, слід зауважити, що реальні логічні вентилі, реалізовані, наприклад, у КМОН, цього не роблять). У цій структурі моделювання інвертора (логічного елемента НЕ) вентиль є оборотним, оскільки його можна скасувати. Елемент "виключне або" (XOR) незворотний, оскільки два його входи не можуть бути однозначно відновлені з його єдиного виходу. Однак оборотна версія логічного елемента XOR - контрольоване заперечення (CNOT) - може бути визначена шляхом збереження одного із входів. Варіант CNOT із трьома входами називається вентиль Тоффолі. Він зберігає два свої входи a, b і замінює третій c на ${\displaystyle c\oplus (a\cdot b)}$. З ${\displaystyle c=0}$, створюється кон'юнкція, а з ${\displaystyle a\cdot b=1}$ отримується функцію заперечення (NOT). Таким чином, вентиль Тоффолі є універсальним і може реалізовувати будь-які оборотні булеві функції (з урахуванням достатньої кількості нульових ініціалізованих допоміжних бітів). Більш загально, оборотні вентилі мають не більше входів, ніж виходів. Оборотна схема з'єднує оборотні вентилі без розгалужень і петель. Тому такі схеми містять однакову кількість вхідних і вихідних проводів, кожен з яких проходить через цілу схему. Подібним чином машина Тьюрінга стає оборотною машиною Тьюрінга, перехідна функція якої є реверсивною, так що кожен стан машини має щонайбільше одного попередника.

^[fr] запропонував оборотну машину Тьюрінга в статті 1963 року, але, мабуть, не знаючи принципу Ландауера, не продовжив займатися цією темою, присвятивши більшу частину своєї кар'єри етнолінгвістиці. У 1973 р. Чарльз Беннетт з IBM Research показав, що універсальну машину Тьюрінга можна зробити як логічно, так і термодинамічно оборотною, і, отже, в принципі можливо виконувати довільно великі обчислення на одиницю розсіяної фізичної енергії в межах нульової швидкості. У 1982 р. Едвард Фредкін і Томмазо Тоффолі запропонували ^[en], механізм, що використовує класичні тверді сфери, щоб робити оборотні обчислення з скінченною швидкістю з нульовим розсіюванням, але вимагаючи ідеального початкового вирівнювання траєкторії куль, і огляд Беннета порівняв ці "броунівські" та "балістичні" парадигми для оборотних обчислень. Окрім мотивації енергоефективних обчислень, оборотні логічні вентилі пропонують практичні вдосконалення бітових маніпуляцій в криптографії та комп’ютерній графіці. Починаючи з 1980-х років, оборотні схеми викликають інтерес як компоненти , а останнім часом у фотонних та нано-обчислювальних технологіях, де деякі комутаційні пристрої не пропонують посилення сигналу.

Доступні огляди оборотних схем, їх побудова та оптимізація, а також останні наукові завдання.

Примітки

1. . Архів оригіналу за 22 січня 2021. Процитовано 1 грудня 2020.
2. J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.
3. Bérut, Antoine; Arakelyan, Artak; Petrosyan, Artyom; Ciliberto, Sergio; Dillenschneider, Raoul; Lutz, Eric (March 2012). Experimental verification of Landauer's principle linking information and thermodynamics. Nature. 483 (7388): 187—189. Bibcode:2012Natur.483..187B. doi:10.1038/nature10872. PMID 22398556.
4. Michael P. Frank, "Foundations of Generalized Reversible Computing," to be published at the 9th Conference on Reversible Computation, Jul. 6-7, 2017, Kolkata, India. Preprint available at https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/grc-rc17-preprint2.pdf [ 20 березня 2021 у Wayback Machine.].
5. Landauer, R. (July 1961). Irreversibility and Heat Generation in the Computing Process. IBM Journal of Research and Development. 5 (3): 183—191. doi:10.1147/rd.53.0183.
6. Lecerf (Y.) : Logique Mathématique : Machines de Turing réversibles. Comptes rendus des séances de l'académie des sciences, 257:2597--2600, 1963.
7. C. H. Bennett, "Logical reversibility of computation [ 25 липня 2020 у Wayback Machine.]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525-532, 1973
8. Bennett, Charles H. (December 1982). The thermodynamics of computation—a review. International Journal of Theoretical Physics. 21 (12): 905—940. Bibcode:1982IJTP...21..905B. doi:10.1007/BF02084158.
9. Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf [ 15 травня 2021 у Wayback Machine.]
10. Saeedi, Mehdi; Markov, Igor L. (1 лютого 2013). Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys. 45 (2): 1—34. arXiv:1110.2574. doi:10.1145/2431211.2431220.
11. Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf [ 26 лютого 2021 у Wayback Machine.]
12. Cohen, Eyal; Dolev, Shlomi; Rosenblit, Michael (26 квітня 2016). All-optical design for inherently energy-conserving reversible gates and circuits. Nature Communications. 7 (1): 11424. Bibcode:2016NatCo...711424C. doi:10.1038/ncomms11424. PMC 4853429. PMID 27113510.
13. Ang, Y. S.; Yang, S. A.; Zhang, C.; Ma, Z. S.; Ang, L. K. (2017). Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate. Physical Review B. 96 (24): 245410. arXiv:1711.05906. Bibcode:2017PhRvB..96x5410A. doi:10.1103/PhysRevB.96.245410.

Подальше читання

• Denning, Peter; Lewis, Ted (2017). Computers That Can Run Backwards. American Scientist. 105 (5): 270. doi:10.1511/2017.105.5.270.
• Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain (April 2000). Reversible Space Equals Deterministic Space. Journal of Computer and System Sciences. 60 (2): 354—367. doi:10.1006/jcss.1999.1672.
• Perumalla K. S. (2014), Introduction to Reversible Computing, CRC Press.
• Vitányi, Paul (2005). Time, space, and energy in reversible computing. Proceedings of the 2nd conference on Computing frontiers - CF '05. с. 435. doi:10.1145/1062261.1062335. ISBN .

Зовнішні джерела

• Introductory article on reversible computing [ 21 січня 2022 у Wayback Machine.]
• First International Workshop on reversible computing [ 22 лютого 2020 у Wayback Machine.]
• Recent publications of Michael P. Frank [ 22 лютого 2020 у Wayback Machine.]
• of the "Reversible computing community Wiki" that was administered by Frank
• Recent Workshops on Reversible Computation [ 30 листопада 2020 у Wayback Machine.]
• Open-source toolkit for reversible circuit design [ 29 листопада 2020 у Wayback Machine.]