Disclaimer

The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, 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, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Tuesday, November 16, 2010

Array_Ports:_Dual_Port,_Multiport,_etc.

I keep plodding along:

http://semipublic.comp-arch.net/wiki/Array_Ports:_Dual_Port,_Multiport,_etc.

wikied, USEnet comp.arch posted, andblogged

= Array Basics =

The classic array is a 2D crosspoint array of memory cells.

In an SRAM based array, the memory cells are cross-linked inverters (or a degenerate version thereof).
In a DRAM based array, the memory cells are capacitors.
In other memory technologies, the memory cells may be a floating gate (which is really a capacitor),
a bit of glass that can be melted, magnetic material, etc., etc.

>2D arrays are possible - but 2D is the basic.
(Actually, 1D memories have been created - e.g. delay lines, magnetic bubble racetrack memory, etc. - but that is not in the scope of this topic.)

Conventionally, one of the two dimensions, let's say X, horizontal, carries word lines, or decoded address lines.
The other, Y, vertical, carries bit lines or data lines.

    (I don't want to say just "bit lines", since multivalued logic is a possibility.)

One of the word lines is activated, and it selects all of the memory cells along that word, and causes them to connect to the bit lines. Either the value is read out, or a new value is written in.

    Usually only one word line at a time is activated. Although you could activate more than one, e.g. and OR or AND the several bits selected for read. Conversely, you could write a value to multiple words at once. However, this is uncommon; it often pushes the edges of circuitry; and some systems will, in fact, have logic to prevent this from ever happening.

= A Single Port =

Sometimes there is a single bitline; sometimes there is a pair of bitlines, typically Q and Q-bar.

Sometimes there is a single wordline, and another wire, often parallel to the wordline, that indicates read or write.

Sometimes there are separate wordlines for read and write.

== Minor Tweaks ==

Read/write is a "diffuse" signal: while there must be a word line per, well, word, for a single ported array we might be able to have a global signal that said "write". Such a global signal could be, well, diffuse - signaled in the ground plane, etc. Possibly by a light shining from the 3rd dimension. Or you could route the write enables vertically, or diagonally. Usually there are not good ideas, costong more than they save in area or power.

However, you can share read/write lines between pairs of wordlines. Or even larger sets of wordlines, at the cost of routing to get the signal to where it would need to go.

See [[byte write enables]] or [[subword write enables]]

= True Multiport Arrays =

The simplest possible array might have a single bitline, a single wordline, and a read/write signal.
Typically two horizontal wires, and 1 vertical.
This would implement a single port that can be used for both read and write.

The next step in complexity would be to have
* a read port, with a wordline and a bitline
* a write port, with a dedicated wordline and a bitline

I call these true ports because almost arbitrary words can be simultaneously accessed in the same array.

    Almost arbitrary... often there are constraints, such as * never writing to the same bitcells (words) simultaneously * never reading and writing the same bitcells simultaneously * sometimes never reading from more than M ports at a time. sometimes, the read limit M=1

In general, each true port costs 1 X and 1 Y wire.
This implies that true ports have an area cost of O(N2).

    At least. Many technologies require dual bitlines, or, two bitlines to write, 1 to read. Note the possibility of a hybrid port with three wordlines and two bitlines, using bit/bit-bar to write, and reading on each bitline separately.

Simple arrays with small numbers of ports may not be wire limited: they may be limited by the bitcells.
But, as the number of ports grows, eventually the O(N2) effect kicks in.

    == Enumerate Ports when designing Arrays == Because of the possibilities of odd tradeoffs, such as combined read;/write ports, or 1 write 2 read ports, it is desirable to enumerate all of the ports you need in your [[abstract array design]], and also to think about which ports may not need to be simultaneously active.

= Array Replication for Read Multiporting =

One way to mitigate the O(N2) effect of ports is to replicate the array.
E.g. a 2-read port, single write port array
may be implemented as two 1R 1W arrays,
with separate read ports,
but the write ports tied together.

Similarly, 2R-1W has area 9c, whereas 2x1R-1R has area 2(4c) = 8c.
The effect gets bigger as the number of read ports increases.

However, there is often a cost to distributing the wires to the arrays.
Simplistically, if all flows along a single datapath, there is O(n2) cost to "turning" the wires to go to the separate array.
However2, circumstances may vary: it may not be necessary to turn all the wires back into the same datapath, etc.

    ;Bluesky (at the time of writing, 2010): If you can work with the third dimension, the costs of such array replication to get extra read ports is lowered: whereas in 2D routing to a separate array costs O(N62), in 3D routing to a separate array placed on a layer above the first is O(n).

= Time Multiplexing =

Another way to get multiple ports is by time multiplexing.

You might, for example, "double pump" an array to get effectively twice the ports.
This can even be done with wave pipelining.

Similarly, you might know by construction that reads can only occur, in 2 out of every 3 clock cycles, while writes may occur only every third clock cycle.

If you cannot make such guarantees, it is necessary to have a mechanism for handling conflicts.
If you can make average rate guarantees but not instantaneous rate guarantees,
a few buffers may suffice.

= Banks =

Banks are a form of spatial multiplexing.
Similar to array replication, but without tying together the write ports.

Address bits are used to assign requests to particular banks.
This weighs heavily in favor of power of two sized banks,
although [[non-power-of-two-sized indexing]] is possible.
especially for arrays relatively far out in the memory subsystem, such as DRAM (e.g. Matrox had 17 way interleaved memory)
or outer level caches.

Bank selection bits may be chosen so as to interleave - successive words in the logical arrray may be assigned to different banks. Or they may be coarse grained - e.g. the lowest half of the address space is assigned to thefirst bank, tyhe upper half to a second bank.

The two may be intermixed - interleaving, and coarse grain banking.
Indeed, there may be multiple levels of interleaving and coarse grain banking.

Before we leave this topic, I want to mention that cache lines may possibly be subject to both
intra-cacheline-banking, and inter-cacheline-banking.
E.g. a 64B (512b) cache line may be divided into 8B (64b) banks within the cacheline,
while the cachelines are interleaved between coarser scalee banks.

= Terminology: Banks, Ranks, etc. =

Terminology may vary.

I (Andy Glew) tend to follow my standard practice of using [[standard terms, with distinguishing adjectives]].
E.g. I say any division of an array is a bank, and the process of distributing addresses across the banks is an interleaving pattern.

Other people invent different terms:
e.g. banks within a DDR DRAM;
DRAM chips mounted on DIMMS, operated as separate ranks;
memory may be interleaved across different DRAM channels.


= Bank Conflicts and Other Port Conflicts =

Whenever there are not enough ports to meet all needs the possibility of conflicting accesses arises.

More terminology: I sometimes call banking pseudo-multiporting.

With power-of-2 bitfield extraction used to create the bank selection and indexing functions, there often arise "resonances" on common power of two boundaries. Such as 64KiB, 1MiB, etc.

Simple hashing, XORing a few upper bits into the indexing and selection functions, sometimes helps.
Non-power-of-two indexing can also help.

Mechanisms to handle bank conflicts can lead to great complexity.

The simplest case would be to stall one of the requests.
Simple - unless you are working on a statically scheduled machine without pipeline interlocks.

Simple - but of course immediately stalling is impossible in many high speed designs.

Replay or recycling the request is another way of handling bank conflicts:
a fixed pipeline's worth of requests drains out,
and is routed back to the pipeline or arrays inputs to be retried.
This is a good workable idea - but it can cause positive feedback leading to unstable behavior.
See [[Replay Pipelines]].

I don't know of any other alternatives to stall or replay - although there are many flavors of each.
However, the microarchitecture can arrange things so as to mitigate the cost of bank conflicts,
(or other port conflicts):

E.g. P6 had a pseudo-dual-ported, banked, L1 cache array, with 1 read and 1 write port. The read port always took priority, since handling such conflicts on a read is more complex because dependent operations may be scheduled.
Whereas write port conflicts, while affecting bandwidth, do not have dependejnt operations.

Similarly, what I call a [[2 and a half ported array]] is another nice design point:
true dual ports used for two read ports,
with a write port using pseudo-multiport banking.
Bank conflicts on the dual ported reads are avoided, while on the writes bank conflicts can sometimes be tolerated,
or scheduled around.

= Related =
* [[Bank scheduling]]
* [[Read and Write Combining]]

Saturday, November 13, 2010

Content Based Query Install

Throwing documents into my document archive, I realize one of the forms of semantic exposure of deduplication that I want:

When I say "put(file)", if file is already in the archivem I want to get told "Hey, you, the file is already in the archive!!!

Perhaps not under the name I want to put it in.

put(Archive,nameInArchive,file) => warn if already there

put(Archive,nameInArchive,file,force=1) => force install, even if already there


Interactively, I want the default o be "don't install if already there".

Editing History

Messing around with Mercurial to keep my stuff in synch, while working on ulfs.

While I am reasonably happy with my scheme for synchronizing partial checkins and checkouts - not merging, but making candidate for merge - it's not yet ready for prime time. Hence my use of Mercurial.

Can't say continued use of Mercurial, because I have only lately switched to using Mercurial from Git.

Anyway: historically, the main reason for wanting to be able to edit history has been legal. E.g. if a court settlement or a sale meant that you were not supposed to have versions of a file that is determined not to belong to you.

Today, another reason: Mercurial on cygwin kept dying. Looks like it was related to large files. I really wanted to remove those large files from the history, but the "Though shalt not edit history" attitude got in the way. Used hg strip, but that was too much; I really just wanted to delete a few entries. Not enter a counteracting entry, but to delete the original.

Really, I am using DVCS not just for revision control of a single project, but for history tracking of an archive of largely unrelated files.

This should not be that hard. Mercurial docs make noise about names incorporating all content checksums. ... Well, while that might be a good integrity check, it suggests that such content based naming is not so great an idea. If it makes history editing hard.

Realistically, all versions of all objects should have names separate from content hashes.

Scratch that: s/name/key/

All versions of all objects should have (a) content hash names, and (b) non-content hash names.

This applies just as much to the "indexes" that list all file versions in a contour, as to individual files.

The history data structure is the interesting issue: should version-sets point to parent version sets, and, if so, by what name? If V3->V2->V1, what happens if V2 gets deleted. How do we convert V3->...->V1 to V3->V1? Especially if V3->V2 lives outside the current repository?

This suggests we may want to keep version-hashes of objects deleted, if only to act as placeholders, and to prevent them from getting recreated.

Saturday, October 30, 2010

Compacting Patent Plaques

Somewhat bittersweet: am today compacting and throwing out my patent plaques. Circa 60-70 of them - eventually I started asking Intel *NOT* to give me any more plaques. They just take up too much space, are a pain to move. Need the bookshelf space.

At the moment I am unscrewing the metal engraving. I'll keep the metal with the actual patent engraved on it. Maybe one day I will actually mount them. But I am going to throw out, discard, recycle, the wooden boards. I wonder if my daughter's school woodshop would want them.

Maybe I'll use the metal for something. Melt it down.

Like beating swords into ploughshares?

Tuesday, October 19, 2010

Textual notation for indexed summation, etc.

I grew up with mathematical notations such as
sum i=1,n n^i

Now, I really believe that our programming systems should support such mathematical systems.

But seeing as most don't, I often wrestle with textural notation.

Here's a pleasant textual notation I came up with today:


first, the usual sum or sigma:
sum for i from 1 to N of A[i]

to create a vector
v[i], i=1,n
::== vector for i from 1 to N of v[i]

combining
vector for j from 1 to N of
sum for i from 1 to N of A[j+i]*B[j+N-i]

other
integral for i from 1 to N of f(i)
union for i from 1 to N of f(i)
intersection for i from 1 to N of f(i)
product for i from 1 to N of f(i)
continued fraction for i from 1 to N of f(i)
::== 1/(1+1/(f(1)+1/(1+1/f(2) + ...

2D
array
for i from 1 to M,
for j from 1 to N
of A[i,j]

3D
array
for i from 1 to N,
for j from 1 to M,
for k from 1 to L
of A[i,j,k]

shaped
array
for i from 1 to N,
for j from i to 2*i,
for k from 1 to j
of A[i,j,k]

Monday, October 18, 2010

Inner Product Instructions

http://semipublic.comp-arch.net/wiki/index.php?title=Inner_product_instructions&action=edit


The mathematical inner product or dot product is often desired in vector instruction sets. However, it poses some challenges for the instruction set designer.

= Integer Dot Product =

For example, consider an integer inner product. E.g. for 4 inputs
A0*B0 + A1*B1 + A2*B2 + A3*B3

If the arithmetic is 2's compliment, signed or unsigned, without overflow, this can be evaluated in any order. Indeed, one need not perform carry propagating adds for the products; we can combine the sum of the products with the sums involved in multiplication, in a redundant, carry-free, form.

However, if we are to detect overflow, or equivalently perform saturation, issues are raised. How are the calculations associated:
(((A0*B0 + A1*B1) + A2*B2) + A3*B3)
or
((A0*B0 + A1*B1) + (A2*B2 + A3*B3))

Should we detect intermediate overflow, or should we ignore overflows that are "corrected" by subsequently adding in numbers of opposite sign. I.e. should we perform calculations as if using extended precision intermediate accumulators or temporary values.

If saturating, e.g. if using leftmost association, when we saturate for overflow should we stay saturated, or should we allow the saturated value to be brought back into range? Etc.

All of these boundary cases are annoying.

Glew recommendation: for small vectors, either don't do overflow detection, or calculate as if in extended precision and detect at the overflow at the end.
* Pro: easy to describe and understand
* Con: gives different results compared to doing scalar calculations in straightforward loops (with overflow detection)

Consider calculations as if in a specific order, typically leftmost or tree.

A hybrid approach is possible: calculate in the fastest possible way, e.g. tree, but then have a slower calculation detecting overflow. CON: extra power.

= Floating Point Dot Product =

Floating point dot product instructions have the same issues of order dependence as described for integer dot product with overflow detection - with the additional issue of rounding. Even in the absence of overflow,
(((A0*B0 + A1*B1) + A2*B2) + A3*B3)
or
((A0*B0 + A1*B1) + (A2*B2 + A3*B3))
may give different answers.

As before, some instruction sets define particular orders of evaluation, while some leave it undefined. Some also define an "infinite intermediate precision" form of inner product, where the sums are formed without rounding, and only rounded (and overflow detected) at the end.

[[Superaccumulators]] are a more general form of such arithmetic.

In the absence of such special support, floating point dot product instructions
with linear, e.g. leftmost, associativity are little faster than a succession of [[FMA]] or [[FMAC]] instructions.

= Alternative Inner Product Support =

Alternative instructions that can be used to synthesize dot products and other
possibly order dependent [[vector reductions]]
may be motivated by the issues discussed above.

For example, horizontal or pairwise add instructions, such as Intel SSE3's PHADDW:
2 packed vector inputs
A0, A1, A2 ...
B0, B1, B2 ...
1 packed vector output
A0+A1, A2+A3 ..., B0+B1, B2+B3, ...

Pairwise add could, of course, be done on a single vector operand, but then the
output would only be half-length.
Combining two vector operands in this manner produces a full-length vector output,
which is convenient.

Wiring-wise, if the A and B vector operands are interleaved
to allow [[vertical add]], this only requires wires sufficient to
route A1 to A0, and vece versa.

Note that horizontal add is "only" a combination of a vector interleave or shuffle operation,
and a vertical add. The interleave operation, however, wants to produce two vector outputs,
or else occupy two instructions (or produce a double width vector operand, or pack two singles into
double precision vector elements (but then what do you do for double precision inputs), or ...)
2 packed vector inputs
A0, A1, A2 ...
B0, B1, B2 ...
2 packed vector outputs
A0, B0, A2, B2 ...
A1, B1, A3, B3 ...
Vertical add
A0+A1, B0+B1, ...

Vertical, element by element, multiplication,
combined with sufficient horizontal adds to perform the sum,
builds a dot product.

Or, a single instruction may combine vertical multiplication and horizontal pairwise addition:
2 packed vector inputs
A0, A1, A2 ...
B0, B1, B2 ...
1 result
A0*B0+A1*B1, A2*B2+A3*B3, ...

E.g. Intel SSE3's PMADDUBSW.
The putative problem of having only half as many vector elements in the PMADDUBSW output is
handled by doubling the precision,
taking 8 bits as input and producing a packed 16 bit vector as output.
Unfortunately, that technique does not work so well for floating point.

= Vector Parallel versus Vector Sequential =

Defining dot product with leftmost associativity
for purposes of overflow and rounding,
is well suited to a [[vector sequential]] implementation.

[[Vector parallel]] implementations are better suited to horizontal adds,
and other parallel orders of summation.

Modern instruction sets such as SSE tend to have [[vector parallel]] implementations.

It is possible to mix vector parallel and vector sequential,
although a latency penalty is paid when transitioning from vector sequential to vector parallel.

Thus we begin sliding down [[The Slippery Slope of Vector Instruction Sets]]:
there are so many different possible definitions of the vector instructions,
with different evaluation orders,
suited to different microarchitectures.
It is easy to define the most basic vector instructions.
Completing the coverage of vector instructions is more challenging.

WebDAV for my wiki?

I want to have drawings, etc., for my http://comp-arch.net wiki.

But I have thrashed on how to get them. I've tried too many different drawing tools for wiki - all have weaknesses.

I am now leaning towards WebDAV. Indeed, I am leaning towards rebuilding my wiki around WebDAV.

WebDAV basically is a filesystem implemented across web protocols.. If you are lucky enough, your favorite drawing program knows how to access a file stored on WebDAV. Or, you may have a tool that allows you to mount WebDAV as a filesystem on Windows or Linux or whatever, allowing almost any tools to access it.

The problem with WebDAV is that it IS a filesystem Just exporting a filesystem across the web is not very interesting. Listings of files in whatever tools you want - PowerPoint, Visio, Inkscape, etc.

But, I think if I write my own WebDAV server, combined with a wiki, it can be better than this. When a file is stored to WebDAV, I can arrange to convert it (if I understand its format) into a format that can be directly viewed by most, if not all, web browsers. E.g. GIF, although I am more hopeful about a vector forma like SVG. Plus, I can provide a link to the original format, .PPT or .VIS or whatever.

Not just for drawings.

Wiki text might be edited by a wiki editor, or potentially accessed by WebDAV and edited in your favorite text editor. My favorite would be EMACS. In org mode?

Heck, Word and PowerPoint and PDF and PS coud be uploaded. Although I prefer not. Viewed in the browser, if known how.

---

I was planning on a WebDAV server with git or hg or bzr as the versioning backend.

All I really want from WebDAV is the ability to click on an edit link and, on your favorite OS, open whatever program is associated with that file's type.

E.g. for a .PPT open PowerPoint or OpenOffice; for a .VIS (or whatever Visio uses) open Visio (if there's any Open Source tool that understands Visio files, I want to hear about it). Ditto Inkscape. .TXT or .WIKI in Emacs or your favorite text editor.

And, similar, on saving the file, have my own hooks to translate into some other format.

I'll probably want to provide some canned, in a web page, wiki text editor. In fact, I probably want to discourage tesxt being written except in a standard wiki markup. (Although having more than one wiki markup has some attractions. E.g. because I crosspost between wki and this blog. At least I want restructured text, since I am in the habit of cross posting wiki pages and comp.arch on USEnet. RST is much more readable that standard mediawiki or twiki markup.)

And maybe even a canned, in a web page, drawing editor.

But, my motivation for WebDAV is that I haven't found a drawing editor that makes me happy. Why reinvent the wheel?

The main problem with existing drawing editors is that their drawings cannot be displayed inline in web pages. But when I realized I can set my own put-time hooks in my own WebDAV server that seems more doable.