Обратное вычисление - Википедия - Reverse computation

Обратное вычисление это программного обеспечения применение концепции обратимые вычисления.

Поскольку обратимые вычисления предлагают возможное решение проблемы нагрева, с которой сталкиваются производители микросхем, они широко изучались в области компьютерной архитектуры. Перспективы обратимых вычислений заключаются в том, что количество тепловых потерь для обратимых архитектур будет минимальным для значительно большого количества транзисторов.[1][2] Вместо того, чтобы создавать энтропию (и, следовательно, тепло) посредством деструктивных операций, обратимая архитектура сохраняет энергию, выполняя другие операции, которые сохраняют состояние системы.[3][4]

Концепция обратных вычислений несколько проще, чем обратимые вычисления, поскольку обратные вычисления требуются только для восстановления эквивалент состояние программного приложения, а не поддерживает обратимость набора всех возможных инструкций. Концепции обратимых вычислений успешно применялись в качестве обратное вычисление в прикладных областях программного обеспечения, таких как проектирование баз данных,[5] чекпоинтинг и отладка,[6] и кодовое дифференцирование.[7][8]

Обратное вычисление для параллельного моделирования дискретных событий

Список операций, которые можно вычислить обратным образом, и их стоимость.

Основываясь на успешном применении концепций обратных вычислений в других областях программного обеспечения, Крис Каротерс, Кальян Перумалла и Ричард Фудзимото[9] предложить применение обратных вычислений для уменьшения накладных расходов на сохранение состояния параллельное моделирование дискретных событий (PDES). Они определяют подход, основанный на обратных кодах событий (которые могут быть автоматически сгенерированы), и демонстрируют преимущества в производительности этого подхода по сравнению с традиционным сохранением состояния для детализированных приложений (с небольшим объемом вычислений на событие). эксплойтов заключается в том, что большинство операций, изменяющих переменные состояния, носят «конструктивный» характер. Это отменить операция для таких операций не требует истории. Для отмены операции требуются только самые последние значения переменных. Например, к этой категории относятся такие операторы, как ++, ––, + =, - =, * = и / =. Обратите внимание, что операторы * = и / = требуют специальной обработки в случае умножения или деления на ноль, а также условий переполнения / потери значимости. Более сложные операции, такие как круговой сдвиг (своп является частным случаем), и некоторые классы генерация случайных чисел тоже принадлежат сюда.

Операции вида a = b, по модулю и побитовый вычисления, которые приводят к потере данных, называются деструктивными. Обычно эти операции можно восстановить только с помощью обычных методов сохранения состояния. Однако мы наблюдаем, что многие из этих деструктивных операций являются следствием поступления данных, содержащихся в обрабатываемом событии. Например, в работе Yaun, Carothers и др. С крупномасштабными TCP моделирование[10] Время последней отправки записывает метку времени последнего пакета, пересылаемого логическим процессом маршрутизатора. Операция обмена делает эту операцию обратимой.

История обратных вычислений применительно к параллельному дискретному моделированию событий

Таксономия цифрового моделирования.

В 1985 году Джефферсон представил протокол оптимистической синхронизации, который использовался в параллельном моделировании дискретных событий, известном как Time Warp.[11] На сегодняшний день методика известна как Обратное вычисление применяется только в программном обеспечении для оптимистически синхронизированного параллельного моделирования дискретных событий.

В декабре 1999 года Майкл Франк окончил Университет Флориды. Его докторская диссертация были сосредоточены на обратных вычислениях на аппаратном уровне, но включали описания как архитектуры набора команд, так и языка программирования высокого уровня (R) для процессора, основанного на обратных вычислениях.[12][примечания 1]

В 1998 году Карозерс и Перумалла опубликовали доклад для семинара по принципам расширенного и распределенного моделирования.[13] в рамках своей аспирантуры под руководством Ричарда Фудзимото, знакомящей с техникой обратных вычислений в качестве альтернативного механизма отката в оптимистически синхронизированных параллельных симуляциях дискретных событий (Time Warp). В 1998 году Карозерс стал доцентом в Политехнический институт Ренсселера. Работая с аспирантами Дэвидом Бауэром и Шоном Пирсом, Карозерс интегрировал конструкцию Технологии Технологии Джорджии Time Warp в систему оптимистического моделирования Ренсселера (ROSS), которая поддерживала только обратные вычисления в качестве механизма отката. Карозерс также построил RC-модели для BitTorrent в General Electric, а также многочисленные сетевые протоколы со студентами (BGP4, ПТС Тахо, Многоадресная рассылка ). Карозерс создал курс по параллельному и распределенному моделированию, в котором студенты должны были построить RC-модели в ROSS.

Примерно в то же время Перумалла окончила Технологический институт Джорджии и пошел работать в Национальная лаборатория Окриджа (ORNL). Там он построил симулятор uSik, который представлял собой комбинированный оптимистичный / консервативный протокол PDES. Система была способна динамически определять лучший протокол для LP и переназначать их во время выполнения в ответ на динамику модели. В 2007 году Perumalla протестировала uSik на Синий Джин / L и обнаружил, что, хотя масштабируемость ограничена процессорами 8K для чистой реализации Time Warp, консервативная реализация масштабируется до 16K доступных процессоров. Обратите внимание, что сравнительный анализ проводился с использованием PHOLD с ограниченной частотой удаленных событий 10%, где временная метка событий определялась экспоненциальным распределением со средним значением 1,0, а к каждому событию добавлялся дополнительный прогноз 1,0. Это была первая реализация PDES на Blue Gene с использованием обратных вычислений.

С 1998 по 2005 год Бауэр выполнял дипломную работу в RPI под руководством Карозерса, сосредоточившись исключительно на обратных вычислениях. Он разработал первую систему PDES, основанную исключительно на обратных вычислениях, под названием Система оптимистического моделирования Ренсселера (ROSS).[14] для комбинированных общий и распределенная память системы. С 2006 по 2009 год Бауэр работал под руководством Э. Страница на Mitre Corporation, и в сотрудничестве с Каротерсом и Пирсом продвинули симулятор ROSS на 131072 процессора. Синий Джин / P (Бесстрашный). Эта реализация была стабильной для 100% удаленных событий (каждое событие, отправленное по сети). Во время работы в RPI и MITER Бауэр разработал систему сетевого моделирования ROSS.Net.[15] который поддерживает полуавтоматический эксперимент по оптимизации моделей сетевых протоколов, выполняемых в ROSS. Основная цель системы заключалась в оптимизации нескольких моделей сетевых протоколов для выполнения в ROSS. Например, создание многоуровневой структуры LP для исключения событий, передаваемых между LP сетевых протоколов на одной моделируемой машине, оптимизирует моделирование сетевых узлов TCP / IP за счет устранения временных меток с нулевым смещением между протоколами TCP и IP. Бауэр также построил RC-агентные модели для социальные сети контактов изучать эффекты инфекционные заболевания, в частности пандемический грипп, масштабы которого составляют сотни миллионов агентов; а также модели RC для мобильных ad-hoc сетей, реализующие функциональность мобильности (обнаружение приближения) и высокоточный физический уровень электромагнитная волна распространение (Матричная модель линии передачи).[16]

Также недавно сообщество PDES сделало шаг в сторону непрерывного моделирования. Например, Фудзимото и Перумалла, работая с Тангом и др.[17] реализовали RC-модель частицы в ячейке и продемонстрировали превосходное ускорение по сравнению с непрерывным моделированием для моделей света как частицы. Бауэр и Пейдж продемонстрировали превосходное ускорение для модели матрицы RC-линии передачи (P.B. Johns, 1971), моделируя свет как волну на микроволновых частотах. Бауэр также создал вариант RC SEIR что значительно улучшает непрерывные модели в области распространения инфекционных заболеваний. Кроме того, модель RC SEIR способна эффективно моделировать множество заболеваний, в то время как непрерывная модель растет экспоненциально по отношению к количеству комбинаций болезней, возможных для всего населения.

События

Примечания

  1. ^ Доктор Франк ведет два веб-сайта своих публикаций на обратный расчет к 2004 г. и потом.

Рекомендации

  1. ^ Ландауэр, Рольф (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM. 5 (3): 183–191. CiteSeerX  10.1.1.68.7646. Дои:10.1147 / rd.53.0183.
  2. ^ Фон Нейман, Джон (1966). Теория самовоспроизводящихся автоматов. Университет Иллинойса Press. п. 388. Получено 2009-04-06.
  3. ^ Беннет, Чарльз Х. (1982). «Термодинамика вычислений - обзор» (PDF). Международный журнал теоретической физики. 21 (12): 905–940. Bibcode:1982IJTP ... 21..905B. CiteSeerX  10.1.1.655.5610. Дои:10.1007 / BF02084158. Получено 2009-04-06.
  4. ^ Франк, Майкл П. (июнь 1999 г.). Обратимость для эффективных вычислений, канд. Тезис (PDF). Массачусетский технологический институт, кафедра электротехники и компьютерных наук. Получено 2009-04-06.
  5. ^ Лиман-младший, Джордж Б. (1986). «Формальный подход к отмене операций в языках программирования». Транзакции ACM по языкам и системам программирования. 8 (1): 50–87. Дои:10.1145/5001.5005.
  6. ^ Бисвас, Битан; Молл, Р. (1999). «Обратное выполнение программ». Уведомления ACM SIGPLAN. 34 (4): 61–69. Дои:10.1145/312009.312079.
  7. ^ Гриванк, Андреас; Juedes, Дэвид; Утке, Жан (1996). «Алгоритм 755: Adolc: пакет для автоматического дифференцирования алгоритмов, написанных на c / c ++». Транзакции ACM на математическом ПО. 22 (2): 131–167. Дои:10.1145/229473.229474.
  8. ^ Гримм, Дж; Pottier, L .; Ростаинг-Шмидт, Н. (1996). «Оптимальное время и минимальное пространство-время для обращения определенного класса программ» (PDF). Технический отчет.
  9. ^ Карозерс, Кристофер Д.; Перумалла, Калян С .; Фудзимото, Ричард М. (1999). «Эффективное оптимистическое параллельное моделирование с использованием обратных вычислений» (PDF). Транзакции ACM по моделированию и компьютерному моделированию. 9 (3): 224–253. CiteSeerX  10.1.1.113.1702. Дои:10.1145/347823.347828. Архивировано из оригинал (PDF) на 2011-07-17. Получено 2009-04-06.
  10. ^ Яун, Гарретт; Карозерс, Кристофер Д.; Калянараман, Шивкумар (2003). Крупномасштабные модели TCP с использованием оптимистичного параллельного моделирования. Труды семнадцатого семинара по параллельному и распределенному моделированию. С. 153–162. CiteSeerX  10.1.1.115.1320. Дои:10.1109 / PADS.2003.1207431. ISBN  978-0-7695-1970-8.
  11. ^ Джефферсон, Дэвид Р. (1985). «Виртуальное время» (PDF). Транзакции ACM по языкам и системам программирования. 7 (3): 404–425. Дои:10.1145/3916.3988. Получено 2009-04-06.
  12. ^ Vieri, C .; Ammer, M.J .; Франк, М .; Марголус, Н.; Найт, Т. (июнь 1998 г.). «Полностью обратимый микропроцессор с асимптотически нулевой энергией» (PDF). Семинар по управляемой микроархитектуре: 138–142.
  13. ^ Семинар по принципам расширенного и распределенного моделирования, сейчас Конференция ACM SIGSIM по принципам расширенного дискретного моделирования (PADS)
  14. ^ Карозерс, Кристофер Д.; Bauer, D. W .; Пирс, Шон О. (2002). «РОСС: высокопроизводительная модульная система Time Warp с малым объемом памяти». Журнал параллельных и распределенных вычислений. 62 (11): 1648–1669. CiteSeerX  10.1.1.78.3105. Дои:10.1016 / S0743-7315 (02) 00004-7.
  15. ^ Бауэр, Дэвид В .; Яун, Гарретт; Карозерс, Кристофер Д.; Юксель, Мурат; Калянараман, Шивкумар (2003). ROSS.Net: оптимистическая среда параллельного моделирования для крупномасштабных интернет-моделей. Труды Зимней конференции по моделированию 2003 г.. 1. С. 703–711. Дои:10.1109 / WSC.2003.1261486. ISBN  978-0-7803-8131-5.
  16. ^ Бауэр младший, Дэвид В .; Пейдж, Эрнест Х. (2007). «Оптимистическое параллельное моделирование дискретных событий матричного метода линий передачи на основе событий». Материалы 39-й конференции по зимнему моделированию: 40 лет! Лучшее еще впереди: 676–684. CiteSeerX  10.1.1.132.307.
  17. ^ Tang, Y .; Perumalla, K. S .; Fujimoto, R.M .; Karimabadi, H .; Driscoll, J .; Омельченко, Ю. (2005). Оптимистическое параллельное моделирование физических систем с дискретными событиями с использованием обратных вычислений (PDF). Принципы расширенного и распределенного моделирования. С. 26–35. CiteSeerX  10.1.1.110.5893. Дои:10.1109 / PADS.2005.16. ISBN  978-0-7695-2383-5. Получено 2009-04-06.