From: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Subject: Re: Resource control (was: Re: Why curry?)
Reply-To: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Organization: Royal Institute of Technology, Stockholm, Sweden
Date: Mon, 12 Oct 1992 15:00:18 GMT

In article <TMB.92Oct10173521@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
|> In article <1992Oct8.124228.10449@kth.se> kff@dentex.tds.kth.se (Karl-Filip Faxen) writes:

|> >And it is precisely why I like it. I believe that the "creative" part
|> >of an algorithm is specifying the data dependencies. Then a good
|> >compiler should be able to come up with an evaluation order that is at
|> >least as efficient in terms of resource (eg memory) consumption,
|> >locality and (when the machine can take advantage of it) parallelism,
|> >as any I could come up with myself with a reasonable amount of work.
|> 
|> Well, then don't hold your breath for "good compilers". Decisions like
|> these are input data dependent 

Yes, sometimes.

|> and/or require a significant understanding of the meaning of the 
|> algorithm you are implementing.

No, they require a significant understanding of the data dependencies
in the algorithm and the kind of schedules that these admit.

|> A compiler has neither, 

I agree.

|> nor can it.

I disagree.

(1) A compiler has no knowledge about input data (except for their
    type). If the programmer has this knowledge, it can be communicated
    to the compiler using annotations, or can be studied with profiling.
    This of course requires access to "typical input", a somewhat shakey
    notion, but no less shakey than the programmers intuition. Also,
    the compiler could generate code for run-time scheduling in some 
    cases.

(2) Understanding of data dependencies and schedules. What is lacking
    here is a language in which to talk about data dependencies and
    schedules of lazy functional languages. In the case of Fortran,
    most of the computation is done with loops and arrays and there is
    a lot of work done on formalizing data dependencies involving these
    structures (e.g. dependece vectors and loop interchange operations
    as well as space-time scheduling methods). In the case of functional
    languages, we need ways to describe dependencies involving recursively
    defined functions and user defined algebraic datatypes, as well as a
    language in which to talk about schedules of recursively defined 
    functions.

|> I find it easier to state in advance what I know about my algorithm.

To be fair, there are cases were an algorithm is crafted so that its data
dependencies will admit a certain schedule, and in those cases it should
be possible to tell the compiler which schedule to use. But even then, 
the same schedule might not be optimal for different machines, with 
different number of processors and differently organized memory hierarchies.

|>    It may be that annotations are a good idea, separating data dependencies
|>    from resource management decisions.
|> 
|> Well, yes. And taking advantage of eager evaluation for these kinds of
|> "annotations" seems to be quite natural. Why change this?

Here, I'm afraid I don't understand what you want to say. Could you please
rephrase it? 

Cheers,
         Karl-Filip

------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!