HPPHM多维数据并行IO存储新策略及其性能研究.doc

第4期陈志刚等：HPPHM：多维数据并行I/O存储新策略及其性能研究63HPPHM：多维数据并行I/O存储新策略及其性能研究陈志刚1，曾碧卿2(1. 中南大学 信息科学与工程学院，湖南 长沙 410083；2. 华南师范大学 南海校区计算机系，广东 佛山 528225)摘 要：针对大型多维数据集合中数据存储访问效率较低的缺陷而进行了相应的研究，通过采用并行I/O技术，将多维数据在分布式系统的多个磁盘之间进行分布存储，通过循环拆分法将已有的数据从适用于二维数据扩展到了多维数据中，并通过对循环法进行理论分析，对多维数据存储访问进行研究，提出了一种新的启发式多维数据循环策略，即基于访问步长值Hi与访问长度M互质的启发式策略(HPPHM)，实验表明了新算法在并行度和顽健性等性能方面都具有优越性。关键词：多维数据；并行I/O；存储访问中图分类号：TP338.8 文献标识码：A 文章编号：1000-436X(2007)04-0057-08HPPHM：new policy of store for multidimensional dataset of parallel I/O and research of retrieve performanceCHEN Zhi-gang1, ZENG Bi-qing2(1. College of Information Science and Engineering, Central South University, Changsha 410083, China;2. Department of Computer Engineering, Nanhai Campus, South China Normal University, Foshan 528225, China)Abstract: The policy of store and retrieve for large-scale multidimensional dataset was researched. The multidimensional dataset was allocated in the multi-disks among the distributed processing system by using the parallel I/O technology. A new multidimensional data cyclic declustering policy was proposed aiming to data retrieve based on scope by extending existing cyclic policy to multidimensional dataset from adapting to two-dimension, and by using theory analysis on the present method, a new heuristic multidimensional data retrieve policy named HPPHM was proposed. The experimental result has demonstrated the efficiency of new strategy not only in parallel degree but also in robust.Key words: multidimensional dataset； parallel I/O; store and retrieve1 引言收稿日期：2006-04-30；修回日期：2007-01-22基金项目：国家自然科学基金资助项目(60573127) Foundation Item: The National Natural Science Foundation of China (60573127)在科学研究和工程设计中有时需要处理大型多维数据集合，如气候模型、物理或化学现象、地震资料以及卫星遥感数据的分析等1,2。推而广之，关系数据库中的表也包括有若干个属性，其中的每一个属性都可以看成是多维数据中的一维3。对多维数据进行处理、分析的应用程序有时候需要根据多维数据中值的范围来对目标数据进行有效访问，因此需要进行多维数据分布存储策略与访问的研究。在大型多维数据集合的所有数据元素中进行数据访问，以得到满足要求的数据对象，其效率是很低的4，因为磁盘由于其本身的机械特性而具有很高的延迟，使得数据访问的性能极大地依赖于磁盘I/O，在随机I/O磁盘访问中，时间开销很大一部分是由于磁头寻道和盘片旋转延迟所引起的，因此，使用并行I/O技术，通过在多个磁盘间以并行方式进行I/O是克服这一缺陷的有效方法5。多维数据中的并行I/O就是将多维数据分割成若干个子数据块，将处于同一个子数据块中的数据对象存储在一起，并将所有的子数据块分布存储于多个磁盘上。当进行数据访问时，只需要以并行I/O方式访问一定数量的磁盘及相关的子数据块，就能够得到所需的数据对象，这样进行访问时，既能够实现并行处理，又能够降低I/O执行的总数据量，从而极大地减少由I/O操作所造成的总延时，提高了数据访问和并行I/O的效率。对数据分布存储问题的研究实质上是对在给定磁盘数量的前提下实现磁盘访问和I/O并行处理优化问题的研究。在高性能计算技术中，多维数据的分布存储一直是一个重要的研究课题，对分发多维数据中的多维子数据块以优化基于范围访问的性能等方面的问题在文献612中已开展了较好的研究。K.A.S. Abdel-Ghaffar等在文献6中提出了如何优化数据文件在磁盘上的分配、从而对分布存储于磁盘中的数据文件进行局部匹配访问的策略，证明了文件达到严格最优分配的必要条件和充分条件，并基于最大距离可分代码理论对文件在磁盘上的最优化分配进行了分析。同时，在文献7中K. A. S. Abdel-Ghaffar等还对二维数据在并行磁盘上的最佳分配进行了深入的研究，他认为通过将一个二维数据分割为许多小的矩形数据块，并分布存储于不同的磁盘上，这对于提高大范围内信息浏览和检索的并行性是非常有益的。当用户需要进行数据查询时，系统可以让用户指定潜在的数据查询区域，从而在众多存储小数据块的磁盘中找到所有的相关信息。对于任意的二维数据查询而言，文献7中的理论和方法能够保证分配到同一个磁盘中的数据块的数量达到最小，从而确保系统中最大数据访问的并行性。S.Prabhakar等在文献12中对于二维数据的循环分配开展了较好的研究。虽然在拆分二维数据，并将数据块分配存储于多个I/O设备方面已经有了不少的方法，但是严格意义上的最优解决方案仅存在于对二维数据的分割存储中，或者仅存在于很少的I/O设备上，而且它们的限制性条件也非常多。S. Prabhakar等提出了一种称之为文件循环分配的方法，这种方法实际上是许多已有文件分配方法的框架，而现有的一些文件分配方法也是它的应用实例，因此，循环分配方法为其他看似特别或者似不相关的文件分配方法提供了一个统一的框架，这个框架还可用于开发和研究新的性能更好、更灵活的方法。文献612中研究的目的都是要达到最大并行性，对任何分布在多个磁盘间的若干个数据块集合进行数据访问时，均认为其访问成本是数据块完全在单独一个磁盘上时的一部分，总体的访问效率不高。本文研究提出了一个启发式的多维数据拆分循环分配与访问策略(HPPHM, a heuristic policy of prime number between step value Hi and finding length M)，该策略是在二维数据循环分配策略的基础上发展而来的，二维数据循环分配方案与其他策略相比已经取得了较大性能的提高12。在二维数据的循环分配中，主要是通过穷尽搜索数据空间来获得较好的性能，但是随着数据量和数据维数的增加，这种穷尽搜索法已很不现实而且显得没有必要。在实际的一次数据访问操作中，只需要对存储的数据在若干个相关的子数据块中进行访问，一般都能够得到所需要的数据，这也是HPPHM策略的主要思想。2 多维数据分配存储现状与HPPHM策略的提出2.1 多维数据分配存储现状研究为了提高并行应用程序对分布存储多维数据的管理能力，改善数据并行访问性能，并行I/O技术在文献1315中得到了较好的研究，它是利用类HPF(high performance fortran)的块或循环方式在多个处理器中分割数据文件，对某个处理器而言，数据可能是本地的，也可能是在所有的处理器间进行全局存取的，性能的提高主要是通过集中I/O、预取及筛选等措施来实现的。但是在文献13,14的研究中，向节点磁盘中分配存储多维数据没有得到有效的研究。对关系数据库形式的多维数据而言，已经有多种成熟的数据分配技术，如磁盘模数法(DM)9、域方式扩充法(FX)11、Gray代码法16以及Hilbert法(HCAM)10等。其他的数据分配策略还有基于纠错码的2种方法，它们分别是字符串分组纠错码17和最大距离可分代码纠错码6，适用于二维数据的2种方法分别是FIB网格法8和循环法12，文献18中研究了适用于二维数据范围访问的循环分配方法。现简单介绍一下在上述的一部分方法中，实现将数据块分发到磁盘中的数据分配策略，几个参数的含义如下：Ni：表示在多维数据中维i上子数据块的数量，如果多维数据中每一维上的子数据块数量相同，那么就用N来代表该数量；d：多维数据中的维数；d维空间中的每一个数据块X，用一组坐标值(x0, x1, xd-1)来确定，由于维j被分为Nj个子数据块，因此每一个坐标xj都在范围0,Nj-1中；M：磁盘数量，即多维数据拆分成子数据块后，接受数据分配的磁盘数量。对多维数据中数据块的一次分配，实质上就是一次映射，它提取子数据块X，并将它映射到范围为0，M-1的一个数值上。访问分配到M个磁盘上的A个数据块时，其最小成本由来确定，对所有数据访问都能够达到最小成本的数据分布存储一定要经过优化处理。DM法是按以下方法来进行数据分发映射的：(1)FX法是按以下方法来进行定义的：(2)其中，bj代表xj的二进制，而代表的是按它的位逻辑运算符“OR”进行操作。HCAM法定义为 (3)其中，函数hilbert_order()是根据输入的坐标值返回在hilbert序列中的条目。hilbert过程能够将一个多维的空间映射为一个线性的顺序。文献12中的循环分配法只定义了二维数据的分配，它将数据块(x0,x1)按以下方式分配到磁盘上，即 (4)在这里，可以通过控制对H值的选择来获得更好的数据拆分与分配效果。H值可以在1到M-1之间变化，对不同的H值，将会得到不同的数据循环分配方案，DM数据分配法实质上是一个H=1的循环方案，H称之为步长值，它是一个决定循环方案性能的关键因素。然而，对一个合适H值的选择依赖于M值。文献12中描述了选择合适H值的方法，其核心思想是H值应该与M值互质，并且H1。以上方法主要是应用在基于范围访问的二维数据中，文献12对它们的相对性能进行了研究，同时对上述方案进行了一些比较，对由每一个方案相对于边界值下界所获得的数据拆分的有效性进行了评估。2.2 HPPHM循环分配策略的提出为了给二维以上的多维数据设计出有效的数据拆分循环分配策略，本研究主要是对二维数据的循环分配法进行了推广，使之能适用于多维数据，由二维数据扩展到多维数据的形式化描述如下 (5)式(5)是HPPHM策略的主要表现形式，实现该策略的关键是要为步长Hi找到一个合适的值，从而形成不同的循环策略，也使得多维数据的循环分配策略能够获得更好的数据拆分效果。3 HPPHM策略的相关理论分析首先研究循环分配策略中的一些性质，定义2个术语。定义1 访问范围：多维数据中每一维的范围值集合，即其中，。定义2 访问集合：满足访问要求的数据块的集合，如：(x0,x1,xd-1)|qlixiqui,i,0id。3.1 基本定理现在证明：对大小相同而位置独立的所有数据访问来说，由循环分配法所产生的数据分配都会有固定的访问成本。引理1 重命名磁盘对访问成本不会产生影响。证明 由于数据块的分配不会因为重命名而改变(因为仅仅是磁盘标识符发生了变化)，分配得到最多子数据块数量的磁盘会发生改变，但是数据块的总数量并没有变化。特别地，对某常量D来说，如果有，则分配映射和是等价的。定理1 对任何数据的循环分配策略，访问成本(ql0,qu0,ql(d-1),qu(d-1)仅依赖于(qui-qli+1)的值，0id, 而与其实际的坐标无关，换句话说，访问开销依赖于数据空间的形状而不是它的位置。证明 一个待访问的数据对象是由它所在多维数组的起点坐标位置和这个数组中每一维上具有等同于访问长度的边所组成的立体图形来定义的，即是由数据对象的位置和形状来定义的。对一个待访问的对象而言，起点坐标位置是由(ql0,ql1,ql(d-1)给出的，形状是由(qu0-ql0+1)，(qu1-ql1+1),(qu(d-1)-ql(d-1)+1)来确定的，考虑到待访问的数据块相对于起点坐标是定位在(y0,y1,yd-1)。这个子数据块的坐标就是(ql0+y0, ql1+y1, ql(d-1)+yd-1)。这个子数据块是通过以下的计算方式分配到某一个指定磁盘上的，即(ql0+y0)+(ql1+y1) H1+(ql(d-1)+yd-1) Hd-1) mod M=(A+y0+yd-1Hd-1) mod M其中，A=ql0+ql1H1+ql(d-1)Hd-1，A是访问的起始位置，因此对不同的访问位置，A的值不同。也就是说，对不同的访问位置，分配是一样的，除非磁盘更名，因此，按照引理1，不同位置的开销是一样的。证毕。在数据访问中，成本开销仅依赖于多维数据的形状，因此需要考虑(0,q0,0,q1,0,qd-1)，该表达式可以简写为(q0,q1,qd-1)，它是可以用于表示数据访问的表达式，因此定义函数Qcost(q0, q1,qd-1)作为访问(q0,q1,qd-1)的成本。3.2 数据访问成本分析现在研究当使用循环分配策略时，一条访问所需要的成本。先从二维数据开始，对于给定的任意循环分配，不失一般性，通过常量值的改变，根据引理1，能对磁盘进行重命名，以使得访问中的顶-左角数据块能分配到磁盘0上。研究中发现在分配二维数据(q0,q1)的一行时，分配到一个磁盘中的数据块要么是，要么是。如果数组行的第一个数据块分配到磁盘i中，那么从磁盘i开始的连续q0 mod M个磁盘会分配到个数据块，而其余磁盘上分配有个数据块。这种情况是沿着数组中的一行将子数据块分配到连续磁盘中的结果。定理2 访问二维数据(q0,q1)的成本等于加上访问(q0 mod M, q1)的成本，也就是 (6)证明 由于在数组的每一行中，数据的分配是连续进行的，一行中任意M个连续的数据块都分别分配到不同的磁盘上，因此在每一行中，开始的个列同样地分配到所有的磁盘上，结果是每个磁盘上分配到了个数据。对于完全访问来说，前面的个列同样分配到所有的磁盘上，导致每一个磁盘上分配到了个数据块。访问成本是由分配到一个磁盘上的最大数量的数据块来决定的，这是由加上在访问(q0 mod M, q1)时分配到一个磁盘上的最大数据块决定的。定理3 如果所有的步长值H0，H1，Hd-1都与M互质，也就是说gcd(Hi，M)=1，0id，那么任何访问(q0,q1,qd-1)的成本都可以用以下式子来确定，即 (7)证明 因为所有的步长值均与M是互质的，所以在多维数据的每一维上，所有的磁盘都得到了利用。此外，对每一维中任何连续M个数据块来说，每一个数据块都会分配到不同的磁盘上，即对于每一维中任何M个连续的数据块，磁盘得到了同样的利用，因此，定理2的参数能够依次应用到每一维上，这样访问(q0,q1,qd-1)的成本都可以由如下式子来给定，即 证毕。因此，数据访问(q0,q1,qd-1)的成本是由更小的数据访问(q0 mod M, q1 mod M,qd-1 mod M)的成本来确定的。如果在任意一维上的访问长度是M的倍数，根据定理3，那么具有互质数步长值的循环分配是最优的。4 HPPHM策略中步长值Hi的确定从上述讨论中可以看到访问成本在很大程度上是依赖于步长值Hi，Hi和M最大公约数的值是一个重要的访问成本影响因素，Hi与M互质会优化访问性能。在研究中根据所选取的步长值Hi的不同，本研究中设计了一个基于访问步长值Hi与访问长度M互质的启发式策略，即HPPHM策略。HPPHM策略的主要基础是FIB法，FIB是一种为二维数据定义、用来将二维数据映射存储到内存中的方法8，它要求M是一个奇数顺序的斐波那契数，即M=F2r+1(r0)。文献12对FIB法进行了扩展，使之能适用于一般的M值。本研究又将FIB法进行了进一步的推广，使它能够适用于多维数据，得到了HPPHM策略，它是一种对多维数据进行循环分配的策略。斐波那契序列可以看作是从一个非负整数值(索引)到另一个非负整数值的映射，如：00，11，32，。索引与斐波那契数之间的关系可以由式来确定，其中,是黄金分割率，值为，=，使用这个关系时，允许索引取非整数值。HPPHM策略的步长值选择方法如下：对给定的M，确定K值，使得Fk=M(这里k可能是非整数值)，步长值按照H1，H2，的顺序选取，在Hi处选择Hi=Fk-i作为其首选的可能值，如果Hi与M互质，则就可以为Hi选定了该值，否则继续搜索相邻的Hi，直至找到一个与M互质的值。如果所选定的符合要求的步长值已经使用过了，就要选择下一个符合要求而且还没有被使用过的值。5 实验及结果分析实验中对HPPHM多维数据循环分配策略与以前的域方式扩充法FX，磁盘模数法DM及HCAM等策略进行了比较，由于数据访问具有随机性，性能评估和比较是基于一系列随机相关数据访问而进行的。为了使实验结果具有可信度，实验中使用了4种不同的随机数据访问集合，其中每个数据集合中有1 000个数据访问请求，根据它们所获得的最优并行处理能力，对不同的策略进行了比较、分析。对各种策略而言，访问成本是由从同一个磁盘中访问到的最大数量的子数据块来决定的，因此，成本下界可以由来确定，其中，A是一次访问完成后所能够找到的数据块数量。实验中，数据访问成本由数据访问的实际成本与成本下界的比值来确定，实际成本是当时所有磁盘上查询成本的平均值。当平均比值为1时，表明该策略对每一个数据访问都达到了下界，数据访问的性能优越，平均比值越高，则表明并行处理能力越低。实验中由于高维数据所产生的数据块一般都较大，因此，随着数据维数的增加，在每一维中的数据块减少了。下面分别针对多维数组的不同维数、每一维上具有不同的数据块数量以及不同的数据规模来进行实验。研究中的实验环境是由16台联想启天4000微机构成的100MB分布式集群计算系统，系统中的每一个节点上仅配置1个硬盘，即系统中的磁盘数量与节点数量相同，实验环境的软、硬件配置相同，均为赛扬1.4GHz/256MB/40GB/Linux/MPI。1) 实验1保持多维数据的维数及每一维上的数据块数量不变，而使磁盘数(即系统中的节点数)发生改变，实验中的参数如下：d=8，N=4，M=2,16，即多维数据的维数为8，每一维中的子数据块数量相同，均为4，磁盘数量(即系统中的I/O节点数量)则从2至16个变化。如图1所示为集群系统中磁盘数量与数据访问成本比之间的关系，实验曲线反映了FX、DM、HCAM及HPPHM相互之间的性能比较。经对实验结果的分析，可以得出以下结论： 对4种策略而言，磁盘访问所增加的成本HPPHM最小，该方法最优，而FX最大，DM、HCAM则居中。具体来说，在磁盘数较少时，FX、DM与HCAM策略得到的性能相差不大，但是当磁盘数增加时，HCAM比DM和FX的性能都要好。另外，在图1中，由实验所得到的HCAM曲线出现了较大的抖动和畸变，这是由于Hilbert过程在将多维空间映射为线性顺序时，算法过于近似所造成的。图1 d=8，N=4，M=2, 16时，FX、DM、HCAM及HPPHM策略的性能比较 随着磁盘数的增加，FX和DM的性能呈现出明显的规律性下降，并且FX的性能比DM要差一些，与具有16个磁盘时的成本下界比较起来，在八维数据中DM需要增加224%的磁盘访问，而FX需要增加232%的磁盘访问。 HPPHM与FX之间数据访问成本相差185%，这也说明了HPPHM的有效性。HPPHM性能优越主要是由其循环文件分配策略的本质特征决定的。2) 实验2在实验1中，多维数据的每一维中数据块数量相同，均为4，即N=4，实验2是在多维数据的不同维有不同数据块的条件下进行的，在该实验中，d=8，每一维上数据块的数量分别是N0=N1=16，N2=N3=8，N4=N5=5以及N6=N7=2，M=2,16。实验结果如图2所示，它是八维数据中HCAM、DM、FX和HPPHM策略相互之间的性能比较曲线。实验结果表明：图2 d=8，M=2,16，维i数据块不同时，FX、DM、HCAM及HPPHM策略的性能比较 由于各维上数据块的划分不同，HCAM的性能明显下降了，当磁盘数是16时，磁盘访问增加率几乎达到成本下界的920%，说明HCAM法对于每一维上的数据块数量Ni的变化非常敏感。另外，由于HCAM策略访问的高成本掩盖了其数据的抖动和畸变，所以在实验曲线上体现得不够明显； DM、FX及HPPHM 3种策略的性能几乎没有变化，特别是HPPHM策略获得了很好的性能，这说明多维数据循环分配策略HPPHM并不因为系统中磁盘数的改变、数据维序或每一维上数据块数量的变化而产生性能方面的明显变化。3) 实验3与实验1、2相比，改变多维数据的维数和每一维上数据块的数量，并使磁盘数发生改变，实验中的参数如下：d=12，N=6，M=2,16，即多维数据的维数为12，每一维中的子数据块数量均为6，磁盘数量从2至16个进行变化。如图3所示为集群系统中磁盘数量与数据访问成本比之间的关系，实验曲线反映了FX、DM、HCAM及HPPHM相互之间的性能比较。图3 d=12，N=6，M=2,16时，FX、DM、HCAM及HPPHM策略的性能比较实验结果表明：对4种策略来说，磁盘访问所增加的成本HPPHM最小，该方法最优，而在磁盘数较小时，DM最大，当磁盘增加到一定数量时，FX较DM大，HCAM居中。4) 实验4在本实验中，设定d=8，M=16，选取5个八维数组，每个八维数组的每一维上数据块的数量分别是4，5，6，7，8，即：N=4, 8来进行实验，以试验不同的子数据数量对FX、DM、HCAM和HPPHM策略的影响。实验结果如图4所示，实验结果表明：随着不同多维数据上子数据块的增加，4种策略的访问成本都呈现出明显的增加。但是HPPHM策略最优，而FX、DM、HCAM的访问成本均高于HPPHM策略。图4 d=8，N=4, 8，M=16时，FX、DM、HCAM及HPPHM策略的性能比较5) 实验5在本实验中，设定d=10，N=8，M=16，多维数据的数据规模从1GB到3GB变化来进行实验，以试验不同的数据规模对FX、DM、HCAM和HPPHM策略的影响，实验结果如图5所示。图5 d=10，N=8，M=16，数据规模在1GB,3GB时，FX、DM、HCAM及HPPHM策略的性能比较实验结果表明：随着多维数据规模的增加，数据访问的成本变得非常高。HPPHM策略最优，HCAM次之，而对于FX和DM来说，在数据规模较小时，DM较优，而在数据规模较大时，FX比DM访问成本要低些。通过对多维数据的不同维数、不同数量的子数据块以及不同规模数据集合的实验，其结果都表明了HPPHM策略的有效性。6 结束语对科学研究与工程设计中的并行应用程序来说，在多维数据中使用基于范围的策略进行访问是非常重要的技术。对大型多维数据而言，数据访问的性能受限于I/O瓶颈，为提高系统的I/O能力，在多个磁盘之间进行并行I/O是一种有效的方法。为了将多维数据块拆分到多个并行磁盘上，以提供较强的并行I/O能力，同时针对基于范围的数据访问，本研究中提出了有效的数据访问策略HPPHM，并证明了循环分配法的一些性质。HPPHM策略促进了多维数据访问性能的提高，同时它对磁盘数量、数据的维数以及不同维上数据块数量的变化均没有表现出明显的敏感性。参考文献：1ISAILA F, TICHY W F. Clusterfile: a flexible physical layout parallel file system.A Concurrency Computat: Pract. ExperC. 2003, 653-679.2SUN J H, JIN H, CHEN H, et al. Server scheduling scheme for asynchronous cluster video serverA. Proceedings of the 17th International Conference on Advanced Information Networking and ApplicationsC. Xian, China, 2003. 509-512.3SHEN X H, LIAO W K, ALOK C, et al. A high-performance application data environment for large-scale scientific computationsJ. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(12): 1262-1274.4BAJAJ R, AGRAWAL D P. Improving scheduling of tasks in a heterogeneous environmentJ. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(2): 107-118.5YANG C T, CHENG K W, LI K C. An enhanced parallel loop self-scheduling scheme for cluster environmentsA. Proceedings of the 19th International Conference on Advanced Information Networking and Applications (AINA05)C. 2005. 207-210.6ABDEL-GHAFFAR K A S, ABBADI A E. Optimal disk allocation for partial match queriesJ. Proc ACM Symp on Transactions of Database Systems. 1993,18(1):132-156.7ABDEL-GHAFFAR K A S, ABBADI A E. Optimal allocation of two-dimensional data.A. Int Conf on Database Theory C.Delphi, Greece, 1997.409-418.8CHOR B, LEISERSON C E, RIVEST R L, et al. An application of number theory to the organization of raster-graphics memoryJ. Journal of the Association for Computing Machinery, 1986, 33(1):86-104. 9DU H C, SOBOLEWSKI J S. Disk allocation for Cartesian product files on multiple-disk systemsJ. ACM Transactions of Database Systems, 1982, 7(1): 82-101.10FALOUTSOS C, BHAGWAT P. Declustering using fractalsA. Proc of the 2nd Int Conf on Parallel and Distributed Information SystemsC. San Diego, CA, 1993.18-25.11KIM, M H PRAMANIK S. Optimal file distribution for partial match retrievalA. Proc ACM SIGMOD Int Conf on Management of DataC. Chicago, 1988. 173-182.12PRABHAKAR S, ABDEL-GHAFFAR K, AGRAWAL D, et al. Cyclic allocation of two-dimensional dataA. Proc of the International Conference on Data EngineeringC. Orlando, Florida, 1998. 94-101. 13SEAMONS K E, WINSLETT M. Multidimensional array I/O in panda 1.0J. Journal of Supercomputing, 1996, 10(2): 191-211. 14THAKUR R, CHOUDHARY A, BORDAWEKAR R, et al. PASSION optimized I/O for parallel applicationsJ. IEEE Computer, 29(6): 70-78. 15ALI S, MACIEJEWSKI A A, SIEGEL H J, et al. Measuring the robustness of a resource allocationJ. IEEE Transactions on Parallel and Distributed Systems. 2004, 15(7): 630-641.16GRAY J, HORST B, WALKER M. Parity striping of disc arrays: low-cost reliable storage with acceptable throughputA. Proceedings of the Int Conf on Very Large DataBasesC. Washington DC, 1990. 148-161.17FALOUTSOS C, METAXAS D. Dec