Krazy Glew's Blog

2012-01-28T07:22:00.000-08:00

[[Write coalescing]] is the term some GPUs, notably AMD/ATI and Nvidia, use to describe how they, umm, combine or coalesce writes from different N different SIMD threads into a single, or at least fewer than N, accesses. There is also [[read coalescing]], and one can imagine other forms of coalescing, such as atomic fetch-and-op coalescing.

At AFDS11 I (Glew) asked an AMD/ATI GPU architect
"What is the difference between [[write coalescing]] and [[write combining]]?"

He replied that [[write combining]] was an x86 CPU feature that used a [[write combining buffer]],
whereas [[write coalescing]] was a GPU feature that performed the optimization between multiple writes that were occurring simultaneously, not in a buffer.

Hmmm...

Since I (Glew) had a lot to do with x86 write combining
- arguably I invented it on P6, although I was inspired by a long line of work in this area,
most notably the [[NYU Ultracomputer]] [[fetch-and-op]] [[combining network]]
- I am not sure that this distinction is fundamental.

Or, rather, it _is_ useful to distinguish between buffer based implementations and implementations that look at simultaneous accesses.

However, in the original NYU terminology, [[combining]] referred to both:
operations received at the same time by a switch in the [[combining network]],
and operations received at a later time that match an operation buffered in the switch,
awaiting either to be forwarded on,
or a reply.
(I'm not sure which was in the Ultracomputer.)

A single P6 processor only did one store per cycle, so a buffer based implementation that performed [[write combining]] between stores
at different times was the only possibility. Or at least the most useful.
Combining stores from different processors was not done (at least, not inside the processor, and could not legally be done to all UC stores).

The NYU Ultracomputer performed this optimization in a switch for multiple processors,
so combining both simultaneous operations and operations performed at different times
was a possibility.

GPUs do many, many, stores at the same time, in a [[data memory coherent]] manner.
This creates a great opportunity for optimizing simultaneous stores.
Although I would be surprised and disappointed to learn that
GPUs did not combine or coalesce
(a) stores from different cycles in the typically 4 cycle wavefront or warp,
and
(b) stores from different SIMD engines, if they encounter each other on the way to memory.

I conclude therefore that the difference between [[write combining]] and [[write coalescing]] is really one of emphasis.
Indeed, this may be yet another example where my
(Glew's) predilection is to [[create new terms by using adjectives]],
e.g. [[write combining buffer]] or [[buffer-based write combining]]
versus [[simultaneous write combining]] (or the [[AFAIK]] hypiothetical special case [[snoop based write combining]]),
rather than creating gratuitous new terminology,
such as [[write combining]] (implicitly restricted to buffer based)
versus [[write coalescing]] (simultaneous, + ...).

= See Also =

This discussion prompts me to create

* [[a vocabulary of terms for memory operation combining]]

Project structure: code, tests, external depndencies

2012-01-28T07:16:00.000-08:00

Say you have a project foo, which I will call .../foo, to emphasize that there is probably a project directory somewhere in the namespace.

.../foo

Where do you put the tests? It's nice to put them in .../foo/tests, so that when you checkout the project, you get the tests as well:

.../foo/tests

.../foo
.../foo/tests

...
foo
tests

It's also good to minimize the external dependencies of .../foo.

But what if the tests have more external dependencies than the non-test part of the project. Should you increase the external dependencies of the non-test part just to have the tests?

Conversely, should you make it harder to write the tests by forbidding external dependencies in them? Tests are hard enough to write, and they often depend on extra libraries that the source code per se does not?

More specifically, should you get stuff that has increased external dependencies if you check out .../foo and .../foo/tests comes along for the ride?

If you don't want the extra dependencies in .../foo/tests to come along with .../foo, you might structure them as separate modules, possibly separate in the file space:

.../foo+tests
.../foo
.../tests

This works, but it creates extra levels of such "meta-modules": .../foo+tests, .../foo+interactive_tests, .../foo+debugging_tools+tests, etc.

You might structure it as a series of optional modules, all within a single metamodule:

.../foo+stuff
.../foo
.../tests
.../stress-tests

or, rather

.../foo+stuff
.../foo+stuff/foo
.../foo+stuff/tests
.../foo+stuff/stress-tests

and so on.

It's still annoying to have an extra level of indirection, but the purity of the bodily fluids of .../foo is maintained.

Now, of course, it is highly likely that you will have some tests within foo and some that are assoviated with foo, but that foo won't let in:

.../foo+stuff
.../foo+stuff/foo
.../foo+stuff/foo/tests
.../foo+stuff/tests
.../foo+stuff/stress-tests

This can be confusing, but apart from changing names it may be unavoidable: if a country has immigration control country, you often get refugee camps on the border. The country may ignore them, but the UNHCR does not.

Some systems allow this "stuff" to be overlays within foo:

.../foo

.../foo/tests -- optional

.../foo/stress-tests -- optional

Perl test brackets with deterministic finalization

2012-01-26T12:21:00.001-08:00

I just realized that you can use deterministic finalization in Perl just like C++. Yay!

{
    package Brackets;
    # my first attempt to use determinsitic finalization in Perl;
    sub name {
 my $self = {};
 $self->{name} = shift @_;
 bless $self;
 print "{name}>\n";
 return $self;
    }
    sub DESTROY {
 my $self = shift @_;
 print "{name}>\n";
    }
}

Note that I use my "pseudo-XML" notation:

<TEST START name>
...
</TEST END name>

It's not nice to violate the standard, but IMHO this is a alot easirr to read than

<TEST context="START" name="name">
...
</TEST context="END" name="name">

and readability is a concern - since I plop these things in test output read by my human coworkers.Human coworkers who really don't like XML because it is so ugly.I can readily translate my pseudo XML into real XML, in case I wanted to use any real XML tools.And can do many operations without such translation.Unfortunately, there aren't many real XML tools to be used withot a lot of work :-(.I need to fix up my pseudo-XML UNIX command line tools, suitable fr use in pipezs and so on.

googletalkplugin issues

2012-01-25T12:45:00.000-08:00

I started having problems with google talk, specifically the googletalkplugin that I get when clicking on "phone" in gmail.I believe I have had these before. Not sure of old workarounds have all been tried, none so far work.Started off with not being able to hear gtalk dial.Then got messages like "XXX-XXX-XXXX (a phone number) cannot be reached."Uninstalled/reinstalled. Witho rebooting. Running as Asministrator. No joy.Just noticed many googletalkplugin processes running. This is what tickled my memory. A new one starts every time I start Chrome. Doesn't always go away.

Code ordering, want none: perl example

2012-01-24T16:08:00.000-08:00

I have several times posted how I find languages without code ordering pleasant, more readable.

E.g.

  let x = y + z
      where z = some log and complicated expressions

Here's an example from writing "shell scripts" - although here I am doing the shell script in Perl:Start off with:

   system("command with some long and complicated command line");

Realize that you want to repeat the command in a pre-announcement of what you are doing,and in an error message:Start off with:

   print "RUNNING: command with some long and complicated command line\n";
   my $exitcode = system("command with some long and complicated command line");
   print "error: exitcode=$exitcode: command with some long and complicated command line\n"
      if there_is_a_problem($exitcode);

Now avoid repetition:Standard way:

   my $cmd = command with some long and complicated command line";
   print "RUNNING: $cmd";
   my $exitcode = system("cmd");
   print "error: exitcode=$exitcode: $cmd\n"
      if there_is_a_problem($exitcode);

In my opinion the non-code ordered way is more readable:

{
   my $cmd;  # maybe some declaration to say it is not ordered?
   print "RUNNING: $cmd";
   my $exitcode = system($cmd = "command with some long and complicated command line");
   print "error: exitcode=$exitcode: $cmd\n"
      if there_is_a_problem($exitcode);
}

I think it is more readable because you see the value set at the point where it matters,where it is used most intensely (the other uses are mild, just prints).Note that I have used a scope.

Tagging is so passe'

2012-01-20T19:17:00.000-08:00

Tagging is so passe'.

Manually adding keywords to stuff you do.

What we need is "tag suggestion" software. Software that looks at what you have written, compares it to a corpus - perhaps your stuff, but perhaps stuff from others - and gives you the choice.

---

Automatic email folder classification rules are so passe'...

---

Gmail's labels are so passe'. Same reasons.

(Plus the absolute lack of structure.)

---

I have played around with Bayesian codes, for determining if tags or labels should apply.

---

Gmail's "important" filter is a step. But more needed. Plus, a more personal classification system.

---

I remember GNUS gnus-topic-mode.el in EMCS fondly. Realizes that at different times of the day, or in different modes, I may prioritize things differehntly.

THERE ARE NO FIXED PRIORITIES for personal information management.

My priorities when I am reading email on vacation, or in the evening at home, are different than in the day at work.

---

Why tag?

Why not just use search?

Tagging is a crystallization of information content. E.g. it records the fact that, at some time, you decided that a post was about VCS, Version Control Software, even though it might not contain the phrase in a way that seach would turn up.

Tags make it easier to track [[terminology drift]]. (TBD, need to write a wiki/blog on that).

E.g. what we call now VCS (Version Control) might have been called REvision Control years ago, or CM (Configuration Management).

Terminology drifts over time. Tags make it easier to track such drift, although even tags drift.

AAdvantage versus Account Aggregation

2012-01-20T19:04:00.000-08:00

I just learned that American Airlines' AAdvantage frequent flyer program has sent cease and desist letters to account aggregators.

(This shows how often I check my AAdvantage miles balance - only when I am planning vacation. It also shows exactly why I depend on an account aggregator - for all of these bleeding accounts...)

Now, perhaps I am exposing myself to hackers because I admit that I use an account aggregator. Single point of failure, and all that.

(By the way, I would be much happier if the aggregators had read-only access to my accounts - if they could only see balances, but not change passwords.)

But the overall thing is: there are, I have, too many bleeding accounts. Too many blinking passwords.

Account aggregators are one major tool to manage this.

If a company will not let *any* account aggregator access them, well, then I do not need to be a customer of that company.

I was considering dropping American Airlines anyway, because of their financial position. This is just more incentive.

---

Heck, if AAdvantage was implementing better security, such as captchas, I would be happy.But sending "cease and desist" letters - that's garbage.

Branch purpose commit message

2012-01-19T11:33:00.000-08:00

I would still like to have a commit message that I write at the time I generate a branch, saying why I am bothering tio generate a named branch.

VCS thoughts

2012-01-18T23:50:00.000-08:00

Some fast, probably cryptic, thoughts after a day merging with a "I wasn't familiar with it originally but I am painfully familiar with it now" VCS tool.

Merges are branches.

Mercurial tracks merge workflow in a workspace, assuming that a merge will be a single commit.
But today I had a complicated enough merge that I started a named branch off just for it. Accomplished the merge between my tasj branch and the trunk. And then merged back from this "merge branch" to the trunk.
Worked fine, but it would have been nice to have some workflow tracking along the branch. Like "hg resolve", but "hg resolve" stops at the first commit boundary.
Had to fall back to tracking things by hand, in a text file.

Mercurial 's names are awkard

"hg revert" isn't revert

"hg revert -r REV file" isn't "revert". It is "include this revision of the file in the candidate commit that you are building in your workspace.
hg revert corresponds to cvs update

"hg update" isn't update

"hg update -r REVorBRABCH" isn't "update". It is "switch the revision or branch that the candidate commit you are building ijn the workspace will be applied to as a child."
hg update corresponds to cvs checkout, although cvs is pretty sucky there too.
It's rather like a rebase when you have no revisions checked in yet

Mercurial's branchs are not branches.

They are floating tags
Not necessarily lines of evolution.
What would be a better name? "Stream of development?" "Genealogy line"?
I'd like to have evolutionary branch0lines, as well as what Mercurial has.

Tags should be versioned.

At least Mercurial got that right.
But old tag versions should be visible in the log.
And it should be possible to refer to an old tag version, something like "last week's official release"

Mercurial's anonymous branches rule

See, I am not purely dissing hg
But "hg tip" has obviously not been brought up0 to date with named branches

Can anyone tell me how to do the equivalent of "cvs update -j branch-base -j branch" in Mercurial?

Without using an external patch
Hint: "hg merge -r branch" doesn't work, if you have anti-patches on the branch

I want to be able to "pull onto a branch" or "push a branch". Not just "push or pull all the branches in the repository". I.e. I want branch renaming or mapping in pull and push

Mercurial doesn't do partial checkouts or checkins?

Maybe not everywhere
But you can screw yourself up in the same way with "hg ci incomplete list of files"

I'm not suggesrting denying hg ci files partial
But I'd like to do it in general.

Partial checkins and checjkourts should correspond to brancges, with merging actively encouraged.

I've talked about this many times.

Enough already.

"system/command" versus "system command"

2012-01-18T11:11:00.000-08:00

A lot of tools have a master command with subcommands. For example


hg clone ...
hg merge

cvs co
cvs update

git clomne
...

I think that the first place I encountered this was with mh. Or, since my friend MH says that mh did not have subcommands, I may have made the following change myself for mh.Why subcommands? I think mainly to avoid name collisions in the bin.Years ago, I kluged - I think it may have been the shell, whoever processes PATH -to search not just for "executable" on the PATH, but also "dir/executable".I.e. instead of saying


hg update

I colud have said


hg/update

Not much of a difference. But it makes it easier for guys to code systems that have lots of subcommands.Also, for users of shells like bash and csh: !hg/update works, whereas "!hg update" doesn't (unless your shell has tweaks.

2012-01-17T11:55:00.001-08:00

Mercurial whine:


hg merge -r tip

is NOT the same as


hg merge -r default

Because Mercurial's tip may be on a branch. tip is just the most recent changeset, anywhere.I have hit bugs caused by following hg recipes that talk about using -r tip.Sigh.

Tentative checkin for branch only, not to be merged?

2012-01-17T11:47:00.000-08:00

Here's another:Working on a branch, I just did a pull, and merged from trunk onto the beranch.I notice that somebody else has a minor bug on the trunk: it looks like they forgot to check in a test reference pattern,although it is also possible that the test has been checked in before the golden behavior is established.I report the bug.But I would like to silence the error, at least on my branch. I can make the change to the reference patterns.However, I do not know if that change is goosd. I just want to silence it, or mark it as a known error.I don't want my change to propagate back to the trunk when eventually I merge and push.I.e. my branch now contains some tentative stuff, as well as some stuff that I am confident will soon be merghed.On CVS I would create a per file branch for the reference, and work off a merged directory.Eventually, I would update to the main branch, ahnd not get5 my patched test.Unclear how to do this in Mercurial, apart from remembering that I have to delete it eventually.Oh, here's a way:

// working on branch B
hg pull
hg merge -r tip
make test
// make change to silence test error
hg branch Bb
// somehow copy old version of patched file to pre brahnch
hg ci // on Bb
hg update -r B
// now work
// when ready to merge, do the usual
hg pull
hg merge
make test
// now do the extra step to be confident that you aren't pushing anything broken
hg update -r Bb
hg merge -r B
// now should have B, except for that one change that was tenative
make test
// see if the bug was fixed by someone else...
// ok, now merge to default branch, and then push
// - since I am paranoid, I might pull and test again
hg update -r default
hg merge -r Bb
make test
hg push

Works, but is complicated. I am quite likely to forget that I am supposed to merge from branch B onto Bb before merging to the trunk.{{Category-VCS}}{{Category-hg}}

2012-01-17T11:28:00.000-08:00

AFAICT Mercurial only allows you to merge entire changesets.

Here is an example of why I may want to do a merge at lower granularity:

I am working on a branch B
I do a pull from the parent, hg pull
I merge from the parent on to my branch B, because I am not yet ready to merge back onto the trunk (aka default branch)
I run my tests

Now I notice that the .hgignore that I got from the parent is missing a file. I fix it in my repository, to shut it up.

Then I realize that I should push such a generic change back to the trunk asap.

What I want to do is something like"

  hg clone work-repo quick-fix
  cd quick-fix
  hg update -r default
  hg merge -r B  .hgignore     # to merge just the change to .hgignore into the trunk
  make clean;hg purge
  make test
  hg ci
  ...
  hg push

I.e. I want to merge JUST the change to .hgignore, using "hg merge -r B .hgignore".Instead I do

  hg clone work-repo quick-fix
  cd quick-fix
  hg update -r default
  cp ../work-repo/.hgignore .
  make clean;hg purge
  make test
  hg ci
  ...
  hg push

I.e. "cp ../work-repo/.hgignore ." is used instead of "hg merge -r B .hgignore".Although this works, it makes me unhappy.E.g. I may blithely have overwritten other changes, e.g. if I cloned from the master rather than the work-repo.Not to mention the fact that the "hg push" abnove would push my branch.And my teammates do not want my branch to be pushed, because it has too many fine grain checkins - they want just a single checkin message.But that's another story.

2012-01-14T16:23:00.001-08:00

I'd like to have a text parser, like Perl CPAN Text::ParseWords,
that *only* breaks the text into words
- but which does not transform the words, handle escape characters, etc.

For example,
Text::ParseWords::
shellwords("a b 'c d' e")
returns
a
b
c d
e
i.e. it breaks the text up into words,
but it also transforms the words.

I would like to separate the breakup from the transformation:
a
b
'c d'
e

Note that if you ever encounter such a list whose words can themselves be further broken up,
then you know that it has been parsed by some tool after your original parser.

[[Category:Programming]] [[Categy::Text]]

Thumb drive as a webserver / NAS

2012-01-08T18:28:00.000-08:00

I wish that I could find a flash drive that acted as a NAS.

Most USB flash drives are passive storage. Encryption is done by the OS you plug into. Since I run Windows and various *IXes, and want to access my data from each, depending on a particular OS is a pain.

Booting an OS from the USB flash drive is better - but still not great, since it makes assumptions about the platform you are plugging in to. Typically, that it is a PC.

Flash drives have non-trivial processors in them. Probably running Linux. Why not make them a peer?

Issue: network interface.

I don't really want to add a typical Cat 5 ethernet connector - what is that, RJ45, 8P8C plug? - to the flash drive, neither in addition to nor replacing USB.

Q: I am sure there is a standard for networking over USB - but how ubiquitous is it? I do not recall ever getting the option, when I plug in a USB flash drive, of connecting a webnrowser to a server running on tghe drive.

Gratuitous key position changes.

2012-01-06T15:51:00.000-08:00

Was wondering why "search" or "find" in Google chrome was broken.

Wasn't. For the past week I was using a keyboard that was not my usual, with the keys in the lower left hand corner looking like Ctrl,Fn,...

Just switched back to what has been my usual keyboard for several months, with those keys swapped: Fn,Ctrl,...

It's funny how these trivial differences in devices are some of the most annoying.

Last time I shopped for keyboards, I bought 3 identical. Not my favorite keyboard, but cheap enough that i could afford 3 of them. Home, work, and Oceanside.

Yeah, yeah: remapping. Loses.

(The only good form of keyboard remapping is one that is downloaded into a PROM on the keyboard, so that it works in all modes, even before the OS boots.)

hg schemes extension

2012-01-05T13:04:00.000-08:00

http://mercurial.selenic.com/wiki/SchemesExtension

I like the idea of this extension, that allows you to create shortcuts for URLs you use often, e.g. cloning.

E.g.

[extensions]
hgext.schemes=

[schemes]
ups = ssh://my-uarch-performance-simulator/...

However, it is something of a no-sale when I saw that the URL was notexpanded in the clone:

> hg clone ups: u
...
> cd u
> hg paths
default = ups://
>

Or in WorkDir/.hg/hgrc

[paths]
default = ups:

PRO: when the remote repository changges location, this *might* allow you to change the scheme URL shorthand in hgrc, and have things work in the possibly multiple clones you have outstanding.

CON: it loses some documentation. If I got run over by a beer truck, my replacement might have trouble finding where it was from. Worse, if a repo was restored from backup (particularly if people keep branches as repos), and my home directory with the ~/.hgrc enabling SchemesExtension was not present.

I'm not sure what I would like. Possibly always expand the shorthand. Possibly record the shorthand with the long path as a comment:

[paths]
default = ups: # ssh://my-uarch-performance-simulator/...

> hg paths
default = ups:// # ssh://my-uarch-performance-simulator/...

TBD: move this to my wiki Category:VCS.

VirtualBoxen

2012-01-03T21:23:00.000-08:00

Gave in, worn down... Installed VirtualBox, and Ubuntu in a virtual box, on my tablet PC running Windows 7.

Stream of consciousness...

Recovering diverged home directory version control

2012-01-02T14:25:00.000-08:00

I have long version controlled my home directory. CVS. Git. Hg.

Unfortunately, they diverged. Divergence happens naturally with CVS. You have to work hard to get git and hg to diverge, but I did.

Now I want to merge the diverged home directories back together. Preserving the history if possible, from the different VCS. Sometimes just merging fikes.

==

Today: I want to start merging a diverged linux tree, from a flash drive, with my working tree (which started off on cygwin).

I created a new hg repo, created a branch on it, and then imported the tree to be merged.

I pulled/pushed this with my main home hg repo. Had to use -f, to force unrelated repos to be together.

Now I have a single repo, with my current working (cygwin derived, homedir, and a not working linux homedir, on different branches. The former n the default branch.

That's okay. Not so bad. A single history object(although I have kept separate working space trees.)

===

Now I want to merge, a file or a few files at a time.

E.g. copy the README from the linux branch to the default working derived from cygwin branch.

AAARGH!!!! Hg doesn't handle partials... neither merges, not copies, nor... Hg just plain really wants to lose track, not make doing this activity easy.

Missing X fonts

2012-01-02T13:26:00.000-08:00

Like http://ubuntuforums.org/showthread.php?p=11544410, I was getting errors such as

Warning: Cannot convert string "-*-courier-medium-r-*-*-*-120-*-*-*-*-iso8859-*" to type FontStruct
Warning: Cannot convert string "-*-helvetica-medium-r-*--*-120-*-*-*-*-iso8859-1" to type FontStruct

(Except that I was getting the errors, not on a fresh Ubintu install, but when trying to use a fairly new machine at work, with what is probably a newer version of redHat.)

The post I quote fixed things by setting ~/.Xdefaultsto

emacs*font: 7x14

And then doing xrdb -merge ~/.Xdefaults

On my end, I found that neither 7x14 nor courier worked. But font "fixed" did.

An Amusing and Frustrating Anecdote about Google 2-step Verification

2012-01-02T11:33:00.001-08:00

I like Google 2-step verification - in which you normally log in with a password, but where, if you are logging in from a new machine, etc., you "verify" your login by entering a one time code sent to your cell phone by voice or text.

I liked the idea as soon as I heard of it, but was reluctant to sign up for it because I frequently use my laptop computer in places where cell phones don't work - e.g. at the coast in Oregon, and, most recently, at my new house in Portland's hills.

I was scared that I might end up unable to log into my gmail, lacking cell phone.

Nevertheless, after reading rave reviews, I finally gave in and signed up for 2-step verification. And have continued to use my laptop fairly successfully at the coast without cell phone coverage, since normally it has already been verified.

But over New Year's I finally tripped up:

Because of a bug with googlevoiceplugin.exe (a new copy was spawned every time I started Chrome: I had 52 copies when I realized what was happening) I uninstalled and reinstalled the plugin, and eventually Chrome itself 9since the plugin would not uninstall while Chrome was running).

So when I tried to log back into gmail on Chrome, 2-step verification was required. But my cell phone doesn't work at the coast.

Now, Google 2-step verification has a backup phone numbeer, which can be a land line using voice. But remember that I said the new house that I have just bought also lacks cell phone coverage? Guess what my backup phone was?

And Google 2-step verification does have a backup set of one time passwords. I know I printed them out for my wallet. Umm... got a new wallet, recently, smaller, and did not carry it over.

So now the fun begins: I don't have to drive too far to receive a text message. I'll try to login, get Google to send the verification code, drive to where I can receive a text message, drive back.

Try #1: got the message. Actually, got several verification code messages. Drive back, they don't work. Perhaps I got confused, and typed the wrong verification code into the wrong box.

Try #2: I realize that I may not need to drive the few miles to the next town. The mountain next to my house may have reception. Drive up it, yep, received the text message. Drive down... Nope, didn't work.

I'm beginning to think there is a timeout.

Try #3: Repeat. An hour or so later, since I had to charge my cell phone - the battery drains quickly in this area. But this time, I can't get any bars on top of the mountain. The fog has moved in and the sun has set, affecting signal strength.

So I drive to the next town. Signal, but no text message. I wait ten minutes, start driving back... and the message arrives while I am driving. Have I mentioned that AT&T Wireless has occasionally taken >4 hours to deliver text messages? 20 minutes is par for the course.

Doesn't work. I', getting pretty sure there is a timeout.

Try #4: This time I request the verification code, drive out, and call back to ask my wife to enter it.

However, my laptop has gone into power saving mode, and although I disabled the power-on password, by wife doesn't realize what has happened, and tries to use the second computer sitting next to the laptop that needs the verification code.

2 days later we try again: my wife drives to the next town with my cell phone. She calls me back when she gets a signal. I request the verification code. She waits a minute or so - fortunately, this morning AT&T is fast - and reads it back to me over the phone. I enter the code, and all is well.

I change my backup hone number to the landline at the coast. Realizing that this will needto be changed again when I get back to Portland.

And I write the backup passwords down by hand.

Powering up multiple displays on Windows 7 - lots of flashing :-(

2011-12-12T17:29:00.000-08:00

I have 4 external 1920x1200 displays connected to my Lenovo Thinkpad X220 Tablet PC, via Diamond DisplayLink based USB adapters.

When I power the besat up, not just cold start, but also, most annoyingly, warm start, from Hibernate (Suspend to Disk) or Suspwend (to RAM) power down modes, it engages in excessive flashing.

The screen blanks and redisplays 15 times!!!

Quite annoying.

Continuing http://andyglew.blogspot.com/2011/12/multiple-displays-on-windows-7-good-but.html

Lifehack: Binder Clips help Debug Chistmas Lights

2011-12-11T00:37:00.000-08:00

Fixing Christmas lights today.

Figured out the binary search approach - e.g. as described by http://www.squidoo.com/howto-fix-broken-christmas-lights#module12970984.

My own embellishment: I find it hard to track where I am in checking the Christmas lights, and/or strand continuity. Even leaving empty sockets behind doesn't help that much, since the empty sockets are hard to see. And since I have a small work space, so had to fold the string of lights back on itself 3 times.

So I marked my position with binder clips. I happened to have at least 4 colours of binder clip. I used four clips to dedfine the boundaries of the interval where I was searching for a duff lightbulb - two clibs at each boundary. Two clips at each boundary because, given the folding ofg the string of lights, it became hard to tell which direction was towards the end, and which inside the interval. So I used two colours of binder clip at each end.

A Modest 1 bit Proposal about Quotification - making the Default Easy

2011-12-08T07:21:00.000-08:00

Listening to an old "Security Now" podcast while doing my morning stretches.

Leo Laporte's TWIT website was hacked, and Steve Gibson, the Security Guy, says "Any time you are soliciting user input, there is a risk of malicious input somehow tricking the backend and executing that input, when it is meant to be, you know, benign [input data, like] user name and password.".

This is typical of the classic SQL injection hack, and, indeed, of any hack where the attacker is able to inject scripting code and fool the backend into executing it. Typically by embedding quotes or the like in the input string.

(For that matter, Steve's description also applies to binary injection via buffer overflow. But we won't go there; this page will talk only about non-buffer-overflow attacks, sijnce we have elsewhere described our agenda for preventing buffer overflow attacks.)

Say that you are talking user input like NAME, and are somehow using it to create an SQL or other language command, like "SELECT FIELDLIST FROM TABLE WHERE NAME = '$NAME' ". But now the attacker, instead of providing a nicely formed string like "John Doe", provides instead something like "anything' OR 'x' = 'x ". (I added spaces between the single and double quotes for readability.) I.e. the user provides a string that contains quotes in the target language - not the language where the query string is composed, but a language further along. So the query string becomes "SELECT FIELDLIST FROM TABLE WHERE NAME = 'anything' OR 'x' = 'x' ". And now the query matches any row in the table. (http://www.unixwiz.net/techtips/sql-injection.html provides examples, as does wikip[edia.).

The general solution to this is "quotification": take the user input, and either delete or quote anything that looks like a quote in the target language:. E.g. transform the attacker's string "anything' OR 'x' = 'x " into either "anything OR x = x " or "anything\' OR \'x\' = \'x ".

The problem with deleting stuff from the user string is that sometimes the user is supposed to have quotelike things. Consider names like "O'Toole". Or consider prioviding, e.g. via cut and paste, Chinese unicode names in an application whose original programmer was English, but where the system is otherwise capable of displaying Chinese. It is a pity if the barrier to internationalizaion is the "security" code scattered throughout your application that santizes user input. Worse, that is the sort of code that might get fixed by somebody who fixing internationalization problems who doesn't understand the security issues

The problem with quotifiying stuff is that it is hard. It is not just a case, for you Perl afficionadoes, of doing s/'/\/g - what about input strings that already have \\' inside them? And so on.

But the real problem, applicable to both deleting and quotification strategies, is that the code doing the user input sanitization does not necessarily know the syntax of all of the languages downstream. It may know that there is SQL along the way - but it may not know that somebody has just added a special filter that looks for French quotes, << and >>. Etc. Not just special symbols: I have defined sublanguages where QuOtE and EnDqUoTe were the quotes.

The security code may know the syntax at the time the sanitization code was written. But the downstream processing may have changed. The syntax of the language may have been extended, in a new revision of the SQL or Perl or ... . (I found a bug like that last year.)

The problem is that the user input santization code is trying to transform user input from strings that may be unsafe, to strings that are guaranteed to be safe forever and ever, no matter what revisions are made to the language, etc. The problem is that the default for character strings is that ANY CHARCATER MAY BE PART OF A COMMAND unless specially quoted.

We need to change this default. Here is my moldest proposal:

Let us define a character set whereby there is a special bit free in all characters. And whereby, if that special bit is set, it is guaranteed by ANY REASONABLE LANGUAGE that no character with that special bit set will be part of any command or language syntax like a quote symbol.

We should strongly suggest, that the visual display for the characters with and without the special bit set is the same. Or at least, the same in most situations - in others you may want to distinguish them, e.g., by shading.
.
If you are using something like BNF to describe your language, then it might be:

ORDINARY_CHARACTER ::== 'A' | 'B' | ...

TAINTED_CHARACTER ::== 1'A' | 1'B' | ...
POSSIBLY_TAINTED_CHARACTER ::= ORDINARY_CHARACTER | TAINTED_CHARACTER

where I am using the syntax 1'A' to describe a single character literal. with the special bit set.

STRING_LITERAL := QUOTED_STRING | TAINTED_STRING
TAINTED_STRING ::= TAINTED_CHARACTER+

QUOTED_STRING ::= " CHARACTER* "

(Actually, I am not sure whether a quoted string should be the abnove, or
QUOTED_STRING ::= " POSSIBLY_TAINTED_CHARACTER* "
)

And we require that the only place where the possibly tainted characters with the tainted bit set are ONLY permitted in strings. Nowhere else in the language. Not in keywords, symbols, operators....

Then we just have to ensure that all of our input routines set the special bit. If you really need to form operators, the programmer can untaint the data expliocitly. Btter to have to untaint explicitly in a few p[laces, than to have to quotify correctly in all places.

Perhaps better to make taintimg the default. To flip the polarity of the special bit. And to require that language syntax, keywords, etcv., be set only if the special bit is set.

This is just the well known taint or poison propagation strategy. Exposed to programming language syntax definitions.

I have elsewhere espoused taking advantage of extensible XML syntax for programming languages. This is similar, although orthogonal.

wi8ki'ed at http://wiki.andy.glew.ca/wiki/A_Modest_1_bit_Proposal_about_Quotification_-_making_the_Default_Easy
as well as posted on my blog

Multiple Displays on Windows 7... Good, but...

2011-12-07T18:00:00.000-08:00

I love the DisplayLink USB display adapters that let my piddling little tablet PC drive 4 1920x1200 external monitors.

However, many, umm, irregularities happen with Windows 7 support and/or the display or device drivers.

Earlier today, and for weeks if not months, I have been able ti have 5 displays - my laptop/tablet PC's built in LCD, and my 4 external displays.

However, I went into hibernation while travelling from home to work (where I did not use the PC) and back to home again.

And when I woke up, I cannot get my laptop built in display to work, when the external displays are plugged. Sure, it works when they are not plugged in; but when they are plugged in, the laptop built in display gets "blackened" in the Orientation box.

Just yet another Windows 7 strangeness.

Organization and time management, technology for

2011-12-03T22:33:00.000-08:00

I felt inspired to start writing this. More like collecting.

Human handwritten proofreading marks

2011-12-03T16:57:00.000-08:00

http://creativeservices.iu.edu/resources/guide/marks.shtml has a nice collection of human proofreading marks.

Some are irrelevant to pen or touch tablet computers - why mark that a period should inserted, when you can just do it?

But some might be usefully considered for use as commands in a pen driven text editing system

Possibly also for depiction of edits and revisions.

Organization Tools, Evolution of

2011-12-03T14:38:00.000-08:00

I am fascinated, or at least interested, in tools for organization, scheduling. Time management. Filing.

American schools say "Time management skills are the most important thing you have to learn in high school to be prepared for success in college." But, as far as I know, nobody actually teaches techniques for organization and scheduling.

Perhaps one of the reasons I am fascinated by this is that it does not come naturally to me. But, as a result, I have studied it, and my career as a computer programmer and computer architect is really all about organization and scheduling. Albeit for computers, not people.

My whole career has been about scheduling for computers. First software operating system schedulers, in particular real time schedulers. Then hardware OOO CPU schedulers.

But I remain interested in scheduling and organization in many different aspects: computerzs, factories (JIT and kanban), people (organizers, PDAs, DayTimers, etc.)

It is quite interesting to see how organizing tools for people have evolved. I probably need to convert this into a wiki post so that I can evolve it. http://wiki.andy.glew.ca/wiki/Organization,_technology,_evolution_of

First paper, and now on computer.

In paper:

Duotangs

Three ring folders.

Tracker-keepr --- I just learned from a friend how this tracker/keeper system for holding papers together became popular for elementary and high school kids in the US in the 1980s. Essentially plastic sheets that folded to provide an envelope out of which is was hard for things to fall.

Three ring folders have made a comeback in my daughter's
school, but with zippers around them.

Staples

Paper clips.

A famous engineering author explains how, prior to paper clips and stables, people used straight pins.

School websites

2011-12-03T12:45:00.000-08:00

School websites sound like a good thing: use your browser to keep track of your kid's school, homework assignments, etc.

In reality, it turns into a mess unless the website is organized. And teachers are not necessarily good website architects[*].

The school may have a website. Good. In a content management system like Drupal. Okay. With pages for every class, a news system, etc. Not so bad.

But then some teachers may use a separate Moodle.

And some other teachers may use a separate Google Apps or Google Sites site,.

So, for class #1 you have to go to the Drupal site. For class #2 you have to go to the Moodle. For class #3, the homework is posted on the Google Sites site, but there's some background info on the Moodle. And, oh yes, still other stuff on the Drupal.

AAARGH!!!! I can't remember which webtool - Drupal, Moodle, Google Sites - to use for any particular class. Yes, I may be a Luddite parent - but I am a reasonably web.savvy Luddite parent.

And it's not just me, the Luddite parent, who finds this confusing. The students do too. Not just my kid: I have had a teacher complain to me that this teacher keeps telling the class to use the Google Sites site for the class, but the students never seem to understand. Could it be because this teacher is their only teacher using Google Sites instead of Drupal or Moodle, and the kids naturally look to one place? Perhaps if this teacher created a class page in standard place on the Drupal or Moodle page, and linked to the Google Sites site for his class? It might also help the Luddite parents.

Note that above at the [*] I decided to say "website architect" or "website organizer" rather than "website designer". Website designers, at least the not so good ones, often concentrate on visual flashy effects. School websites have plenty of that. What they seem to lack is organization, or architecture.

Note: it's not just a question of installing a new content management system. They already have more than enough. Note that I am not saying "too many" - I am saying "more than enough". I am not against using different CMSes. But, if you do, you need to link them together, so you can get from one to the other.

---

Here is a dream, a suggestion a modest proposal for school websites:

(0) Have a front end, in whatever CMS you want. Drupal, say.

(1) Allow the teachers to create sites in whatever other CMSes they insist on using. Moodle. Google Sites. Whatever.

(2) But insist that there be a classroom page created on the front end site (Drupal, in this example). If nothing else, it should point to where on the other CMSes the real classroom contents.

Note that I don't mean just with text saying "some teachers use the Moodle or other tools". Which basically means that you have to figure out how to get there on your own. No, I mean a real, clickable, link to that other site. If you can't create a link into that other site, well... (IMHO that's the only reason to forbid using a different tool.)

---

More on the same lines: Use dates, so that stale data does not keep rising to the top.

I keep clicking to links and URLs that say stuff like "Fourth Grade Science". But it turns out that it was 4th grade science for 2008. Or last years' class. Or ...

A page identifier like "4th grade science" is really a floating identifier. At any particular time it should point to something like "4th grade science 2011-2012". Every year, it should be updated.

I'm quite happy to have the old years' stuff remain on the website(s). It's nice to look at. But, I don't like it getting in my way when I am looking for this year's stuff.

---

Perhaps "News" should expire after a while?

I.e. I am not at all sure that class presentations for history class from two years ago are still "News". More like "Olds". Again, useful for reference, but a time waster when I, am a parent, am trying to find what is really new at my child's school website.

---

In my dreams: wouldn't it be nice to have a page you or your child could log into, that contained links to the particular class webpages for all the classes your child is taking?

Actually, my effort to do that myself - to create a wiki/Evernote/whatever page, pointing to all of the key information on my child's school website - is what inspired this post. It's darned frustrating finding it.

---

Hypertext systems like the web have great potential. But they are a pain to use if disorganized.

It's hard to keep them organized.

Search engines like Google are the saving grace for the real web. But Google is not allowed to index a school website with possibly sensitive information. Most CMSes have their own search, but when you have multiple CMSes, this doesn't help much.

It would be nice if each school ran its own private Google indexer on its various websites and CMSes. (Hmm, Google, maybe that would be a nice public service? Or are you hell bent on getting as many schools as possible to use Google Sites and Apps, giving non-Google Drupal and Moodle the cold shoulder?)

But even if there was decent search for school websites, some modicum of organization is desirable. I think what I suggest is pretty basic: (1) All class webpages in a fixed place, linking to whatever other websites or services the teacher chooses to use. (2) With dated content content, and floating labels - ("4th grade science 2008-9" versus "This year's 4th grade science".)

===

Nothing that I say here is specific to schools. This is just good website design - or should I say "architecture" - for a heterogeneous system.

Nothing that I say here is critical of school IT. School IT just sets up the system - the teachers provide the content. The only slight criticism is that IT should enforce the very minimal standards that I suggest. Perhaps school IT should set up the default classroom pages on the primary website. Teachers should be responsible for linking to whatever other non-standard website technology they choose to use.

===

I just had a thought about why this schizophrenia arises aty school websites.

Teachers are often not the most sophisticated web.users, whether in their own college days, or afterwards.

In college, teachers probably used whatever their university IT department provided. And university IT departments are often pretty good, in particular good at providing services to unsophisticated users (faculty and students)

But different universities have different CMSes. Some use Drupal, some Moodle, Google Apps and Google Sites increasingly common.

So a newly graduated teacher is used to whatever they used at school. And is also used to having reasonably good IT support.

But when they start teaching at a K-12 school, you get teachers who graduated from different university programs, each used to different CMSes. And they all want to use what they are familiar with. Moreover, the K-12 school IT, although perfectly competent, is NOT as fledged as that of a university IT department.

I am sure that large school districts enforce website standards: e.g. they probably tell their teachers that Moodle is the only CMS supported, use it or else. Makes it easier to organize. However, that is not true for the schools that I have interacted with. And I remain an advocate of heterogeneous systems. It;s just that they require a certain minimum amount of work.

===

I should probably volunteer to help my kid's school organize its website.

Reagan Cattledog Links - reverifiable COW BOW links

2011-11-16T08:17:00.000-08:00

Thinking about updating shared libraries:

Shared libraries' true advantage is their true disadvantage: multiple users can be updated, whether for good or ill.

Perhaps what we need are shared library linkages that are not automatically updated. Where an update is marked pending, encouraging the user of the library to update it asap, but the change is not made.

I am calling this a reverifiable COW link. A link,that is broken when somebody else writes to the linked object (hence COW, Copy on Write, or BOW, Break on Write). But which is reverifiable. Retestable. (As one of my friends says "If you really believe in unit tests..." (I do, he doesn't).

I would like very much to be able to have acronym COWBOY instead of COW BOW. But I am humour deprived.

In the meantime I can call them Reagan Cattledog links. Get it? BOW, as in bowwow, dog. Reagan, as in "trust, but verify."

---

This not just for shared libraries. Any sharing. web pages. Like the "cached link" I have described elsewhere. Cached links are really just COW BOW links which are assumed to be updated when the linkee comes back online.

Shared libraries and data deduplication

2011-11-16T08:08:00.000-08:00

People have talked about the advantages of shared libraries: reducing virtual memory requirements, reducing disk space requirements, etc, because of sharing.

Here's a thought: Q: if we had truly ubiquitous data deduplication, what would be the advantages of shared libraries?

A: none of the performance wins through sharing need apply. Deduplication beats them in a more flexible, more abstract, way.

(Of course, we do not have truly ubiquitous deduplication. And it usually requires things to be block or file aligned.)

This leaves the only fundamental advantage of shared librares

the fact that you can effect a ubiquitous change by updating a shared library.

Which is also their fundamental disadvantage. You can propagate a bug fix. But you can also propagate bugs.

Modules(1)

2011-11-16T07:55:00.000-08:00

So I read Furlani et al's papers on "Modules".

Modules is not so bad - it is a nice way of dealing with an annoying problem.

Or, rather, Modules may be the best possible way of dealing with environment dependent code. But it might be better to discourage environment dependent code in the first place. See my earlier post about environment dependent code being a dominant meme.

--

Minor observation: I would like to bring some non-Modules source scripts "kicking and screaming into the '90s with Modules". I would like to simply wrapperize some existing legacy code that requires you to "set some environment variables and then source foo". I.re.I don't want to rewrite foo - I would just like to wrap it in a module.

Modules does not seem to be able to do this.

Although it looks as if it would only be a minor extension to modules to handle it.

To do foo, start off in a new window

2011-11-16T07:49:00.001-08:00

How many times have you seen "How to" directions begin:

To do foo

Start in a fresh xterm
Start in a fresh shell (typicaly csh)
Log out and log in again so that you get a clean environment

etc.

While this may be good advice, certainly good advice for debugging brokenesses and/or avoiding bugs in the first place - it is basically an admission that something is not right.

Some tool depends on the environment in weird ways.Possibly not just the standard UNIX environment string;possibly also the extended shell environment.

Tools should be callable from almost arbitrary environments. They should not DEPEND on environment variables. It may be acceptable to USE environment variables to change some behaviors, but, consider: if you had a setuid script, it would probably be unwise to depend on environment variables. Environment variables should be considered tainted.

I suppose my version of the above is to say

To do foo

Empty all of your environment variables, and start off with a minimum environment
Type the absolute path to the tool,/a/b/.../c/d/tool

IMHO tools should work when invoked like this. If they are using the equivalent of Perk FindBin, they should be able to locate all of the relevant library files, etc., they need. Or else they should have, embedded in them, the paths to same.

GLEW OPINION: much of the reason for environment abuse is the broken, non-object oriented, UNIX installation model, where a tool may be put in /bin, its libraries in /usr/lib, etc - where the directories are not known at build time. PATH, LIBPATH. MANPATH. FindBin can live with this - a FindBin script can be relocated by copying - so long as the relative locations of what it depends on are maintained.

source scripts

2011-11-16T07:36:00.000-08:00

I am going to try calling the sort of shell command file that must be source'd, i.e. read into the user so that it can modify the environment, a "source-script".

As opposed to a "shell-script" or other command which is usually executed as a subprocess.

UNIX-style subprocess execution of commands provides isolation. The parent is unaffected by the child, except for interactions through the filesystem. (Although with the /proc filesystem, or the child applying a debugger to the parent, that could be significant.)

Whereas, consider a csh style source-script. It can be changing directories all over the place to get its work done. And it may terminate with an error before finishing properly. So the "caller" or the source-script may not know what directory he is in after the source script terminates.

Q: how many people do:

set saved_dir=`pwd`
source srcscript.csh
cd $saved_dir

And,of course, even that has obvious bugs.

environment setting a dominant meme?

2011-11-16T07:29:00.000-08:00

Thinking about why I go through this paroxysm of disgust whenever I encounter a toolchain that depends on environment variables. Like Modules or modulefiles(1). Like many CAD tools.

This morning it struck me: they are a dominant meme. An evolutionarily stable strategy.

Not because environment based tools are better.

But because cleanly written stuff,like I try to write, can be called pretty safely from anywhere. Whereas stuff that does what I consider unclean environment modifications cannot be called so easily from other code. It can call other code, but it is hard to be called from other code. So there is a tendency for users to just give in, and write in csh (since csh in so often the language associated with such environment dependent tools).

Sure, you can try to write code that prints the environment and which then gets called. However, this only catches the UNIX environment - modulefiles(1) rely on sideeffects in the extended shell environment, shell functions and aliases. You could print these, but would have to parse them to pass to a different language, or at least reread them if passing to a later compatible shell.

Bandaid.

The best way to work with such tools is to start a persistent subprocess, pass it commands, and interpret the results. Expect style. Coroutines. Which is doable, but is more complex than order function calls / UNIX style subprocess invocations.

calling a function to change the environment

2011-11-13T13:37:00.000-08:00

I think that what I really object to in tools that dedpend on environmebt variables is that it is hard to put a wrapper around environment variables. I.e. it is hard to "call a function" to set environment variables.

However, I have to parse out what I mean by the terms above.
Remember: I am talking about scripting, in shell and Perl, etc.
"Calling a function" in a shell script usually means executing a child process. And, by definition, a child process dos not pass environment variables back to its parent.
Now, of course, in every scripting language worth its salt, it is possible to write a function that sets environment variables. But that's a function in the language you are running in. It's a lot harder to have, e.g. perl or bash call a csh function, and have that child csh set environment variables in the parent perl or bash.
Similarly, you can source a file in csh, or "." it in bash, and hae some degree of modularization. But again it is same language.

Why do I care? Mainly because I am writing stuff in bash or perl or python, and I want to get whatever environment variables legacy csh scripts set up.
But, in general, you lose abstraction if you are constrained to call functions only written in your current language. Or, even then, if only callable via a special syntax, eg. csh's "source file" rather than just executing file.
Loss of abstraction. But, requiring a special syntax provides a but of security.You can tell who is side effectful, and who is not. Pure vs impure functions.

My clear-env script does things oppositely - it allows me to call a script in a subshell with a clean environment, but I don't necessarily see what it set up in the environment.
Similarly, my friends trick where bash can get a csh script's environment by doing something like

csh -c "source module; exec bash

is NOT a "function call". It's more like continuations.

Part of the trouble is that the whole point of processes is to isolate the parent from the child.
Except that here, the whole point is to get access tyo the child's side effects.

I think that I may need to create a family of scripts in various languages that execute or source or whatever, and then, at the end, printenv into a file or stdout - so that the parent can parse the printenv.

A better way would be to do something like stop the child process in a debugger - and then have the parent look through the child's environment with the debugger.

---
I haven't even touched on other side effects. Not just the environment, but file descriptors.

E.g. "I have a bash script that wants to call a csh script that redirects stdout and stderr - and then have the parent bash script use those settings".

Why depend on UNIX environment variables?

2011-11-12T10:32:00.000-08:00

Previously I have posted about how I find tools that depend on sourcing csh files to get environment variables set a real pain to deal with. Largely because I don't have good ways of automating such procedures, both for use and test. And also because of environment variable interference.

So, I ask myself: Q: why depend on environment variables?

Then I remember how excited I was to learn of shell environment variables.

By setting an environment variable I could arrange for a parameter to be passed from the outside world right into the middle of a tool. Without having to modify any of the interveing levels.

No need to create argument parsing code.

In fact, in Bell Labs type shells,argument parsers are implicitly created for environmrnt variables:

VAR1=val1 VAR2=val2 program options...

I hate (csh) environment based tools

2011-11-12T10:27:00.000-08:00

I hate tools that have heavy, undocumented, environment dependencies.

csh scripts seem to be the classic example. Beware of anything that says

source file1
source file2
do this
source file3
do that

where the csh files you are source'ing mainly act by setting up environment variables, but also may act by side effects such as cd'ing.

---

Why do I hate these things? They are hard to automate. Especaly to automatically test.

Really, to automate I need to insert checks into the script above after each step. At least if it is flakey. (If it is not flakey and is all working, I don't care what it does. As long as I can put t in a black box, and don't have to let its side effects escape.)

---

Why do I hate these things?

So often the are designed for interactive use. And interfere with other stuff you may be using interactvely.

Oftentimes I need to fall back to re,oving all of my interactive customizations to get something like this working in a clean environment.

---

I have a script I call clear-env that deletes environment variables, and starts up new subshells. Has saved my bacon many times

However, today I am running into problems that depend on running exactly the sit standard initialization files, .login and .cshrc, before running any other csh-&**^&**^&^-source modules.

Testing: just (start) doing it

2011-11-12T10:19:00.000-08:00

Trying to test something that I don;t know how to automate. In fact, my goal is to automate - but I can't automate it enough even to run the smallest self checking automated test. The blinking procedure only works, at all, interactively.

So, do what I can:

I can't run the program under test automatically. (Yet: I hope to change this.)

But the program under test does leave some output files, etc.

Therefore, I can automate CHECKING the output of the manual test.

Perhaps in a while I will be able to automate the whole thing.

--

It is amazing the sense of ease that even this small degree of automation brings.

hgignore

2011-11-08T11:51:00.000-08:00

hgignore:

'via Blog this'

Most version control tools have a .ignore file or ignore - .cvsignore, .hgignore, vk ignore, bzr ignore, etc.

All that I am aware of ignore fils based on pattern matching on the filename. E.g. in Mercurial:

An untracked file is ignored if its path relative to the repository root directory, or any prefix path of that path, is matched against any pattern in .hgignore.

I would like to extend this to be able to do simple queries.

E.g. I usually have an ignore rule that looks something like

*.novc/

I.e. I ignore directories that are suffixed .novc (for no version control).

This works fine, but is somewhat verbose. Plus, it gets in the way when certan tools have other conventions about names.

I should like to get the .novc directvetive out of the filename, and into a placeholder file in the directory.

E.g. if .../path/.novc exists, then ignore .../path

Q: is it there, and I do not know?

Comp-arch.net wiki on hold from October 17, 2011 - CompArch

2011-10-17T21:23:00.000-07:00

Comp-arch.net wiki on hold from October 17, 2011 - CompArch:

'via Blog this'

= On Hold =

The comp-arch.net wiki is being put on hold - or at least to a very low boil back burner -
as of Monday, October 17, 2011.

Reason: I (Andy Glew, the creator of and main contributor to comp-arch.net)
have decided to go back to work in industry as a computer architect at MIPS Technologies.

= (Pre)History of comp-arch.net =

I have long wanted to write a book that I threatened to call "The Art of Computer Architecture".
I would like it to be like Knuth's "The Art of Computer Programming",
except that I am no Don Knuth: I am willing to compromise, not necessarily provide full academic references,
if in exchange I can document the "folklore" of computer architecture - the things that hardware engineers
know or used to know, but which never seem to get written down, and which get re-invented every decade or so.

The web, and wikis in particular, provided a forum and technology to allow me to write this in small pieces.

At most of the computer companies I have worked at, in particular AMD and Intel
(but also to a lesser extent at Gould and Motorola, prior to the creation of the web)
I have created wikis like this.
Whenever other engineers asked me a question
for which the answer was known, in the literature and/or folklore,
but not necessarily easily accessible,
I would write up a white paper or wiki page explaining the topic.
Bonus: often in so doing I would realize missing alternatives in a taxonomy,
which would lead to new inventions.

These company-internal web and wiki sites proved popular.
Several times, former co-workers who had left industry to become academics
asked me if they were accessible outside the company.
I always had to say "No".

Intel and AMD never allowed me to create public versions of such websites.
Perhaps they would have given extensive legal review - but I found the process of getting such approval a large disincentive.
The document or wiki or website would be stale before approved.

In September 2009 I left Intel to join Intellectual Ventures.
One of the conditions for my joining IV was that I be allowed to work on such a public website,
http://comp-arch.net.
(I actually created the website during the brief period between leaving Intel and starting work at IV.)
I am incredibly grateful to IV for giving me that opportunity.

Progress on comp-arch.net was slow, and probably not steady, but at least visible.
In two years I had created 300 public pages on comp-arch.net.

In addition, I created a certain number of private wiki pages, sometimes on topics that I thought might be worth patenting,
sometimes because I was afraid that disclosing the topics I was writing about might create conflict with IV.
Even though my employment agreement might give me the right to work on something in public,
I would not want to get in the way of my employer's business or marketing strategy.
Such conflicts would have loomed very large for Intel
- I would have had trouble writing honestly about Itanium at the time when Itanium was Intel's main emphasis
- and were much less of a problem for IV,
but still FUD and self-censorship were an impediment
to work on comp-arch.net.

However, I say again: I am immensely grateful to Intellectual Ventures for giving me the chance to start working on comp-arch.net.
THANK YOU, IV!!!!
If I was confident I could stay state-of-the-art as a computer architect while continuing to work on comp-arch.net
and with Intellectual Ventures, I would keep doing so.

= Present of comp-arch.net =

For reasons such as these I left Intellectual Ventures to return to work in industry as a computer architect.
On October 17, 2011, I joined MIPS Technologies.

At MIPS I do not expect to be able to write pages on comp-arch.net and post them in real time.
I will continue to try to work on comp-arch.net in private,
and occasionally seek approval to make stuff public.

= Working on the Wiki =

I will also take this opportunity to work on the technology of comp-arch.net.

In 2009 I started comp-arch.net using mediawiki.

I have long wanted a better wiki technology. My wiki wishlist is documented elsewhere on this wiki, and other places.
It includes better support for drawings,
and better support for melding of public and private content
- since it appears that such restrictions will be something I have to live with for the foreseeable future.
The computer hardware industry is not "open" as the wiki philosophy would have it,
except possibly within companies.

= Future of comp-arch.net =

As mentioned above, I hope to continue working on comp-arch.net,
making stuff public occasionally, when permitted.

Plus, if ever I retire, I hope to continue this labor of love.

= It's not just about me! =

Although I have been the main contributor to comp-arch.net,
there have been other contributors.

For example, Paul Aaron Clayton has made some contributions.

I hope that others can continue to work on comp-arch.net
during this time when I must leave it on hold.

If you are interested, please contact me, and I will arrange for access.

(I may need to do a bit of wiki work to separate the old stuff from new stuff.)

= Au revoir, et à bientôt =

I hope to see myself working on comp-arch.net again.

But for the moment, I am excited to be working towards actual shipping product again at MIPS.

perlsec - Perl security

2011-10-16T21:51:00.000-07:00

perlsec - Perl security:

'via Blog this'

More of the same.

This is probably stale.

Mint to Quicken 2011

2011-10-14T13:21:00.000-07:00

Mint to Quicken 2011:

'via Blog this'

I would be posting this on a Mint.com forum, but I don't want to bother with registering, so I will post it here.

I am yet another person who would like to synch Quicken from Mint, and possibly vice versa.

Although just being able to take transactions from Mint into Quicken would be wonderful. A backup.

In my case, although I am a past Quicken user, I am not currently. Not even a Mint user. I use Yodlee. I would consider switching to any product that allowed me to keep both online and offline accounts.

Google Plus Traffic Drops, 1269% Gains Erased

2011-10-12T10:57:00.000-07:00

Google Plus Traffic Drops, 1269% Gains Erased:

'via Blog this'

Google+ is declining.

But I am still using Google+.

For one big reason: the "circles" provide better access control than LinkedIn or FaceBook.

Why do you want access control? Well, it often becomes obvious, looking at LinkedIn or FaceBook updates, when a person from company 1 is interviewing with company 2. Now, you can often turn off the automatic notification - but I know former coworkers/managers who proactively searched LinkedIn and FaceBook, to see if people they knew had suddenly become, e.g. linked directly to people in other companies, or even rivals within the same company.

I.e. YOU SHOULD NOT ENTER JOB INTERVIEW CONTACTS IN LINKEDIN OR FACEBOOK!!!

(Not if there is a possibility that your present employer might retaliate.)

(Yes, there are limited fixes for this in LinkedIn and FaceBook. None satisfactory.)

Now, Google+ circles may help here. Except, as is typical with so many Google apps, they don't scale, in the user interface.

E.g. I have separate Google+ circles for all companies I used to work for, as well as old schools, etc. But when you reach more than a dozen circles, they become a pain to deal with. I currently have 24 circles - that's too many for Google's user interface. It needs some sort of hierarchy - e.g. a meta-circle of Companies containing several sub-circles of particular coompanies, and so on.

As is typical with so many Google apps, the user interface doesn't scale. People repeat, over and over and over again, the mistake of providing a flat set of categories (Google+ circles, Gmail labels), rather than providing structure and nesting. I can just imagine the "data driven" conversation at Google: "prove that people need more than 8 circles", "prove that people want nested circles and labels".

Colorado College | Block Plan

2011-10-11T10:04:00.000-07:00

I learned about the Colorado College Block Plan from my daughter's school counselor. Instead off juggling 8 classes at a time, take one class at a time, intensely.

I find this interesting and attractive - this is almost, for example, how I got into computers, via a summer session Concordia University organized for high school students in the Montreal region.

The school itself has the usual issues with small liberal arts colleges versus universities.

Load-linked/store-conditional (LL/SC)

2011-10-01T20:34:00.001-07:00

http://semipublic.comp-arch.net/wiki/Load-linked/store-conditional_(LL/SC)

The load-linked/store-conditional instruction pair provide a [[RISC]] flavor of [[atomic RMW]] [[synchronization]], emphasizing primitives which can be flexibly composed. It can be viewed as a minimal form of [[transactional memory]].

Part of the [[RISC philosophy]] was to espouse [[load/store architecture]] - instruction sets that separated load and store memory operations
from computational or ALU operations such as add or increment. This works fine for single processor operations, but runs into problems
for multiprocessor synchronization.

== Pre-LL/SC ==

After years of evolution, prior to the so-called [[RISC revolution]]
multiprocessor synchronization instruction sets were converging on simple [[atomic RMW]] instructions such as
[[compare-and-swap]], [[atomic increment memory]] or [[fetch-and-add]] and other [[fetch-and-op]]s.
Now, these atomic RMWs can be seen as composed of fairly simple primitives, for example:

[[locked increment memory]]
begin-atomic
tmp := load(MEM)
tmp := tmp+1
store( MEM, tmp )
end-atomic

However, the implementation of begin-atomic/end-atomic is not necessarily simple.

The atomicity can be provided in a simple way:

[[locked increment memory]]
tmp := [[load-locked]](MEM)
tmp := tmp+1
[[store-unlock]]( MEM, tmp )

Where [[load-locked]] may be
* implemented at the memory module
** locking the entire module
** or a limited number of memory locations at the module
** or potentially an arbitrary number of memory locations, using per-location lock-bit [[memory metadata]], e.g. [[stolen from ECC]]

or
* implemented via a bus lock

or
* implemented via a cache protocol
** e.g. an [[address lock]]: acquiring ownership of the cache line, and then refusing to respond to [[snoops or probes]] until the [[address lock]] was released
** or, more primitive: acquiring ownership of the cache line, and then acquiring a [[cache lock]], locking the entire cache or a fraction thereof

Interestingly, implementing locking at the memory module quite possibly came first, since many early multiprocessor systems were not snoopy or bus-based.

So far, so good: [[load-locked]] and [[store-unlocked]] are somewhat RISCy.

But they have a problem: [[load-locked]] and [[store-unlocked]] as separate instructions
raise certain security, performance, and reliability problems in some (but not necessarily all) implementations.

E.g. what happens if a user uses load-locked to lock the bus,
and never unlocks it?
That *might* be interpreted as giving one user exclusive access to the bus.

Obviously, one can eliminate these problems by architecture and microarchitecture.
But doing so is a source of complexity.
Many, probably most, implementations have found it easier to package the atomic RMW
so that the primitive operations are not exposed to the user

== [[Load-linked/store-conditional]] ==

The basic idea behind [[LL/SC]] is that, instead of guaranteeing forward progress with a [[load-locked]] that always succeeds,
but which may deadlock,
[[load-linked]] would employ [[optimistic concurrency control]].
Software would assume that it had worked, perform the operation that you want to be atomic,
and then try to commit the operation using [[store-conditional]].

If the operation was atomic, i.e. if nobody else had accessed the memory location load-link'ed, the store-conditional would proceed.

But if the operation were non-atomic, if somebody else had accessed the memory location, the store-conditional would fail.
And the user software would be required to handled that failure, e.g. by looping.

fetch-and-add:
L: oldval := load-linked MEM
newval := oldval+a
store-conditional( MEM, newval )
if SC_failed goto L
return oldval

Typically LL/SC are implemented via a snoopy bus protocol:
a memory location is "linked" by putting its address into a snooper.
If another location writes to it, the link is broken so that SC will fail.

Some implementations did not implement an address snooper - they might fail if there was ANY other activity on the bus.
Needless to say, this does not exhibit good performance on contended systems.

Non-snoopy implementations of LL/SC are possible.
E.g. implementing them at a memory module is possible. [[TBD]].

As with more extensive forms of transactional memory, LL/SC has issues with fairness and forward progress. It is not desirable to loop forever in the LL/SC code.
This is solvable - through much the same mechanisms as one uses to implement a [[locked atomic RMW]] with [[load-locked]].

One way amounts to converting a [[load-linked]] into a [[load-locked]] after a certain number of failures.

== Synthesizing Complex RMWs ==

The nice thing about [[LL/SC]] is that they can be used to implement many different forms of synchronization. E.g. almost any form of [[fetch-and-op]].
Say you want [[floating point fetch-and-add]] .. you can build that with LL/SC.
Whereas if you don't have LL/SC, and just have a fixed repertoire of integer [[atomic RMW]]s, you may just be out of luck.

This *is* one of the big advantages of RISC: provide primitives, rather than full solutions.

The problem, of course, is what was mentioned above: "plain" LL/SC may have problems with fairness and forward progress. Mechanisms that solve these problems
for LL/SC may be more complicated than they would be for non-LL/SC instructions.

See [[list of possible atomic RMW operations]].

== [[Remote Atomic RMWs]] ==

The "most natural" implementation of [[LL/SC]] is to pull the data into registers and/or cache of the processor on which the instructions are executing. By "the instructions" I mean those before the LL, the LL itself, between the LL and SC, the SC itself, and after the SC.

This is also the most natural implementation for locked implementations of atomic RMWs:

[[LOCK INC mem]]
tmp := [[load-locked]] M[addr]
dstreg := tmp+1
[[store-unlock]] M[addr] := dstreg

I call this the "local implementation" of the atomic RMW.

However, many systems have found it useful to create "remote implementations" of the atomic RMW.

For example, special [[bus or interconnect]] transactions could be created that indicate that the memory controller should do the atomic RMW operation itself.

For example, the [[NYU Ultracomputer]] allowed many [[fetch-and-add]] operations to be exported. They could be performed at the ultimate destination, the memory controller. But they could also be handled specially at intermediate nodes in the interconnection fabric, where conflicting atomic RMWs to the same location could be combined, forwarding only their net effect on towards the destination.

You can imagine such [[remote atomic RMW]]s as being performed by

[[LOCK INC mem]]
send the command "fetch-and-add M[addr],1" to the outside system

This is the advantage of CISCy atomic RMW instructions: they can hide the implementation.
If the interconnect fabric supports only [[fetch-and-add]] but not [[fetch-and-OR]], then the two respective [[microoperation expansions]] might be:

[[LOCK INC mem]]
send the command "fetch-and-add M[addr],1" to the outside system

[[LOCK FETCH-AND-OR mem]]
oldval := [[load-locked]] M[addr]
newtmp := oldval OR src1
[[store-unlock]] M[addr] := newtmp

For that matter, the CISC implementation migh well use [[LL/SC]] optimistic concurrency control within its [[microflow]].

It is more work to create such a [[remote atomic RMW]] with [[LL/SC]], since the very strength of LL/SC
- that the user can place almost arbitrarily complicated instruction sequences between the [[LL]] and [[SC]]
is also its weakness.
If you wanted to create a [[remote atomic RMW]] implementation that supported just, say, [[fetch-and-add]],
then you would have to create an [[idiom recognizer]] that recognized
code sequences such as:

fetch-and-add:
L: oldval := load-linked MEM
newval := oldval+a
store-conditional( MEM, newval )
if SC_failed goto L
return oldval

Actually, you might not have to recognize the full sequence, complete with the retry loop.
You would only need to recognize the sequence

oldval := load-linked MEM
newval := oldval+a
store-conditional( MEM, newval )

and convert that into whatever bus operations create the [[remote atomic RMW]].

Recognizing a 3-instruction idiom is not THAT hard.
But in general [[it is harder to combine separate instructions that to break up complex instructions in an instruction decoder]].

One might even imagine creating a fairly complete set of instructions executable on the interconnect.

=== The best of both worlds? ===

Let me end this section by describing a hybrid implementation of the CISC atomic RMWs that combines the best of both worlds wrt [[local and remote atomic RMWs]].

[[LOCK FETCH-AND-OP mem]]
oldval := [[load-locked/fetch-and-op]] M[addr]
newtmp := oldval OP src1
[[store-unlock/fetch-and-op]] M[addr] := newtmp
return oldval

If M[addr] is exclusive in the locak cache, then the [[load-locked/fetch-and-op]] and [[store-unlock/fetch-and-op]]
are equivalent to ordinary [[load-locked]] and [[store-unlock]].

If M[addr]] is not present in the local cache, then [[load-locked/fetch-and-op]] is equivalent to sending a remote atomic RMW fetch-and-op command to the external network. The [[store-unlock/fetch-and-op]] may then become a NOP (although it may be used for bookkeeping purposes).

If M[addr] is present in the local cache in a shared state, then we *COULD* perform the atomic RMW both locally and remotely. The remote version might invalidate or update other copies. However, if the operation is supposed to be [[serializing]], then the local update cannot proceed without coordinating with the remote.

== Extending the semantics ==

[[PAC]]:

(Paul Clayton added this.)

Because existing LL/SC definitions either fail or have [[undefined semantics]] if other memory operations are performed, the semantics can be safely extended without sacrificing [[compatibility]]. (While it may be possible in some architectures ([[TBD]]: check whether this is the case for Alpha, MIPS, ARM, Power, etc.) that a non-SC memory operation was used by software to cancel an atomic section, such is generally discouraged and unlikely to have been done.) Such extensibility could allow increasingly more extensive forms of transactional memory to be implemented without requiring additional instructions. While an implementation of an older architecture would not generate an illegal instruction, an architecture which guaranteed failure on additional memory accesses would guarantee either deadlock (which would simplify debugging and fixing) or the use of an already in place software fallback (which, while slower, would maintain correctness). In architectures which use a full-sized register to return the success condition and define a single success condition, that register could be used to communicate failure information.

A natural progression for such extensions might be: to initially constrain the transaction to an aligned block of 32 or 64 bytes or the implementation-defined unit of coherence (This last could cause a significant performance incompatibility but would maintain the semantics.), perhaps with a single write, then to expand the semantics to something like those presented in Cliff Click's "IWannaBit!" where any cache miss or eviction cancels the reservation (For many uses, this would require that the cache be warmed up before the transaction can succeed. If the reservation mechanism is expensive, prefetching data outside of the atomic section might be preferred over retrying the transaction.), perhaps extending writes to an entire cache line, and then to an arbitrary number of memory accesses.

Providing non-transactional memory accesses within the atomic section would be more difficult. It would be possible to define register numbers which when used as base pointers for memory accesses have non-transactional semantics (See [[Semantic register numbers]]). This definition would have to be made at the first extension of LL/SC and it might be difficult to establish compiler support.

A non-transactional extension of LL/SC would be to guarantee the success of the store-conditional under certain limited conditions. E.g., a simple register-register operation might be guaranteed to succeed, providing the semantics of most RMW instructions. Such a guaranteed transaction could itself be extended to allow more complex operations, though it might be desirable to allow a transaction that can be guaranteed to fail if lock semantics are not desired under contention. E.g., a thread might work on other tasks rather than wait for the completion of a heavily contended locked operation.

== See Also ==

* [[locked versus atomic]]
* [[Returning the old versus new value: fetch-and-add versus add-to-mem]]
* [[atomic RMW spinloops and CISCy instructions]]

Xfinity failing every afternoon 2:30-6pm approx; comcast DNS problems fixed by google

2011-09-28T18:06:00.001-07:00

Xfinity failing every afternoon 2:30-6pm approx; comcast DNS problems fixed by google

My comcast internet cvonnection was failing regularly, every weekday, starting at approximately 2:30pm, lasting until 6 or 7pm. This started happening shortly after labor day.

I conjecture that this was probably happening because schoolkids were getting off school (which in my area happens circa 2:30pm) and starting to use the net.

The failures were accompanied by error meessages of the form "DNS error... DNS lookup failure... Error 105 net:ERR_NAME_NOT_RESOLVED". That error message was from a Windows 7 machine. I also regularly have a Vista machine and an Apple Mac connected to my home network. The Vista machine occasionally worked when the Windows 7 machine did not, and the Apple Mac more frequently worked; but all regularly failed about the same time in the afternoon. Yes, I tried powering off/disconnecting/connecting only 1 machine at a time. Not a cure.

Coincidence? I think not.

I reported the problem to Comcast, who very quickly sent over a "cable guy" who apologized that my 7 year old Linksys cable modem had not been replaced. So now I have a new SMC cable modem, and the net performs much better, up to 10X faster than in earlier speed tests. This is great!

But, it did not fix the DNS problem.

My Windows 7 machine (actually, the Windows 7 laptop my employer gave me) still got DNS errors between roughly 2:30 and 7pm.

My Vista machine sometiimes ran when the Windows 7 machine failed.

And the Apple Mac seemed nearly always to work, failing only occasionally.

But the Windows 7 machine reliably failed between 2:30 and 7pm.

OK, so I get more serious. I check the DNS settings. Finally, I do what I should have done in the first place: I switch the Windows 7 machine DNS server frm "automatic", i.e. from comcast's DNS servers, to Google's DNS servers, 8.8.8.8 and 8.8.4.4.

Fixed! :-)

Conclusion: Comcast DNS servers have problems. Particularly when the kids get home from school.

But I'm happy that I got a new, faster, cable modem out of this. And it is interesting that different machines with their different OSes behaved differently. Different timeouts (DNS settings that don't appear at the usual configuration places)? BTW, the machine that failed most often is the fastest machine by far.

===

BTW, I did try fixing DNS earlier, to no avail. OpenDNS did not seem to work. But I wasn't that serious, so I did not try all possibilities. It is possible that both the cable modem needed to be upgraded, AND the DNS needed to point away from comcast's DNS servers.

Pipelined Bloom Filter

2011-09-17T13:13:00.000-07:00

http://semipublic.comp-arch.net/wiki/Bloom_Filters#Pipelined_Bloom_Filter

= [[Pipelined Bloom Filter]] =

Occasionally one wants to keep track of what (micro)instructions are in a pipeline.
For example, an aggressively speculative x86 may need to
[[snoop the pipeline]]
to detect [[self-modifying code]] that writes to instructions
that are already in the process of being executed.

A brute force technique might be to [[CAM]] all of the instructions in the pipeline.
Or to mark I$ lines or even ITLB pages when instructions from them are fetched for execution.
These can be expensive and/or complex.

This suggests a Bloom filter implementation:
set bit(s) in a bitvector according to a hash of the physical address of instructions
as the enter the pipeline.

unfortunately, a straightforward Bloom filter only ever sets bits.
It only ever accumulates. Eventually this will reduce in false conflicts being detected.

The basic idea behind a [[pipelined Bloom filter]] is to have a set of Bloom filters.
E.g. 2 1024 bit Bloom filters.
A new Bloom filter is (re)allocated by clearing it every 128 instructions.
It accumulates bits as instructions as executed for the next 128 instructions.
It is checked, but new instructions are not allocated into it, for the next 128 instructions.
It is then reallocated, and cleared.
Two such filters therefore can ping pong, providing coverage to the pipeline.

== Generalized ==

A set of K filters, used to protect a pipeline.

Use filter j for a specified period of time
- e.g. L instructions, or perhaps until B bits are set,
or C entries in a counted Bloom filter are saturated.
Switch to the next.
During this period one sets bits in the filter as new items are placed in the pipeline.

After this "allocation" period, continue to use the filter for checking, without writing new entries.

Deallocate the filter when it is guaranteed that no items inserted into the filter remain in the system, i.e. the pipeline.

== Other Terminology ==

It appears that there are some papers that use the term "pipelined Bloom filter"
to refer solely to a physical or electronic pipeline, and not the the logical structure
of overlapping Bloom filters that can be deallocated.

Google Desktop (Search) Dying

2011-09-10T10:36:00.000-07:00

Google is end-of-life-ing several products, including Google Desktop, in particular Google Desktop Search, which I use constantly, and Google Notebook and Sidewiki, which I would like to use, but which, fortunately, I decided not to become dependent on.

Google says

Desktop: In the last few years, there’s been a huge shift from local to cloud-based storage and computing, as well as the integration of search and gadget functionality into most modern operating systems. People now have instant access to their data, whether online or offline. As this was the goal of Google Desktop, the product will be discontinued on September 14, including all the associated APIs, services, plugins, gadgets and support.
Fair enough. I *am* trying to keep most of my information in the cloud. But unfortunately I do not have full connectivity - large areas of rural Oregon still do not have cell phone connectivity, voice, let alone data, and, for that matter, I am too cheap to pay for data connectivity at all times. Plus, some things I am not allowed to keep in the cloud, and

So it looks like I will have to use Microsoft Desktop Search, as built in to Windows 7, for stuff on my laptop. I prefer the Google user interface - but since Google Desktop Search will be discontinued, I don't have much choice. And because I am using Microsoft Desktop Search, I have started using Bing for my web search. Here, I still prefer the Google user interface, which I am familiar with - but Bing's user interface is more similar to MS Desktop Search, and I value consistency between Desktop and Web more than I value the more familiar Google Search interface.

I suspect that Microsoft Desktop Search cannot search my Google Chrome browser history. Just like Google Desktop Search could not search my Microsoft OneNote.

Unfortunately, this begins to look like dominoes falling. So long as I have substantial local data on my Microsoft PC, I am attracted, despite my personal preferences, to Microsoft tools like Microsoft Desktop Search, Bing, and Internet Explorer.

Not everyone will be in this situation. Some people will be purely cloud based. But, unfortunately, I am not. Yet?

I wonder if this will affect my next choice of cell phone? I was leaning towards Android, but perhaps this is enough to tilt me towards Windows 8.

Bit Interleaving, Instruction Set Support for

2011-09-05T16:22:00.001-07:00

[[Category:ISA]]

http://semipublic.comp-arch.net/wiki/Bit_Interleaving,_Instruction_Set_Support_for
= Instruction Set Support for Bit Interleaving =

== What is Bit Interleaving? ==

[[Bit interleaving]] is a very common form of multi-operand bit permutation.
It has been important enough to occasionally warrant special instruction set support.

2-way bit interleaving of A and B;

for i = 0 to N do
result.bit[2*i] := A.bit[i]
result.bit[2*i+1] := B.bit[i]

3-way bit interleaving off A, B, C:

for i = 0 to N do
result.bit[3*i] := A.bit[i]
result.bit[3*i+1] := B.bit[i]
result.bit[3*i+2] := C.bit[i]

M-way bit interleaving of A[i]

for i = 0 to N do
for j = 0 to M do
result.bit[N*i+j] := A[j].bit[i]

Note that since bit interleaving combines multiple operands into a single operand, issues of overflow may arise.
For example, the result is often used in address arithmetic,
in which case the inputs (aka the coordinates)
are probably not full width addresses.
The bit interleaving may be used in only a subrange of the input bits.

== Why Bit Interleaving? ==

See [[http://en.wikipedia.org/wiki/Morton_number_(number_theory) Wikipedia Morton numbers]].

Bit interleaving is often used as a component of hash functions.

In particular, bit interleaving of 2D and 3D coordinates in computer graphics
often produces hash functions that have better cache locality than uninterleaved coordinates used to index an array.

== Bit Interleaving Instructions ==

Intel Larrabee has 1:1 and 2:1 interleave instructions, in both scalar and vector form:

vbitinterleave11pi: 1:1 bit-interleave vectors
vbitinterleave21pi: 2:1 bit-interleave vectors

bitinterleave11: 1:1 bit-interleave scalar
bitinterleave21: 2:1 bit-interleave scalar

(See [[http://drdobbs.com/architecture-and-design/216402188?pgno=5 Mike Abrash's Dr. Dobb's article]] which comments that
"is useful for generating swizzled addresses, particularly in conjunction with vinsertfield, for example in preparation for texture sample fetches (volume textures in the case of vbitinterleave21pi".)

The 1:1 interleaving instruction obviously accomplishes 2D interleaving,
i.e. the interleaving of two coordinates for a 2D system.

The 2:1 interleaving instruction accoplishes 3D interleaving.
Or, rather, first one interleaves two coordinates, say X and Y, using 1:1,
and then one interleaves the third coordinate, Z, using 2:1.

4:1 interleaving is accomplished by two 1:1 interleaves.
However, operations on objects and spaces of more than 1D, 2D, or 3D are much less common.

== Expand (Interleave with 0) ==

Although 1:1 and 2:1 interleaving "fit" into commion instruction sets,
higher degrees of interleaving may not - too many operands may be required.

Some support may be afforded by bit expansion,
or interleaving with 0.
This takes 2 (or 3) inputs:
* the bitvector to which 0s will be inserted between elements
* the number of 0 bits to be inserted between elements
* possibly an offset to cause the result to be aligned appropriately for the last step.

The last step would be ORing the results together.
(Or equivalently, ANDing).

comp-arch.net mal-hacked - cloned, maybe broken into.

2011-08-28T19:54:00.000-07:00

Googling "glew FP16" today, I found my own website, comp-arch.net.

But I also found another website, waboba.info, that seems to be a clone of comp-arch.net.

This is probably a malware site, probably directing people to attack code, or at least trying to promote search engine scores.

It is certainly unauthorized. I.e. nobody asked me about setting it up/

It is probably a violation of the very loose copyright and licensing setup for comp-arch.net - a derivative of Creative Commons.

In a way, it is flattering that compo-arch.net might be considered worth cloning. But then again, I imagine that this sort of thing is automated by the bad guys.

If you ever use comp-arch.net stuff, beware of waboba.info, and other possible clones.

--

If anyone here has advice on steps to take, Id appreciate it.

===

Of more concern is the fact that my copyright notice,
https://semipublic.comp-arch.net/wiki/index.php?title=CompArch:Copyrights_and_Other_Intellectual_Property_Rights,
seems to have disappeared.

Now, this may have happened for innocuous reasons - such as an automatic update of the underlying mediawiki version.

But, it may also indicate that my site has been hacked.
If only to legitimize the unauthorized cloning described above.

I will investigate 0 bt that may take a while.

---

The real problem here is that I spend very little time working on this site, and I want to spend that time writing content, not administering Mediawiki.

I may need to give in and use a hosted wiki.

Register_File_Port_Reduction_using_Time-based_SIMD

2011-08-13T17:29:00.000-07:00

http://semipublic.comp-arch.net/wiki/Register_File_Port_Reduction_using_Time-based_SIMD

= Background: 4-cycle GPU SIMD instruction groups =

The most popular GPUs circa 2010 - Nvidia, AMD/ATI, Intel Gen - share the followng characteristics:
* they have [[SIMD or SIMT]] [[coherent threading]]
* the SIMD is 16-way spatially:
** i.e. each SIMD engine is circa 16 [[lanes]] wide
** although the definition of the lane varies, e.g. from 32 bit wide scalar for Nvidia to 5-way VLIW for AD/ATI
* the SIMD is 4 way temporally
* i.e. every [[SIMD instruction group]], [[wavefront]] or [[warp]], occupies the 16 lanes for 4 cycles.

This wiki page discusses the temporal aspect,
at least one specific advantage of taking at least 4 cycles peer [[SIMD instruction group]].
This is a particular case of
[[register file port reduction]].

= [[Register File Port Reduction using Time-based SIMD]] =

For simplicity, let us ignore the possibility of [[spatial SIMD]].
Let us assume that we have only one ALU,
taking 2 inputs peer cycle and producing a single output per cycle.
(Or possibly 3 inputs, if we want to consider [[multiply-add]].)
(Or more different combinations of inputs and outputs, if we are particularly aggressive.)

I.e.
dest := opcode( src, src2, src3 )

On a conventional scalar microarchitecture, this would require 3 read ports and 1 write port on the register file per cycle.
(Let's forget the possibility of architecturally requiring the registers to belong to banks with non-interfering ports.)

Now, instead, let us imagine that we are dealing with a SIMD instruction group or wavefront, i=0,3.
And let us say that it is distributed over time, 4 successive clock cycles t0..t3

I.e.
t0: dest[0] := opcode( src[0], src2[0], src3[0] )
t1: dest[1] := opcode( src[1], src2[1], src3[1] )
t2: dest[2] := opcode( src[2], src2[2], src3[2] )
t3: dest[3] := opcode( src[3], src2[3], src3[3] )

Now, instead of reading 3 separate (e.g. 32) values per cycle, and writing a single such value every cycle,
we could make each separate access 4X larger, but only do one such 4X larger access every cycle:

I.e.
t-3: src3_4x := RF.read( src3 )[0:127]
t-2: src2_4x := RF.read( src2 )[0:127]
t-1: src1_4x := RF.read( src1 )[0:127]
t0: dest_4x[0:31] := opcode( src1_4x[0:31], src2_4x[0:31], src3_4x[0:31] )
t1: dest_4x[32:63] := opcode( src1_4x[32:63], src2_4x[32:63], src3_4x[32:63] )
t2: dest_4x[64:95] := opcode( src1_4x[64:95], src2_4x[64:95], src3_4x[64:95] )
t3: dest_4x[96:127] := opcode( src1_4x[96:127], src2_4x[96:127], src3_4x[96:127] )
t3+1: RF.write( dest )[0:127] := dest_4x[0:127]

(As is typical in these discussions, we are constrained by the lack of universally understood [[slicing notation]])

This shows that you can get away with a single 4X wider read/write port,
at the cost of muxing/delay elements:

The pipeline might look like

W0.write W1.exec_0
W2.read1* W1.exec_1
W2.read2* W1.exec_2
W2.read3* W1.exec_3
W1.write W2.exec_0*
W3.read1 W2.exec_1*
W3.read2 W2.exec_2*
W3.read3 W2.exec_3*
W2.write* W3.exec_0
... ...

although of course it can be extended to be deeper, tolerating more ALU latency, etc.

= 4X Wider versus 4X Time-skewed =

This register file port reduction can be obtained in at least two ways:

* 4x wider
** by performing 4X wider reads and writes
** in a single "cycle" of RF access
** to and from 4X wider temporary registers
** and then muxing 1/4 of those wider registers in any given cycle of execution

* 4x time skewing
** by having 4 register files
** each skewed from the others by 1 cycle
** e.g. providing the same register number to each, but delayed 1 cycle for each skewing

These are very similar.

The 4X wider approach has the advantage of being very easy to express in conventional synthesized logic,
even though it might be marginally more expensive in full custom logic.
As of 2011 time skewed register files are hard to express in RTL languages.

= Why 4X? =

4X is a convenient power of two,
and [[powers of 2 are convenient in computer architecture]].

4X matches 3 reads and 1 write
for a register file with a single read and write port in any cycle.
Which conveniently matches multiply add, A:=B*C+D, one of the most common operations in graphics
- and GPUs were one of the first places this occurred.

3X could be a possibility, if restricted to [[2-input operations]].
But I suspect that 4X is just plain nicer.

Larger than 4X also a possibility. But, again, 4X is the smallest convenient size
that reaps most of the benefits.

Things you can do with a double precision multiplier

2011-07-14T07:57:00.001-07:00

Consider a processor that has hardware sufficient to do a double precision multiplication.
Or perhaps a multiply-add.

([[WLOG]] we will talk about floating point; similar discussion applies to 2X wide integer.)

A double precision multiplier overall has a multiplier capable of forming 4 single precision products.
Let us draw something like this, except using byte wide multipliers as subcomponents rather than single bit:
Compare the partial products array for 64x64 to 32x32:
XXXX/XXXX
X X/X X
X X/X X
XXXX/XXXX
----+-----
XXXX/XXXX
X X/X X
X X/X X
XXXX/XXXX

or briefly if the numbers are (Ahi+Blo)*(Xhi+Ylo)
AY BY
AX BX

the summation network is similarly larger, although the final [[CPA (Carry Propagate Adder)]] is "only" 2X wider
(more than 2X more gates, but only a bit deeper in logic depth).

Given such a double precision multiplier, we can synthesize several different types of single precision operations

* [[LINE]]: v=p*u+q
:: this is just an [[FMA]], with possibly a different arrangement of inputs
* [[PLANE]]: w=p*u+q*v+r
:: this has 2 multiplications, although the sum network must be adjusted to align the products differently. This can be achieved by shifting the input to the upper half of the multiplier array
* [[LRP]] or [[BLEND]]: w=u*x+v*(1-x)
:: This is like [[PLANE]], except the second multiplier part is calculated. Like 2X, etc. products for advanced [[Booth encoding]]?

The above uses the 4 multiplications of the double precision multiplier,
but only uses 2 of them.
We can be more aggressive, trying to use all 4 - but then the summation network needs considerable adjustment.

An arbitrary 2D outer product:
[[OUTER2]] = (a b) X (x y) =
ax ay
bx by
although this causes some difficulties because it needs to write back an output twice as wide as its inputs.

[[CMUL (Complex multiply)]]: can be achieved using this multiplier: (a+bi) X (x+yi) = ax-by + (ay+bx)i
although once again there are difficulties with alignment in the summation network.

Paradox and Consistency

2011-07-09T15:38:00.000-07:00

I am fascinated by paradox. I am interested in the possibility of logical systems which are not consistent but where the inconsistency is somehow limited, so that it does not propagate and pollute the whole system. I am unhappy with systems where, given any inconsistency, any theorem can be proven.

I suspect that there may be much existing work in this area. Certainly I am aware of Russel's "set of all sets that do not contain themselves". And with Godel (although I probably do not understand Godel as well as I would like.). I should probably research the literature.

But since this is a hobby, I thought I might begin by writing down some simple observations. Not new - not to me, and probably well known.

But fun.

Consider simple systems of statements:

A single statement system:

S0: "This statement is false." The classic Liar's Paradox. The statement is neither false nor true: some say that it reflects an extra logic value, "paradox". Three valued logic.

A two statement system:

S1: "S2 is false"
S2: "S1 is false"

This system is self referential, but not necessarily paradoxical. It might be that S1 is true, in which case S2 is false, confirming that S1 is true. Or, vice versa. Thus, it is not contradictory. Either situation is consistent. But, from the outside, we don't know which.

What should we call this? Bistable? Metastable, if more than 2 stable states? Unknowable?

A three statement system:

S1: "S2 is false"
S2: "S3 is false"
S3: "S4 is false"

This is paradoxical, in the same way that the single statement Liar's Paradox is paradoxical.

Conjecture: I suspect that be a true paradox, then the feedback loop must have an odd number of stages. Whereas to be bistable or metastable, it must have an even number of stages.

Compare to inverter rings or storage bitcells with cross coupled inverters in computer electronics.

Q: can you construct a system that has interescting self referential rings of odd and even length?

Address Generation Writeback

2011-07-06T23:32:00.000-07:00

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

= Hardware Motivation for Address Register Modifying Addressing Modes =

Apart from the software datastructure motivation,
there is a hardware motivation for addressing modes such as pre-increment or decrement.

In more generality - addressing modes that calculate an address, and then save the results of that calculation
in a register - typically one of the registers involved in the addressing mode.

Consider [[Mitch Alsup's Favorite Addressing Mode]],
the x86's [[Base+Scaled-Index+Offset]].

A succession of such instructions might look like:

;an [[RMW]]
r1 := load( M[ rB+rO*4+offset1 ] )
r1 := ... some calculation involving r1 ...
store( M[ rB+rO*4+offset1 ] := r1 )

or

; nearby loads
r1 := load( M[ rB+rO*4+offset1 ] )
r2 := load( M[ rB+rO*4+offset2 ] )
r3 := load( M[ rB+rO*4+offset3 ] )

Notice the possibility of [[CSE (Common Subexpression Elimination)]]:

For the [[RMW]] case, this is straightforward:

rAtmp := [[lea]]( M[ rB+rO*4+offset1 ] )
r1 := load( rAtmp ] )
r1 := ... some calculation involving r1 ...
store( M[ rAtmp ] := r1 )

Is this a win? It depends:
* in terms of performance, on a classic RISC, probably note: the extra instruction adds latency, probably costs a cycle.
* in terms of power, possibly

For the nearby load case, we could do:

rAtmp := lea( M[ rB+rO*4 ] )
r1 := load( M[ rAtmp+offset1 ] )
r2 := load( M[ rAtmp*4+offset2 ] )
r3 := load( M[ rAtmp*4+offset3 ] )

or

rAtmp := lea( M[ rB+rO*4+offset1 ] )
r1 := load( M[ rAtmp ] )
r2 := load( M[ rAtmp*4+(offset2-offset1) ] )
r3 := load( M[ rAtmp*4+(offset3-offset1) ] )

Is this a win? Again, it depends:
* probably not in performance
* possibly in terms of power.

As an aside, let me note that if the base address rB+rO*4 is aligned,then the subsequent addresses could use [[OR indexing]] rather than [[ADD indexing]].Which may further save power.At the cost of yet another piece of crap in the instruction set.
To avoid conundrums like this - is it better to [[CSE]] the addressing mode or not?
- processors like the [[AMD 29K]]
abandoned addressing modes except for [[absolute addressing mode]] and [[register indirect addressing mode]]
- so to form any nomn-trivial address you had to save the results to a register, and thereby were
encouraged to CSE it whenever possible.

Generalized pre-increment/decrement is a less RISCy approach to this.
Instead of encouraging CSE via separate instructions,
it encourages CSE by making it "free" to save the result ofthe addressing mode calculation.

:Let's call this [[Address Generation Saving]], or, if it modifies a register used in the addressing mode, [[Address Register Modification]]:

In our examples:

;RMW
rAtmp := [[lea]]( M[ rB+rO*4+offset1 ] )
r1 := load( rAtmp := rB+rO*4+offset1 ] )
r1 := ... some calculation involving r1 ...
store( M[ rAtmp ] := r1 )

; nearby load
r1 := load( M[ rAtnp :=rB+rO*4+offset1 ] )
r2 := load( M[ rAtmp*4+(offset2-offset1) ] )
r3 := load( M[ rAtmp*4+(offset3-offset1) ] )

Note that the nearby case that changes the offsets is simpler than the nearby case that saves only part ofthe address calculation:

;Using C's comma expression:
r1 := load( M[ (rAtmp := rB+rO*4, rAtmp+offset1) ] )
r2 := load( M[ rAtmp*4+offset2 ] )
r3 := load( M[ rAtmp*4+offset3 ] )

:: Again, [[OR indexing]] may benefit, for addressing mode [[(Base+Scaled-Index)}Offset]]

What is the probem with this?
* Writeback ports

Such an [[Address Generation Saving]] requires an extra writeback port, in addition to the result of an instruction like load.

For this reason, some instruction sets have proposed to NOT have [[address generation writeback]] for instructions that write other results, such as load,
but only to have [[address generation writeback]] for instructions that do not have a normal writeback, such as a store.

: Glew opinion: workable, minor benefit, but ugly.

Except that pre-increment/decre more general form:

Post-increment and decrement goes further, generalized in this way:
then the address calculation looks like

{ old := address_reg; address_reg := new_address; return old }

Not only does this require a writeback port for the updated address register,
but it also requires two paths from the AGU or RF to where the address is used
- one for the address, the other for the updated address_reg.

OVERALL OBSERVATION: addressing modes begin the slippery slope to VLIW.

Mitre Top 25 SW bugs

2011-07-04T16:40:00.000-07:00

http://cwe.mitre.org/top25/index.html

Rank Score ID Name
[1] 93.8 CWE-89 Improper Neutralization of Special Elements used in an SQL Command ('SQL Injection')
[2] 83.3 CWE-78 Improper Neutralization of Special Elements used in an OS Command ('OS Command Injection')

-- the top two are handled by taint propagation. "Improper Neutralization" => "quotification"



[3] 79.0 CWE-120 Buffer Copy without Checking Size of Input ('Classic Buffer Overflow')

-- handled by stuff like Milo Martin's Hardbound and Softbound.


[4] 77.7 CWE-79 Improper Neutralization of Input During Web Page Generation ('Cross-site Scripting')

-- tainting/quotification

[5] 76.9 CWE-306 Missing Authentication for Critical Function
[6] 76.8 CWE-862 Missing Authorization

-- more like real SW bugs, with no crutches like bounds checks of tainting.

-- except that we can imagine that capability systems might help here - it might be made mandatory to activate some capabilities positively, rather than passively inheriting them.

[7] 75.0 CWE-798 Use of Hard-coded Credentials
[8] 75.0 CWE-311 Missing Encryption of Sensitive Data


[9] 74.0 CWE-434 Unrestricted Upload of File with Dangerous Type

-- while we might hope that a capability system might upload such a file but strip it of all ability to do harm, experience suggests that a user will just blindly give the file whatever privileges it asks for.

[10] 73.8 CWE-807 Reliance on Untrusted Inputs in a Security Decision

-- tainiting

[11] 73.1 CWE-250 Execution with Unnecessary Privileges

-- capability systems are supposed to make it easier to implement the "Principle of Least Privilege".  However, it still happens.

-- we can imagine security tools that profile privileges - that determine what privileges have never been used, to allow narrowing the privileges as much as possible.

[12] 70.1 CWE-352 Cross-Site Request Forgery (CSRF)

-- tainting, capabilities


[13] 69.3 CWE-22 Improper Limitation of a Pathname to a Restricted Directory ('Path Traversal')
[14] 68.5 CWE-494 Download of Code Without Integrity Check
[15] 67.8 CWE-863 Incorrect Authorization

[16] 66.0 CWE-829 Inclusion of Functionality from Untrusted Control Sphere

-- tainting


[17] 65.5 CWE-732 Incorrect Permission Assignment for Critical Resource
[18] 64.6 CWE-676 Use of Potentially Dangerous Function
[19] 64.1 CWE-327 Use of a Broken or Risky Cryptographic Algorithm

[20] 62.4 CWE-131 Incorrect Calculation of Buffer Size

-- classic buffer overflow, such as Martin Hardbound/Softbound.

[21] 61.5 CWE-307 Improper Restriction of Excessive Authentication Attempts
[22] 61.1 CWE-601 URL Redirection to Untrusted Site ('Open Redirect')

[23] 61.0 CWE-134 Uncontrolled Format String
[24] 60.3 CWE-190 Integer Overflow or Wraparound

-- these two, 23 and 24, are somewhat handled by buffer overflow checking as in Hardbound and Softbound - the security flaws with integer overflow often manifest themselves as unchecked buffer overflows.

-- however, they can manifest themselves in other ways as well.


[25] 59.9 CWE-759 Use of a One-Way Hash without a Salt

Notions of Time in Computer Architecture

2011-06-29T15:10:00.001-07:00

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

Advanced computer architecture admits several different notions of time.

= Real World Time =

First, there is [[real time]] or [[wall clock time]]. Time in the real world (forgetting Einsteinian relativistic issues for the moment).

Unfortunately, the term [[real time]], which would be the best term for this, is often overloaded with the additional meaning
of pertaining to a system that must respond in real time - e.g. "Drop the rods in the nuclear power plant quickly or the nuclear fuel will melt down."
Or "adjust the aileron pitch with a few milliseconds, or the plane will stall and crash."
These applications are often called [[hard real time]], and there are also [[soft real time]] applications that have less stringent timing requirements.

Because of the use of real time in phrases such as [[real time operating system]] or [[real time response]], terms such as [[wall clock time]] may be used.

== Absolute versus Relative ==

Real time (and, indeed, other times) may be absolute or relative.

Absolute time is wall clock time, or calendar time.

Relative time is the amount of elapsed time since some other event. E.g. one might start a timer on entering a function, and read it on exit.

Obviously, you can calculate relative timer from absolute time samples.
But, it can be considerably easier to build the hardware to measure relative time that it is to measure ab solute time.
Timers used in relative timing may be in isolation, whereas clocks measuring absolute time may need to be kept in synchronization
with other clocks in other systems.

== [[Timers versus Timestamps]] ==

Oftentimes appplications do not need actual time.
Instead, what they really need is timestamps that indicate relative position.
The application may care who came first or second, but not how much time elapsed between arrivals.

Therefore, some timer architectures provide absolute time in uppper bits,
but simply indicate a unique counter in the lower bits of a timestamp.

= Von Neuman Time =

In out-of-order and speculative processors,
even when single threaded, it is often convenient to talk about the
[[Von Neumann sequence number]] or [[Von Neumann time]].

On a single threaded program, this is the sequence number at which every and any [[dynamic instruction sequence]] executes.

The [[Von Neumann time]] or sequence number for an instruction is NOT the [[wall clock time]]
at which an instruction executes.
Even on simple in-order processors, where instructions may have differing [[instruction latency]],
the VN time is not linearly related to the wall clock time.
On complex out-of-order processors instructions that are later in the Von Neumman instruction sequence
may execute earlier in wall clock time (that's what makes them out-of-order).

The [[Von Neumann time]] or sequence number may be a convenient book-keeping tool.
* it is often made available in a [[simulator]] user interface
* I have proposed using it it [[hardware data structures]] such as store buffers and schedulers.
** When I talk about an "age based scheduler", I usually mean a [[Von Neumann age]] based scheduler.
** Of course, real hardware must implement a finite number of bits, typically wrapping

== Multithreading ==

The [[Von Neumann time]] or sequence number is unambiguous for a single threaded program.

For multithreaded programs that interact, it is necessary to establish correspondences - VN1 time of thread A corresponds to VN time of thread B,
at different points if interaction.

It should be seen that this multithreaded time is a partial order. Ideally one from which a total order can be constructed.
(Although certain microarchitectural interactions may imply cycles in such a time graph.)

I know of no standard term for this [[multithreaded time]]. [[Multithreaded Von Neuman time]].

I think that it might be nice to call it [[Lamport time]],
since Leslie Lamport was a pioneer in this area.

= Pipeline Time(s) =

Any given [[dynamic instruction instance]] desn't execute at a single point in time.,
Rather, it executes in different ways at many different points in tiime:
* [[instruction fetch time]]
* [[decode time]]
* [[schedule time]]
* [[operand ready time]]
* [[execution time]]
* [[register read time]]
* [[writeback time]]
* re-execution time]] or [[replay time]]
* [[commit time]]
* [[retirement time]]

Plus of course there is the
* [[Von Neuman time]] or [[Von Neumann sequence number]] of a [[dynamic instruction instance]].

For that matter
* the [[Von Neumann time]] relative to a given thread of execution
may differe from the
* [[Von Neuman time]] relative to the processor it is executed on
because of [[timesharing]] or [[multitasking]] between threads or processors.

= Simulator Times =

Consider
* Real time of the machine on which the simulator runs: [[simulator real time]]
* [[Simulated real time]] of the workload running on the simulator: [[simulatee real time]]
* [[Von Neumann time]] or sequence number for the workload running on the simulator.

This can be fully recursive. A simulator may be ruunning on top of a simulator on top of ...

= Conclusion =

Be careful what notion of time you are talking about.
It may not be the notion of time for the person you are talking to.

[[Microarchitecture]] is concerned with [[real time]].
[[Macroarchitecture]] is concerned more with abstract time, such as [[Von Neumann time]].
Systems that have different microarchitectures and hence different real time behavior,
may execute the same [[macroarchitecture]].
But, of course, [[macroarchitecture]] features such as [[ISA]] greatly influence [[real time]] performance.

cygwin startxwin problem with multiple displays

2011-06-23T10:48:00.000-07:00

I use cygwin on my Windows PCs. Especially my tablet PC. AFAIK there is no equally good UNIX or Linux or Apple equivalent for a Microsoft Windows tablet PC. Tell me if there is. (Yes, I write and draw with the pen.))

Unfortunately, my cygwin setup has decayed - things stopped working on various upgrades, and I do not always fix the problem immediately. Here's one:

For a while, I would use startxwin to start up X Windows in Cygwin's multiwindow mode. At some point, it worked, but the xterm started by default was off obably havescreen, could not be seen. If I maximized I could find it, but when non-maximized, not seen.

Turns out that startxwin's default was to start "xterm -geometry +1+1 ...".

And I have been using multiple displays - e.g. currently have 4. Irregularly arranged. So that there is no display at +1+1 in the bounding box of all displays.

FIX: provide my own ~/.startxwinrc, with no location specified for the xterm.

--

Meta-issue: almost want a sanity check, to make sure that no windows are raised offscreen, invisibly.

Overall, there are probably a lot of such issues relating to assumptions about screen geometry being regular and rectangular, that no longer hold in the world of multiple displays.

---

Another meta-issue: took a while to find out where the xterm was coming from.

It would have been nice to have an audit trail that allowed me to find where the xterm came from.

Similarly, to find out where its geometry parameter came from.

As it was, I just guessed "startxwin". But I am embarassed to say how long it took...

A vocabulary of terms for memory operation combining

2011-06-19T18:14:00.000-07:00

There are many different terms for the common optimization of memory operation combining or coalescing.
See the discussions of the [[difference between write combining and write coalescing]],
as well as [[write combining]] and [[write coalescing]],
and [[NYU Ultracoomputer]] [[fetch-and-op]] [[combining networks]].

Here is a by no means complete list of such terms:

* [[combining]]
** [[write combining]]
*** [[write combining buffer]]s
*** [[write combining cache]]
** [[read combining]]
** [[fetch-and-op combining]]
*** [[NYU Ultracomputer]] [[fetch-and-op]] [[combining networks]]

* [[coalescing]]
:: on GPUs...
** [[write coalescing]]
** [[read coalescing]]

I have not heard anyone talk about fetch-and-op or atomic RMW coalescing
as distinct from the historic
[[NYU Ultracomputer]] [[fetch-and-op combining]].
But I suppose that inevitably this will arise.

* [[squashing]]
:: mainly refers to finding that an operation is unnecessary, and cancelling it - or at least the unnecessary part
** [[load squashing]]
::: On P6, referred to a cache miss finding that there was already a cache miss in flight for the same cache line. No need to issue a new bus request, but the squashed request was not completely cancelled - arrangement was made so that data return from the squashing cache miss would
** [[store squashing]]
::: I am not aware of this being done, but it could refer to comparing store addresses in a [[store buffer]], and determining that an older store is unnecessary since a later store completely overwrites it (and there would be no intervening operations that make it visible according to the [[memory ordering model]]). (Actually, I am not sure that there could be such, but I am leaving the possibility as a placeholder.)
::: [[Write combining]] accomplishes much the same thing, although [[store squashing]] in the store buffer gets it done earlier.
::: Note that this is similar to [[store buffer combining]] - combining entries in the store buffer, separate from a [[write combining buffer]].

Again, I have not heard of fetch-and-op squashing, although I am sure that it could be done, e.g. for lossy operations such as AND and OR (a later fetch-and-OR with a bitmask that completely includes an earlier...).

* [[snarfing]]
:: I have usually seen this term used in combination with a [[snoopy bus]], although it can also be used with other interconnects. [[Read snarfing]] means that a pending request from P1 that has not yet received the bus in arbitration observes the data for the same cachelines from a different processor P0, and "snarfs" the data as it goes by.
Depending on the cache protocol, it may be necessary to assert a signal to put data into [[shared (S) state]] rather than [[exclusive (E) state]].

I am not sure what [[write snarfing]] would look like.
An [[update cache]] is somewhat like, but it updates an existing cache line, not an existing request.
I.e. an update cache protocol snarfs write data from the bus or interconnect to update a cache line.
Whereas a pending load can snarf data either from read replies or write data transactions on the bus or interconnect.
I.e. a read can snarf from a read or a write.
But does a write "snarf"?
More like a write may combine with another write -
[[snoopy bus based write combining]],
as distinct from [[buffer based write combining]].

Difference between write combining and write coalescing

2011-06-19T18:13:00.001-07:00

Write combining

2011-06-15T23:24:00.000-07:00

http://semipublic.comp-arch.net/wiki/Write_combining#WC_policies

Many processors have [[write combining]] support. The [[WC buffers]] and [[USWC memory type]] that I (Andy Glew) added to the Intel P6 are probably by no means the first, or last, such feature. Although arguably pretty successful.

= The basic idea of write combining =

Say that you have a memory bus of width N, e.g. N=64b.

But say that software, for its own nefarious reasons, is writing only in size M, ME.g. say that software is writing a byte at a time.

Simplistically, each such byte write would be wasting 7/8 of the 64b bus.

The basic idea of a write combining buffer is to have a buffer at least N bits wide, with subset validity bits
- e.g. 64 bits, with 1 bit per byte indicating that a byte has been written.

With the valid bits initially empty, as you write to the WC buffer you place data in the corresponding byte, and set the corresponding byte valid bit.

At some later point in time, you may evict the WC buffer. If all of the bytes have been written, you use a single efficient N=64b write. If not, you do some sort of [[partial eviction]].

If the silly software completely overwrites the WC buffer, you have used 8/8 of the bus bandwidth, rather than only 1/8.

== A more realistic example ==

There may be several WC buffers,
each a full cache line (e.g. 64B (not bits, but Bytes) in length.

The [[bus]] is optimized for 8-chunk bursts.
The bus may permit full utilization if 64B burst transfers, but smaller transfers are less efficient es
- and, in fact, in some systems occupy exactly the same number of cycles.
Let's say 8 cycles - 8x8B.

The processor may be clocked faster than the bus. E.g. 8GHz, versus a 1GHz memory bus.

Processor does 64b stores to uncached bit not memory mapped I/O.
Each creates a [[bus write partial line]] command,
occupying 8 cycles on the bus in our example.

If, instead, we use a write combining buffer,
the first 64b/8B store may allocate the [[WC buffer]],
storing data in it
and and set the byte valid bits to
11111111_00000000_00000000_00000000_00000000_00000000_00000000_00000000

The second 64b/8B store may hit the WC buffer, and set the byte valid bits to
11111111_11111111_00000000_00000000_00000000_00000000_00000000_00000000

And so on..

When the [[wrte combining buffer]] is full, and when it is eventually evicted,
then a [[bus write full line]] transaction would be done.
In our contrived example, occupying the same 8 cycles as the bus write partial line transcation for each of the stores separately.
Bottom line: 8X speedup.
1/8 the bus occupancy - freeing up the bus for other use.
Etc.

The point of this exercise was to show that write combining does not need to work with tiny 64b buffers.
Full cache line buffers are possible, and, in fact, are what the Intel P6 and most subsequent x86 machines have.
Also, clocking the processor faster than the bus may motivate WC.
Also, it's not just a question of silly software doing 8b writes: even software doing 64b writes may benefit.

Real world example: on the Intel P6 family, a 64B full cache line transfer ([[BWL (Bus Write Line)]] occupied circa 5 cycles.
A [[BWP (Bus Write Partial)]] transaction occupied 3 cycles.
So the speedup is not quite so extreme as in the contrived example, but is still significant.
Even if the partial writes had been optimized, integer code could only do 32 bit stores, and the bus was 64b wide.

== Write Combining versus Wide Instructions ==

Some may consider that write combining is a poor substitute for having wider instructions.
I.e. instead of building a complicated write combining mechanism, why not create full cache line wide instructions such as
* Load/Store 64B (512b) between vector registers and memory
* [[Load/store-multiple-registers instruction]]

Now, I am nearly always an advocate of explicit software control, even here.
I am quite in favor of vector instructions,
and less so, but still positive, on load/store-multiple-registers.

But history shows: Intel x86 had only 32b integer registers
and worked quite successfully with write combining for more than 5 years before [[x86-64]], 1996-2002;
and even at the time I am writing this does not have 512b/64B full cache line registers.
(Proposed in LRBNI, but not yet implemented.)
I.e. history shows that you can be successful for quite a long time without explicit instruction set support.

Explicit instruction set support may have advantages in other ways.
But it also has costs, e.g. context switching the vector registers.

== Write Combining versus Writeback, DMA, ... ==

Many other arguments have been made against write combining.

E.g. Why not just use [[writeback (WB)]] memory everywhere?
A: although there is more and more cache coherent I/O, at the time I am writing this uncached memory for framebuffers, etc.,
is still very common.

E.g. Why not use DMA engines? Or smart I/O devices such as GPUs?
A: not a complete answer, but basically these do not always exist.
Moreover, I am writing this at a GPU conference,
where the designers of AMD's Llano APU (CPU/GPU hybrid) memory subsystem
expressed, in conversation, the desire for better uncacheable / write combining performance.

Bottom line: the need for write combining is not going away.

= WC policies =

== P6 USWC ==

Intel P6 family USWC memory manages write-combining buffers
in a weakly ordered manner.
E.g. you can write A0, B0, A1, B1, etc. to two different cache lines,
and two different WC buffers will be allocated.
No account is taken, for USWC memory, of write ordering.
E.g. line B may be evicted first, so that B1 is observed before A0.

Eviction is almost random - from the point of view of a programmer.
Certain events are defined to cause evictions, including:
* interrupts
* I/O instructions
* uncacheable memory accesses (to [[UC]] memory) (which are possibly memory mapped I/O)
* possibly certain fence and flushes operations (althohgh x86 fence instructions were added later).

The motivation for these USWC WC buffer eviction policy
was mainly to try to make it look transparent when coordinating with a GPU,
sending commands via MMIO or I/O.

Note: there was no guarantee of timeliness, no guarantee that USWC writes would eventually be flushed out,
e.g. to the framebuffer. Except that mt systems at the time had regular timer interrupts.
Now, circa 2011, [[tickless OS]]es are common.
It might be advisable to have hardware periodically flush USWC.

Carl Amdahl observed that USWC was a cache - a small, non-coherent, cache - not a buffer.

== [[Left to right write combining]] ==

An alternative to P6 USWC's WC policies
was [[left to right write combining]].

This would typically only allocate a WC buffer that wrote to byte 0 of a line.
(Although starting in the middle can be imagined.)

It would perform write combining so long as the write was adjacent to, and to the right, of bytes already written in the WC buffer.

If a write was performed that was not adjacent and to the write, the WC buffer would be evicted immediately.

[[Left to right write combining]] has the putative advantage that it works with some forms of memory mapped I/O - devices for which the registers are designed so that they are written from low address to high. Typically, parameters, with the last location written triggering a side effect.
This is actually a very attractive feature, since it allows efficient MMIO for all devices designed in this way.
Unfortunately, it is not compatible with all MMIO devices - some MMIO devices actually look at the size of the bus transaction, interpretinbg that as an aspect of the MMIO command. (You might consider this stupid, but... )

[[Left to right write combining]] also has the advantage that it preserves write ordering So long as evictions are done left to write.

In an ideal world, there would be two write-combining memory types: left to right, and USWC.
Unfortunately, in P6's [[feature diets]] we had to choose only one, and USWC was it.
USWC is better for certain types of framebuffer worklolads.
[[Left to right write combining]] for well behaved MMIO.

== WC for WB ==

The previous two topics, USWC and [[Left to right write combining]],
deal with write combining with what is fundamentally uncached memory.

Write combining can also be used for [[WB (Writeback)]] memory.

If weakly ordered, this is straightforward.
Similarly, it is straightforward if used to optimize writethrough traffic,
e.g. from a WT L1$ to a WB L2$.
So long as exclusive owne
rship has already been obtained.

However, write combining for a store-ordered memory system like [[TSO]] or [[processor consistency]]
is more of a challenge.

TBD: seek the patents on this. Public info.

= Eviction Mechanism =
At some point it is necessary to evict a write combining buffer.

If the buffer is completely written, then evicting it,
on USWC memory, is straightforward:
* use a [[BWL (Burst Write Line)]] bus transaction that writes the entire line
:: (Caveat: some systems require obtaining ownership before writing like this. But nt P6.)

If the buffer is not completely written, you can use any of the following
* read the missing bytes using a [[BRL (Burst Read Line)]], merge, and then write using [[BWL]].
** works but potentially uses MORE memory traffic than not write combining
* using the most efficient sequence of [[partial writes]] possible
** e.g. using 64b [[write bytes under mask bus transaction]]s - eliding empty chunks
** some systems do not have [[write bytes under mask bus transaction]], but only support 8b, 16b, 32b, etc. partial writes. A state machine can emit a sequence of these
*** note: this probably violates any pretense of the original writes being atomic, particularly if not aligned
* ideally, use an efficient [[BWLM (Burst Write Line under Mask)]] bus transaction.
** this might consist of 4 or 8 data chunks, along with a data chunk that contains a 64 bit mask for the operation.
*** Issue: is the mask attached to address or data? Possibly both. Possibly there is no distinction.
*** Aside: in [[BS: Bitmask Coherency for Writeback Caches]] I discuss the possibility of having two bitmasks, dirty and clean, on such a bus transaction. Possibly with a read version.

= TBD - fatigue =

I'm too tired to finish this. Let me just list some topics:

* [[WC buffer as a store buffer extension]] - constraining eviction order if you want to maintain processor conssistency.

* The [[difference between write combining and write coalescing]]

Writethrough with write allocate versus no write allocate

2011-06-15T22:35:00.000-07:00

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

Write-through caches can be write allocate or no-write allocate.

A no-write allocate write-through cache can only put data in the cache on a read.
A write that misses is written through, to the next cache level or memory, but not stored in the cache.

A write-through with write-allocate cache, if it does not read clean data,
must necessarily have valid bits for bytes or words within the cache line.
Unless the writes can only be cache line sized.

Actually, we can imagine a write-through with write allocate cache, that reads clean data,
and thereby avoids the need to have byte valid bits.
I was about to say that this somewhat misses the point...
and it certainly would on "write and forget" systems.
But, some systems must obtain ownership even on write-through caches.
E.g. the IBM z-series (descendants of the System 360)
must ensure that all other copies of a cache line are invalidated before
"performing" the write.
If you have to do that, you might almost as well obtain the clean data,
and not have to maintain byte dirty bits.

Contrast:
* P6 family: the write-through invalidates other caches, but the data can be read from the local cache before the remote invalidations. Do not need to get a reply from the invalidation.
* IBM family: must invalidate before forwarding locally; i.e. must wait for the invalidation to be complete.

Dynamic shifts

2011-05-18T06:40:00.000-07:00

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

This essay isn't finished - need to collect more info.

= [[Why dynamic shift count instructions are often slower than constant shift count instructions]] =

I don't know.

I don't even know if they are, in general. Terje Mathisen says that they are in his experience,
and on at least two anecdotal machines dynamic shifts have been a pain. But I am aware of no fundamental reason.

TBD: survey.

== Possible Circuit Reasons - Unlikely ==

Paul Clayton suggests that knowing the static shift count could be used to do early set up of a shifter, whereas dynamic shift counts may arrive too later. This is possibly true, even probably true - it _could_ be used as an optimization. But in my experience I have not seen this done. Ditto Mitch Alsup's.

Now, a very basic reason is that a shift by a small constant, e.g. a shift left or right by 1, can be much cheaper. On a 4 pipeline machine I can easily imagine building 4 narrow shifters but only one general shifter. Similarly, I can imagine converting <<1 into ADD instructions. I.e. I can imagine why we might have more small width shifters that a full width shifter. Similarly for latency. But I still don't see a generic reason.

== x86 dynamic shift - flags hassle ==

The x86 OOO/P6 family slowness for variable shifts is largely due to the fact that a variable shift by zero was defined be a NOP. On a 2-input OOO machine, this necessitated a third input for the old flags, and a second uop:

tmp := concat( value_to_be_shifted, old_flags )
dest,new_flags := shift( tmp, shift_count )

or (with lower latency for the shift, and a widget uop to handle to flag selection)

dest,tmp_flags := shift( value_to_be_shifted, shift_count )
final_flags := select_shift_flags( tmp_flags, old_flags)

If the instruction had been defined without this 0-NOP flag business, e.g. if you set a flag combination on zero rather than inheriting one, it would have been faster.

Now that 3-input datapaths are common for multiply-add, this could be undone. Perhaps it has already been?

== Gould - no dynamic shift instruction ==

E.g. on Gould we did not have them: we had to resort to the moral equivalent of self-modifying code, generating the shift by constant in a register and then using the execute register instruction.

== Discussion ==

Apart from this, why are dynamic shifts slow? What machines make them slow?

A dynamic shift is always going to be more expensive than a shift by 1 or 2 bits. At least, you can probably build 4 shift by 1s, but only 1 dynamic full width shifter, on a typical datapath. But not necessarily more expensive than a shift by a large constant, unless tyhe sort of optimization Paul was talking about is done. Which has not been the case in my experieence.

But, you are right: dynamic shifts are often penalized.

This sounds like an essay for the comp-arch.net wiki.

What machines make dynamic shifts slower than, say, a shift by 29?

Why?

Is it fundamental, or is it an accident of the instruction set, as it was for x86 and Gould?

What would an instruction set definition of dynamic shift look like that did NOT causse such implementation artifacts look like?

ISO ACLs for Wiki; considering Drupal

2011-05-15T12:51:00.000-07:00

I have long wanted ACLs for wikis, both at companies like Intel and AMD, and on comp-arch.net.

I punted ion this when I set up comp-arch.net, with the semipublic and public areas. Abandoning the public areas when I got spammed.

But now my need is growing again. I am wiki'ing things that may get patented, so they cannot be initially public --- but it is too much hassle to write them up privately, and then later post to a wiki, a year or so later when the patent is published. I want to write them up in the wiki once, and then have them go public when allowed.

Setting up a private wiki is a pain, because wikidmin wants to be shared. It's a pain to have to propagate changes made to a template on a public wiki to a private wiki, and vice versa.

---

This became annoying enough today that I considered switching to a CMS like Drupal or Joomla, from mediawiki.

Transferring the mediawiki content will be a hassle.

---

I''m starting to dream of a file based wiki. Each wiki page, or attachment, living in a filesystem. OS filesystem security and ACLs. Webdav if appropriate. Wikiserver running as OS user accounts - requiring setuid CGI scripts or the equivalent.

The content files being separate from the wiki web presentation engine. E.g. one might have a CMS-like web system, or a wiki system, that interpret the files separately. In which case changing the CMS/wiki engine is just changing the scripts.

2011-05-11T13:27:00.000-07:00

Love it!!!!!

http://www.math.utah.edu/~palais/pi.html

Pi is wrong.

Not mathematically - but observes that setting some other symbol to be what we now call 2pi or 6.28... leads to many simplifications in formulae, many fewer factors of 2 - and probably far fewer errors.

The astounding thing is how recent the modern use of pi=3.14... emerged. Of course, mathematicians back to the Greeks knew the concept, but the convention arose only in the 18th century, and stuck when Euler used it, borrowing it from a much less prominent Welsh mathematician. (I want to say "an obscure Welsh mathematician, William Jones, but I'll get in trouble for that.) Euler apparently previously used p/c, where p is the periphery and c the radius of any circle.

I'm just piling on to a flash mob, and I'm arriving late. But, what the heck.

Potential customers for tagged memory

2011-04-18T20:47:00.001-07:00

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

There are many potential customers for [[tagged memory]] or [[memory metadata]].
I have long maintained a list (or, rather, lists, since I have had to recreate these lists on 3 occasions)
of uses for tagged memory.
Here is a list that is by no means complete (previous versions of this list have exceeded 20 items).

Which should be allocated the tags?
Obviously, my favorite idea...

Glew opinion: tagged memory should be microarchitecture, not macroarchitecture. If there are physical tags, it is a good idea to be able to use them to speed things up. But there should always be a fallback proposal that does not depend on having main memory tags. See Milo Martin's Hardbound for an example of how to have metadata in memory, without tags.

* Tagged memory to identify data types - integer, floating point ...
:* Problem: there is an infinite number of types ...
:* 1..n bits. Per qword? Maybe per byte?
* Tagged memory to aid in [[garbage collection]]. [[Read and write barriers]].
:* 1 bit (or more) per minimum allocation unit, 1-4 words
* Tagged memory to aid security, e.g. to create [[non-forgeable pointers]] as in the IBM AS400
:* This may well be my favorite use of only a single bit of tagged memory.
:* 1 bit per pointer - 64 or 128 bits
* Tagged memory for [[taint or poison propagation]], as in [[DIFT (Dynamic Information Flow Tracking)]]. E.g. Raksha.
:* 1 bit per ... word? byte?
:* Raksha uses multiple bits
* Tagged memory for [[transactional memory]] support
:* 1 bit per ... many TM systems use cache line granularity, although smaller better
* Tagged memory for [[debugging]]
:* 1 bit per ... can deal with coarse granularity, e.g. by trapping, determining not interested, and going on.
* Tagged memory for [[performance monitoring]] - e.g. to mark all memory accessed in a time interval.
:* 1 bit per cache line
* Tagged memory for [[uninitialized memory]]
:* 1 bit per ... byte? word?
* Tagged emory for [[synchronization]] of parallel programs. E.g. [[full/empty bits]].
* Fine grain [[copy-on-write]] data structures
** [[Myrias style parallelism]]
:* 1 bit per ... byte? word? ...

Heck, I suppose that conventional width oriented ECC can be considered a form of tagged memory. And although ECC is common, at least at the time of writing it is not in 99% of all PCs. It causes problems enough to warrant the invention of [[Poor Man's ECC]], a non-width oriented implementation of ECC that avoids physical tagged memory.

Wide operand cache

2011-04-18T20:37:00.001-07:00

http://semipublic.comp-arch.net/wiki/Wide_operand_cache
= By Microunity =

The [[wide operand cache]] is a concept originally by [[Microunity]] =

Situation:
* you want to design a RISC machine, with "naturally 32 or 64 bit regissters.
** or even 1024 bit registers - no matter how wide you go, there will nearly always be a reason to have significantly wider operands.
* but you also want to support "simple" instructions that just happen to have very wide operands.

See [[#Examples of instructions with wide operands]].
For the purposes of this discussion, we will consider [[BMM (bit matrix multiply)]].
BMM wants to have one, say, 64 bit operand, and a second operand, the matrix, that is 64x64 bits in size - 4Kib.

Defining an instruction such as
BMM destreg64b := srcreg64b * srcreg4x64b
could be possible - but it has many issues:
* how many 64x64=4Kib operand registers do you want to define? 1? 2? 4?
* you probably do not want to copy such a wide operand around - instead, you might want it to live inside its execution unit
etc.

The [[wide operand cache]] approach is as follows: define an instruction with a memory operand
BMM destreg64b := srcreg64b * M[...]
* You may spercify the memory operand simply as register direct, M[reg], or you may define it using a normal addressing mode such as M[basereg+offset], or even using scaled indexing.

Conceptually, the wide operand is loaded before every use:
BMM destreg64b := srcreg64b * M[addr]
tmp64x64b := load M[addr]
destreg64b := srcreg64b * tmpreg64x64b

However, we may avoid unnecessary memory traffic by caching the wide operand.

This leads to the basic issue: [[#TLB semantics versus coherent|]].

= TLB semantics versus coherent =

The [[wide operand cache]] concept admits a basic question:
* do you snoop the wide operand cache, keeping it coherent with main memory, so that if somebody writes to a cached wide operand it is reflected in the next execution of the instruction?
* or do you use "[[TLB semantics]]", i.e. making it a [[noncoherent cache]], requiring the user to explicitly invalidate it (requiring an [[invalidate wide operand cache(s) instruction]].

If coherent then an implementation can vary the number of wide operand cache entries transparently.

If noncoherent then not only can the number of entries be detected, but also you run the risk of getting different answers depending on the context switching rate.

[[Glew opinion]]: I prefer coherent, but would live with noncoherent if necessary.

= So Close... =

Frustrating anecdote: at AMD I was working, with Alex Klaiber, out how to support instructions like with very wide operands, such
as [[BMM]]. My whiteboard was full of scribblings, with the basic question of [[#TLB semantics versus coherent|]].

I then went to a meeting where Microunity presented their patents.

So close... Actually, probably off by 5-10 years. But I was following a path that I did not know had been trailblazed...

= Examples of instructions with wide operands =
Any instruction that has an operand that is significantly wider than some of its inputs,
and which either tends to be constant, or which tends to be modified in place,
is a candidate for a [[wide operand in memory]] implemented via a [[wide operand cache]].
For that matter, one could have wide operand instructions whose operands are all pseudo-regosters in a wide operand cache.
* [[BMM (bit matrix multiply)]] - 64b X 64x64b
* [[vector-matrix instructions]] - N X NxN
* [[permutation index vector instruction]] - Nbits*log2(Nbits)
* [[permutation bit matrix instruction]] - really a form of [[BMM]]
* [[superaccumulator]] - 32 bit - thousands ...
* [[regex instructions]] - with large regex operands that can be compiled
* [[LUT (lookup table) instructions]]
* [[texture sampling]]
* [[interpolation instructions]]
* [[CAM instructions]]

TBD

New models for Industrial Research (in reply to: The death of Intel Labs and what it means for industrial research)

2011-04-09T12:09:00.000-07:00

Matt Walsh's post on "The death of Intel Labs and what it means for industrial research" must have struck a nerve with me, because I have spent a morning writing a long response.

BRIEF:

Intel's lablets have been shut down, not the labs. I helped started Intel's labs, but not the lablets. It's not clear how effective the lablets ever were. Same for the labs. I discuss models for research, including

(1) Academia far-out, and industry close-in (nice if it were true)

(2) Google's 20%

(3) IBM and HP's business group motivated research labs

(4) Some of my experience from Intel, in both product groups and research labs

(5) Open Source (if ever I can retire I would work on Open Source. But I have not yet managed to find a job that allowed me to work on Open Source.)

I think my overall point is that each of these models works, sometimes - and each is subject to herd mentality, deference to power, etc. Perhaps there is room for new ways of doing research, invention, and invention - a new business model.

Finally, I mention briefly, providing links to quotes, Intellectual Venture's website. With a disclaimer saying that I don't speak for IV, although obviously I have hope for its potential since I left Intel to join IV.

DETAIL:

Intel recently announced that it is closing down its three "lablets"
in Berkeley, Seattle, and Pittsburgh

So it goes. This might be unfortunate. None of the lablet work in my
field, computer architecture, has caught my eye, although I did enjoy
interacting with Todd Mowry's group in Pittsbugh on Log Basse
Architecture (I had come up with Log Based Microarchitecure at
Wisconsin).

However, it is wrong to say that the lablets reflects the death of
Intel Labs. I was involved with the creation of Intel Labs, circa
1995 inside Intel.

This was historically a hard sell, since Intel had been *created* by
refugees from the research labs of other companies. It was a
touchstone of Intel culture that Intel would never do ivory tower
research not relevant to product groups.

E.g. while campaigning for the creation of Intel Labs I created a
slideset that said "Intel must start doing our own research in
computer architecture, now that we have copied all of the ideas from
older companies." I am not sure, but it seems like Craig Barrett may
have seen these slides when he was quoted in the Wall Street Journal
''Now we're at the head of the class, and there is nothing left to
copy,'' Mr. Barrett was quoted as having said.

(Ironically, DEC used this to justify their patent infringement
lawsuit against Intel circa 1997 -- but when I created these slides I
had IBM in mind, not DEC, since I freely admit that much of my work at
Intel was built upon a foundation of IBM work on RISC and Tomasulo
out-of-order. Not DEC Alpha. Perhaps I should never have created
those slides, but it put the case pithily, it helped justify the
creation of Intel Labs. And *I* did not quote them to the WSJ.)

Ref: http://query.nytimes.com/gst/fullpage.html?res=9F02E3D61F39F937A25756C0A961958260&pagewanted=2

Matt says "Before the Labs opened, Intel Research was consistently
ranked one of the lowest amongst all major technology companies in
terms of research stature and output." Well, yes and no. The lablets
opened in 2001. MRL, the Microprocessor Research Lab I helped start,
opened in 1995, as did some of the other labs. When I was at AMD in
2002-2004 my AMD coworkers were already sating to me that Intel's MRL
work was the most interesting work being published in computer
architecture conferences like ISCA, HPCA and Micro. I.e. I think MRL
was picking up steam well before the lablets were created.

Actually, the lablets were part of a trend to "academify" Intel
Labs. E.g. around that time my old lab MRL was taken over by a famous
professor imported from academia, who proceeded to do short term work
on the Itanium - and over the next few years most of the senior
researchers who did not agree with Itanium left or were forced out.
Ironically, the academic created a much shorter term focus at MRL by
betting on VLIW - and then ultimately he moved out of Intel.

Now, don't get me wrong: the guys left over the lab formerly known as
MRL do good work. Chris Wilkerson has published lots of good
papers. Jared Stark accomkplished the most successful technology
transfer I am aware of, of branch prediction to SNB. Chris and Jared
are largely the guys whose work my former AMD coworkers admired.

But, such work at Intel is largely incremental, evolutionary. I
mentioned that the famous professor in charge of my old research lab
tried to play politics by favoring Itanium, even though his
researchers were opposed.

Annoyingly, from when I joined Intel in 1991 to when Intel Labs
started in 1995 computer architecture work inside Intel was pretty
much 10 years ahead of academia. Out-of-order execution like P6 did
not come from mainstream academia, who were busy following the fads
RISC and in-order. (OOO came from at that time not mainstream
academia like Yale Patt and Wen-Mei Hwu, but they became maiinstream
as OOO became successful.)

But companies like Intel rest on their laurels. Having defeated RISC,
Intel did not need to do any serious computer architecture work for,
what, 10 years? 16 years now?

Matt says: I am very concerned about what happens if we don't have
enough long-range research. One model that could evolve is that
universities do the far-out stuff and industry focuses on the shorter
term.
It is hard to justify the Bell Labs model in today's world,
though no doubt it had tremendous impact.

I share your concern. But my experience is that universities are not
necessarily good at doing the far-out stuff.

About my experience: I'm not an academic, although perhaps I should
have been one. I failed to complete my Ph.D. twice (first marriage,
then when my daughter got born). I've never had an academic paper
published (although I had a few rejected, that later got built in
successful products). But I made some useful contributions to the
form of OOO that is in most modern computers. You are almost 100%
likely to have used some of my stuff, probably in the computer
you are reading this on. At one time I was Intel's most prolific
inventor. I helped start Intel Labs.

I wasted too many years of my life on what I think is the next major
step forward in computer architecture to improve single threaded
execution - speculative multithreading (SpMT). I say "wasted" not
because I think that SpMT is a bad idea, but because I spent far too
many of those years seeking funding and approval, rather than just
doing the work. The actual work was only a few intense months,
embedded in years of PowerPoint and poltics. But even though SpMT has
not proven a success yet, a spin-off idea, Multi-cluster
Multithreading (MCMT), the substrate that I wanted to build SpMT on,
is the heart of AMD's next flagship processor, Bulldozer. 7 years
after I left AMD in 2004. 13+ years after I came up with the idea of
MCMT, at Wisconsin during my second failed attempt to get a PhD.

My last major project at Intel 2005-2009 has not yet seen the light of day,
but newsblurbs such as Intel developing security 'game-changer':
Intel CTO says new technology will stop zero-day attacks in their
tracks suggest that it may.

Source: http://www.computerworld.com/s/article/9206366/Intel_developing_security_game_changer_

But in my last year at Intel, this major project, and a couple of
minor projects, were cancelled under me, until I was forced to work on
Larrabee, a project that I was not quite so opposed to as I was to
Itanium. Enough being enough, I left.

So: I am not an academic, but I have worked at, and hope to remain
working at, the leading edge of technology. I have tried to create
organizations and teams that do leading edge research, like MRL, but I
am more interested in doing the work myself than in being a manager.

The question remains: where do we get the ideas for the future? How
do we fund research, invention, and innovation?

Matt says One model that could evolve is that universities do the
far-out stuff and industry focuses on the shorter term.

"Could evolve"? Believe me, this is what every academic research
grant proposal said that I saw when I sat on an Intel committee giving
out research grants. It usually doesn't work - although once in a while it does.

Matt says: Google takes a very different approach, one in which
there is no division between "research" and "engineering." This is
an interesting approach. Myself, I am not a very good multi-tasker - I
tend to work intensely on a problem for weeks at a time. I don't know
how well I could manage 20% time, 1 day a week, for new projects.
(Although I am supposedly doing something like this for my current
job, the 90% main job tends to expand to fill all time available to
it.) But it may work for some people.

Somebody else posts about industry research: IBM Research and HP
Labs don't really have an academic research mindset and haven't for a
long time thanks to business unit based funding. Then goes on to say
Even within Intel Research, successful researchers (in terms of
promotion beyond a certain key point) also had to have some kind of
significant internal impact. Which is, I suspect, why the famous
professor who ran MRL after I left emphasized the VLIW dead-end,over
the objections of his senior researchers.

My own vision for Intel's Microprocessor Research Labs that the best
technology transfer is by transferring people. You can't throw
research over the wall and expect a product group to use it. Instead,
I wanted to have people flow back andforth between product groups and
research. In part I wanted to use the labs as an R&R stop for smart
people in the product groups - give them a place to recharge their
batteries after an exhausting 5 to 7 year product implementation. A
place to create their own new ideas, and/or borrow ideas from the
academics they might interact with in the labs. And then go back to a
product group, perhaps dragging a few of the academics along with
them, when they align with the start of a new project. "Align with the
start of a new project" - this is important. Sometimes a project
finishes, and there is no new project for the smart guys coming off
the old project to join, because of the vagaries of project schedules.
All too often people jump ship off an old project too early, because
they want to get onto the sexy new project at the right time for their
career growth. By providing such a scheduling buffer, this thrashing
may be avoided - and the even worse happenstance, when a smart guy
leaves the company, because there is no new project for him at his
current employer, while there is at the new company. And, finally,
once in a while a new project flows out of the lab.

I am particularly sympathetic to the Anonymous poster who said How
about a totally different alternative model? and then talks about
memes popular in the Open Source community, such as People do not
need to spend half of their life in formal schooling to start doing
cutting edge work. But then he says:

Most academic research outside of the top 5-10 schools in any field
is not useful, even by academic standards. I go further: MOST
academic work at MOST schools, even the top 5-10 schools, is not
useful. But oftyen the best academic work is at some little known
third or fouth tier school, and has trouble getting published.

Code is (far) more useful than papers. I am very sympathetic to
this. But (a) most engineers and programmers are not free to publish
either code or papers, limited by their employment agreements. And
occasionaly (b) the papers are a useful summary of the good ideas.

I look forward to the day when we can have Open Source computer
hardware. I don't say this facetiously: some of my best friends are
working on it. I would also, if I did not need an income.

Many of the people capable of contributing at a high level in
academia have the ability to start significant companies and create
genuine wealth. Many, but not most. Not every good technical person
is a good business person.

Which leads in to my closing point: Not every good technical person is
a good business person. Not every inventor is capable of building a
company around his investions. Many of the most useful inventions
cannot justify a completely new and independent company: they need the
ecosystem of an existing product line, and the support of a larger
organization.

For many years my resume said that my gioal was to re-create Thomas
Edison's Invention Factory in the modern world. In 2009 I left Intel
for the second time, and joined Intellectual Ventures. (With whom I
had earlier worked on some inventions I had made in 2004, in the short
time between my leaving AMD and rejoining Intel, the only time in my
career that my ideas belonged to me, and not my employer.)

I'm not authorized to speak for Intellectual Ventures, but I can refer
you to some of the things on the IV website,
http://www.intellectualventures.com:

“An industry dedicated to financing inventors and monetizing their
creations could transform the world.” Nathan Myhrvold, Founder and
CEO

We believe ideas are valuable. At Intellectual Ventures, we invest both expertise and capital in the development of inventions. We collaborate with leading inventors and partner with pioneering companies. ... We are creating an active market for invention... We do this by: * Employing talented inventors here at Intellectual Ventures who work on new inventions to help solve some of the world’s biggest problems. * Purchasing inventions from individual inventors and businesses ... * Partnering with our international network of more than 3,000 inventors and helping them to monetize their inventions.
Most of posters, the original blogger and the authors of the comments,
on this topic are interested in promoting research, invention, and
innovation. Sometimes you need to create a new economic or business
model. I hope it works.

Matt says: It is hard to justify the Bell Labs model in today's
world, though no doubt it had tremendous impact.

Somebody else once said to me that Bell Labs could have been kept running, avoiding its decline, based solely on its patent royalties.

Would that have been worth it? These were the people that gave us the
transistor. Information Theory. UNIX.

Finally, I must make the following disclaimer:

The content of this message is my personal opinion only. Although I am
an employee (currently of Quantum Intellectual Property Services,
working for Intellectual Ventures; in the past of companies such as
Intel, AMD, Motorola, and Gould), I reveal this only so that the
reader may account for any possible bias I may have towards my
employer's products. The statements I make here in no way represent my
employer's position on the issue, nor am I authorized to speak on
behalf of my employer.

hy_saying_"You_need_N-way_associativity_in_the_TLB_to_guarantee_forward_progress"_is_bogus_and_reflective_of_an_in-order_mindset

2011-04-05T19:41:00.000-07:00

http://semipublic.comp-arch.net/wiki/Why_saying_%22You_need_N-way_associativity_in_the_TLB_to_guarantee_forward_progress%22_is_bogus_and_reflective_of_an_in-order_mindset
[[Category:Virtual Memory]]

= The Annoying Quote =

One occasionally hears (and reads in computer architecture textbooks) statements such as

"Instruction set XXX can access N memory locations in a single instruction, so therefore requires a TLB with at least N-way associativity."

This statement is wrong in several ways, both as an underestimate and as an overestimate.
It reflects ignorance of out-of-order processors, and even for in-order processors it reflects ignorance of other implementations.

= Basic Assumption =

The basic assumption begind this statement is something like this:

Assume you have an instruction whose operation may be described in pseudocode or microcode as:

tL1 := load(M[A1])
...
tLN := load(M[AN])

tC1 := f1(tL1..tLN)
...
tCN := fN(tL1..tLN)

store( M[A1] := tC1 )
...
store( M[AN] := tCN )

Assume that you have a [[restart versus resume instruction exception|restart and not a resume instruction fault architecture]] - i.e. assume that you must access all of M[A1] .. M[AN], eventually, without a fault or TLB miss.
Then you need N TLB entries to hold all of the [[translation]]s for M[A1]..M[A2].

Or, equivalently, assume that you are not allowed to take a fault or TLB miss in the "[[commit phase]]" of the instruction.
Then, once again, you need N TLB entries to hold all of the [[translation]]s for M[A1]..M[A2].

Sounds simple, eh?

= Out-of-order with Speculative TLB miss handling =

This betrays an in-order mindset. It does not necessarily work on an [[out-of-order]] machine that does not block on a TLB miss,
i.e. which can perform ALU operations, memory references, and TLB misses out-of-order.

It doesn't work because, even though an operation such as load, store, or a [[tickle]] in the pseudocode or microcode for an instruction may load an TLB entry,
this TLB entry may be thrashed out of the TLB by (a) a later operation in same instruction, (b) an earlier operation in the same instruction (remember, out-of-order), or (c) a TLB use from a different instruction (remember, out-of-order and non-blocking: other instructions may be executing at the same time).

In particular, not that there is northing that says that the operations within a single instruction will be performed in-order --- and, indeed, on an out-of-order machine like the Intel P6 where the microinstructions within an instruction were performed out-of-order - so you can't necessarily make assumptions about the order of accesses, how they will affect LRU, etc.

== Kluges to Make It Work ==

* Allow out-of-order between instructions, but impose ordering restrictions within an instruction - e.g. by implementing every instruction with a strictly in-ordr state machine.

* TLB misses in-order, at commit time

= Other Implementations =

== Save Translations ==
Allow a "translation" to be saved in a register.

tT1 := save_translation_and_permission(M[A1])
...
tTN := save_translation_and_permission(M[AN])

tL1 := load_using_saved_translation_and_permission(M[phys_tr=tT1])
...
tLN := load_using_saved_translation_and_permission(M[phys_tr=tTN])

tC1 := f1(tL1..tLN)
...
tCN := fN(tL1..tLN)

store_using_saved_translation_and_permission( M[phys_tr=tT1] := tC1 )
...
store_using_saved_translation_and_permission( M[phys_tr=tTN] := tCN )

Issues:
* such a "saved translation" should contain not only the physical address corresponding to a virtual address, but also permissions.
* it is relatively easy to provide such an operation to microcode. It is harder to make it available to software.
** it obviously cannot be provided to user code
** virtualizing such a saved translation may be a challenge - even the OS may not be allowed to see the true physical address or permissions

== Who Cares? So What? ==

One could take the viewpoint of "Who Cares?": allow multiple TLB misses in the same instruction, don't restart.

Issue:
* there arises the possibility of [[intra-instruction translation inconsistency]] - different accesses to the same virtual address may receive different translations, different physical addresses, or, perhaps worse, a check may pass but a subsequent access fault.

Again, one may say "Who cares? The OS should not be changing translations while an instruction may be in flight."

But
* Saying that the OS should not do something does not always mean that it will
* An OS implemented on top of a VMM may lead to issues: the VMM may not be tracking where the OS keeps its page tables
* While this strategy may be acceptable, it may have lousy performance because of the necessity of stopping multiple processors for a [[TLB shootdown]] while changing a translation, e.g. in a [[page table]] in memory.

= Conclusion =

Saying

"Instruction set XXX can access N memory locations in a single instruction, so therefore requires a TLB with at least N-way associativity."

* underestimates the TLB entries required for an out-of-order processor with non-blocking TLB miss handling

* overestimates the TLB entries required for several reasonable implementation strategies, such as "Save Translations" and "Who Cares?"

More accurately, one might say

"Instruction set XXX can access N memory locations in a single instruction,
and for a certain set of microarchitecture assumptions
may require a TLB with at least N-way associativity."

But there are other ways...

Reset: Hard, Soft, Cold, Warm

2011-04-01T23:03:00.000-07:00

http://semipublic.comp-arch.net/wiki/Reset:_Hard,_Soft,_Cold,_Warm
= The need for RESET after REST at power-on =

In the beginning there was [[RESET]]: a signal asserted while powering on, deasserted when power and logic levels were stable, so that the circuit could could be initialized.

Soon thereafter, or even before, there was POWEROK:
* !POWEROK and RESET => do not attempt operation
* POWEROK and RESET => power good, now do initialization
* POWEROK and !RESET => initialization done, running.

But let us not get obsessed by the details of signalling: I'm okay, you're okay, I've initialized and you are ready.
Moving forward: ...

Eventually people realized that they wanted to be able to restore the state of the system to that right after RESET, without going through the full power on sequence.
Hence the concept of [[soft reset]] was born.
On Intel x86 systems the INIT pin or meessage can be considered to be approximately a [[soft reset]].
With the old reset and power on constituting [[hard reset]].

But [[soft reset]]s like INIT cannot recover from all errors. Sometimes a computer is truly hung, and a [[power cycle]] is necessary.
Or, if not a power cycle, an assertion of the RESET signal
so that all ofthe rest of the system is initialized?

Did I mention that, perhaps before [[soft reset]], people would build circuits that could interrupt power with a relay, and thus provooke a power on [[hard reset]] under software control?

Trouble is, after a [[hard reset]] system state might be unreliable, or might be initialized to a true reset state, such as all zeros.
How can you then distinguish a true [[power on reset]] from a [[hard reset]] invoked under software control?
Perhaps used to recover from a system hang?

What you need is a softer hard reset - a [[warm reset]] that acts like a [[hard reset]], asserting the RESET signal to the rest of the system, I/O devices et al,
so that the state of the machine is as close as you can get to a true power on [[cold reset]] as possible.
But where power persists across the [[warm reset]],
so that at least certain status registers can be reliably read.

At first the state that persisted across such a [[warm reset]] might reside only in a battery backed up unit near to the reset state machine.
But when the amount of state that you want to persist grows large,
e.g. the [[MCA (Machine Check Architecture)]] error status log registers,
state inside the [[CPU]] may be allowed, indeed, required, to persist across such a [[warm reset]].

= A possible sequence of progressively harder RESETs for error recovery =

I am sure that you can see that [[cold reset]] versus [[warm reset]] and [[hard reset]] versus [[soft reset]] are not necessarily discrete points but,
as usual, may be points on a spectrum,
a not necessarily 1D ordered list of possible reset mechanisms.

If an error is detected,
e.g. if a processor stops responding
* first you might try sending it a normal interrupt, of progressively higher priority
* then you might try sending in an [[NMI (Non-Maskable Interrupt)]]
** then any of the flavors of [[even less maskable non-maskable interrupt]]s, such as Intel's [[SMI (System Management Interrupt]], some sort of [[VMM]] or [[hypervisor]] interrupt
* then you might try sending a [[soft reset]] message like INIT to the apparently hung processor
* this failing, you may try to do a [[warm reset]] of the hung processor
** although by this time you probably want to reset all of the processors and I/O that are tightly bound to the hung processor
** exactly how you define such a "reset domain" is system specific, although it is often the same as a [[shared memory cache coherency domain]].
* failing this, you might try to use a [[hard reset]] under the control of an external circuit, e.g. at the power supply, that can trip a relay and then untrip it after a time has elapsed
** heck, this can be done at power supply points increasingly distant: inside the PC or blade, at the rack, in the datacenter...
* all of these failing, you can try to notify the user, although by this point that probably is impossible; or you may rely on some external mechanism, such as a user or a watchdog, to try to use ever more extreme forms of resetting the system.

The above tends to imply that there is a linear order of reset mechanisms. This is not necessarily true. You may reset subsystems in heuristic order.

= RESET is a splitting concept =

I.e. overall [[RESET]] is one of those concepts that inevitably split,
whenever you look too closely at it.
Of course, create no more flavors of reset than you need, because each brings complexity.
But inevitably, if your system is successful and lasts for several years,
you will need one or two more flavors of RESET than were originally anticipated.

= Similar =

[[Watchdog timer]]s are a concept that splits similarly to RESET.
Indeed, each level of progressive reset forerror recovery of a hung system is often driven
by a new level of [[watchdog timer]].
Or [[sanity timer]].

(Or [neurosis timer]], or [[psychosis timer]] ... no, I am writing this on April Fool's.)

Hardware data structures

2011-03-31T21:28:00.001-07:00

Computer software education (at least, if not the whole field) was greatly influenced by Niklaus Wirth's 1976 book
"Algorithms + Data Structures = Programs".
This popularized the importance of a programmer or software practitioner having a toolkit of datastructures,
and algorithms that employ or operate on such datastructures.

The situation in computer hardware is somewhat inchoate, less well defined.
Nevertheless the same [[hardware data structures]]
crop up over and over again in different applications.

I am not really sure what "algorithms" would be in the hardware version of "Algorithms + Data Structures = Programs".
Nor, for that matter, what "programs" would be.
Modules? Devices?
Sure, hardware implements algorithms, but it is hard to tease apart the concept of algorithms and data structures.
Moderately hard for software; especially so for hardware.

However, we should always keep in mind that hardware "algorithms" are just like software algorithms,
and data structures, except that implementation in hardware has diofferent constraint:
* size is limited - software often treats program size and data memory suze as infinite
* communications is restricted: whereas in software any module can talk to any other module or object, in hardware only a limited number of nearby communications are cheap.

== List of [[hardware data structures]] ==
* [[Arrays]]
** [[RAMs]] versus [[CAMs]]
** [[Encoded CAMs versus Decoded CAMs]]
-
* [[CAM]]s
** [[Equality match CAM]]s
** [[Priority CAM]]s
** [[Greater than CAM]]s
** [[Range CAM]]s
** [[Bitmask CAM]]s, a more general case of [[Ternary CAM]]s
-
* [[Pipelines]] - I'm not sure that these should be considered a [[hardware data structure]]
** [[Stalling pipelines]]
** [[Stall-free pipelines]]
*** [[Draining pipelines]]
*** [[Replay pipelines]]
** [[Bubble collapsing pipelines]]
-
* [[Queues and Buffers]]
** [[Collapsing queues]]
-
* [[Circular arrays]]
-
* [[FIFOs]]
** [[True data movement FIFOs versus array-based circular buffers]]
** [[Synchronizers (asynchronous logic)]]
*** [[Synchronization and clock domain crossing FIFOs]]
**** [[AMD synchronization FIFO]]
**** [[Intel Bubble Generating FIFO (BGF)]]
-
** [[Alignment issues for queues, buffers, and pipelines]]
** [[Holes in queues, buffers, and pipelines]]
-
[[Caches]]
* [[Fully associative in-array CAM tag matching]]
* [[Separate tag and data arrays]]
* [[N-way associative tag matching outside array]]
** [[index sequential]] - tag match, and then index data array
** [[index parallel]] - read out tags and data in parallel, then do a late mux
** [[in-array tag matching for N-way associative arrays]]
-
* [[Bloom Filters]]
** [[M of N Bloom filter]]
** [[N x 1 of M Bloom filter]]
** [[Pipelined Bloom filter]]
** [[Counted Bloom filter]]
-
* [[Arrays of 2-bit saturating counters]] crop up again and again, in predictors and elsewhere
-
* [[Permutation bit matrix]]es
-
* Schedulers
** [[Pickers versus packers]]
** [[Prioritizers]]
*** [[Carry chain prioritizer]]
**** [[Pick most extreme on one side]] - [[pick oldest (or youngest)]]
**** [[Pick most extreme on both sides]] - [[pick oldest and youngest]]
*** [[CAM matching prioritizer]]
**** [[Pick N-th]] - [[pick N-th oldest]]
*** [[Prioritizers after permutation bit matrix]]

In the aftermath of [[Mead and Conway]]'s "VLSI revolution"
there was a flurry of work on arbitrary hardware datastructures,
often 1:1 corresponding to software datastructures.
These include
* [[hardware sorting networks]]
* [[hardware heap sorting structures]]
* [[true hardware stack]]s
* [[true hardware FIFO]]s
Unfortunately, many of these have not proved practical in most computer applications.

== Duality between Hardware and Software Data Structures ==

We have long observed a regular pattern of [[duality between hardware and software data structures]].

This can be observed
* When implementing a hardware microarchitecture inside a software simulator.
* When converting an algorithm implemented in software into hardware
Oftentimes the most direct implementatin of a hardware data structure in software is stupidly slow, but there are regular patterns of good equivalences.

Such duals include

Hardware	Software	Comments
Equality match CAM	Hash table
Range or Greater Than CAM	No good SW equivalent
[[PLA]]s	[[Lookup table (LUT)]]	[[HW]] can handle irregular lookup tables: different granularity of LUTs for different ranges. [[SW]] must

The duality is useful,
not just for implementing HW in SW or vice versa,
but also because trends in VLSI scaling have meant, more and more, that the "traditional" hardware datastructures
must be foregone.
E.g. limiting the number of bits on a bit-line in a [[RAM array]] or a [[CAM match bitline]]
often means that that hash table like approaches should be used.

== Dual or equivalent implementations for [[hardware data structures]] ==

* [[Arrays are equivalent to multiple flopped registers outputting to a MUX]]

== Other [[hardware data structures]] ==

The ShuffleBox: a rectangular array of bits that can store, XOR and rotate all bits in all directions.
* Hala A. Farouk
* An efficient hardware data structure for cryptographic applications
* http://www.universitypress.org.uk/journals/cc/cc-10.pdf

=== Shifters ===

Various shift implementations - [[barrel shifter]]s,
[[cascaded multistage shifter]]s
- "feel" to me like the hardware instantiation of an algorithm more than a data structure,
since they are stateless.

Perhaps I should limit the concept of a [[hardware data structure]] to something that can store state for retrieval later.

= References =
* http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs
* Wirth, Niklaus (1976) (in English). Algorithms + Data Structures = Programs. Prentice Hall. ISBN 978-0-13-022418-7. 0130224189.

Intel BGF mentioned in:
* ftp://download.intel.com/design/processor/datashts/320835.pdf

* http://en.wikipedia.org/wiki/Mead_%26_Conway_revolution

Dynamic dead code elimination and hardware futures

2011-03-02T21:51:00.000-08:00

[[Category:BS]]
http://semipublic.comp-arch.net/wiki/Dynamic_dead_code_elimination_and_hardware_futures
= [[Dynamic dead code elimination]] =

It has been shown that often more than 1/3 of all computations, data movement, etc., are dynamically dead - they will never be used by the program, on its current path of execution.

There have been hardware proposals that delay computations, and elide some such dynamically dead code. Something like the flip side of [[hardware futures]].

; [[Semi-static optimization]]

Dynamic dead code elimination may be done as a [[semi-static optimization]] in an [[optimized trace cache]].
Basically, one applies classic compiler algorithms to the code to be cached,
augmented by reachability predicates.

Or, another classic way of doing hardware optimization is to examine the post-retirement instruction stream, eliminate dead code, and install that in the [[optimized trace cache]].

; [[Rename time optimization]]

Dynamic dead code elimination may also be done in the [[renamer]] pipestage. The basic idea is, instead of emitting uops as the are decoded,one assembles blocks of uops in the renamer.
Essentially, large expressions, potentially with multiple inputs and outputs.
One does not emit such a block of uops from the renamer to execution until a usage of the block is detected.

Typically, a store that may be visible to another processor constitutes a usage that will cause uops to be emitted.
(Although certain stores can be elided, e.g. push/pop/push [[stack optimizations]] and [[temporary variable optimizations]].)

Similarly, the evaluation of a branch condition may cause uops to be emitted. But one only need emit the subset of the buffered uops necessary to evaluate the branch.

Exceptions and other situations whether the entire program state may cause uops to be emitted.

And overflow of the renamer buffer.

If the output of an expression buffered in the renamer is overwritten, that part of the expression can be eliminated as dead code.

; [[Dataflow optimization]]

[[Dynamic dead code elimination]] can also be done in the OOO dataflow scheduling part of the machine.
Essentially, one assembles the dataflow graph, but one does not necessarily start execution as soon as inputs are ready.

The renamer adds an additional [[WAW]] arc to the dataflow graph, for a new uop that overwrites an old uop's output.
If that old uop has no [[RAW]] dependencies, then it can "fire", cancelling itself,
and signalling that cancellation to its own input dependencies in turn.

This is essentially [[reverse dataflow execution]].
It is straightforward, although it does require hardware that is not normally present.
It is easiest to accomplish with a [[bit matrix]] scheduler, where the [[input bitvector]] becomes the [[output bitvector]] of a cancelled uop.

It is not at all clear how useful this form of dataflow dead code elimination is:
it is buildable, but how much does it help?
It is probably most useful if it can be remembered in an [[optimized trace cache]].

= [[Hardware futures]] =

[[Hardware futures]] are the dual of [[dynamic dead code elimination]].
Instead of eliminating code that does not need to be executed,
it delays execution and evaluation of code until it is known to be needed.
This delay naturally accomplishes [[dynamic dead code elimination]].
It also provides increased scope for [[hardware CSE]],
and other optimizations.
But it potentially increases latency.

As for [[dynamic dead code elimination]],
it is fairly easy to see how to do this at the renamer:
have the renamer accumulate expressions.
Only release an expression to be evaluated when a usage that demands evaluation is detected.

We can go further, and avoid the buffering at the renamer becoming an issue by emitting such buffered instructions for a hardware future
into a sort of side car storage, rather like that of Akkary's [[CFP]].
When evaluation is demanded, we issue a token to cause insertion of those instructions.

Issue: are the buffered instructions pre or post rename? It is easiest to buffer them post rename,
using dataflow single assignment registers and memory locations.

Also as above, this can be deferred into the OOO dataflow scheduler.
But, again, that is using a fairly critical resource.

To make hardware futures less dynamic, more [[semi-static]] at the [[optimized trace cache]]
involves dividing the future into two parts:
the first part captures any live inputs,
that must be captured lest they change;
the second part does the actual evaluation on demand.
Typically memory load values must be live inputs, as well as registers,
and the future is constrained from doing stores that may be visible to other threads.

I.e. the hardware future is constrained to be a chunk of code that has no internal memory references.
Or at least only sharply limited internal memory references.

It is unclear how useful such a future would be. It would have to be saving considerable register based computation
- complicated instructions such as transcendentals - or be a complicated calculation on a small amount of memory.

Such hardware futures might be much more useful if we were released from the constraints of the [[Von Neumann memory model]],
e.g. if we had classic dataflow style [[single assignment memory]].
But in 2011 that does not seem likely any time soon.

Using Redundancies to Find Errors

2011-03-02T21:02:00.000-08:00

Cleaning out old journals from my bookshelf.

Came across

Yichen Xie, Dawson Engler, "Using Redundancies to Find Errors," IEEE Transactions on Software Engineering, pp. 915-928, October, 2003

(actually, a slightly different version in Software Engineering Notes / SIGSOFT 2002/FSE 10.

Very interesting paper: used analysis tools that detected dead code, redundant conditionals, idempotent operations such as x&x to detect bugs.

Causes me to wonder about applying similar techniques to look for hardware/RTL/HDL bugs, e.g. in Verilog or VHDL.

For that matter, it caused me to think about similar hardware techniques. For example, it has been shown that often more than 1/3 of all computations, data movement, etc., are dynamically dead - they will never be used by the program, on its current path of execution. There have been hardware proposals that delay computations, and elide some such dynamically dead code. Something like the flip side of hardware futures.

Now, such dynamic dead code detection *might* help locate bugs - but it suffers because it is dynamic, bound to the current path of execution. Whereas Xie's work looks at reachable code, including paths that may not be currently taken but which might use the values that are dead on the current path.

--

Done in xgcc, so code should be publicly available.

I wish I had had such tools in my last project.

Stream Processors, specifically Stream Descriptor Processors

2011-03-01T08:33:00.000-08:00

http://semipublic.comp-arch.net/wiki/Stream_processor
{{Terminology Term}}
[[Category:ISA]]
[[Category:Memory]]

= [[Stream processor]] is an overloaded term =

The term [[stream processor]] is fashionable and overloaded.
It often means just a processor that is "optimized" for a [[stream workload]].
Where "optimized" may mean just "has little cache".
(E.g. the use of the term "stream processor" in [[GPU]]s such as tyhose by AMD/ATI and Nvidia.)

= What is a [[stream]]? =

A [[stream workload]] operates on sets of data,
operating on one or a few data elements
before moving on,
not to return to those data elements for a long time.
Because of this access pattern,
[[LRU replacement]] is often ineffective, and may even be pessimal,
for [[stream workload]]s.
Keeping cache entries around that are not going to be reused is wasteful.
Sometimes a stream is restarted, in which case an MRU policy that keeps the head of the stream in cache is better than LRU.
Sometimes there is no reuse at all.

= [[Stream descriptor processor]] =

By [[stream processor]], I mean processors with [[stream descriptor]]s
- processors that have specific features, whether ISA or microarchitecture,
that support streaming.
(I would prefer to reserve this term for ISA features, but [[many good ISA features become microarchitecture]]].)
Possibly should call them [[stream descriptor processor]]s,
to distinguish them from the overloaded term [[stream processor]].

= [[Stream descriptor]] =

A [[stream descriptor]] is a description, in a register or memory data structure, that describes a memory access pattern.

For example, a [[1D stream descriptor]] might include
* data item description - size, type
* base
* stride
* length
* current position

A [[2D stream descriptor]] might include
* data item description - size, type
* base
* horizontal stride, length
* vertical stride, length
* current position, row and column

Obviously extendable to N dimensions.

In addition to arrays, there may be other types of stream descriptor

A scatter/gather descriptor
* a 1D descriptor of a vector of addresses
* with an indication that each addressshould be dereferenced

A linked list descriptor
* Base
* a skeleton [[structure descriptor]]
** payload to be accessed while traversing the list - offset, type
** position within a list element of pointer to next element

A tree or B-tree descriptor
* Base
* a skeleton [[structure descriptor]]
** payload
** key
** pointers

For the case of a tree or B-tree descriptor,
the access pattern may
(a) traverse all of a tree or subtree
or (b) traverse only a path seeking an individual element

= Why [[stream processor]]s? =

There are two main motivations for stream processors:
* memory access patterns
* data manipulation overhead
I think there is an additional property, probably nort considered important by most, but [[IMHO]] quite important:
* decoupling and ease of programming

; Memory Access Patterns

Support for streaming memory access patterns is probably the most important.
As mentioned above, many [[stream workload]]s do not fit in the cache.
But that could be handled by a simple [[cache bypass hint]] instruction.

Of more long term interest is the possibility that [[stream descriptor]]s, etc., may allow
streams that fit in the cache to be managed.
As cache sizes grow, [[memory data structures]] that did not fit in an old, smaller, cache, may fit in a new, larger, cacge.
E.g. a 1000x1000x32b array does not fit in a 32K [[L1$]], but may fit in an 8M [[L3$]].
Of course, this cannot be managed in isolation:
a workload that accessed only one 2MB 2D array might fit in an 8MB cache, but one that accessed 4 such would not.
Nevertheless, explicitly indicating the data structures provides more information to whoever is trying to manage the cache,
whether hardware or software.

The [[stream descriptor]] may have a bit associated with it, either inside or [[non-adjacent]], that indicates which cache levels to use. Furthermore, even in the absence of cache control in the stream descriptor, the stream descriptor provides guidance for [[cache prefetch]].
Guidance that may be more accurate that [[SW prefetch using cache control instructions]].
A stream descriptor may be associated with a prefetch control data structure, that seeks always to avoid delays accessing a stream,
without excessive prefetch.

; Data Manipulation Overhead

Users of [[SIMD packed vector]] instruction sets quickly come to realize
that the actual memory access and computation is only a small part of the task of programming code to use such instructions.
Often more than half of the instructions in such kernels are
data manipulation overhead
* unpacking 8 bit numbers into 16 bit numbers, or, worse, even fancier unpackings such as 5:6:5
* transposng rows and columns
* [[chunky versus planar]] data, i.e. [[SOA versus AOS]]

Explicit support for streams via [[stream descriptor]]s can eliminate much of this overhead, avoiding explicit instructions.

[[The CSI Multimedia Architecture]] goes further: not only does it hide the data packing and unpacking,
but it also seeks to hide the [[SIMD packed vector]] nature of the hardware datapath.
Instead of the programmer loading from a stream into a register of N bits, operating, and then storing,
this paper proposes complex streaming instructions that are implemented N bits at a time
in such a way that the code does not need to be changed when the microarchitecture changes the width of N.

Others have attempted to go even further, providing ways of expressing streaming kernels using simple instructions
that automatically get mapped onto a fixed length datapath.

; Decoupling and ease of programming

Streams are the equivalent of UNIX pipes.

If you had an architecture that allowed [[lightweight thread forking]],
some code could be written by connecting two library function kernels together by a stream
- instead of
* writing two separate loops that store the intermediate value to memory
* or merging the two operations into a single loop for a single pass

PROBLEM: allocating buffer space for such inter-thread streams. It may be necessary to spill to memory in some situations.

= If streams are such a good idea, why aren;t they popular yet? =

TBD.

Proper [[stream descriptor processor]]s have not taken off by 2010.

Instead, [[SIMD packed vector]] has dominated.

= See Also =

;[[The CSI Multimedia Architecture]], IEEE T. VLSI, Jan 2005.
: [[Stream descriptor]]s, plus optimizations to allow implicit SIMDification.
* [[iWarp]] - stream descriptors bound to registers
* [[Wm]] - William Wulf's processor, firs instance I know of stream descriptors bound to register

Unified_versus_Split_or_Typed_Register_Files

2011-02-27T18:06:00.001-08:00

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

There used to be a big debate in computer architecture about whether
one should have [[Unified versus Split Integera and Floating Point]].
Both ISA or macroarchitecurally, in the programmer exposed register
file. Or microarchitecturally, in the implementation.

E.g. the [[Intel P6 microarchitecture]] implemented the [[Intel
x86/x87 ISA]], with separate integer and floating point. But the
original P6 microarchitecture implemented this is a unified datapath,
in which both integer and floating point use the same scheduler, and
occupy the same [[PRF]] in the form of the unified [[ROB]], each entry
of which can hold a full 80+ bit x87 FP value. But they are split at
the [[RRF]].

Over time, Intel added [[SIMD packed vector extensions]]. [[MMX]]
shared the x86 registers, both architecturally and
microarchitecturally (in most implementations). But wider SIMD, such
as SSE with 128 bit [XMM]] regisyyers, and AVX with 256 bit [[YMM]]
registers, introduced yet another split architectureal register file.
Microarchitecturally, they may have kept the P6 unified structure, but
the wastage of storing an 8, 16, 32, or even 64 bit scalar in a 128 or
256 bit wide PRF entry becomes more and more of a concern.

AMD, by contrast, has typically had separate integer and FP/SIMD
clusters, with separate schedulers and PRFs and ...

Intel's 2011 processor, Sandybridge, has split integer and SIMD PRFs,
a unified scheduler, but split scalar and SIMD clusters.

It is becoming increasingly obvious that any desire to split datapaths
should be based not on type, not on integer versis floating point, but
should be based on width, intrger or scalar versus SIMD packed
vectors. Narrow data types, 8, 16, 32, 64 bits, versus wide packed
data types, 128, 256, possibly even 512 bits wide. Latency versus
throughput.

Currently it is pretty standard to separate

* integer, scalar, 8, 16, 32, and 64 bit data. Addresses and branches. Latency sensitive

* SIMD packed vector, both integer and FP. 128, 256, and possibly 512 bit data. Bandwidth.

The only real question is whether one should support scalar FP on a
datapath optimized for low latency, and interaction with branches and
addresses. Or whether scalar FP should only be handled as a single
lane in a vector register, as in SSE, in a throughput manner.

Now, there will always be workloads where FP scalar latency will
matter. For that matter, there will always be workloads where vector
latency matters. Nevertheless, this division into narrow latency and
wide throughput datapaths seems to be a trend.

It will always be desirable to be able to access the bits of an FP
number, whether scalar or vector, in an ad-hoc manner. It will always
be desirable to branch and form addresses based on such accesses. But
these desires will not always outweigh the separation into narrow
latency and wide throughput clusters.

Power concerns now are paramount. Split datapaths naturally save
power; but unified datapaths may be able to save power in an even
finer grained manner. Much depends on the granularity possible with
[[clock gating]] (which can be quite fine grained, e.g. to bytes of a
datapath) and [[power gating]] (which in 2011 is quite coarse grained,
unlikely to be done within the width of a unified datapath). For that
matter, separate narrow/latency and wide/throughput clusters would
probably be easier to clock at different frequencies, with different
coltages - although as of 2011 this does not seem yet to be done.

I can make no hard and fast conclusion: although there is a trend
towards split narrow/latency and wide/throughput datapaths, there will
still be occasional winning attempts to unifiy. Much depends on the
evolution of power, frequency, and voltage management, in terms of
granularity.

Why non-inclusive/non-exclusive caches?

2011-02-27T17:30:00.000-08:00

Sheesh! I can't usually take all the time this article needed to write in one sitting.

http://semipublic.comp-arch.net/wiki/Why_non-inclusive/non-exclusive_caches

[[Category:Cache]]

[[Non-inclusive/non-exclusive (NI/NE)]] caches are used in
[[multilevel cache hierarchies]] that are, duh, neither [[inclusive]]
nor [[exclusive]].

I.e. there is no enforcement of either the [[cache inclusion
property]] nor the [[cache exclusion property]]. A cache line in an
inner cache may or may not be in an outer cache. You can't be sure.
If necessary, you must check.

Because there is no [[cache inclusion]], both the inner and outer
caches must be checked, i.e. snooped or probed, when responding to
requests from other processors.

= Historical Background - Accidental Inclusion in the Original [[P6]] =

Probably the most widely known processor that has an [[NI/NE]] cache
is the [[Intel P6 family]].

The original P6 had an external L2 cache, on a [[back-side bus]]. In
an ascii diagram (TBD, I need drawing in this wiki):

[[L2$]] <---> P([[I$,L1$]]) <---> [[FSB]]

In more detail

[[L2$]] <---------> [[SQ]] <---> [[FSB]]
^
|
[[FB]]
|
+-----+----+
| | |
v v v
[[I$]] [[P]] [[L1$]]

Most of the symbols used in the diagrams above are standard; as for
those that are not:

* [[SQ (super queue)]] - on the [[P6 Pentium Pro]] die, coordinated interaction with the [[Front side bus (FSB)]], the back side buss and the off-chip [[L2]], and [[DCU]], mainly interacting with the [[fill buffers (FB)]].

* [[FB (fill buffers)]] - a staging area under the control of the [[data cache unit (DCU)]] of the P6 cpu core, talking to the [[bus cluster]] and hence the [[SQ]], [[L2$]], and the outisde world via the [[FSB]], and the caches of the [[processor core]], the [[IFU]] and [[DCU]] arrays. Also talked directly to the processor core, to minimize latency.

The original P6 had a completely external [[L2$]]. Not just the
[[cache data array]]s, but also the [[cache tag array]]s.

Now, there were several reasons why the original P6 had [[NI/NE]] or
[[accidental inclusion]]:

== Backside L2$ ==

Because the L2$ was on a backside bus, it was not necessarily faster
to access than the L1 caches, the [[IFU]] and [[DCU]]. In fact, you
can easily imagine circumstances where it might have been slower to
[[snoop]] or [[probe]].

Note; having the L2$ tags on-chip might have made it possible toprobe the L2$ faster than the L1$.
== [[Deterministic Snoop Latency]] ==

One of the design goals of the original P6 was to have [[deterministic
snoop latency]] - to be able to respond within a relatively small
fixed number of cycles to an snoop from remote processors on the
[[FSB]].

[[Cache inclusion]]] would get in the way of this. You would first
have to prove the L2$, and then, if a hit, probe the L1$. This
naturally leans towards a [[variable snoop latency]], and slows the
snoop down.

In the long run I think that [[deterministic snoop latency]] must be
considered a worthy goal, but a dead-end. I think even the original
P6 gave up on it, providing it in most cases, but also provided a
snoop stall as a way of handling cases where it could not be provided.
Nevertheless, the goal of [[dererministic snoop latency]] influenced
the design.

== L2$ relatively large compared to the L1$ ==

The external, off-chip but inside package, L2$ for the original P6
Pentium Pro was 512Kib, 1Mib, with some versions as small as 256KiB.

The DCU or L1 data cache was die dieted over the life of the project
from 64KiB in our dreams to 16 or 8KiB.

Thus, the L2 was typically 32x bigger than the L1 data cache,
and similarly wrt the instruction cache.

Although Intel has experience with [[exclusive cache]]s from earlier
processors, with a 32:1 or 16:1 size ratio, there is little point in
using an exclusive cache to try to increase cache hit rate. The
increase in the hit rate from having circa 3-66% more data is small.
Most of the time the data in the L1$ is included in the L2$ buyy
accident.

This property Wen-Hann Wang called [[accidental inclusion]]. Wen-Hann
Wang was the leader of the P6 cache protocol design, and the inventor
(in his PhD) of [[cache inclusion]].

== Simplifying Design ==

In truth I must admit that we started P6 expecting to build an
[[inclusive cache]] hierarchy. However, Wen-Hann's performance data
showed that [[accidental inclusion]] because of the relatively large
L2$ removed most of the performance incentive for inclusion. And
moving to [[NI/NE]] considerably simplified the cache protocol,
removing many boundary conditions.

For example, how do you handle cases where a cache line is being made
dirty in the L1 exactly as it is being evicted from the L2? ... It is
not impossible to handle these cases. But [[accidental inclusion]]
made it just plain easier to leave them decoupled.

By the way, at the time on P6 we did not really have a term for thecache inclusion properties of the P5 L2, or lack thereof. Wen-Hanncalled it [[accidental inclusion]], but that term has stuck only inGlew's memory. The term [[non-inclusive/non-exclusive (NI/NE)]] wascreated years later.
== [[Silent eviction of clean data]] ==

It is, of course, always necessary to perform a [[writeback]] when
[[evicting dirty data]].

When [[evicting clean data]], however, one can silently drop the clean
line. It is not always necessary to inform the outer cache.

Now, this isn't 100% linked to [[cache inclusion]] or [[NI/NE]]. One
can perform [[silent eviction of clean data]] in an [[inclusive
cache]]. However, doing so means that any [[inclusion tracking]] that
the outer cacheis performing, so that it knows which cachelines in the
outer cache are inside which inner cache(s), may be inaccurate.
I.e. [[possibly inaccurate inclusion tracking ]].

[[Accurate inclusion tracking]] is a [[slippery slope]]. It is not
necessary, but it has several nice properties. Worse, some people
implicitly assume [[accurate inclusion tracking]] in any [[inclsuive
cache]] design.

[[Accidental inclusion]] or [[NI/NE]] avoids this slippery slope
altogether. Which not only simplifies design, bit also avioids the
sort of incorrect assumptions that often arise on such a [[slippery slope]].

== Allocation in L1$ without L2$ interaction ==

[[Accidental inclusion]] enabled or made easier certain cache protocol
optimizations, in particular [[eliminating unnecesary RFOs]] for
full-line cache writes, without requiring L2 involvement.
Especially as used in [[P6 fast strings]].

This probably was not a design goal for most of the people involved,
but it was something I (Andy Glew) was happy to take advantage of.

The basic observation is that a sizeable fraction of all cache lines
are completely overwritten, without any of the old data being read.
Therefore, reading the old data via an [[RFO (read for ownership)]]
bus request is wasted bandwidth.

In operations such as [[block fill]], e.g. zeroing a page of memory,
50% of the data bus bandwidth is wasted by such unnecessary RFOs. In
[[block copy]], 33%, (Assuming all miss the cache - not that bad an
assumption for an 8 or 16Hob L1$, but also not unreasonable even on
many larger caches, for many [[block memory operations]].)

Even in non-block memory code, unnecessary RFOs occupy a significant
fraction of data bus bandwidth. I have measured speedups of 10-20% on
many simulated workloads, and even on a few [[FIB-edited chips]].

The biggest challenge with [[eliminating unnecessary RFOs]] ismaintaining [[memory ordering]], in particular [[store ordering]]. Itis easy to do on a [[weakly ordered]] system. I have invented severaltechniques for maintaining memory ordering, some of which are [[NDA]],but some of which can be discussed here. When I get around to writingthem up. In my [[copious free time]].
The original P6 eliminated unnecessary RFOs using the [[deferred
invalidation cache protocol]] for [[fast strings]] [[block memory
operations]]. The bandwidth benefit was clear; unfortunately, the
overhead of microcode, in the absence of microcode branch prediction,
made fast strings not always the best approach. Since the original P6
[[fast strings]] have been hit and miss: when somebody in microcode
gets around to tuning them they can be a win, but if untuned they may
be a loss compared to the best hand rolled assembly code.

P6's [[WC memory type]] also eliminated unnecessary RFOs, but was not
allocated in the cache. Similarly the [[SSE streaming stores]] added
in later processors.

The [[deferred invalidate cache protocol]] continued in use all the
way to Intel's Nehalem processor, the last of the P6 family. Nehalem,
however, added an inclusive [[LLC]] with snoop filtering, killing the
deferred invalidate cache protocol.

So much for history. The point remains: not having an inclusive cache
enables certain cache protocol optimizations, such as [[eliminating
unnecessary RFOs]], that are much harderto buildin an inclusive cache
system.

== Optionally Removing the L2$ ==

The [[NI/NE]] cache structure makes it easier to optionally disable or
remove the [[L2$]]. This option has been explored several times.

Now, it is possible to do this with an inclusive cache structure by
"faking out" the absent L2$, always returning "Yes, the cache line is
included in all possible internal caches", such as the instruction and
data and other caches.

But it is very easy, in an inclusive cache hierarchy, to slip dfown
the slippery slope and assume that the L2$ is present. And then to
take advantage of the L2$ being present in a way that breaks when the
L2$ is absent. [[NI/NE]] seeems to avoid this.

== Enabling [Funky Caches]] and Decoupling Associativity ==

In an [[inclusive cache]] system, one tends to want the associativity
of the outer, inclusive, cache to be greater than or equal to the sum
of the associativities of the inner caches it "covers".

E.g. if you have a 16 way associative outer cache that is inclusive of
8 inner caches, all of 4 way associativity, and if the usual indexing
of the cache using bitfields is performed (which usually implies a
1:many relationship between inner sets and outer sets), then it is
possible that for some set So of the outer cache mapping to sets Si of
each of the inner caches, each inner cache may want to have a distimct
line in each of the 4 ways. Implying that the inner caches may "want"
to have 8*4 distinct lines. Which exceeds the 16 way associativity of
the outer cache.

[[NI/NE]] caches do not have this constraint on associativity.

Furthermore, when playing the [[Funky Cache Rag]], exploring
structures such as [[victim caches]] or [[prefetch caches]] or
specialized caches for different data types, [[cache inclusion]] once
again gets in the way. Often these [[Funky Caches]] are fully
assiociative. They do a great job of reducing glass jaws related to
cache associativity - e.g. a 16 or 32 entry victim cache makes a 4 way
cache look like it has a much higher effective associativity. But a
32 entry fully associative victim or prefetch cache may only be able
to use 16 entries, if all entries map to the same way in the outer
cache. [[Cache inclusion]] prevents some of the worst [[glass jaws]]
that these caches can fix, from being fixed.

Now, these interactions are not necessarily large, at least in average
effect, although they can be a fertiole source of [[glass jaws]].

However, they do couple the design of the outer cache and the inner
cache. They mean, for example, that the outer cache design team
cannot simply change associativity without checking with the inner
cache design team, which may be making assumptions based on the
earlier outer cache design team [[POR]] for associativity. It means
that the outer and inner caches are more tightly coupled. Which can
lead to more efficient designs. But which can also make it slower and
harder to innovate.

== Backwards Invalidation Traffic ==

There are two main methods to maintain [[cache inclusion]]:
[[backwards invalidation]], and the considerablly less practical
[[outer cache victim identification by inner cache]]. I will ignore
the latter.

[[Backwards invalidation]]s are simple and straightforward. But they
also consume power, affect performance on an outer to inner cache
interconnect that may be saturated. And, in any case, are an
incremental source of complexity.

[[NI/NE]] cache hierarchies eliminate [[backwards invalidation]]s.

Now, in the 2011 Intel processors that motivated this article,
Sandybridge, with an inclusive snoop filtering [[LLC]] but a [[NI/NE]]
[[MLC]], backwwards invalidations are still required for LLC
evictions. But not for MLC evictions.

Let's talk some scenarios:

In workloads that use mainly read-only data, [[NI/NE]] allows [[silent eviction of dirty data]], but [[cacheinclusion]] requires BIs.

In workloads that use a lot of shared data, there may be multiple BIs for every inclusive cache eviction.

Etc. etc.

It is by no means certain that power saved by not [[probe filtering]] is not outweighed by the power saved by eliminating BIs.
It all depends on the type of multiproceessing in the system.
If the coherency traffic from beyond the outer cache is small relative to the cache thrashing inside the system,
e.g. if you have 16 cores crunching on large data serts, but no other multicore CPU chips and relatively small I/O,
BI traffic may outweigh snoop filttering.
But if you are building a very large shared memory system with many other CPUs and much cache coherent I/O traffic,
then inclusion may win.

= Are [[NI/NE]] caches still important? =

Obviously, since [[NI/NE]] caches are still in use in the Intel
Sandybridge processors being released at the time of writing in 2011,
they are still important in a practical sense? But is this just
[[legacy computer architecture]] dating back to the original P6? If
they were desiged from scratch, would [[NI/NE]] still be built

Maybe... lacking access to full simulation results, it is hard to say.

However, many of the advantages of [[NI/NE]] relate to making design
easier, decoupling inner and outer cache design. This is probably one
source of the longevity of the [[P6 microarchitecture]], which is now
coming to an end with Sandybridge.

Certainly, the old advantage of [[eliminating unnecessary RFOs]] no
longer stands. But that was always one of the most minor advantagesof
[[NI/NE]].

Much depends on the system. [[Probe filtering]] [[coherency traffic]]
makes a big difference in large multiprocessor systems with many outer
caches. It also helps with large amounts of high bandwidth cache
coherent I/O, as sometimes arises with ill-tuned [[discrete GPU]].
(Most discrete GPUs are tuned to use [[non-cache coherent I/O]], if
accessing [[UMA]] or processor memory at all.)

But as multicore systems get more cores,
and GPUs are largely integrated,
there may be less bandwidth on the other side of the [[outermost cache]].

== Where does cache inclusion win? ==

=== Snoop or probe filtering ===

One big win for cache inclusion is [[snoop filtering]].

However, such [[probe filtering]] does not necessarily require that
the cache data be inclusive. A data-less [[probe filter]] or
[[ownership cache]], a structure that allows ownership to be tracked,
and which permits lines to be exclsuively owned even though in main
memory may provide the benefits of [[probe filtering]] without the
costs of cache inclusion on a relatively small data cache. At the
cost of a new [[hardware data structure]], the [[ownership cache]].

Basically, the ownership cache maintains the cache inclusion property,
not necessarily the data cache. Since the ownership cache maintains
only a few state bits per cache line, the ownership cache can covedr
much more memory than an ordinary data cache. It is therefore less
liable to the issues of cache associativity.

=== Power management ===

Probably the most important win for [[cache inclusion]] is wrt power
management - really just an elaboration of [[snoop filtering]].

If you have [[cache inclusion]] you can power down all of the inner
caches, putting them into a low power mode that maintains state, but
which does not snoop.

Whereas if you have a [[NI/NE]] cache, you either must keep snooping
the inner caches, or you must flush the inner caches when going into
such a [[no-snoop cache mode]].

Now, you always needto be able to do such cache flushes. But they
take time, and if they are not required you can enter tye low power
mode more quickly, and more often, and thereby save more power.

Note that an inclusive LLC in combination with a NI/NE [[MLC]] and [[FLCs]]
gives the best of both worlds in this regard.
Note also that a datalerss [[snoop filter]] also works.

= Conclusion =

Many people, taught in school about [[inclusive caches]], are
surprised to learn how common and important [[exclusive caches]] and
[[non-inclusive/non-exclusive caches]] are, or at least have been, in
history.

It is by no means clear that any approiach is always best. All 3
approaches have pros and cons, and win in some situations.

Cache replacement - tweaks and variations

2011-02-27T10:31:00.001-08:00

http://semipublic.comp-arch.net/wiki/Cache_replacement
{{Terminology Term}}
[[Category:Cache]]

[[Cache replacement]] or [[cache victim selection]] is the method one uses to choose which cache line will be overwritten or replaced, i.e. victimized, when a new cache line is pulled in.

Common algorithms include
* [[Random replacement]]
* [[LRU (least recently used)]]
** approximations to [[LRU]:
*** [[pseudo-LRU]] or [[tree LRU]]
*** [[the clock algorithm]]

= Minor Tweaks =

== When is the cache [[LRU information]] or [[cache usage information]] updated? ==

E.g. do you update it speculatively, for instructions that may be on a [[branch misprediction wrong path]], thereby corrupting the LRU?

Should you update at retirement? (Probably not, but just in case.)
:By the way, here is a reason to update at retirement: so that you get more [[deterministic behavior]], which eases validation. However, this only works if you do not do [[speculative cache misses]].

Perhaps you should only update it for slightly speculative instructions:
* e.g. do not update for highly speculative [[SpMT]] threads?
* e.g. update only for isntructions that have not retired, but for which all earlier branches have been resolved. (Such instructions are stil speculative - there may be a page fault or exception or interrupt - but they7 are only [[slightly speculative]]).

== What requests update the LRU information? ==

Should all requests, reads and writes, update the LRU information equally?

Many have proposed [[non-temporal hint bits]] in instructions, to say "ignore this access".

It is an open issue whether prefetches, whether initiated by [[prefetch instruction]]s or by [[hardware prefetchers]],
should update the LRU.

Multilevel caches:
* update the LRU on all accesses
* on misses
* on [[LRU leak-through]] from the inner cache
* only on capacity evictions from the inner cache (suggested in comp.arch by EricP on 2/25/2011)

By the way, the idea of updating the cache usage information only on capacity evictions from the inner cache
exposes several issues:

Updating the LRU information and advancing the LRU pointer are two different issues.Invalidation traffic may result in several coherency cache misses between capacity misses.It would be bad to keep choosing the same victim.Oftentimes coherency misses do not need a victim chosen: they fill into the empty or stale or non-present line left behind by the invalidation.(May not happen in all systems.)Dirty writebacks naturally notify the outer cache of a capacity replacement.However, replacing a clean line may not naturally require such notiification:i.e. we may have [[silent replacement of clean cache lines]].This may require [[LRU leakthrough]] so that the outrr cache can track.
== When is the victim chosen? ==

Should you choose the victim at the time the cache is missed,
or at the time the data to be placed in the cache line has returned?

It may not matter on an in-order machine. However, on an out-of-order machine, chooising the victim early may raise isssues, such as what should happen if too many cache misses to the same set occur
- i.e. if the victim itself needs to be victimized before the first victim's replacement has arrived.

One advantage of choosing the victim early is that you may be able to send the data for the [[cache line fill]]
returning directly to where it belongs in the cache - you may not have to stage it through a [[fill buffer]],
and you may be able to avoid fairly expensive [[fill buffer forwarding]] logic.
I.e. you may be able to have [[data-less fill buffers]].

Half baked Idea: choose the victim early. But also allocate a fill buffer. At [[fill time]], determine if the early victim choice is still accurate. If not, write to the fill buffer.(I call this a half baked idea because it doesn't really solve the problem of wanting to avoid data fill buffers.Elaboration: choose the victim early. Allocate a [[address and control fill buffer]], but do not allocate a [[data fill buffer]].If the victim is thrashed, allocate a [[data fill; buffer]] (which may simply be a [[spill buffer]] allocated circularly.At fill time, choose.
== Biasing the victim choice ==

* Prefer invalid lines, rather than replacing valid lines.
* Prefer clean lines to dirty lines
:: Thereby avoiding [[dirty writeback]] traffic.

* in multilevel caches, prefer lines that are in none of, or the fewest, inner caches

* prefer to replace lines containing data to lines containing instructions
** or vice versa - although oftentimes [[I$]] misses are more expensive than [[D$]] misses

* extend the above to more data types - integer versus FP (FP is often accessed in a cache thrashing manner)

= Better cache replacement algorithms =

There has been much work on trying to adjust these algorithms.

Ideally, we know that [[Belady's algorithm]] is optimal for many assumptions.
It amounts to "replacing the cache line that will be used furthest in the future".
It must be adjusted when there are non-uniform costs.

There have been attempts to [[approximate Belady cache replacement using speculation and lookahead]].E.g. do not replace a line that is used in an instruction window.This works better when you have a really large instruction window, such as might be provided by [[SpMT]].It also may not be necessary if the [[LRU bits]] or [[cache usage information]] is updated speculatively.Others have attempted to unroll memory access pattern predictors,to get a list of predicted accesses, against which a Belady query can be made
See [[Victim Choice for Multilevel and Shared Caches]] for a discussion of issues in multilevel cache victim selection.
One of the main issues is that in a [[multilevel cache hierarchy]] the LRU bits of the outer caches are not adjusted
by accesses to the inner caches, so choosing a victim based purely on LRU bits updated only by accesses sent to the outer cache
is often not good.
Many proposals [[leak-through LRU]] information, to allow the outer cache to track the inner LRU.

It is well known that certain access patterns are not well suited to LRU cache replacement.
For example, circularly accessing N lines, in a cache of M lines, M < N, is better suited by MRU cache replacement than LRU.
Many have proposed to exploit this, e.g. by [[non-temporal]] hint bits attached to instructions,
or by predictors that attempt to identify such non-temporal cache access patterns.

Reading List for Computer Architecture (seed)

2011-02-27T08:26:00.000-08:00

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

TBD:

I am often asked for a reading list for computer architecture.

Unfortunately, there aren't many good books in computer architecture.

= [[Hennessy and Patterson]] =

[[Hennessy and Patterson]] is the current must-read, since its first publication
but that is not really a comprehensive book or survey of the field,
as a text book suitable for classes, espousing a quantitative design philisophy.

In fact, one of the reasons I am trying to create the comp.arch wiki is as an antidote to Hennessy and Patterson.
I want to collect a survey or grab bag of many techniques not mentioned in [[H&P]],
or potentially deprecated by them.
Many students raised on H&P, particularly the early versions, developed a common attituide
- they were [[RISC bigot]], and deprecated any advanced microarchitecture such as [[OOO]],
since they felt sure that the [[simple 5-stage pipeline]] was the be-all and end-all.
It is not fair to ascribe these viewpoints to Professors Hennessy and Patterson
- their views are much more nuanced
- but nevertheless this viewpoint was common.

= Random Grab-bag =

This list was assembled from a recent email to an undergraduate (2011).
TBD: collect past recommended reading lists.

Hennessy and Patterson is required reading. However, I don't much like any of the textbooks - which is why I am working on my wiki, sort of as an antidote.

You pretty much have to read the conferences and journals:
* [[ISCA]]
* [[ASPLOS]]
* [[Micro]]
* [[HPCA]]
* [[Hotchips]]
* [[ISSCC]] - usually lower level than computer architecture, but oftentimes the only information you can get about industry chips

I suggest reading every issue of [[Microprocessor Report]] you can, although I warn you that there was a period when MPR was owned by EE Times when it was not very good. Back in the 80s and 90s, MPR was the bible, by installments; and since The Linley Group bought it back it has become much better than it was when EE Times owned it.

* the old [[Microprocessor Forum]] conference

As for reading the conferenves and journals, a good place to start would be the "Best of" issues:

* 25 Years of ISCA, Selected Papers, ed Guri Sohi

* 20 years of ACM SIGPLAN conferencvve on PLDA, 1979 - 1999, ed McKinley.

Other books on my shelf:

* Mead Conway VLSI - old, but classic. Read it.

* Laura Prince, Semiconductor Memories -old; I wish there was a better book on DRAM. Probably better to read papers.

* Bell and Newell,
* Bell Sieworik and Newell,
:: Computer Structures
::- this was the classsic when I was in school. Very old now.

* Mike Flynn, Computer Architecture
* Blauuw and Brooks, Computer Architecture

* Pfister - In search of clusters.

Many many instruction set manuals

esp.
* the IBM 360 Principles of Operation

* Hacker's Delight

* Inside the AS/400

Organick's books on computer hardware
* TBD: list

* The Soul of a New Machine

Use a library and used book store. I bought, and still buy, a lot of 2nd hand books.

* read manuals on http://bitsavers.org

= Best of Lists and Collections =

* papers that won the ACM SIGARCH and IEEE-CS TCCA ISCA Influential Paper Award, http://www.sigarch.org/influential_paper.html

= Bibliography Surfing =

Many students, especially graduate students assemble personal bibliographies and reference lists of papers they encountered in their research.
The bravest students may annotate the references, with discussions of value.
Many such lists can be found on the web.
Use them shamelessly for inspiration - but beware that your opinions may not agree with the bibliographers./

Unfortunately, more experienced professionals, professors, etc.
have usually learned to only provide positive recommendations,
and to never make public anti-recommendations
about authors who may eventually be recommending funding for the reviewer.

Still more experienced professionals may recommend papers that they dislike,
because not mentioning them would be an obvious dis.

Pattern History Invariant Branch Prediction

2011-02-21T14:04:00.000-08:00

Taking a vacation day - actually, a so-called "floating holiday"on today, USA President's Day- so that I could be with my daughter, who is off school,and so that I could pick up my wife at the airport.

https://semipublic.comp-arch.net/wiki/Pattern_History_Invariant_Branch_Prediction
{{Terminology Term}}
[[Category:Branch Prediction]]

= Terminology =

Many branch predictors have a property that I call [[Pattern History Invariant Branch Prediction]].
By this I mean that the cannot change their prediction for a branch, e.g. from taken to not-taken, or vice versa, without having an intervening misprediction.

== Bad Joke ==Oooh, how about "Can't change its mind without a fight"? I'm tempted to call it a Scottish, Irish,or a "My Wife" branch predictor - but I'll get in trouble for any and all of these,and only mention them because I am humor impaired.

= Why does this matter? =

== [[Timing Invariant Branch Prediction]] ==

Pattern history invariance can be a useful property, because it makes it easier to build
[[Timing Invariant Branch Prediction]].
Which has several good properties, such as making val

In particular, it means that delaying updating the pattern tables used to make predictions until retirement will NOT result in any more mispredictions than would otherwise occur
- any such mispredictions would already be on the wrong path, younger than a misprediction that would occur no matter what.

Delaying the pattern table update from, e.g. branch execution to retirement has the possible benefit that [[wrong path]] execution will not corrupt the branch predictor.

However, it may be pointed out that it is possible that there will be a performance loss because of other benefits of execution on the multiply speculative wrong path that speculatively updating a branch pattern history table may bring.
But to get this, you must have several nested effects:
* there must be a first branch misprediction pending
* a younger branch may update the predictor tables
* this may result in a misprediction underneath the first branch misprediction
* which may itself update the predictor tables
** possibly eliminating a misprediction when execution resumes after the first branch misprediction is repaired
** possibly producing instruction prefetch and other [[good wrong path effects]]

I.e. with [[Pattern History Invariant Branch Prediction]] there must be a misprediction to result in a change of prediction.
However, that misprediction may itself occur, and be repaired, speculatively.
And that misprediction may have other [[good wrong path effects]].

== [[BTB Unrolling]] ==

[[Pattern History Invariant Branch Prediction]]
also enables [[BTB Unrolling]]:
give a current (IP,history) tuple
and a separate pattern table used to make a prediction
one can "unroll" the predictor to produce a trace
of multiple, N, branch (from,to) addresses.
And such a trace unrolling is guaranteed to be as accurate as if the predictor were accessed one branch at a time.

= Examples of Pattern History Invariance =

= Examples of non-Pattern History Invariance =

I was tempted to say

The most powerful example of a non-pattern history invariant branch predictor is a [[loop predictor]].E.g. it may predict that the loop closing branch is taken 99 times in a row, and then not-taken the 100th time.Even more advanced loop predictors, such as predicting that if the last few loops were executed were 67,66,65, times,then the next will be executed 64 times,are even less pattern history invariant.But this is not true: such a loop predictor will always make the same prediction, if the current loop count
is considered to be part of the history that used, along with the branch in question, to index
the pattern tables.

It is necessary to work ahrder to contrive branch predictors that are not pattern history invariant.

TBD: I believe that certain McFarling-style branch predictors may break the pattern history invariance property.
TBD: get the details right.

In particular, in a multi-predictor system such as McFarling,
if you update the predictors and choosers that are NOT being used as well as the predictors and choosers that are being used,
you can "mask" a misprediction in a second predictor,
if a first predictor was being used.
If the choice of which predictor should be used can then change in the pattern table so that
when the same (IP,history) pair is used at a later time the second predictor wins...

= See Also =

* [[Branch predictor state update]]
* [[Timing Invariant Branch Prediction]]

Timing Invariant Branch Prediction

2011-02-21T07:39:00.000-08:00

http://semipublic.comp-arch.net/wiki/Timing_Invariant_Branch_Prediction
{{Terminology Term}}
[[Category:Branch Prediction]]

By [[Timing Invariant Branch Prediction]] I mean branch prediction that is independent of timing.

E.g. a branch predictor design that, if you slowed down the clock or changed the pipeline, e.g. by inserting idle pipestages,
would not vary.

Such invariance is very convenient
(1) for validation
(2) for separation of concerns - it allows you to change the pipeline without worrying about its effect on branch prediction accuracy, etc.

However, many microarchitectures do not adhere to this design principle.

Tweaks and adjustments to the branch prediction microarchitecture may be necessary to attain [[Timing Invariant Branch Prediction]].
For example
* Per-branch history often leads to timing dependent branch prediction, which can be remedied by [[path history]]
* Updating the branch history tables can lead to timing dependent branch prediction

= Per-branch history often leads to timing dependent branch prediction =

For example, if you are using a [[per-branch history]] such as a [[TNT branch history]],
in many pipelines there are several clocks between instruction fetch,
i.e. delivering an instruction pointer to the instruction cache and branch predictor,
and instruction decode.
This means that an instruction fetch/branch prediction time you do not know where the branch instructions are;
you only know where the branch instructions are at decode time.

Therefore, unless you stall,
branch prediction may be using a [[per-branch history]] that is several cycles out of date,
and which may miss several branches
from what it would be ideally using if branches could be identified instantaneously.
Moreover, how many branches are missing may depend on timing, such as [[I$]] misses, pipeline stalls, etc.

== Path history enables timing independent branch prediction ==

If it is a problem to have timing dependent branch prediction
caused by per-branch history, this can be assuaged by [[path history]] branch prediction.

Instruction fetch does not necessarily know where the branches are. However, it necessarily does know the sequence of instruction fetch addresses.
If it is possible to create a path history suitable for use in a branch predictor,
e.g. by XORing the instruction fetch pointers,
then this [[path history]] is accurate and timing invariant.
Since XOR hashing is fast, this probably can be acheived.

However, XORing all fetch IPs may not be the best [[path history]] to use in branch prediction.
Creating a hash, probably XOR based, of [[branch from/to addresses]],
suffices to describe the path - although it losses information about branches between instruction fetch blocks.
Hashing such a [[branch from/to addresses]] [[path history]] with the current instruction fetch pointer
is about as good as you can do at instruction fetch,
without identifying individual instructions.

== Combining ... ==

[[Path history]] based branch predictors are usually reported as being more accurate than [[per-branch history TNT]],
so the pipeline adjustments above may help performance as well as providing [[Timing Invariant Branch Prediction]].

However, if they do not, you can obtain a hybrid that provides many of the benefits of [[timing invariant branch prediction]]
along with the possible improved accuracy of [[per-branch history]]:
* use [[path history]] at instruction fetch
* use [[per-branch history]] at the decoder, in a form of [[late-pipestage branch prediction]]

This gives you timing invariance,
but it also gives the [[decoder branch predictor]] the chance to make corrections to the earlier branch prediction.

= Branch History Update Time =

Q: when should the prediction tables, the [[pattern history table (PHT)]], also sometimes called the [[branch histogram]] or [[branch history table (BHT)]],
be updated?

At execution time, or at retirement time.

Updating at retirement time enables [[Timing Invariant Branch Prediction]]

Updating at execution time may cause only minor issues on an in-order machine.
On an out-of-order machine, however, updates may be done out of order.
In either case they may be done speculatively,
for branches that will not actually be retired because of earlier misspeculations.

Furthermore there arises the question of what history or [[stew]] is used to update the pattern history table.
If every branch at execution carries its history or stew with it, no problem.
But if a big complicated history is maintained only at retirement,
some processor designs have updated the pattern table for branches at execution
with a history corresponding to a position in the instruction stream several cycles before the branch.
Not necessarily a consistent number of cycles, either.

Updating the prediction tables a tretirement time seems to avoid these issues.

TBD: performance cost

TBD: latencies of table update - immaterial if [[pattern history invariant branch prediction]].

= Conclusion =

Is [[Timing Invariant Branch Prediction]] an absolutely vital design goal?

Not necessarily - if performance is increased by timing variant branch prediction, so be it.

However, [[Timing Invariant Branch Prediction]] is definitely a nice thing to have:
* it makes validation much easier
* it makes the design more robust, less fragile, less likely to break if you have to add a pipestage or stall late in the design cycle.
* it is usually associated with higher performance rather than lower performance branch prediction algorithms
* it can usually be achieved by a hybrid predictor design.

It is my experience that most timing dependent branch predictors
happened by accident, rather than by design:
* naive designers building a [[per-branch history]] out of a textbook
* naive extension of in-order designs to out-of-order exacerbating unnecessary timing dependence
etc.

[[Timing Invariant Branch Prediction]] is not necessarily a must-have,
but it is always a good thing to keep in mind when designing
your branch predictor and your microarchitecture/pipeline.
It is a pity to lose its benefits due to ignorance rather than deliberation.

CSE (Common Subexpressions) in HW andSW

2011-02-18T20:55:00.001-08:00

http://semipublic.comp-arch.net/wiki/CSE_(common_sub-expression)

CSE is an optimization that recognizes common sub-expressions, and saves them and reuses them rather than recalculating them.

E.g.

var1 := (a*b) + c
var2 := (a*b) + d;

can be rewritten as

tmp := a*b
var1 := tmp + c
var2 := tmp + d

This is obvious, right?

It is less obvious when you have, e.g. complex addressing modes such as (base+index*scale+offset).
Should you CSE part of address computation?

Sometimes it is cheaper to recalculate than it is to store, allocating a register that may spill other registers.

[[Memoization]] is a form of hardware CSE, where an expensive execution recognizes recently performed calculations and avoids reperforming them.

[[1/x inverse instructions]] provide greater opportunity for CSE than do ordinary [[divide instructions]].

[[Micro-optimization_primitive_instructions]] provide more opportunity for [[CSE]]ing.

[[Hardware common-sub-expression elimination]] has been proposed - by me (Andy Glew), in my abandoned Ph.D. on [[instruction refinement]],
if by no one elsse. In fact [[nearly all Dragon-book compiler optimizations can be doone in hardware]].

[[Instruction reuse]] is a hardware technique that extenddsCSE dynamically over moderate to large distances.

Micro-optimization primitive instructions

2011-02-18T20:42:00.001-08:00

http://semipublic.comp-arch.net/wiki/Micro-optimization_primitive_instructions

By [[micro-optimization primitive instructions]] I mean instructions that expose the internal steps and partial results of what are otherwise considered to be primitive instructions.

One of the best academic and published examples is in the Dally paper referenced at the bottom:
[[Micro-optimization of floating-point operations]].
However, other examples have been found in actual instruction sets, particularly before transistor counts increased to the point where fully pipelined floating point [[FADD]] and [[FMUL]] instructions were common.

= Examples of Floating-Point Micro-Optimization Instructions (from Dally paper) =

Examples from Dally paper: (transcribed not quite exactly)

;Automatic Block Exponent
:Identifying the largest exponent is cascaded additions, aligning all mantissae and adding without normalization.
* Saves: power of intermediate normalizations and roundings, unnecesary shifts
* Cost: Precision, unless extra mantissae width.See also [[block floating-point]], [[superaccumulator]].

;Shift Combining
:An alternative to automatic block exponent used in casxes where order of operations must be preserved: avoids repeatedly shifting left for normalization, and then shifting right for alignment.
;I.e. combines normalization and alignment shifts.
* Saves: power in redundant shifts.
* Cost: precision, sometimes

;Post Multiply Normalization
:Maintain extra guad bits to the right of mantissa, to avoid normalizzation shift, since multiplication of normalized numbers can denormalize by at most one bit position. (Denorm*norm can produce greater shifts.)

;Conventional Optimizations
:E.g.
(A + B) * (A - B)
can [[CSE (common sub-expression)]] the alignment of A and B.
* Saves: power
* Cost: the exposed micro-optimization, possibly requiring a few extra bits of mantissa and exponent.

;Scheduling
:Exposing primitive operations permits more effective optimization by compiler (or, for that matter, by a dynamic or [[OOO]] scheduler).

Dally suggests a fairly horizontal instruction format for these microoptimizations, consisting of
* Exponent Ops
** E+, E1 - exponent add/subtract (EC <- EA op EB)** FF1 - returns shift required to normalize mantisssa MA (EC <- FF1 MA)* LDE, STE - load or store exponent as integer* Mantissa Ops** M+, M-, M* - mantisssa add, subtract, multiply (MC <- MA op MB)** SHR, SHL - mantissa shift left or right; supports [[shifting by a negative count]] in either dirrection** ABS, NEG - zeroes and complements the mantissa sign bit** LDM, STM - loads and stores mantissa as integer** LDF, STF - load and store mantissa and exponent together as standard floating point number* Branch Ops** BNEG - [[branch on exponent negative]]** Bcond - [[branch on exponent and mantissa compare]]] (EA,MA) relop (EB,MB)= Other Possible Micro-optimizations === Booth Encoding ==Many processors use Booth encoding and multiplierarrays,for both integer and floating point.Booth encoding involves (a) preparing multiples of one operand. Unfortunatyely, the actual multiples depeend on how advanced the multiplier is - {-1,0,+1}, {-2,-1,0,+1,+2}, 3X, 4X, etc.(b) using the second operand selecting which multiples of the first operand are to be fed into the array for each digit group.We can certainly imagine [[CSE]]ing the work in preparing such multiples, for eother operand.Unfortunately, the multiples needed change with the exact multiplier used - one microarchitecture might require produced -1X and 3X multiples (1X and 2X are "free", shifting - while another might require 5X, etc.Therefore, the number of bits needed might change from chip to chip.We can imagine storing these large intermediate results in a SIMD packed vector, via an instruction that looks like: vreg256b <- booth_encode(64b)Heck - that might be a useful operation to provide even if not doing microoptimization. It has uses.The details of the Booth encoding used might be hidden.However, perhaps an easier approach might be to do this microoptimization in microarchitecture:e.g. have a [[dynamic scheduler]] recognize several multiplications that share a common first operand,and then decide to skip the [[Booth encoding]] pipestage.The skip might shorten the pipeline - or it might just be used to save power.This amounts to [[memoizing]] the Booth encoding.== Virtual Memory Translations ==There are many, many, repeated translations of nearby virtual addresses that result in the same physical page address.; CacheTranslation with Base RegistersE.g. Austin and Sohi suggested caching the translations next to the base register, and thereby avoiding TLB lookup, and supporting more translatuons on a low ported TLB.

Equivalently, power can be saved.

; Instructions to Save Translations
We can imagine that this might be exposed to software as an instruction that looks like
treg := [[translate_virtual_address]]( virtual address )
dreg := load_using_physical_adddress( treg + offset )
store_using_physical_address( treg + offset)

The first instruction saves the translation, and any permissions bits required, in treg.
treg might be an ordinary address sized integer register, or a special register to hold such a translation.

Note: this instruction, [[translate_virtual_address]], is often requested even outside the context of micro-optimization.
See [[uses of an instruction to save virtual to physical address translation]].

The load and store operations use a saved translation. I would imagine that they would trap if the memory location specified by offset and sizze fell outside the saved translation.

NOTE: in a [[virtual machine]] environment, a Guest OS executing this instruction would get at most a partial benefit.

;User Mode Instructions to Save Translations
Instructions such as [[load_using_physical_address]] can only be used by privileged code - if software can construct arbitrary physical registers.

But if the saved translation lives in a special treg, translation register, that can only be written by certain instructions,
then unprivileged code could employ this instruction.
Equivalently, this could be a [[privilege tagged capability register]] - possibly an ordinary register, with an extra bit that
gets set by the translate instruction.
The physical memory accesses would require that bit to be set.
Other operations on such a register might clear the tag bit.

This is how [[capability registers]] work for other capabilities;
physical addresses are just an extra capability.

Except... physical addresses can change, e.g. during [[virtual memory]] operations such as [[page fault]]s and [[COW]].

(1) we could expose the [[translation registers]] to the OS, which can treat them as an extended TLB, changing them as necessary.
: This is not unlike what old OSes needed to do when [[multitasking using base registers]].

(2) However, we might then need to re-translate. This could be accomplished by storing the original virtual address inside the treg [[[translation register]].

I.e. we have circled back to Austin and Sohi - except that instead of the physical address being a cache, it is more exposed.

Not completely exposed - it is a [[covert channel security hole]] to expose physical addresses.
But it is an explicitly acknowledged, albeit opaque, data quantity.

== Division Step, etc. ==

Any "step" operation, such as divide-step, multiply-step, sqrt-step,
can be considered as a micro-optimization primitive.

With the concomitant problem, that the algorithm, may vary between versions of a processor.

== TBD: other micro-optimizations ==

TBD

= References =
W. J. Dally. 1989. [[Micro-optimization of floating-point operations]]. SIGARCH Comput. Archit. News 17, 2 (April 1989), 283-289. DOI=10.1145/68182.68208 http://doi.acm.org/10.1145/68182.68208

W. J. Dally. 1989. Micro-optimization of floating-point operations. In Proceedings of the third international conference on Architectural support for programming languages and operating systems (ASPLOS-III). ACM, New York, NY, USA, 283-289. DOI=10.1145/70082.68208 http://doi.acm.org/10.1145/70082.68208

RISC versus CISC

2011-02-12T12:11:00.001-08:00

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

* [[RISC (Reduced Instruction Set Computer)]]
* [[CISC (Complicated Instruction Set Computer)]]

[[RISC]] and [[CISC]] have been discussed elsewhere, outside this wiki, in great detail.
I will not try to add much to what has already been written.

However, although I am a RISC sympathizer, I may take a contrarian stance, talking about some of the issues and problems with RISC.
The RISC philosophy was certainly influential. However, in many ways it failed.
I may try to talk about those failures.
And how the so-called [[RISC Revolution]] warped a generation of computer architects.

= Conclusion =

I did not really want to write this article. There is not much to add to all that has been written about the so-called [[RISC Wars]] except to say
that they caused a lot of thrashing, amounted to less than promised, although they did bring some improvements.

However, I could not really write a wiki on computer architecture without mentioning [[RISC versus CISC]].'

I would prefer, however, to discuss interesting aspects of RISC computer architecture, that may not be discussed in many other places,
than to rehash this old debate:

* [[Breaking out of the 32-bit RISC instruction set straitjacket]]
** [[variable length RISC instruction sets]]
** [[16-bit RISC instruction sets]]
** [[RISC instruction sets with prefix instructions]]

* [[post-RISC proliferation of instructions]]

* [[How do you count instructions in an instruction set architecture?]]

* [[Microcoded instructions and RISC]]
* [[Hardwired instructions and RISC]]
* [[Hardware state-machine sequenced instructions and RISC]]

Many of these latter issues are of the form "XXX and RISC", and really should be only of the form "XXX",
except that one of the leftovers of the [[RISC era]] is that it is considered obligatory to explain
how a feature supports or opposes the [[[RISC philosophy]].

= Background =

The late 1970s and early 1980s were an era of increasing complexity of increasing capability and complexity in computers.
The mainframe IBM 360 family was reaching the peak of its influence.
The relatively simple PDP-11 minicomputer
was supplanted by the more complex DEC VAX.
Microprocessors were marching forward: the Intel 8086 started along the road to world domination in 1978,
the Motorola 68000 started along the road to elegant failure in 1979.
Intel had been talking about the
[http://en.wikipedia.org/wiki/Intel_432 Intel iAPX 432]
microprocessor for a while, with features such as bit granular instructions,
garbage collection in hardware and microcode,
a software object model supported by hardware, etc.
People were trying to solve the so-called software gap with hardware, by building computers that more closely mapped
whatever language implementation they were targeting.

Complexity seemed increasing.
In actuality, much of the software complexity was moved into microcode.
Woe betide languages and operating systems that did not match the language and operating system use cases the computer was designed to support.

= The RISC Revolution =

Into this came a bolt of sanity:

David A. Patterson and David R. Ditzel. 1980. The case for the reduced instruction set computer. SIGARCH Comput. Archit. News 8, 6 (October 1980), 25-33. DOI=10.1145/641914.641917 http://doi.acm.org/10.1145/641914.641917Heck - it was not even published in a refereed journal!

One must also mention the [[IBM 801 minicomputer]], arguably the first RISC.

The late 1980s and early 1990s were full of RISC computers, especially microprocessors: [[Power]], [[PowerPC]], [[MIPS]], [[SPARC]], [[Motorola 88K]].
Not to mention many more failed companies.
All seemed destined to replace the IBM mainframe, the VAX minicomputer and,
then, as the importance of the PC market grew, the PC microprocessor.
But only the 68000 Apple PC fell to the PowerPC RISC onslaught.
The VAX and other minicomputers died out.
But the IBM mainframe, and the Intyel x86, continued, the latter spectacularly.

Now, by 2010,
* IBM is slowly transitioning to [[Power]], but the IBM Z-series mainframe stays strong
* the PC world is still ruled by Intel [[x86]]
** Intel's RISC and VLIW projects fell by the wayside
* [[PowerPC]] and [[MIPS]] have been relegated to [[embedded computing]]
* [[ARM]] is the biggest RISC success story, in embedded and, particularly, in low power, cell phones, etc.
** [[ARM]] is likely to be Intel's big competition
* Sun [[SPARC]] survives, barely - but Sun itself got swallowed by Oracle
** Sun/Oracle x86 boxes predominate even here
* DEC is long dead, as is [[Alpha]]

= What Happened? =

Many RISC companies went after the high priced, high profit margin, workstation or server markets.
But those markets got killed by [[The March of the Killer Micros]], specifically, the x86 PC microprocessor.
It is telling that ARM is the most successful "RISC", and that ARM targetted embedded and low power, the low end,
lower than the PC market, rather than the high end.

[[PowerPC]] and [[MIPS]] made a concerted attack on the Intel x86 PC franchise.
Microsoft even provided Windows NT support.
But when Intel proved that they could keep the x86 architecture competitive,
and stay the best semiconductor manufacturer, the "RISC PC" withered.

Intel proved they could keep the x86 PC microprocessor competitive in several stages:
* the i486 proved that the x86 could be pipelined.
** Up until then one of the pro-RISC arguments was that CISCs were too complicated to pipeline. But, see the next section
** I was thinking about Motorola 88Ks about this time, when the i486 started being talked about, and I realized - RISC had no fundamental advantage
* the Intel P5/Pentium did in-order superscalar
* the Intel P6, first released as the Pentium Pro, then Pentium II, did out-of-order
** briefly, the fastest microprocessor in the world, beating even DEC Alpha

Some say that the P6 killed RISC.

A more nuanced view is that RISC was a response to a short term issue:
the transition from board level to chip level integration.
When only a small fraction of a board level computer could fit on a chip,
RISC made more sense. When more could fit on a chip, RISC made less sense.

Not no sense at all. The RISC principles always have value.
But less sense, less of a competitive advantage.
Unnecessary complexity is always wasteful.

Moving on...

= The CISCs that survived were not that CISCy =

The CISCs that failed - DC VAX and the Motorola 68000 - were the most CISCy.
Most instructions were variable length.
Some frequently used instructions could be very long.
Many instructions had microcode.
Many operations had side effects.
They had complicated addressing modes - elegant in their generality, but coompliocated, sometimes neceessitating microcode just to calculate an address.

The CISCs that survived - the IBM 360 mainframe family, and the Intel x86 - were not that CISCy.

Sure, they had some complicated, almost impossible to implement without microcode, instructions.
Just consider x86 FAR CAL through CALL GATE.

However, most of their instructions were simple:
ADD src_reg += dest_reg_or_mem.
True, Note [[load-store]].
But [[load-op]] pipelines were not that hard for the IBM mainframes, and the Intel i486 and P5, to implement.
And the Intel P6 showed that the microarchitecture could be [[load-stiore]], even though the ISA was not.

The IBM 360 family has relatively simple instruction decoding.

The Intel x86 has painful instruction encodings, ranging from a single byte up to 15 bytes.
But the most frequently used instructions are small.
The really complicated instruction encodings, with prefixes, proved possible to (a) implement in hardware, but (b) at a significant performance cost, on the order of 1 cycle per prefix originally.

Most important, these instruction sets had few side effects.
Yes, the x86 has condition codes.
But most x86 instructions overwrite all of the arithmetic condition codes (INC and DEC not affecting the carry flag being the notable exception).
This avoided the sort of RAW hazard on the condition codes that would have been required for an OOO implementation of, say, the Motorola 68000.

= Didn't RISC win anyway? =

Did not RISC win anyway? After all, doesn't a modern CISC processor translate to RISC uops internally?

Well, yes and no. Let's look at some of the RISC principles proposed in early papers

* fixed length instructions - 32 bit
** at the [[macroinstruction set level]], not so much
** at the [[microinstruction set]] or [[UISA]] level, maybe
*** maybe- but definitely not "small". Is it a RISC if the (micro)instructions are 160 bits wide
*** even here, the recent trend is to compressing microcode. Some are small, some take more bits.
** the most popular surviving RISC instruction sets have 16 bit subsets to increase code density

* simple instruction decoding
** ISA level, no
** UISA level - undocumented. Probably. But, again, very wide!!

* software floating point
** nope!!

* large uniform register set
** in the early days, not so much
** over time, the register set has grown. As has the complexity of the ISA encoding, [[REX bytes]] etc.

* small number of instructions
** definitely not!!!
** microcode instruction sets have long been full of many instructions, particularly widget instructions
** even macroinstruction sets have increased dramatically in size since 1990. More than quadrupled.

Some have said that the point of RISC was not reduced instruction count,
but reduced instruction complexity.
This may be true - certainly, this was always the argument that I used *against* rabid RISC enthusiasts who were trying to reduce the number of instructions in the instruction set.
But nevertheless, there were many, many, RISC zealots and managers who evaluated proposals by counting instructions.

= What's left? =

The most important intellectual survivor of the RISC philosophy has been to aversion to complicated microcode sequences.
Expanding instructions to 1 to 4 [[uop]]s may be okay,
but taking a cycle or more to branch into a [[microcode sequencer]], perform the operation, and branch back is a performance penalty nobody wants to take.

The number of instructions in instruction sets has increased dramatically over the past decade.
But the vast majority of these are instructions that can be implemented directly by hardware,
by combinatoric logic,
or by simple state machines in the case of operations such as divide.

One may conjecture that the original RISC aversion to floating point
was actually to microcode floating point:
when the most important floating point operations like [[FADD]] and [[FMUL]] became pipelined,
capable of being started one or more per clock
even though the operation took several cycles of latency,
the objections to FP on a RISC died away.

== Bad Effects ==

We are still paying the cost of certain RISC-era design decisions.

For example, Intel MMX is irregular.
It does not have all the reasonable combinations of
datasize={8,16,32},
unsaturated, signed and unsigned saturation.
This irregularity was NOT because of hardware complexity,
but because management was trying to follow RISC principles by counting instructions.
Even when providing all regular combinations would have made the hardware simpler rather than harder.
(Aside: validation complexity is often used as an argument here, against regularity. The complexity of validating all regular combinations grows combinatorically.)

AMD x86-64 is not a bad instruction set extension.
But life might be easier in the future, if x86 does not die away, if it had been more regular.
More RISC-like.
But in this way RISC was its own enemy:
RISC did not achieve the often hoped for great performance improvements over CISC.
RISC reduces complexity, which does not directly improve performance.
So people went chasing after a Holy Grail of VLIW performance, which also did not pan out.

= Conclusion =

I did not really want to write this article. There is not much to add to all that has been written about the so-called [[RISC Wars]] except to say
that they caused a lot of thrashing, amounted to less than promised, although they did bring some improvements.

However, I could not really write a wiki on computer architecture without mentioning [[RISC versus CISC]].'

I would prefer, however, to discuss interesting aspects of RISC computer architecture, that may not be discussed in many other places,
than to rehash this old debate:

* [[Breaking out of the 32-bit RISC instruction set straitjacket]]
** [[variable length RISC instruction sets]]
** [[16-bit RISC instruction sets]]
** [[RISC instruction sets with prefix instructions]]

* [[post-RISC proliferation of instructions]]

* [[How do you count instructions in an instruction set architecture?]]

* [[Microcoded instructions and RISC]]
* [[Hardwired instructions and RISC]]
* [[Hardware state-machine sequenced instructions and RISC]]

Many of these latter issues are of the form "XXX and RISC", and really should be only of the form "XXX",
except that one of the leftovers of the [[RISC era]] is that it is considered obligatory to explain
how a feature supports or opposes the [[[RISC philosophy]].

Non-speculative or less speculative versus more speculative

2011-02-09T21:01:00.001-08:00

http://semipublic.comp-arch.net/wiki/Non-speculative_or_less_speculative_versus_more_speculative

When discussing [[speculative execution]] techniques such as [[speculative multithreading]] (or [[skipahead]], or [[slipahead]], or ... )
we often need to talk about less speculative and more speculative threads or instructions.

E.g. a later, younger, more speculative load instruction may be blocked by an earlier, older, less speculative store instruction to the same address.

E.g. in [[SpMT]] or [[SkMT]] a less speculative thread may fork a more speculative thread.

Often in early work we only talk about non-speculative threads forking,
and do not discuss the possibility of a speculative thread forking.
Late, it is realized that it is entiirely reasonable for speculative threads to fork.
Thus, often we need to read "non-speculative" in early work,
and implicitly substitute "less speculative".

E.g. a common [[speculative thread management policy]] is to always keep the least speculativethreads,
and cancel any more speculativethreads,
when there is an opportunity to spawn a less speculative thread.

---

Note that "less speculative" is not necessarily the same as "older".
E.g. in a [[fork-on-call]] thread, certain instructions may beindependent of the skipped code,
and be guaranteed to be executed;
whereas other instructions, inside a skipped function,
or older in the [[Von Neumann instruction sequence]],
but are actually more speculative, as in less likely to be executed.
However, it is often too hard to track this, so often discussions
will implicitly assume "less speculative" is "older".

---

Note that it is not always possible to determine the order of speculative threads or instructions.
E.g. one may fork loop bodies out of order, with no known order,
and later string them together as memory items iterated on by the loop are encountered.
However, arbitrarily imposing an order simplifies many speculative algorithms,
even at the cost of potential performance.

---

* See[[spawning versus forking a thread]].

Skipahead Multithreading

2011-02-09T21:00:00.000-08:00

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

[[Skipahead multithreading (SkMT)]] is a form of [[speculative multithreading (SpMT)]]
characterized by "skipping ahead" at certain points in
[[non-speculative or less speculative versus more speculative|non-speculative or less speculative execution to more speculative execution]].

Typically these "certain points" in thecode are places
where there is a well characterized [[control independence or convergence]] point:
* the instruction after a CALL instruction
* end of loop
* later iterations of loop
* IF convergence

I, Andy Glew, coined the term [[SkMT]]
when it became evident that the term [[SpMT]],
which was itself coined by Antonio Gonzales and promoted by me,
was more generic.
I.e. you can imagine creating speculative threads
that do not really skip that far ahead,
but which, e.g. execute past a place where execution would bee blocked,
either an in-order blockage, or where an OOO window would be full.
See [[non-skipahead speculative multithreading]].

Oooo.... I just created a new term: [[slip-ahead multithreading]].It rather nicely encapsulates what I just described,and is consistent with published project names such as [[slipstream]].
In much the same way, I had earlier used the term [[implicit multithreading (IMT)]],
and replaced it by [[speculative multithreading (SpMT)]],
which I am now (after, 10 years ago, 2000) specializing to [[skipahead multithreading (SkMT)]].

The term [[skipahead]] is intended to be contrasted with [[lookahead]],
a term which was once used to characterize all [[out-of-order (OOO)]] execution.

Look-ahead processors.Robert M. Keller, Princeton.ACM Computing Surveys,Vol 7, Issue 4, Dec 1975.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5118&rep=rep1&type=pdf

Managing branch prediction history: copying short history versus pointing to large history

2011-02-06T16:40:00.001-08:00

http://semipublic.comp-arch.net/wiki/Managing_branch_prediction_history:_copying_short_history_versus_pointing_to_large_history

When [[branch prediction history]] was short, 8-12 bits, and global,
then it was not unreasonable to manage the history by copying it.

E.g. in one simulator I actually arranged so that a branch [[uop]]
wrote back, as its result
* an indication of whether it was mispredicted or not
* the taken [[target IP]]
* the branch predictor history to be restored on a branch misprediction.

I.e. the branch prediction history was propagated, in this simulator, from the [[instruction fetch front end]]
across the scheduler to execution, and back again.

While simple, this involves a lot of unnecessary data movement - both for the history, but also for the [[target IP]].
Most machines of my acquaintance create a [[branch information table (BIT)]], holding information for branches in flight.
This avoids copying the history from the front end to execution and back again,
but nevertheless may involve making copies of the history.

I confess an ulterior motive for copying the history and other branch information around: this naturally leads to the number of branches in flight scaling with the window size. Many early OOO designs were crippled by supported too few branches in flight.

Making copies of the history seems silly if, as in a TNT history, they differ only by 2 bits:
new_history := (old_history << 1) | new_branch_taken_or_not

But making copies seems to be required if we want to be able to restore to any mispredicted branch point, i.e. if we want to do [[instantaneous versus incremental branch misprediction repair]].

Making copies works well enough if the branch prediction history is small enough - 8 bits, etc.
But by the time we are talking about 16 bit histories and 32 or 64 bit IPs, we are talking about quite a few bits.

Furthermore, in the late 1990s and early 2000s branch predictors arose with hitherto unseen long histories,
such as Seznec's OGEHL predictor (with multiple history lengths 9, 2, 4, 8, 16, 32, 64, 128, ...).
Copying around a 128 bit history, even to a [[BIT]], is wasteful;
copying around the even larger 1000+ bit histories that have been proposed is even worse.

Hence the interest in pointing to a position in a branch prediction history,
rather than copying the entire history.
On a branch misprediction one would restore the pointer, rather than overwriting the history with a savedcopy.

This would be straightforward for a long [[TNT]] history, since only 1 bit depends on any branch.
You would simply keep a history of total length TL=PHL+BIF, the sum of predictor history length plus branches in flight.
On a misprediction you would restore the pointer in this circular buffer.
(Or equivalently shift the buffer- I suspect that shifting is too power hungry.)

This could scale to almost any length of history, potentially thousands of bits.

Unfortunately, modern [[stew]] histories are more complicated than [[TNT]] histories.
The [[branch IP]], or even both [[from IP]] and [[to IP]], may be [[hashed, e.g. XORed]] into the stew.
This means that several of the youngest bits in the history may change on every branch.
Simply restoring a pointer will not suffice.

TBD: explain stew management in more detail.

Simple strategy: constrain the stew to have only the N youngest bits affected by the most recent branch. Bits TL..N are unaffected by the most recent branch, except for shifting.
One can then keep a copy of the parts of the history affected by recent branches, the N youngest bits, and a pointer that locates the older bits.

= See Also =

* [[How to use a really long predictor history]]

Branch Prediction Stew

2011-02-06T00:21:00.000-08:00

{{Terminology Term}}
http://semipublic.comp-arch.net/wiki/Stew

The [[stew]] is a form of history used by certain branch predictors.

See, for example, US patent 7143273,
Method and apparatus for dynamic branch prediction utilizing multiple stew algorithms for indexing a global history,
Mile, Slade, and Jourdan,
filed March 31, 2003,
assignee Intel.

A simple [[branch predictor history]] might be a simple [[TNT]] history,
with 0s corresponding to non-taken and 1s corresponding to taken.
Such a simple TNT history cannot distinguish some convergeing paths,
and indirect branches.

US7143273
describes one embodiment of a stew as
stew = ((stew << 1)|new_bit ^ ip)

A stew formed in this way can distinguish converging paths such as ("if true" means a condition that evaluates as true, not an unconditional branch):
   L1: if true got L2
   L2: if true goto L99
   L10: if true goto L11
   L11: if true goto L
   L: if ?? goto L99

However, it does not distinguish multiple branch targets and paths out of an indirect branch, such as
   L1: Reg:= IL1; if true goto L2
   L2: if true goto L99
   L10: Reg:=IL2; if true goto L11
   L11: if true goto L
   L: if ?? goto [Reg]
   IL1: ...
   IL2: ...
It can be seen that mixing in arc information as well as node information remedies this situation,
and distinguishes different paths so long as the hashes do not collide:

stew <<= number_of_bits_to_discard
stew = hash( stew, from_IP, to_IP, taken/not_taken, ...)

Issue: how many bits to use? Which may vary as a function of the type of branch: e.g. a direct conditional branch
may not need as many to_ip bits to be hashed in
as a completely random indirect branch.
Similarly, indirect calls and returns may be handled separately.

(TBD-IP)

Slow :-(

2011-01-31T21:10:00.003-08:00

Minor bitching: writing in the comp-arch wiki is so slow.

Hard to get big chunks of time.

Hard to write big chunks when I don't have big chunks of time.

But at least my present employer allows me to write this. And does not forbid me, like my past employer.

I wish that I could average 1 new page a day. Instead, I am averaging less than half a page a day, and probably less than 1 substantial page a week.

OOO_versus_Runahead_versus_Log-based_replay_for_runahead

2011-01-31T21:03:00.001-08:00

http://semipublic.comp-arch.net/wiki/OOO_versus_Runahead_versus_Log-based_replay_for_runahead

In the era of Willamette I suffered a moral dilemma - or, rather, a dilemma of morale.
I had evangelized [[OOO execution]] with P6.
But I had been introduced to runahead.
And runahead execution seemed to be asymptotically as good as OOO execution,
as memory latencies got longer - i.e. as we entered the era of [[MLP (memory level parallelism)]], which I was then starting to evangelize.

OOO execution is ... well, I'll assume you know what OOO is, or can read about it [[OOO|elsewhere]].

= What Runahead Is ==

[[Runahead]] consists essentially of
* executing
* when an unpredictable, long-latency, event such as a cache miss occurs
** take a checkpoint
** mark the result invalid
* continue executing past the checkpoint in a speculative manner
** saving speculative values into registers
** saving speculative values into a store buffer, or similar [[memory speculation datastructure]]
* when the cache miss returns
** discard all speculative state, registers and memory
** restore from the checkpoint.

= Runahead and OOO are asymptotically equal =

Runahead is a comparatively simple action.
And, in some sense, it gets nearly all of the benefit of OOO.
I.e. as memory latencies increase to infinity and execution latencies becomeinfinitesimal by comparison,
runahead execution will approach OOO execution in performance.

Normally, barring funny effects, runahead will always be lower performance than OOO.
For the same size of instruction window.
But runahead is much cheaper in hardware, and can potentially runahead much farther than OOO for the same hardware cost.
Both runahead and OOO are limited by the [[memory speculation datastructure]];
but runahead need build no large physical register file, etc., save only for a number of RF checkpoints.

= [[log-based]] =

Confounded by OOO/run-ahead, I looked for something better than runahead in some asymptotic sense.
Hence [[log-based]] execution - specifically [[log-based verify re-execution]].

Although subsequently I applied [[log-based]] to [[speculative multithreading]],
at first I thought about it only wrt the same [[single sequencer microarchitecture]]
as OOO or runahead:

Imagine that you are executing in a runahead manner.
However, instead of re-executing all of the instructions after a cache miss returns and a checkpoint is restored,
instead you (1) record all of the results of runahead execution in a log,
and (2) you execute instructions out of the log.

This raises several questions:
Why would this be any faster than runahead?
Why would it be any "larger" than OOO or as large as runahead?
Why would it be as cheap as runahead?

Let;'s answer them out of order.

;Why would this be as cheap as runahead?

Well, if you had a dedicated log [[hardware datastructure]] it would not be.
However, the log is accessed sequentially during [[verify re-execution]].
Sequential access patterns can be easily prefetched.
therefore, you could put the log in slow memory - potentially in main memory.
you might need some fast hardware log to "start off" the verify re-execution,
sufficient to tolerate the latency to main memory.
Equivalently, you might manage cache replacement to ensure that the oldest entries in the log are not displaced from a cache of main memory,
as they normally would be in LRU.

;Why would it be any "larger" than OOO or as large as runahead?

As explained above, the log need not be a small size hardware datastructure. It could potentially scale in size as main memory.

;Why would this be any faster than runahead?

Two reasons.

First, [[verify re-execution]] is inherently more parallel than normal execution.

I like to explain this using repeatedly increment a register as an example:

r9 := load(cache misss)
INC r9
INC r9
...
INC r9

If INC is unit latency, then runhead re-execution would take N cycles to re-execute N such INCrements of a register.

However, in [[log-based verify re-execution]],
the example code above would be rewritten in the log as

r9 := load(cache misss)
assert(r9 = 1042)
INC r9 // assert(r9=1042); r9:= 1043
INC r9 // assert(r9=1043); r9:= 1044
INC r9 // assert(r9=1044); r9:= 1045
...
INC r9 // assert(r9=1042+N); r9:= 1042+N+1

i.e. the instructions rewritten for storage in the log,
and for [[verify re-execution]] out of the log, consist of nothing except moves of a cionstant to a register.
Rather than N cycles, these would take N/IF cycles, where IF is the instruction width.

Furthermore, there are many optimizations that can be applied to the log:
removing redundant asserts and redundant overwrites, etc.
In general, for a block of register based code,
[[log-based verify re-execution]] has one assert for every live-in,
and one constant to register move for every live-out.
Assuming the assertions are met.
(And if the assertions are not met, fall back to normal (re-)execution.

The second reason for log-based verify re-execution being faster is this:

Normal runahead re-execution is limited by cache associativity.
If you have N independent memory references that were cachemisses prefetched by the runahead speculative execution epoch,
they are normally independent, and all prefetched.
EXCEPT when they happen to collide in the cache, e.g. in the limited associativity cache.
In which case, another runahead/checkpoint/re-execution would begin.

Log-based verify re-execution suffers this not at all.
If a cache missing load is thrashed out of the cache,
its value is still present in the log,
and dependent instructions can still be executed - or, rather, verify re-executed.
You will need to pay the memory latency to fetch it and verify, but that can be overlapped.

= Conclusion =

Log-based verify re-execution, or`replay, for runahead
is asymptotically faster than ordinary runahead in two senses:
non-cache miss execution latency,
and cache thrashing.

Ultimately, the fashion or fad of runahead petered out.
Runahead did not replace OOO, although it caused much heartburn.

Runahead did not replace OOO because, although asymptotically better than OOO, we aren't at the asymptote.
Execution unit latencies are not 0, and cache misses infinite.
OOO handles both.

Also, runahead may consume more power than OOO. This is somewhat debatable:
OOO's hardware datastructures may waste power, e.g. leakage,
whereas runahead may consume static power.

Probably the biggest reason why runahead did not supplant OOO in the late 1990s and early 2000s is this:
runhead is only as good as OOO.
It doesn't do anything new.
OOO was an already established and well understood technology by the time runahead appeared on the scene.
Although runahead has putative benefits, they were not enough to warrant a switch-over.

Be this as it may, log-based verify re-execution is a technique that rose out of the [[Runahead versus OOO]] debate.
It is better than runahead in some asymptotic senses. And it has application to other areas, such as [[SpMT]].

= Hybrids =

Of course it is possible to create hybrids of OOO, runahead, and log-based.

For example, one need not record all instruction results in the log. One can re-execute that which is fast,
and only record in the log that which is slow.

Similarly, an OOO machine need not record all speculative results in the instruction window.

Onur Mutlu and others have proposed hybrids that fill an OOO instruction window, and then use runahead.

Cygwin X multidisplay bug

2011-01-29T17:05:00.000-08:00

Today I figured out a problem that has been plaguing me on Cygwin for a year or two, since things broke in an update. (I probably figured it out before, but neglected to record or remember it.)

When I start up Xwin -multiwindow, using windows manipulated by MS Windows rather than a desktop in an MS Window window (try saying that fast), the initial xterm was always invisible.

Eventually I realized that if I maximized it from the MS Windows task bar, I could see it.

Apparently, this window was being created at location (0,0) in a bounding box for my multi-display configuration. (That's multiple physical displays, not multiple X displays.) However, location (0,0) was invisible - since my multi-display configuration has a big tall portrait mode window in the middle for reading PDFs, with flat landscape displays on either side for webpages. The portrait display rising above landscape displays.

By the way, it is actually +1+1 asthe default location, not +0+0. Minor difference.

I need to play around and see if I can find a guaranteed visible place.

Removing the geometry spec seems to work okay for me.

Why_full-speed_denormal_handling_makes_more_sense_for_CPUs_than_CPUs

2011-01-28T12:25:00.001-08:00

http://semipublic.comp-arch.net/wiki/Why_full-speed_denormal_handling_makes_more_sense_for_CPUs_than_CPUs

o a collector of computer architecture trivia like me,
it was quite remarkable
that the Nvidia Fermi GPU
provides full-speed support for denormal operands and results,
whereas Intel and AMD CPUs, at the time of writing, do not.

By the way, terminology: [[full-speed support for denormals]] is not quite the same as [[hardware support for denormals]].

The first question is whether you provide hardware support,
or whether it is necessary to [[trap to microcode or software]], to provide the denormal support.

The second question is,
if you do provide hardware support for denormals and do not need to trap to microcode or software.
Even if denormals are performed in hardware, there may be a performance cost:
it may cost latency, e.g. 5 cycles for an FADD rather than 4 cycles;
or it may cost bandwidth.
The latency and bandwidth impacts are related but may be decoupled:
e.g. it is possible that a scheduler can arrange so that throughput is not reduced even if latency is increased,
so long as there is sufficient [[ILP]].

By [[full-speed denorms]] we mean mainly that throughput or bandwidth is not affected.
E.g. you may arrange to add to the latency of all FP ops,
to avoid [[writeback port collisions for operations with different latencies]].
Since GPUs are throughput machines, this is usually a reasonable tradeoff;
on some GPUs even integer arithmetic is stretched out to 40 cycles.

So, why would a GPU like Nvidia Fermi provide full-speed denorms,
whereas x86 CPUs from Intel and AMD do not?

Let's skip the possibility of a marketing bullet.

Remember [[GPU-style SIMD or SIMT coherent threading]]?

If a GPU takes a trap, or otherwise takes a hiccup, to handle denorms, then not only is the current thread impacted.
All 16 or 64 threads the [[wavefront or warp]] are impacted.
And if only one of the [[spatial threads]] in the [[warp]] is taking the trap,
the efficiency of the machine decreases by at least 16-64X in that period.
Let alone the possibility that the denorm handling code is also not well suited to a GPU.

I.e. the relative cost of [[denorm handling via trapping]] is much higher on a GPU than on a CPU.
Even denorm handling in hardware, in a manner that impacts latency or throughput,
is relatively more expensive and/or harder to deal with.

Hence: there are good technical reasons to do [[full-speed denorm handling]] in GPUs.
These reasons are not quite so compelling for CPUs
- although I predict that ultimately CPUs will be compelled to follow.

--

Ancedote:on one of my few trips to Pixar,I talked to Bruce Perens about denorm handling.Apparently Pixar would be happily rendering a movie at high speed,and then Bam! they would have a scene like a night sky, black, full of denorms,and performance would fall off a cliff.We talked about flush-to-zero modes, which Intel x86 CPUs did not have at that time.I suggested biasing the numbers, e.g. adding 1 or similar,to prevent getting into denorm range.Now that x86 has flush-to-zero the need for such [[kluge]]s is greatly reduced.But, denorms exist for a reason.flush-to-zero can introduce artifacts,and always introduces [[FUD (Fear, Uncretainty, and Doubt)]].[[Full-speed support for denorms]] may just be the coming thing,a place where GPUs lead the way for CPUs.

ISO mediawaiki macro

2011-01-27T18:35:00.000-08:00

I'm still using mediawiki for my comp-arch wiki.

I want a "macro", something like

   {{acronym_and_term SIMT "simultaneous multithreading"}

that will create pages

   SMT
   simultaneous mulrtithreading
   SMT (simultaneous multithreading)

and redirect them all to
   simultaneous multithreading (SMT)


Come to think of it, a primitive
   {{create_redirect_to_current_page Redirect_From}
would be nice.

I imagine that it would first see if the Redirect_From page already exists. If not, it would create
it, redirecting to the current page. If so, it would probably not do anything - which might be a minor lossage if
the Redirect_From page doesn't link to the current page, but which allows things like disambiguation pages.

Perfunctory attempts to find this on mediawiki fail; I'm not sure where to go ask (and I confess to not liking the wikimedia community).

Processor redundancy: FRC/TMR/QMR RAS

2011-01-27T12:46:00.001-08:00

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

---

[[FRC]] - [[failure redundant computation]]. A fairly generic term.
However, at Intel prior to 1990 or so it often referred to [[master-checker]] pairs
- microprocessors wired tiogether at the pins,
one chip driving the pins,
the other comparing what it would drive, were it not configured in FRC checker mode,
to what is actually being driven.
If a different is detected, an error is asserted.

[[TMR]] - [[three module redundancy]] - three processors, voting to choose outcome.
The loser may be deactivated, failing down to [[FRC]].

[[QMR]] - [[quad module redundancy]] - usually 2 [[FRC]] pairs. NOT a voting scheme.
One [[master-checker]] pair is designated active, and its outputs are actually used.
The other [[master-checker]] pair is designated inactive.
If the active pair exhibits a difference,
it is failed, and the other pair continues the computation.

The inactive pair follows the computation so that its state will be "hot".
It probably makes sense to compare the inactive pair's results to the active pair's results,
although if there is such a difference between the pairs
but not within the pairs, it is not clear which can be trusted.

---

[[TMR]] and other voting schemes requires somewhat challenging external voting logic.

[[FRC]] [[master-checker]] pairs require much less external logic: most logic is within the CPU chip.

[[QMR]] is built out of [[FRC]] [[master-checker]] pairs.
It requires no voting logic.
The comparison logic is within the chip, as in [[FRC]] pairs.
You might imagine needing external logic to select which pair's outputs should be used;
however, this may not be necessary
if you trust the einternal logic of an FRC pair to disable its outputs.
I.e. if asserting FRCERR from a checker can reliably disable the master's outputs, then no external logic may be needed.

However, such multiple drivers per signal configurations are now deprecated (circa 2010),
so external muxes may be necessary.

---

Above we have talking about FRC/TMR/QMR between chips.
However, it can be applied to any logic block, potentially within the same chip
(although then chip failures might corrupt both).

Similarly, we have talked about doing FRC/TMW/QMR RAS for processors,
but these techniques can be applied to non-processor logic.

ublic_comp-arch_wiki_shut_down_because_of_attack_corruption

2011-01-16T16:26:00.003-08:00

The title pretty much says it all:
the public comp-arch wiki was shutdown because of an attack
that caused corruption
- specifically, pages direct to what can only be assumed to be malware infested websites

See [[WikiAdminLog: Description of attack on wiki.public.comp-arch.net, November 2011]].

My hope has long been to have a wik site for computer architecture discussions.
I set up a semipublicarea, writeable by me and readable by the world,
and a public area, read/write by the world
(with whatever security mediawiki provides, e.g. Captchas).

The public site has been attacked twice.
Can't really say that the security was broken,
just that the attackers or spammers took advantage of the openness of wiki.

Shutting it down.
Jan 16, 2011.

http://wiki.public.comp-arch.net/ - public wiki - now shut down

semipublic wiki still okay:
http://comp-arch.net
http://semipublic.comp-arch.net
https://www.semipublic.comp-arch.net/wiki/index.php?title=Main_Page

Description of attack
https://www.semipublic.comp-arch.net/wiki/WikiAdminLog:_Description_of_attack_on_wiki.public.comp-arch.net,_November_2011

This page
https://www.semipublic.comp-arch.net/wiki/WikiAdmin:_public_comp-arch_wiki_shut_down_because_of_attack_corruption