List ranking and list scan on the Cray C-90

ABSTRACT

List ranking and list scan are two primitive operations used in many parallel algorithms that use list, trees, and graph data structures. But vectorizing and parallelizing list ranking is a challenge because it is highly communication intensive and dynamic. In addition, the serial algorithm is very simple and has very small constants. In order to compete, a parallel algorithm must also be simple and have small constants. A parallel algorithm due to Wyllie is such an algorithm, but it is not work efficient—its performance degrades for longer and longer linked lists. In contrast, work efficient PRAM algorithms developed to date have very large constants. It does not achieve O(log n) running time, but we contend that work efficiency and small constants is more important, given that vector and multiprocessor machines are used for problems that are much larger than the number of processors and, therefore, the O(log n) running time, but we contend that work efficiency and small constants is more important, given that vector and multiprocessor machines are used for problems that are much larger than the number of processors and, therefore, the O(log n) time is never achieved in practice. In particular, to the best of our knowledge, our implementation of list ranking and list scan on the CRAY C-90 is the fastest implementation to date. In addition, it is the first implementation of which we are aware that outperforms fast workstations. The success of our algorithm is due to its relatively large grain size and simplicity of the inner loops, and the success of the implementation is due to pipelining reads and writes through vectorization to hide latency, minimizing load balancing by deriving equations for predicting and optimizing performance, and avoiding conditional tests except when load balancing.

REFERENCES

• 1: K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
• 2: R. J. Anderson , G. L. Miller, Deterministic parallel list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 3: R. J. Anderson , G. L. Miller, A simple randomized parallel algorithm for list-ranking, Information Processing Letters, v.33 n.5, p.269-273, January 1990 [doi>10.1016/0020-0190(90)90196-5]
• 4: S. Baase. Introduction to parallel connectivity, list ranking, and Euler tour techniques. In J. Reif, editor, Synthesis of Parallel Algorithms, pages 61-114. Morgan Kaufmann, 1993.
• 5: Guy E. Blelloch , Siddhartha Chatterjee , Marco Zagha, Solving Linear Recurrences with Loop Raking, Proceedings of the 6th International Parallel Processing Symposium, p.416-424, March 01, 1992
• 6: Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 conference on Supercomputing, p.666-675, October 1990, New York, New York, United States
• 7: R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
• 8: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• 9: Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
• 10: W. Feller. An lntoduction to Probability Theory and Its Applications. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York, 1971.
• 11: H. Gazit, G. L. Miller, and S.-H. Teng. Optimal tree contraction in the EREW model. In S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, editors, Concurrent Computations, pages 139-156. Plenum Publishing Corporation, 1988.
• 12: Allen R. Hainline , Steven R. Thompson , Lawrence L. Halcomb, Vector performance estimation for CRAY X-MP/Y-MP supercomputers, The Journal of Supercomputing, v.6 n.1, p.49-70, March 1992 [doi>10.1007/BF00128642]
• 13: R. Halverson and S. K. Das. A comprehensive survey of parallel finked fist ranking algorithms. Technical Report CRPDC-93-12, University of North Texas, Aug. 1993.
• 14: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 15: S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 16: M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
• 17: G. L. Miller and 3. H. Reif. Parallel tree contraction and its application. In Proceedings Symposium on Foundations of Computer Science, pages 478-489, Oct. 1985.
• 18: Gary L. Miller , John H. Reif, Parallel tree contraction part 2: further applications, SIAM Journal on Computing, v.20 n.6, p.1128-1147, Dec. 1991 [doi>10.1137/0220070]
• 19: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 20: Margaret Reid-Miller , Guy E. Blelloch, List Ranking and List Scan on the CRAY C-90, Carnegie Mellon University, Pittsburgh, PA, 1994
• 21: M. Reid-Miller, G. L. Miller, and F. Modugno. List ranking and parallel tree contraction. In J. Reif, editor, Synthesis of Parallel Algorithms, pages 115-194. Morgan Kaufmann, 1993.
• 22: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 23: U. Vishkin. Advanced parallel prefix-sums, list ranking and connectivity. In J. Reif, editor, Synthesis of Parallel Algorithms, pages 215-257. Morgan Kaufmann, 1993.
• 24: J. C. WyUie. The complexity of parallel computations. Technical l#eport TR-79-387, Department of Computer Science, Cornell University, Ithaca, NY, Aug. 1979.
• 25: M. Zagha. Efficient Irregular Computations on Vector Multiprocessors. PhD thesis, School of Computer Science, Carnegie Mellon University. In Preparation.
• 26: Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126164]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Measurement, Performance, Theory