Title :
study on Sorting of A Parallel Computer Using Protocol in Ubiquitous Environment
Author :
Jung, Chang-Duk ; Park, You-Keon
Abstract :
Sorting can a be major bottleneck in many applications. Performance can vary by orders of magnitude, depending on how the sort operation is implemented. Parallel sorting algorithms have been developed to take advantage of distributed ubiquitous computers. But the speedup of parallel sorting algorithms decrease rapidly with increased number of processors due to parallel processing overhead such as context switching time and inter-processor communication cost. In this paper, we propose a parallel sorting method which provides linear speedup of an optimal serial algorithm for a system with a large number of processors. This algorithm may even provide superlinear speedup for a practical system. The algorithm takes advantage of an interconnection network properties and its protocol in ubiquitous environment.
Keywords :
multiprocessor interconnection networks; parallel algorithms; protocols; sorting; ubiquitous computing; context switching time; distributed ubiquitous environment; interconnection network; interprocessor communication cost; optimal serial algorithm; parallel computer; parallel processing; parallel sorting algorithm; protocol; Application software; Communication switching; Concurrent computing; Context; Costs; Parallel processing; Pervasive computing; Protocols; Sorting; Ubiquitous computing;
Conference_Titel :
Multimedia and Ubiquitous Engineering, 2007. MUE '07. International Conference on
Conference_Location :
Seoul
Print_ISBN :
0-7695-2777-9
DOI :
10.1109/MUE.2007.197