2009-05-04

and I'll teach you, teach you, teach you, I'll teach you the numeric slide

Sliding numeric scales should pretty much never show up outside of color pickers, volume controllers, and other things so (a) closely linked to sensory input that people get emotional and (b) providing such instantaneous feedback that binary search is possible without taking notes. Not that I write code with UI's, but this applies just as well to bullshit command line arguments like gzip's compression-vs-time level, oggenc's quality-vs-space level, mpd/pulseaudio's sampling-vs-cpu level, and gcc's optimization-vs-everything turkey shoot of -O and -f options.

If gcc had broken tradition with past compilers (Cray and SGI compilers I've known supported a gamut of -O levels beyond -O3, and surely a surfeit of others as well), and called...actually, I guess I give compilers a pass here: you don't want to throw crap like --optimize-space into a compilation line, due to iterated consumption of terminal real estate during a build. Exactly as -Os (optimize for space on gcc) indicates, you'd end up with a series of difficult-to-remember flags, ala the -Q options on Intel's icc c++ compiler (then again, how often need you remember optimization flags outside makefile creation?) I think, however, that the generated-code-speed vs. compilation-time tradeoff will slide (has already slid?) in importance, and the competing axes of compilation decisions -- power-vs-performance, codespace-vs-codecycles, parallelism-vs-fastserial, all that -- will render a single vector meaningless. At this point, you'll need even more rely on descriptions of processing environments and architectures, and almost certainly parameterize on them at runtime.

Let's remove the optimization level decision, aside from as a debugging aid, from the realm of the code's creators and to the code's executers. It'd be a win all around.

Oh, to complete an earlier thought: if -O0..-O9 had never been introduced, I wouldn't have to listen to someone say "I think it ran faster with -O4 than -O2", and tell them "uhhh, gcc on x86 has never meaningfully supported an optimization level higher than -O3." This happens every few years, and it typically results in a bad scene. I'd like to bring out rms ala Annie Hall: "I heard, I heard what you were saying. You, you know nothing of my work. How you ever were hired to write any kind of code is totally amazing." Tyro assholes!

2009-05-03

mother of god

Holy crap, blogger sucks like three bitches in a bitch boat! No threaded comments? What is this, the time of Charlemange? I tried to respond to Leon twice (the missing context, btw, was LU decomposition for solving matrix problems), and both posts were dispatched into the ether. So, we might soon take flight to a more reasonable format.

2009-05-02

totalwonkerr gone??!

[oh yeah, i've just decided that in addition to computers, this blog will talk about nuclear weapons, because they're just as interesting, and I hope to do national lab work at some point]

So I'm in g-reader and notice new TotalWonKerr posts -- hurrah! time to catch up on the world of strategic weapons after finals! oh, hurrah, a phatty new OTA report on SLV's -- and follow through to http://totalwonkerr.com...

This weblog has been taken offline by request. 4/24/2009.

wtf? from the g-cache:
Paul Kerr used to work for the Arms Control Association. Josh Pollack is a consultant specializing in arms control, proliferation, and deterrence issues.
By far my second-favorite nucarms blog, after the inimitable ArmsControlWonk. Lots of good references to original sources, placed handily on his page (as opposed to government links, which so regularly get pulled offline). Where are you, Paul?

In any case, I've downloaded and archived -- so far, at least, as I know -- all the files he's linked. I'll put them up, once I verify he didn't get into trouble or something.

computer scientist trading card 2/32

Today we have an early hero of mine, Dawson Engler of MIT, Stanford and now Coverity. Professor Engler's magic/xgcc project was an awesome feat, one of the coolest tools I've ever seen (or at least, seen its output -- the project was never released, and presumably formed the base of Coverity's armamentarium), and served the open source community well with its discovery of flaws in the Linux kernel and other large code bases (the open source community, of course, helped out by correcting magic's many errors and assisting in its refinement).

Allegations that Coverity's "patented analysis" is actually a ruthlessly managed legion of teenage Ukranian programmers, raised on pure rainwater, grain alcohol, methamphetamines and steroid shakes in sweatshop conditions have been denied as "baseless conjecture and libel" by Coverity officials, but that's what you get for not opening your code.

2009-05-01

at long last, a line of puerile computer scientist trading cards


let's try this again, players. btw, while i admire spunk, the traditional means of communicating disagreement is a reasonable letter to the editor.

chaitin's book

If you've never had the pleasure of reading G. J. Chaitin, the Algorithmic Information Theory text I referenced is freely available. Thanks a lot, Professor Chaitin! This kind of thing is really appreciated, simply because a pdf can be searched.

automatic extraction of parallelism

[Be forewarned: I'm about to appeal to a number of fields I don't know in much depth. Experts might find one suggestion or another bewildering. As opposed to spending much time trying to figure out what I mean, you can likely assume it to be gibberish -- assuming you're indeed a suitable expert, and not just a jackass.]

I have been marinating on this today, putting on my algorithmic information theory hat following the semester's close. As it turned out, PLD and automated theorem proving hats were also needed.

Think of decompositions as a language to be recognized by some turing machine. We have all the decidable languages at our disposal; can dependence-free decomposition be described by a DL?

An hour's review of the research suggests that:
  1. there's a ton of PLD research into this at a formal languages / program transformation standpoint. most of it makes use of toy languages that'll work great for half a page examples in some obscure journal. LogP is a great example of this kind of thing.
  2. from a dynamics standpoint, you have hoare and milner and all that hoary old communicating processes stuff. it's a great mathematical description of processes as they're running but not applicable, or at least not applied, to program analysis. deriving a milner system or any other pi-calculus description from program text seems a nonstarter in the Entscheidungsproblem sense
  3. quentin stout's seminal busy beaver work seems a great place to start putting the nails in any behavioral analysis argument and thus also anything involving "so we start simulating...." nosir, no we don't
  4. EXPTIME is a class not very well known outside the complexity and AI communities, but a reduction to this class would work for our purposes. Yu Ding's work on description logic satisfiability could be a good starting point.
  5. so let's turn to the AIT folks (this gets a bit esoteric). i've read chaitin's book, and it doesn't have anything really relevant, save all the mathematical tools necessary for talking about program size. how far can we push Chaitin's arithmetization process? this is for data- and not task-based parallelism. can we reduce to some Kolmolgorov description and pair it with some number theory / analysis (think Banerjee's Inequality) to isolate information-theoretic chunks of parallelism?
  6. yeah, heuristics (ala the FFTW paper and countless others). pretty much anything with heuristics is kinda lame IMHO, because the underlying assumptions change more quickly than the code. a spiritual dead end.
The problem seems sorely in need of really firm theoretical underpinnings. A good place to start: 2006's "Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws." The miles between AIT's current state and the power we'd need to do anything interesting suggest that (a) there's fundamental results to be had for the taking here and (b) it'll be tough.

What would be just as useful, theoretically, is determining that AIT models *can't* address certain parallelisms, or at a more fundamental level that some decomposition languages can't be described by a type-0 Chomsky grammar. Of course, what we really want is to find a suitable DL, or preferably a parameterized set of such languages generated from a description, in some operator syntax, because then we could *apply* it.

Operator syntaxes! If we can decompose a program into, say, primitive recursive functions and SSA -- well, from Chaitin we already know changes that can be made assuming exponential time. Thus, we don't need a decidable language for the source; we could merely recognize safe and parallel transformations of said IR, if we had a language for THOSE, and rather than try to solve HOW to do it just start testing structured or random transformations upon the source!

To be more practical, you of course can't EXPTIME-ly generate all modifications within a finite distance, but I bet randomized methods could be used to find (with a high degree of probability) any "seed points" with a spark of parallelism, the local space around which more targeted (possibly genetic?) algorithms could search. Think of them as jeweled raindrops of parallelism forming in our stormy, branch-heavy cloud of code.

Either way, recognizing transformations as opposed to recognizing source patterns could be a very key insight here. I should go talk to Prof. Lipton, who ran one hell of a Randomized Algorithms class this semester.

Holla with your thoughts!