TWI559688B - 用於有效以ｌｚ７７爲基礎的資料解壓縮之技術 - Google Patents

用於有效以ｌｚ７７爲基礎的資料解壓縮之技術 Download PDF

Info

Publication number
TWI559688B
TWI559688B TW104125964A TW104125964A TWI559688B TW I559688 B TWI559688 B TW I559688B TW 104125964 A TW104125964 A TW 104125964A TW 104125964 A TW104125964 A TW 104125964A TW I559688 B TWI559688 B TW I559688B
Authority
TW
Taiwan
Prior art keywords
value
symbol
tag
indicator
computing device
Prior art date
Application number
TW104125964A
Other languages
English (en)
Chinese (zh)
Other versions
TW201626730A (zh
Inventor
維諾德 歌波
西恩Ｍ 格利
詹姆斯Ｄ 古爾福德
Original Assignee
英特爾公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 英特爾公司 filed Critical 英特爾公司
Publication of TW201626730A publication Critical patent/TW201626730A/zh
Application granted granted Critical
Publication of TWI559688B publication Critical patent/TWI559688B/zh

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3086—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing a sliding window, e.g. LZ77
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0875—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with dedicated cache, e.g. instruction or stack
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0604—Improving or facilitating administration, e.g. storage management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
    • G06F3/065—Replication mechanisms
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3818—Decoding for concurrent execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3861—Recovery, e.g. branch miss-prediction, exception handling
    • G06F9/3863—Recovery, e.g. branch miss-prediction, exception handling using multiple copies of the architectural state, e.g. shadow registers
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3091—Data deduplication
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/60—General implementation details not specific to a particular type of compression
    • H03M7/6005—Decoder aspects
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/60—General implementation details not specific to a particular type of compression
    • H03M7/6017—Methods or arrangements to increase the throughput
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1041—Resource optimization
    • G06F2212/1044—Space efficiency improvement
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/45—Caching of specific data in cache memory
    • G06F2212/452—Instruction code

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Software Systems (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
TW104125964A 2014-09-24 2015-08-10 用於有效以ｌｚ７７爲基礎的資料解壓縮之技術 TWI559688B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US14/494,766 US9524169B2 (en) 2014-09-24 2014-09-24 Technologies for efficient LZ77-based data decompression

Publications (2)

Publication Number Publication Date
TW201626730A TW201626730A (zh) 2016-07-16
TWI559688B true TWI559688B (zh) 2016-11-21

Family

ID=55525809

Family Applications (1)

Application Number Title Priority Date Filing Date
TW104125964A TWI559688B (zh) 2014-09-24 2015-08-10 用於有效以ｌｚ７７爲基礎的資料解壓縮之技術

Country Status (5)

Country Link
US (2) US9524169B2 (de)
EP (1) EP3198729A4 (de)
CN (1) CN106664100B (de)
TW (1) TWI559688B (de)
WO (1) WO2016048516A1 (de)

Families Citing this family (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9524169B2 (en) * 2014-09-24 2016-12-20 Intel Corporation Technologies for efficient LZ77-based data decompression
US10657053B2 (en) * 2017-03-31 2020-05-19 Kyocera Document Solutions Inc. Memory allocation techniques for filtering software
JP2019036810A (ja) * 2017-08-14 2019-03-07 富士通株式会社 データ圧縮装置、データ復元装置、データ圧縮プログラム、データ復元プログラム、データ圧縮方法、およびデータ復元方法
US11509328B2 (en) * 2018-05-31 2022-11-22 Microsoft Technology Licensing, Llc Computer data compression utilizing multiple symbol alphabets and dynamic binding of symbol alphabets
US11387844B2 (en) * 2019-04-19 2022-07-12 Preferred Networks, Inc. Data compression method, data compression apparatus, data decompression method, data decompression apparatus and data storage system
US11108406B2 (en) 2019-06-19 2021-08-31 Intel Corporation System, apparatus and method for dynamic priority-aware compression for interconnect fabrics
CN110545108B (zh) * 2019-09-09 2022-12-20 飞天诚信科技股份有限公司 数据处理方法、装置、电子设备及计算机可读存储介质
AU2021210145A1 (en) 2020-01-21 2022-09-08 Heerema Marine Contractors Nederland Se Assembly and method for installing a pile into a seabed
US20220113913A1 (en) * 2021-12-23 2022-04-14 Intel Corporation Target offload for scale-out storage
US20230020359A1 (en) * 2022-09-28 2023-01-19 Nitish Paliwal System, method and apparatus for reducing latency of receiver operations during a containment mode of operation
CN117097442B (zh) * 2023-10-19 2024-01-16 深圳大普微电子股份有限公司 一种数据解码方法、系统、设备及计算机可读存储介质
CN119210460B (zh) * 2023-11-20 2025-04-29 华为云计算技术有限公司 数据处理方法、装置、设备及计算机可读存储介质
JP2025139943A (ja) * 2024-03-13 2025-09-29 キオクシア株式会社 データ圧縮装置、データ伸張装置、およびメモリシステム

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020087732A1 (en) * 1997-10-14 2002-07-04 Alacritech, Inc. Transmit fast-path processing on TCP/IP offload network interface device
US6963934B2 (en) * 2001-03-21 2005-11-08 Microsoft Corporation Hibernation of computer systems
US20090058693A1 (en) * 2007-08-31 2009-03-05 Raza Microelectronics, Inc. System and method for huffman decoding within a compression engine
US20100141488A1 (en) * 2008-12-10 2010-06-10 Selcuk Baktir Accelerated decompression
US20110154169A1 (en) * 2009-12-22 2011-06-23 Vinodh Gopal System, method, and apparatus for a scalable processor architecture for a variety of string processing applications

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2346470B (en) * 1999-02-05 2003-10-29 Advanced Risc Mach Ltd Bitmap font data storage within data processing systems
GB0210604D0 (en) * 2002-05-09 2002-06-19 Ibm Method and arrangement for data compression
GB0513433D0 (en) * 2005-06-30 2005-08-10 Nokia Corp Signal message compressor
WO2009067181A2 (en) * 2007-11-16 2009-05-28 Broadcom Corporation Low density parity check (ldpc) encoded higher order modulation
CN101616320B (zh) * 2008-06-26 2011-05-04 展讯通信（上海）有限公司 图像压缩、解压缩方法及设备
CN102841907A (zh) * 2011-06-24 2012-12-26 环达电脑(上海)有限公司 数据压缩和解压缩的处理方法
US8824569B2 (en) * 2011-12-07 2014-09-02 International Business Machines Corporation High bandwidth decompression of variable length encoded data streams
US8766827B1 (en) * 2013-03-15 2014-07-01 Intel Corporation Parallel apparatus for high-speed, highly compressed LZ77 tokenization and Huffman encoding for deflate compression
US9252807B2 (en) * 2013-10-21 2016-02-02 Globalfoundries Inc. Efficient one-pass cache-aware compression
US9524169B2 (en) * 2014-09-24 2016-12-20 Intel Corporation Technologies for efficient LZ77-based data decompression
US9515678B1 (en) * 2015-05-11 2016-12-06 Via Alliance Semiconductor Co., Ltd. Hardware data compressor that directly huffman encodes output tokens from LZ77 engine

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020087732A1 (en) * 1997-10-14 2002-07-04 Alacritech, Inc. Transmit fast-path processing on TCP/IP offload network interface device
US6963934B2 (en) * 2001-03-21 2005-11-08 Microsoft Corporation Hibernation of computer systems
US20090058693A1 (en) * 2007-08-31 2009-03-05 Raza Microelectronics, Inc. System and method for huffman decoding within a compression engine
US20100141488A1 (en) * 2008-12-10 2010-06-10 Selcuk Baktir Accelerated decompression
US20110154169A1 (en) * 2009-12-22 2011-06-23 Vinodh Gopal System, method, and apparatus for a scalable processor architecture for a variety of string processing applications

Also Published As

Publication number Publication date
EP3198729A1 (de) 2017-08-02
US20160085555A1 (en) 2016-03-24
US9917596B2 (en) 2018-03-13
US9524169B2 (en) 2016-12-20
WO2016048516A1 (en) 2016-03-31
CN106664100B (zh) 2020-10-09
EP3198729A4 (de) 2018-06-13
CN106664100A (zh) 2017-05-10
US20170250706A1 (en) 2017-08-31
TW201626730A (zh) 2016-07-16

Similar Documents

Publication Publication Date Title
TWI559688B (zh) 用於有效以ｌｚ７７爲基礎的資料解壓縮之技術
RU2629440C2 (ru) Устройство и способ для ускорения операций сжатия и распаковки
CN112514270B (zh) 数据压缩
US10666288B2 (en) Systems, methods, and apparatuses for decompression using hardware and software
KR20220049522A (ko) 다중 데이터 스트림을 포함하는 압축된 입력 데이터를 압축 해제하기 위한 압축 해제 엔진
US10230392B2 (en) Techniques for parallel data decompression
US10694217B2 (en) Efficient length limiting of compression codes
US9929748B1 (en) Techniques for data compression verification
CN103283149B (zh) 用于处理数据元素序列的装置和方法
CN105844210B (zh) 硬件有效的指纹识别
US9100042B2 (en) High throughput decoding of variable length data symbols
CN114342264A (zh) 多符号解码器
CN114450676B (zh) 用于生成压缩数据的具有最长匹配处理的压缩系统
CN113454593B (zh) 保持多个机器生成上的复杂功能的兼容性
CN115344826B (zh) 计算装置、操作方法和机器可读存储介质
US9628109B1 (en) Operation of a multi-slice processor implementing priority encoding of data pattern matches
US9348535B1 (en) Compression format designed for a very fast decompressor
US12511044B2 (en) Fast decoding of compressed data
US10707897B1 (en) Command processor with multiple string copy engines for a decompression system
CN105843837B (zh) 硬件有效的拉宾指纹识别
KR20260012097A (ko) 복수의 애플리케이션과 관련된 페이지 데이터의 압축 해제를 수행하는 시스템 및 방법

Legal Events

Date Code Title Description
MM4A Annulment or lapse of patent due to non-payment of fees