Datamation Sort 1 Million Record Sort using OpenMP

Datamation Sort 1 Million Record Sort using OpenMP

Datamation Sort 1 Million Record Sort using OpenMP and MPI Sammie Carter Department of Computer Science N.C. State University November 18, 2004 1 Background The Datamation sorting benchmark was

introduced in 1985 by a group of database experts as a test of a processor's I/O subsystem and operating system. The performance metric is the time to sort 1 million 100-byte records, where the first 10bytes are the key. 2 Sorting Review The common sorting algorithms can be divided into two classes by the complexity of their algorithms. Algorithmic complexity is a complex subject (imagine that!) that would take too much time to explain here, but suffice it to say that there's a direct correlation between the complexity of an algorithm and its

relative efficiency. Algorithmic complexity is generally written in a form known as Big-O notation, where the O represents the complexity of the algorithm and a value n represents the size of the set the algorithm is run against. The two classes of sorting algorithms are O(n2), which includes the bubble, insertion, selection, and shell sorts; and O(n log n) which includes the heap, merge, and quick sorts. O(logn) < O(n ) < O(nlogn) < O(n2) < O(n3) < O(2n) 3

O(n2) Sorts 4 O(n log n) Sorts 5 Sorting Example Sorting Example 6

OpenMP OpenMP is an industry standard application programming interface (API) for writing parallel applications for shared memory computers. At the heart of OpenMP are directives, or pragmas, programmers insert to incrementally add parallelism to a program. 7 OpenMP Hello World

#include main () { int nthreads, tid; /* Fork a team of threads giving them their own copies of variables */ #pragma omp parallel private(nthreads, tid) { /* Obtain thread number */ tid = omp_get_thread_num(); printf("Hello World from thread = %d\n", tid); /* Only master thread does this */ if (tid == 0) { nthreads = omp_get_num_threads(); printf("Number of threads = %d\n", nthreads); } } /* All threads join master thread and disband */ }

8 MPI Message Passing Interface MPI defines a standard library for message passing that can be used to develop portable message passing programs using either C or Fortran. The MPI stand defines both the syntax as well as the semantics of a core set of library routines that are very useful in writing message-passing programs.

MPI was developed by a group of researchers from academia and industry, and has enjoyed wide support by almost all the hardware vendors. Vendor implementations of MPI are available on almost all commercial parallel computers. 9 MPI Hello World /* mpicc o helloworld helloworld.c */ /* bsub W 2 I n 4 mpiexec ./helloworld */ #include "mpi.h" #include int main(int argc,char *argv[]) { int myrank, numprocs; MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myrank); MPI_Comm_size(MPI_COMM_WORLD,&numprocs) printf("Hello World from process %d of %d\n", numprocs); MPI_Finalize(); return 0; } myrank, 10 OpenMP and MPI Examples

OpenMP Hello World omp_hello.c (mcrae) OpenMP Sort ompmerge3.c (mcrae) MPI Hello World helloworld.c (henry2) MPI Sort mpimerge5.c (henry2) 11

Conclusion Final Sorting Algorithm Description Questions / Comments / Suggestions Contact Information: Sammie Carter [email protected] 12 References

Sorting Algorithms http://linux.wku.edu/~lamonml/algor/sort/sort.html Sorting Algorithms Demo http://www-hm.ma.tum.de/archiv/in2/ss02/vorlesungen/v020606/sort/sort.html Parallel Programming with OpenMP

http://www.intel-u-press.com/openmp/summary.htm Grid Computing (Barry Wilkinson) http://sol.cs.wcu.edu/~abw/CS493F04/slides9.ppt 13

Recently Viewed Presentations

  • Structure of plant and animal cells under an electron microscope

    Structure of plant and animal cells under an electron microscope

    Structure of plant and animal cells under an electron microscope Advanced Higher Biology Cell and molecular Biology The Electron Microscope Two main advantages High resolving power (short wavelength of electrons) As electrons negatively are charged the beam can be focused...
  • PowerPoint Template - CQRC Engage

    PowerPoint Template - CQRC Engage

    Incorporate NHTSA's BAC testing and reporting guidelines, into a statewide action plan to achieve BAC reporting rates of at least 80 percent of fatally injured drivers and at least 60 percent of surviving drivers involved in fatal crashes. Our recommendations...
  • Virágok és gondolatok - ingyenTV.hu

    Virágok és gondolatok - ingyenTV.hu

    Wayne Gretzky A virágok remény nélkül élnek. Ennek az az oka, hogy a HOLNAP a remény, és a virágok számára nincs HOLNAP. Antonio Porchia Ha útelágazáshoz érsz, haladj tovább! Yogi Berra Talán-mivel festő lett belőlem-adósa vagyok a virágoknak.
  • MYTH VS REALITY Body Image Lesson Plan Students

    MYTH VS REALITY Body Image Lesson Plan Students

    Students can make comparisons between what is considered the 'ideal' body image online and the actual reality. Students can propose effective strategies to help young people develop a healthy and positive attitude towards their body image. Students will know where...
  • NCBI FieldGuide NCBI Molecular Biology Resources Using Entrez

    NCBI FieldGuide NCBI Molecular Biology Resources Using Entrez

    NCBI Molecular Biology Resources Using Entrez January 2008 WWW Access Entrez: Database Integration The Links Menu: Access to Neighbors and Links The Links Menu: Access to Neighbors and Links The Links Menu: Access to Neighbors and Links Database Searching with...
  • How to give a scientific talk - Lamont-Doherty Earth ...

    How to give a scientific talk - Lamont-Doherty Earth ...

    More formal attire makes you appear more authoritative and you show you care enough to try to look nice. From "Ask Dr. Marty" AnimalLabNews (Jan-Feb 2007) Dark clothes are more powerful than light clothes. Shirts or blouses with collars are...
  • 新學制下的 多元出路 - Wah Yan College, Hong Kong
  • Topic: Procedural Law - pgil.pk

    Topic: Procedural Law - pgil.pk

    Engles states that socioeconomics develops in a series of stages from primitive communism, slave society, feudalism, capitalism and finally communism. unilineal evolutionism. T. The first stage, primitive communism was an aspect of savagery. characterized by a public control and ownership...