Результат интеллектуальной деятельности: КОНТЕКСТНО-ЗАВИСИМОЕ РАССЛАИВАНИЕ ДЛЯ ДИНАМИЧЕСКОЙ ПАРАЛЛЕЛИЗАЦИИ ДВОИЧНЫХ ПРОГРАММ

Область техники, к которой относится изобретение

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

Уровень техники

Программное расслаивание может определять набор программных операторов (например, индивидуальных машинных инструкций), которые влияют на правильность указанного оператора, называемого критерием расслаивания в программе. Срез может состоять из операторов, от которых зависит критерий расслаивания. Например, срез программы в отношении машинной инструкции S может включать в себя набор или поднабор машинных инструкций, от которых зависит инструкция S, для правильного внедрения входных значений. Срез может относиться или может не относиться к инструкциям, включенным в определенную область кода. Такая область может включать в себя, например, статическое представление часто исполняемого сегмента кода.

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

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

Срезы могут быть контекстно-независимыми или контекстно-зависимыми. Для выполнения контекстно-независимого расслаивания, статический обратный срез относительно заданной инструкции может быть построен следующим образом. Граф зависимости программы (PDG) формируют на основе информации о зависимости данных статического однократного назначения (SSA) и рассчитанной информации зависимости управления. Анализ достижимости обратного графа может быть затем выполнен по PDG, начиная с инструкции критерия. Однако контекстно-независимое расслаивание может игнорировать контекст вызова функции (например, контура возврата, контура вызова и/или псевдоконтур неосуществленного прохода, все из которых описаны ниже), и может предоставлять набор срезов, которые слишком велики, намного больше, чем эквивалентный контекстно-зависимый срез. Большой размер среза может отрицательно влиять на попытки автоматической параллелизации.

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

На фиг. 1(a) показан образец кода программного источника, где функцию "квадрат" вызывают дважды в операторах 2 и 5. Соответствующий PDG показан на фиг. 1(b). При контекстно-независимом расслаивании срез для оператора 3 включает в себя 1, 2, 3, 4, 5, 7, 8, и срез для оператора 6 включает в себя 1, 2, 4, 5, 6, 7, 8. Однако оператор 3 не обязательно должен зависеть от 4 и 5, поскольку 4 и 5 выполняются после 3. Оператор 6 не обязательно должен зависеть от 1 и 2, поскольку значения, рассчитанные по 1 и 2, делают менее значимыми или не значимыми в 4 раза, перед тем, чем как будет достигнут оператор 6. Этот пример иллюстрирует различные недостатки обычных технологий расслаивания.

Краткое описание чертежей

На приложенных чертежах, вместе с описанием изобретения, поясняются такие различные варианты осуществления изобретения. На чертежах:

на фиг. 1 показана блок-схема для обычного способа расслаивания;

на фиг. 2 показана блок-схема способа расслаивания в одном варианте осуществления изобретения;

на фиг. 3 показана блок-схема способа расслаивания в одном варианте осуществления изобретения;

на фиг. 4 представлен псевдокод для способа расслаивания в одном варианте осуществления изобретения;

на фиг. 5 показана блок-схема системы для использования с одним вариантом осуществления изобретения.

Осуществление изобретения

В следующем описании представлены различные конкретные детали. Однако следует понимать, что варианты осуществления изобретения могут быть выполнены на практике без этих конкретных деталей. В других случаях хорошо известные схемы, структуры и технологии не были представлены подробно, с тем, чтобы не мешать пониманию данного описания. Ссылки на "один вариант осуществления", "вариант осуществления", "примерный вариант осуществления", "различные варианты осуществления" и т.д., обозначают, что вариант (варианты) осуществления изобретения, описанные таким образом, могут включать в себя определенные свойства, структуры или характеристики, но не каждый вариант осуществления обязательно включает в себя определенные свойства, структуры или характеристики. Кроме того, некоторые варианты осуществления могут иметь некоторые, все или ни одни из свойств, описанных для других вариантов осуществления. Кроме того, используемое здесь, если только не будет указано другое, применение обычных прилагательных "первый", "второй", "третий" и т.д., для описания общего объекта, просто обозначает, что делается ссылка на разные экземпляры одинаковых объектов, и не предназначены для подразумевания того, что объекты, определенные таким образом, должны иметь определенную последовательность, либо временную, пространственную или ранжирующую, или любую другую.

В одном варианте осуществления изобретения контекстно-зависимый алгоритм или способ могут улучшаться при использовании способов расслаивания. Например, на фиг. 2(a) представлен тот же код, который показан на фиг. 1(a). Однако, в отличие от контекстно-независимой обработки кода, в результате которой получают срез, показанный на фиг. 1(b), вариант осуществления улучшенного, контекстно-зависимого способа, может найти два среза, представленные, соответственно, на фиг. 2(b) и (с). В отличие от большого, громоздкого одиночного среза на фиг. 1(b), два среза на фиг. 2(b) и (с) также могут быть выполнены независимо, параллельно, но с повышенной эффективностью по сравнению с обычными способами, например, из-за уменьшенных размеров срезов.

Таким образом, варианты осуществления изобретения включают в себя технологию анализа программы, которую можно использовать для обеспечения контекстно-зависимого расслаивания двоичных программ для представления, для расслаивания активных областей, идентифицированных во время работы, при использовании небольшого количества лежащих в основе предположений о программе, из которой была получена данная двоичная последовательность. Варианты осуществления изобретения могут предоставлять значения для продуктов на двоичной основе, которые основаны на расслаивании программы, в качестве меры для обеспечения связанности и параллелизма программы. Такое значение может быть предусмотрено, в качестве примера инфраструктуры параллелизации на основе расслаивания, для улучшения автоматического параллелизма для последовательного обеспечения рабочих характеристик в одном потоке во время выполнения. Кроме того, варианты осуществления изобретения могут принимать несколько или могут не принимать предположений о структуре оцениваемой программы. И при этом определенные варианты осуществления не требуют вспомогательных метаданных, таких, как информация о символах или отладки. Как таковые, варианты осуществления могут быть применимы не только для традиционных двоичных кодов программы, но также и к другим исполнительным последовательностям, таким как трассы микрооперации (micro-op) или потоки, формируемые во время выполнения. Трассы micro-op могут включать в себя детальные инструкции низкого уровня, используемые для выполнения сложных машинных инструкций. Таким образом, варианты осуществления изобретения могут обеспечивать технологию, которая работает на произвольных двоичных потоках и, поэтому, обеспечивает преимущество контекстно-зависимого расслаивания, как для систем с динамической оптимизацией, так и для инфраструктур виртуализации.

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

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

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

Результаты такой предварительной обработки можно найти на фиг. 3. На фиг. 3(a) снова представлен тот же иллюстративный код, который можно найти на фиг. 1(a) и 2(a). Однако, фигура 3(b) включает в себя CFG для образца программы, показанной на фиг. 3(a), после того, как следующие этапы предварительной обработки будут выполнены. В частности, предварительная обработка может быть выполнена следующим образом, в одном варианте осуществления изобретения. Вначале, выполняют проход CFG, для определения всех узлов, которые представляют собой инструкции 305, 310 вызова процедуры или эквивалентные действия. Возможные примеры таких эквивалентных действий могут включать в себя механизмы вызова исключений, в результате чего получают родственные совместные процедуры и, возможно, другие передачи потока обработки, которые определяют новый контекст, в дополнение к изменению управления. Для каждого из этих узлов исходящие контуры узла могут быть помечены, как контуры 315, 320 вызова, и соединения могут быть выполнены с узлом, представляющим инструкцию, непосредственно следующую после этих инструкций (в порядке двоичного кода программы, а не в порядке динамического исполнения). Такие соединения могут быть помечены, как псевдоконтуры 325, 330 неосуществленного прохода. Псевдоконтур неосуществленного прохода обозначает "инструкции вызова", возвращающие к инструкции, выполняемой в некоторой точке в будущем. Кроме того, CFG проходит для определения некоторых или всех узлов, которые представляют инструкции 335 возврата процедуры или эквивалентные действия. Примеры таких эквивалентных действий могут включать в себя возврат из блоков исключения, в результате чего получают родственную совместную процедуру, или передачу потока управления, для которой известно, что она закрывает контекст в дополнение к изменению управления потока. Для каждого из этих узлов исходящие контуры 340, 345 узла могут быть помечены, как возвратные контуры.

Для модифицирования CFG 300, на фиг. 3(c) вариант осуществления изобретения начинается с пересечения в требуемом узле критерия среза (например, в узле 6) и вычисления обратного среза. Возвратные контуры 340, 345 в CFG наблюдают. Вариант осуществления способа может выполняться поперек возвратных контуров 340, 345 и может инициировать начало рекурсивного подсреза в хвостовой инструкции 6 возвратного контура 345. Рекурсивный подсрез может представлять участок общего среза, который во время вычислений возникает в подконтексте программы. Определенные контуры могут быть игнорированы во время расчета подсреза для обеспечения такого поведения. Например, во время расчета рекурсивного подсреза, в соответствии с различными вариантами осуществления изобретения, могут игнорироваться любые встретившиеся контуры вызова. В определенных вариантах осуществления способа, таким образом, не требуется использовать контуры вызова, для инициирования рекурсивных подсрезов на основе метаданных, которые отображают цели вызова на корневые узлы процедуры.

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

В частности, подробный переход предварительно обработанного CFG 300 на фиг. 2(c) теперь не предусмотрен. Переход обозначен номерами, обозначающими порядок перехода в варианте осуществления способа с обратным расслаиванием. Для расчета обратного расслаивания, начинающегося в узле 6, могут быть выполнены следующие этапы, в то время, как flowln и flowOut представляют собой находящиеся внутри и находящиеся снаружи наборы для заданного узла инструкции.

Во-первых, набор flowln для узла 6 устанавливают в {b}, и инициируют рекурсивный подсрез через контур 345 возврата, начинающуюся в узле 8. Во-вторых, в этом рекурсивном вызове flowln, установленный для узла 8, устанавливают в {b, а}. Поскольку узел 8 определяет b, узел 8 добавлен к срезу, и предшествующий узлу 8 узел 7 добавляют к рабочему списку. В-третьих, flowOut для узла 7 устанавливают равным объединению набора flowln в его инструкциях-преемниках, которые в данном примере представляют собой только узел 8 с flowln {b, a}. Поскольку узел 7 определяет b, который представлен в наборе flowOut для узла 7, его добавляют к срезу, и его flowln устанавливают в {а}. Узел 7 не имеет предшественников (когда контуры вызова игнорируют), и, таким образом, рекурсивный расчет подсреза заканчивается, и способ возвращается к узлу 6. В-четвертых, теперь, когда подсрез (см. аннотации 1-4 для узлов 6, 7, 8) был рассчитан, проход выполняют через узел 6, через его псевдоконтур 330 неосуществленного прохода и продолжают расслаивание. Это может быть выполнено путем добавления узла 5 к рабочему списку. В-пятых, узел 5 может рассчитать свой набор flowOut, путем просмотра набора flowln его узлов-преемников, который представляет собой узел 7 с flowln {а}. Поскольку узел 5 ничего не определяет, его набор flowln равен его набору flowOut {а}. Узел 5 добавляют к набору среза, поскольку его контур вызова в узел 7 рассматривается слабой формой зависимости управления и необходима для расчета исполняемых срезов. Узел 5 может добавлять своего предшественника, узел 4, к рабочему списку. В-шестых, узел 4 может рассчитывать свой набор flowOut, как представляющий собой {а}, набор flowln узла 5. Поскольку узел 4 определяет {а} и не ссылается ни на какие другие значения, его набор flowln равен {}. Узел 4 добавляют к срезу, поскольку он определяет {а}, который находится в его наборе flowOut. Учитывая, что узел 4 имеет нулевой набор flowln, узел 4 не добавляет каких-либо предшественников к рабочему списку. Поскольку больше ничего нет иного в рабочем списке, способ заканчивается. В-седьмых, рассчитанный срез для узла 6 представляет собой: {6, 8, 7, 5, 4}, что меньше, чем срез, представленный на фиг. 1(b), который для узла 6 составляет: {1, 2, 4, 5, 6, 7, 8}.

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

Фиг. 4 включает в себя псевдокод для способа расслаивания в одном варианте осуществления изобретения. В зависимости от начальной точки расслаивания, вариант осуществления изобретения может сталкиваться "с несбалансированными" возвратами и вызовами во время расслаивания. Это может произойти, когда расслаивание начинается ниже, чем наивысший уровень CFG, такой как в пределах функции входящего вызова, и достигает функции исходящего вызова. В этом случае, для способа может потребоваться выполнять расслаивания через несбалансированный контур вызова. На фиг. 4 функция оболочки sliceBackwards может обрабатывать такие случаи. Например, если исходная точка для расслаивания представляет собой наивысший уровень CFG, подсрез может обрабатывать контекстно-зависимое расслаивание для этой исходной точки. Однако, если исходная точка не находится на самом высоком уровне CFG, может возникнуть зависимость от начальной точки в пределах функции входящего вызова в отношении его функции исходящего вызова (например, через контур "несбалансированного" вызова).

В одном варианте осуществления подсрез может обрабатывать такой несбалансированный контур вызова, в случае, когда от начальной точки присутствует вызов, но нет соответствующего возврата, и может устанавливать контур вызова в (вызовы flowln) фиг. 4, линия 1, как результат подсреза. Таким образом, в некоторых вариантах осуществления контур вызова может быть игнорирован в по дерезе. Затем функция sliceBackwards может рекурсивно обрабатывать контур вызова, путем повторного вызова sliceBackwards для (вызовов flowln). В других вариантах осуществления подсрез может генерировать новую неразрешенную зависимость данных, для обработки которых требуется sliceBackwards. Однако такие неразрешенные зависимости могут принадлежать срезу текущей начальной точке. В других вариантах осуществления список неразрешенных зависимостей данных может поддерживаться, и sliceBackwards могут быть вызваны для каждой неразрешенной зависимости данных без необходимости рекурсии.

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

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

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

Варианты осуществления могут быть воплощены во множестве разных других типах системы. Рассматривая теперь фиг. 5, можно видеть блок-схему системы в соответствии с вариантом осуществления настоящего изобретения. Микропроцессорная система 500 представляет собой систему взаимного соединения из точки в точку, и включает в себя первый процессор 570 и второй процессор 580, соединенный через взаимное соединение 550 из точки в точку. Каждый из процессоров 570 и 580 может представлять собой многоядерные процессоры, включая в себя первое и второе ядра процессора (то есть, ядра 574а и 574b процессора и ядра 584а и 584b процессора), хотя потенциально еще большее количество ядер могут присутствовать в процессорах. Термин "процессор" может относиться к любому устройству или части устройства, которое обрабатывает электронные данные из регистров и/или памяти, для преобразования этих электронных данных в другие электронные данные, которые могут быть сохранены в регистрах и/или памяти.

Первый процессор 570 дополнительно включает в себя концентратор 572 контроллера памяти (МСН) и интерфейсы 576 и 578 "из точки в точку" (Р-Р). Точно так же, второй процессор 580 включает в себя МСН 582 и интерфейсы 586 и 588 Р-Р. МСН 572 и 582 соединяют процессоры с соответствующими запоминающими устройствами, а именно, запоминающим устройством 532 и запоминающим устройством 534, которые могут представлять собой участки оперативной памяти (например, динамического оперативного запоминающего устройства (DRAM)), локально закрепленного с соответствующими процессорами. Первый процессор 570 и второй процессор 580 могут быть соединены с набором 590 микросхем через взаимные соединения 552 и 554 Р-Р, соответственно. Поднабор 590 микросхем включает в себя интерфейсы 594 и 598 Р-Р.

Кроме того, поднабор 590 микросхем включает в себя интерфейс 592, для соединения набора 590 микросхем с графическим механизмом 538 высокой производительности, с помощью взаимного соединения 539 Р-Р. В свою очередь, набор 590 микросхем может быть соединен с первой шиной 516 через интерфейс 596. Различные устройства 514 ввода/вывода (I/O), могут быть соединены с первой шиной 516, вместе с мостом 518 шины, который соединяет первую шину 516 со второй шиной 520. Различные устройства могут быть соединены со второй шиной 520, включая в себя, например, клавиатуру/мышь 522, устройство 526 передачи данных и модуль 528 сохранения данных, такой, как привод диска, или другое устройство накопитель большой емкости, которое может включать в себя код 530, в одном варианте осуществления. Кроме того, аудио I/O 524 может быть соединен со второй шиной 520.

Варианты осуществления могут быть воплощены в коде и могут быть сохранены на носителе записи, на котором записаны инструкции, которые могут использоваться для программирования системы для выполнения инструкций. Носитель записи может включать в себя, но не ограничен этим, любой тип диска, включая в себя гибкие диски, оптические диски, оптические диски, твердотельные приводы (SSD), постоянные запоминающие устройства на компакт-дисках (CD-ROM), перезаписываемые компакт-диски (CD-RW) и магнитооптические диски, полупроводниковые устройства, такие как постоянные запоминающие устройства (ROM), оперативные запоминающие устройства (RAM), такие как динамические оперативные запоминающие устройства (DRAM), статические оперативные запоминающие устройства (SRAM), стираемые программируемые постоянные запоминающие устройства (EPROM), запоминающее устройство типа флэш, электрически стираемые программируемые постоянные запоминающие устройства (EEPROM), магнитные или оптические карты или носители любого другого типа, пригодные для сохранения электронных инструкций.

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

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