Systolic algorithms to examine all pairs of elements

ABSTRACT

Four methods to solve the all pairs examination problem are presented. The first two methods are based on the fold-over scheme. The remaining two methods are adopted from some parallel sorting algorithms. All of these approaches can be implemented on a linear systolic array.

REFERENCES

• 1: Batcher. K.E. Sorting networks and their applications. In AFIP Proceedings 32. {Atlantic City, N.J.. Apr. JO-May 2. 1968). 307-314.
• 2: Bentley. J.L.. and Ottmann. T. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28, 9 (1979). 643-647.
• 3: Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984 [doi>10.1145/2514.2516]
• 4: Chazelle. B. Computational geometry on a systolic chip. IEEE Trans. Conynil. C-33, 9 (1984). 774-785.
• 5: Hambrusch, A.E. VLSI algorithms for the connected component problem. SIAM /. Compuf. 12, 2 (1983). 354-365.
• 6: Hackney. R.W.. and Jesshope, C.R. Parallel Computers. Adam Hilger Ltd.. Bristol, 1981.
• 7: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 8: Knuth. D.E. Tire Art of Conlpufer Programming. Vol. 3. Addison- Wesley, Reading, Mass., 1972.
• 9: Kong. H.T. The structure of parallel algorithms. In Advances in Cow puters, Vol. 19. Academic Press, New York, 1980, 65-112.
• 10: Kong. H.T. Why systolic architecture? Comput. 15. 1 (1982). 37-46.
• 11: Kong. H.T. Notes on VLSI computation. In Parallel Processing System. D.J. Evans, Ed.. Cambridge University Press, 1982. 339-356.
• 12: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 13: Lee. D.T.. Chang. H., and Wang. C.K.. An on-chip compare steer bubble sorter. IEEE Trans. Contpuf. C-30. 6 (1981). 396-405.
• 14: Lee, D.T.. and Praparata, F.P. Computational geometry: A survey. IEEE Trans. Conlpul. C-33, 12 (1984). 1072-1101.
• 15: Li. G.J.. and Wah. B.W. The design of optimal systolic arrays. IEEE Tracts. Conrpuf. C-34, 1 (1985). 66-77.
• 16: Miranker, G.. Tang, L.. and Wang, C.K. A zero-time VLSI sorter. IBM /. Res. Develop., 27, 2 (1983). 140-148.
• 17: Moldovan, D.I. On the analysis and synthesis of VLSI algorithms. IEEE Tram. Compuf. C-31. 11 (1982), 1121-1126.
• 18: Moldovan. D.I. On the design of algorithms for VLSI systolic arrays. Proc. IEEE 71, 1 (1983), 113-120.
• 19: Patrice Quinton, Automatic synthesis of systolic arrays from uniform recurrent equations, Proceedings of the 11th annual international symposium on Computer architecture, p.208-214, January 1984
• 20: Shames. M.I. Geometric intersection problems. In Proceedings of the 17th IEEE Anmu Symposiunt on Foundations of Computer Science (Houston. Tex.. Oct. 25-27. 1976). 208-215.
• 21: Michael Ian Shamos, Computational geometry., 1978
• 22: Shames. ML. Hoey, D. Closest-point problem. In Proceedings of the 16th IEEE Annual Symposium on Foundations of Cornpurer Science (Berkeley, Calif.. Oct. 13-15. 1975), 151-162.
• 23: Tseng. S.S.. and Lee. R.C.T. A new parallel sorting algorithm based upon min-mid-max operations. BIT 24, 2 (1984). 187-195.
• 24: Ullman. J.D. Conlpufafioflal Aspects of VLSI. Computer Science Press, Rockville. Md.. 1984.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms