Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!stanford.edu!neon.Stanford.EDU!DEC-Lite.Stanford.EDU!andy
From: andy@DEC-Lite.Stanford.EDU (Andy Freeman)
Newsgroups: comp.arch
Subject: Re: More on Linpack pivoting: isamax and instruction set design
Message-ID: <1991Jun13.234834.22970@neon.Stanford.EDU>
Date: 13 Jun 91 23:48:34 GMT
References: <396@validgh.com>
Sender: news@neon.Stanford.EDU (USENET News System)
Organization: Computer Science Department, Stanford University
Lines: 33

In article <396@validgh.com> dgh@validgh.com (David G. Hough on validgh) writes:
>      do 30 i = 2,n
>         if(abs(dx(i)).le.dmax) go to 30
>         isamax = i
>         dmax = abs(dx(i))
>   30 continue

One instruction that can eliminate the conditional branch is
conditional assignment.  (It is unclear whether it should be a 3 in 1
out operation or a 2 in 1 out operation with the destination as an
implicit operand.)  In the above, it can be used like:

	isamax = 1
	dmax = abs(dx(1))
	do 30 i = 2, n
	    absdx = abs(dx(i))
	    ibig  = absdx .le. dmax
	    asm("<if ibig is true, replace isamax's value with i>")
	    asm("<if ibig is true, replace dmax's value with absdx>")
    30	continue

Obviously one can pipeline the abs.  The delay caused by the
loop-carried dependence can be eliminated by unrolling (or recursive
doubling) and computing separate values of ibig and dmax for different
sections of the array.

One has to be careful with this, as branch-prediction might hide the
branch penalty associated with the original version.

-andy
--
UUCP:    {arpa gateways, sun, decwrl, uunet, rutgers}!neon.stanford.edu!andy
ARPA:    andy@neon.stanford.edu