Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!p.cs.uiuc.edu!gillies From: gillies@p.cs.uiuc.edu Newsgroups: comp.arch Subject: Re: quest for breakthroughs (long) Message-ID: <76700063@p.cs.uiuc.edu> Date: 14 Feb 89 06:14:00 GMT References: <740@tetons.UUCP> Lines: 52 Nf-ID: #R:tetons.UUCP:740:p.cs.uiuc.edu:76700063:000:2050 Nf-From: p.cs.uiuc.edu!gillies Feb 14 00:14:00 1989 O.k., here is an idea, perhaps based on a fallacy ----- "Currently, the quality of the code from several commercial compilers and hand-optimization for the same machine (e.g. 68000) might vary tremendously. The best (compiled or hand-optimized) code might easily be X (X >= 10?) times faster than the worst. What is this constant X, for most commercial compilers? Why do compilers vary so much? Clearly, reducing X bootstraps the performance of *all* compilers/architectures. Here's a plan: 1. Discover X 2. Discover the three contributors to X with the most variance. For example, here are 6 possible contributors to X (PLEASE NO FLAMES THESE ARE IMAGINARY REASONS) (1) Most compilers do poor register scheduling. (2) The architecture is so (a) non-orthogonal? => compiler optimization is too hard (b) orthogonal? => simple implementations are microcoded & slow (c) powerful? => combinatorial search is necessary to discover optimal code sequences (3) Most compiler writers don't (a) have enough time (b) have enough knowledge / experience .... Of these, reason (1) might have a variance of 1.5, reason 2(a) might result in a variance of 2.0, 3(b) might be 4.0, etc. 3. Propose a technical solution for the top-3 contributers to the variance of X. ------------------------------------------------------------ Also, I've always wondered if we could design a simple architecture + language, from a theoretical standpoint, for which provably optimal code could be generated. At the moment this problem is ill-defined and requires a lot of formulation. You can perhaps start with some ultra-simple architecture (Turing Machine), and simple language (Turing Machine Language), and try abstracting the two farther apart to see how far you can get. This problem is not for the faint-hearted. Don Gillies, Dept. of Computer Science, University of Illinois 1304 W. Springfield, Urbana, Ill 61801 ARPA: gillies@cs.uiuc.edu UUCP: {uunet,harvard}!uiucdcs!gillies