Sorting and merging on the DAP

ABSTRACT

The sorting problem is of fundamental importance in non-numerical algorithms. Many applications require the ordering of data based the relationship of some set of keys with in the data. Merging is a natural companion of sorting, and is known to yield a very efficient sorting algorithm in sequential processing. Numerous sorting and merging techniques have been developed for many actual and theoretical models, we examine a number of these techniques for implementation on the Distributed Array of Processors, DAP.

REFERENCES

• 1: Active Memory Technology, Irvine CA. DAP Series: FORTRAN-PLUS Language, 1988.
• 2: Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
• 3: Selim G. Akl, The design and analysis of parallel algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: Hussein M. Alnuweiri , V. K. Prasanna Kumar, Optimal VLSI Sorting with Reduced Number of Processors, IEEE Transactions on Computers, v.40 n.1, p.105-110, January 1991 [doi>10.1109/12.67326]
• 5: K.E. Batcher, Sorting Networks and their Applications, Proc. AFIPS 1968, Spring Joint Comp. Conf., 307-314.
• 6: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 7: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: R. Lin, S. Olariu, J.L. Schwing and J. Zhang, Sorting in 0(1) time on an nxn reconfigurable mesh, submitted, 1991.
• 10: B.C. Merifield, J.B.G. Roberts, P. Simpson, and A. Stanley. Real time applications of DAP, Third Int'l Conf Supercomputing, 1988.
• 11: D. Parkinson, DJ. Hunt, and K.S. MacQueen, The AMT DAP 500, Thirty Third IEEE Comp. Soc. Int'l Conf, 196-199, 1988.
• 12: Dennis Parkinson , John Litt, Massively parallel computing with the DAP, MIT Press, Cambridge, MA, 1990
• 13: J. Pecht and I. Ramm, Recognition of handwritten characters using the DAP, IC L Technical Journal, 199-217, Nov. 1982
• 14: B.-F. Wang , G.-H. Chen , F.-C. Lin, Constant time sorting on a processor array with a reconfigurable bus system, Information Processing Letters, v.34 n.4, p.187-192, April 1990 [doi>10.1016/0020-0190(90)90158-T]

INDEX TERMS

Keywords:
DAP, merging, parallel algorithms, sorting