- Parallel algorithm for Sorted Sequence Search(Akshay Singh)
-
Material Type:
Coding example 
Technical Format:
text file, PDF document, zip archive Location:
Go to materials Date Added:
08/06/2010 Date Modified:
08/06/2010 Author
Akshay Singh , Pune, India Description: The included source code implements a parallel search algorithm on an input sorted sequence of strings, as described in the included problem description text file. The parallel algorithm divides the input data into a number of non-intersecting segments, one per thread, and does parallel binary searches on the assigned segment by each thread for each of the multiple search strings. POSIX Threads is used for implementing the parallelism. The code was intended for Linux OS and includes a makefile to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Parallel binary search, sorted search, POSIX Threads, Pthreads
- Parallel algorithm for Sorted Sequence Search (Deng Hui)
-
Material Type:
Coding example Technical Format:
text file, Word document, zip archive Location:
Go to materials Date Added:
08/06/2010 Date Modified:
08/06/2010 Author
Deng Hui, Beijing, China Description: The included source code implements several different serial and parallel search algorithms on an input sorted sequence of strings, as described in the included problem description text file. Besides the standard binary search algorithm, the code includes a hash map based search. The hash map search algorithm is in two ways, one with Intel Threading Building Blocks (TBB) and the second using OpenMP. The choice of search algorithm can be selected on the command line in order to more easily compare execution performance of different algorithms on given data sets. Build environments for both Windows and Linux are included. Utilization of Intel Parallel Studio to correct and refine the performance is documented.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
Chinese Keywords:
Parallel binary search, sorted search, Threading Building Blocks, TBB hash map, OpenMP
- Parallel algorithm for Sorted Sequence Search(Dmitry Vyukov)
-
Material Type:
Coding example Technical Format:
text file, zip archive, Word document Location:
Go to materials Date Added:
08/06/2010 Date Modified:
08/06/2010 Author
Dmitry Vyukov, Moscow, Russia Description: The included source code implements a parallel search algorithm on an input sorted sequence of strings, as described in the included problem description text file. The included write-up considers two approaches to the parallel algorithm, and reasons for lack of performance are examined. In order to overcome random memory access overheads, a pipeline algorithm is employed to preload cache. OpenMP is used for implementing the parallelism. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Parallel search, sorted search, pipeline, memory access, OpenMP
- Parallel algorithm for Sorted Sequence Search(Vincent Zhang)
-
Material Type:
Coding example Technical Format:
Word document, text file, zip archive Location:
Go to materials Date Added:
08/06/2010 Date Modified:
08/06/2010 Author
Paul Steinberg, Beijing, China Description: The included source code implements a parallel search algorithm on an input sorted sequence of strings, as described in the included problem description text file. The included write-up of the parallel algorithm sets for the pros and the cons for using either OpenMP or Pthreads to implement the parallelism. The implemented Pthreads code attempts to overlap I/O with the parallel searches to boost performance. The code was intended for Linux OS and includes a makefile to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Undergraduate students Language:
English Keywords:
Parallel search, sorted search, POSIX Threads, Pthreads, OpenMP, overlap computation, and, I/O