Sorting(2)

Sorting

  • Definition: Arranging numbers (or alphabet) in non-increasing order based on compare and exchange.

Sorting Algorithms

  • Bubble Sort

  • Merge Sort

  • Insertion Sort

Compare and Exchange in Processors

  • Example of communication between processors:

    • Processor 1:

      • Send(A, P2)

      • Recv(M, P2)

      • A = M

    • Processor 2:

      • Recv(M, P1)

      • A = M

      • If (A > B) Send(B, P1) B = A

      • Else Send(A, P1)

Advantages and Disadvantages of Parsing Methods

  • Method I

  • Method II

Definitions

  • Definition 1: Sorted list held in the memory of a single processor.

  • Definition 2: Portion of the list in each processor’s memory is sorted; the value of the last element on Pi’s list is less than or equal to the value of the first element on Pi+1’s list.

    • Allows problem size to scale with the number of processors.

Comparing and Exchange to Sort Two Sets of Numbers

  • Given two sets of numbers: {m1…mx} and {n1..ny} in Processors P0 and P1.

  • How to sort the entire set of numbers? What is the computational complexity?

Steps for Sorting

  • Sort numbers in Processor 0.

  • Sort numbers in Processor 1.

  • Ensure that the max and min of P0 and P1 respect condition 2.

  • Exchange numbers until condition 2 is satisfied.

  • Computational Complexity: ( (n/2)^2 )

  • Communication: ( n/2 )

  • Sequential Complexity: ( n^2 )

Processor Element Count

  • Each processor has ( n/p ) elements

  • Condition 2: Max(Pi) <= Min(P(i+1))

    • Example of swap logic between processors:

      • P0: max(P1) min(P2) P3

      • P0 max(P1) max(P2) min(P3)

Parallel Sorting Algorithms

  • For n numbers to sort on p processors:

    • Allocate ( n/p ) numbers to each processor.

    • Use a parallel sorting algorithm to enforce condition 2:

      • Odd-Even Sorting (Bubble Sort)

      • Hyper-Quicksort

      • PSRS

Objective of Sorting Algorithm Implementation

  • Position the ( i^{th} ) highest number in the ( i^{th} ) iteration:

    for (i = n-1; i > 0; i--) {
    for (j = 0; j < i; j++) {
        Compare and exchange (a[j], a[j+1])
    }
}

  • Sequential Complexity: ( \frac{n(n-1)}{2} = O(n^2) )

Iterative Changes Through Phases

  • Only two neighboring entries are modified in any iteration.

  • Entries to the left have already been modified, enabling the next phase for the left-hand entries.

Phases in Processor Comparison

  1. Processor 1:

    • Compare and exchange position 1 and 2, then send a message to P2.

  2. Processor 2:

    • Receive message from P1, compare and exchange position 1 and 2; send a message to P2.

Alternative Phases for Sorting

  • First phase: compare and exchange between:

    • P0-P1

    • P2-P3

    • P4-P5

    • P6-P7

  • Second phase: compare and exchange between:

    • P1-P2

    • P3-P4

    • P5-P6

Unordered Lists and QuickSort

  • Unordered list of values with selected pivot.

  • Average-case time complexity: Q(n log n) and Worst-case time complexity: Q(n^2).

  • Recognized for faster sorting in average cases due to natural concurrency.

Sample Distribution and Communication Overview

  • Communication patterns during exchanges need to balance work across processors.

  • Exchanges and merges occur after sorting on individual processors:

    • Stepwise merging depends on communication pattern.

Total Computational Complexity Overview

  • Total Communication Complexity: q(log(p) + n/p)

  • Assumption: n >> p, leading to a communication bottleneck.

  • Sequential Time Complexity: Q(n log n)

  • Parallel Overhead: Parallel complexity = Q(n/p)

Summary: Dependencies and Scalability

  • Parallel sorting is influenced by the distribution of numbers.

  • All sorting algorithms fundamentally rely on how effectively numbers are exchanged among processors.