Оптимизация операций программной транзакционной памяти

Оптимизация операций программной транзакционной памяти

Иллюстрации

Показать все

Реферат

Перекрестная ссылка на родственные заявки

По этой заявке испрашивается приоритет патентной заявки США №11/389,451, поданной 23 марта 2006 года, которая притязает на приоритет предварительной заявки США №60/748,386, поданной 7 декабря 2005 года.

Предшествующий уровень техники

Общим для множественных потоков многопотокового процесса является совместное использование общих ячеек памяти во время параллельного исполнения. Следовательно, два разных потока многопотокового процесса могут читать и обновлять одну и ту же ячейку памяти, к которой обращается программа. Однако следует предпринимать осторожность, чтобы гарантировать, что один поток не модифицирует значение совместно используемой ячейки, в то время как другой поток находится в середине последовательности операций, которые зависят от этого значения.

Например, предположим, что программа обращается к содержимому двух разных программных объектов, в которых каждый объект представляет количество денег на разных банковских счетах. Первоначально сумма первого счета, равная $10, сохранена по адресу A1 памяти, в то время как сумма второго счета, равная $200, сохранена по адресу A2 памяти. Первый поток банковской программы закодирован, чтобы переводить $100 с A2 на A1, а второй поток закодирован, чтобы вычислить общее количество денежных средств на обоих счетах. Первый поток может начаться добавлением $100 к содержимому A1, обновлением его до $110 и затем перейти к вычитанию $100 из содержимого A2, обновлению его до $100. Однако если второй поток выполняется между этими двумя операциями, то второй поток может вычислить скорее неправильную сумму в $310 для обоих счетов, чем правильную сумму в $210.

Программная транзакционная память предоставляет абстракцию программирования, посредством которой поток может безопасно выполнить последовательность обращений к совместно используемой памяти, позволяющую потоку завершить свою транзакцию без помех от другого потока. Соответственно транзакционные запоминающие устройства могут быть применены в программном обеспечении, чтобы гарантировать, что транзакция, включающая в себя примерные операции добавления и вычитания первого потока, является "атомарной" по отношению к ячейкам A1 и A2 памяти, и поэтому второй поток будет вычислять правильную итоговую сумму на обоих счетах.

Однако существующие подходы осуществления транзакционной памяти в программном обеспечении страдают от проблем, связанных с производительностью. Например, в одном существующем подходе, когда поток обращается к последовательности ячеек памяти в рамках транзакции, этот поток поддерживает отдельный список ячеек памяти и значений, которые он желает прочитать и обновить (т.е. записать) во время транзакции, и затем, в конце транзакции, поток обновляет все эти значения в фактически совместно используемых ячейках памяти. Если во время транзакции поток хочет повторно прочитать или повторно записать в любую ячейку памяти в своем списке, поток должен исследовать запись ячейки памяти в списке, чтобы обратиться к записи, что является медленным с программной точки зрения. Соответственно этот косвенный способ осуществления транзакционной памяти в программном обеспечении страдает от плохой производительности.

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

Сущность изобретения

Описана система программной транзакционной памяти ("STM"). Система и методика, описанные в данном документе, выполняют оптимизации инструкций программной транзакционной памяти, чтобы достичь эффективной работы. Описан компилятор, который заменяет блоки программной транзакционной памяти инструкциями программной транзакционной памяти и дополнительно декомпозирует эти инструкции на декомпозированные инструкции программной транзакционной памяти. Компилятор использует знание семантики инструкции, чтобы выполнять оптимизации, которые будут недоступны в традиционных системах программной транзакционной памяти. Компилятор дополнительно выполняет высокоуровневые оптимизации кода STM. Некоторые из этих оптимизаций выполняются, чтобы получить преимущество низкоуровневых оптимизаций. Эти высокоуровневые оптимизации включают в себя удаление необязательных модернизаций чтения-для-обновления, перемещение операций STM по вызовам процедур и удаление необязательных операций по новым создаваемым объектам. Дополнительно, код STM оптимизируется, чтобы предоставить строгую атомарность обращений к памяти, записанных вне транзакций.

В одном примере способ компиляции программы, включающей в себя блоки программной транзакционной памяти, описан в вычислительной системе, содержащей процессор и компилятор, сконфигурированный со знанием операций программной транзакционной памяти. Способ содержит оптимизацию программы, чтобы создать оптимизированную программу, содержащую инструкции программной транзакционной памяти, и компиляцию оптимизированной программы.

Данное изложение сущности изобретения предусмотрено для того, чтобы в упрощенной форме представить набор идей, которые дополнительно описываются ниже в подробном описании. Это изложение сущности изобретения не предназначено для того, чтобы идентифицировать ключевые признаки или важнейшие признаки заявляемого предмета изобретения, а также не предназначена для того, чтобы быть использованной в качестве помощи при определении объема заявляемого изобретения.

Дополнительные признаки и преимущества станут очевидными из последующего подробного описания варианта осуществления, которое продолжается со ссылкой на сопровождающие чертежи.

Перечень фигур чертежей

Фиг.1 является блок-схемой компилятора, используемого, чтобы скомпилировать исходный код, содержащий атомарные блоки памяти транзакций.

Фиг.2 является блок-схемой компонентов компилятора на фиг.1.

Фиг.3 является блок-схемой, иллюстрирующей примерный процесс компиляции и выполнения программы, использующей транзакционную память.

Фиг.4 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на фиг.1, для компиляции программы с транзакционной памятью.

Фиг.5 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на фиг.1, для выполнения высокоуровневых оптимизаций программной транзакционной памяти.

Фиг.6 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на Фиг.1, для оптимизации декомпозированных инструкций программной транзакционной памяти во время компиляции.

Фиг.7 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на Фиг.1, для ввода операций для осуществления строгой атомарности.

Фиг.8 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на Фиг.1, для удаления модернизаций чтения-для-обновления.

Фиг.9 является блок-схемой, иллюстрирующей дополнительный примерный процесс, выполняемый компилятором на Фиг.1, для удаления модернизаций чтения-для-обновления.

Фиг.10 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на Фиг.1, для перемещения операций по вызовам процедур.

Фиг.11 является блок-схемой, иллюстрирующей примерный процесс, выполняемый компилятором на Фиг.1, для удаления операций регистрации для новых создаваемых объектов.

Фиг.12 является блок-схемой, иллюстрирующей дополнительный примерный процесс, выполняемый компилятором на Фиг.1, для удаления операций регистрации для новых создаваемых объектов.

Фиг.13 является блок-схемой, содержащей программные модули, использованные во время прогона программы в рабочей среде системы программной транзакционной памяти.

Фиг.14a и 14b являются блок-схемами, иллюстрирующими примерные объекты, использующие универсально используемые слова заголовков.

Фиг.15a и 15b являются блок-схемами, иллюстрирующими примерный объект с изменяющимся моментальным снимком.

Фиг.16 является блок-схемой, иллюстрирующей примерный процесс среды выполнения на Фиг.6 для проверки достоверности объекта с помощью моментальных снимков.

Фиг.17 является блок-схемой, иллюстрирующей примерный процесс среды выполнения на Фиг.6 для модификации моментального снимка объекта, использующего наполненное слово заголовка.

Фиг.18a и 18b являются блок-схемами, иллюстрирующими примеры выполнения транзакций.

Фиг.19a-19c являются блок-схемами, иллюстрирующими дополнительные примеры выполнения транзакций.

Фиг.20 является блок-схемой, иллюстрирующей примерную ассоциативную таблицу, используемую в среде выполнения на Фиг.6 для фильтрации журнала.

Фиг.21 является блок-схемой, иллюстрирующей примерный процесс среды выполнения на Фиг.6 для фильтрации журнальных записей с помощью ассоциативной таблицы на Фиг.13.

Фиг.22 является блок-схемой, иллюстрирующей дополнительный примерный процесс среды выполнения на Фиг.6 для фильтрации журнальных записей с помощью ассоциативной таблицы на Фиг.13.

Фиг.23 является блок-схемой, иллюстрирующей примерный процесс среды выполнения на Фиг.6 для уплотнения журналов во время очистки памяти.

Фиг.24 является блок-схемой, иллюстрирующей дополнительный примерный процесс, выполняемый в среде выполнения на Фиг.6, для уплотнения журналов во время очистки памяти.

Фиг.25 является блок-схемой, иллюстрирующей дополнительный примерный процесс, выполняемый в среде выполнения на Фиг.6, для уплотнения журналов во время очистки памяти.

Фиг.26 является блок-схемой подходящего вычислительного окружения для осуществления технологий данного документа.

Подробное описание

Примеры, иллюстрированные в данном документе, описывают примеры программных и аппаратных систем транзакционной памяти, также как и улучшения в производительности этих систем. В частности, примеры осуществления ниже описывают: декомпозированные операции программных транзакций; использование примитивов STM в промежуточном представлении компилятора ("IR"), чтобы предоставить возможность для оптимизации кода (этот термин объяснен ниже), улучшения компилятора, которые работают так, чтобы улучшить производительность этих примитивов, фильтрацию журнала работы с помощью ассоциативных таблиц и эффективные операции выполнения по каждому объекту. В то время как описания, предоставленные в данном документе, предоставлены в качестве оптимизаций отдельного осуществления программной транзакционной памяти, будет признано, что технологии и системы, описанные в данном документе, могут работать в разных осуществлениях, и необязательно предполагать какое-либо ограничение в осуществлении, производительности или требованиях технологий, описанных в данном документе.

1. Примеры системы программной транзакционной памяти

Атомарные блоки представляют обещанное упрощение проблемы записи параллельных программ. В системах, описанных в данном документе, блок кода обозначается атомарным, и компилятор и исполняющая система обеспечивают то, что операции в блоке, включающие в себя вызовы функций, являются атомарными. Программисту больше не нужно беспокоиться о ручной блокировке, низкоуровневых режимах состязаний или взаимных блокировках. Атомарные блоки могут также обеспечивать восстановление исключений, посредством чего действия со стороны блока откатываются, если исключение прекращает его. Это является значимым даже в однопотоковом приложении: код обработки ошибки часто трудно записать или протестировать. Осуществления атомарных блоков масштабируются на многопроцессорные машины, поскольку они сохраняют параллелизм: атомарные блоки могут выполняться одновременно при условии, что ячейка, обновляемая в одном блоке, не доступна в любом другом месте. Это сохраняет вид совместного использования, разрешенный в традиционном кэше данных.

Технологии, описанные в данном документе, сделаны со ссылкой на осуществление STM, которое тесно объединено с компилятором и исполняющей системой. Одним признаком осуществления является то, что это является STM с прямым обновлением. Это позволяет объектам обновляться непосредственно скорее в динамически распределяемой области памяти, чем работать в частных точных копиях объектов или через дополнительные уровни между ссылкой на объект и содержимым текущего объекта. Это более эффективно для транзакций, которые успешно фиксированы.

Системы и технологии, описанные в данном документе, используют признак осуществления, который предоставляет декомпозированный интерфейс STM. Например, поле obj.field=42 транзакционной памяти разбивается на этапы, которые (a) делают запись о том, что объект обновляется текущим потоком, (b) регистрируют старое значение, которое удерживалось в поле, и (c) сохраняют новое значение 42 в поле. Этот новый замысел позволяет предоставлять классические оптимизации в транзакционных операциях. Например, три этапа в нашем примере управляются отдельно компилятором, и этапы (a) и (b) могут часто подниматься из цикла. В технологиях, описанных в данном документе, декомпозированный интерфейс STM сделан более эффективным посредством использования компилятора с определенным знанием интерфейса STM и семантики, и который может выполнять оптимизации, которые сконфигурированы, чтобы действовать конкретно с этим интерфейсом.

В другом примере системы и технологии, описанные в данном документе, иллюстрируют действия в описанном осуществлении STM посредством эффективных операций с каждым объектом, которые используют объединенный транзакционный контроль версий. Эти осуществления используют объединение транзакционного контроля версий с существующим заголовком объекта. Это отличается от других систем STM, так как эти системы либо используют внешние таблицы записей контроля версий, дополнительные слова заголовков, либо уровни преобразования логических адресов в физические между ссылками на объект и текущим содержимым объекта. Эти подходы вызывают плохую локальность кэша или увеличивают использование пространства. Осуществление, описанное в данном документе, использует наполненное слово заголовка вместе с эффективными инструкциями моментального снимка памяти, которые предоставляют возможность быстрой верификации изменений объекта в то время, когда фиксируется транзакция.

Кроме того, описывается фильтрация журнала выполнения. Фильтрация полезна, так как не все ненужные операции STM могут быть идентифицированы статистически в момент компиляции.

В одном осуществлении примеры, описанные в данном документе, осуществлены в компиляторе Бартока, оптимизирующем компиляторе с предварительным поиском и исполняющей системе для программ на общем промежуточном языке (CIL) с производительностью, конкурирующей с платформой Microsoft.NET. Исполняющая система может быть осуществлена в CIL, включая в себя программы очистки памяти и новую STM.

1.1. Семантика

Технологии, описанные в данном документе, фокусируются на производительности атомарных блоков. Различные осуществления могут отличаться точной семантикой, включающей в себя взаимодействие атомарных блоков с кодом блокировки и объединением операций ввода/вывода с атомарными блоками при продолжении использования этих технологий.

1.2. Допущения проекта

В примерах, описанных в данном документе, сделаны некоторые предположения о том, как будут использоваться атомарные блоки. Они необязательно представляют ограничения в осуществлениях, описанных в данном документе, а вместо этого служат для того, чтобы упростить описание.

Одним предположением является то, что большинство транзакций фиксируются успешно. Это является приемлемым предположением, поскольку, во-первых, использование сохраняющей параллелизм STM означает, что транзакции не будут прекращаться 'спонтанно', или из-за конфликтов, которые программист не может понять (в альтернативных вариантах осуществления конфликты обнаруживаются на основе значений хэш-функции, с которыми могут неожиданно сталкиваться). Предполагается, как часть этого, что программист уже имеет сильный стимул избежать конфликтной ситуации из-за расходов на излишнее перемещение данных между кэшами. Технологии, такие как операции с высокой конкуренцией передачи в очереди обработки, управляемые одним потоком, остаются полезными.

Вторым предположением является то, что операции чтения превышают по численности обновления в атомарных блоках. Это предположение подкрепляется наблюдениями текущих программ и попытками разработать их транзакционные версии. Это акцентирует пользу сохранения накладных расходов на транзакционные операции чтения очень низкими: чтения затрагивают просто регистрацию адреса читаемого объекта и содержимое его слова заголовка.

Конечным предположением является то, что размер транзакции не должен быть ограничен. Это сохраняет композиционность при предложении того, что осуществление STM нужно также масштабировать, когда растет длина транзакций. В этом проекте накладные расходы на пространство растут с величиной объектов, к которым осуществляется обращение в транзакции, а не с числом сделанных обращений. В этих примерах, описанных в данном документе, транзакции неформально называются "короткими" и "длинными". Короткие транзакции, вероятно, работают без необходимости какого-либо распределения памяти посредством STM. Длинными транзакциями являются те, чье выполнение, вероятно, должно охватывать GC-циклы (например, оценку одного из эталонных тестов LISP в версии эталонного теста xlip SPEC95, который был транслирован в C#).

1.3. Пример STM на основе слова

Один традиционный интерфейс для STM на основе слова предоставляет следующие два набора операций:

void TMStart()

void TMAbort()

bool TMCommit()

bool TMIsValid()

word TMRead(addr addr)

void TMWrite(addr addr, word value)

Первый набор используется, чтобы управлять транзакциями: TMStart начинает транзакцию в текущем потоке. TMAbort прерывает транзакцию текущего потока. TMCommit пытается фиксировать транзакцию текущего потока. Если транзакция не может быть фиксирована (например, в одном осуществлении из-за того, что параллельная транзакция обновила одну из ячеек, к которой она обращалась), тогда TMCommit возвращает ложное значение, и текущая транзакция отвергается. Иначе TMCommit возвращает истинное значение, и любые обновления, которые были сделаны во время транзакции, атомарно распространяются на совместно используемую динамическую область памяти. TMIsValid возвращает истинное значение, если и только если транзакция текущего потока может быть фиксирована в момент вызова. Второй набор операций выполняет обращения к данным: TMRead возвращает текущее значение конкретной ячейки или наиболее последнее значение, записанное посредством TMWrite в текущей транзакции.

В одном осуществлении технологий, описанных в данном документе, процесс программирования напрямую с STM автоматизирован за счет наличия обращений компилятора к перезаписываемой памяти в атомарных блоках, чтобы использовать операции STM, и его необходимости формировать специализированные версии вызванных методов, чтобы гарантировать, что TMRead и TMWrite используются для всех обращений к памяти в атомарном блоке.

Проект, описанный выше, страдает от ряда проблем, которые ограничивают его применимость. Следующие примеры кода иллюстрируют это: Пример 1a, показанный ниже, выполняет итерацию по элементам связанного списка между сигнальными узлами this.Head и this.Tail. Он суммирует значения полей узлов и сохраняет результат в this.Sum. Пример 1b иллюстрирует один пример автоматически размещаемых вызовов TMRead и TMWrite для всех обращений к памяти.

Однако несколько проблем производительности могут произойти с этой системой на основе слова. Во-первых, многие осуществления TMRead и TMWrite используют журналы транзакций, которые исследуются по каждой операции TMRead и TMWrite. TMRead должен видеть более ранние сохранения посредством той же транзакции, таким образом, он исследует журнал транзакций, который хранит пробные обновления. Такое исследование не может масштабироваться для поддержки больших транзакций. Производительность зависит от длины журнала транзакций и эффективности структур вспомогательных указателей. Во-вторых, непрозрачные вызовы библиотеки STM препятствуют оптимизации (например, больше невозможно поднимать чтение this.Tail из цикла, так как характер TMRead не известен компилятору). В заключение, монолитные операции TM вызывают повторную работу. Например, повторяющиеся исследования при обращении к полю в цикле.

1.4. STM с декомпозированным прямым доступом

Осуществление STM с декомпозированным прямым доступом, которое используется в примерах, предоставленных выше, обходит эти проблемы. Первая проблема обходится системами проектирования так, что транзакция может выполнять операции чтения и записи непосредственно в динамической области памяти, давая возможность чтению легко видеть предшествующее транзакционное сохранение без какого-либо поиска. Журналы все еще нужны для отката транзакции, который отменяет и отслеживает информацию о версии ячеек, к которым осуществлен доступ. Для коротких транзакций эти журналы являются только дополняемыми. Таким образом, поиск не требуется, невзирая на размер транзакции.

Вторая проблема обходится введением TM-операций своевременно во время компиляции и продолжения фаз последующего анализа и оптимизации, чтобы знать об их семантике. В заключение, третья проблема обходится разбиванием монолитных TM-операций на отдельные этапы так, что повторяющаяся работа может быть отменена. Например, управление журналами транзакций отделяется от фактических обращений к данным, часто позволяя управлению журналом подниматься из циклов.

Этот интерфейс делит операции с транзакционной памятью на четыре набора:

tm_mgr DTMGetTMMgr()

void DTMStart (tm_mgr tx)

void DTMAbort(tm_mgr tx)

bool DTMCommit(tm_mgr tx)

bool DTMIsValid(tm_mgr tx)

void DTMOpenForRead(tm_mgr tx, object obj)

void DTMOpenForUpdate (tm_mgr tx, object obj)

object DTMAddrToSurrogate(tra_mgr tx, addr addr)

void DTMLogFieldStore (tm_mgr tx, object obj, int offset)

void DTMLogAddrStore(tm_mgr tx, addr obj)

Первые два набора являются прямыми, представляя DTMGetTMMgr, чтобы получить менеджер транзакций текущего потока, и, далее, представляя обычные операции управления транзакциями. Третий набор обеспечивает обнаружение конфликтной ситуации: DTMOpenForRead и DTMOpenForUpdate указывают, что к конкретному объекту можно обращаться только в режиме чтения, и что он может быть впоследствии обновлен. Доступ к статическим полям опосредован замещающими объектами, которые хранят информацию о версии от их лица: DTMAddToSurrogate отображает адрес на своего заместителя. Последний набор сохраняет журнал отката, необходимый, чтобы откатить обновления при преждевременном прекращении. DTMLogFieidstore имеет дело с сохранением в поля объектов, а DTMLogAddrstore имеет дело с сохранением по какому-либо адресу.

Вызовы этих операций должны быть корректно упорядочены, чтобы обеспечить атомарность. Существуют три правила: (a) ячейка должна быть открыта для чтения, когда она читается, (b) ячейка должна быть открыта для обновления, когда она обновляется или сохраняет журнал для него, (с) старое значение ячейки должно быть зарегистрировано в журнале перед тем, как оно обновляется. На практике это означает, что вызов в TMRead для поля объекта делится на последовательность DTMGetTMMgr, DTMOpenForRead и затем чтение поля.

TMWrite является последовательностью DTMGetTMMgr, DTMOpenForUpdate, DTMLogAddstore и затем запись поля. Вызов в TMRead для статического поля делится на последовательность DTMGetTMMgr, DTMAddrToSurrogate, DTMOpenForRead и затем чтение статического поля. TMWrite является последовательностью DTMGetTMMgr, DTMAddrToSurrogate, DTMOpenForUpdate, DTMLogAddstore и затем запись статического поля.

Следующие примеры демонстрируют пример использования STM с декомпозированным прямым доступом. Код в примере 1a выполняет итерацию элементов связанного списка между сигнальными узлами this.Head и this.Tail. Он суммирует поля Значения узлов и сохраняет результат в this.Sum. Пример 2 показывает, как Sum может быть осуществлена с помощью STM с декомпозированным прямым доступом.

Пример 1a

Пример 1b

Пример 2

2. Оптимизации в процессе компилирования

Секция 2 описывает оптимизацию декомпозированных операций STM с помощью компилятора, который сконфигурирован со знанием операций STM. Следует заметить, что в качестве используемых в данной заявке термины "оптимизировать", "оптимизированный", "оптимизации" и подобные являются терминами области техники, которые, как правило, ссылаются на улучшение без ссылки на какую-либо определенную степень улучшения. Таким образом, в разных сценариях, в то время как "оптимизация" может улучшить один или более аспектов производительности системы или техники, она необязательно требует, чтобы каждый аспект системы или технологии был улучшен. Дополнительно, в различных ситуациях "оптимизация" необязательно подразумевает улучшение какого-либо аспекта до какой-либо определенной минимальной или максимальной степени. Кроме того, в то время как "оптимизированная" система или технология могут показывать улучшение производительности в одной или более областях, она может также показать снижение в производительности в других областях. В заключение, в то время как "оптимизация" может улучшить производительность системы или технологии в некоторых ситуациях, может быть возможно, что она уменьшает производительность в других ситуациях. В определенных обстоятельствах, описанных ниже, в то время как оптимизации будут иметь результатом удаление излишних или ненужных инструкций STM или журнальных записей, возможно предоставление улучшенной производительности, эти оптимизации должны подразумевать, что каждые возможные избыточные или ненужные инструкции будут удалены.

Фиг.1 является блок-схемой, иллюстрирующей один пример компилятора 100, используемого для того, чтобы создать оптимизированную программу 120, использующую программную транзакционную память. В иллюстрированном примере компилятор 100 рассматривается как входной исходный код 110. Как иллюстрировано, исходный код 110 содержит один или более атомарных блоков 115. Как упоминалось выше, в одном осуществлении включение в состав таких атомарных блоков отменяет дополнительное программирование для программиста, желающего использовать STM; эти блоки модифицируются компилятором так, чтобы включать в себя декомпозированные инструкции STM, которые затем оптимизируются. В то время как Фиг.1 иллюстрирует один участок исходного кода, следует принимать во внимание, что это представлено только для упрощения иллюстрирования; технологии и системы, описанные в данном документе, применяются также к множественным файлам исходных кодов, которые компилируются вместе, также как и к исходному коду, который использует уже скомпилированный код. Дополнительно, в различных осуществлениях используются разные кодовые языки, включающие в себя C++, C#, Java, C и другие; также, в различных осуществлениях интерпретируемые языки также могут быть оптимизированы. В иллюстрированном примере эта оптимизация обеспечивается оптимизациями 150 STM, которая интегрирована в компиляторе, дополнительные детали этой интеграции обсуждаются ниже. После компиляции и оптимизации создается оптимизированная программа 120, которая использует программную транзакционную память. Дополнительные детали операций исполнения такой оптимизированной программы описаны более подробно ниже. Дополнительно, в то время как иллюстрированное осуществление показывает компиляцию в исполняемый файл перед выполнением, альтернативные осуществления технологий, описанных в данном документе, могут компилировать и оптимизировать программы непосредственно перед или параллельно с выполнением.

Фиг.2 является блок-схемой, иллюстрирующей примерные компоненты компилятора 100 на Фиг.1. Фиг.2 иллюстрирует примерный путь операции через компилятор. В то время как Фиг.2 иллюстрирует определенные модули отдельно, следует принимать во внимание, что в различных осуществлениях модули могут быть соединены или разделены в различных комбинациях. Путь начинается с первого модуля 220 компилятора, который принимает исходный код 110 и создает из него промежуточное представление 230. В одном осуществлении это IR принимает форму графа управляющего процесса ("CFG"), который позволяет легко управлять им посредством оптимизирующих технологий, описанных в данном документе.

Далее, IR 230 модифицируется модулем 240 оптимизации, чтобы создать оптимизированное IR 250. В этой операции модуля 240 оптимизации традиционные оптимизации в процессе компилирования расширяются с помощью низкоуровневых и высокоуровневых характерных для STM оптимизаций. Примеры таких оптимизаций будут описаны более подробно ниже. В заключение, оптимизированное IR 250 компилируется вторым модулем 260 компилятора в исполняемый код, такой как оптимизированная программа 120 на Фиг.1.

Фиг.3 является блок-схемой примерного процесса 300 компиляции и выполнения программы, использующей STM. В различных осуществлениях этапы иллюстрированного процесса могут быть объединены, разделены на подэтапы или опущены. Процесс начинается на этапе 320, где принимается исходный код, содержащий блоки транзакционной памяти (такие как атомарные блоки на Фиг.1). В альтернативном осуществлении исходный код может не содержать блоков транзакционной памяти, а вместо этого будет содержать индивидуальные инструкции программной транзакционной памяти, такие как построенные на слове или декомпозированные инструкции, описанные выше. Далее, на этапе 340 этот исходный код компилируется в исполняемую программу. Конкретные примеры компиляции описываются более подробно ниже. В заключение, на этапе 360 исполняемая программа выполняется.

Фиг.4 является блок-схемой примерного процесса 400 компиляции исходного кода, который объединяет блоки транзакционной памяти. Процесс 400 соответствует этапу 340 на Фиг.3. В различных осуществлениях этапы иллюстрированного процесса могут быть объединены, разделены на подэтапы или опущены. Процесс начинается на этапе 420, где инструкции программной транзакционной памяти вставляются в каждый атомарный блок посредством компилятора 100. В одном осуществлении эта вставка выполняется посредством вставки подходящих основанных на слове STM-инструкций чтения и записи вокруг каждого события чтения или записи в блоке. В другом осуществлении, если программист решает вставить свои собственные STM-инструкции, процесс этапа 420 может быть опущен.

Далее, на этапе 440 основанные на слове STM-инструкции заменяются компилятором 100 на декомпозированные инструкции. В одном осуществлении, если исходный код, принятый компилятором, содержит уже декомпозированные инструкции, процесс этапа 440 пропускается. Дополнительно, в некоторых осуществлениях процессы блоков 420 и 440, в частности, могут быть объединены, чтобы вставить декомпозированные STM-инструкции непосредственно в ответ на прием атомарного блока. Пример 2, выше, иллюстрирует, что часть кода может выглядеть как после работы процесса этапа 440.

В другом осуществлении процесса этапа 440 компилятор дополнительно уменьшает расходы на управление журналом регистрации посредством декомпозиции журнальных операций, предоставляя возможность списания стоимости работы по управлению журналом регистрации по множественным операциям. В частности, в одном осуществлении операции DTMOpen* и DTMLog* начинаются с проверки того, что существует пространство в текущем массиве. Для DTMOpenForRead это только проверка того, что должно быть выполнено в версии кода с быстрым маршрутом. Чтобы амортизировать расходы на эти проверки, компилятор использует новую операцию, EnsureLogMemory, беря целое число, которое указывает, как много сегментов зарезервировать в данном журнале.

Характерные декомпозированные версии операций DTMOpen* и DTMLog* могут, таким образом, предположить, что пространство существует. Чтобы уменьшить регистрацию использования системных ресурсов во время выполнения в одном осуществлении операции EnsureLogMemory не являются аддитивными: две последующие операции резервируют запрошенный максимум, но не полностью. Для простоты, одно осуществление не устанавливает специализированные операции, где зарезервированное пространство потребуется после вызова или возврата. В другом осуществлении резервирования объединяются для всех операций между вызовами в каждом базовом блоке. В другом случае обратный анализ, который используется, чтобы интенсивно зарезервировать пространство заранее, насколько возможно, принуждается останавливаться во всех вызовах и заголовках циклов. Это имеет преимущество объединения большего числа резервирований, но может ввести операции резервирования в маршрутах, которые не требуют их.

На этапе 460 компилятор выполняет высокоуровневые оптимизации STM, включающие в себя введение операций строгой атомарности, перемещения и удаления необязательных STM-операций и удаление журнальных операций для новых создаваемых объектов. Этот процесс описан более подробно ниже. В заключение, на этапе 480 программа оптимизируется, включая в себя инструкции STM. В то время как процесс на Фиг.4 иллюстрирует высокоуровневые операции, за которыми следуют другие оптимизации в блоках 460 и 480, и не иллюстрирует повторение оптимизаций, в некоторых осуществлениях процессы в Фиг.460 и 480 или их подпроцессы могут быть выполнены в другом порядке, чем проиллюстрировано, и могут быть повторены. Одной причиной повторения является то, что определенные оптимизации могут раскрывать возможности для других оптимизаций. Таким образом, может быть желательно повторно выполнить оптимизации, чтобы получить пользу от возможностей, когда они могут возникать.

Фиг.5 является блок-схемой примерного процесса 500 выполнения высокоуровневых оптимизаций по инструкциям STM. Процесс 500 соответствует этапу 460 на Фиг.4. В различных осуществлениях блоки иллюстрированного процесса могут быть объединены, разделены на подэтапы или опущены. В одном осуществлении процесс 500 выполняется перед оптимизациями в процессе компилирования процесса 600, описанного ниже с тем, чтобы операции, добавленные посредством высокоуровневых оптимизаций, могли быть дополнительно оптимизированы компилятором. Процесс начинается на этапе 520, где компилятор вводит операции для строгой атомарности. Далее, на этапе 540 операции для того, чтобы открыть объекты для чтения, за которыми следуют операции, чтобы открыть те же объекты для обновления, заменяются операциями открытия для обновления, чтобы позволить последующее удаление операций открытия во время последующей оптимизации. В одном осуществлении эти операции открытия-для-чтения, за которыми следуют операции открытия-для-обновления, называются модернизациями чтения-для-обновления; процесс этапа 540 удаляет эти модернизации. Далее, на этапе 560, декомпозированные STM-операции перемещаются по вызовам процедур, чтобы предоставить большие оптимизации в процессе на Фиг.6. В заключение, на этапе 580 операции записи в журнал объектов, которые заново создаются в транзакциях, для которых они протоколируются, удаляются, чтобы предотвратить ненужные вызовы операции записи в журнал. Отдельные примеры каждого из этих процессов описаны более подробно ниже относительно Фиг.7-12.

2.1. Оптимизации в процессе компилирования по декомпозированному коду

Фиг.6 является блок-схемой примерного процесса 600 выполнения оптимизаций по инструкциям STM. Процесс 600 соответствует этапу 480 на Фиг.4. В различных осуществлениях блоки иллюстрированного процесса могут быть объединены, разделены на подэтапы или опущены. Дополнительно, в то время как илл