Comment on page

# Computational Model

- 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

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

- 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

Last modified 2yr ago