Blog
About

  • 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