Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!rochester!PT!k.gp.cs.cmu.edu!lindsay
From: lindsay@k.gp.cs.cmu.edu.UUCP
Newsgroups: comp.arch
Subject: Re: VLIW
Message-ID: <1232@k.gp.cs.cmu.edu>
Date: Thu, 17-Sep-87 17:37:36 EDT
Article-I.D.: k.1232
Posted: Thu Sep 17 17:37:36 1987
Date-Received: Sat, 19-Sep-87 09:49:29 EDT
References: <4782@sdcrdcf.UUCP> <475@esunix.UUCP> <347@erc3ba.UUCP> <1941@encore.UUCP>
Organization: Carnegie-Mellon University, CS/RI
Lines: 30
Keywords: Multiflow, trace scheduling, VLIW


Yes, trace scheduling is a useful technique on non-VLIW machines.

To recap: the basic trick is to eliminate constraints from the precedence
graph, by placing fixup code on paths which are thought to be less likely.
For example: 
	if(a) then { x; b } else c;
might become
	x; if(a) then b else { undo-x; c };

A VLIW machine does this because you can't "schedule" two ops into the
same large instruction word if one is constrained to be before/after the
other.

On more normal machines, scheduling still has wins. Anyone with a floating
point coprocessor can try for integer/float overlap. The MIPS cpu can be
scheduled. Crays have multiple functional units: they can be scheduled
because opcodes are issued faster than functions complete.  Other vector
machines, such the Alliant, have scheduling.

So, the trace scheduling method can be used to improve the scheduling on
all of these. The win is basically that the machine's average throughput
gets nearer the peak throughput. If your application is already peaked,
then you don't need to know.

The Multiflow machine can do branch logic in every instruction,
so they hope to do "junk code" better than anyone else. Supposedly
their Unix is quite quick: I will try to get some numbers.
-- 
	Don		lindsay@k.gp.cs.cmu.edu    CMU Computer Science