基于流水线架构的海量文件指导型预取并行处理加速方法

摘要

本发明公开了一种基于流水线架构的海量文件指导型预取并行处理加速方法，该加速方法包括应用程序依据海量文件的预取信息，使用进程从外部存储器提取预取文件到内存缓冲区的步骤；进程对预取文件进行分阶段计算的步骤；进程对并行处理结果进行输出的步骤。本发明的加速方法基于流水线架构，采用指导型预取对海量文件进行提前处理，并且将海量文件的计算过程分为多个阶段，使其在多个阶段并行进行，提高了系统的执行效率。在数据预取阶段，本发明采用了指导型预取，将海量文件的预取行为置于应用程序的控制之下，使其更准确、更有预见性地进行预取，从而提高了海量文件预取和处理的效率。

说明书

技术领域

本发明涉及一种计算机中的海量数据处理，特别地是涉及一种基于流水线架构的 海量文件处理指导型预取并行处理加速方法。

背景技术

随着互联网技术的发展和云计算的兴起，海量数据的处理需求日益增长，其中， 针对海量文件（mass file）（例如网页、图片、视频、音频等）的处理尤其增多。这 些处理操作步骤繁杂，需要频繁的访问文件系统和外部存储系统，同时又需要快速地 返回处理结果，对系统的高并发性、低延迟性要求极高。因此，加速海量文件的处理 速度对于提升海量数据处理性能有着重要的意义。为了方便说明，海量文件简称为 F，采用集合表示为F＝{f₁,f₂,…,f_a}，f₁表示海量文件的第一个文件（file），f₂表示海量文件的第二个文件，f_a表示海量文件的最后一个文件，为了方便也称为海 量文件的任意一个文件，a表示海量文件的个数。

流水线架构（pipeline framework），是把一件任务分解为若干个按先后顺序执 行的子任务（sub task），不同的子任务由不同的阶段（process）来负责执行，前 一个阶段的输出作为后一个阶段的输入，所有这些阶段可以并行工作，其阶段工作总 时间记为T_总。在任意一个时刻，任意一个任务只占用其中一个子阶段（sub  process），这样就可以实现多个任务的重叠执行，以提高工作效率。对于处理海量 文件的流水线架构，是将繁杂的海量文件处理过程分成多个阶段并行进行，每个处理 阶段完成各自工作后，再交由下一处理阶段处理。

随着多核或众核处理器的使用，处理器硬件计算性能快速增长，与此同时，外部 存储系统性能的增长却要缓慢的多，导致文件访问性能提升较慢。因此，计算、存储、 输入/输出（即I/O）的速度越来越不匹配，输入/输出访问时延已经成为制约系统 性能的一个最主要的瓶颈。海量文件处理需要频繁访问存储系统，更会加剧输入/输 出的访问延迟。

预取（prefetching），是提高系统的输入/输出性能的有效手段，指系统在后台 提前进行的数据输入/输出，将所需数据提前加载到内存的过程，以隐藏应用程序的 输入/输出延迟，从而可以有效地提高计算机系统的利用率。预取主要分为两类，猜 测型预取（predictive prefetching）和指导型预取（informed prefetching）。

猜测型预取是基于过去的输入/输出信息进行建模，预测下一步要预取的数据。

指导型预取是应用程序通知文件系统预取的内容，告诉预取进程/线程即将要进 行的输入/输出操作和文件信息。

应用程序（application）通过预取信息（prefetching information，简称为PI） 对外部存储系统中的对海量文件F＝{f₁,f₂,…,f_a}进行预取，从而得到预取文件 （prefetching file），预取文件记为MF＝{mf₁,mf₂,…,mf_n}中的任意一个文件，即 mf_n。预取信息PI为预取文件MF＝{mf₁,mf₂,…,mf_n}的路径，所述路径记为i， 且i＝1,2,…,n，n∈a，n表示预取文件的文件个数。mf₁表示从海量文件中预取的 第一个预取文件，mf₂表示从海量文件中预取的第二个预取文件，mf_n表示从海量文 件中预取的最后一个预取文件，为了方便也称为任意一个预取文件。

发明内容

为了改善海量文件的处理速度，以及通过应用程序提供给外部存储系统准确的预 取信息，提高预取的精度，本发明提出一种基于流水线架构的海量文件指导型预取加 速的并行处理方法。该架构采用流水线处理方法，采用指导型预取对海量文件进行提 前处理，并且将海量文件的计算过程分为多个阶段，使其在多个阶段并行进行，提高 了系统执行效率。在数据预取阶段，本发明采用了指导型预取，将海量文件的预取行 为置于应用程序的控制之下，使其更准确、更有预见性地进行预取，从而提高了海量 文件预取和处理的效率。

在本发明中，提出了一种基于流水线架构的海量文件指导型预取并行处理加速方 法，该方法包括有三个步骤：在各个步骤中对海量文件采用并行处理；

第一步骤：应用程序依据海量文件的预取信息，使用进程/线程（下述统一称为 进程）从外部存储系统提取预取文件到内存缓冲区的步骤；

第二步骤：进程对预取文件进行分阶段计算的步骤；

第三步骤：进程对并行处理结果进行输出的步骤。

本发明针对海量文件指导型预取的并行处理加速方法的优点在于：

①本发明加速方法依据流水线架构将海量文件的处理划分为预取、计算、输出三个 阶段，使海量文件的处理在多个阶段并行进行，其中，计算阶段又分为多个子计 算阶段，同样可以以流水线的形式并行处理。此种架构有效地提高了海量文件的 处理效率。

②本发明在流水线架构的预取阶段采用了指导型预取，在程序员编写程序的过程中 定义需要预取的海量文件列表，将预取行为置于应用程序的控制之下，提高了海 量文件预取的准确性和处理效率。

附图说明

图1是海量文件串行处理的流程图。

图2是本发明基于流水线架构的海量文件并行处理的流程图。

图3是本发明基于流水线架构的海量文件处理的串行、并行执行时间的对比图。

图4是本发明基于流水线架构的海量文件处理的加速比图。

图5是本发明基于流水线架构的海量文件指导型预取并行处理的流程图。

具体实施方式

下面将结合附图对本发明做进一步的详细说明。

参见图1所示，海量文件的串行处理中，以处理时间为横坐标，纵坐标为无量 纲建立平面坐标系。对文件进行处理时，先处理第一个文件f₁、然后处理第二个文 件f₂、……、最后处理第a个文件f_a。

所述第一个文件f₁顺次经读取阶段第一子计算阶段第二子计算阶段 ……、最后子计算阶段输出阶段处理第一个文件f₁的时间记为

所述第二个文件f₂顺次经读取阶段第一子计算阶段第二子计算阶段 ……、最后子计算阶段输出阶段处理第二个文件f₂的时间记为

所述第a个文件f_a顺次经读取阶段第一子计算阶段第二子计算阶段 ……、最后子计算阶段输出阶段处理第a个文件f_a的时间记为

在串行处理时，对文件的总处理时间记为T_串总（简称为串行总时间），

在本发明中，基于流水线架构，将任意一个预取文件mf_n的处理分为预取、计算、 输出三个阶段；所述计算阶段中包括多个子计算阶段，分别记为C¹、C²、……、C^g（g表示某一子计算阶段的标识），C¹表示第一个子计算阶段，C²表示第二个子计 算阶段，C^g表示最后一个子计算阶段，也可以称为任意一个子计算阶段。对于所述 预取阶段是本发明中的第一步骤，所述输出阶段是本发明中的第三步骤。

在本发明中，提出了一种基于流水线架构的海量文件指导型预取并行处理加速方 法，该方法包括有三个步骤：

第一步骤：应用程序依据海量文件的预取信息，使用进程/线程（下述统一称为 进程）从外部存储系统提取预取文件到内存缓冲区的步骤；

第二步骤：进程对预取文件进行分阶段计算的步骤；

第三步骤：进程对并行处理结果进行输出的步骤。

参见图2所示，海量文件的并行处理中，以并行总时间为横坐标，纵坐标为流 水段建立平面坐标系。对预取文件进行处理时，根据预取信息对预取文件进行本发明 的三步骤处理。

不同的阶段使用不同的进程进行处理，第一个预取文件mf₁顺次经预取阶段第一子计算阶段第二子计算阶段……、最后子计算阶段输出阶段 处理第一个预取文件mf₁的时间记为

第二个预取文件mf₂顺次经预取阶段第一子计算阶段第二子计算阶 段……、最后子计算阶段输出阶段处理第二个预取文件mf₂的 时间记为

第n个预取文件mf_n顺次经预取阶段第一子计算阶段第二子计算阶 段……、最后子计算阶段输出阶段处理第n个预取文件mf_n的 时间记为

在并行处理时，对文件的总处理时间记为T_并总（简称为并行总时间），

为了定量分析海量文件在串行处理与流水线并行处理中的加速效果，分别对 1000个、10000个、100000个文件进行处理，处理时间单位为秒。

加速检测条件：海量文件的处理平台为普通PC机，CPU为Intel i7-2600（四 核八线程），4G内存；操作系统为CentOS6.2。

表1不同文件数量的串行和并行处理时间

海量文件的加速比即为1.77、2.18、2.85。其结论用图表征为图3 和图4所示，当处理的文件数量越多时，并行执行时间的优势越明显。因此，对于 海量文件处理，本发明的基于流水线架构的海量文件指导型预取并行处理具有较高的 执行效率。

图5是采用多任务并行的处理方式，是将海量文件指导型预取并行处理的三个 步骤归结为一个处理组，这样就可以开启多个处理组同时对海量文件进行处理，加速 处理速度，提高对海量文件的处理时间。

在本发明中，一种基于流水线架构的海量文件指导型预取并行处理加速方法，各 个步骤的详细说明为：

步骤一：预取阶段

本发明使用的预取技术为指导型预取，需要应用程序显示的给出预取内容，例如 需要预取文件的路径名等信息。预取文件的数量可以为一个或者多个，使用专门的进 程或线程将上述的文件从海量文件外部存储系统预取到缓存区，缓存区为程序员于内 存中开辟的一块区域，大小由程序员决定。为了提升预取效率，流水线架构的预取的 文件为多个，具体的预取文件数量根据程序员开辟的缓存区大小确定。如图5所示， 预取用预取阶段中的带箭头的虚线表示，它根据文件列表，将其中的文件从海量文件 外部存储系统预取到缓存区，等待下一步的处理。

步骤二：处理阶段

在处理阶段，同样使用流水线架构进行处理，即把海量文件的处理分成多个子处 理过程，如图2、图5所示，处理阶段由子阶段1、子阶段2和子阶段3三个子处理 阶段组成，每个子处理过程将各自的处理结果交由下一个子处理过程进行处理。子处 理过程之间的处理，即子阶段1、子阶段2和子阶段3同样可以以流水线的形式并行 处理。在进行海量文件处理时，预取阶段不受影响，可继续依次从外部存储系统中预 取文件到缓存区。

1.单个进程或线程

对于计算量不大的海量文件处理，如图2所示，每个子阶段可以使用单个进程 或线程进行处理。

2.多个进程或线程

对于计算量较大的海量文件处理，如图5所示，每个子阶段可以使用多个进程 或线程进行处理。使用多个进程或线程进行处理，即保证了流水线的各个阶段的运算 速度，是流水线处理过程没有瓶颈。

步骤三：结果输出阶段

对经过数据处理阶段处理后的数据进行输出，得出最终结果。

基于以上三个的步骤，对于海量文件处理，如图5所示，可以采用多任务并行 的方式进行处理。即以上三个步骤可以归结为一个处理组，可以开启多个处理组同时 对海量文件进行处理。由此可以对海量文件进行更加快速的处理。

本发明的加速方法基于流水线架构，采用指导型预取对海量文件进行提前处理， 并且将海量文件的计算过程分为多个阶段，使其在多个阶段并行进行，提高了系统的 执行效率。在数据预取阶段，本发明采用了指导型预取，将海量文件的预取行为置于 应用程序的控制之下，使其更准确、更有预见性地进行预取，从而提高了海量文件预 取和处理的效率。