Blog
About

137
views
0
recommends
+1 Recommend
1 collections
    8
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Breadth-First, Ordered Parallel Tree Traversal

      Preprint

      1 , 1 , 1 ,   , 1

      ScienceOpen Preprints

      ScienceOpen

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          There has been a shift towards parallel computing in the computer science field over the past years, which has spurred interest in investigating the parallelization of classic sequential algorithms. Much research has been vested in graphs, particularly the application of breadth-first search. However, a subset of graphs, the tree data structure, has common use in various applications, yet focus tends to remain on graphs. A possible reason is that an effective graph algorithm could easily be applied to a tree, but a tree has a more distinct structure. Therefore, developing algorithms to exploit the specific design of a tree may improve efficiency over the application of a graph algorithm.

          We present concurrent breadth first tree traversal algorithm for M-ary trees, where M is an upper bound to the number of child nodes that a given node may have. The algorithm was developed in Java for portability and differs from other approaches in that it shall provide a meaningful ordering of nodes, which is absent in breadth first graph traversals. The approach provides relative fairness in the work done by each thread to aid scalability and eliminates the use of transactional memory, which appears in other concurrent tree traversals that do provide ordering. However, the use of rollback in these methods introduces a higher level of non-determinism to the computation, which we attempt to avoid for a better analysis of the algorithm.

          Related collections

          Most cited references 1

          • Record: found
          • Abstract: not found
          • Article: not found

          An Efficient Wait-Free Vector

            Bookmark

            Author and article information

            Affiliations
            [1 ] UCF
            Journal
            ScienceOpen Preprints
            ScienceOpen
            26 August 2019
            10.14293/S2199-1006.1.SOR-.PP4CFVL.v1

            This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

            Software engineering

            Comments

            Comment on this article