Blogging from ISCA: CARD: Panel Session, Multicore Programming

Arvind, David August, Keshav Pingali

Phrased as a debate between A and P

The motion: How should the potential of multicore processors be extracted by applications programmers?

Arvind: Intro

Implicit vs. Explicit

...composability...

Too much detail => programming to hard. But is there an appropriate level of detail.

(AFG: infinite fine grain CPUs. Expose memory, cache, line size.)

Is expressing non-determinism essential to ||?

Speculation? Or not?

Debaters: August for (implicit), Pingali against (implicit, for explicit).

The motion: How should the potential of multicore processors be extracted by applications programmers.

August

NOT parallel programming

NOT parallel compilers

FOR implicitly parallel programming, + parallelizing compilers.

What is implicitly parallel programming.

E.g. "inline" directive on function. - explicit. Implicit inlining done automatically by compiler. Often better than human.

Tim Mattson's list of >150 explicit parallel programming languages/systems.

Q: Is explicit parallel programminginherently more difficult than implicit parallel programming?

Quotes Pingali PLDI, quoting Tim Sweeney, who said that Unrel || tripled SW development.

SQL: ... implicit parallel. Another Pingali quote.


Example: commutative annotation. e.g. indicating orderof rand calls between loop iterations. "It's okay if I get my random numbers out of order."

SPECint2000, modified ~50 lines of code of 2M. "Restored the trend" ...

Is it important to be able to express non-dererminism: YES.

Speculative Execution? YES

Is explicitly || needed by anyone other than compiler writers and systems programmers? NO

Only explicit indications needed are of the form function/anti-function (ad-to-list/remove-from-list).

Allies: Church Turing Thesis

Full Employment for Compiler Writer's Thesis.

Pingali

For explicit.

Necessary evil for applications programmers writing irregular programs, e.g. linked data structures.

YES to non determinism. YES to speculation. (Data value dependent parallelism.)

Delaunay Mesh Refinement.

Don't care non-determinism.

Parallelism depends on run-time analysis. Compiler can't...

(AFG: can compiler generate the code to do the analysis?)


Galois model (non deterministic set iterators.)

Collections approach: libraries implemented parallel by experts,
used by higher level programmers. E.g. database B-trees.

Problems: no fixed set of datastructures.

Even generic datastructures need to be tuned.

In many applications the API functions do little computation. Little time in the datastructures. (AFG: but ||ing e.g. a map execute-over-all...)

August counterexamination of Pingali

A: Are there more libraries than programs?

P: Doesn't matter. App programmer still needs to optimize data structure for his app.

A: since in Q&A, I won't explain how you were wrong.

A: Are there patterns? Cliches? Compiler support for same.
In the past when compilers were a 15% solution, not enough money to develop.

(AFG: how many compilers handle even the Gang of 4 patterns? Let alone parallel programming.)

P: functional languages, compilers, haven't gone anywhere over the years.

A: analysis wrong crutch to lean on. E.g. perl (perlbmk). Parallelism in input set. No amount of analysis, neither compiler nor Perl programmer, will know ||ism.
Runtime analysis.

Audience

Mattav (sp?) UT prof: Parallelism not a problem. Implicit works. Explicit works. Tuning is the problem.

A: compiler needs to observe effects of transformation. Run-time feedback.

Mattav summarized P and A's response as "both of you are saying implicit for locality".

I asked my STL question.

To P: not using STL grounds for firing. Customizing grounds for firing. Maybe just fire them all / wait until ew generation hired?

P: STL doesn't parallelize. Is just the datastructure. (He didn't follow the map applicator). Joe programmers, doman specific. Stephanie programmers, ||. (He didn't say ninja/padawab.)

To A: people using iterators, but not map application. Can your compiler convert?

A responded: there exist tools that change datastructure, e.g. list to vector,
or to skiplist.

...

Audience Q: to A: where do you draw the line between explicit ad explicit.

A: if the annotation brings information that cannot be determined automatically, that's implicit. (AFG: copout. That's explicit. But nevertheless still appropriate.)

Arvind's close

If a course is important enough to teach to grad students, why not teach to freshmen?

Should || programming be taught to freshmen?

A: explicitly || programming taught to junior/senior (3rd/4th year)

P: Teach about parallelism in algorithms first. Later, implicit parallel at Joe level.
Later still, fully explicitly parallel.

Vote

Applications programmers do not need to write explicitly parallel programs.

The motion does not carry.

Blogging from ISCA: I fell behind

I fell behind. Laptop battery died, couldn't find a plug. Session hopped. I'll write more when I get a chance.

TBD:

FutMem tutorial

HP Kauffman datacenters.

Blogging from ISCA: ACLD: Chuck Thakker, Rethinking Data Centers

Chuck Thakker invented the PC and Ethernet.

Chuck is now a post-PC person. He has no laptop. He survives with a SmartPhone. (It wasn't clear if he showed a Windows Mobile SmartPhone or an iPhone.)

Datacenters... shipping containers full of servers.

Anecdote: shipping containers were designed as a system... they succeeded where others had failed because he made them into an ISO standard.

Anecdote: SF longshoremen fought containerization of Port of SF. Oakland did not. SF is no longer a commercial port.

Container advantages:

Side to side airflow not impeded by the server case. There is no case. The container is... Loop airflow. Big impeller fans.

Shock mounting at the server, not the rack.

Aggressive ideas:

Once through water: pump through datacenter, and then on to farms.

Power distribution: reduce conversion steps.

12VDC->1VDC point of load regulators ~90%

AC->12VDC 2 stage 85%. Can do better: combined power factor correction, etc.

AC transformers 98%

Final efficiency ~80%

UPC and backup generators aren't part of the picture until the grid fails.

Datacenter close to big hydro dam => reliability. Not cost.

Now 1 phase AC to rack. Direction 3 phase AC to rack. Balance, lower ripple. 12-20VAC? Select to maximize overall efficiency.

Commodity servers: HP, Rackable, others.

Thakker: "The PC ecosystem is awful. Terrible." IBM non-x86 servers not in PC ecosystem. "Design our own..."

Custom motherboards.

Commodity disks

Cables at front

Redesign power supply

Thakker: whats ECC / checking.

Use lower power processors, notebook rather than server. (Note, opposite HP Kauffman.)

Network switches expensve. Unreliable.

Data center network:

fixed top

limited nodes

no broadcast/multicast

security simpler

load balance

design goals:

get rid of large switches

push complexity to edge

standard link technology, but not standard protocols

he likes monsoon.

short copper, long optical

2 kinds of switch: middle of rack, boundary. Both can be implemnted using Xilinx Virtex 5 FPGAs. Prototypable...

rack

boundary: 10 Gb ports, 64 copper to rack, 64 optical outside container

rack 20 1+1 Gb to servers, 2 x10Gb to container boundary switches

AFG Q: what switches are outside the containers?

route controllers. (I am not sure if those are outside the containers)

likes monsoon valiant load balancing.

boundary switches are synchronous. source routed. less packet like. long lived connections.


Objections:

Commodity hardware ... network switches to connect commodity parts NOT commodity.

...

Conclusion:

Treating data centers as systems, and do full system optimization.


Questions:

Thakker likes ATM. ATM better than Ethernet cause it doesn't lose packets. Chuck allowed to say this, since he invented Ethernet. But IP community refused to cooperate with ATM.

I asked him a question about switches outside the containers. He said, none: the datacenter is nothing except server containers and the NOC (Network Operations Center).

I asked about containers of switches. Chuck had thought, but doesn't like reliability.

Audience Q: Server computers have a 3 year lifetime. The container itself - power, cooling - can be reused - send back to manufacturer, and upgrade computers.

Compare to servers with cooling integrated: then the cooling solution lifetime is reduced to the computer electronics lifetime.

Audience Q: free air cooling. Thakker: outside air variations. (AFG: Think, winter/summer in the Dalles.) Running electronics hotter bad, reliability.

Audience Q: is power density going to increase. Thakker: microchannels, etc., bad. 8KW/rack now. Thakker doesn't think we will see 24KW/rack.

Mark Horowitz: no more than 10 cores per chip.

Blogging from ISCA: AMAS-BT: Pardo, Crusoe

Transmeta Crusoe

VLIW 5 wide

Generic simulation support

Shadowed registers, commit/abort

Gated store buffer - 32 entries x 32 bytes.

load-and-protect - like ALAT (hw trap)

x86 condition code support.

PC support - low memory steering I/O vs. DRAM. A20M. Crusoe had hardware for memory map.

Crusoe: x86 ISA support, entirely software decode.
Pardo argues that x86 decode big & power hungry.

LongRun, voltage scaling. E.g. leave CPU at 90%, mem at 100%

Shade: 100 inst/sim inst. Perf 3:1 int, 1:1 FP.

Crusoe translation: 10,000 inst/inst.

Schedulig to VLIW target harder than Shade's RISC SPARC target.

x86 reuse rates low.

Crusoe summary:

Reliability, x86ness - good

Cost: good 1/2 Intel/AMD

Power: good 1/3 Intel/AMD

Perf: umm...

Crusoe faster than low power parts, but slower than 15W laptop parts.

Compute bound, often faster at lower watts. But there aren't that many compute bound workloads.

Memory/cache traffic: slower.

Low reuse: translation overhead -> slower

Crusoe has system gotchas:

PCI graphics, not AGP.

Software DMA, not overlapped.


How to do a small project:

Automate, automamte, automate.

Reference simulator. Must be fast enough go boot OS.

Fast VLIW simulator (for host): 30 inst/sim inst. (30 I/I)

Never published?

Narrowing: Reverse execution. Cosimulation, compae. "Nexus" binary search for first divergence. => Bit 17 in register 5 is wrong in this context ... I.e. nexus = automatic bug narrowing.

Testing:

conventional, hand written

Random. Biased to interesting cases.

"Test" means "checkable". Crash => failure. Consistency check => suspicious.

AFG Q: MP non-determinism.

AFG: one nice aspect of SW DMA would be reproducibility.

Reverse HW execution in HW VLIW debugger started, no finished.

Single step trough nested fault handling. A complete debuggeris totally transparent.

Fast builds. Check in early and often.

On failure: binary search of checkins.

War stories...

CMS SW allowed working around many hardware bugs.

Not all reg resources were shadowed. Some bugs due to rolling back after non-shadowed state changed. Added rules checker to catc future bugs.

What Pardo would do differently:

Hardware was bottleneck. Changing ISA was *different* for software teams.

Big projects rules of thumb do not apply to small teams.

Better perf studies from get go. (Threw out 1st 2 CMS.)

More software inspection.

--

CMS written in C, gcc extension to provide HW access. More control.

Modest amount of assembly. Modest amount. Including modest amount of self modifying VLIW assembly code.

Not MP.

Blogging from ISCA: BIC: MATLAB, CUDA

This just a placeholder. Must take more notes for Pardo.

Blogging from ISCA: AMAS-BT: Pardo, SMC

Dave Keppel, Pardo, Google: Self Modifying Code

Everyone knows SMC is dead, but SMC is alive in the very tools that complain about it: dynamic optimizers, dynamic linkers, etc.

Pardo talks fast.

Detecting SMC via page protection. Slow if data and code in same page.

BitBLT - recomile every 10K instructions.

Debugger watchpoints. Change immediates in code.

Present in real commercial workloads.

Coherency events:

x86 - non.

Hardware instructions: ISCP "something changed". iflush addr. coherency(base,length).
Poor match between application and simulator/emulator. Need to detect what really changed.

Adaptive: default-write protect. Change strategy if too many faults. Fall back to default after a while.

Self checking strategy: check current ibytes against saved copy of original ibytes.

Pardo noted that invalidated code often reappears - thing like debugger watchpoints maychange back to original. "Revalidation". Another use for invaid cache entries.

Shade. SPARC. Iflush addr. But, there were some applications that did not use iflush, but which worked on real hardware.

Transmeta Crusoe. Subpage write protection.

"Fetch imediates" - translate code, but fetch immediates that might have been patched.

Crusoe: lots of retranslations when falling through the gears.

Deoptimized translators: fetch immediates. Translation calls interpreter.

Bad: BT leads to more implementations, more chances of bugs, reduced test coverage.

Performance stability, lack of. Consistent sometimes better than fast.

SMC/ISC. Q: what does ISC stand for?

Hardware support:

Crusoe: 2 write protect bits per page. Subpage WP cache.

Shade: 100 instructions to translate an instruction.

Gill51 - universa simulator.

Blogging from ISCA: AMAS-BT keynote

I'll be at ISCA the next few days.

Today: AMAS-BT workshop.

Antonio G. keynote.

Unfortunately, Antonio G and I share the same initials,AG. I will annotate him by Antion, me by me, or AFG.

Pollack's Rule: I suppose I should be gratified that one of my laws, perf = sqrt(power), is now widespread. I am somewhat chagrined that my old boss, Fred Pollack, has his name asociated with it. He publicized it in some keynotes.

Somehow perf=sqrt(power) has also crept in. And Antonio is multiplying the effects. This was not part of my, or Fred's, formulation. Perf=sqrt(area). We often assume that power, at least leakage, is 1:1 with area, which would imply perf=sqrt(power). But I do not think that this needs to be the case. Leakage may be negligible, and active power also seems to be proportional to sqrt(area). Or even less. This implies that perf=sqrt(active power), or less.

Antonio says that multicore => 1:1 perf increases. 2 cores => 2x parallelism. Q: is this correct? The old rule of thumb is that MP, too, perf=sqrt(#processors).

Antonio makes the EPI = Vdd**2 * Cdyn + Leakage. Handwaves leakage. Says Vdd cannot be lowered. (Me: is this true? Differential signalling?) So argues about Cdyn.

Guest ISA / Host ISA. Me: although part of the story, the real challenge is not BT fro ISA to ISA. The real challenges are (a) coming up with a host uarch and ISA that makes sense - that would make sense if compatibility was not a requirement. (b) Minimizing the cost of dynamic instrumentation and optimization.

I.e. the basic host ISA and uarch must make sense, irrespective of the guest ISA.

With an exception: possibly the host ISA is big, with lots of hint bits. The guest ISA may be small and compact. In this case, perhaps the act of binary translation itself helps. The guest ISA may be considered to be a cpmpact form of the host ISA, with just the semantics. The host ISA may be considered to be an expanded form. The host ISA may be considered to be a cache of performance annotations to the guest ISA.

Antonio: memory checkpointing. AFG comment: easier to BT single threaded or message passing programs, harder shared memory.

Antonio: adapting hardware. Resizing, power gating. AFG: hardware can do simiar adaptation. Software dynamic must have larger time constants.

Antonio: BT advantages include compatibility, both over time and across different microarchitectures (which he calls scalability). He notes that forward compatibility is especially interesting. E.g. old binaries taking advantage of new hardware features, like longer vector registers.

Pardo asked about soft real time workloads. Variability introduced by dynamic systems.