Path: utzoo!yunexus!maccs!nusip From: nusip@maccs.McMaster.CA (Mike Borza) Newsgroups: comp.arch Subject: Re: getting rid of branches Message-ID: <1282@maccs.McMaster.CA> Date: 2 Jul 88 17:09:03 GMT Article-I.D.: maccs.1282 References: <1941@pt.cs.cmu.edu> <3208@ubc-cs.UUCP> <1986@pt.cs.cmu.edu> <91odrecXKL1010YEOek@amdahl.uts.amdahl.com> <12258@mimsy.UUCP> Reply-To: nusip@maccs.UUCP (Mike Borza) Organization: McMaster U., Hamilton, Ont., Can. Lines: 29 In article <12258@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >In article <91odrecXKL1010YEOek@amdahl.uts.amdahl.com> >chuck@amdahl.uts.amdahl.com (Charles Simmons) writes: >>You guys aren't thinking big enough. How about multiple parallel >>pipelines to compute all the various instruction threads in parallel >>and just keep the results of the one that is actually taken? > >Actually, this sort of idea is contained in some research and thesis >work that is (was?) going on here at Maryland. How do you move old I was at a talk given by A.K. Dewdney some time ago, about non-deterministic programming languages. The jist of these languages was exactly what you're talking about. At the outset, all possible outcomes of a particular computation are accounted for, then a selection criterion is applied to accept or reject particular outcomes. Lots of interesting possibilities and problems here. One of the most interesting features is that whole classes of possible solutions can be selected, rather than a single solution. I think this leads to a very natural way to program some problems which are very difficult in more traditional approaches. Global optimization of the route-and-place problem in VLSI and PCB design is a good example. We're starting to see the emergence of architectures which address these sorts of ideas in things like the Connection Machine. Of course, exponential explosion of the state space does appear to be something of a problem :-) mike borza