可重构运算装置、数据压缩装置和可重构运算方法

摘要

本发明公开一种可重构运送装置、数据压缩装置和可重构运算方法可重构运算装置包括可重构电路、存储单元和控制单元。可重构电路具有多个小电路，并且基于所记录的电路信息利用从多个小电路中选出的小电路来重构电路。存储单元存储分别与第一压缩电路和第二压缩电路对应的第一电路信息和第二电路信息。控制电路根据输入数据串，通过将第一电路信息或第二电路信息记录在可重构电路中，来将可重构电路重构成第一压缩电路或第二压缩电路。

说明书

技术领域

本发明涉及可重构运算装置、数据压缩装置和可重构运算方法。

背景技术

尽管行程长度压缩为简单算法，但由于该算法与图像数据很好 地匹配，因此通常用作图像数据压缩方法。行程长度压缩是用长度 (行程长度)信息替换具有相同值的连续段(行程)的方法。

对于执行行程长度压缩的数据压缩装置，例如， JP-A-2000-261675公开了一种数据压缩装置。

该数据压缩装置输入图像数据串并且输出各颜色像素连续的行 程长度，并且该数据压缩装置包括：变化点检测电路，其接收m位 图像数据串的输入，并且输出像素变化的像素变化点；以及行程分 解电路，其接收变化点检测电路的输出并且将m位图像数据串最大 限度地分解成n个行程。

发明内容

本发明一些方面的优点是提供可重构运算装置、数据压缩装置 和可重构运算方法，其中与始终执行并行处理的构造相比，所述方 法可以在不增加电路规模的情况下压缩数据。

[1]根据本发明的一方面，可重构运算装置包括可重构电路、 存储单元和控制单元。可重构电路具有多个小电路，并且基于所记 录的电路信息利用从多个小电路中选出的小电路来重构电路。存储 单元存储分别与第一压缩电路和第二压缩电路对应的第一电路信息 和第二电路信息。控制电路根据输入数据串，通过将第一电路信息 或第二电路信息记录在可重构电路中，来将可重构电路重构成第一 压缩电路或第二压缩电路。

[2]根据本发明的另一个方面，数据压缩装置包括根据项[1]所 述的可重构运算装置。第一压缩电路是对输入数据串执行行程长度 压缩的电路。第二压缩电路为以下电路，(i)输入作为多个并行数 据串的输入数据串，(ii)执行关于多个并行数据串的行程判断以及 (iii)基于行程判断执行行程长度压缩。控制电路根据第一压缩电路 或第二压缩电路的输入数据的行程长度，将第一电路信息或第二电 路信息记录在可重构电路中。

[3]在项[2]所述的数据压缩装置中，第一压缩电路和第二压缩 电路构造成，通过分别向第一通道和第二通道输入输入数据串来执 行行程长度压缩，并且控制单元根据输入数据串的行程长度和可用 小电路的空状态来判断输入至第二压缩电路的第一通道和第二通道 的并行数据串的量，并且将与所确定的并行数据串的量对应的第二 电路信息记录在可重构电路中。

[4]根据本发明的另一方面，一种用于可重构运算装置的可重 构运算方法，所述可重构运算装置包括：可重构电路，其具有多个 小电路，并且其基于所记录的电路信息利用从多个小电路中选出的 小电路来重构电路；以及存储单元，其存储分别与第一压缩电路和 第二压缩电路对应的第一电路信息和第二电路信息，所述运算方法 包括：根据输入数据串，通过将第一电路信息或第二电路信息记录 在可重构电路中，来将可重构电路重构成第一压缩电路或第二压缩 电路。

利用项[1]和项[4]所述的构造，与始终执行并行处理的构造相 比，可以在不增加电路规模的情况下压缩数据。

利用项[2]所述的构造，可以简单地压缩数据。

利用项[3]所述的构造，可以有效地使用小电路。

附图说明

将基于附图详细描述本发明的示例性实施例，其中：

图1是示出根据本发明第一实施例的数据压缩装置的示意性构 造的正视图；

图2是示出可重构运算装置的构造实例的框图；

图3是示出典型电路的构造实例的框图；

图4是示出高速电路的构造实例的框图；

图5是示出可重构运算装置的整个操作实例的流程图；

图6是示出判断程序的操作实例的流程图；

图7A至图7E示出了压缩操作的详细实例，其中图7A是示出 输入数据实例的视图，图7B是示出运算电路的视图，图7C是示出 输出数据实例的视图，图7D是示意性示出典型电路的视图，以及图 7E是示意性示出高速电路的视图；

图8A至图8C是示出根据本发明第二实施例在重构之后的可重 构电路实例的视图；

图8D至图8F是示出根据本发明第二实施例在重构之后的可重 构电路实例的视图；

图9是示出本发明第二实施例的操作实例的流程图；以及

图10是示出本发明第二实施例的操作实例的流程图。

具体实施方式

图1是示出根据本发明第一示例性实施例的数据压缩装置的构 造实例的正视图；

数据压缩装置1包括：CPU 2，其控制数据压缩装置的各个单 元；可重构运算装置10；存储器4；DMAC(直接存储存取控制器) 5；以及仲裁器6，其经通过总线3与CPU 2连接。

例如，数据压缩装置1可应用于在图像形成装置中传送数据的 情况，诸如对图像读取单元所读取的数据进行压缩并将其输出至图 像处理单元；以及在装置与装置之间压缩并传送数据的情况，诸如 在PC(个人计算机)与如打印机和复印机等具有多种功能的多功能 装置之间，或者在PC与如传真机等图像形成装置之间。在该情况下， 数据压缩装置1的应用实例不限于上述情形。

存储器4存储压缩之前的数据和通过根据本实施例的方法对压 缩之前的数据进行压缩而获得的数据。

DMAC 5直接控制在存储器4与可重构运算装置10之间的 DMA数据传送，且不经过CPU 2的处理。

仲裁器6用作在DMAC 5等执行数据传送时进行总线3的使用 权判断的判断单元。

图2是示出可重构运算装置10的构造实例的框图。可重构运算 装置10包括：控制单元11，其基于判断程序110和重构控制程序 111来控制可重构运算装置10的各个单元；可重构电路12，其能够 重构电路；以及构造数据存储单元13，其作用存储电路信息的存储 单元。

可重构电路12也称DRP(动态可重构处理器)。可重构电路 12包括诸如ALU(算术逻辑单元)、RAM(随机存取存储器)等多 个小电路，并且能够基于所记录的电路信息利用从多个小电路中选 出的小电路来重构电路。

构造数据存储单元13存储第一构造数据130和第二构造数据 131，第一构造数据用于将可重构电路12重构成典型电路，第二构 造数据用于将可重构电路12重构成高速电路。在该情况下，构造数 据存储单元13还可以存储将可重构电路12重构成除典型电路和高 速电路以外的其它电路的构造数据。第一重构数据130是第一电路 信息的实例，而第二重构数据131是第二电路信息的实例。另外， 典型电路是第一压缩电路的实例，而高速电路是第二压缩电路的实 例。

控制单元11基于判断程序110和重构控制程序111来执行处 理。控制单元11通过判断程序110来判断由可重构电路12获得的 状态信息，并且向重构控制程序111输出作为判断结果的判断信息。 此外，控制单元11构造成，基于由判断程序110输出的判断信息并 通过重构控制程序111对可重构电路12执行重构控制，并且对构造 数据存储单元13执行构造控制。

判断程序110构造成，监视来自可重构电路12的状态信息，并 且如果包含于状态信息的行程长度等于或大于阈值(例如，4)，则 判断程序110选择高速电路，而如果行程长度小于阈值，则判断程 序110选择典型电路。判断程序110将与所选电路有关的信息通知 重构控制程序111。

如果判断程序110通知选择了典型电路，则重构控制程序111 通过将构造数据存储单元13中的第一构造数据载入可重构电路12 来将可重构电路12重构成典型电路12a。另外，如果判断程序110 通知选择了高速电路，则重构控制程序111通过将构造数据存储单 元13中的第二构造数据131载入可重构电路12来将可重构电路12 重构成高速电路12b。

图3是示出典型电路的构造实例的框图。如图3中所示，通过 将第一构造数据130载入可重构电路12来将可重构电路12重构成 典型电路12a。

典型电路12a是执行输入数据串的行程长度压缩的电路，并且 包括判断单元120a、行程长度计数器121a、行程长度控制单元122a、 数据控制单元123、FIFO单元124a、合并单元125和重构中断判断 单元126。

判断单元120a，例如，接收从存储器4通过DMAC 5传送的输 入数据。另外，判断单元120a判断是否存在与输入数据具有相同值 的数据的连续部分(行程)。输入数据可以为，例如，具有与黑色 和白色对应的两个值或与多种颜色(例如，红、绿和蓝)对应的多 个值的图像数据。在该情况下，输入数据不限于图像数据。

行程长度计数器121a对判断单元120a判断的行程计数，并且 输出行程的长度(行程长度Ln)。

行程长度控制单元122a将从行程长度计数器121a输出的行程 长度按像素输出至FIFO单元24a。另外，行程长度控制单元122a 产生包含电路信息的状态信息，并且向判断程序110输出状态信息， 所述电路信息指示出行程长度和当前可重构电路12是典型电路12a 还是高速电路12b。

数据控制单元123按像素向FIFO单元124输出输入数据。

FIFO单元124a对来自数据控制单元123的数据和来自行程长 度控制单元122a的行程长度进行缓冲，并且根据合并单元125进行 处理所需的时间长度使数据和行程长度延迟，以便向合并单元125 输出延迟后的数据和行程长度。

合并单元125通过合并行程和数据来生成输出数据。例如，输 出数据通过DMAC 5传送至存储器4。

如果由CPU 2等产生结束中断，则重构中断判断单元126向控 制单元11输出结束中断信号Si。

图4是示出高速电路的构造实例的框图。如图4中所示，通过 将第二构造数据131载入可重构电路12来将可重构电路12重构成 高速电路12b。

高速电路12b是输入作为多个(在本实施例中为4个)并行数 据串的输入数据串，并且通过对多个(4个)数据串执行行程判断来 执行行程长度压缩的电路。高速电路12b包括判断单元120b、行程 长度计数器121b、行程长度控制单元122b、、FIFO单元124b和重 构中断判断单元126。在不使用典型电路12a所使用的数据控制单元 123和合并单元125的情况下来构造高速电路12b。

判断单元120b按像素输入多个(在本实施例中为4个)并行数 据串，并且判断是否存在与输入数据具有相同值的数据的连续部分 (行程)。由判断单元120b判断的并行数据串的量对应于判断程序 110所使用的阈值(4)。

行程长度计数器121b对判断单元120b并行判断的行程计数， 并且输出作为计数和的行程长度。

行程长度控制单元122b构造成，当途中行程不连续(例如，行 程长度小于4)并发生重构时，仅在不连续之前的连续行程中保持数 据。行程长度计数器121b合并并且输出输出行程长度和保持数据。

FIFO单元124b输出通过将行程长度和由行程长度控制单元 122b输出的数据合并所获得的数据，作为连续输出数据。

图5是示出可重构运算装置10的整个操作实例的流程图。重构 控制程序111将构造数据存储单元13中的第一构造数据130载入可 重构电路12(步骤S1)。在载入第一构造数据时，将可重构电路12 重构成典型电路12a。

重构控制程序111启动可重构电路12，即典型电路12a的处理 (步骤S2)。

重构中断判断单元126判断是否存在结束中断(步骤S3)，并 且如果判断出存在结束中断(步骤S3中为是)，则重构中断判断单 元126向控制单元11输出结束中断信号Si。

重构控制程序111基于来自重构中断判断单元126的结束中断 信号Si来停止由可重构电路12执行的处理(步骤S4)。

在步骤S3中，如果重构中断判断单元126判断出不存在结束中 断(步骤S3中为否)，则由于未从重构中断判断单元126输出结束 中断信号Si，判断程序110基于来自可重构电路12的状态信息来判 断是否执行重构(步骤S6)。如果判断出执行重构(步骤S6中为是)， 则判断程序110将选择高速电路的信息通知重构控制程序111(步骤 S7)。

重构控制程序111停止由可重构电路12执行的处理(步骤S8)， 并且将构造数据存储单元13中的选择高速电路的第二构造数据131 载入可重构电路12(步骤S9)。将可重构电路12重构成高速电路 12b。重构控制程序111重启由可重构电路12执行的处理(步骤S10)。

图6是示出判断程序110的操作实例的流程图。该附图示出了 图5中的步骤S5、步骤S6和步骤S7的细节。

判断程序110从可重构电路12获取状态信息(步骤S21)，并 且根据状态信息判断当前电路为典型电路12a还是高速电路12b(步 骤S22)。如果判断程序110判断出当前电路为典型电路12a(步骤 S22)，则判断程序110判断行程长度Ln是否等于或大于阈值Th(例 如，4)(步骤S23)。如果行程长度Ln等于或大于阈值Th(步骤 S23中为是)，则判断程序110选择高速电路12b，并且通知重构控 制程序111已经选择高速电路12b(步骤S24)。如果行程长度Ln 小于阈值Th(步骤S23中为否)，则判断程序110选择不重构(步 骤S25)。

在步骤S22中，如果判定当前电路为高速电路12b(步骤S22)， 则判断程序110判断行程长度Ln是否为最大行程长度，该最大行程 长度可以用一般的行程长度压缩方法来压缩(步骤S26)。如果行程 长度Ln不是最大行程长度(步骤S26中为否)，则判断程序110判 断行程是否连续(步骤S27)，并且如果行程不连续(步骤S27中为 否)，则判断程序110判断行程长度Ln是否等于或大于阈值Th(步 骤S28)。如果行程长度Ln小于阈值Th(步骤S28中为否)，则判 断程序110选择典型电路12a，并且通知构造控制程序111已经选择 典型电路12a(步骤S29)。

在步骤S26中行程长度变为最大行程长度(步骤S26中为是) 的情况下，在步骤S27中行程连续(步骤S27为是)的情况下，或 者在步骤S28中行程长度Ln等于或大于阈值Th(步骤S28中为是) 的情况下，判断程序选择不重构(步骤S30)。

图7A至图7E示出了压缩操作的详细实例。具体地说，图7A 是示出输入数据实例的视图，图7B是示出压缩输入数据的电路的视 图，图7C是示出输出数据实例的视图，图7D是示意性示出典型电 路的视图，以及图7E是示意性示出高速电路的视图。

如图7A所示，由于输入数据片段“AABCC”中的行程长度小 于阈值(4)，因此将可重构电路12重构成典型电路12a以处理输 入数据。如图7D所示，典型电路12a通过判断各个像素(px)的行 程是否存在来压缩输入数据，并且输出输出数据“2AB2C”。

在下一组输入数据“DDDDD……DDDDD”中，行程长度等于 或大于阈值(4)，进而将可重构电路12重构成高速电路12b以处 理输入数据。如图7E中所示，高速电路12b对输入数据执行并行处 理，并且输出输出数据“256D 256D 120D”。

在下一组输入数据“A”中，行程长度小于阈值(4)，进而将 可重构电路12重构成典型电路12a以处理输入数据。典型电路12a 将输入数据“A”输出为输出数据“A”。

在下一组数据“BBBBB……BBBBB”中，行程长度等于或大于 阈值(4)，进而将可重构电路12重构成高速电路12b以处理输入 数据。如图7E所示，高速电路12b对输入数据执行并行处理，并且 输出输出数据“256B 256B 200B”。

在下一组输入数据“CCCD”中，行程长度小于阈值(4)，进 而将可重构电路12重构成典型电路12a以处理输入数据。如图7D 所示，典型电路12a压缩输入数据“CCCD”，并且输出输出数据 “3CD”。

图8A至图8F是示意性示出根据本发明第二实施例的在重构之 后的可重构电路实例的视图。在图8A至图8F中，省略了行程长度 计数器、数据控制单元、行程长度控制单元和构造中断判断单元。

在第一实施例中，示例出了输入数据经由通道1(ch1)输入的 例子，而在第二实施例中，示例出了输入数据经由通道1(ch1)和 通道2(ch2)输入的例子。如下文将描述的图8A至图8F所示，构 造数据存储单元13存储用于重构电路的构造数据。

如图8A所示，在该实施例中，典型电路12a包括：判断单元 120a₁，其作为通道1处理输入数据X₁，；FIFO单元124a₁；合并单元 125a₁；判断单元120a₂，其作为通道2处理输入数据X₂；FIFO单元 124a₂；以及合并单元125a₂。

如图8B所示，4×1并行高速电路12b₁包括：判断单元120b₁， 其作为通道1处理4串输入数据X₁；FIFO单元124b₁；判断单元120b₂， 其作为通道2处理一串输入数据X₂；FIFO单元124b₂；以及合并单 元125b₂。

如图8C所示，8×1并行高速电路12b₂包括：判断单元120b₁， 其作为通道1处理8串输入数据X₁；FIFO单元124b₁；判断单元120b₂， 其作为通道2处理一串输入数据X₂；FIFO单元124b₂；以及合并单 元125b₂。

如图8D所示，1×4并行高速电路12b₁包括：判断单元120b₁， 其作为通道1处理一串输入数据X₁；FIFO单元124b₁；合并单元 125b₁；判断单元120b₂，其作为通道2处理4串输入数据X₂；以及 FIFO单元124b₂。

如图8E所示，4×4并行高速电路12b₁包括：判断单元120b₁， 其作为通道1处理4串输入数据；FIFO单元124b₁；判断单元120b₂， 其作为通道2处理4串输入数据X₂。

如图8F所示，1×8并行高速电路12b₂包括：判断单元120b₁， 其作为通道1处理一串输入数据X₁；FIFO单元124b₁；合并单元 125b₁；判断单元120b₂，其作为通道2处理8串输入数据X₂；以及 FIFO单元124b₂。

图9和图10是示出本发明第二实施例的操作实例的流程图。

通过获取通道(ch)1的状态信息来执行关于ch1的判断处理(步 骤S41)，并且通过获取通道(ch)2的状态信息来执行关于ch2的 判断处理(步骤S43)。

判断当前构造，并且判断并行数据串的量是否等于当前状态(步 骤S45)。如果并行数据串的量等于当前状态(步骤S45中为是)， 则选择不重构(步骤S46)。如果并行数据串的量不同于当前状态(步 骤S45中为否)，则通知重构控制程序111判断的构造(步骤S47)。

在步骤S42和步骤S44中，执行如图10所示的处理。下面，将 参考图10描述判断处理。

判断途中行程是否不连续(步骤S51)，并且如果途中行程并 非不连续(步骤S51中为否)，则确定通道x中并行数据串的量。

如果通道x中并行数据串的量为“1”，则判断行程长度Ln是 否等于或大于阈值Th(4)，并且判断原数据串中是否存在空部分(步 骤S53)。如果行程长度Ln等于或大于阈值Th，并且原数据串中存 在空部分(步骤S53中为是)，则将并行数据串的量设定为“4”(步 骤S54)，而如果行程长度Ln小于阈值Th或如果原数据串中不存 在空部分，即使行程长度Ln等于或大于阈值Th(步骤S53中为否)， 则也将并行数据的量设定为“1”(步骤S55)。

如果通道x中并行数据串的量为“4”，则判断行程长度Ln是 否等于或大于阈值Th×2，并且判断原数据串中是否存在空部分(步 骤S56)。如果行程长度Ln等于或大于阈值Th×2，并且原数据串 中存在空部分(步骤S56中为是)，则将并行数据串的量设定为“8” (步骤S57)，而如果行程长度Ln小于阈值Th×2或如果原数据串 中不存在空部分，即使行程长度Ln等于或大于阈值Th×2(步骤S56 中为否)，则也将并行数据的量设定为“1”(步骤S58)。

如果通道x中并行数据串的量为“8”，则判断行程长度Ln是 否等于或大于阈值Th×2，并且判断原数据串中是否存在空部分(步 骤S59)。如果行程长度Ln等于或大于阈值Th×2，并且原数据串 中存在空部分(步骤S59中为是)，则将并行数据串的量设定为“8” (步骤S60)，而如果行程长度Ln小于阈值Th×2或如果原数据串 中不存在空部分，即使行程长度Ln等于或大于阈值Th×2(步骤S59 中为否)，则也将并行数据的量设定为“1”(步骤S61)。

在第二实施例中，尽管通道量设定为“2”，但也可以设定为 “3”或更高。

本发明不限于上述实施例，并且在不脱离本发明范围的情况下 可以对本发明进行各种修改。例如，用于上述实施例的程序可以存 储并设置在诸如CD-ROM等记录介质中。另外，可以用诸如ASIC 等硬件来实现根据上述实施例的各个装置的一部分或所有部分。此 外，可以对上述实施例描述的步骤进行变换、删除和添加等。

出于示例和说明的目的提供了本发明的示例性实施例的上述说 明。其意图不在于穷举或将本发明限制为所公开的确切形式。显然， 对于本领域的技术人员而言许多修改和变型是显而易见的。选择和 说明这些实施例是为了最佳地解释本发明的原理及其实际应用，从 而使得本领域的其他人员能够理解各种实施例的发明和适合于特定 预期应用的各种修改。本发明的目的在于用所附权利要求书及其等 同内容来限定本发明的范围。