使用 r-Train 数据结构的矩阵乘法

0AASRI Procedia 5 (2013) 189 – 19302212-6716 © 2013 The Authors. Published by Elsevier B.V.under responsibility of American Applied Science Research Institute doi:10.1016/j.aasri.2013.10.0770ScienceDirect02013年AASRI并行与分布式计算系统会议0使用r-Train数据结构的矩阵乘法0Bashir Alam*0印度新德里Jamia Millia Islamia大学计算机工程系0摘要0最近在2011年提出了一种新的动态数据结构。有几种矩阵乘法算法，但没有一种算法使用r-Train数据结构来存储和相乘矩阵。本文提出了一种使用r-Train进行并行机器矩阵乘法的算法。© 2013 ElsevierB.V.出版。选择和/或同行评审由美国应用科学研究学会负责。关键词：R-Train，SIMD，并行算法01. 引言0在并行模型中，有几个处理元素同时执行单个指令。在MIMD模型中，多个指令在多个数据上执行。本研究使用的是SIMD模型。许多作者针对不同目的开发了许多有用的数据结构，具有不同的理念和要求。这里列举了一些重要的非线性数据结构。图是计算机科学中最普遍的数据结构之一。Sleator和Tarjan在[5,6]中引入了数据结构Splay Trees和DynamicTrees。哈希表是由H.P.Luhn引入的。非常有用的数据结构AVL树是由G.M.Velskii和Landis引入的[8]。B-树是由Bayer和McCreight引入的。Bayer发明了红黑树这种数据结构[11]。0*通讯作者。电话：+91-9810650497；电子邮件地址：babashiralam@gmail.com（Bashir Alam）0在线获取 www.sciencedirect.com0© 2013 The Authors. Published by Elsevier B.V.responsibility of American Applied Science Research Institute0根据CC BY-NC-ND许可进行开放访问。0根据CC BY-NC-ND许可进行开放访问。 0190 Bashir Alam / AASRI Procedia 5 (2013) 189 – 1930Seidel和Aragon提出了Treaps[7]。Treap是一种二叉搜索树，其中每个节点都有一个键和一个优先级：节点按键进行中序排序（与标准二叉搜索树相同），按优先级进行堆排序（使得每个父节点的优先级都比其子节点高）。二叉搜索树似乎是由许多人独立发现的[4]。Goodrich提出了一种名为TieredVectors的动态数组算法，用于在数组的中间进行有序插入或删除[9]。EdwardSitarski发明了一种名为哈希数组树（HAT）的动态数组算法[3]。动态数组是一种随机访问、可变大小的列表数据结构，允许添加或删除元素。动态数组与动态分配数组不同，动态分配数组是一个固定大小的数组，在分配数组时其大小是固定的，尽管动态数组可能使用这样的固定大小数组作为后端。最简单的动态数组是通过分配一个固定大小的数组，然后将其分为两部分来构建的：第一部分存储动态数组的元素，第二部分是保留的或未使用的。通过使用保留空间，我们可以在常量时间内向动态数组的末尾添加或删除元素，直到该空间完全消耗。动态数组内容使用的元素数量称为其逻辑大小或大小，而底层数组的大小称为动态数组的容量，即最大可能的逻辑大小。在逻辑大小有界的应用中，这种数据结构足够使用。调整底层数组的大小是一种昂贵的操作，通常涉及复制整个数组的内容。动态数组的性能类似于数组，但新增了在末尾添加和删除元素的操作。与链表相比，动态数组具有更快的索引（常数时间对比线性时间）和通常更快的迭代，这是由于改进的引用局部性。即使在高度碎片化的内存区域中，为大型动态数组找到连续的空间可能是昂贵的或不可能的，而链表不需要整个数据结构连续存储。有些工程情况需要比数组、链表、哈希表、二叉搜索树、字典等简单的基本数据结构更多的数据结构。在现今的巨大数据库中，许多情况下需要一种新的或更好的、更强大的基本数据结构的创造性构思。有些情况下，我们需要创建一种完全新的通用数据结构，并且创建这样一个新而简单的数据结构并不总是一项直接的任务。本研究的目标是引入一种新的、强大的动态数据结构，它结合了数组和链表的优点，并且同时继承了它们的一部分特点。通过“动态”这个词，我们指的是它随着时间的变化而变化，不像静态的。表面上看，这种新的数据结构似乎是混合链表和数组的，但是在构造上（由于其架构的特性），它更复杂。这种新的数据结构被称为“r-Train”。使用数据结构“r-Train”，可以存储大量的数据元素，并且可以非常容易地执行基本操作，如插入/删除/搜索，特别是在许多情况下，并行编程可以以改进的时间复杂度和性能轻松地完成。术语“train”（火车）是从常规的铁路运输系统中构造的，因为r-Train对象的性质与实际铁路的火车有很多相似之处；类似地，在我们的讨论方式中，我们使用了教练、乘客、座位的可用性等术语。r-Train的概念不是对链表概念的直接推广。它不仅仅是数组的链表，看起来是这样的，但是更多。然而，每个链表都是1-Train的示例（即r-Train，其中r =1）。引入数据结构“r-Train”的主要目的是如何以替代的方式存储一个大的数组。r-Train从数组的属性中继承了一个基本的缺点，即无法在两个现有的连续数据之间插入新数据，因为我们保留了每个数据的唯一索引，该索引在整个时间内保持不变。然而，r-Train数据结构在处理大量数据时明显优于数组和链表。R.Biswas提出的一种名为r-Train的新型数据结构既不是动态数组[9]，也不是HAT[3]。下面简要描述了它。 0191 Bashir Alam / AASRI Procedia 5 (2013) 189 – 1930r-Train（R型火车）基本上是由带有标记的车厢组成的链表。这个链表被称为r-Train的“引导器”。但是，在内存中实现这个引导器的方式有时也可以使用数据结构数组，这将在本文后面进行解释。r-Train的引导器通常是一个链表。但是，如果我们确信将来不会需要任何额外的车厢，那么最好将引导器实现为数组。关于这些操作的详细信息将在后续章节中进行解释。r-Train中的车厢数量被称为r-Train的“长度”，这个长度可能随时间增加或减少。如果没有混淆，也可以将r-Train称为“火车”。长度为l（>0）的r-Train将用以下标记表示0T   =   <  (C1, sC1),  (C2, sC2),  (C3, sC3),  ……,  (Cl, sCl) >,0其中教练 Ci 是(Ai,ei)，其中Ai是长度为r的数组，ei是教练Ci+1的地址（或者在Ci是最后一节教练的情况下是无效地址），sCi是教练Ci的状态，对于i=1,2,3,……,l。对于一个r-train，START是指针（将其在内存中实现为链表）指向的地址。因此，START指向内存中的数据C1。操纵杆的长度l可以是任何自然数，但是车厢的数组（TCs）的长度都是固定的r，它们存储具有公共数据类型的数据元素（包括元素）。因此，按名称，1-train、60-train、75-train、100-train等都是r-train的几个实例，其中术语0-train是未定义的。数据结构r-train的最重要特点是，即使在某个时间点上不能存储相同元素的大小为x的数组，它可能存储x个相同数据类型的元素。而且，可以使用索引很好地访问数据。在r-train中，教练名称C1、C2、C3、………，Cl也表示地址（指针），编号顺序与数组的情况类似，例如：数组z = (5, 9, 3,2)只需通过调用其名称z就可以轻松访问。教练的状态反映了座位的可用性（即是否可以将数据元素存储在此教练中）。状态可能随时间变化。r-train的每个教练可以容纳恰好r个按顺序编号的数据元素，每个数据元素称为乘客。因此，r-train的每个教练指向r个乘客的数组。根据定义，数据ei对于任何i都不是乘客。考虑一个教练Ci = (Ai,ei)。在数组Ai = 中，数据元素eij被称为“第j个乘客”或“第j个数据元素”，其中j = 1, 2, 3, 4, ...,r。因此，我们可以将r-train视为larrays的链表。从任何教练开始，可以访问所有下一个教练的内部，但不能访问任何前一个教练。r-train是一个向前线性对象，不是一种圆形对象。它既不是动态数组也不是HAT。它相对于HAT具有一个额外的优势，即从一个数据元素开始，可以很好地读取所有下一个数据元素，而无需参考任何哈希表或操纵杆。02. 使用r-Train数据结构表示矩阵0一个NXN矩阵A可以使用两种方式使用N-train表示：1.行主导的N-Train表示  2.列主导的N-Train表示 0192     Bashir Alam /  AASRI Procedia  5 ( 2013 )  189 – 1930在行主导的N-Train表示中，一个NXN矩阵A可以通过以下方式用N-train数据结构Xa表示。Xa =    其中 A 0 =               A 1 =                  A 2 =                           …………                           ...............0                  A n-1 =在列主导的N-Train表示中，一个NXN矩阵A可以通过以下方式用N-train数据结构Xa表示。  Xa=   其中 A0=                A 1 =                  A2=  ..  ..                A n-1 =  在这里，A 0 ，A 1 …………………A n-1  是教练，a 00 , a 10 , a 02 ,a 12…… 是教练的乘客，e 1  ,  e 2  ……e n-1  是教练A 1 ，A 2 ………………….A n-1 的地址。此外，A 0.0  , A 0.1………….A 0.n-1   表示a 00 ,  a 10 , a 20 ………a n-10  。03. 提出的矩阵乘法算法0以下是在具有M个处理器的并行系统上使用r-train数据结构进行矩阵乘法的提议算法。每个处理器都有一个唯一的ID用于识别。如果一个for循环之前有Par，则for循环的主体必须由所有处理器并行执行。A，B，C是三个NXN矩阵。该工作的目标是使用r-train数据结构计算C=AXB。提议的算法如下所示。  1.将矩阵A存储为行主导的N-train数据结构TA，如前一节所讨论的。  2.将矩阵B存储为列主导的N-train数据结构TB，如前一节所讨论的。  3. Par for(id=0;id

下载后可阅读完整内容，剩余1页未读，立即下载