Transcript grossman_mpe09

Parallel Programming in Undergraduate
Education: A View from the Ground
Dan Grossman
University of Washington
Workshop on Directions in Multicore Programming Education
March 8, 2009
A few hats
1. Researcher in programming languages
– Semantics for transactional memory, etc.
2. Teacher at University of Washington
– Freshmen through advanced graduate courses
– Added 10% concurrency/parallelism to some courses
3. Current co-chair of department core-curriculum revision
– Updating a 20-year-old course structure
– Largely juggling 40 brilliant people’s perspectives
Today’s opinions, all my own, informed by all
– But focus on experience from (3)
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
2
Trade-offs
Do I believe every computer-science undergraduate needs to be
prepared for the multicore era?
Absolutely. But rather than “preaching to the choir”…
What about:
Web programming
MapReduce
Software security
Software process
UI design
Machine learning
Embedded systems
March 8, 2009
Technical writing
Business
Co-op experience(s)
Foreign language
Shakespeare, Freud, Darwin, …
And of course everything
we already require?
Dan Grossman: Undergraduate Parallel Programming
3
First things first
So before what/how/where to teach multicore programming…
What does an undergraduate curriculum actually look like?
– The outdated one we’re changing
– Where we’re probably heading
• Similar to many of our peers
– Where concurrency/parallelism currently appears
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
4
A few details
Each University has particular constraints
University of Washington:
– Top-ten department at a large public university
– Very selective admission to the major
– Quarter system: 10-week courses
– Community-college transfers 2+2 years (in theory)
– Arcane credit-hour rules and such
None of this matters… except it does
Walk through an undergraduate career…
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
5
Curriculum overview
CS1
March 8, 2009
Procedural programming in Java
• 1800+ students a year
• 88% won’t become CS majors
– What should they see
• Massive logistical infrastructure
Dan Grossman: Undergraduate Parallel Programming
6
Curriculum overview
CS1
CS2
March 8, 2009
ADTs, lists, trees, recursion, inheritance
• 900+ students a year
• 75% won’t become CS majors
Dan Grossman: Undergraduate Parallel Programming
7
Curriculum overview
CS1
CS2
March 8, 2009
“300-level”
8 required courses
– back to this in a minute
– what we are trimming / modernizing
Dan Grossman: Undergraduate Parallel Programming
8
Curriculum overview
CS1
“300-level”
CS2
“400-level”
 20 choices
– students take  5
–  1 per “area”
• almost no sequences
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
9
Curriculum overview
CS1
“300-level”
CS2
“400-level”
capstone
design
March 8, 2009
synthesis experience
• several options
• widely loved
Dan Grossman: Undergraduate Parallel Programming
10
300-level today (8 required courses)
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
11
300-level today (8 required courses)
discrete
structures
March 8, 2009
logic, proofs, sets,
combinatorics,
probability, …
Dan Grossman: Undergraduate Parallel Programming
12
300-level today (8 required courses)
discrete
structures
formal
models
March 8, 2009
finite automata, regexps,
context-free languages,
Turing machines
Dan Grossman: Undergraduate Parallel Programming
13
300-level today (8 required courses)
discrete
structures
formal
models
March 8, 2009
data
structures
big-O, balanced trees, heaps,
hashing, sorting, graph
algorithms, NP-completeness
Dan Grossman: Undergraduate Parallel Programming
14
300-level today (8 required courses)
discrete
structures
formal
models
March 8, 2009
programming
languages
functional programming, static
vs. dynamic typing, modularity,
ML/Haskell, Scheme, Ruby
data
structures
Dan Grossman: Undergraduate Parallel Programming
15
300-level today (8 required courses)
discrete
structures
formal
models
March 8, 2009
programming
languages
digital
design
boolean algebra,
gates, binary
numbers, finite
automata, ALUs
data
structures
Dan Grossman: Undergraduate Parallel Programming
16
300-level today (8 required courses)
discrete
structures
formal
models
March 8, 2009
programming
languages
digital
design
“303”
C, tools, “ethics”,
everything else
data
structures
Dan Grossman: Undergraduate Parallel Programming
17
300-level today (8 required courses)
discrete
structures
formal
models
programming
languages
data
structures
digital
design
“303”
architecture
assembly programming,
CPU design, caching,
pipelining
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
18
300-level today (8 required courses)
discrete
structures
formal
models
programming
languages
data
structures
digital
design
architecture
“303”
statistics
probability distributions,
regression, …
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
19
What’s the problem
discrete
structures
formal
models
programming
languages
data
structures
digital
design
architecture
“303”
statistics
Too many requirements
– Field now too large for everyone to take everything
Outdated
– In overall focus and details
Have innovated within courses, especially parallelism (more later)
– Me: 1 week C threads and shared-memory in “303”
– Luis Ceze: 1 week in architecture
– Note: Digital design inherently parallel too
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
20
Where we’re going
Revision in progress and highly tentative, but broad strokes are:
– Fewer requirements
• Cannot require the entire “embarrassed list”
– Opportunity for earlier specialization
– (cf. Berkeley, Cornell, Stanford, Texas, many others)
Only touching 300-level for now
– Free up room to modernize 400-level later
– Little parallelism at 400-level today
• Synchronization mechanisms in O/S
• New elective course on MapReduce computing
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
21
Required core
math
foundations
probability
for CS
modern
software
design
data
structures
+ ??
hw/sw
interface
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
22
Optional core (50-90%)
March 8, 2009
data mgmt
C/C++
programming
net-centric
computing
hardware
design
??
??
Dan Grossman: Undergraduate Parallel Programming
23
Where are we
•
Done: A top-down view of a curriculum
•
Now: How might we prepare students for multicore
1. Reorient entire curriculum
• unlikely, risky
2. Add concurrency and parallelism courses
• yes, but “we” don’t mean the same thing by that
3. Integrate concurrency and parallelism where relevant
• my preference
• some personal experience
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
24
Being radical
I’m not opposed to parallel-from-day-one
– After all, I’m a functional programmer at heart
– And we can avoid so much unnecessary sequential thinking
But I think it’s unrealistic
– What can most instructors teach freshmen in 10 weeks?
Even though you can do it:
“Educational experiments are doomed to succeed”
Albert Shanker, former Pres. Amer. Federation of Teachers
(Reminds me of “my” programming-languages course.)
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
25
Senior-level courses
• Yesteryear: Threads + synchronization mechanisms in O/S
– Historical accident: only course that needed it
• But: “a course on multicore stuff” means too many things
– Architecture / very-low-level software
– Concurrency*
• primary challenge: responsiveness to external events
• Example: O/S
– Parallelism*
• primary challenge: use resources to increase throughput
• Example: scientific computing
* other words we can agree on welcome
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
26
Some great, very different things
…
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
27
To be clear
• These are all great and important topics
– Not just saying that because you are here
– (But probably a dozen more books from people not here)
• But they’re also really different
– Topics, paradigms, emphases, levels of abstraction
– Overlap < 30% (?) (probably seems even less to students)
• Do we mean students should have:
– One of these?
– All of these?
– “My way”
– …
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
28
My preference
Add 1-2 weeks of parallelism to an existing core-topic course
1.
2.
3.
4.
5.
Data structures / algorithms
Introductory architecture*
Programming languages
Compilers and run-time systems
C programming* (or Java, doesn’t matter)
Briefly consider each of these, with more details on (5)
– Something I’ve done 3 times with 2nd-year students
*Actually done at Washington
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
29
Data structures / algorithms
• Amdahl’s Law
• Span
– The notion of dependencies
• Thread-local versioning (caching)?
Basically what Guy B. suggested
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
30
Architecture
Topics mentioned “at least in lecture”
• Amdahl’s Law
• Synchronization primitives (CAS, LLSC, etc.)
• Mutual exclusion
• Need for cache coherence
• SIMD
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
31
Programming languages
• Threading and synchronization primitives
– An interpreter supporting concurrent threads
• Data races vs. application-level races
• Data-race freedom
Similar to coverage in Michael’s book chapter, but less is okay
Note: In graduate courses, I teach Concurrent ML
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
32
Compilers / run-time systems
• “Threads Cannot Be Implemented as a Library” [Boehm 05]
• Why nearly every compiler optimization violates sequential
consistency
• Maybe why concurrent and/or parallel garbage collection is hard
Separate/related note: Would like more focus on “how Java is
implemented” than on “how is C converted to assembly”
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
33
C programming
For students with 20 weeks of Java + 3 of C, I do this in 2 hours:
1. Race condition on a file via bash scripts
2. Thread basics (multiple call stacks, creation in C and Java)
3. Why use threads? Any one of:
– Performance, Failure isolation, Responsiveness,
Natural for the algorithm
4. Shared memory; the need to synchronize
– Data races vs. higher-level races
5. Fork/join parallelism (in C and Java)
6. Bank-account example
– First with atomic blocks (via Eclipse debugger plug-in)
– Then with locks (discussing deadlock and false sharing)
7. One slide warning them against sequential consistency
– So I’m not lying
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
34
Why this methodology
Some “director’s commentary” on this material
•
Using atomic blocks for pedagogy nicely separates:
1. Determining application’s critical sections (hard!)
2. Finding a good locking protocol (also hard!)
•
I heavily emphasize basic methodology:
1. Immutable data isn’t racy (remember, I’m a functional guy)
2. Thread-local data isn’t racy
3. Rarely acquire a lock while holding one
•
Obviously there is more to do, such as:
1. Communication beyond shared memory
2. Actually achieving speed-up or responsiveness
About exposure to the issues, not (yet) about broad competence
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
35
Conclusions
• Computing undergoing a multicore revolution
– But it’s okay for education to undergo a multicore evolution
– Research should be radical and contrarian
– Teaching experiments are doomed to succeed
• Replace 10% of your course with parallelism and/or concurrency
– Go ahead and teach parallelism to freshmen if you want to
– Also add focused senior-level courses
• Teach good habits even when assumption is sequential
– High-level operations without unnecessary dependencies
– Mostly functional
• Don’t despair: always better to have too much to teach!
March 8, 2009
Dan Grossman: Undergraduate Parallel Programming
36