# MPD programs that find the maximum of an array in various ways and generates
# timing for them.
#
# CS 598 - Concurrent Programming, Summer 2002.

global input

  type etype = double

  # const int A_SIZE = 100
  const int a_size = A_SIZE
  etype a[1:a_size]

  sem mutex = 1
  etype a_max

end input


resource main()

  import input

  procedure find_half_max(int start) returns etype max {

    # Starting at a[start], return the maximum of every other value in the
    # global array a.

    max = a[start]
    int i = start + 2;

    while (i <= ub(a)) {
      if (a[i] > max) {
        max = a[i]
        }
      i += 2
      }
    }


  procedure find_global_half_max(int start) {

    # Starting at a[start], return the maximum of every other value in the
    # global array a.

    int i = start + 2;

    while (i <= ub(a)) {
      P(mutex)
      if (a[i] > a_max) {
        a_max = a[i]
        }
      V(mutex)
      i += 2
      }
    }


  procedure find_par_max() returns etype mx {

    # Return the maximum element in the global array a by looking at the even
    # and odd indices in parallel.

    etype odd_max, even_max

    co
       odd_max = find_half_max(lb(a))
    //
       even_max = find_half_max(lb(a) + 1)
    oc

    mx = max(odd_max, even_max)

    }


  procedure find_seqpar_max() {

    # Return the maximum element in the global array a by looking at the even
    # and odd indices in parallel.

    etype odd_max, even_max

    a_max = a[lb(a)]

    co
       find_global_half_max(lb(a))
    //
       find_global_half_max(lb(a) + 1)
    oc
    }


  procedure find_seq_max() returns etype max {

    # Return the maximum element in the global array a, sequential style.

    int i = lb(a) + 1
    max = a[i - 1]

    while (i <= ub(a)) {
      if (a[i] > max) {
        max = a[i]
        }
      i++
      }
    }


  procedure time_seq(int iters) {

    # Time the sequential array max.

    int etime = 0;

    for [i = 1 to iters] {
      const int stime = age()
      find_seq_max();
      etime += age() - stime;
      }

    printf("sequential %d elements %4.1f ms/call.\n",
           a_size, real(etime)/real(iters))
    }


  procedure time_par(int iters) {

    # Time the parallel array max.

    int stime = age()
    for [i = 1 to iters] {
      }
    const int otime = (age() - stime);

    stime = age()
    for [i = 1 to iters] {
      find_par_max();
      }
    const int etime = (age() - stime) - otime;

    printf("parallel %d elements %4.1f ms/call.\n",
           a_size, real(etime)/real(iters))
    }


  procedure time_seqpar(int iters) {

    # Time the parallel array max.

    int etime = 0;

    for [i = 1 to iters] {
      const int stime = age()
      find_seqpar_max();
      etime += age() - stime;
      }

    printf("sequential-parallel %d elements %4.1f ms/call.\n",
           a_size, real(etime)/real(iters))
    }


  procedure get_opt(int ono, int def) returns int oval {

    # Return the ono-th argument if it exists or the default value def if it
    # doesn't.

    if (numargs() >= ono) {
      getarg(ono, oval)
      }
    else {
      oval = def
      }
    }


  const int iter = get_opt(1, 10);

  time_par(iter)
  time_seq(iter)
  time_seqpar(iter)

end main