УСТРОЙСТВО И СПОСОБ ДЛЯ УСКОРЕНИЯ ОПЕРАЦИЙ СЖАТИЯ И РАСПАКОВКИ Российский патент 2017 года по МПК G06F9/30 H03M7/30 

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

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

Для обнаружения совпадений кодер отслеживает некоторое количество самых последних данных, таких как последние 2 кб, 4 кб или 32 кб. Структура, в которой эти данные содержаться, называется "окном скольжения" (таким образом, LZ77 иногда называют сжатием с использованием окна скольжения). Кодер содержит самые последние данные в окне скольжения для поиска совпадений (и декодер аналогично содержит эти данные для интерпретации совпадений, на которые ссылается кодер).

На фиг. 1 показан простой пример схемы кодирования LZ77. Как представлено на фиг.1, структуры битов предшествующего (раннего или более позднего) участка 101 в потоке 100 битов сравнивают с текущим участком 102 потока битов. Если в текущем участке 102 будет найдена последовательность битов, которая соответствует последовательности битов на предшествующем участке 101, эта последовательность битов на текущем участке 102 заменяется ссылкой на такую же последовательность битов на более раннем участке 101. Например, последовательность битов на текущем участке 102 могла бы быть заменена ссылкой на последовательность 103 битов на более раннем участке 101.

Ссылка, которую вставляют вместо последовательности 102 битов, идентифицирует длину 104 последовательности 102 битов (которая также является такой же, как и длина последовательности 103 битов) и местоположение последовательности 103 битов. Здесь местоположение последовательности 103 битов выражается, как "расстояние" 105 от текущего участка 102 до совпадающей последовательности 103 битов. При этом схема сжатия LZ77 кодирует последовательность 102 битов, как "пару длина - расстояние", которую вставляют в поток битов вместо последовательности 102. При декодировании сжатого потока, когда декодер достигает пары длина-расстояние, которая встроена в поток битов вместо последовательности 102 битов, он просто использует часть расстояния пары длина-расстояние для ссылки обратно на начало последовательности 103 битов и воспроизводит правильную последовательность битов для участка 102 декодированного потока путем воспроизведения множества битов от начала последовательности 103 битов, которая совпадает с компонентом длины для пары длина, расстояние.

Алгоритм сжатия DEFLATE. В схеме сжатия DEFLATE, которая используется для сжатия файлов gzip, Zlib, PKZip и WinZip, использует алгоритм сжатия LZ77 вместе с другими схемами сжатия для выполнения полной общей схемы сжатия.

На фиг. 2 показан обзор алгоритма сжатия DEFLATE. Как можно видеть на фиг.2, после сжатия LZ77, сжатый поток 200 битов можно рассматривать, как последовательность пар длина/расстояние 201_1, 201_2…201_М, которые смешаны с литералами 202_1, 202_2… 202_N. Литералы соответствуют структурам битов в пределах оригинального потока битов, для которых невозможно идентифицировать более раннюю идентичную структуру в пределах применимого окна для преобразования в пару длина/расстояние.

Алгоритм сжатия DEFLATE затем переходит к внедрению следующего уровня сжатия 203 для сжатого потока 200 LZ77. Следующий уровень сжатия 203 вводит два разных типа кодирования Хаффмана, которые вместе заменяют более общие структуры битов пар 201 длина/расстояние и литералов 202 меньшими кодами 204 и менее общими структурами битов пар 201 длина/расстояние и литералов 202 кодами 205 большего размера. Первый тип кодирования Хаффмана используется для кодирования литералов и значения длины. Второй тип кодирования Хаффмана используется для кодирования расстояния. В результате представления более общих структур битов для сжатого потока 200 LZ77 с меньшим количеством битов, общий размер информации, как представлено в конечном сжатом потоке 206 DEFLATE должен быть уменьшен.

Представление первого типа кодирования Хаффмана, используемого для литералов и значений длины, представлено на фиг. 3. Как можно видеть на фиг. 3, информация литералов разбита на основе байт за байтом. Поскольку байт соответствует 8 битам информации, существует разных значений байта литерала (от 0 до 255 в десятичном выражении). Каждое значение байта литерала соответствует узлу в дереве Хаффмана, где идентичность самих узлов 1:1 соответствует значениям литералов (то есть байт литерала 00000000 соответствует идентичности узла дерева Хаффмана, равной 0, байт литерала 00000001 соответствует идентичности узла дерева Хаффмана 1…, байт литерала 11111111 соответствует идентичности узла дерева Хаффмана 255).

Каждый из узлов дерева Хаффмана имеет ассоциированное значение кодирования, которое непосредственно вставляют в поток битов, как кодированный символ для этого байта литерала, соответствующего узлу дерева. Таким образом, например, узел 0 дерева Хаффмана имеет кодирование Хаффмана 00110000, и узел 255 дерева Хаффмана имеет кодирование Хаффмана 111111111. При этом байт литерала 00000000 в потоке 203 будет кодирован в сжатом битовом потоке 206 DEFLATE, как 00110000, и байт литерала 11111111 в потоке 203 будет кодирован в сжатом битовом потоке 206 DEFLATE, как 111111111. Следует отметить, что байт литерала 00000000 имеет более высокую вероятность возникновения, чем байт 11111111 литерала, и, таким образом, кодирование байта литерала 00000000 в потоке 200 занимает меньшее битовое пространство (00110000 содержит 8 битов) в конечном кодированном потоке 206 битов, чем кодирование байта 11111111 литерала в потоке 200 (111111111 содержит 9 битов).

Дерево Хаффмана также имеет узел с идентичностью 256. Этот узел соответствует возникновению в потоке 200 символа "конец блока" (ЕОВ). В схеме сжатия DEFLATE общие данные разбивают на меньшие блоки и разметка между соседними блоками помечена символом ЕОВ. Для простоты, символ ЕОВ не показан в потоке 200, и также не показано его кодированное значение в потоке 206.

Дерево Хаффмана включает в себя дополнительные 29 узлов, имеющие идентичности 257-285, которые используются для кодирования информации длины (размер окна) для пары длина - расстояние. Информация длины может составлять 3-258 байтов. Здесь идентичности 257-264 и 285 дерева соответствуют конкретным (и более часто встречающимся) значениями длины (в частности, идентичность 257 соответствует длине 3 байта, идентичность 258 соответствует длине 4 байта… и т.д. … идентичность 264 соответствует длине 10 байтов, и идентичность 285 соответствует длине 258 байтов). Каждое из значений идентичности 257-264 и 258 кодируются 6 битами или меньше (при этом более часто встречающиеся значения длины занимают меньше, чем 6 битов, и менее часто встречающиеся значения длины занимают вплоть до 6 битов.

Идентичности 265-284 дерева Хаффмана используются для установления диапазонов длины вместо конкретных значений длины. Здесь значения длины в пределах диапазона 11 байтов - 257 байтов устанавливают по идентичностям 265 - 284. Каждая идентичность узла дерева Хаффмана соответствует разному диапазону значений длины. Например, идентичность 265 соответствует диапазону длины от 11 до 12 байтов. В отличие от этого, идентичность 284 соответствует диапазону длины от 227 байтов до 257 байтов. Для установления конкретного значения длины из идентичности узла кода Хаффмана, которая соответствует диапазону значений длины, "добавляют дополнительные биты" для кодирования идентичности узла кода Хаффмана. Например, один дополнительный бит добавляют для кодирования идентичности 265 узла кода Хаффмана таким образом, что могут быть установлены два значения длины (от 11 до 12 байтов). В отличие от этого, 5 дополнительных битов добавляют к идентичности 284 узла кода Хаффмана таким образом, что 31 разных значений длины (то есть любое одно из значений длины 227-257, включительно) могут быть индивидуально установлены.

Следует отметить, что кодирование любой из идентичностей от 0 до 285 узла Хаффмана "не перекрывается", что означает, что их последовательности битов являются уникальными. Например, если одно из самых коротких значений кода составляет 1010, никакое другое из значений кода, более короткое или наоборот, не начинается с последовательности битов 1010. При этом, когда декодирует полностью кодированный поток битов, каждый отдельный кодированный символ можно легко распознать, и он может соответствовать только одной структуре из 8 битов, если она представляет собой литерал или значение длины. Как описано выше, некоторые кодированные значения длины имеют ассоциированные дополнительные биты. Как можно видеть в потоке 205, любые дополнительные биты прикрепляют к кодированным значениям длины. Таким образом, например, если конкретная последовательность битов будет распознана в потоке 205 декодером, как соответствующие идентичности 265 узла, тогда немедленно распознается, что следующий бит после установленной последовательности битов должен представлять собой дополнительный бит для этой идентичности узла. В качестве другого примера, если конкретная последовательность битов будет распознана в потоке 205 декодером, как соответствующая идентичности 284 узла, затем немедленно распознается, что следующие пять битов после конкретной последовательности битов должны представлять собой дополнительные биты для этой идентичности узла.

Значения расстояния кодируют в соответствии с аналогичной технологией, как и значения длины, но используют другое дерево Хаффмана (дерево Хаффмана второго типа, не показано). Второй тип дерева Хаффмана, используемый для расстояний, имеет 30 узлов вместо 286 (как при кодировании литерала/длины) и используется для кодирования любого расстояния от 1 байта до 32 768 байтов. И снова, более частые значения расстояния соответствуют меньшей идентичности узла дерева и меньшему количеству битов в кодированном символе, тогда как менее часто встречающиеся значения расстояния соответствуют более высокой идентичности узла дерева, большему количеству битов в кодированном символе и использованию дополнительных битов. Например, 30^-ый узел в дереве Хаффмана второго типа используется для установления любого расстояния в пределах диапазона от 16 385 байтов до 32 768 байтов, и 13 дополнительных битов используются совместно с кодированной структурой битов для 30^-ого узла, для установления конкретного одного из значений расстояния в пределах этого диапазона.

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

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

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

на фиг. 1 иллюстрируется примерная схема кодирования LZ77;

на фиг. 2 иллюстрируется один вариант осуществления алгоритма сжатия DEFLATE;

на фиг. 3 иллюстрируется представление первого типа кодирования Хаффмана, используемого для литералов и значений длины;

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

на фиг. 5 А иллюстрируется таблица литералов/значений длины (LL);

на фиг. 5 В иллюстрируется таблица расстояний (D);

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

на фиг. 7 иллюстрируется один вариант осуществления архитектуры исполнительного модуля;

на фиг. 8 иллюстрируется ядро обработки, воплощенное с логической схемой полупроводниковой микросхемы;

на фиг. 9 иллюстрируется архитектура примерного многоядерного процессора;

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

на фиг. 11А показана блок-схема, иллюстрирующая как примерный конвейер обработки по порядку, так и примерный конвейер задачи/исполнения, работающий не по порядку, с переименованием регистра, в соответствии с вариантами осуществления изобретения;

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

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

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

На фиг. 14 показана блок-схема примерной системы, в соответствии с вариантом осуществления настоящего изобретения;

На фиг. 15 показана блок-схема первой более конкретной примерной системы, в соответствии с вариантом осуществления настоящего изобретения;

На фиг. 16 показана блок-схема второй более конкретной примерной системы, в соответствии с вариантом осуществления настоящего изобретения;

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

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

Подробное описание изобретения

Для уменьшения размера памяти, занимаемой программным обеспечением в декодере DEFLATE, была предложена инструкция, которая может полностью декодировать кодированный символ DEFLATE в одной инструкции. Для воплощения такой технологии, инструкция разработана так, что она ссылается на табличную информацию, содержащую трансляцию/декодирование всех кодированных символов DEFLATE. В одном варианте осуществления, со ссылкой на фиг.4, инструкция: 1) принимает 401, указатель на определенное местоположение в кодированном потоке битов DEFLATE; 2) выбирает 402 часть (например, следующие 16 битов) кодированного потока битов DEFLATE от указанного местоположения; и 3) применяет 403, часть кодированного потока битов DEFLATE, в качестве входного параметра для внесенной в таблицу информации.

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

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

На фиг. 5A и 5B показаны элементы табличной информации. Табличная информация включает в себя как таблицу 501 литерал/значение длины (LL), как представлено на фиг.5A, так и таблицу 502 расстояния (D), как представлено на фиг. 5B. В варианте осуществления обе таблицы 501, 502 содержатся в системной памяти. В другом варианте осуществления обе таблицы 501, 502 содержатся в специальных схемах памяти с адресуемым содержанием, которые являются, например, локальными и частными для логических схем модулей исполнения инструкции или, более глобально, доступны для других схем в процессоре. Для удобства, в оставшейся части данной заявки ссылка, в основном, делается на вариант осуществления, где схемы САМ являются локальными и частными для логических схем модулей исполнения инструкции.

Модуль исполнения инструкции разработан так, чтобы он мог вырабатывать запрос на считывание к таблице 501 LL (и затем в таблице D, если ссылка на таблицу LL "сталкивается" с длиной), используя часть кодированной входной информации DEFLATE в качестве параметра поиска. Таблица LL 501 предоставляет декодированные компоненты литерала и значения длины для кодированного потока битов. В Таблице 502 D предоставляют декодированные компоненты расстояния кодированного потока битов.

Таблица LL 501 не только предоставляет декодированную информацию, но также и показатель, соответствует ли декодированная информация литералу или значению длины. Если декодированная информация представляет собой значение длины, инструкция автоматически выполняет поиск в таблице 502 D после того, как значение длины, и все из его дополнительных битов (если присутствуют) были обработаны. Здесь, при декодировании сжатого потока DEFLATE, расстояние автоматически следует после длины. При этом в аппаратных средствах известно, что после обработки битов длины (включая в себя все их дополнительные биты, если присутствуют), непосредственно должны следовать биты расстояния. Таблица D возвращает декодированное значение расстояния, которое инструкция должна возвращать, как второй результат, вместе с декодированной длиной.

В варианте осуществления каждый вход в любую таблицу 501, 502 соответствует определенному узлу дерева в пределах соответствующего дерева Хаффмана. Учитывая, что литералы и значения длины (первый тип) дерева Хаффмана содержат 285 узлов, в варианте осуществления, таблица 501 LL, поэтому, содержит 285 входов. Аналогично, учитывая, что дерево Хаффмана расстояния содержит 30 узлов, в варианте осуществления, таблица 502 D содержит 30 входов. Левая сторона каждого входа в обе таблицы содержит кодированное значение для соответствующего узла дерева Хаффмана. Схема САМ пытается найти соответствие этой информации при сравнении с участком входной информации, кодированной по алгоритму DEFLATE, обрабатываемой инструкцией, и используемой, как параметр поиска в САМ.

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

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

На фиг. 5A представлен вариант осуществления входа 520 в таблице 501 LL. Как можно видеть на фиг. 5, вход 520 включает в себя: 1) первое (с левой стороны) поле 511, которое содержит кодированную последовательность битов определенной части кодированной информации DEFLATE (которая представляет собой соответствующую информацию для входа САМ); 2) второе (с правой стороны) поле 512, которое содержит декодированную (оригинальную) информацию кодированной последовательности битов для литерала (если кодированный вход соответствует литералу); 3) третье поле 513, которое устанавливает размер кодированной последовательности битов (то есть в какой степени часть входной информации, кодированной по алгоритму DEFLATE, декодирована с использованием этого входа); 4) четвертое поле 514, которое обозначает, соответствует ли кодированная последовательность битов символу конец блока, литералу или значению длины, и применяются или нет дополнительные биты, если кодированный вход соответствует значению длины; 5) пятое поле 515, которое обеспечивает декодированную длину (если кодированный вход соответствует значению длины); и 6) шестое поле 516, которое обозначает количество применимых дополнительных битов (если кодированный вход соответствует значению длины).

В соответствии с одним вариантом осуществления, в котором используется структура входа по фиг.5, таблица LL содержит вход только для значений длины и литералов. Поскольку значения длины всегда предшествуют расстояниям в потоке, кодированном по алгоритму DEFLATE, при исполнении инструкции "известно", что, если возникает соответствие длины в таблице LL, следующий набор информации в кодированном потоке должен представлять собой расстояние. При этом модуль исполнения инструкций далее выполняет переход в таблицу 502 D на фиг. 5B для декодирования информации расстояния после приема входа для значения длины из таблицы 501 по фиг. 5A.

В варианте осуществления, на фиг. 5, 4 бита зарезервированы для поля 513 (таким образом, что могут быть установлены выходные декодированные размеры вплоть до 16 битов, при этом следует отметить, что значение поля 513 для входа 520 представляет собой значение восемь для обозначения того, что кодированные входные данные 511 входа 520 имеют размер восемь битов), и 2 бита зарезервированы для поля 514 (00=ЕОВ; 01=литерал; 10=длина, и дополнительные биты не используются; 11=длина с приложением дополнительных битов); 6 битов зарезервированы для поля 515, которое содержит "основу" декодирования для значения длины (то есть декодирование значения длины без дополнительных битов); и, 4 бита зарезервированы для поля 516, которое устанавливает, какое количество дополнительных битов применяется (если поле 514=11). В варианте осуществления фактические входы построены таким образом, что содержание поля 512 физически накладывается на содержание полей 515 и 516 (например, те же 10 битов во входе обеспечивают декодируемый литерал в случае литерала или основание размером из 6 битов и информацию из дополнительных 4 битов в случае значения длины).

Таким образом, в случае, когда декодированный символ соответствует значению длины, аппаратные средства, выполняющие инструкцию, получают информацию о том, следуют ли дополнительные биты после основания длины, и если это так, каково их количество. В ответ на это, если дополнительные биты отсутствуют, основное значение длины, содержащееся в поле 515, соответствует декодируемому значению длины, которое возвращают в качестве результата. Если присутствуют дополнительные биты, тогда аппаратные средства дополнительно выбирают правильное количество дополнительных битов из потока данных (поскольку они непосредственно следуют основной длине кодированного потока данных), и используют эти дополнительные биты в комбинации с основной длиной, возвращенной из таблицы LL, для определения конечной, полной длины, которая возвращается, как результат. Как упоминалось выше, следующая операция, которая должна быть выполнена аппаратными средствами, после того, как будет определена конкретная длина, должна выполнять второй поиск в таблице 502 D. Здесь, поскольку расстояние следует после значения длины при сжатии по алгоритму DEFLATE, логическая инструкция будет выбирать следующий сегмент потока битов на участке информации, кодированной по алгоритму DEFLATE, первоначально представленной в модуль исполнения инструкции, как входной операнд. Аппаратные средства исполнения инструкции применяют следующий сегмент входной кодированной информации DEFLATE для таблицы 502 D.

В варианте осуществления, как можно видеть на фиг. 5B, вход в таблицу 502 D форматируют так же, как (аналогично) вход длины в таблице 501 LL. В частности, поскольку расстояния имеют основные значения и также могут иметь дополнительные биты, входы в таблице 502 D напоминают входы 257-284 на фиг. 5A. Значение 530 типа обозначает, применяются или нет дополнительные биты (0 = отсутствие дополнительных битов; 1 = дополнительные биты). Если применяются дополнительные биты, декодированные по основанию поля 531 расстояния, декодированное расстояние представляют в качестве результата. Если дополнительные биты применяются, поле 533 информирует аппаратные средства о количестве применяемых дополнительных битов. Аппаратные средства инструкции затем анализируют дополнительные биты из колированного потока битов и, в комбинации с основным значением, предоставляют их, как декодированное полученное в результате расстояние.

На фиг. 6 показана первая обработка, описанная выше, выполняемая аппаратными средствами модуля исполнения инструкции. Как можно видеть на фиг.6, после приема указателя 601 для начальной части потока, кодированного по алгоритму DEFLATE, в качестве входного операнда (и, например, адреса, где можно найти кодированный поток в системной памяти), модуль исполнения инструкции выбирает часть потока 602, кодированного по алгоритму DEFLATE и представляет ее, как входной параметр, в первую схему САМ, имеющую таблицу 603 LL. Таблица LL возвращает вход, который обозначает, содержится ли на ведущем краю литерал или значение 604 длины.

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

Если ведущий край содержит значение длины, таблица LL возвращает основание декодированной длины и количество дополнительных битов, если они присутствуют. Исполнительный модуль выполняет последовательное приращение указателя 607, для учета, как основания декодированной длины (6 битов), так и дополнительных битов (если присутствуют) таким образом, что новое значение указателя указывают на ведущий край не кодированной информации, которая, как описано выше, указывает на значение расстояния. Следует отметить, что из-за присутствия дополнительных битов, не только в непосредственно в декодированном значении длины, но также и потенциально в значении расстояния, которое должно быть немедленно декодировано, количество кодированной информации DEFLATE может превышать часть информации DEFLATE, выборка которой была первоначально выбрана модулем выполнения инструкции. По существу, если новый указатель указывает на информацию, выборка которой должна быть выполнена, тогда модуль исполнения инструкции будет вырабатывать запрос на считывание в системной памяти дополнительной информации. В варианте осуществления, поскольку известно, что значение расстояния следует после значения длины, исполнительный модуль может выполнять выборку информации, находящейся после дополнительных битов в значении длины, по меньшей мере, в основном значении последующего расстояния и может соответственно регулировать указатель.

Независимо от того, будет ли выполнена выборка дополнительной кодированной информации DEFLATE или нет, после выборки всей информации для кодированной длины из кодированного потока DEFLATE выполняют поиск в первом ROM для преобразования основной длины и дополнительных битов (если присутствуют), введенных при кодировании Хаффмана, обратно в кодированную длину 608 LZ77.

Поиск в таблице 609 D также выполняется автоматически (его можно рассматривать, как часть обработки декодирования длины, выполняют последовательное приращение указателя до начала значения 607 расстояния, и даже может быть выполнена выборка кодированной информации DEFLATE после значения длины и его дополнительных битов (если присутствуют), для захвата, по меньшей мере, основного компонента следующего кодированного значения расстояния, и указатель соответственно обновляют). Часть кодированной информации о расстоянии DEFLATE затем представляют в таблице D, которая возвращает основание декодированного расстояния и количество дополнительных битов (если присутствуют) 609. Модуль исполнения инструкции затем выбирает дополнительную кодированную информацию DEFLATE, чтобы, по меньшей мере, охватить дополнительные биты (если имеются), и, соответственно, обновить указатель. Когда получают кодированное основные и дополнительные биты, и указатель обновляют до точки начала следующего кодированного символа в потоке DEFLATE, после кодированной информации 610 расстояния, исполнительный модуль выполняет поиск в установленном ROM для декодирования расстояния Хаффмана в расстояние 611 LZ77.

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

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

В дополнительном варианте осуществления исполнительный модуль разработан с возможностью записи флагов в пространство регистра управления для обозначения: 1) пара длина/расстояние была возвращена, как результат; 2) встретился ЕОВ; 3) требуется ли повторное выполнение какой-либо части инструкции. Последний флаг соответствует возможности "частичного выполнения" модулей исполнения инструкции. В частности, возможно, что доступ к памяти, выполняемый модулем исполнения инструкции, мог привести к некоторому виду ошибки. В этом случае, модуль исполнения инструкции возвращает в качестве своего результата, значение указателя, и в этой точке обработка декодирования должна быть повторно запущена. В одном варианте осуществления такое значение указателя может представлять собой начало значения расстояния, когда инструкция была выполнена, с возможностью успешного декодирования значения длины.

На фиг. 7 показан вариант осуществления конструкции логической схемы для исполнительного модуля 700. Как можно видеть на фиг. 7, логическая схема включает в себя логическую схему 701 конечного автомата, которая контролирует/обеспечивает характеристики различных описанных выше методик. Конечный автомат 701 принимает входной указатель, как входной операнд из пространства регистра. Модуль исполнения инструкции включает в себя логику 702 запроса памяти для выработки запросов на считывание из памяти следующих частей кодированной информации DEFLATE в системной памяти. Модуль исполнения инструкции также включает в себя первую и вторую схемы 703, 704 САМ для воплощения упомянутых выше таблиц LL и D. Модуль исполнения инструкции также включает в себя первую и вторую схемы 705, 706 ROM для воплощения преобразований Хаффмана в LZ77, описанных выше. Исполнительный модуль также включает в себя логическую схему обновления указателя 707 для обновления значений указателя, которые соответствуют представленному выше описанию. Результаты исполнительного модуля записывают обратно в пространство регистра. Конечный автомат может быть встроен, как специализированная логическая схема, микрокод или некоторая их комбинация.

На фиг. 8 показана схема высокого уровня ядра 800 обработки, в которой воплощена логическая схема на полупроводниковой микросхеме. Ядро обработки включает в себя конвейер 801 обработки. Конвейер состоит из множества каскадов, каждый из которых разработан с возможностью выполнения определенного этапа при многоэтапной обработке, необходимой для полного выполнения инструкции программного кода. Они обычно включают в себя, по меньшей мере: 1) выборку и декодирование инструкции; 2) выборку данных; 3) исполнение; 4) обратную запись. Исполнительный каскад выполняет конкретную операцию, идентифицированную инструкцией, которая была выбрана и декодирована в предшествующем каскаде (каскадах) (например, на этапе 1)), для данных, идентифицированных той же инструкцией и выбранных в другом предшествующем каскаде (например, на этапе 2), представленном выше). Данные, с которыми выполняют операции, обычно выбирают из пространства 802 сохранения регистра (общего назначения). Новые данные, которые формируют по окончании операции, также обычно "записывают обратно" в пространство сохранения регистра (например, в каскаде 4), как описано выше).

Логическая схема, ассоциированная с каскадом вьшолнения, обычно состоит из множества "исполнительных модулей" или "функциональных модулей" 803_1-803_N, каждый из которых разработан для вьшолнения своего собственного уникального поднабора операций (например, первый функциональный модуль выполняет операцию сопоставления целых чисел, второй футщиональный модуль выполняет инструкции с плавающей точкой, третий функциональный модуль выполняет операции загрузки и сохранения в/из кэш/памяти и т.д.). Подборка всех операций, выполняемых всеми функциональными модулями, соответствует "набору инструкций", поддерживаемому ядром 800 обработки. Логическая конструкция 700 по фиг. 7 может быть встроена в один из функциональных модулей исполнительного каскада для реализации ядра, имеющего упомянутую выше возможность исполнения инструкции.

На фиг. 9 показана архитектура примерного многоядерного процессора 900. Как можно видеть на фиг. 9, процессор включает в себя: 1) множество ядер обработки 901_1-901_N; 2) сеть 902 взаимного соединения; 3) систему 903 кэширования последнего уровня; 4) контроллер 904 памяти и концентратор 905 I/O. Каждое из ядер обработки содержит один или больше конвейеров исполнения инструкций для выполнения инструкции программного кода. Любые из таких конвейеров исполнения инструкций могут включать в себя исполнительный модуль для вьшолнения декодирования DEFLATE, как описано выше. Сеть 902 взаимного соединения используется для взаимного соединения каждого из ядер 901_1-901_N друг с другом, а также для других компонентов 903, 904, 905. Система 903 кэширования последнего уровня используется, как последний уровень кэш в процессоре перед тем, как инструкции и/или данные будут переданы в системную память 908.

Контроллер 904 памяти считывает/записывает данные и инструкции в/из системной памяти 908. Концентратор 905 I/O управляет передачей данных между процессором и устройствами "I/O" (например, энергонезависимыми устройствами накопителя и/или сетевыми интерфейсами). Порт 906 выведен из сети 902 взаимного соединения для соединения множества процессоров, таким образом, что системы, имеющие больше чем N ядер, могут быть реализованы. Графический процессор 907 выполняет графические расчеты. Схема управления питанием (не показана) управляет характеристиками и состоянием питания процессора в целом ("уровень пакета"), а также аспектами рабочих характеристик и состоянием питания отдельных модулей в пределах процессора, таких как отдельные ядра от 901_1 до 901_N, графический процессор 907 и т.д. Другие важные функциональные блоки (например, схема фазовой автоподстройки частоты (PLL)) не представлены на фиг. 9 для удобства.

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

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

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

Группа изобретений относится к области кодирования и может быть использована для ускорения операций сжатия и распаковки. Техническим результатом является упрощение процесса декодирования. Способ содержит этапы, на которых декодируют инструкцию посредством модуля декодирования в процессоре; выполняют инструкцию посредством исполнительного модуля в процессоре, причем на этапе выполнения инструкции: принимают указатель на поток информации, кодированной в соответствии со схемой сжатия; выполняют выборку части кодированной информации; и применяют упомянутую часть кодированной информации к схеме ассоциативной памяти (САМ) для получения декодированной информации. 4 н. и 17 з.п. ф-лы, 21 ил.

1. Процессор, содержащий:

модуль декодирования, выполненный с возможностью декодирования инструкции; и

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

2. Процессор по п. 1, в котором схема САМ содержит информацию для декодирования литералов и значений длины.

3. Процессор по п. 2, в котором упомянутая информация указывает, сколько дополнительных битов применяется к конкретному кодированному значению длины.

4. Процессор по п. 2, в котором записи в схеме САМ указывают, содержат ли они информацию для литерала.

5. Процессор по п. 2, в котором записи в схеме САМ указывают, содержат ли они информацию для значения длины.

6. Процессор по п. 1, в котором исполнительный модуль содержит вторую схему САМ, содержащую информацию для декодирования расстояния.

7. Процессор по п. 6, в котором записи во второй схеме САМ указывают, применяются ли дополнительные биты.

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

9. Процессор по п. 1, в котором исполнительный модуль выполнен с возможностью выполнять запись в пространство регистра управления для указания частичного завершения, если инструкция только частично завершает выполнение.

10. Процессор по п. 9, в котором исполнительный модуль выполнен с возможностью возвращать обновленный указатель, даже если исполнение только частично завершает выполнение.

11. Способ декодирования кодированной информации, содержащий этапы, на которых:

декодируют инструкцию посредством модуля декодирования в процессоре;

выполняют инструкцию посредством исполнительного модуля в процессоре, причем на этапе выполнения инструкции:

принимают указатель на поток информации, кодированной в соответствии со схемой сжатия;

выполняют выборку части кодированной информации; и

применяют упомянутую часть кодированной информации к схеме ассоциативной памяти (САМ) для получения декодированной информации.

12. Способ по п. 11, дополнительно содержащий этап, на котором предоставляют информацию в схеме САМ для декодирования литералов и значений длины.

13. Способ по п. 12, в котором информация указывает, сколько дополнительных битов применяется к конкретному кодированному значению длины.

14. Способ по п. 12, в котором записи в схеме САМ указывают, содержат ли они информацию для литерала.

15. Способ по п. 12, в котором записи в схеме САМ указывают, содержат ли они информацию для значения длины.

16. Способ по п. 11, в котором процессор содержит вторую схему САМ, содержащую информацию для декодирования расстояния.

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

составляют программный код, при этом:

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

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

18. Энергонезависимый машиночитаемый носитель информации по п. 17, в котором на этапе составления программного кода дополнительно: вводят инструкцию записи в память между упомянутой инструкцией и упомянутой циклической операцией для записи упомянутой декодированной части в системную память.

19. Энергонезависимый машиночитаемый носитель информации по п. 17, в котором на этапе составления программного кода дополнительно: вводят код для обработки частичного завершения упомянутой инструкции.

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

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

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

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