Comment on page

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
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