Path: utzoo!attcan!uunet!husc6!uwvax!dogie!uwmcsd1!ig!agate!ucbvax!decwrl!labrea!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.arch
Subject: Re: m88000 benchmarks
Message-ID: <754@garth.UUCP>
Date: 18 Jun 88 20:38:57 GMT
References: <1941@pt.cs.cmu.edu> <3208@ubc-cs.UUCP> <1986@pt.cs.cmu.edu>
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 21

>Viewed from a distance, an 88000 scheduler looks quite simple: the "machine
>model" isn't too complex, and the interface (machine code in, machine code
>out) is straightforward. Viewed close up, I'm sure that the implementers
>have hit some kind of grief: a problem with register lifetimes and live
>sets: or, problems with labels and directives: or just suboptimal results
>on the biggest customer's favorite benchmark.

The problem with writing a scheduler is finding an efficient (read: heuristic)
method of traversing the code graph. The simplest method produces the best code
at exponential compilation time: try every possible sequence. The grief is
trying to find a linear to quadratic time method which still gives a good
sequence.

We humans seem to have innate ability to find the best graph traversal (or
perhaps we are not overwhelmed until the graph becomes large), so human
experts will continue outcode compilers for the near future.

                                             sm ryan

            Nature is immacuately fair and implacably cruel.
                                 -- Sara James