On storage schemes for parallel array access

ABSTRACT

In parallel matrix manipulation operations, some data patterns need to be accessed in one memory cycle without conflict. Investigating the frequently used data patterns, we propose a powerful skewing scheme which allows most frequently used data patterns of N elements, including rows, columns, diagonals, blocks with various shapes, points scattered over various blocks, and chessboards with various shapes, to be accessed in one memory cycle. We also propose simple methods to combine different skewing schemes into a single parallel storage system such that all the frequently used data patterns of N elements (the above patterns plus folded lines, two-pairs, and column-pairs) can be accessed in one memory cycle. The storage sytem uses N memory modules where N is any (even or odd) power of two. Address generation in the system need only exclusive-or operations and can be completed in constant time. The storage scheme allows different sized matrices to be processed efficiently on large scale systems by using the skewing scheme designed according to the size of the system, i.e. address generation mechanism is independent of the size of the matrices to be processed. Data alignment requirements (connecting each memory module to a proper processor) can be easily realized on a general-purpose interconnecting network, such as a hypercube.

REFERENCES

• 1: M. Balakrishnan, R. Jain, and C. S. Raghavendra. On array storage for conflict-free memory access for parallel processors, in Proc. of lhe 1988 International Conference on Parallel Processing, volume I, pages 103-107, Aug. 1988.
• 2: K. Batcher. The multidimensional access memory in STARAN. IEEE Trans. on Computers, C-26(2):174-177, February 1977.
• 3: B. V. Boppana and C. S. Raghavendra. Efficient storage schemes for arbitrary size square matrices in parallel processors with shuffle-exchange networks, in Proc. of the 1991 International Conference on Parallel Processing, volume I, pages 365-368, Aug. 1991.
• 4: P. Budnik and D. J. Kuck. The organization and use of parallel memories. IEEE Trans. on Computers, C-20(12):1566-1569, Dec. 1971.
• 5: B. Chor, C. E. Leiserson, and R. L. Rivest. All a,pplication of number theory to the organizatiol~ of raster-graphics memory. In Proc. of lhe 23rd Annual IEEE Symposium on Foundations of Computer Science, pages 92-99, 1982.
• 6: J. M. Frailong, W. Jalby, and J. Lenfant. XOR- Schemes: A flexible data organization in parallel memories. In Proc. of the 1985 lnternatzonal Conference on Parallel Processing, pages 276- 283, Aug. 1985.
• 7: Rafael C. Gonzales , Paul Wintz, Digital image processing (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 8: D. Harper III. Address transformation to increase memory performance. In PTvc. of the 1989 h~lernational Conference on Parallel Processing, pages 237- 241, Aug. 1989.
• 9: D. T. Harper , D. A. Linebarger, A dynamic storage scheme for conflict-free vector access, Proceedings of the 16th annual international symposium on Computer architecture, p.72-77, April 1989, Jerusalem, Israel
• 10: D. T. Harper, III, Block, Multistride Vector, and FFT Accesses in Parallel Memory Systems, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.43-51, January 1991 [doi>10.1109/71.80188]
• 11: K. Kim and V. K. P. Kumar. Parallel memory systems for image processing. In Proc. of the 1989 Conference on Compuler vision and Patter~ Recognition (CVPR'89), pages 654-659, 1989.
• 12: K. Kim , V. K. Prasanna-Kumar, Perfect Latin squares and parallel array access, Proceedings of the 16th annual international symposium on Computer architecture, p.372-379, April 1989, Jerusalem, Israel
• 13: D. H. Lawrie. Access and alignment of data in array processors. IEEE Trans. on Computers, C- 24(12):1145-1155, Dec. 1975.
• 14: D. H. Lawrie and C. R. Vora. The prime memory system for array access. IEEE Trans. on Computers, C-31(5):435-442, May 1982.
• 15: D.-L. Lee, A multiple-processor architecture for image processing, University of Alberta, Edmonton, Alta., Canada, 1987
• 16: D.-L. Lee, On access and alignment of data in a parallel processor, Information Processing Letters, v.33 n.1, p.11-14, Oct. 1989 [doi>10.1016/0020-0190(89)90180-4]
• 17: D. Lee and M. Aboelaze. An efficient method for distributing data in hypercube computers. In Proc. of the 5th D~strzbuted Memory Computing Conference, pages 858-866, April 1990.
• 18: X. Li, Parallel Algorithms for Hierarchical Clustering and Cluster Validity, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.11, p.1088-1092, November 1990 [doi>10.1109/34.61708]
• 19: A. Norton and E. Melton. A class of Boolean linear transformations for conflict-free power-of-two stride access, in Proc. of the 1987 International Conference on Parallel Processing, pages 247- 254, Aug. 1987.
• 20: Jong Won Park, An efficient memory system for image processing, IEEE Transactions on Computers, v.35 n.7, p.669-674, July 1986 [doi>10.1109/TC.1986.1676813]
• 21: C. S. Raghavendra and R. Boppana. On methods for fast and efficient parallel memory access. In Proc. of 1he 1990 international Conference on Parallel Processing, volume I, pages 76- 83, Aug. 1990.
• 22: D. V. Voorhis and T. H. Morrin. Memory systems for image processing. IEEE Trans. on Computers, C-27(2):113-125. February 1978.
• 23: Harry A. G. Wijshoff, Data Organization in Parallel Computers, Kluwer Academic Publishers, Norwell, MA, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  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.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Performance, Theory

Keywords:
address generation, matrix manipulation, memory conflict, parallel processing, skewing schemes