Computational Model

Random-Access Machine (RAM)

• Unit cost for

  • any instruction on O(log(n))-bit words

  • Read/write a single memory location from an infinite memory

• The cost measure: time complexity

variant: Parallel RAM (PRAM) model

Fork-Join Model

• is the main model of parallel execution in the OpenMP framework

• In addition to RAM instructions, you can also use in parallel and parallel for instructions.

mergesort(A, lo, hi):
  if lo < hi:
    mid = ⌊lo + (hi - lo) / 2⌋
    fork mergesort(A, lo, mid) // process (potentially) in parallel with main task
      mergesort(A, mid, hi)    // main task handles second recursion
    join
      merge(A, lo, mid, hi)

Work-Span Model

• For all computations, draw a DAG

  • A->B means that B can be performed only when A has been finished

• Work: the total number of operations

• Span (depth): the longest length of chain