Fast and Efficient Parallel Coarsest Refinement

• Autorzy: Juneam N. , Kantabutra S.

Identyfikatory

DOI

10.3233/FI-2017-1465

• Języki publikacji: EN

Abstrakty

EN

The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X, Y of the set U such that X = {X1, X2, ...,Xx} and Y = {Y1, Y2, ..., Yy}, and determine a new partition Z = {Z1, Z2, ..., Zz} such that each is a common non-empty subset of some Xa ∈ X and some Yb ∈ Y and |Z| is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t(n) + log n) parallel time using max{nlogn, p(n)} processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW PRAM. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(lognlog(nlogn)) parallel time using nlogn processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm.

Słowa kluczowe

EN

PRAM algorithms; parallel computation; coarsest refinement; partition refinement

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 150, nr 2
• Strony: 211--220
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Juneam N.

• Department of Computer Science, Faculty of Science, Chiang Mai University, Chiang Mai, 50200, Thailand

autor

Kantabutra S.

• The Theory of Computation Group, Department of Computer Engineering, Faculty of Engineering, Chiang Mai University, Chiang Mai, 50200, Thailand

Bibliografia

• [1] Ajtai M, Komlós J, Szemerédi E. An 0(n log n) Sorting Network. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC’83. ACM, New York, NY, USA. ISBN: 0-89791-099-0, 1983 pp. 1-9.
• [2] Cole R. Parallel Merge Sort. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS’86, IEEE Computer Society, 1986 pp. 511-516. doi: 10.1109/SFCS.1986.41.
• [3] Leighton T. Tight Bounds on the Complexity of Parallel Sorting. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC’84. ACM, New York, NY, USA. ISBN: 0-89791-133-4, 1984 pp. 71-80. doi: 10.1145/800057.808667.
• [4] Bahig HM, Daoud SS, Khairat MKA. Parallel Self-Index Integer Sorting. J. Supercomput, 2002; 22 (3): 269-275. doi: 10.1023/A:1015365901501.
• [5] Hopcroft JE. An n log n Algorithm for Minimizing States in a Finite Automaton. In: Theory of Machines and Computations. Academic Press, London, 1971 pp. 189-196. doi: 10.1016/B978-0-12-417750-5.50022-1.
• [6] Paige R, Tarjan RE. Three Partition Refinement Algorithms. SIAM J. Comput., 1987; 16 (6): 973-989. doi: 10.1137/0216062.
• [7] Habib M, Paul C, Viennot L. Partition Refinement Techniques: An Interesting Algorithmic Tool Kit, 1999 doi: 10.1142/S0129054199000125.
• [8] Bender MA, Sethia S, Skiena SS. Data Structures for Maintaining Set Partitions. Random Struct. Algorithms, 2004; 25 (1): 43-67. doi: 10.1002/rsa.20025.
• [9] Greenlaw R, Hoover HJ, Ruzzo WL. Limits to Parallel Computation: P-completeness Theory. Oxford University Press, Inc., 1995. ISBN: 0-19-508591-4.
• [10] Leighton FT. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992. ISBN: 1-55860-117-1.
• [11] Cormen TH, Stein C, Rivest RL, Leiserson CE. Introduction to Algorithms. McGraw-Hill Higher Education, 3nd edition, 2009. ISBN: 9780262533058.
• [12] Brent RP. The Parallel Evaluation of General Arithmetic Expressions. J. ACM, 1974; 21 (2): 201-206. doi: 10.1145/321812.321815.
• [13] Ladner RE, Fischer MJ. Parallel Prefix Computation. J. ACM, 1980; 27 (4): 831-838. doi: 10.1145/322217.322232.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).