Обратные вычисления - это программное приложение концепции обратимых вычислений .
Поскольку обратимые вычисления предлагают возможное решение проблемы нагрева, с которой сталкиваются производители микросхем, они широко изучались в области компьютерной архитектуры. Перспективы обратимых вычислений заключаются в том, что количество тепловых потерь для обратимых архитектур будет минимальным для значительно большого количества транзисторов. [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 , TCP Tahoe, Multicast ). Карозерс создал курс по параллельному и распределенному моделированию, в котором студенты должны были построить RC-модели в ROSS.
Примерно в то же время Перумалла окончил Технологический институт Джорджии и пошел работать в Национальную лабораторию Ок-Ридж (ORNL). Там он построил симулятор uSik, который представлял собой комбинированный оптимистичный / консервативный протокол PDES. Система была способна динамически определять лучший протокол для LP и переназначать их во время выполнения в ответ на динамику модели. В 2007 году Перумалла протестировал uSik на Blue Gene / L и обнаружил, что, хотя масштабируемость ограничена процессорами 8K для чистой реализации Time Warp, консервативная реализация масштабируется до 16K доступных процессоров. Обратите внимание, что сравнительный анализ проводился с использованием PHOLD с ограниченной частотой удаленных событий 10%, где временная метка событий определялась экспоненциальным распределением со средним значением 1,0, и к каждому событию добавлялся дополнительный прогноз 1,0. Это была первая реализация PDES на Blue Gene с использованием обратных вычислений.
С 1998 по 2005 год Бауэр выполнял дипломную работу в RPI под руководством Карозерса, сосредоточившись исключительно на обратных вычислениях. Он разработал первую систему PDES, основанную исключительно на обратных вычислениях, под названием система оптимистического моделирования Ренсселера (ROSS). [14] для комбинированных систем с общей и распределенной памятью . С 2006 по 2009 год Бауэр работал в компании EH Page в Mitre Corporation , и в сотрудничестве с Каротерсом и Пирсом продвинул симулятор ROSS на 131072 процессора Blue Gene / P (Intrepid). Эта реализация была стабильной для 100% удаленных событий (каждое событие, отправленное по сети). Во время работы в RPI и MITER Бауэр разработал систему моделирования сети ROSS.Net [15], которая поддерживает полуавтоматический дизайн экспериментов для оптимизации черного ящика моделей сетевых протоколов, выполняемых в ROSS. Основная цель системы заключалась в оптимизации нескольких моделей сетевых протоколов для выполнения в ROSS. Например, создание многоуровневой структуры LP для исключения событий, передаваемых между LP сетевых протоколов на одной моделируемой машине, оптимизирует моделирование сетевых узлов TCP / IP, устраняя временные метки с нулевым смещением между протоколами TCP и IP. Бауэр также построил агент-ориентированные модели RC для сетей социальных контактов для изучения эффектов инфекционных заболеваний , в частности пандемического гриппа, которые распространяются на сотни миллионов агентов; а также модели RC для мобильных одноранговых сетей, реализующие функциональность мобильности (обнаружение приближения) и высокоточное распространение электромагнитных волн на физическом уровне (матричная модель линии передачи). [16]
Сообщество PDES также недавно сделало шаг в сторону непрерывного моделирования. Например, Фудзимото и Перумалла, работая с Тангом и др. [17] реализовали RC-модель частицы в ячейке и продемонстрировали превосходное ускорение по сравнению с непрерывным моделированием для моделей света как частицы. Бауэр и Пейдж продемонстрировали превосходное ускорение для модели матрицы линии передачи RC (PB Johns, 1971), моделируя свет как волну на микроволновых частотах. Бауэр также создал RC-вариант SEIR, который значительно улучшает непрерывные модели в области распространения инфекционных заболеваний. Кроме того, модель RC SEIR способна эффективно моделировать множество заболеваний, в то время как непрерывная модель расширяется экспоненциально по отношению к количеству комбинаций болезней, возможных для всей популяции.
События
Заметки
- ^ Д-р Франк поддерживает два веб-сайта своих публикаций по обратным вычислениям до 2004 года и позже .
Рекомендации
- ^ Ландауэр, Рольф (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. CiteSeerX 10.1.1.68.7646 . DOI : 10.1147 / rd.53.0183 .
- ^ Фон Нейман, Джон (1966). Теория самовоспроизводящихся автоматов . Издательство Иллинойского университета. п. 388 . Проверено 6 апреля 2009 .
- ^ Беннетт, Чарльз Х. (1982). «Термодинамика вычислений - обзор» (PDF) . Международный журнал теоретической физики . 21 (12): 905–940. Bibcode : 1982IJTP ... 21..905B . CiteSeerX 10.1.1.655.5610 . DOI : 10.1007 / BF02084158 . Проверено 6 апреля 2009 .
- ^ Франк, Майкл П. (июнь 1999 г.). Обратимость для эффективных вычислений, канд. Диссертация (PDF) . Массачусетский технологический институт, факультет электротехники и информатики . Проверено 6 апреля 2009 .
- ^ Лиман-младший, Джордж Б. (1986). «Формальный подход к отмене операций в языках программирования». Транзакции ACM по языкам и системам программирования . 8 (1): 50–87. DOI : 10.1145 / 5001.5005 .
- ^ Бисвас, Битан; Молл, Р. (1999). «Обратное выполнение программ». Уведомления ACM SIGPLAN . 34 (4): 61–69. DOI : 10.1145 / 312009.312079 .
- ^ Гриванк, Андреас; Juedes, Дэвид; Утке, Жан (1996). «Алгоритм 755: Adolc: пакет для автоматического дифференцирования алгоритмов, написанных на c / c ++». Транзакции ACM на математическом программном обеспечении . 22 (2): 131–167. DOI : 10.1145 / 229473.229474 .
- ^ Гримм, Дж; Pottier, L .; Ростаинг-Шмидт, Н. (1996). «Оптимальное время и минимальное пространство-время для обращения вспять определенного класса программ» (PDF) . Технический отчет .
- ^ Карозерс, Кристофер Д.; Перумалла, Калян С .; Фудзимото, Ричард М. (1999). «Эффективное оптимистическое параллельное моделирование с использованием обратных вычислений» (PDF) . Транзакции ACM по моделированию и компьютерному моделированию . 9 (3): 224–253. CiteSeerX 10.1.1.113.1702 . DOI : 10.1145 / 347823.347828 . Архивировано из оригинального (PDF) 17 июля 2011 года . Проверено 6 апреля 2009 .
- ^ Яун, Гарретт; Карозерс, Кристофер Д.; Калянараман, Шивкумар (2003). Крупномасштабные модели TCP с использованием оптимистичного параллельного моделирования . Труды семнадцатого семинара по параллельному и распределенному моделированию . С. 153–162. CiteSeerX 10.1.1.115.1320 . DOI : 10.1109 / PADS.2003.1207431 . ISBN 978-0-7695-1970-8.
- ^ Джефферсон, Дэвид Р. (1985). «Виртуальное время» (PDF) . Транзакции ACM по языкам и системам программирования . 7 (3): 404–425. DOI : 10.1145 / 3916.3988 . Проверено 6 апреля 2009 .
- ^ Vieri, C .; Аммер, MJ; Франк, М .; Марголус, Н .; Найт, Т. (июнь 1998 г.). «Полностью обратимый микропроцессор с асимптотически нулевой энергией» (PDF) . Power Driven Microarchitecture Workshop : 138–142.
- ^ Семинар по принципам расширенного и распределенного моделирования, сейчас Конференция ACM SIGSIM по принципам расширенного дискретного моделирования (PADS)
- ^ Карозерс, Кристофер Д.; Бауэр, DW; Пирс, Шон О. (2002). «РОСС: высокопроизводительная модульная система Time Warp с малым объемом памяти». Журнал параллельных и распределенных вычислений . 62 (11): 1648–1669. CiteSeerX 10.1.1.78.3105 . DOI : 10.1016 / S0743-7315 (02) 00004-7 .
- ^ Бауэр, Дэвид В .; Яун, Гарретт; Карозерс, Кристофер Д.; Юксель, Мурат; Калянараман, Шивкумар (2003). ROSS.Net: оптимистическая среда параллельного моделирования для крупномасштабных Интернет-моделей . Материалы Зимней Simulation конференции 2003 . 1 . С. 703–711. DOI : 10,1109 / WSC.2003.1261486 . ISBN 978-0-7803-8131-5.
- ^ Бауэр младший, Дэвид В .; Пейдж, Эрнест Х. (2007). «Оптимистическое параллельное моделирование дискретных событий матричного метода линий передачи на основе событий». Материалы 39-й конференции по зимнему моделированию: 40 лет! Лучшее еще впереди : 676–684. CiteSeerX 10.1.1.132.307 .
- ^ Tang, Y .; Perumalla, KS; Fujimoto, RM; Karimabadi, H .; Driscoll, J .; Омельченко, Ю. (2005). Оптимистическое параллельное моделирование дискретных событий физических систем с использованием обратных вычислений (PDF) . Принципы расширенного и распределенного моделирования . С. 26–35. CiteSeerX 10.1.1.110.5893 . DOI : 10.1109 / PADS.2005.16 . ISBN 978-0-7695-2383-5. Проверено 6 апреля 2009 .