Обратное вычисление
Обратные вычисления — это программное применение концепции обратимых вычислений .
Поскольку обратимые вычисления предлагают возможное решение проблемы нагрева, с которой сталкиваются производители чипов, они широко изучаются в области компьютерной архитектуры. Перспективы обратимых вычислений заключаются в том, что потери тепла в обратимых архитектурах будут минимальными при значительно большом количестве транзисторов. [1] [2] Вместо того, чтобы создавать энтропию (и, следовательно, тепло) посредством разрушительных операций, обратимая архитектура сохраняет энергию, выполняя другие операции, сохраняющие состояние системы. [3] [4]
Концепция обратных вычислений несколько проще, чем обратимые вычисления, поскольку обратные вычисления необходимы только для восстановления эквивалентного состояния программного приложения, а не для поддержки обратимости набора всех возможных инструкций. Концепции обратимых вычислений успешно применяются в качестве обратных вычислений в таких областях программного обеспечения, как проектирование баз данных, [5] контрольные точки и отладка, [6] и дифференциация кода. [7] [8]
Обратные вычисления для параллельного моделирования дискретных событий
[ редактировать ]
Основываясь на успешном применении концепций обратных вычислений в других областях программного обеспечения, Крис Карозерс, Калян Перумалла и Ричард Фуджимото [9] предложить применение обратных вычислений для уменьшения накладных расходов на сохранение состоянияв параллельном моделировании дискретных событий (PDES). Они определяют подход, основанный на кодах обратных событий (которые могут генерироваться автоматически) ипродемонстрировать преимущества этого подхода в производительности по сравнению с традиционным сохранением состояния для мелкомодульных приложений (с небольшим объемом вычислений на событие).Ключевое свойство, которое использует обратное вычисление, заключается в том, что большинство операций, изменяющих переменные состояния, носят «конструктивный» характер. То есть операция отмены для таких операций не требует истории. Для отмены операции требуются только самые текущие значения переменных. Например, к этой категории относятся такие операторы, как ++, ––, +=, -=, *= и /=. Обратите внимание, что операторы *= и /= требуют особого обращения в случае умножения или деления.по нулю, а также условия переполнения/недополнения. Более сложные операции, такие как циклический сдвиг (особый случай — обмен) и некоторые классы операций. Генерация случайных чисел также относится сюда.
Операции вида a = b, вычисления по модулю и поразрядные , приводящие к потере данных, называются разрушительными. Обычно эти операции можно восстановить только с использованием традиционных методов сохранения состояния. Однако мы наблюдаем, что многие из этих деструктивных операций являются следствием поступления данных, содержащихся в обрабатываемом событии. Например, в работе Яуна, Каротерса и др. с крупномасштабным TCP : моделированием [10] время последней отправки записывает отметку времени последнего пакета, перенаправленного логическому процессу маршрутизатора. Операция обмена делает эту операцию обратимой.
История обратных вычислений применительно к параллельному моделированию дискретных событий
[ редактировать ]
В 1985 году Джефферсон представил протокол оптимистической синхронизации, который использовался в параллельном моделировании дискретных событий, известный как Time Warp. [11] На сегодняшний день метод, известный как обратные вычисления, применяется только в программном обеспечении для оптимистически синхронизированного параллельного моделирования дискретных событий.
В декабре 1999 года Майкл Франк окончил Университет Флориды . Его докторская диссертация была посвящена обратным вычислениям на аппаратном уровне, но включала описания как архитектуры набора команд, так и языка программирования высокого уровня (R) для процессора, основанного на обратных вычислениях. [12] [примечания 1]
В 1998 году Карозерс и Перумалла опубликовали статью для семинара «Принципы расширенного и распределенного моделирования». [13] в рамках своей аспирантуры под руководством Ричарда Фудзимото они представили технику обратных вычислений как альтернативный механизм отката в оптимистично синхронизированном параллельном моделировании дискретных событий (Time Warp). В 1998 году Карозерс стал доцентом Политехнического института Ренсселера . Работая с аспирантами Дэвидом Бауэром и Шоном Пирсом, Карозерс интегрировал проект деформации времени Технологического института Джорджии в систему оптимистического моделирования Ренсселера (ROSS), которая поддерживала только обратные вычисления в качестве механизма отката. Каротерс также построил RC-модели для BitTorrent в General Electric, а также вместе со студентами разработал многочисленные сетевые протоколы ( BGP4 , TCP Tahoe, Multicast ). Карозерс создал курс по параллельному и распределенному моделированию, в котором студентам предлагалось построить RC-модели в ROSS.
Примерно в то же время Перумалла окончил Технологический институт Джорджии и поступил на работу в Окриджскую национальную лабораторию (ORNL). Там он построил симулятор uSik, который представлял собой комбинированный оптимистический/консервативный протокол PDES. Система была способна динамически определять лучший протокол для ЛП и переназначать их во время выполнения в ответ на динамику модели. В 2007 году Перумалла протестировал uSik на Blue Gene/L и обнаружил, что, хотя масштабируемость ограничена процессорами 8 КБ для чистой реализации Time Warp, консервативная реализация масштабируется до доступных процессоров 16 КБ. Обратите внимание, что сравнительный анализ проводился с использованием PHOLD с ограниченной частотой удаленных событий 10 %, где временная метка событий определялась экспоненциальным распределением со средним значением 1,0, а к каждому событию добавлялся дополнительный просмотр вперед 1,0. Это была первая реализация PDES на Blue Gene с использованием обратных вычислений.
С 1998 по 2005 год Бауэр выполнял дипломную работу в RPI под руководством Карозерса, сосредоточившись исключительно на обратных вычислениях. Он разработал первую систему PDES, основанную исключительно на обратных вычислениях, названную Системой оптимистического моделирования Ренсселера (ROSS). [14] для комбинированных систем с общей и распределенной памятью . С 2006 по 2009 год Бауэр работал под руководством Э. Х. Пейджа в Miter Corporation и в сотрудничестве с Каротерсом и Пирсом внедрил симулятор ROSS на процессор 131 072 Blue Gene/P (Intrepid). Эта реализация была стабильной при уровне удаленных событий 100 % (каждое событие, отправленное по сети). Во время работы в RPI и MITRE Бауэр разработал систему сетевого моделирования ROSS.Net. [15] который поддерживает полуавтоматическую разработку экспериментов для оптимизации «черного ящика» моделей сетевых протоколов, выполняемых в ROSS. Основная цель системы заключалась в оптимизации нескольких моделей сетевых протоколов для выполнения в ROSS. Например, создание многоуровневой структуры LP для устранения событий, передаваемых между LP сетевых протоколов на одной и той же моделируемой машине, оптимизирует моделирование сетевых узлов TCP/IP за счет устранения меток времени с нулевым смещением между протоколами TCP и IP. Бауэр также построил модели на основе агентов RC для сетей социальных контактов для изучения последствий инфекционных заболеваний , в частности пандемического гриппа, которые масштабируются до сотен миллионов агентов; а также модели RC для мобильных одноранговых сетей, реализующие функции мобильности (обнаружение близости) и высокоточного электромагнитных волн распространения на физическом уровне (модель матрицы линии передачи). [16]
Сообщество PDES недавно также предприняло попытку перейти к сфере непрерывного моделирования. Например, Фудзимото и Перумалла, работающие с Tang et al. [17] реализовали RC-модель частицы в ячейке и продемонстрировали превосходное ускорение по сравнению с непрерывным моделированием для моделей света как частицы. Бауэр и Пейдж продемонстрировали превосходное ускорение модели матрицы RC-линий передачи (PB Johns, 1971), моделируя свет как волну на микроволновых частотах. Бауэр также создал RC-вариант SEIR , который обеспечивает огромные улучшения по сравнению с непрерывными моделями в области распространения инфекционных заболеваний. Кроме того, модель RC SEIR способна эффективно моделировать множество заболеваний, тогда как непрерывная модель экспоненциально расширяется по отношению к количеству возможных комбинаций заболеваний среди населения.
События
[ редактировать ]Примечания
[ редактировать ]- ^ Доктор Франк поддерживает два веб-сайта со своими публикациями по обратным вычислениям, начиная с 2004 года и позже .
Ссылки
[ редактировать ]- ^ Ландауэр, Рольф (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. CiteSeerX 10.1.1.68.7646 . дои : 10.1147/рд.53.0183 .
- ^ Фон Нейман, Джон (1966). Теория самовоспроизводящихся автоматов . Издательство Университета Иллинойса. п. 388 . Проверено 6 апреля 2009 г.
- ^ Беннетт, Чарльз Х. (1982). «Термодинамика вычислений — обзор» (PDF) . Международный журнал теоретической физики . 21 (12): 905–940. Бибкод : 1982IJTP...21..905B . CiteSeerX 10.1.1.655.5610 . дои : 10.1007/BF02084158 . S2CID 17471991 . Проверено 6 апреля 2009 г.
- ^ Фрэнк, Майкл П. (июнь 1999 г.). Обратимость для эффективных вычислений, к.т.н. Диссертация (PDF) . Массачусетский технологический институт, факультет электротехники и информатики . Проверено 6 апреля 2009 г.
- ^ Лиман младший, Джордж Б. (1986). «Формальный подход к отмене операций в языках программирования» . Транзакции ACM в языках и системах программирования . 8 (1): 50–87. дои : 10.1145/5001.5005 .
- ^ Бисвас, Битан; Молл, Р. (1999). «Обратное выполнение программ» . Уведомления ACM SIGPLAN . 34 (4): 61–69. дои : 10.1145/312009.312079 . S2CID 11685971 .
- ^ Гриванк, Андреас; Юедес, Дэвид; Утке, Жан (1996). «Алгоритм 755: Adolc: пакет для автоматического дифференцирования алгоритмов, написанных на c/c++» . Транзакции ACM в математическом программном обеспечении . 22 (2): 131–167. дои : 10.1145/229473.229474 . S2CID 7339428 .
- ^ Гримм, Дж; Поттье, Л.; Ростен-Шмидт, Н. (1996). «Оптимальное время и минимальное произведение пространства-времени для обращения определенного класса программ» (PDF) . Технический отчет .
- ^ Карозерс, Кристофер Д.; Перумалла, Калян С.; Фудзимото, Ричард М. (1999). «Эффективное оптимистичное параллельное моделирование с использованием обратных вычислений» (PDF) . ACM-транзакции по моделированию и компьютерному моделированию . 9 (3): 224–253. CiteSeerX 10.1.1.113.1702 . дои : 10.1145/347823.347828 . S2CID 969021 . Архивировано из оригинала (PDF) 17 июля 2011 г. Проверено 6 апреля 2009 г.
- ^ Яун, Гарретт; Карозерс, Кристофер Д.; Кальянараман, Шивкумар (2003). «Крупномасштабные модели TCP с использованием оптимистического параллельного моделирования». Семнадцатый семинар по параллельному и распределенному моделированию, 2003 г. (PADS 2003). Слушания . стр. 153–162. CiteSeerX 10.1.1.115.1320 . дои : 10.1109/PADS.2003.1207431 . ISBN 978-0-7695-1970-8 . S2CID 6196101 .
- ^ Джефферсон, Дэвид Р. (1985). «Виртуальное время» (PDF) . Транзакции ACM в языках и системах программирования . 7 (3): 404–425. дои : 10.1145/3916.3988 . S2CID 2654080 . Проверено 6 апреля 2009 г.
- ^ Вьери, К.; Аммер, MJ; Франк, М.; Марголюс, Н. ; Найт, Т. (июнь 1998 г.). «Полностью обратимый микропроцессор с асимптотически нулевой энергией» (PDF) . Семинар по микроархитектуре с силовым приводом : 138–142.
- ^ Семинар по принципам расширенного и распределенного моделирования, ныне Конференция ACM SIGSIM по принципам расширенного дискретного моделирования (PADS)
- ^ Карозерс, Кристофер Д.; Бауэр, Д.В.; Пирс, Шон О. (2002). «РОСС: Высокопроизводительная модульная система Time Warp с малым объемом памяти». Журнал параллельных и распределенных вычислений . 62 (11): 1648–1669. CiteSeerX 10.1.1.78.3105 . дои : 10.1016/S0743-7315(02)00004-7 .
- ^ Бауэр, Дэвид В.; Яун, Гарретт; Карозерс, Кристофер Д.; Юксель, Мурат; Кальянараман, Шивкумар (2003). «ROSS.Net: Оптимистическая система параллельного моделирования для крупномасштабных интернет-моделей». Материалы Международной конференции по машинному обучению и кибернетике 2003 г. (каталожный номер IEEE 03EX693) . Том. 1. С. 703–711. дои : 10.1109/WSC.2003.1261486 . ISBN 978-0-7803-8131-5 . S2CID 2735827 .
- ^ Бауэр-младший, Дэвид В.; Пейдж, Эрнест Х. (2007). «Оптимистическое параллельное моделирование дискретных событий с помощью матричного метода линий передачи на основе событий». Материалы 39-й конференции по зимнему моделированию: 40 лет! Лучшее еще впереди : 676–684. CiteSeerX 10.1.1.132.307 .
- ^ Тан, Ю.; Перумалла, Канзас; Фудзимото, РМ; Каримабади, Х.; Дрисколл, Дж.; Омельченко Ю. (2005). «Оптимистическое параллельное моделирование дискретных событий физических систем с использованием обратных вычислений». Семинар по принципам расширенного и распределенного моделирования (PADS'05) (PDF) . стр. 26–35. CiteSeerX 10.1.1.110.5893 . дои : 10.1109/PADS.2005.16 . ISBN 978-0-7695-2383-5 . S2CID 802601 . Проверено 6 апреля 2009 г.
{{cite book}}:|journal=игнорируется ( помогите )