PARALLEL QUICKSORT ALGORITHM APPLICATION

Fatin Ameera bt Alissak #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 ameera.alfa@gmail.com
2 faidzms@ieee.org 

 
Abstract—Experienced algorithm designers depend vigorously on an arrangement of building blocks and on the tools expected to assemble the blocks into a calculation. This presentation outlines the general engineering of the parallel vector models; introduces two imperative classes of primitive instructions, the scan and segmented instructions; shows how the model and the instructions can be used to assemble part of a parallel quicksort calculation. The engineering of a V-RAM states that the machine is a random access machine with the expansion of a vector memory, a parallel vector processor, and a vector input/output port. Every area of the vector memory can contain a vector of various length. The parallel vector processor executes operations on entire vectors.
 
Keywords: Parallel, Quicksort, Algorithm, PRAM



REFERENCES

[1]	C. C. Elgot and A. Robinson, "Random-access stored-program machines, an approach to programming languages," in Selected Papers, ed: Springer, 1982, pp. 17-51.

[2]	G. E. Blelloch, "Prefix sums and their applications," 1990.

[3]	G. E. Blelloch, "Scans as primitive parallel operations," Computers, IEEE Transactions on, vol. 38, pp. 1526-1538, 1989.

[4]	D. Cederman and P. Tsigas, "A practical quicksort algorithm for graphics processors," in Algorithms-ESA 2008, ed: Springer, 2008, pp. 246-258.

[5]	G. E. Blelloch and B. M. Maggs, "Parallel algorithms," in Algorithms and theory of computation handbook, 2010, pp. 25-25.

[6]	D. Cederman and P. Tsigas, "Gpu-quicksort: A practical quicksort algorithm for graphics processors," Journal of Experimental Algorithmics (JEA), vol. 14, p. 4, 2009.

[7]	G. E. Blelloch, Vector models for data-parallel computing vol. 75: MIT press Cambridge, 1990.

[8]	A. Church, "Turing AM. On computable numbers, with an application to the Entscheidungs problcm. Proceedings of the London Mathematical Society, 2 s. vol. 42 (1936–1937), pp. 230–265," The Journal of Symbolic Logic, vol. 2, pp. 42-43, 1937.

[9]	E. Sintorn and U. Assarsson, "Fast parallel GPU-sorting using a hybrid algorithm," Journal of Parallel and Distributed Computing, vol. 68, pp. 1381-1388, 2008.

[10]	K. E. Batcher, "Sorting networks and their applications," in Proceedings of the April 30--May 2, 1968, spring joint computer conference, 1968, pp. 307-314.

[11]	N. K. Govindaraju, N. Raghuvanshi, M. Henson, and D. Manocha, "A cache-efficient sorting algorithm for database and data mining computations using graphics processors," University of North Carolina, Tech. Rep, 2005.

[12]	N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, "GPUTeraSort: high performance graphics co-processor sorting for large database management," in Proceedings of the 2006 ACM SIGMOD international conference on Management of data, 2006, pp. 325-336.

[13]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to algorithms second edition," The Knuth-Morris-Pratt Algorithm”, year, 2001.

[14]	S. Sengupta, M. Harris, Y. Zhang, and J. D. Owens, "Scan primitives for GPU computing," in Graphics hardware, 2007, pp. 97-106.