Revisiting the Sequential Programming Model for Multi-Core

New capabilities needed:
- Automatically run sequential source code on a multi-core processor
- The need for new semantics to achieve this automated process for sequential code
Current capabilities of the hardware towards solving the problem:
- Dependence/Alias speculation
- Value speculation
- Thread-level speculation (TLS) on a shared memory chip multi-processor (CMP) where the hardware maintains the speculative thread state (memory versioning)
- Efficient core-to-core communication
- FIFOs

Single-threaded code that requires performance:
- Existence of inherent parallelism is assumed.
- Code is written in sequential programming style without considering explicit parallelism.
Not following purely sequential semantics:
- Results are non-deterministic.
- Timing is non-deterministic.
“General purpose” code/productivity/performance

Combines many previously known techniques:
- Combining task (pipeline) and data parallelisms have been done in the past. These solutions target pure streaming applications:
  - StreamIt (MIT)
  - Ptolemy (UC Berkeley)
TLS - Data parallelism
Decoupled software pipelining (DSWP) - Pipeline and task parallelism
Added semantics to remove “unnecessary” determinism:
- Y-Branch:
  - True path can always be executed and achieves forward progress.
  - False path is very rare and impacts “quality” but not correctness. It allows refinement control. Paper has introduced the probibility of false path into the system.
- Commutative property
Templatized (pipeline) parallelism

Positive points:
- Presented case studies of some SPEC CINT2000 applications
- Modified applications using new semantics
- Measured parallel speedup - Scalability to more cores
Negative points:
- Didn’t compare to anything else
- Didn’t fully explain why things don’t scale
- No quantitative measurements of specific techniques - Very qualitative explanations
- “Magic” communication - Impacts scalability