[go: up one dir, main page]

CN111324479A - 用于错误修正代码的加速的装置及系统 - Google Patents

用于错误修正代码的加速的装置及系统 Download PDF

Info

Publication number
CN111324479A
CN111324479A CN201911143197.3A CN201911143197A CN111324479A CN 111324479 A CN111324479 A CN 111324479A CN 201911143197 A CN201911143197 A CN 201911143197A CN 111324479 A CN111324479 A CN 111324479A
Authority
CN
China
Prior art keywords
processing device
error correction
data elements
correction code
data
Prior art date
Legal status (The legal status 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 status listed.)
Granted
Application number
CN201911143197.3A
Other languages
English (en)
Other versions
CN111324479B (zh
Inventor
秦冕
李周桓
瑞克哈·皮茲马尼
奇亮奭
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
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 Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of CN111324479A publication Critical patent/CN111324479A/zh
Application granted granted Critical
Publication of CN111324479B publication Critical patent/CN111324479B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/20—Handling requests for interconnection or transfer for access to input/output bus
    • G06F13/28—Handling requests for interconnection or transfer for access to input/output bus using burst mode transfer, e.g. direct memory access DMA, cycle steal
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/0703—Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation
    • G06F11/079—Root cause analysis, i.e. error or fault diagnosis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G06F11/1096—Parity calculation or recalculation after configuration or reconfiguration of the system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/0703—Error or fault processing not based on redundancy, i.e. by taking additional measures to deal with the error or fault not making use of redundancy in operation, in hardware, or in data representation
    • G06F11/0793—Remedial or corrective actions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error
    • G06F11/1032—Simple parity
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1048—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using arrangements adapted for a specific error detection or correction feature
    • 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/0614—Improving the reliability of storage systems
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/30076—Arrangements for executing specific machine instructions to perform miscellaneous control operations, e.g. NOP
    • G06F9/30079—Pipeline control instructions, e.g. multicycle NOP
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/30076—Arrangements for executing specific machine instructions to perform miscellaneous control operations, e.g. NOP
    • G06F9/3009—Thread control instructions
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6575—Implementations based on combinatorial logic, e.g. Boolean circuits

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Quality & Reliability (AREA)
  • Software Systems (AREA)
  • Human Computer Interaction (AREA)
  • Probability & Statistics with Applications (AREA)
  • Health & Medical Sciences (AREA)
  • Biomedical Technology (AREA)
  • Detection And Correction Of Errors (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
  • Error Detection And Correction (AREA)

Abstract

本发明公开一种用于错误修正代码的加速的装置及系统。所述装置可包括主机接口电路，所述主机接口电路被配置以从主机处理器件接收分担指令，其中分担指令指示所述装置计算与多个数据元相关联的错误修正代码。所述装置可包括存储接口电路，所述存储接口电路被配置以接收所述多个数据元。所述装置可包括多个存储缓冲器电路，所述多个存储缓冲器电路被配置以临时存储所述多个数据元。所述装置可包括多个错误代码计算电路，所述多个错误代码计算电路被配置以至少部分地计算错误修正代码而不由主机处理器件进行额外处理。

Description

用于错误修正代码的加速的装置及系统
[相关申请的交叉参考]
本申请主张2018年12月14日提出申请、标题为“用于最小存储再生代码的现场可编程门阵列加速系统(FPGA ACCELERATION SYSTEM FOR MSR CODES)”且序列号为62/780,185的临时专利申请的优先权。此先前提交的申请的主题并入本文供参考。
技术领域
本说明涉及数据存储，且更具体来说，涉及一种用于错误修正代码的加速的系统、器件和/或方法。
背景技术
在编码理论中，擦除代码(erasure code)是在假设为比特擦除(而不是比特错误)的情况下的前向错误修正(forward error correction，FEC)代码，它将由k个符号形成的消息转换成具有n个符号的较长消息(码字(code word))以使得可从这n个符号的子集恢复原始消息。分数r＝k/n被称为码率(code rate)。分数k’/k被称为接收效率，其中k’表示进行恢复所需的符号的数目。
再生代码会解决从现有编码片段重建(也被称为修复)丢失的编码片段的问题。更详细来说，再生代码是一类旨在减少修复期间的下载量、同时保持传统最大距离可分(maximum distance separable，MDS)代码的存储效率的代码。这个问题发生在其中为保持编码冗余而进行的通信成为问题的分布式存储系统(distributed storage system)中。
分布式存储系统一般是将信息存储(常常以复制方式存储)在多于一个节点或器件上的计算机网络。它常常用来指其中用户将信息存储在多个节点上的分布式数据库、或者其中用户将信息存储在多个对等网络节点(peer network node)上的计算机网络。分布式存储系统通常使用错误检测及修正技术。一些分布式存储系统使用前向错误修正技术以在文件的一些部分受到损坏或不可用时恢复原始文件、块(chunk)或二进制大对象(binarylarge object，blob)。其他分布式存储系统则再次试图从不同的镜像(mirror)下载所述文件。
发明内容
根据一个一般方面，一种用于错误修正代码的加速的装置可包括主机接口电路，所述主机接口电路被配置以从主机处理器件接收分担指令，其中所述分担指令指示所述装置计算与多个数据元相关联的错误修正代码。所述装置可包括存储接口电路，所述存储接口电路被配置以接收所述多个数据元。所述装置可包括多个存储缓冲器电路，所述多个存储缓冲器电路被配置以临时存储所述多个数据元。所述装置可包括多个错误代码计算电路，所述多个错误代码计算电路被配置以至少部分地计算所述错误修正代码而不由所述主机处理器件进行额外处理。
根据另一一般方面，一种用于错误修正代码的加速的系统可包括存储器，所述存储器被配置以存储多个数据元。所述系统可包括主机处理器件，所述主机处理器件被配置以将所述错误修正代码的计算分担到能够重新编程的处理器件。所述系统可包括所述能够重新编程的处理器件，所述能够重新编程的处理器件可被配置以至少部分地基于所述多个数据元来计算错误修正代码。所述能够重新编程的处理器件可包括能够重新配置的管线，所述能够重新配置的管线至少部分地计算所述错误修正代码且基于所述多个数据元的数目进行重新配置。
根据另一一般方面，一种用于错误修正代码的加速的装置可包括主机处理器件，所述主机处理器件被配置以将错误修正代码的计算分担到分担处理器件。所述装置可包括输入/输出(I/O)系统，所述输入/输出(I/O)系统被配置以读取数据元并将所述数据元写入到多个存储器件。所述装置可包括所述分担处理器件，所述分担处理器件可被配置以至少部分地基于多个数据元来计算所述错误修正代码。所述分担处理器件可包括存储接口电路，所述存储接口电路被配置以接收所述多个数据元。所述分担处理器件可包括多个存储缓冲器电路，所述多个存储缓冲器电路被配置以临时存储所述多个数据元。所述分担处理器件可包括多个错误代码计算电路，所述多个错误代码计算电路被配置以至少部分地计算所述错误修正代码而不由所述主机处理器件进行额外处理。
在附图及以下说明中阐述一种或多种实施方式的细节。通过本说明及图式以及通过权利要求书，其他特征将显而易见。
实质上在各图中的至少一个图中示出和/或结合各图中的至少一个图阐述的一种用于数据存储的系统和/或方法、且更具体来说一种用于错误修正代码的加速的系统、器件和/或方法在权利要求书中予以更完整地阐述。
附图说明
图1是根据所公开主题的系统的示例性实施例的方块图。
图2是根据所公开主题的系统的示例性实施例的方块图。
图3A及图3B是根据所公开主题的系统的示例性实施例的方块图。
图4A及图4B是根据所公开主题的系统的示例性实施例的时序图。
图5是可包括根据所公开主题的原理形成的器件的信息处理系统的示意性方块图。
各个图式中相同的参考符号表示相同的元件。
具体实施方式
在下文中，将参照附图更充分地阐述各种示例性实施例，在所述附图中示出一些示例性实施例。然而，本发明所公开主题可被实施为许多不同形式，而不应被视为仅限于本文所述示例性实施例。确切来说，提供这些示例性实施例是为了使本公开将透彻及完整，并将向所属领域中的技术人员充分传达本发明所公开主题的范围。在图式中，为清晰起见，可夸大各个层及各个区的大小及相对大小。
应理解，当称一元件或层位于另一元件或层“上(on)”、“连接到(connected to)”或“耦合到(coupled to)”另一元件或层时，所述元件或层可直接位于所述另一元件或层上、直接连接到或直接耦合到所述另一元件或层，抑或可存在中间元件或层。相比之下，当称一元件“直接位于(directly on)”另一元件或层上、“直接连接到(directly connectedto)”或“直接耦合到(directly coupled to)”另一元件或层时，则不存在中间元件或层。相同的编号自始至终指代相同的元件。本文所用用语“和/或(and/or)”包括相关列出项中的一个或多个项的任意及所有组合。
应理解，尽管在本文中可使用“第一(first)”、“第二(second)”、“第三(third)”等用语来阐述各个元件、组件、区、层和/或区段，然而这些元件、组件、区、层和/或区段不应受限于这些用语。这些用语仅用于区分各个元件、组件、区、层或区段。因此，以下论述的第一元件、组件、区、层或区段也可被称为第二元件、组件、区、层或区段，而此并不背离本发明所公开主题的教示内容。
为易于说明，在本文中可使用例如“在…之下(beneath)”、“在…下面(below)”、“下部的(lower)”、“在…上方(above)”、“上部的(upper)”等空间相对性用语来阐述图中所示一个元件或特征与另一(其他)元件或特征的关系。应理解，空间相对性用语旨在除图中所绘示的取向外还囊括器件在使用或操作中的不同取向。举例来说，如果图中所示器件被翻转，则被阐述为位于其他元件或特征“下面”或“之下”的元件此时将被取向为位于所述其他元件或特征“上方”。因此，示例性用语“在…下面”可囊括“上方”及“下面”两种取向。器件可具有其他取向(旋转90度或处于其他取向)且本文所用的空间相对性描述语相应地进行解释。
同样地，为易于说明，在本文中可使用例如“高(high)”、“低(low)”、“上拉(pullup)”、“下拉(pull down)”、“1”、“0”等电性用语来阐述图中所示电压电平或电流相对于其他电压电平或电流的关系或者相对于另一(其他)元件或特征的关系。应理解，所述电性相对用语旨在除了图中所绘示的电压或电流之外还囊括器件在使用或操作中的不同的参考电压。举例来说，如果图中所示器件或信号被反相或使用其他参考电压、电流或电荷，则被阐述为“高”或“被上拉”的元件此时与新的参考电压或电流相比将为“低”或“被下拉”的。因此，示例性用语“高”可囊括相对低的电压或电流或者相对高的电压或电流二者。器件可另外地基于不同的电性参考框架且本文所用的电性相对描述语相应地加以解释。
本文所用术语仅是出于阐述特定示例性实施例的目的而并非旨在限制本发明所公开主题。除非上下文清楚地另外指明，否则本文所用单数形式“一(a、an)”及“所述(the)”旨在也包括复数形式。还应理解，当在本说明书中使用用语“包括(comprises和/或comprising)”时，是指明所陈述特征、整数、步骤、操作、元件和/或组件的存在，但不排除一个或多个其他特征、整数、步骤、操作、元件、组件和/或其群组的存在或添加。
在本文中参照剖视图阐述示例性实施例，所述剖视图是对理想示例性实施例(及中间结构)的示意性例示。由此，预期会因例如制造技术和/或容差而导致相对于例示形状的变化。因此，示例性实施例不应被视为仅限于本文所示区的特定形状，而是应包含由例如制造引起的形状偏差。举例来说，被例示为矩形的注入区将通常具有圆形特征或曲线特征和/或在其边缘存在注入浓度的梯度而非从注入区到非注入区为二元变化。同样地，通过注入而形成的掩埋区可在所述掩埋区与在进行注入时所经过的表面之间的区中引起一些注入。因此，图中所例示的区为示意性的且其形状并非旨在例示器件的区的实际形状且并非旨在限制本发明所公开主题的范围。
除非另外定义，否则本文所用所有用语(包括技术及科学用语)的含义均与本发明所公开主题所属领域中的一般技术人员所通常理解的含义相同。还应理解，用语(例如在常用词典中所定义的用语)应被解释为具有与其在相关技术的上下文中的含义一致的含义，且除非在本文中明确定义，否则不应将其解释为具有理想化或过于正式的意义。
在下文中，将参照附图详细阐释示例性实施例。
图1是根据所公开主题的系统100的示例性实施例的方块图。在所示实施例中，系统100可包括跨多个节点或存储器件180存储数据的分布式存储系统114。
分布式存储系统常常用于提供大规模可靠性存储。这常常是通过将冗余或错误修正(例如奇偶性)散布在大量的节点或存储器件中来完成的。然而，当节点或存储器件离线(go off-line)时(例如，由于网络错误、硬件故障等)，数据存在可能受到损坏的嫌疑，或者至少冗余度(level of redundancy)降低。存储系统分布越广，这种情况会越频繁发生。
可采用多种技术来防止这种情况的发生(例如镜像(mirroring)、里德-所罗门编码(Reed-Solomon encoding))，但是所公开的主题并不仅限于特定编码。在此种实施例中，使用基于剩余数据的公式来再生或重构遗失的数据(块)。
在所示实施例中，系统100可包括一个或多个主机或计算器件112，所述一个或多个主机或计算器件112被配置成管理分布式存储系统或多个数据节点114。计算器件112可包括从存储系统180进行读取以及向存储系统180进行写入的计算器件(例如，计算机、服务器、虚拟机)。当发生错误(例如，数据块遗失)时，计算器件112一般负责检测错误并在可能的情况下修复错误。
在各种实施例中，计算器件112可包括计算器件，例如(举例来说)膝上型计算机(laptop)、台式计算机、工作站、个人数字助理、智能手机、平板计算机、系统芯片(system-on-a-chip，SoC)及其他适合的计算机或者虚拟机或虚拟机的虚拟计算器件。在各种实施例中，计算器件112可由用户(未示出)使用。在各种实施例中，计算器件112可包括处理器102，处理器102被配置成执行一个或多个机器可执行指令或软件、固件或其组合。在一些实施例中，计算器件112可包括存储器(未示出)，所述存储器被配置成临时、永久、半永久、或以其组合方式存储一条或多条数据。此外，存储器可包括易失性存储器、非易失性存储器、或其组合。在各种实施例中，计算器件112可包括存储介质114或与存储介质114进行通信，存储介质114被配置成以半永久或实质上永久的形式存储数据。
在所示实施例中，每一数据集可被计算器件112分解或片段化(fragmented)成多个较小的数据或块198。在所示实施例中，数据199(图1中未示出199)被划分成块198(例如，D1、D2、D3及D4)。此外，在各种实施例中，计算器件112可将某种形式的冗余应用到数据块198，例如奇偶性块(例如，被命名为P1及P2，且也被编号为198，因为它们也是块)。
在所属领域的用语中，原始数据块198(D1、D2、D3及D4)的数目被阐述为变量K或k。同样，冗余数据块198(P1及P2)的数目被阐述为变量R或r。这样使得块198的总数目是K+R。在所示实施例中，K等于4，R等于2，且K+R等于6；尽管如此，但应理解，以上仅为例示性实例，所公开的主题并不仅限于此。
在所示实施例中，计算器件112使得这些块198(原始的块及冗余的块二者)中的每一者被存储在存储系统114的相应的节点或存储器件上。在各种实施例中，存储器件180的数目可不等于块198的数目。
在各种实施例中，块198可能会遗失(例如，网络或硬件故障)或者可能以其他方式与错误相关联。在所示实施例中，假设块198(以及相应的存储器件180)突然变得不可用。计算器件112在检测到错误时可尝试重新创建遗失的块198或以其他方式纠正错误。
在此种实施例中，如果一个块失效，且原始数据中存在总共K个(例如，4个)块，则至少K个(例如，4个)节点或计算器件180必须向主机器件112发送信息以恢复失效的块。请注意，这些K个(例如，4个)块可来自K+R个(例如，6个)块中的任意块。举例来说，块198D1、D2、D4及P1可用于重新创建遗失的块198D3。
再生代码通过从D个节点发送小于完整块大小的信息来减小修复带宽，其中通常D>K。换句话说，通过使用巧妙的公式，计算器件112可能够通过使用并非完整的块198D1、D2、D4及P1，而是通过使用198D1、D2、D4、P1及P2的仅一部分来重新创建遗失的块198D3。再生代码一般从更多的存储器件180获取信息，但是与非再生代码相比，它从每一存储器件180获取的信息较少。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
举例来说，如果使用了6个数据块(K＝6)且使用了6个冗余块(R＝6且K+R＝12)，且每一个块的大小为16MB，则标准里德-所罗门(RS)错误修正编码方案要求将6(K)个16MB的块发送到主机器件或者传输96MB的数据来修正遗失的16MB的块。相反，如果使用了再生技术，则将读取所有12个(在这种情况下是K+R个或D个)块的一些部分，但是由于每一个块的仅一部分被使用(例如，2.7MB)，因此传输到主机器件的总量可较低(例如，29.7MB)。
再生代码常常具有存储与带宽折衷关系(tradeoff)。在各种实施例中，一般来说，存在两类或两组再生代码。如果存储开销(storage overhead)非常小，则所述再生代码被称为最小存储再生(Minimum Storage Regeneration，MSR)代码。如果修复带宽非常小而存储开销增加，则所述再生代码被称为最小带宽再生(Minimum Bandwidth Regeneration，MBR)代码。在这些宽泛的类别内，可采用各种特定的技术或公式来实行再生代码。应理解，以上仅为几个例示性实例，所公开的主题并不仅限于此。
返回图1，在所示实施例中，存储系统114可包括多个存储器件180。每一存储器件180可被配置成以块或其他方式存储数据。在所示实施例中，存储器件180可为相对传统的存储器件，例如硬盘驱动器(hard drive)、固态驱动器、或者甚至为易失性存储器。
在所示实施例中，系统100还可包括计算器件112，如上所述。在此种实施例中，计算器件112可包括主机处理器或处理器件102。在各种实施例中，主机处理器件102可包括中央处理器(central processing unit，CPU)、器件专用或控制器处理器(例如，如在存储器件中可见到的器件专用或控制器处理器)、或其他处理电路系统。
在所示实施例中，计算器件112还可包括输入/输出(input/output，I/O)接口或系统106。在各种实施例中，I/O系统106可被配置成与存储系统114进行通信。在一些实施例中，I/O系统106可至少部分地与主机处理器件102集成在一起。在另一实施例中，I/O系统106可包括存储器管理单元(memory management unit，MMU)或常常被认为是芯片组的装置的其他组件。应理解，以上仅为几个例示性实例，所公开主题并不仅限于此。
在所示实施例中，计算器件112可包括可重新编程的分担处理器件(reprogrammable offload processing device，ROPD)104。在各种实施例中，此ROPD 104可包括专用逻辑电路系统，例如现场可编程门阵列(field programmable gate array，FPGA)或专用集成电路(application-specific integrated circuit，ASIC)。在各种实施例中，ROPD 104可由外部器件进行编程，以使得其编程一般为固定的。在另一实施例中，ROPD 104可由主机处理器件102或其他器件动态地进行重新编程，以使得其电路系统(例如，管线)可基于运行时状态(runtime conditions)而动态地调整。应理解，以上仅为几个例示性实例，所公开主题并不仅限于此。
如上所述，尽管一般由主机处理器件102负责计算所需的错误修正代码(例如，奇偶性块、遗失数据块的重新创建)，但是在所示实施例中，主机处理器件102可选择或被配置成将此任务全部或部分地分担或委托到ROPD 104。
传统上，由主机处理器件102进行的错误修正代码的计算(常常由软件控制)是一项成本高昂的任务。常常，与MSR(或其他)代码构建及重建的并行特性相比，中央处理器架构(例如，对称多处理(Symmetric multiprocessing，SMP)、单指令多数据(Singleinstruction,multiple data，SIMD))具有有限程度的并行性。另外，创建错误修正代码(即，存取所有的块198)所需的存储器存取模式缺乏局部性(locality)。对数据元及对每一数据元内的数据的串流模式(streaming pattern)的随机存取并不提供太多的局部性，从而导致差的高速缓存性能及整体编码/解码性能的劣化。因此，采用传统软件的概念会导致高的处理器及存储器带宽利用率并阻碍利用可更好地用于其他任务的主机处理器件102。在所示实施例中，系统100提供了用于错误修正编码(例如，构建及重建)的加速系统，所述加速系统会解决至少这些问题。
在所示实施例中，主机处理器件102可被配置成将错误修正编码分担到硬件加速器或ROPD 104。在此种实施例中，当被要求实行错误修正编码时，主机处理器件102可将此请求传送给ROPD 104。ROPD 104可然后利用I/O系统106来存取数据元(例如，块198或其他大小的数据)。一旦完成，ROPD 104便可将操作的最终结果传送给主机处理器件102，主机处理器件102可然后存取数据、错误修正代码，或者简单地继续其操作。在此种实施例中，在ROPD 104正在计算错误修正代码的同时，主机处理器件102可实行另一项任务。
在各种实施例中，主机处理器件102及ROPD 104可通过直接存储器存取(directmemory access，DMA)进行通信。在一个实施例中，这可涉及I/O系统106内的存储器的映射部分。在另一实施例中，这可涉及器件102与器件104之间的直接通信。同样，I/O系统106及ROPD 104可通过对等DMA协议进行通信。应理解，以上仅为几个例示性实例，所公开主题并不仅限于此。
图2是根据所公开主题的系统200的示例性实施例的方块图。在各种实施例中，系统200可包括可重新编程的分担处理器件(ROPD)，如上所述。
在所示实施例中，系统200可包括分担处理电路202。在各种实施例中，此分担处理电路202可被重新编程，如上所述。在此种实施例中，分担处理电路202可被配置成计算错误修正代码，而不由主机处理器件进行额外处理。
在所示实施例中，分担处理电路202包括被配置成与主机处理器件或处理器进行通信的主机接口232。在各种实施例中，主机处理器可位于系统200的外部或者被集成为单独的逻辑区块(例如，作为系统芯片(SoC)的一部分)。在各种实施例中，主机接口232可至少部分地或完全地通过DMA进行通信。
在所示实施例中，系统200可包括存储电路或单元204或者与存储电路或单元204交互。在一些实施例中，存储器204可包括系统存储器，例如双倍数据速率(double datarate，DDR)同步动态随机存取存储器(synchronous dynamic random access memory，SDRAM)；尽管如此，但应理解，以上仅为一个例示性的实例，所公开主题并不仅限于此。在此种实施例中，存储器204可被配置成存储用于错误修正代码计算(例如，创建或重建)的数据元(例如，信息或奇偶性块)。
在一个实施例中，对于创建或编码程序，主机处理器可将需要被编码的数据对象(例如，所有信息块)发送到存储器204。在此种实施例中，这些数据元可被存储为输入212。然后分担处理电路202可计算奇偶性块(错误修正代码的一种形式)，并将所述奇偶性块写回到存储器204(在输出214处)。最后，可将信息及奇偶性块(由I/O系统或主机处理器件)分布到不同的存储节点。
在另一实施例中，对于重建或解码程序，可首先检索幸存的信息数据元及奇偶性数据元并将其存储在存储器204中(在输入212处)。然后分担处理单元202可计算重建块(错误修正代码)并将所述重建块写入存储器204(在输出214处)。最后，将重建的块传送到主机处理器件。
在所示实施例中，分担处理电路202可包括被配置成与存储器204进行通信的存储接口电路222。在所示实施例中，存储接口电路222被示出为可接收数据元的多路复用器(multiplexer，MUX)。同样，多路分用器(de-multiplexer，DeMUX)可将数据元写入到存储器204。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
分担处理电路202可包括被配置成临时存储所述多个数据元的多个存储缓冲器电路224。在一个特定实施例中，输入数据212可采用高效的512位分组(512-bit grouping)形式到达分担处理电路202处，但这些元本身可仅为8位。在此种实施例中，存储接口电路222可将输入212分成64个数据元，并将这些数据元存储在各别的缓冲器224(或缓冲器224的经分割的部分)中。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
在所示实施例中，分担处理电路202可包括地址控制器228，地址控制器228被配置成管理如何从存储器204读取数据以及如何将数据写入到缓冲器224。在一些实施例中，地址控制器228还可被配置成管理如何从缓冲器224读取数据以进行错误修正代码计算。在一些实施例中，分担处理电路202可包括索引表230，索引表230包括缓冲器224被存取时将采用的预存储顺序。
分担处理电路202可包括多个错误代码计算电路226。这些错误代码计算电路226可被配置成计算错误修正代码，而不由所述主机处理器件进行额外处理。在所示实施例中，错误代码计算电路226可主要包括乘法-加法电路(multiple-add circuit)。在各种实施例中，错误代码计算电路226可被实施为查找表或按位异或门(bitwise XOR gate)。应理解，以上仅为几个例示性实例，所公开主题并不仅限于此。
在一些实施例中，系统200可分三个阶段实行错误修正代码的创建：读取、处理及写入。在读取阶段中，可从存储器204读取数据元(如果重建的话，则包括奇偶性元)，并将数据元放入到缓冲器224中。
在处理阶段期间，地址控制器单元228可根据预存储的索引表230来控制存储器读取且同时读取k个缓冲器224中的正确数据片。此数据可被馈送到错误代码计算电路226用于错误修正计算。
错误代码计算电路226的一个可能的实施例的详细架构在附图的分解视图部分中示出。错误代码计算电路226可包括与期望的奇偶性计算或信息重建技术(例如，伽罗瓦域(Galois field，GF)计算)对应的预存储系数表242。错误代码计算电路226还可包括k个乘法器或乘法查找表244，以进行快速的乘法运算。错误代码计算电路226还可包括XOR或加法器246树结构。在一个实施例中，每一乘法器244可处理一个数据元252(例如，8位数据)。最终，错误代码计算电路226可产生或输出错误修正代码254(或错误修正代码254的一部分，如下所述)。
在写入阶段期间，错误修正代码254可作为输出214被写回到存储器204。在各种实施例中，错误修正代码254可在处理之后立即被写回到存储器204。这可被认为是在XOR 246树之后再增加一个管线阶段(pipeline stage)。在此种实施例中，这可使得系统200参与管线式数据处理，而不是离散运算或原子运算。在此种实施例中，这可加快多遍次运算(multi-pass operation)，如下所述。在一些实施例中，由于数据在被读取到缓冲器224中时被分割，因此数据输出以单独的输出分割部分形式被写回到存储器204。
在各种实施例中，由于(例如MSR代码(n、k、m))存在k个输入数据块(在编码程序中)，因此整个输入数据可大于内部缓冲器224的大小。在此种实施例中，系统200可采用多个或“p个”遍次来处理整个输入数据集，其中p等于对每一信息/奇偶性元分割的信息/奇偶性片的数目。在此种实施例中，系统200可将较大的数据集分割成p个分割部分，每一分割部分具有k个或小于k个数据元。在此种实施例中，每一遍次可涉及读取、处理及写入与相应的分割部分相关联的错误修正代码。
在其中数据集的数目少于缓冲器224中的总存储量的另一实施例中，数据集可被映射到k个数据元，每一数据元均小于缓冲器大小。在此种实施例中，可由系统200处理可变的数据元大小。
在其中数据元的数目小于k个缓冲器224(且因此小于k个错误代码计算电路226)的再一实施例中，错误代码计算电路226的数目可动态地改变。在此种实施例中，系统200的管线可动态地改变以优化延迟以及吞吐量。在此种实施例中，可调整错误代码计算电路226的数目以与数据元的数目(最大到最大硬件限制)匹配。在此种实施例中，每一循环可对乘法查找表244进行存取。数据元(且因此数据节点)之间的这种并行性不同于传统的CPU，在传统的CPU中，SIMD指令中的操作数(operand)的数目是固定的且因此必须对操作数本身进行操纵以解决不方便的奇数个数据元。
图3A及图3B是根据所公开主题的系统300的示例性实施例的方块图。图3A示出没有ROPD的系统300的简化版本，而图3B示出在系统300内使用ROPD。图3A及图3B示出在利用本文所述错误修正代码计算的系统300内执行指令或软件线程。
在所示实施例中，系统300可包括正在实行需要对数据集进行存取(且因此对数据元进行存取)的某个任务的主线程或用户线程或应用程序接口(application programinterface，API，302。在此种实施例中，用户线程302可由主机处理器执行。
在所示实施例中，系统可包括程式库(library，LIB)304，LIB 304处理指令312的计算线程且通过I/O队列316与存储器件306交互。
在其中分担处理器件不现用的实施例中，计算线程312可接收用户请求(置于请求队列322中)以计算错误修正代码(例如，建立奇偶性元或重建数据元)。如果请求进行编码(建立奇偶性元)，则当请求到达编码操作324时，主机处理器件可实行编码，且然后使I/O队列316及其I/O线程317(单独的I/O线程352)将奇偶性元写入到相应的存储介质306。同样，当所需的剩余数据元(包括奇偶性元)被I/O线程352返回到完成队列326且最终到达解码操作328(解码操作328由主机处理器实行)时，请求进行解码(重建数据元)。
在图3B中，阐述硬件加速器或分担处理器件308如何与主机处理器(主机处理器正在执行线程302、312及LIB 304)交互。此外，计算线程312可处理来自用户线程302的请求。在此种实施例中，这可涉及将编码/解码计算分担到分担处理器件308。
如上所述，每一计算线程312可包括请求队列322(由用户线程302列入队列)及完成队列326(由I/O线程317列入队列)。在此种实施例中，计算线程312可与分担处理器件308交互。
举例来说，在编码或奇偶性创建情景中，计算线程312可将编码请求放在请求队列322中。当编码请求到达编码阶段324时，计算线程312可将编码请求分担到分担处理器件308，而不是由主机器件直接处理。在一个实施例中，这可通过回调线程(callback thread)314来追踪。在此种实施例中，分担请求可被放到硬件加速或分担请求队列332中。由于所述请求存在于硬件加速队列332中，因此回调线程314可向分担处理器件308发出DMA请求。分担处理器件308可包括错误代码计算电路342，如上所述。一旦完成，回调线程314便可向回报告给计算线程312，计算线程312继而报告给用户线程302。此时，I/O线程317可将编码数据写入到存储器件306。
在解码或重建操作的实例中，计算线程312从I/O线程317请求数据。计算线程312可然后将请求放在完成队列326中。当请求到达解码阶段328时，计算线程312可将解码请求分担到分担处理器件308，而不是由主机器件直接处理。在一个实施例中，这可通过回调线程314来追踪。在此种实施例中，分担请求可被放到硬件加速或分担请求队列332中。分担处理器件308可通过DMA从I/O线程317接收现有的数据元。当请求存在于硬件加速队列332中时，回调线程314可向回报告给计算线程312和/或用户线程302。
图4A及图4B是根据所公开主题的系统的示例性实施例的时序图。图4A示出编码或奇偶性创建操作的时序图400。图4B示出解码或重建操作的时序图401。在各种实施例中，这些时序图可由图3A及图3B的系统300创建。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
在所示实施例中，行402示出用户线程的可能的时序。在所示实施例中，行404示出计算线程的可能的时序。在所示实施例中，行406示出用户线程的可能的回调。在所示实施例中，行408示出输入/输出(I/O)线程的可能的时序。
在图4A中，时序图400示出用于编码操作的线程阶段及时序的实施例。在此种实施例中，用户线程402可使用计算线程将I/O写入请求列入队列(方块412)，且然后等待请求的完成(方块414)。在各种实施例中，主机器件可在等待完成(方块414)的同时实行其他操作(未示出)。
在此种实施例中，计算线程404可将用户请求从请求队列退出队列(方块422)且将硬件或分担请求列入到队列(方块424)。计算线程404可然后等待完成(方块426)。
在此种实施例中，回调线程406可然后将硬件加速请求退出队列(方块432)、启动编码操作(方块434)、等待(方块436)、以及当操作完成时通知完成队列(方块438)。在所示实施例中，计算线程404可然后将I/O请求列入到I/O队列(方块428)。
在此种实施例中，I/O线程408可通过将I/O请求退出队列(方块442)、以及向存储器件发出请求(方块444)来实行I/O操作。在等待数据被写入(方块446)之后，I/O线程408可通知用户线程其已完成(方块448)。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
在图4B中，时序图401示出解码操作的线程阶段及时序的实施例。在此种实施例中，用户线程402可使用计算线程将I/O读取请求列入队列(方块413)且然后等待请求的完成(方块415)。在各种实施例中，主机器件可在等待完成(方块415)的同时实行其他操作(未示出)。
在此种实施例中，计算线程404可将用户请求从请求队列退出队列(方块422)且将I/O请求列入到队列(方块428)。计算线程404可然后等待完成(方块427)。
在此种实施例中，I/O线程408可通过将I/O请求退出队列(方块442)并将请求发出到存储器件(方块444)来实行I/O操作。在等待数据被读取(方块447)之后，I/O线程408可通过将硬件加速请求列入队列来通知计算线程404其已完成(方块449)。
在此种实施例中，回调线程406可然后将硬件加速请求退出队列(方块432)、启动解码操作(方块435)、等待(方块436)、以及当操作完成时通知用户线程402(方块439)。应理解，以上仅为一个例示性实例，所公开主题并不仅限于此。
图5是可包括根据所公开主题的原理形成的半导体器件的信息处理系统500的示意性方块图。
参照图5，信息处理系统500可包括根据所公开主题的原理构造而成的一个或多个器件。在另一实施例中，信息处理系统500可采用或执行根据所公开主题的原理的一种或多种技术。
在各种实施例中，信息处理系统500可包括计算器件，例如(举例来说)膝上型计算机、台式计算机、工作站、服务器、刀片服务器(blade server)、个人数字助理、智能手机、平板计算机及其他适合的计算机或者虚拟机或虚拟机的虚拟计算器件。在各种实施例中，信息处理系统500可由用户(图中未示出)使用。
根据所公开主题的信息处理系统500还可包括中央处理器(central processingunit，CPU)、逻辑或处理器510。在一些实施例中，处理器510可包括一个或多个功能单元块(functional unit block，FUB)或组合逻辑块(combinational logic block，CLB)515。在这种实施例中，组合逻辑块可包括各种布尔逻辑运算(例如，与非、或非、非、异或)、稳定化逻辑器件(例如，触发器、锁存器)、其他逻辑器件或其组合。这些组合逻辑运算可以简单方式或复杂方式进行配置，以对输入信号进行处理来实现期望结果。应理解，尽管阐述了同步组合逻辑运算的几个例示性实例，然而所公开主题并不受限于此且可包括异步运算或其混合。在一个实施例中，组合逻辑运算可包括多个互补金属氧化物半导体(complementarymetal oxide semiconductor，CMOS)晶体管。在各种实施例中，这些CMOS晶体管可被排列成用于实行逻辑运算的门；但是应理解，也可使用其他技术且所述其他技术也处于所公开主题的范围内。
根据所公开主题的信息处理系统500还可包括易失性存储器520(例如，随机存取存储器(RAM))。根据所公开主题的信息处理系统500还可包括非易失性存储器530(例如，硬驱动器、光学存储器、与非存储器或闪存存储器)。在一些实施例中，易失性存储器520、非易失性存储器530或它们的组合或一些部分可被称为“存储介质”。在各种实施例中，易失性存储器520和/或非易失性存储器530可被配置成以半永久形式或实质上永久形式存储数据。
在各种实施例中，信息处理系统500可包括一个或多个网络接口540，所述一个或多个网络接口540被配置成使信息处理系统500成为通信网络的一部分且通过通信网络进行通信。Wi-Fi协议的实例可包括但不限于电气及电子工程师协会(Institute ofElectrical and Electronics Engineers，IEEE)802.11g、IEEE 802.11n。蜂窝协议的实例可包括但不限于：IEEE 802.16m(又名，先进无线城域网(Metropolitan Area Network，MAN)、先进长期演进(Long Term Evolution，LTE)、增强数据速率全球移动通信系统(Global System for Mobile Communications，GSM)演进(Enhanced Data rates for GSMEvolution，EDGE)、演进高速封包存取(Evolved High-Speed Packet Access，HSPA+)。有线协议的实例可包括但不限于IEEE 802.3(又名以太网)、光纤信道、电力线通信(例如，家庭插座(HomePlug)、IEEE 1901)。应理解，以上仅为几个例示性实例，所公开主题并不受限于上述几个例示性实例。
根据所公开主题的信息处理系统500还可包括用户接口单元550(例如，显示适配器、触觉接口、人机接口器件)。在各种实施例中，这种用户接口单元550可被配置成从用户接收输入和/或向用户提供输出。也可使用其他种类的器件来实现与用户的交互；举例来说，提供到用户的反馈可为任意形式的感觉反馈，例如，视觉反馈、听觉反馈或触觉反馈；且来自用户的输入可以任意形式接收，包括声学输入、语音输入或触觉输入。
在各种实施例中，信息处理系统500可包括一个或多个其他器件或硬件组件560(例如，显示器或监视器、键盘、鼠标、相机、指纹读取器、视频处理器)。应理解，以上仅为几个例示性实例，所公开主题并不受限于上述几个例示性实例。
根据所公开主题的信息处理系统500还可包括一条或多条系统总线505。在这种实施例中，系统总线505可被配置成对处理器510、易失性存储器520、非易失性存储器530、网络接口540、用户接口单元550及一个或多个硬件组件560进行通信耦合。经处理器510处理的数据或从非易失性存储器530外部输入的数据可存储在非易失性存储器530中或易失性存储器520中。
在各种实施例中，信息处理系统500可包括或执行一个或多个软件组件570。在一些实施例中，软件组件570可包括操作系统(operating system，OS)和/或应用。在一些实施例中，OS可被配置成向应用提供一种或多种服务并管理或充当应用与信息处理系统500的各种硬件组件(例如，处理器510、网络接口540)之间的中间介质。在这种实施例中，信息处理系统500可包括一种或多种本地应用，所述一种或多种本地应用可在本地安装(例如，安装在非易失性存储器530内)且被配置成由处理器510直接执行并与OS直接进行交互作用。在这种实施例中，本地应用可包括预先编译的机器可执行代码。在一些实施例中，本地应用可包括脚本解释器(例如，C shell(csh)、苹果脚本(AppleScript)、AutoHotkey)或虚拟执行机(virtual execution machine，VM)(例如，Java虚拟机、微软公共语言运行时环境(Microsoft Common Language Runtime))，脚本解释器及虚拟执行机被配置成将源代码或目标代码转换成可执行代码，然后由处理器510来执行所述可执行代码。
上述半导体器件可使用各种封装技术来进行包封。举例来说，根据所公开主题的原理构造而成的半导体器件可使用以下中的任意一种来进行包封：层叠封装(package onpackage，POP)技术、球栅阵列(ball grid array，BGA)技术、芯片尺寸封装(chip scalepackage，CSP)技术、塑料引线芯片载体(plastic leaded chip carrier，PLCC)技术、塑料双列直插式封装(plastic dual in-line package，PDIP)技术、华夫包装式裸片(die inwaffle pack)技术、晶片式裸片(die in wafer form)技术、板上芯片(chip on board，COB)技术、陶瓷双列直插封装(ceramic dual in-line package，CERDIP)技术、塑料公制四方扁平封装(plastic metric quad flat package，PMQFP)技术、塑料四方扁平封装(plastic quad flat package，PQFP)技术、小外形集成电路(small outline integratedcircuit，SOIC)技术、缩小型小外形封装(shrink small outline package，SSOP)技术、薄型小外形封装(thin small outline package，TSOP)技术、薄型四方扁平封装(thin quadflat package，TQFP)技术、系统级封装(system in package，SIP)技术、多芯片封装(multi-chip package，MCP)技术、晶片级构造封装(wafer-level fabricated package，WFP)技术、晶片级处理堆叠封装(wafer-level processed stack package，WSP)技术或所属领域中的技术人员将知晓的其他技术。
方法步骤可由一个或多个可编程处理器执行计算机程序来实行，以通过对输入数据进行操作并产生输出来实行功能。方法步骤还可由专用逻辑电路系统(例如，现场可编程门阵列(field programmable gate array，FPGA)或专用集成电路(application-specificintegrated circuit，ASIC))来实行，且装置可被实施为所述专用逻辑电路。
在各种实施例中，计算机可读介质可包括指令，所述指令在被执行时会使器件实行方法步骤的至少一部分。在一些实施例中，计算机可读介质可包括在磁性介质、光学介质、其他介质或其组合(例如，压缩盘只读存储器(compact disc read only memory，CD-ROM)、硬驱动器、只读存储器、闪存驱动器)中。在这种实施例中，计算机可读介质可为以有形的及非暂时方式实施的制品。
尽管已参照示例性实施例阐述了所公开主题的原理，然而对所属领域中的技术人员来说显而易见的是，在不背离这些所公开概念的精神及范围的条件下，可对其作出各种改变及修改。因此，应理解，以上实施例并非限制性的，而是仅为例示性的。因此，所公开概念的范围将由以上权利要求及其等效范围所许可的最广范围的解释来确定，而不应受上述说明约束或限制。因此，应理解，随附权利要求旨在涵盖落于实施例的范围内的所有这种修改及改变。

Claims (20)

1.一种用于错误修正代码的加速的装置，包括：
主机接口电路，被配置以从主机处理器件接收分担指令，其中所述分担指令指示所述装置计算与多个数据元相关联的所述错误修正代码；
存储接口电路，被配置以接收所述多个数据元；
多个存储缓冲器电路，被配置以临时存储所述多个数据元；以及
多个错误代码计算电路，被配置以至少部分地计算所述错误修正代码而不由所述主机处理器件进行额外处理。
2.根据权利要求1所述的装置，其中所述装置被配置以通过以下方式计算所述错误修正代码：
将所述多个数据元分割成多个子部分；
按每一子部分执行所述多个数据元的多个遍次；以及
对每一遍次的输出进行聚合，以形成所述错误修正代码。
3.根据权利要求1所述的装置，其中所述存储接口电路被配置以将所述多个错误代码计算电路的输出自动地写入到外部存储器。
4.根据权利要求1所述的装置，其中所述多个数据元与数据节点的数目相关联；以及
其中所述多个错误代码计算电路内的数目能够重新配置以与所述数据节点的所述数目相匹配，使得在所述数据节点与所述多个错误代码计算电路之间存在关联。
5.根据权利要求1所述的装置，其中所述多个错误代码计算电路包括：
由交替的乘法电路与加法电路形成的树。
6.根据权利要求5所述的装置，其中所述乘法电路包括查找表；以及
其中所述加法电路包括异或门。
7.根据权利要求1所述的装置，其中所述多个错误代码计算电路能够由所述主机处理器件进行重新编程。
8.根据权利要求1所述的装置，其中所述错误修正代码包括最小存储再生代码。
9.一种用于错误修正代码的加速的系统，包括：
存储器，被配置以存储多个数据元；
能够重新编程的处理器件，被配置以至少部分地基于所述多个数据元来计算所述错误修正代码；以及
主机处理器件，被配置以将所述错误修正代码的计算分担到所述能够重新编程的处理器件，
其中所述能够重新编程的处理器件包括：
能够重新配置的管线，至少部分地计算所述错误修正代码且基于所述多个数据元的数目进行重新配置。
10.根据权利要求9所述的系统，其中所述主机处理器件被配置以在运行期间：
执行指令的计算线程，所述指令的所述计算线程产生要将所述错误修正代码的所述计算分担到所述能够重新编程的处理器件的请求，以及
创建所述指令的回调线程，以控制所述能够重新编程的处理器件，以及
创建所述指令的至少一个输入/输出线程，以从所述存储器读取所述多个数据元或者将所述错误修正代码读取到所述存储器。
11.根据权利要求10所述的系统，其中所述主机处理器件被配置以当产生奇偶性数据元时：
响应于将分担请求列入队列而暂停所述计算线程；
响应于所述回调线程表明所述能够重新编程的处理器件已计算所述错误修正代码，重新开始所述计算线程；以及
使所述输入/输出线程将所述错误修正代码作为所述奇偶性数据元写入到所述存储器。
12.根据权利要求11所述的系统，其中所述主机处理器件被配置以当重构数据元时：
使所述输入/输出线程将所述多个数据元从所述存储器读取到所述能够重新编程的处理器件；
暂停所述计算线程，直到所述输入/输出线程表明所述能够重新编程的处理器件已接收到所述多个数据元；以及
一旦所述能够重新编程的处理器件已计算所述错误修正代码，便通知所述指令的用户线程所述数据元已被重构。
13.根据权利要求9所述的系统，其中所述能够重新编程的处理器件包括：
主机接口电路，被配置以从所述主机处理器件接收分担指令；
存储接口电路，被配置以接收所述多个数据元；
多个存储缓冲器电路，被配置以临时存储所述多个数据元；以及
多个错误代码计算电路，被配置以至少部分地计算所述错误修正代码而不由所述主机处理器件进行额外处理。
14.根据权利要求9所述的系统，其中所述主机处理器件与所述能够重新编程的处理器件被配置以通过直接存储器存取进行通信。
15.根据权利要求9所述的系统，其中所述存储器与所述能够重新编程的处理器件被配置以通过直接存储器存取进行通信。
16.一种用于错误修正代码的加速的装置，包括：
主机处理器件，被配置以将所述错误修正代码的计算分担到分担处理器件；
输入/输出系统，被配置以读取多个数据元并将所述多个数据元写入到多个存储器件；以及
所述分担处理器件，被配置以至少部分地基于所述多个数据元来计算所述错误修正代码，其中所述分担处理器件包括：
存储接口电路，被配置以接收所述多个数据元；
多个存储缓冲器电路，被配置以临时存储所述多个数据元；
多个错误代码计算电路，被配置以至少部分地计算所述错误修正代码而不由所述主机处理器件进行额外处理。
17.根据权利要求16所述的装置，其中所述分担处理器件被配置以通过以下方式计算所述错误修正代码：
将所述多个数据元分割成多个子部分；
按每一子部分执行所述多个数据元的多个遍次；以及
对每一遍次的输出进行聚合，以形成所述错误修正代码。
18.根据权利要求16所述的装置，其中所述多个数据元与数据节点的数目相关联；以及
其中所述多个错误代码计算电路内的数目能够重新配置以与所述数据节点的所述数目相匹配，使得在所述数据节点与所述多个错误代码计算电路之间存在关联。
19.根据权利要求16所述的装置，其中所述多个错误代码计算电路包括由交替的乘法电路与加法电路形成的树；以及
其中所述乘法电路包括查找表，且
其中所述加法电路包括异或门。
20.根据权利要求16所述的装置，其中所述分担处理器件被配置以：
响应于编码请求，计算所述错误修正代码作为奇偶检验元，以及
响应于解码请求，计算所述错误修正代码作为重建数据元。
CN201911143197.3A 2018-12-14 2019-11-20 用于错误修正代码的加速的装置及系统 Active CN111324479B (zh)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US201862780185P 2018-12-14 2018-12-14
US62/780,185 2018-12-14
US16/271,777 2019-02-08
US16/271,777 US11061772B2 (en) 2018-12-14 2019-02-08 FPGA acceleration system for MSR codes

Publications (2)

Publication Number Publication Date
CN111324479A true CN111324479A (zh) 2020-06-23
CN111324479B CN111324479B (zh) 2022-08-09

Family

ID=71072501

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911143197.3A Active CN111324479B (zh) 2018-12-14 2019-11-20 用于错误修正代码的加速的装置及系统

Country Status (5)

Country Link
US (3) US11061772B2 (zh)
JP (1) JP7356887B2 (zh)
KR (1) KR102491112B1 (zh)
CN (1) CN111324479B (zh)
TW (1) TWI791891B (zh)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10949301B2 (en) * 2011-06-06 2021-03-16 Pure Storage, Inc. Pre-positioning pre-stored content in a content distribution system
WO2018176238A1 (en) 2017-03-28 2018-10-04 Intel Corporation Technologies for hybrid field-programmable gate array-application-specific integrated circuit code acceleration
US11061772B2 (en) * 2018-12-14 2021-07-13 Samsung Electronics Co., Ltd. FPGA acceleration system for MSR codes
US11934330B2 (en) 2020-05-08 2024-03-19 Intel Corporation Memory allocation for distributed processing devices
US11568089B2 (en) * 2020-08-31 2023-01-31 Frontiir Pte Ltd. Offloading operations from a primary processing device to a secondary processing device
US11868777B2 (en) 2020-12-16 2024-01-09 Advanced Micro Devices, Inc. Processor-guided execution of offloaded instructions using fixed function operations
US12073251B2 (en) * 2020-12-29 2024-08-27 Advanced Micro Devices, Inc. Offloading computations from a processor to remote execution logic
US11625249B2 (en) 2020-12-29 2023-04-11 Advanced Micro Devices, Inc. Preserving memory ordering between offloaded instructions and non-offloaded instructions
US12468474B2 (en) * 2021-11-15 2025-11-11 Samsung Electronics Co., Ltd. Storage device and method performing processing operation requested by host
US12197378B2 (en) 2022-06-01 2025-01-14 Advanced Micro Devices, Inc. Method and apparatus to expedite system services using processing-in-memory (PIM)
US12050531B2 (en) 2022-09-26 2024-07-30 Advanced Micro Devices, Inc. Data compression and decompression for processing in memory
US12147338B2 (en) 2022-12-27 2024-11-19 Advanced Micro Devices, Inc. Leveraging processing in memory registers as victim buffers
US12265470B1 (en) 2023-09-29 2025-04-01 Advanced Micro Devices, Inc. Bypassing cache directory lookups for processing-in-memory instructions
US12455826B2 (en) 2024-03-29 2025-10-28 Advanced Micro Devices, Inc. Dynamic caching policies for processing-in-memory

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1040698A (zh) * 1988-09-02 1990-03-21 三菱电机株式会社 错误校正电路
CN101740135A (zh) * 2008-11-18 2010-06-16 富士通株式会社 错误判断电路和共享的存储器系统
US20160110254A1 (en) * 2014-10-15 2016-04-21 Empire Technology Development Llc Partial Cloud Data Storage
US20170179979A1 (en) * 2015-12-18 2017-06-22 Netapp, Inc. Systems and Methods for Minimum Storage Regeneration Erasure Code Construction Using r-Ary Trees
US20180300201A1 (en) * 2017-04-17 2018-10-18 Intel Corporation Bypassing error correction code (ecc) processing based on software hint

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7673222B2 (en) * 2005-07-15 2010-03-02 Mediatek Incorporation Error-correcting apparatus including multiple error-correcting modules functioning in parallel and related method
WO2010041093A1 (en) * 2008-10-09 2010-04-15 Federico Tiziani Virtualized ecc nand
US8356137B2 (en) * 2010-02-26 2013-01-15 Apple Inc. Data storage scheme for non-volatile memories based on data priority
US8650446B2 (en) * 2010-03-24 2014-02-11 Apple Inc. Management of a non-volatile memory based on test quality
CN102624866B (zh) * 2012-01-13 2014-08-20 北京大学深圳研究生院 一种存储数据的方法、装置及分布式网络存储系统
WO2014131148A1 (zh) 2013-02-26 2014-09-04 北京大学深圳研究生院 一种最小存储再生码的编码和存储节点修复方法
US9021188B1 (en) 2013-03-15 2015-04-28 Virident Systems Inc. Small block write operations in non-volatile memory systems
US9547458B2 (en) 2014-12-24 2017-01-17 International Business Machines Corporation Intra-rack and inter-rack erasure code distribution
US10007587B2 (en) 2015-09-18 2018-06-26 Qualcomm Incorporated Systems and methods for pre-generation and pre-storage of repair fragments in storage systems
US10452477B2 (en) 2016-08-26 2019-10-22 Netapp, Inc. Multiple node repair using high rate minimum storage regeneration erasure code
US11061772B2 (en) * 2018-12-14 2021-07-13 Samsung Electronics Co., Ltd. FPGA acceleration system for MSR codes

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1040698A (zh) * 1988-09-02 1990-03-21 三菱电机株式会社 错误校正电路
CN101740135A (zh) * 2008-11-18 2010-06-16 富士通株式会社 错误判断电路和共享的存储器系统
US20160110254A1 (en) * 2014-10-15 2016-04-21 Empire Technology Development Llc Partial Cloud Data Storage
US20170179979A1 (en) * 2015-12-18 2017-06-22 Netapp, Inc. Systems and Methods for Minimum Storage Regeneration Erasure Code Construction Using r-Ary Trees
US20180300201A1 (en) * 2017-04-17 2018-10-18 Intel Corporation Bypassing error correction code (ecc) processing based on software hint

Also Published As

Publication number Publication date
US20230367675A1 (en) 2023-11-16
JP2020095722A (ja) 2020-06-18
TW202026871A (zh) 2020-07-16
US20200192757A1 (en) 2020-06-18
US20210334162A1 (en) 2021-10-28
US11061772B2 (en) 2021-07-13
KR102491112B1 (ko) 2023-01-20
KR20200073978A (ko) 2020-06-24
CN111324479B (zh) 2022-08-09
US11726876B2 (en) 2023-08-15
US12117903B2 (en) 2024-10-15
JP7356887B2 (ja) 2023-10-05
TWI791891B (zh) 2023-02-11

Similar Documents

Publication Publication Date Title
TWI791891B (zh) 用於錯誤修正代碼的加速的裝置及系統
CN111435292B (zh) 利用自适应写缓冲区释放的存储介质编程
US12346202B2 (en) System, device and method for storage device assisted low-bandwidth data repair
US11086525B2 (en) Resilient external memory
US11467902B2 (en) Apparatus to insert error-correcting coding (ECC) information as data within dynamic random access memory (DRAM)
US10430336B2 (en) Lock-free raid implementation in multi-queue architecture
US9632831B2 (en) Distributed real-time computing framework using in-storage processing
CN110572164A (zh) Ldpc译码方法、装置、计算机设备及存储介质
CN111610932B (zh) 减少键值存储服务器的漏洞窗口而不牺牲可用容量的系统
US20220067212A1 (en) Offloading operations from a primary processing device to a secondary processing device
US20220069942A1 (en) Error correction for network packets

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant