Problem:

  • Automatic parallelization techniques don’t do well on many codes
  • Compile, run sequential programs on multiple cores/programs
  • High Level: Have any programmer write any sequential code, and run in parallel. Because no more serial processors.

(Write code as you do, run in parallel)

Intended Users:

  • Programmers. Or someone with access to source ( can update code for benefit). Even parallel programmers can benefit. Leave more code sequential.
  • Update old parallel code. (Tweak for changes in processors).
  • Potential users:(not discussed) already parallel programmers can benefit.

Debugging, maintaining, overly parallelizing can be an issue. Single Program with automatic threading.

Solution

  • Used “existing” techniques:

Couple Techniques (Mechanisms for parallelism) (DSWP,TLS) and mechanisms to express opportunities for parallelism. DSWP- Decoupled software pipelining. (Analogous to SWP). 

		for(i=0…n){
		A[i]=2*B[i]
		}

Not directly coupled 

		Ld B[I]
		   =2*
		  St A[i] ld B[I+1]
		   i++
  • TLS (Thread level speculation)−95’ or so. (Multiscalar, wisconsin) and (Hydra, first multi core research project)

(Guessing parallelism is ok (loop iterations, function calls) (Value speculation) might help with loop counters. Many loops don’t have loop carry dependance. (unrolling loops in space).

  • Y Branches, Sanjay Patel.
  • Probability somehow involved. ( Not exactly, more how frequently)

Compiler hint to how frequently should have taken. Historically no hints, programmer hints, profiling hints, profile driven compile hints. (Too far from original) It’s ok to take the branch even if it is not supposed to.

  • User cannot be completely oblivious to techniques.

Possible multiple paths to same answer Say we’re trying to optimize a problem,try to find minimum. Not fully deterministic execution, but acceptable answer is ok. Many programs have multiple potential correct outputs. Lossless compression, small enough that can store in. Modern search.

  • Find Commutative functions-

Associativity (1+2)+(3+4)+(5+6) Comuutative Arbitrary order allowed. Execute in any order

Does it Solve? Mechanisms for parllelization aren’t’ necessarily available. Need support for recovery/communication and synchronization. Recently beginning to have transactional memory support on hardware.

Evaluation Simulation (Because of DSWP and TLS) Doesn’t model important behavior, like limited memory bandwidth and inter thread communication. (Unrealistic assumptions) Some parameters came from measurements on real HW SPEC INT 2000 – Suite meant to evaluate sequential processors, get it to run on parallel “automatically”. Sensitivity/Scaling analysis - Pretty good.

  • Qualitative

Show code examples to show how little they have to change. Lines of code metrics No Comparisons, (Changed code but didn’t show what would happen if they didn’t) Used single thread as base) No comparisons to other techniques.

  • Quantitative

Quantifying how hard it was to change code is not easy. Lines of code (Some might measure productivity of programmers by lines of code produced per day) Easy to measure Number of Tokens Easy but annoying to measure Time ( How many programming hours, time to solution) Hard to measure. What is an average programmer in terms of time hard to find Surveys (Give a problem and tools to solve, ask how hard to do it) Paper doesn’t tell you how many lines of code needed to understand. (Vs changed as stated. However,these can result in potentially better and more insightful conclusions.

Convincing? Contention between threads is not modeled. Conducting experiments is rarely done. (Bureaucracy)

Final Thoughts

  • Open NP ( Annotate code)

Explicitly parallel code. Must explicitly say there are no dependencies. Difference is in this don’t need to understand parallelism, just that certain parts are commutative, or meet characteristics of Y branches. (Meet certain characteristics)

  • Moral is, if you write sequential code, expect little gain.

Exceptions: Streaming, certain restricted formats that are automatically parallelized well. However, very few people program in parallel, so any help may potentially be good.

  • Functional languages is an example of arbitrary people writing parallel code.

(SQL – very parallel without knowing it). Java- threading primitives, (Primitives to write parallel code). Open NP( For all- every iteration of this loop is independent of other iterations)

  • Multiple programs lets us use our processors without running explicitly parallel code.