Method and Improvement of Maximum Search Based on PRAM Parallel Model
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [24]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    With the emergence of multiprocessors, parallel technology has attracted widespread attention and become an important technology to speed up the processing of problems. Nevertheless, the use of parallel technology to speed up computing has also led to a sharp increase in the number of processors and a significant increase in parallel costs. To solve this problem, by studying the shortcomings of three parallel maximum search algorithms based on PRAM (Parallel Random Access Machine), a parallel maximum search algorithm based on data partitioning method is proposed, which is better than the balanced tree algorithm, fast search method and double logarithmic depth tree method. The maximum searching algorithm based on data partitioning method effectively solves the problems of uneven workload allocation, excessive demand for processors and harsh implementation conditions in existing parallel methods. This provides a direction for similar parallel algorithms to reduce parallel costs.

    Reference
    [1] 王青云,罗泽.基于LOD的海量地形数据并行渲染技术.计算机系统应用, 2017, 26(12):200-206.[doi:10.15888/j.cnki.csa.006113
    [2] 李晓梅.并行算法的发展及其前沿研究课题.中国科学基金, 1995,(3):13-18
    [3] 严蔚敏,李冬梅,吴伟民.数据结构(C语言版).计算机教育, 2012,(12):62
    [4] 罗贵章,陈忠伟.并行算法综述.计算机光盘软件与应用, 2013,(15):51-52
    [5] 陈国良,孙广中,徐云,等.并行算法研究方法学.计算机学报, 2008, 31(9):1493-1502.[doi:10.3321/j.issn:0254-4164.2008.09.002
    [6] Shiloach Y, Vishkin U. Finding the maximum, merging, and sorting in a parallel computation model. Journal of Algorithms, 1981, 2(1):88-102.[doi:10.1016/0196-6774(81)90010-9
    [7] 胡峰,胡保生.并行计算技术与并行算法综述.电脑与信息技术, 1999,(5):47-59
    [8] Acharya HB. Parallel processing of packets with a PRAM. Proceedings of the 19th International Conference on Distributed Computing and Networking. Varanasi, India. 2018. 45.
    [9] Forsell M, Leppänen V. An extended PRAM-NUMA model of computation for TCF programming. Proceedings of the IEEE 26th International Parallel and Distributed Processing Symposium Workshops&Phd Forum. Shanghai, China. 2012. 786-793.
    [10] 明玉瑞,李思泽.基于SIMD机制的并行排序算法.计算机系统应用, 2009, 18(11):87-90.[doi:10.3969/j.issn.1003-3254.2009.11.022
    [11] 赵军,张东梅.平衡二叉树.电脑学习, 2007,(2):33-34.[doi:10.3969/j.issn.2095-2163.2007.02.018
    [12] 陈海涛,李宗惠.平衡二叉树的失衡调整方法探讨.中国科教创新导刊, 2010,(34):146, 148
    [13] Ha PH, Anshus OJ, Umar I. Efficient concurrent search trees using portable fine-grained locality. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(7):1580-1595.[doi:10.1109/TPDS.71
    [14] 陈国良.并行算法的设计与分析. 3版.北京:高等教育出版社, 2009. 63-64, 78-80.
    [15] Huang D, Han DZ, Wang J, et al. Achieving load balance for parallel data access on distributed file systems. IEEE Transactions on Computers, 2018, 67(3):388-402.[doi:10.1109/TC.2017.2749229
    [16] Jackson A, Campobasso MS, Drofelnik J. Load balance and parallel I/O:Optimising COSA for large simulations. Computers&Fluids, 2018, 173:206-215
    [17] Berkman O, Matias Y, Vishkin U. Randomized range-maxima in nearly-constant parallel time. Computational Complexity, 1992, 2(4):350-373.[doi:10.1007/BF01200429
    [18] Olariu S, Overstreet M, Wen ZF. Reconstructing a binary tree from its traversals in doubly logarithmic CREW time. Journal of Parallel and Distributed Computing, 1995, 27(1):100-105.[doi:10.1006/jpdc.1995.1075
    [19] Pan Y, Hamdi M. Quicksort on a linear array with a reconfigurable pipelined bus system. Proceedings of the 2nd International Symposium on Parallel Architectures, Algorithms, and Networks. Beijing, China. 1996. 313-319.
    [20] Pavel S, Akl SG. Efficient algorithms for the hough transform on arrays with reconfigurable optical buses. Proceedings of 1996 International Conference on Parallel Processing. Honolulu, Hawaii, USA. 1996. 697-701.
    [21] 李庆华,蒋廷耀.基于LARPBS模型的最大值查找算法.计算机科学, 2004, 31(3):183-185.[doi:10.3969/j.issn.1002-137X.2004.03.052
    [22] 陈旭,孟朝晖.基于深度学习的目标视频跟踪算法综述.计算机系统应用, 2019, 28(1):1-9.[doi:10.15888/j.cnki.csa.006720
    [23] 梁娟娟,任开新,郭利财,等. GPU上的矩阵乘法的设计与实现.计算机系统应用, 2011, 20(1):178-181, 149.[doi:10.3969/j.issn.1003-3254.2011.01.038
    [24] Campos V, Sastre F, Yagües M, et al. Scaling a convolutional neural network for classification of adjective noun pairs with TensorFlow on GPU clusters. Proceedings of the 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Madrid, Spain. 2017. 677-682.
    Related
    Cited by
Get Citation

贺成,施华君.基于PRAM并行模型最大值查找的方法与改进.计算机系统应用,2019,28(10):138-144

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 20,2019
  • Revised:April 17,2019
  • Online: October 15,2019
  • Published: October 15,2019
Article QR Code
You are the first992102Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063