© 2013由Elsevier B.V.发布。由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）189 - 1932013年AASRI并行和分布式计算系统使用r-Train数据结构的Bashir Alam*计算机工程系，Jamia Millia Islamia New Delhi，110025，India。摘要最近在2011年提出了一种新的动态数据结构。矩阵乘法有几种算法。但是没有一个使用r-train数据结构来存储和乘以矩阵。本文提出了一种基于r-train的并行机矩阵乘法算法。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：R-Train，SIMD，并行算法1. 介绍并行系统有几种模型[2]。在SIMD模型中，单个指令同时在多个处理元件上执行。在MIMD模型中，多个指令在多个数据上执行。在这项工作中使用的SIMD模型。有许多有用的数据结构由不同的作者开发，用于不同的目的，具有不同的哲学，用于不同类型的需求。这里列出了一些重要的非线性数据结构。图是计算机科学中普遍存在的数据结构之一。Sleator和Tarjan在[5，6]中介绍了数据结构Splay树和Dynamic树。哈希表是由H.P.Luhn引入的。AVL树是G.M. Velskii和Landis [8]。 B树是由Bayer和McCreight引入的[10]。拜耳发明了红黑树数据结构[11]。* 通讯作者。 联系电话：+91-9810650497;电子邮件地址：babashiralam@gmail.com（Bashir Alam）2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.077190Bashir Alam / AASRI Procedia 5（2013）189Seidel和Aragon提出了Treaps[7]。Treap是一种二叉搜索树，其中每个节点都有一个键和一个优先级：节点按键顺序排列（如标准二叉搜索树），并按优先级堆排序（因此每个父节点的优先级高于其子节点）。二叉搜索树似乎是由许多人独立发现的，正如Knuth在[4]中提到的那样。Goodrich [9]提出了一种称为分层向量的动态阵列算法，用于保持阵列中间插入或删除的顺序。哈希数组树（HAT）是由Edward Sitarski [3]发明的动态数组算法。动态数组是一种随机访问、大小可变的列表数据结构，允许添加或删除元素。动态数组与动态分配的数组不同，动态分配的数组是一个固定大小的数组，其大小在分配数组时是固定的，尽管动态数组可以使用这种固定大小的数组作为后端。最简单的动态数组是通过分配一个固定大小的数组，然后将其分为两部分来构造的：第一部分存储动态数组的元素，第二部分是保留的或未使用的。然后，我们可以通过使用保留空间在常量时间内添加或删除动态数组末尾的元素，直到该空间完全耗尽。动态数组内容使用的元素数是其逻辑大小或大小，而底层数组的大小称为动态数组的容量，这是最大可能的逻辑大小。在逻辑大小受限的应用程序中，这种数据结构就足够了。调整基础数组的大小是一项开销很大的操作，通常涉及复制数组的整个内容。动态数组的性能与数组类似，只是增加了从末尾添加和删除元素的新操作。与链表相比，动态数组具有更快的索引（常数时间与线性时间），并且由于改进了引用的局部性而通常具有更快的迭代。即使在高度碎片化的存储器区域中，为大型动态数组找到连续空间也可能是昂贵的或不可能的，而链表不需要连续存储整个数据结构有一些工程情况，需要比简单的基本数据结构，如数组，链表，哈希表，二叉搜索树，字典等，在当今的数据库的巨大规模，在许多情况下，需要一个新的或更好的装备/功能强大的基本数据结构的创造力。在某些情况下，我们需要创建一种全新的具有广义性质的数据结构，而创建这样一种新的但简单的数据结构并不总是一项简单的任务。这项研究工作的目的是引入一种新的和强大的动态数据结构，封装的优点的数组和链表，并在同一时间继承了减少量的特征缺点。我们所说的“动态”性质是指它随着时间的推移而变化，它不像静态的。显然，这种新的数据结构似乎是混合性质的，混合了链表和数组;但构造方面（凭借其体系结构），它更多。这种新的数据结构被称为“r-train”。使用数据结构'r-train'，可以存储大量的数据元素，并且可以非常容易地执行插入/删除/搜索等基本操作，特别是在许多情况下可以非常容易地进行并行编程，并具有改进的时间复杂度和性能。“火车”一词在这里是从通常的铁路运输系统中创造出来的，因为对象r-火车与实际的铁路火车在性质上有许多相似之处;类似地，我们在本书的讨论中使用了长途汽车、乘客、座位可用性等术语。r-trains的概念并不是链表的直接推广。它不只是数组的链表，因为它看起来是这样的，但更多的东西。然而，每个链表都是1-train的例子（即r = 1的r-train）。引入数据结构'r-train'的主要目的是如何以另一种方式存储大型数组。r-train的一个基本缺点是继承了数组的属性，不能在两个现有的连续数据之间插入新数据，因为我们保留了每个数据的唯一索引，这些索引始终保持不变。然而，在处理大量数据的情况下，数据结构r-train明显优于数据结构数组和链表。R. Biswas[1]既不是动态数组[9]，也不是HAT [3]。下面简要介绍Bashir Alam / AASRI Procedia 5（2013）189191r-train基本上是一个带标签的教练的链接列表。这个链表被称为r-train的“pilot”。但是，在某些情况下，也可以使用数据结构阵列来在存储器中实现该导频，这将在本文稍后进行解释。因此，火车的驾驶员通常是一个链表。但是，如果我们确定将来不需要任何额外的教练，那么最好将pilot实现为阵列。有关这些操作的详细信息将在后续章节中解释。 r型列车中的车厢数量称为r型列车的“长度”，它可能会随着时间的推移而增加或减少。 如果没有混淆的话，“r-火车”也可以被称为“火车”。长度为l（>0）的r列T将由以下符号表示：不 = <（C1，sC1），（C2，sC2），（C3，sC3），其中教练Ci是（Ai，ei），Ai是长度为r的数组，ei是下一个教练Ci+1的地址（或者在Ci是最后一个教练的情况下是无效地址），sCi是教练Ci的状态，i = 1，2，3，...，L.对于r-train，START是pilot的地址（将其在内存中的实现视为链表）。因此，START指向存储器中的数据C1。导频的长度l可以是任何自然数，但是TC的列各自具有固定长度r，其存储公共数据类型的数据元素（包括元素），其中r是自然数。因此，就名称而言，1-train、60-train、75-train、100-train等是r-train的少数实例，其中术语0-train未定义。数据结构r-train的概念是一种新的但非常简单的数据结构，一种2层数据结构，具有非常方便的执行各种基本操作的方法，如插入，删除，搜索等，对于大量的数据，特别是对于并行计算。数据结构r-train最重要的特征是，即使在某个时刻，一个大小为x的相同元素的数组不能存储在内存中，它也可能存储x个相同数据类型的元素。同时，通过索引可以很好地访问数据。在r列中，教练命名为C1、C2、C3、..，Cl也意味着像数组一样连续编号的地址（指针），例如：数组z =（5，9，3，2）可以通过调用其名称z轻松访问。车厢的状态反映了座位的可用性（即，数据元素现在是否可以存储在该车厢中）。状态可能随时间而变化。r-列车的每个车厢可以容纳正好r个连续编号的数据元素，每个数据元素被称为乘客。 因此，r列火车的每节车厢都指向一列r名乘客。根据定义，数据ei不是任何i的乘客。考虑教练Ci =（Ai，ei）。 在阵列Ai = ei1，ei2，ei3，....中，ei（r-1），eir>，数据元素eij被称为“第j个乘客”或“第j个数据元素”，其中j = 1，2，3，4，.，R.因此，我们可以把r- train看作是一个larray的链表. 从任何一节车厢开始，你可以参观所有下一节车厢的内部，但不能参观任何一节以前的车厢。r列车是一个向前的线性物体，而不是一种圆形物体。 它既不是动态数组，也不是HAT。与HAT相比，它还有一个额外的优点，即从一个数据元素开始，可以很好地读取所有下一个数据元素，而无需参考任何哈希表或导频。2. 使用r-Train数据结构NXN矩阵A可以使用两种方式1.行主N列表示2.列主N列表示192Bashir Alam / AASRI Procedia 5（2013）189在行优先N列表示中，NXN矩阵A可以由如下给出的N列数据结构Xa表示。Xa = A0，A1，其中A0 = a00，a01，a02........... a0 n-1，e1>A1 = a10，a11，a12.............. a1n-1>A2 = a20，a21，…………...............An-1 = an-10，an-11，这里A0，A1e2在列主N-Train表示中，NXN矩阵A可以由如下给出的N-Train数据结构Xa表示。Xa= A0，A1，其中A0= a00，a10，a20............ an-10，e1>A1 = a01，a11，a21.............. an-11>A2= a02，a12，....An-1 = a0n-1，a1n-1，这里A0、A1..此外，A0.0、A0.1..3. 提出的矩阵乘法算法这里提出的算法矩阵乘法使用r-火车数据结构的并行系统上有M个处理器。每个处理器都有一个唯一的ID用于识别。如果一个for循环的前面是Par，那么for循环的主体必须由所有处理器并行执行。A、B、C是三个NXN矩阵。本工作的目的是使用r-train数据结构计算C=AXB。建议的算法如下所示。1.将矩阵A存储为行优先的N列数据结构TA，如前一节所述。2.将矩阵B存储为列优先的N串数据结构TB，如前一节所述。3.Par for（id=0;id M;id++）{4.读取TAidmodN5.读取TB下限（id/N）6.return 0;7.对于（i=0;i N;i++）8.temp=temp+ TAid mod N .i* TB floor（id/N）.i9.C id/N.id mod N =temp}Bashir Alam / AASRI Procedia 5（2013）189193乘积任意两个N × N阶矩阵都可以通过该算法得到，验证是显而易见的。算法的复杂性分析如下。这是一个O（N）时间复杂度的问题。步骤3，4，5，6，8，9可以在O（1）时间内完成。由于步骤7的循环，步骤8重复O（N）次。应用计算复杂性的和积法则，当M=N2时，算法的复杂性为O（N）.4. 结论本文给出了一种新的N-序列数据结构的矩阵存储方案和一种新的N × N矩阵乘算法，并计算了它们的计算复杂度。引用[1]r-Train（TRAIN）：一种新的灵活的动态数据结构。INFORMATION：An InternationalJournal（Japan）2011;14（4）：1231-1246.[2]放大图片作者：Kai Hwang，Faye A.布里格斯计算机体系结构和并行处理。国际版。MCGraw Hill 1985; 32-49.[3]西塔斯基，爱德华算法巷. HATS：哈希数组树。Dr. Dobb's Journal 1996; 21（11）. http：//www. ddj.com/architect/184409965? pgno=5[4]Donald E.高德纳计算机程序设计的艺术。Addison Wesley 1968; E- I，II，III. [5]D.D.Sleator和R.E. Tarjan.动态树的数据结构.计算机系统科学杂志1983;26（3）：362-391.[6]D.D.Sleator和R.E.Tarjan。自调整二叉搜索树。Journal of the ACM 1985;32（3）：652-686.[7]R.Seidel和C.R. Aragon.随机搜索树。《自然》1996;16：464-497。[8]第八届中国国际纺织品展览会Landis.一种组织信息的算法。Soviet Mathematics Doklady 1962;3：1259-1263.[9]Goodrich，Michael T.;作者声明：John G.（）.分层向量：基于秩序列的高效动态数组。算法和数据结构研讨会1999;1663：205[10]R.Bayer和E.M. McCreight。大型有序索引的组织和维护.Acta Informatica 1972;1（3）：173-189.[11]R.Bayer，对称二进制B树。数据结构和维护算法。Acta Informatica 1972;1：290-306。
我的内容管理
展开
