Dynamic Instruction Rewriting

http://semipublic.comp-arch.net/wiki/Dynamic_instruction_rewriting

[[Dynamic instruction rewriting]] is a microarchitecture optimization that I, Andy Glew, came up with while I was a student at the University of Wisconsin, 1996-2000.
Undoubtedly others have had similar ideas:
I know for sure after (TBD, publication)
and suspect before.
I will describe my version here (TBD add and compare other versions).

I often refer to this optimization as simply [[flattening]], since that it what it doesto the dataflow graph. [[Dynamic instruction rewriting]] was  one of several optimizations I grouped as [[instruction refinement]] for  the PhD I never completed.

[[Dynamic instruction rewriting]] does what it says - it rewrites instructions,
in particular, flattening the dataflow graph of a computation,
in hardware.
It does this much as a compiler would do, but goes beyond a compiler's capabilities in that it performs these optimizations across basic blocks, procedures,
infrequently taken branches, and other boundaries that might impede a compiler based optimization.
(In this, I also include [["compiler-like optimizations" performed inside the instruction cache]].)

My flavour of [[dynamic instruction rewriting]] is based on letting instructions flow around a microarchitecture much as values might.

It can be performed in several places in the pipeline,
in particular in the   instruction renaming pipestage,
and/or in actual execution.
Also possibly as a [[post-retirement optimization]].

The quintessential example [[dynamic instruction rewriting]] is this:
imagine an instruction sequence that increments a register.
(Actually, we will change  the registers for didactic purposes, as might happen with simple loop unrolling.)
   ...
   r2 := r1 + 1
   ...
   r1 := r2 + 1
   ...
   r2 := r1 + 1
   ...

Let us discuss the renamer pipestage optimization.

The renamer or map pipestage has a table indexed by logical register number.
In a simple in-orrder scoreboarded machine, the entries of this table may be  single bity indicating whether a register value is ready or not;
in a P6 or [[HaRRM]] style machine, the entries of this table may also contain physical register numbers that the logical registers are mapped to, which are scheduled later;
in a [[future file]] or [[active register file]], the actual values may also be in this table.

In renamer pipestage [[dynamic register rewriting]], the  table also includes  the instruction, the actual instruction, that writes the result.
Or at least a subsert thereof (the subset that can be optimized in this manner).

Considering the above code sequence, let us indicate the value of a P6 or [[HaRRM]] style register renamer, mapping logical to physical register numbers
The actual physical register numbers do not matter, and could be random - whatever preg is free next.
      
   ...
     r1 -> pr11
     r2 -> pr22
   r2 := r1 + 1
     r1 -> pr11
     r2 -> pr33
   ...
   r1 := r2 + 1
     r1 -> pr44
     r2 -> pr33
   ...
   r2 := r1 + 1
     r1 -> pr44
     r2 -> pr55
   ...

Now let us augment with the actual instruction producing the result - but without performing the optimization


   ...
     r1 -> pr11
     r2 -> pr22
   r2 := r1 + 1
     r1 -> pr11  
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r1 := r2 + 1
     r1 -> pr44   pr44 := pr33 + 1
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r2 := r1 + 1
     r1 -> pr44   pr44 := pr33 + 1
     r2 -> pr55   pr55 := pr44 + 1

Now let us imagine that renamer logic is enabled to substitute the input "value" of a register - the instruction - in its ouutput expression

   ...
     r1 -> pr11
     r2 -> pr22
   r2 := r1 + 1
     r1 -> pr11  
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r1 := r2 + 1
     r1 -> pr44   pr44 := pr33 + 1 == (pr11 + 1) + 1
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r2 := r1 + 1
     r1 -> pr44   pr44 := pr33 + 1
     r2 -> pr55   pr55 := pr44 + 1

When the [[dynamic instruction rewriting]] logic sees a value of tyhe form
   (pr11 + 1) + 1
it performs the associative and commutative transformations, to produce optimizations
   => pr11 + 1 + 1
   => pr11 + 2

and overall

   ...
     r1 -> pr11
     r2 -> pr22
   r2 := r1 + 1
     r1 -> pr11  
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r1 := r2 + 1
     r1 -> pr44   pr44 := pr33 + 1 == (pr11 + 1) + 1 == pr11 + 2
     r2 -> pr33   pr33 := pr11 + 1
   ...
   r2 := r1 + 1
     r1 -> pr44   pr44 := pr33 + 1 == pr11+2
     r2 -> pr55   pr55 := pr44 + 1 == pr11+3

and so on.


Actually, nothing in the above description depends on the [[dynamic instruction rewriting]] logic being in the renamer pipestage.

If it is in the renamer pipestage, and there is no additional delay for the optimization, we would never see a multi-stage transformation
  pr55:=pr44+1 == (pr33+1)+1 == ((pr11+2)+1) == pr11+3
i.e. if the [[dynamic instruction rewriting]] logic at the  renamer pipestage were fast enough, only the optimized version would propagate.


However, if the [[dynamic instruction rewriting]] logic were in the out-of-order execution system, we might see such multistage  transformations.
(Also, if renamer pipestage logic had a delay.)

Indeed, we might place unrewritten instructions into the out-of-order scheduler,
and trigger a rewrite when one of the operands arrives
- but not the other, without waiting for the second  or other operands to arrive.
I.e. this  [[dynamic instruction rewriting optimization]] can take advantage of [[operand inter-arrival time skew]],
indeed, of [[dynamic operand inter-arrival time skew]], when the operand arrival times cannot be estimated in advance.

(Another  class of optimizations can be performed when you can estimate [[operand inter-arrival time skew]].)

Consider
    ...
    r1 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    r2 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    r3 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    r4 := r1 + r2
    r5 := r4 + r3
    ...

Let all of these operations be  placed  into an out-of-order scheduler.
(The renamer for this is trivial.)

Now let us assume that the r3 load completes early, r3:=C

    ...
    r1 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    r2 := load ( ... ) // cache  miss, unpredicataly randomized arrival time
    COMPLETE C <= r3 := load ( ... ) // cache  miss, unpredicatably randomized arrival time
    r4 := r1 + r2
    r5 := r4 + (r3=C)
    ...

Now let us assume that the r2 load completes early, r2:=B

    ...
    r1 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    COMPLETE B <= r2 := load ( ... ) // cache  miss, unpredicataly randomized arrival time
    COMPLETE C <= r3 := load ( ... ) // cache  miss, unpredicatably randomized arrival time
    r4 := r1 + (r2=B)
    r5 := r4 + (r3=C)
    ...

Then let us "fire" the partially complete instruction
    r4 := r1 + (r2=B)
producing


    ...
    r1 := load ( ... ) // cache  miss, unpredictably randomized arrival time
    COMPLETE B <= r2 := load ( ... ) // cache  miss, unpredicataly randomized arrival time
    COMPLETE C <= r3 := load ( ... ) // cache  miss, unpredicatably randomized arrival time
    r4 := r1 + (r2=B)
    r5 := r4 + (r3=C) == (r4=(r1+(r2=B))+(r3=C))== r1 + (B+C)
    ...

where B+C is a constant that can be evaluated, and written into the  scheduler entry for r5:=.

Therefore, when r1 completes, both
   r4 := r1 + B
and
   r5 := r1 + (B+C)
can be evaluated in dataflow graph depth 1 - rather than the two if not rewritten.

Grr...

I just deleted a blog entry I had been writing for an hour or so. Blogger has a "save" button, which l was using -but when I Lit the refresh button, because I Lad rotated my screen and I wanted the text box to fit, I lost everything.

 Grrr....

 I go now to find the text box backup plugin I use at work.

Flying Tablet

Flying today once again demonstrates the advantage of a pen-based tablet PC. The seats are just too close to open my convertible tablet PC in clamshell/notebook mode so I can use the keyboard to type. And, even though I have three seats next to each other all to myself, twisting sideways to use the PC keyboard in clamshell mode is too much of a pain. Especially since turbulence was producing a lot of typing errors.

But using it in slate mode works fine. interestingly, I normally use cursive, as I am doing now, for handwriting input. But, earlier, when the turbulence was bad, I found that the letter "comb" was less sensitive to turbulence induced errors.

 --

 Sometimes I fear that I am the only person in the world to like handwriting. yesterday shopped for a new cellulose and/or tablet. First time I actually held a Dell Streak, the 5" phone. I quite like the size _ it fit in mf pocket _ but the device B show, with slow wireless, a slow processor, and an old version of Android. I quite liked the Samsung Galaxy, and I actually used its on-screen touch keyboard to enter a page on my comp-arch.net wiki. I quite wish it cou\d be used as a phone, just to avoid having to pay for another dataplan. I am considering getting the tablet and going with a cheap non-smart phone.

Https not everywhere sucks

Woke up this morning with a little idea wrt an FPGA fun hacking project.
Wrote it up.
Wanted to post on my private wiki, but instead posted on Google sites
https://sites.google.com/site/glewprivate/fpga-processor-isa--uarch-hacking.

Why?  I hate Google sites.  But Google sites uses https/SSL.  Whereas, my privae wiki does not have https/SSL.

Why not?  because my web hoster, Dreamhosts, requires a fixed IP for SSL.  And I have only paid extra for two domains to have the fixed IP and SSL.  Not the domain that hosts my private wiki.

Why not host my private wiki on one of my two fixed IP https/SSL domains?   Because dreamhost only supports, by default, one UNIX (Linux) user ID per such domain.  So all of the websites on such a domain are vulnerable to each other.

I'm moving towards fixing this, with my own virtual private server, so I can set up setuid CGI.  Mainly, haven't gotten around to setting that up yet.   But, also, doing so loses me the automatic updates that dreamhost provides.

Why do I care about https/SSL?  I really should not need to answer this, but...  In particular, this morning I'm at a motel.  I can assume that bad guys may be monitoring all of my traffic that is not encrypted.  No VPN.  Hence, want to use https/SSL for anything that needs a password.

Why no VPN?  A1: can't use work VPN, personal.  A2: haven't paid for personal VPN server.  But, in any case, a VPN server would only encrypt from my tablet across the motel wifi to the VPN server somewhere in the net.  From there, it would be unencrypted if, e.g., using plain old http.  VPN helps, but really need end to end encryption, such as https/SSL give.

Bottom line: this morning decided to use Google sites, even though I hate it, because it offers https/SSL.  Could have used Google docs, similar.

Hmm...   Google's www.blogger.com, which I am using now, doesn't seem to use https.    Doesn't this make blogging vulnerable?   Isn't the rule that everything  password protected needs to be encrypted - or at least the cookies carrying the authentication need to be.  Not just the login, but all authorizing?

Personal To Do:

1) Set up setuid cgi asap

2) install whatever wiki I care about - and move my wiki

3) keep playing with virtual server apache

Monitor/Mwait

http://semipublic.comp-arch.net/wiki/Monitor-Mwait


= Monitor/Mwait =

Monitor/Mwait are a pair of instructions introduced as follows:

 What: Monitor/Mwait
 Where: Intel x86 PNI SSE3
 When: 2004 Prescott

Brief description from [[Instruction_Set_Extensions,_a_Rough_History#Monitor-Mwait]]

Originally intended to be used for fast thread synchronization, to implement "Wait until a memory location has changed" (or "may have" changed, since might exit the wait when cache line evicted but variable unchanged). Really, what people want is a cheap way to "wait until condition on memvar is met",  but we implement by spinning and reevaluating the condition, blocking as efficiently as possible to reduce as many spins as possible. "Hardware Event Driven" The Monitor part necessary to handle race conditions in such loops. Unfortunately, Monitor/Mwait had problems that resulted in them not being used outside the OS.  MWAIT became a power management instruction, saying to enter a power management state like C3 or C4.

Let's discuss in more detail - not just monitor/mwait, but the class of synchronization operations that these are an exampleof.

== The Ideal: Monitor a Datastructure in Memory ==

What people, at least naive programmers, want to do is to be able to monitor arbitrary datastructures in memory
* arbitrary datastructures,
* involving arbitrary numbers of memory locations 9some of which are contingent, e.g. linked lists)
* evaluating arbitrary conditions.

I.e. people want to do something like

 WAIT UNTIL
   arbitrary condition on arbitrary datastructure(s)

or

 SIGNAL EVENT WHEN
   arbitrary condition on arbitrary datastructure(s)

Note the two forms: the first synchronous, the second interrupt or event handler based.

E.g. something like
 WAIT UNTIL
   there are 500 elements on the run queue

or
 WAIT UNTIL
   the B tree is unbalanced by more than 2X

; Transactions

Note a first issue:  monitoring an arbitrary datastructure in memory may be hard to do, if the datastructure is constantly being updated, relinked, etc.
The programmer really wants to monitor this transactionally.
Later we will return to this issue inspired by hardware or software transactional memory techniques.
To start off with, however, we will retreat, past multiple memory locations known a-priori (non contingent),
all the way to monitoring a single memory location.

== Incremental Monitoring ==

First, let's get the easy part out of the way:  many such monitoring conditions can be handled by having any code that changes the datastructure evaluate the condition,
and invoke the handler.

E.g.
   insert onto queue( Q, el )
       ...
       if( Q.size > 500 ) call handler_for_queue_gt_500

This works for single threaded code.

It even works for multithreaded code - the handler on one thread may set a shared variable or signal other threads. In many ways, monitor/mwait devolves into how to perform such cross thread notification easily.

It doesn't work when you can't modify or extend the existing code.

E.g. a debugger attempting to evaluate such a condition.  However, a debugger is such a special case.

Note that it is usually not necessary to evaluate the whole of a complicated condition on a datastructure.  Depending on what has recently happeneed in the modifying code, specialization or early out.

So, let's just get this out of the way, and assume that we still want to do monitor/mwait or the equivalent, between threads, at least on a single variable.

== Monitor/Mwait ==

Restricting ourselves to a single memory location,
we want to evaluate an arbitrary condition on that single memory location.

E.g.

    LOOP
       tmpReg := load( memLoc )
       if( arbitrary_condition(tmpReg) then exit loop
    END LOOP

E.g. specific:

    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
    END LOOP

The example condition is chosen to be one that is unlikely to be hardwired. In reality, the conditions are usually simpler, such as tmpReg == 0 or -1, etc., which raises the possibility odf hardwiring the condition. With the usual issue of what hardwired conditions should be supported.

Such a loop is semantically "good enough" (so long as the programmer understands that the condition may have been changed by another thread immediately thereafter, e.g.
even before the loop exits; and so long as there is no need for an operation such as if zero then set to 1 that needs to be atomic.

However, such a spin loop can cause unnecessary bus traffic, waste power, etc.
so, what we are looking for with monitor/mwait is a way of (a) saving power, by blocking the spinloop, and (b) possibly allowing the operation to be exported.
The former, (a), is the main story behind monitor/mwait.
The latter, (b), may be considered an advanced topic.

Simply adding a pause inside the loop is considered unacceptable, since it adds latency to detecting the change:

    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
       sleep for time T
    END LOOP

What we want is a way of monitoring the memory location to see if anything has changed.
In a MESI cache protocol, it is sufficient to obtain exclusive ownership of a cache line.
If the cache line is written by another processor, the local processor loses ownership,
and the condition can be re-evaluated:


    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
       mwait( memLoc ) - wait until another processor may have written the cache line
    END LOOP

However, because the condition may initially be true, etc., the mwait is accompanied by a monitor outside the loop:

    MONITOR(memLoc)
    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
       MWAIT( memLoc ) - wait until another processor may have written the cache line
    END LOOP

Note  that I say "may have",
in "wait until another processor may have written the cache line".
The MWAIT typically unblocks when the cache line in question has been written,
or at least ownership has been transferred so that it may have been written.
But it will also unblock when the cacheline has been thrashed out (e.g. by another thread, if the monitpr mechanism is implemennted in the cache linees, and not via a dedicated monitor reghister),
or after a context switch to another processor,
or after going into a low power mode for a while;
... essntially, whenever you can no longer guarantee that the value has changed.

I.e. it is not monitoring changes; it is monitoring for lack of change, and blocking while lack of change is guaranteed.

== Monitor/Mwait and LL/SC ==

Monitor/Mwait are similar to load-linked/store-conditional
- the so-called RISC form of atomic synchronization,
that only works in systems with caches, at the processor,
which does not [[exporting synchronization operations]].

My tone of voice indicates my attitude:
M/MW, like LL/SC, is limited.
It will not work in all circumstances, neither at the low end nor at the upper end.
however, it may be a point of time solution.

For the most future-proof instruction set
just as I advocate wrapping LL/SC inside instructions such as "atomic increment memory location",
I advocate using M/MW as an implementation mechanism for possible instructions such as
* Wait until memory location is nonzero

Indeed, IBM's virtual machie experience has shown us that it is desirable to identify all sorts
of spinloops to the hardware or VMM, for virtual machines or otherwise.
(This warrants a discussion of it's own - [[encapsulating or advising spinloops]].)

== Climbing Back Up ==

Now that we have single location monitor/mwait spinloops:

    MONITOR(memLoc)
    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
       MWAIT( memLoc ) - wait until another processor may have written the cache line
    END LOOP

it is natural to think about extending it to multiple locations.

    MONITOR(memLoc1)
    MONITOR(memLoc2)
    LOOP
       tmpReg := load( memLoc )
       if( tmpReg = 42 || tmpReg == -21 ) then exit loop
       MWAIT( * ) - wait until another processor may have written any of the monitored locations
    END LOOP

You can even imagine re-evaluating the MONITOR'ed locations, e.g. to handle insertion and deletions on a list being monitored.

Note that you can probably get away with having multiple monitors, and a single MWAIT.
In much the same way as people have proposed multiple load-linked with a single store conditional

  loop:
    tmp1 := load-linked(memLoc1)
    tmp2 := load-linked(memLoc2)
    if( condition(tmp1,tmp2) then store-conditional( someMemLoc )
    if failure goto loop

Although this starts us on the slippery slope towards transactions.
First, with an explicit store commit phase

  loop:
    tmp1 := load-linked(memLoc1)
    tmp2 := load-linked(memLoc2)
    if_unchanged_then_commit_stores_atomically {
        store(memLoc1,...)
        store(memLoc1,...)
    }
    else {
        goto loop
    }

Then relaxing the requirement of users grouping the stores.

The problem with all of these is that the limits are arbitrary.
How many memory locations can you access?  1? 2? 4?  An L1 cache in size?

Flowchart Connectors: Coming Soon - Google Docs Help

I am very happy to learn that proper diagram drawing - connectors that stay connected - is coming soon to Google draw.

Flowchart Connectors: Coming Soon - Google Docs Help

This will put me in a quandary: this makes Google drawings almost exactly what I need for my comp-arch.net wiki.

Except that the wiki aspects of Google docs and Google sites are pretty darn poor.

The URLs are unreadable. And there doesn't seem to be a way to create a link to a page that does not yet exist yet, that you can click on to create the page, like [[New Idea To Be Filled In Later]] - which IMHO is the essence of wiki.

Moving programming languages beyond ASCII text

Just read Pul-Henning Kamp's CACM article "Sir, Please Step Away from the ASR-33!"

Amen.

Constraining ourselves to use ASCII has led to less readable programming languages and programs, and probably has also led to bugs and security breakins, as Kamp suggests with C's & and &&.

Kamp advocates using unicode, with "the entire gamut of Greek letters, mathematical and technical symbols, brackets, brockets, sprockets, and weird and wonderful glyphs..."

I am not so sure that I would go all the way to full unicode, if for no other reason that I don't no how I would edit a program that used "...Dentistry symbol light down and horizontal with wave" (0x23c7)", as Kamp finishes the previous quote. People complain about APL being write-only! But certainly a subset of unicode - subscripted letters in the major alphabets, and ideograms.

Let us end not just the tyranny of ascii, but the tyranny of English. Variable names with accents for the rest of the Europeans; variable names in Chinese and Japanese ideograms. Internationalization systems for program variable names and keywords!!!!

Okay, maybe that goes a bit far - but nevertheless I feel the pain of non-English native speakers.

Kamp goes on to talk about using wide screens, e.g. "Why can't we pull minor scopes and subroutines out in that right-hand space...?"

I'm not sure about that, but I am a big user of tables. Truth tables, etc., that make it easy to see when you have handled all of the possible cases. Arrange the code in a table; heck, click through to zoom in and see details if the code in a table cell gets too hard to read even on our wide screens.

And Kamp goes on to talk about using color for syntax. Again, amen... although that raises the possibility of red/green colorblindness causing new bugs.

Myself, I learned to program from theAlgol 60 primer, with boldfaced keywords.

I think, however, most of this is presentation. We need to start using something like XML as the basis of our languages. It can express all of the above. It can be presented using color, fonts, etc, on wide and narrow screens. It can be customized to your local display devices using CSS.

I know: many people hate XML.  I suggest it mainly because it exists, and is sufficient, and there are many existing tools that can be leveraged.

And did I mention language extensions via domain-specific languages? Many conference speakers and famous California professors advocate them.

Me, I am mixed about domain specific languages: I want to express things as natural in my domain, but I want all of my existing tools, my emacs modes, my interface generators, etc., to have a chance of handling them. More important than anything, it can be parsed by language processors that do not necessarily know the syntax of the domain specific language in use.

Think of how hard it was to extend C to C++: whenever they added a new keyword, existing programs using that keyword as a variable broke. This will not happen if your keywords are distinguished in XML using

< keyword > if < / keyword >

or  

< keyword ascii="if" / >

or

< if type="keyword" / >  

I don't terribly care which representation is used, so long as there are standard tools to convert back and forth to a form that my other tools can expect to receive.


(Although the multiple tries it took me to get Google's blogging software to type  XML < literals > - I had to add spaces - shows how much tool change is needed.)