Re: [Way OT] Spacetime analysis of parallel algorithms [Was: Re:

On 2009-06-27, Victor Eijkhout <see@xxxxxxxxxxxxxxx> wrote:
Garamond Lethe <cartographical@xxxxxxxxx> wrote:

1. Yes, I'm unaware of the paper. It was written in 1988 and has been
cited five times.

I always thought it was a fun result.

Very much so.


2. Give me some context to work with here. Why did you think this paper
was relevant to the discussion on whether or not Computer Science is
science?

It was mostly a response to one paper you quoted. Both seem good
examples of theoretical results that still respect practical
restrictions.

3. What does log complexity have to do with any of this?

That your LogP paper, despite being fairly realistic, still has formulas
showing logarithmic complexity,


DOH!

Thank you.

That paper has informed quite a bit of my work, but while I internalized
the model I completely forgot the fact that they also did some complexity
work. Thanks for pointing that out --- your comment now makes a great
deal more sense. (It also points out the title was probably supposed to
be a pun, which I had also never picked up until now.)

Now that I've skimmed the first two sections of the paper, I see that
they're doing a neat trick by mapping computation and communication
onto a hypercylinder and using that to bound algorithmic complexity.

Nice, eh? Shows that speed up is asympotically bounded because of the
number of space dimensions. Not that this fact ever shows up in
practice. The asymptote is always somewhere on the horizon.


Very, very cool.

Victor.

.

Relevant Pages

  • Re: 6502s and Symbol Tables
    ... Knuth's work is the "Principia Mathematica" of computer science; ... that complexity has for actual performance. ... The rules for computer performance have changed radically from the ... by transistors and gate delays, but by wiring delays and, ultimately, ...
    (comp.sys.apple2.programmer)
  • Re: Programming languages and math
    ... >having them lead the development of computer science we got programming ... I feel addressed because I'm a math person by character, ... In my opinion we would have gotten nowhere, neither in physics ... I guess having a culture that reveres complexity ...
    (comp.lang.forth)
  • Re: Are there any non-gifted scientists?!?!?
    ... >> computability (eg. Turing machines, halting problem, etc.), complexity ... >> constitute the basic areas of computer science. ... >That's just mathematics with a paintjob. ...
    (comp.theory)
  • Re: Are there any non-gifted scientists?!?!?
    ... >>computability, complexity ... >>constitute the basic areas of computer science. ... > That's just mathematics with a paintjob. ... programming languages are based on formal language theory which is ...
    (comp.theory)
  • Re: How do you feel ?
    ... > I have beebn coding with different languages and the only that has given ... > me not to focus on the complexity of the language itself. ... It's a lot of fun, rewarding, often giving instant gratification. ... online tutorials are very basic, and online reference is hard to ...
    (comp.lang.python)