Paradox and Consistency

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

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

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

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

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

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

[[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]]