# Computational Model

![](https://3310611219-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LwRt8_BWYScDaMKj3wZ%2F-McaNEZMMUEOGHTHdVPU%2F-McaektC1vRICzPinXPk%2Fcomputational_model.PNG?alt=media\&token=faac8aee-6569-43e8-9d71-c3cd7179b6a7)

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

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

![](https://3310611219-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LwRt8_BWYScDaMKj3wZ%2F-McaNEZMMUEOGHTHdVPU%2F-Mcal8btyD57on7epp8q%2Fcomputational_model_2.PNG?alt=media\&token=9b6317bd-6ae0-48b9-bb8d-343b782a0298)