Sorting is one of the basic problems that have been extensively studied. There are many sorting algorithms which are efficient in computation but cannot use cache efficiently. Efficient use of cache is an important factor for determining the performance of an algorithm. Cache-oblivious algorithms are designed that are both work and cache efficient. The aim of this paper is to evaluate the performance of cache-oblivious sorting algorithm called Lazy Funnelsort on multicore processors. The evaluation is made against the well known fast sorting algorithms: quick sort, merge sort on multicore processor machine. The experiments are conducted against different input sizes and number of processing cores and threads using Intel Cilk Plus, which is extension to C and C++ to express task and data parallelism. The performance of algorithms is examined in terms of execution time, speedup, efficiency and scalability. The results show that parallel implementation of Lazy Funnelsort is better than its sequential implementation and also scalable on multiple cores. Though it has been outperformed by quick sort and merges sort algorithms but shows moderate promise as a parallel algorithm.

Cache-oblivious, Funnelsort, Performance, Speedup, Efficiency, Cache-miss-ratio

[1] L. Arge, M. Goodrich, M. Nelson, and N.Sitchinava, “Fundamental parallel algorithms for private-chip multiprocessors”, In the Proceedings of the 20th ACM SPAA, pp. 197-206, 2008.
[2] G. Blelloch and P. Gibbons, “Effectively sharing a cache among threads”, In the Proceedings of the 16th ACM SPAA, pp. 235-244, 2004.
[3] U. A. Acar, G. E. Blelloch, and R. D. Blumofe, “The data locality of work stealing”, Theory of Computing Systems, vol. 35, pp.3, 2002.
[4] G. Bilardi, A. Pietracaprina, G. Pucci, and F. Silvestri, “Network-oblivious algorithms”, In the Proceedings of the 21st IEEE IPDPS, 2007.
[5] R. A. Chowdhury and V. Ramachandran, “The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and experimental evaluation”, In the Proceedings of the 19th ACM SPAA, pp. 71–80, 2007.
[6] R. A. Chowdhury and V. Ramachandran, “Cache-oblivious dynamic programming”, In the Proceedings of the 17th ACM-SIAM SODA, pp. 591–600, 2006.
[7] G. Blelloch, R. Chowdhury, P. Gibbons, V. Ramachandran, S. Chen, and M. Kozuch, “Provably good multicore cache performance for divide-and-conquer algorithms”, In the Proceedings of the SODA, pp. 501–510, 2008.
[8] M. Frigo and V. Strumpen, “The cache complexity of multithreaded cache oblivious algorithms”, Theory Compute. Syst., vol. 45, no. 2, pp. 203–233, 2009.
[9] R. Cole and V. Ramachandran, “Resource oblivious sorting on multicores”, In the Proceedings of the ICALP, Track A, 2010.
[10] Richard Cole and Vijaya Ramachandran, “Efficient Resource Oblivious Algorithms for Multicores with False Sharing”, In the Proceedings of the IEEE 26th IPDPS, pp. 201 – 214, 2012.
[11] L. Arge, M. T. Goodrich, M. Nelson, and N. Sitchinava, “Fundamental parallel algorithms for private-cache chip multiprocessors”, In the Proceedings of the ACM SPAA, pp. 197–206, 2008.
[12] G. Belloch, P. Gibbons and H. Simhadri, “Brief announcement: Low depth cache-oblivious sorting”, In the Proceedings of the ACM SPAA, ACM, 2009.
[13] G. S. Brodal and R. Fagerberg, “Cache-oblivious distribution sweeping”, In the Proceedings of the 29th International Colloquium on Automata, Language and Programming, ICALP, vol. 2518, Springer, New York, pp. 426-438, 2002.
[14] M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran, “Cache-oblivious algorithms”, In the Proceedings of the 40th IEEE FOCS , pp.285-297, 1999.
[15] A. Aggarwal and J. S. Vitter, “The input/output complexity of sorting and related problems”, Comm. ACM 31, 9, 1116-1127, 1988.
[16] G. S. Brodal, R. Fagerberg and K. Vinther, “Engineering Cache-Oblivious Sorting Algorithm”, Journal of Experimental Algorithmics, vol. 12, ACM, New York, 2008