From Newsgroup: comp.arch

On 11/5/25 2:00 AM, BGB wrote:

On 11/4/2025 3:44 PM, Terje Mathisen wrote:

MitchAlsup wrote:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

[snip]

Branch prediction is fun.

When I looked around online before, a lot of stuff about branch
prediction was talking about fairly large and convoluted schemes
for the branch predictors.

You might be interested in looking at the 6th Championship
Branch Prediction (2025): https://ieeetcca.org/2025/02/18/6th- championship-branch-prediction-cbp2025/

TAgged GEometric length predictors (TAGE) seem to the current
"hotness" for branch predictors. These record very long global
histories and fold them into shorter indexes with the number of
history bits used varying for different tables.

(Because the correlation is less strong, 3-bit counters are
generally used as well as a useful bit.)

But, then always at the end of it using 2-bit saturating counters:
  weakly taken, weakly not-taken, strongly taken, strongly not
taken.

But, in my fiddling, there was seemingly a simple but moderately
effective strategy:
  Keep a local history of taken/not-taken;
  XOR this with the low-order-bits of PC for the table index;
  Use a 5/6-bit finite-state-machine or similar.
    Can model repeating patterns up to ~ 4 bits.

Indexing a predictor by _local_ (i.e., per instruction address)
history adds a level of indirection; once one has the branch
(fetch) address one needs to index the local history and then
use that to index the predictor. The Alpha 21264 had a modest-
sized (by modern standards) local history predictor with a 1024-
entry table of ten history bits indexed by the Program Counter
and the ten bits were used to index a table of three-bit
counters. This was combined with a 12-bit global history
predictor with 2-bit counters (note: not gshare, i.e., xored
with the instruction address) and the same index was used for
the chooser.

I do not know if 5/6-bit state machines have been academically
examined for predictor entries. I suspect the extra storage is a
significant discouragement given one often wants to cover more
different correlations and branches.

TAGE has the advantage that the tags reduce branch aliases and
the variable history length (with history folding/compression)
allows using less storage (when a prediction only benefits from
a shorter history) and reduces training time.

(I am a little surprised that I have not read a suggestion to
use the alternate 2-bit encoding that retains the last branch
direction. This history might be useful for global history; the
next most recent direction (i.e., not the predicted direction)
of previous recent branches for a given global history might be
useful in indexing a global history predictor. This 2-bit
encoding seems to give slightly worse predictions than a
saturating counter but the benefit of "localized" global history
might compensate for this.)

Alloyed prediction ("Alloyed Branch History: Combining Global
and Local Branch History for Robust Performance", Zhijian Lu et
al., 2002) used a tiny amount of local history to index a
(mostly) global history predictor, hiding (much of) the latency
of looking up the local history by retrieving multiple entries
from the table and selecting the appropriate one with the local
history.

There was also a proposal ("Branch Transition Rate: A New Metric
for Improved Branch Classification Analysis", Michael Huangs et
al., 2000) to consider transition rate, noting that high
transition rate branches (which flip direction frequently) are
poorly predicted by averaging behavior. (Obviously, loop-like
branches have a high transition rate for one direction.) This is
a limited type of local history. If I understand correctly, your
state machine mechanism would capture the behavior of such
highly alternately branches.

Compressing the history into a pattern does mean losing
information (as does a counter), but I had thought such pattern
storage might be more efficient that storing local history. It
is also interesting that the Alpha 21264 local predictor used
dynamic pattern matching rather than a static transformation of
history to prediction (state machine)

I think longer local history prediction has become unpopular,
probably because nothing like TAGE was proposed to support
longer histories but also because the number of branches that
can be tracked with long histories is smaller.

Local history patterns may also be less common that statistical
correlation after one has extracted branches predicted well by
global history. (For small-bodied loops, a moderately long
global history provides substantial local history.)

Using a pattern/state machine may also make confidence
estimation less accurate. TAGE can use confidence of multiple
matches to form a prediction.

The use of confidence for making a prediction also makes it
impractical to store just a prediction nearby (to reduce
latency) and have the extra state more physically distant. For
per-address predictors, one could in theory use Icache
replacement to constrain predictor size, where an Icache miss
loads local predictions from an L2 local predictor. I think AMD
had limited local predictors associated with the Icache and had
previously stored some prediction information in L2 cache using
the fact that code is not modified (so parity could be used and
not ECC).

Daniel A. Jiménez did some research on using neural methods
(e.g., perceptrons) for branch prediction. The principle was
that traditional global history tables had exponential scaling
with history size (2 to the N table entries for N history bits)
while per-address perceptrons would scale linearly (for a fixed
number of branch addresses). TAGE (with its folding of long
histories and variable history) seems to have removed this as a
distinct benefit. General correlation with specific branches may
also be less predictive than correlation with path.
Nevertheless, the research was interesting and larger histories
did provide more accurate predictions.

Anyway, I agree that thinking about these things can be fun.

Where, the idea was that the state-machine in updated with the
current state and branch direction, giving the next state and
next predicted branch direction (for this state).

Could model slightly more complex patterns than the 2-bit
saturating counters, but it is sort of a partial mystery why
(for mainstream processors) more complex lookup schemes and 2
bit state, was preferable to a simpler lookup scheme and 5-bit
state.

Well, apart from the relative "dark arts" needed to cram 4-bit
patterns into a 5 bit FSM (is a bit easier if limiting the
patterns to 3 bits).

Then again, had before noted that the LLMs are seemingly also
not really able to figure out how to make a 5 bit FSM to model a
full set of 4 bit patterns.

Then again, I wouldn't expect it to be all that difficult of a
problem for someone that is "actually smart"; so presumably chip
designers could have done similar.

Well, unless maybe the argument is that 5 or 6 bits of storage
would cost more than 2 bits, but then presumably needing to have significantly larger tables (to compensate for the relative
predictive weakness of 2-bit state) would have costed more than
the cost of smaller tables of 6 bit state ?...

Say, for example, 2b:
 00_0 => 10_0  //Weakly not-taken, dir=0, goes strong not-taken
 00_1 => 01_0  //Weakly not-taken, dir=1, goes weakly taken
 01_0 => 00_1  //Weakly taken, dir=0, goes weakly not-taken
 01_1 => 11_1  //Weakly taken, dir=1, goes strongly taken
 10_0 => 10_0  //strongly not taken, dir=0
 10_1 => 00_0  //strongly not taken, dir=1 (goes weak)
 11_0 => 01_1  //strongly taken, dir=0
 11_1 => 11_1  //strongly taken, dir=1 (goes weak)

Can expand it to 3-bits, for 2-bit patterns
  As above, and 4-more alternating states
  And slightly different transition logic.
Say (abbreviated):
  000   weak, not taken
  001   weak, taken
  010   strong, not taken
  011   strong, taken
  100   weak, alternating, not-taken
  101   weak, alternating, taken
  110   strong, alternating, not-taken
  111   strong, alternating, taken
The alternating states just flip-flopping between taken and not
taken.
  The weak states can more between any of the 4.
  The strong states used if the pattern is reinforced.

Going up to 3 bit patterns is more of the same (add another bit,
doubling the number of states). Seemingly something goes nasty
when getting to 4 bit patterns though (and can't fit both weak
and strong states for longer patterns, so the 4b patterns
effectively only exist as weak states which partly overlap with
the weak states for the 3-bit patterns).

But, yeah, not going to type out state tables for these ones.

Not proven, but I suspect that an arbitrary 5 bit pattern within
a 6 bit state might be impossible. Although there would be
sufficient state-space for the looping 5-bit patterns, there may
not be sufficient state-space to distinguish whether to move
from a mismatched 4-bit pattern to a 3 or 5 bit pattern.
Whereas, at least with 4-bit, any mismatch of the 4-bit pattern
can always decay to a 3-bit pattern, etc. One needs to be able
to express decay both to shorter patterns and to longer
patterns, and I suspect at this point, the pattern breaks down
(but can't easily confirm; it is either this or the pattern
extends indefinitely, I don't know...).

Could almost have this sort of thing as a "brain teaser" puzzle
or something...

Then again, maybe other people would not find any particular
difficulty in these sorts of tasks.

Terje

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 11/18/25 10:16 AM, Anton Ertl wrote:
[snip]

How can register renaming be implemented on SPARC? As discussed
above, this can be done independently: Have 96 architectural registers
(plus the window pointer), and make 8 of them global registers, and
the rest 24 visible registers plus 4 windows of 16 registers, with the
usual switching. And then rename these 96 architectural registers.

Rather than having all the architectural registers be "visible"
in a single RAT structure, one could use a technique similar to
RAT checkpointing (used for reproducing state after a branch
misprediction; MIPS R10000 had a 4 entry "branch stack" that
included mapping table copies). The window shifts would adjust
which block specific RAT subtables provide mappings for and
blocks shifted out would behave like RAT checkpoints.

A variant in the opposite direction would be to treat only the 32
visible registers as architectural registers, avoiding large RAT
entries. The save instruction would emit store microinstructions for
the local and in registers, and then the renamer would rename the out registers to the in registers, and would assign 0 to the local and out registers (which would not occupy a physical register at first). This approach makes the most sense with a separate renamer as is now
common. The restore instruction would rename the in registers to the
out registers, and emit load microinstructions for the local and the
in registers.

Another possibility would be to use special register storage for
checkpoint values which only supports transfers to and from a
multiported entry. With the high wire overhead of multiported
register files, such storage can be substantially hidden under
the wires. (For in-order designs, Sun had the (academic-only?)
concept of 3D register files that used select lines to choose
which set of registers was being used. Aside from register
windows for an in-order core, this could be used for fine-
grained but not simultaneous multithreading.)

(I have not found the paper that suggested such checkpoint
registers — the intent as I recall was to reduce the storage
overhead for values which were likely dead but still within the
speculative window. The 3D register file paper has "Three-
Dimensional" in the title so is easy to find among my files: "A
Three Dimensional Register File For Superscalar Processors",
Marc Tremblay et al., 1995. I wish I had kept better notes about
the papers I have looked at.)

OoO tends to work fine with storing around calls and loading around
returns in architectures without register windows, because the storing
mostly consumes resources, but is not on the critical path, and
likewise for the loading (the loads tend to be ready earlier than the instructions on the critical path); and store-to-load forwarding
deals with the problem of a return shortly after a call.

I think lazy saving might be preferred over treating such as
ordinary stores. Also storing to a dedicated single-ported wide
and multibanked storage might be desirable. In some sense, a
register window is a single 256-byte register when referenced by
SAVE and RESTORE instructions (if I remember/understand
correctly), so tracking loads and stores by individual 8-byte
chunks seems less efficient. In addition such would not require
full address tagging. I have no clue whether it would be
worthwhile to specialize these cases for efficiency rather than
use more general resources (with higher utilization).

I would guess that for individual store-data operations, the
operation would also include information to free the register so
that it is not freed before the data is read but is potentially
freed before the data reaching the longer-term storage.

Since wide accesses are cheaper than multiple independent
accesses, there might be a preference to batch the stores. On
the other hand, if using the data cache for storage, separate
stores could be done opportunistically to exploit unused banks.

Given the predictability of demand for saved values, one might
be able to move the storage farther away, exploiting the
predictability (and pipeline latency) to hide the latency of
accessing the storage.

Even though high-performance SPARC is effectively dead, it is
interesting to think about such things.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 12/2/25 2:55 PM, MitchAlsup wrote:

Robert Finch <robfi680@gmail.com> posted:

Semi-unaligned memory tradeoff. If unaligned access is required, the
memory logic just increments the physical address by 64 bytes to fetch
the next cache line. The issue with this is it does not go backwards to
get the address fetched again from the TLB. Meaning no check is made for
protection or translation of the address.

You can determine is an access is misaligned "enough" to warrant two
trips down the pipe.
a) crosses cache width
b) crosses page boundary

Case b ALLWAYS needs 2 trips; so the mechanism HAS to be there.

While that might be true of all practical designs, I _think_
that with a virtually tagged cache even crossing a page boundary
might not be a problem.

(I also discovered a way of using overlaid skewed associativity
to support variable alignment of cache blocks, so one could have
64-byte cache blocks aligned at 32-byte boundaries. Within a
page (or contiguous physical address chunk) physical tagging
could be used for such "misaligned" blocks. This was intended
primarily for instruction caches where contiguous useful chunks
are more common, wide access is common, and the chunks may not
be within an ordinary aligned block. With such cache blocks,
crossing a block size alignment boundary would not require a
second tag check. Of course, that is a special case and assumes
a design that is unlikely to be used.)

A cache that recorded the way of the next cache block might be
able to avoid both TLB and tag checks. (One of the Alpha Icache
designs had a next block _predictor_ so such a next adjacent
block designator might not be so crazy that the proposer would
be sent to an asylum.)

With a direct-mapped cache, accessing two adjacent blocks in
parallel would be somewhat easier since one would not need way
prediction or determination to do the access.

I would also think that if two cache tags could be checked in
parallel (even if constrained to "paired" tags) one could do the
same with a TLB (a clustered TLB has multiple adjacent pages so
the constraint would be more about crossing a page-cluster
boundary, I think).

I *am* skeptical that supporting page-crossing (or even block-
crossing) accesses is important enough to justify a lot of
complexity and extra hardware, but it seems that such would not
be impossible even without general two-entry TLB probes.

If I understand correctly, for the data access itself, there is
no significant difference between unaligned at the SRAM array
level and unaligned at the cache block level. I.e., the issue is
the tags.

If one allows multiple accesses to exploit the bank/bandwidth
support of the cache provided for unaligned accesses, supporting
block-crossing and page crossing loads may not be unreasonable
(it seems to me). If one supports three loads per cycle, one may
already support three TLB look-ups; if two of the loads are in
the same page, then the third load could use two TLB-access
slots. For streaming accesses, the TLB entry might be cached
separately, so an end-of-page unaligned access might use the
separately cached TLB entry and only make one access to the
general TLB.

I recognize that there is a huge difference between physically
possible and practical or worthwhile, but 'never' and 'always'
seem to be trigger words for me, "forcing" me to find an
exception.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/6/26 10:54 AM, John Dallman wrote:

In article <10m12ue$2t2k5$1@dont-email.me>, paaronclayton@gmail.com (Paul Clayton) wrote:

Currently, assembly-level compatibility does not seem worthwhile.

Not now, no. There was one case where it was valuable: the assembler
source translator for 8080 to 8086. That plus the resemblance of early
MS-DOS to CP/M meant that CP/M software written in assembler could be got working on the early IBM PC and compatibles more rapidly than new
software could be developed in high-level languages. That was one of the factors in the runaway success of PC-compatible machines in the early
1980s.

I remember reading about the 8080 → 8086 assembly translator. I
did not know that CP/M and MS-DOS were similar enough to
facilitate porting, so that note was interesting to me.

Software is usually distributed as machine code binaries not as
assembly,

Or as source code...

I think source distribution, even of free/open-source (or
shrouded source or other source-available) software, was not the
common case. I am lazy enough to use Fedora Linux.

Would the Intel-64 have been assembly compatible with AMD64? I
would have guessed that not just encodings would have been
different. If one wants to maintain market friction, supporting
the same assembly seems counterproductive.

It would hardly have mattered. Very little assembler is written for
64-bit architectures.

Quite true, of course.

Cooperating with AMD to develop a more sane encoding while
supporting low overhead for old binaries would have been better
for customers (I think).

Intel didn't admit to themselves they needed to do 64-bit x86 until AMD64
was thrashing them in the market. Far too late for collaborative design
by then.

Yes, seeking peace the morning before the Little Big Horn would
not have been an effective strategy. Intel presumably thought
Itanium would be the only merchant 64-bit ISA that mattered (and
this would exclude AMD) and that the masses could use 32-bit
until less expensive Itanium processors were possible.

It is not clear if assembly programmers would use less efficient
abstractions (like locks) to handle concurrency in which case
a different memory model might not impact correctness.

You are thinking of doing application programming in assembler. That's
pretty much extinct these days. Use of assembler to implement locks or
other concurrency-control mechanisms in an OS or a language run-time
library is far more likely.

I've been doing low-level parts of application development for over 40
years. In 1983-86, I was working in assembler, or needed to have a very
close awareness of the assembler code being generated by a higher level language. In 1987-1990, I needed to be able to call assembler-level OS functions from C code. Since then, the only coding I've done in assembler
has been to generate hardware error conditions for testing error handlers. I've read and debugged lots of compiler-generated assembler to report compiler bugs, but that has become far less common over time.

I did think that assembly was mostly a niche skill nowadays.
Your little history is interesting.

I do not think ISA heterogeneity is necessarily problematic.

It requires the OS scheduler to be ISA-aware, and to never, /ever/ put a thread onto a core that can't run the relevant ISA. That will inevitably
make the scheduler more complicated and thus increase system overheads.

I think it depends on how much heterogeneity there is. If an
unimplemented instruction exception is generated, a thread could
be migrated to a core supporting that instruction. The OS might
even then mark that application as requiring that feature. Of
course, this also prevents using a less feature-ful core for
programs that only occasionally use a feature.

I agree that such would add complexity, but there is already
complexity for power saving with same ISA heterogeneity. NUMA-
awareness, cache sharing, and cache warmth also complicate
scheduling, so the question becomes how much extra complexity
does such introduce.

For SIMD width — apart from the broken, in my opinion, memory
copy implementations — a lot of programs probably do not use
SIMD. (That may be changing slowly as single thread performance
improvement has slowed. Maybe?) While I agree that SIMD width
was not a good basis for the heterogeneity, it was the feature
that differed for the Intel chip.

I suspect it might require more system-level organization (similar
to Apple).

Have you ever tried to optimise multi-threaded performance on a modern
Apple system with a mixture of Performance and Efficiency cores? I have,
and it's a lot harder than Apple give the impression it will be.

Apple make an assumption: that you will use their "Grand Central Dispatch" threading model. That requires multi-threaded code to be structured as a one-direction pipeline of work packets, with buffers between them, and
one thread/core per pipeline stage. That's a sensible model for some
kinds of work, but not all kinds. It also requires compiler extensions
which don't exist on other compilers. So you have to fall back to POSIX threads to get flexibility and portability.

Interesting.

If you're using POSIX threads, the scheduler seems to assign threads to
cores randomly. So your worker threads spend a lot of time on Efficiency cores. Those are in different clusters from the Performance cores, which means that communications between threads (via locks) are very slow.
Using Apple's performance category attributes for threads has no obvious effect on this.

While there would be some inevitable slowness in communication
between clusters (and power domains), I wonder if this was a
chosen simplification in Apple's case. It makes sense to not
bother optimizing a use case one does not expect to happen.

The way to fix this is to find out how many Performance cores there are
in a Performance cluster (which wasn't possible until macOS 12) and use
that many threads. Then you need to reach below the POSIX threading layer
to the underlying BSD thread layer. There, you can set an association
number on your threads, which tells the scheduler to try to run them in
the same cluster. Then you get stable and near-optimal performance. But finding out how to do this is fairly hard, and few seem to managed it.

Also interesting.

Even without ISA heterogeneity, optimal scheduling
seems to be a hard problem. Energy/power and delay/performance
preferences are not typically expressed. The abstraction of each
program owning the machine seems to discourage nice behavior (pun
intended).

Allowing processes to find out the details of other processes' resource
usage makes life very complicated, and introduces new opportunities for security bugs.

I still feel an attraction to a market-oriented resource
management such that threads could both minimize resource use
(that might be more beneficial to others) and get more than a
fair-share of resources that are important.

(I thought Intel marketed their initial 512-bit SIMD processors
as GPGPUs with x86 compatibility, so the idea of having a
general purpose ISA morphed into a GPU-like ISA had some
fascination after Cell.)

Larabee turned out to be a pretty bad GPU, and a pretty bad set of CPUs.

Yeah. I was commenting more on the spirit of the age or the
seductiveness of some ideas.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Used a new acronym today - HHI standing for hardware based hardware
interrupt. An interrupt thats runs a hardware process instead of an
interrupt subroutine.

The Qupls co-processor has an interrupt tied to the graphics command
queue being non-empty. It then triggers graphics operations instead of
running an ISR.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/16/2026 3:14 PM, Paul Clayton wrote:

On 11/5/25 2:00 AM, BGB wrote:

On 11/4/2025 3:44 PM, Terje Mathisen wrote:

MitchAlsup wrote:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

[snip]

Branch prediction is fun.

When I looked around online before, a lot of stuff about branch
prediction was talking about fairly large and convoluted schemes for
the branch predictors.

You might be interested in looking at the 6th Championship
Branch Prediction (2025): https://ieeetcca.org/2025/02/18/6th- championship-branch-prediction-cbp2025/

Quick look, didn't see much information about who entered or won...

TAgged GEometric length predictors (TAGE) seem to the current
"hotness" for branch predictors. These record very long global
histories and fold them into shorter indexes with the number of
history bits used varying for different tables.

(Because the correlation is less strong, 3-bit counters are
generally used as well as a useful bit.)

When I messed with it, increasing the strength of the saturating
counters was not effective.

But, increasing the ability of them to predict more complex patterns did
help.

But, then always at the end of it using 2-bit saturating counters:
   weakly taken, weakly not-taken, strongly taken, strongly not taken.

But, in my fiddling, there was seemingly a simple but moderately
effective strategy:
   Keep a local history of taken/not-taken;
   XOR this with the low-order-bits of PC for the table index;
   Use a 5/6-bit finite-state-machine or similar.
     Can model repeating patterns up to ~ 4 bits.

Indexing a predictor by _local_ (i.e., per instruction address)
history adds a level of indirection; once one has the branch
(fetch) address one needs to index the local history and then
use that to index the predictor. The Alpha 21264 had a modest-
sized (by modern standards) local history predictor with a 1024-
entry table of ten history bits indexed by the Program Counter
and the ten bits were used to index a table of three-bit
counters. This was combined with a 12-bit global history
predictor with 2-bit counters (note: not gshare, i.e., xored
with the instruction address) and the same index was used for
the chooser.

OK, seems I wrote it wrong:
I was using a global branch history.

But, either way, the history is XOR'ed with the relevant bits from PC to generate the index.

I do not know if 5/6-bit state machines have been academically
examined for predictor entries. I suspect the extra storage is a
significant discouragement given one often wants to cover more
different correlations and branches.

If the 5/6-bit FSM can fit more patterns than 3x 2-bit saturating
counters, it can be a win.


As noted, the 5/6 bit FSM can predict arbitrary 4 bit patterns.

With the PC XOR Hist, lookup, there were still quite a few patterns, and
not just contiguous 0s or 1s that the saturating counter would predict,
nor just all 0s, all 1s, or ...101010... that the 3-bit FSM could deal with.


But, a bigger history could mean less patterns and more contiguous bits
in the state.

TAGE has the advantage that the tags reduce branch aliases and
the variable history length (with history folding/compression)
allows using less storage (when a prediction only benefits from
a shorter history) and reduces training time.

In my case, was using 6-bit lookup mostly to fit into LUT6 based LUTRAM.

Going bigger than 6 bits here is a pain point for FPGAs, more so as
BRAM's don't support narrow lookups, so the next size up would likely be
2048x but then inefficiently using the BRAM (there isn't likely a
particularly good way to make use of 512x 18-bits).


Though, more efficient case here would likely be to use LUT5's (5-bit
index), or maybe MUXing LUT5's (for 128x 6b, maybe 512x 6b with 3-levels
of LUTs).


I guess, it is an open question if one did:
reg[4:0] predArray[511:0];
If the synthesis would figure out the most optimal pattern on its own,
vs needing to get more manual, with an array more like:
reg[95:0] predArray[31:0]; //fit to 5b index / 3b data.

With it padded up to 6-bits per entry to allow fitting it to the LUTRAM
1R1W pattern (densely packing to 80 bits would not fit the pattern).


But, yeah, if the size of the lookup were extended, it could make sense
to start hashing part of the history, say, maybe:

hhist[ 5: 0] = hist[5:0];
hhist[ 9: 6] = hist[9:6] ^ hist[13:10];
hhist[11:10] = hist[11:10] ^ hist[13:12] ^ hist[15:14];

Then, say:
index[11:0] = hhist[11:0] ^ { pc[12:2], pc[13] ^ pc[1] };

...

(I am a little surprised that I have not read a suggestion to
use the alternate 2-bit encoding that retains the last branch
direction. This history might be useful for global history; the
next most recent direction (i.e., not the predicted direction)
of previous recent branches for a given global history might be
useful in indexing a global history predictor. This 2-bit
encoding seems to give slightly worse predictions than a
saturating counter but the benefit of "localized" global history
might compensate for this.)

Alloyed prediction ("Alloyed Branch History: Combining Global
and Local Branch History for Robust Performance", Zhijian Lu et
al., 2002) used a tiny amount of local history to index a
(mostly) global history predictor, hiding (much of) the latency
of looking up the local history by retrieving multiple entries
from the table and selecting the appropriate one with the local
history.

There was also a proposal ("Branch Transition Rate: A New Metric
for Improved Branch Classification Analysis", Michael Huangs et
al., 2000) to consider transition rate, noting that high
transition rate branches (which flip direction frequently) are
poorly predicted by averaging behavior. (Obviously, loop-like
branches have a high transition rate for one direction.) This is
a limited type of local history. If I understand correctly, your
state machine mechanism would capture the behavior of such
highly alternately branches.

Compressing the history into a pattern does mean losing
information (as does a counter), but I had thought such pattern
storage might be more efficient that storing local history. It
is also interesting that the Alpha 21264 local predictor used
dynamic pattern matching rather than a static transformation of
history to prediction (state machine)

I think longer local history prediction has become unpopular,
probably because nothing like TAGE was proposed to support
longer histories but also because the number of branches that
can be tracked with long histories is smaller.

Local history patterns may also be less common that statistical
correlation after one has extracted branches predicted well by
global history. (For small-bodied loops, a moderately long
global history provides substantial local history.)

...

It seems what I wrote originally was inaccurate, I don't store a history per-target, merely it was recent taken/not-taken branches.

But, I no longer remember what I was thinking at the time, or why I had written local history rather than global history (unless I meant "local"
in terms of recency or something, I don't know).

Using a pattern/state machine may also make confidence
estimation less accurate. TAGE can use confidence of multiple
matches to form a prediction.

The use of confidence for making a prediction also makes it
impractical to store just a prediction nearby (to reduce
latency) and have the extra state more physically distant. For
per-address predictors, one could in theory use Icache
replacement to constrain predictor size, where an Icache miss
loads local predictions from an L2 local predictor. I think AMD
had limited local predictors associated with the Icache and had
previously stored some prediction information in L2 cache using
the fact that code is not modified (so parity could be used and
not ECC).

Daniel A. Jiménez did some research on using neural methods
(e.g., perceptrons) for branch prediction. The principle was
that traditional global history tables had exponential scaling
with history size (2 to the N table entries for N history bits)
while per-address perceptrons would scale linearly (for a fixed
number of branch addresses). TAGE (with its folding of long
histories and variable history) seems to have removed this as a
distinct benefit. General correlation with specific branches may
also be less predictive than correlation with path.
Nevertheless, the research was interesting and larger histories
did provide more accurate predictions.

Anyway, I agree that thinking about these things can be fun.

A lot of this seems a lot more complex though than what would be all
that practical on a Spartan or Artix class FPGA.


I was mostly using 5/6 bit state machines as they gave better results
than 2-bit saturating counters, and fit nicely within the constraints of
a "history XOR PC" lookup pattern.


Also initially, a while ago, it seemed that the patterns for these state machines were outside the reach of LLM AIs, but it seems the AIs are
quickly catching up at these sorts of mental puzzles.

Granted, I am mostly within the limits of cheap/free.


But, OTOH, paying a steep per-month fee so that "vibe coding" could take
my hobby from me isn't particularly compelling personally. But, even as
such, it does seem like if people can do so, my "existential merit" is weakening.

Even if as-is, apparently the people who try to do non-trivial projects
via "vibe coding" generally end up with some big mess of poorly written
code that falls on its face one the code gets big enough that the LLMs
can no longer reason about it.

Where, the idea was that the state-machine in updated with the current
state and branch direction, giving the next state and next predicted
branch direction (for this state).


Could model slightly more complex patterns than the 2-bit saturating
counters, but it is sort of a partial mystery why (for mainstream
processors) more complex lookup schemes and 2 bit state, was
preferable to a simpler lookup scheme and 5-bit state.

Well, apart from the relative "dark arts" needed to cram 4-bit
patterns into a 5 bit FSM (is a bit easier if limiting the patterns to
3 bits).



Then again, had before noted that the LLMs are seemingly also not
really able to figure out how to make a 5 bit FSM to model a full set
of 4 bit patterns.


Then again, I wouldn't expect it to be all that difficult of a problem
for someone that is "actually smart"; so presumably chip designers
could have done similar.

Well, unless maybe the argument is that 5 or 6 bits of storage would
cost more than 2 bits, but then presumably needing to have
significantly larger tables (to compensate for the relative predictive
weakness of 2-bit state) would have costed more than the cost of
smaller tables of 6 bit state ?...

Say, for example, 2b:
  00_0 => 10_0  //Weakly not-taken, dir=0, goes strong not-taken
  00_1 => 01_0  //Weakly not-taken, dir=1, goes weakly taken
  01_0 => 00_1  //Weakly taken, dir=0, goes weakly not-taken
  01_1 => 11_1  //Weakly taken, dir=1, goes strongly taken
  10_0 => 10_0  //strongly not taken, dir=0
  10_1 => 00_0  //strongly not taken, dir=1 (goes weak)
  11_0 => 01_1  //strongly taken, dir=0
  11_1 => 11_1  //strongly taken, dir=1 (goes weak)

Can expand it to 3-bits, for 2-bit patterns
   As above, and 4-more alternating states
   And slightly different transition logic.
Say (abbreviated):
   000   weak, not taken
   001   weak, taken
   010   strong, not taken
   011   strong, taken
   100   weak, alternating, not-taken
   101   weak, alternating, taken
   110   strong, alternating, not-taken
   111   strong, alternating, taken
The alternating states just flip-flopping between taken and not taken.
   The weak states can more between any of the 4.
   The strong states used if the pattern is reinforced.

Going up to 3 bit patterns is more of the same (add another bit,
doubling the number of states). Seemingly something goes nasty when
getting to 4 bit patterns though (and can't fit both weak and strong
states for longer patterns, so the 4b patterns effectively only exist
as weak states which partly overlap with the weak states for the 3-bit
patterns).

But, yeah, not going to type out state tables for these ones.


Not proven, but I suspect that an arbitrary 5 bit pattern within a 6
bit state might be impossible. Although there would be sufficient
state-space for the looping 5-bit patterns, there may not be
sufficient state-space to distinguish whether to move from a
mismatched 4-bit pattern to a 3 or 5 bit pattern. Whereas, at least
with 4-bit, any mismatch of the 4-bit pattern can always decay to a 3-
bit pattern, etc. One needs to be able to express decay both to
shorter patterns and to longer patterns, and I suspect at this point,
the pattern breaks down (but can't easily confirm; it is either this
or the pattern extends indefinitely, I don't know...).


Could almost have this sort of thing as a "brain teaser" puzzle or
something...

Then again, maybe other people would not find any particular
difficulty in these sorts of tasks.

Terje

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/9/2026 8:18 PM, Paul Clayton wrote:

On 2/9/26 2:33 PM, MitchAlsup wrote:

Paul Clayton <paaronclayton@gmail.com> posted:

On 2/5/26 2:02 PM, MitchAlsup wrote:

[snip]>>> MS wants you to buy Office every time you buy a new PC.

I thought MS wanted everyone to use Office365. It is harder to
force people to get a new computer, but a monthly fee will recur
automatically.

When I need a tool--I buy that tool--I never rent that tool.

Name one feature I would want from office365 that was not already
present in office from <say> 1998.

I do not know if MS can legally cancel your MS Office license, and I
doubt the few "software pirates" who continue to use an unsupported ("invalid") version would be worth MS' time and effort to prevent such people from using such software.

However, there seems to be a strong trend toward "you shall own nothing."

MS, then moves all the menu items to different pull downs and
makes it difficult to adjust to the new SW--and then it has the
Gaul to chew up valuable screen space with ever larger pull-
down bars.

Ah, but they are just beginning to include advertising. Imagine
every time one uses the mouse (to indicate to the computer that
the user's eyes are focused on a particular place) an
advertisement appears and follows the cursor movement. Even just
having menu entries that are advertisements would be kind of
annoying, but one would be able to get rid of those by leasing
the premium edition (until one needs to lease the platinum
edition, then the "who wants to remain a millionaire" edition).

Why would I or anyone want advertising in office ????????

Why would anyone want advertising in in a Windows Start Menu?

For Microsoft such provides a bit more revenue/profit as businesses seem willing to pay for such advertisements. Have you ever heard "You are not
the consumer; you are the product"?

I think I read that some streaming services have added
advertising to their (formerly) no-advertising subscriptions, so
the suggested lease term inflation is not completely
unthinkable.

Better at this point to just use LibreOffice or similar...

Well, and to not use Windows 11 ...


For now, my main PC still uses Windows 10, and at this point would
almost rather jump ship to Linux if need be, than go to Windows 11.

Like, MS has become hell bent on turning Windows 11 into a trash fire.

Is it any wonder users want the 1937 milling machine model ???

Have no fear; soon you may be merely leasing your computer.
Computers need to have the latest spyware so that advertisements
can be appropriately targeted and adblocking must be made
impossible.

I am the kind of guy that turns off "telemetry" and places advertisers
in /hosts file.

If all new computers are "leased" (where tampering with the
device — or not connecting it to the Internet such that it can
phone home — revokes "ownership" and not merely warranty and one
agrees to a minimum use [to ensure that enough ads are viewed]),
ordinary users (who cannot assemble devices from commodity
parts) would not have a choice. If governments enforce the
rights of corporations to protect their businesses by outlawing
sale of computer components to anyone who would work around the
cartel, owning a computer could become illegal. Governments have
an interest in having all domestic computers be both secure and
to facilitate domestic surveillance, so mandating features that
remove freedom and require an upgrade cycle (which is also good
for the economy☺) has some attraction.

I doubt people like you are a sufficient threat to profits that
such extreme measures will be used, but the world (and
particularly the U.S.) seems to be becoming somewhat dystopian.

This is getting kind of off-topic and is certainly not something I want
to think about.

Ironically, this sort of thing, and also locking down computers enough
that they only allow basic user programs and disallow "side loading"
etc, was an element in some of my sci-fi stories.

But, not exactly an optimistic point.

And, there was effectively an illicit black market for unconstrained
computers and computer parts (mostly salvaged). Where, a computer built
mostly from salvaged parts from old electronics would be worth more than
a new computer available though official channels (and within legal
limits in terms of OS and hardware specs).


Though, in such a world, owning an unconstrained computer would be seen
as both illegal and dangerous.

But, not all sci-fi needs to be utopic or optimistic (this itself seems
like a trap, both that people assume this as a default, or that people
can mistake overt dystopias as an ideal to strive for).

But, then if one includes "obvious bad" things (like a bunch of WWII
type stuff; mass euthanasia and so on), then almost invariably someone
thinks that one is endorsing it and gets offended about it.

Well, and sometimes one needs to be able to reference and depict bad
things in order to denounce them as such.

Granted, things are not so great when one is more prone to dealing with
"gray on gray morality" rather than a more clear cut "battle of good
versus evil" theme. Reality more tends towards the former, but society
prefers the latter, and choosing the latter more often leads one into a
trap (more so if one assumes that the protagonists' side is always
necessarily the "good" one).

Say, flip the perspective, and tell a story from the POV of the villain,
and almost invariably they become an anti-hero even if they continue
pretty much the exact same actions they would have taken if a villain
from the hero's POV (more so if they are humanized in any way, or their actions are given any sort of justification, even if said justification
is purely self-serving and egocentric).

Alas...


...


--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <10n2u02$270jc$5@dont-email.me>, paaronclayton@gmail.com (Paul Clayton) wrote:

I remember reading about the 8080 _ 8086 assembly translator. I
did not know that CP/M and MS-DOS were similar enough to
facilitate porting, so that note was interesting to me.

/Early/ MS-DOS. That used CPM-like File Control Blocks, and didn't have hierarchical directories. It didn't really support hard disks. The
CP/M-style APIs all carried on existing after MS-DOS 2.0 introduced a new
set of APIs that were more suitable for high-level languages, but they
weren't much used un new software.

Intel presumably thought Itanium would be the only merchant
64-bit ISA that mattered (and this would exclude AMD) and
that the masses could use 32-bit until less expensive Itanium
processors were possible.

Pretty much. Then the struggle to make Itanium run fast became the
overpowering concern, until they gave up and concentrated on x86-64,
claiming that Itanium would be back in a few years.

I don't think many people took that claim seriously. Some years later, an
Intel marketing man was quite shocked to hear that, and that the world
had simply been humouring them.

I agree that such would add complexity, but there is already
complexity for power saving with same ISA heterogeneity. NUMA-
awareness, cache sharing, and cache warmth also complicate
scheduling, so the question becomes how much extra complexity
does such introduce.

If the behaviour of Apple's OSes are any guide, complexity is avoided as
far as possible.

I still feel an attraction to a market-oriented resource
management such that threads could both minimize resource use
(that might be more beneficial to others) and get more than a
fair-share of resources that are important.

The difficulty there is that developers will have a very hard time
creating /measurable/ speed-ups that apply across a wide range of
different configurations. Companies will therefore be reluctant to put developer hours into it that could go into features that customers are
asking for.

John
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/19/2026 2:02 AM, John Dallman wrote:

In article <10n2u02$270jc$5@dont-email.me>, paaronclayton@gmail.com (Paul Clayton) wrote:

I remember reading about the 8080 _ 8086 assembly translator. I
did not know that CP/M and MS-DOS were similar enough to
facilitate porting, so that note was interesting to me.

/Early/ MS-DOS. That used CPM-like File Control Blocks, and didn't have hierarchical directories. It didn't really support hard disks. The
CP/M-style APIs all carried on existing after MS-DOS 2.0 introduced a new
set of APIs that were more suitable for high-level languages, but they weren't much used un new software.

My own limited experience with MS-DOS programming mostly showed them
using integer file-handles an a vaguely Unix-like interface for file IO
at the "int 21h" level.

Which is, ironically, in conflict with the "FILE *" interface used by
C's stdio API.

But, I do remember a mechanism involving shared FCB structs existing on MS-DOS, but AFAIK it was mostly unused in favor of the use of integer
handles.

But, it has been a very long time since I have messed around much with
DOS (well, and in my childhood it was mostly 6.20 and 6.22 and similar,
or 7.00 if using the version that came with Win95).


Though, I have a vague memory of sometimes setting up chimeric versions
of DOS, mostly intentionally installing 7.00 on top of 6.22 because
there were a lot of additional programs that existed within a 6.22
install that were absent 7.00.

IIRC, in 6.22 it had QBASIC and EDIT was a thin wrapper over QBASIC,
whereas 7.00 had dropped QBASIC and made EDIT self-contained, or
something to this effect. So, in this sense, it made sense to install
6.22 first and then 7.00 on top of it to get a DOS install that still
had things like QBASIC and similar.


Though, this was before switching over to dual-booting Slackware and
NT4, and then running Cygwin on NT4 (was my general setup in
middle-school before switching to Win2K in high-school). By that point,
had mostly abandoned QBASIC (but, QBASIC was used some in elementary
school).

Well, apart from some vague (unconfirmed) memories of being exposed to
Pascal via the "Mac Programmer's Workbench" thing at one point and being totally lost (was very confused, used a CLI but the CLI commands didn't
make sense). Memory was like a Macintosh II with an external HDD and magneto-optical drive (*). Seemingly, the hardware exists and matches my memory, so presumably I saw it, but the memories also, doesn't make much sense.

*: Like, it use disks that were sort of like giant versions of the 3.5" floppies holding a something resembling a rainbow-colored CD-ROM (disk protected by the sliding door). Or, say, if one took a 3.5" floppy and
scaled it up to be a little larger than a 5.25" floppy (and if it held something resembling a rainbow-patterned CD-ROM).

These things were a novelty as basically none of the other computers
used them (everything else using normal floppies or CD-ROMs). Like, some
sort of weird alien tech.


Like, someone brought it in and had me try to use it (at the elementary school), and I didn't get it (like, it was confusing, and/or I was too
stupid to use it at the time).

Well, nothing like this ever happened again, I guess I had kinda blew it pretty hard at the time. The person took the computer with them and
left. I am not sure why they came by (was managed by a guy who wasn't
one of the usual teachers).


Pretty much everything else ran DOS, apart from some Apple II/E and an
Apple II/GS and similar (where the II/GS was kinda like the Mac, but
with no MPW). The II/E's could also do BASIC, or one could boot up games
like "Oregon Trail" and similar.

Or, sorta timeline:
Early years: Mostly played NES and watched TV.
Like, mostly Super Mario Bros and similar.
Well, and TV shows like "Captain N" and "Super Mario Super Show".
Lots of NES related stuff going on in this era.
Started elementary school:
Distrurbing experience of being around other people;
And like, none of them could read or similar (*1);
Teacher was surprised, went and got librarian, ...
Started messing around with Apple II/e's;
Some BASIC on the II/e.
Encounter with the guy with the Mac II;
PCs were around, typically with 5.25" floppy drives;
TV shows included things like the Sonic the Hedgehog cartoons.
Also ReBoot and similar.
Well, and "Star Trek: TNG".
Parents got a PC: Had Win 3.11 and a CD-ROM drive.
Mostly played games like Wolfenstein 3D and similar.
QBASIC era started;
Got my own PC;
Started writing some stuff in real-mode ASM;
Started moving from QBASIC to C;
Windows 95 appeared;
Moved (~ end of Elementary School era, following 6th grade);
Tried using Win95, but it sucked.
Jumped to NT4;
Started Middle School.
TV Shows in this era: "Star Trek: Voyager" and "Deep Space Nine".
High School:
Jumped to Windows 2000.
"Star Trek: Enterprise" (but... it sucked...).
...

*1: Was likely unexpected that I would make an issue about no one being
able to read, but I think at the time, I was not particularly impressed
by being shown cards with letters and similar, so...

I don't remember my very early years though (my span of memory seemingly starting in the NES era).


But, alas, my life since then was basically a failure...

I guess back then, maybe people didn't realize it yet.

Well, starting in middle school, stuff sucked a lot more. Just had to
sit around classes and basically say nothing to draw undue attention,
which sucked (was nicer when people just let me go off and mess with
computers and similar). Still never really did much schoolwork though,
just did tests when they came along (though, this strategy was an epic
fail for college level calculus classes though... I just sorta figured I
was too stupid for this stuff...).

...

Intel presumably thought Itanium would be the only merchant
64-bit ISA that mattered (and this would exclude AMD) and
that the masses could use 32-bit until less expensive Itanium
processors were possible.

Pretty much. Then the struggle to make Itanium run fast became the overpowering concern, until they gave up and concentrated on x86-64,
claiming that Itanium would be back in a few years.

I don't think many people took that claim seriously. Some years later, an Intel marketing man was quite shocked to hear that, and that the world
had simply been humouring them.

In a way, it showed that they screwed up the design pretty hard that
x86-64 ended up being the faster and more efficient option...

I guess one question is if they had any other particular drawbacks other
than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;
...


I guess it is more of an open question of what would have happened, say,
if Intel had gone for an ISA design more like ARM64 or RISC-V or something.

These don't seem like they would have been too out-there, but then
again, at the time there were also some of the WTF design choices that
existed in MIPS and Alpha, so no guarantee it wouldn't have been screwed up.


Well, or something like PowerPC, but then again, IBM still had
difficulty keeping PPC competitive, so dunno. Then again, I think IBM's
PPC issues were more related to trying to keep up in the chip fab race
that was still going strong at the time, rather than an ISA design issue.

I agree that such would add complexity, but there is already
complexity for power saving with same ISA heterogeneity. NUMA-
awareness, cache sharing, and cache warmth also complicate
scheduling, so the question becomes how much extra complexity
does such introduce.

If the behaviour of Apple's OSes are any guide, complexity is avoided as
far as possible.

Unnecessary complexity is best avoided, as it often comes back to bite
later.

I still feel an attraction to a market-oriented resource
management such that threads could both minimize resource use
(that might be more beneficial to others) and get more than a
fair-share of resources that are important.

The difficulty there is that developers will have a very hard time
creating /measurable/ speed-ups that apply across a wide range of
different configurations. Companies will therefore be reluctant to put developer hours into it that could go into features that customers are
asking for.

John

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

According to BGB <cr88192@gmail.com>:

/Early/ MS-DOS. That used CPM-like File Control Blocks, and didn't have
hierarchical directories. ...

My own limited experience with MS-DOS programming mostly showed them
using integer file-handles an a vaguely Unix-like interface for file IO
at the "int 21h" level.

Yeah, Mark Zbikowski added them along with the tree structred file system in DOS 2.0.
He was at Yale when I was, using a Unix 7th edition system I was supporting.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/19/2026 1:59 PM, John Levine wrote:

According to BGB <cr88192@gmail.com>:

/Early/ MS-DOS. That used CPM-like File Control Blocks, and didn't have
hierarchical directories. ...

My own limited experience with MS-DOS programming mostly showed them
using integer file-handles an a vaguely Unix-like interface for file IO
at the "int 21h" level.

Yeah, Mark Zbikowski added them along with the tree structred file system in DOS 2.0.
He was at Yale when I was, using a Unix 7th edition system I was supporting.

Looks it up...


Yeah, my case, I didn't exist yet when the MS-DOS 2.x line came out...

Did exist for the 3.x line though.
I don't remember much from those years though.


Some fragmentary memories implied that (in that era) had mostly been
watching shows like Care Bears and similar (but, looking at it at a
later age, found it mostly unwatchable). I think also shows like Smurfs
and Ninja Turtles and similar, etc.

Like, at some point, memory breaking down into sort of an amorphous mass
of things from TV shows all just sort of got mashed together. Not much
stable memory of things other than fragments of TV shows and such.


Not sure what the experience is like for most people though.


--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

My own limited experience with MS-DOS programming mostly showed
them using integer file-handles an a vaguely Unix-like interface
for file IO at the "int 21h" level.

Which is, ironically, in conflict with the "FILE *" interface used
by C's stdio API.

However, it's entirely concordant with Unix's lower-level file
descriptors, as used in the read() and write() calls.

<https://en.wikipedia.org/wiki/File_descriptor> <https://en.wikipedia.org/wiki/Read_(system_call)>

The FILE* interface is normally implemented on top of the lower-level
calls, with a buffer in the process' address space, managed by the C
run-time library. The file descriptor is normally a member of the FILE structure.

MS-DOS is not a great design, but it isn't crazy either.

Well, apart from some vague (unconfirmed) memories of being exposed
to Pascal via the "Mac Programmer's Workbench" thing at one point
and being totally lost (was very confused, used a CLI but the CLI
commands didn't make sense).

I used it very briefly. It was a very weird CLI, seemingly designed by
someone opposed to the basic idea of a CLI.

In a way, it showed that they screwed up the design pretty hard
that x86-64 ended up being the faster and more efficient option...

They did. They really did.

I guess one question is if they had any other particular drawbacks
other than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;

Those huge register files had a lot to do with the low code density. They
had two much bigger problems, though.

They'd correctly understood that the low speed of affordable dynamic RAM
as compared to CPUs running at hundreds of MHz was the biggest barrier to making code run fast. Their solution was have the compiler schedule loads
well in advance. They assumed, without evidence, that a compiler with
plenty of time to think could schedule loads better than hardware doing
it dynamically. It's an appealing idea, but it's wrong.

It might be possible to do that effectively in a single-core,
single-thread, single-task system that isn't taking many (if any)
interrupts. In a multi-core system, running a complex operating system,
several multi-threaded applications, and taking frequent interrupts and
context switches, it is _not possible_. There is no knowledge of any of
the interrupts, context switches or other applications at compile time,
so the compiler has no idea what is in cache and what isn't. I don't
understand why HP and Intel didn't realise this. It took me years, but I
am no CPU designer.

Speculative execution addresses that problem quite effectively. We don't
have a better way, almost thirty years after Itanium design decisions
were taken. They didn't want to do speculative execution, and they close
an instruction format and register set that made adding it later hard. If
it was ever tried, nothing was released that had it AFAIK.

The other problem was that they had three (or six, or twelve) in-order pipelines running in parallel. That meant the compilers had to provide
enough ILP to keep those pipelines fed, or they'd just eat cache capacity
and memory bandwidth executing no-ops ... in a very bulky instruction set.
They didn't have a general way to extract enough ILP. Nobody does, even
now. They just assumed that with an army of developers they'd find enough heuristics to make it work well enough. They didn't.

There was also an architectural misfeature with floating-point advance
loads that could make them disappear entirely if there was a call
instruction between an advance-load instruction and the corresponding check-load instruction. That cost me a couple of weeks working out and reporting the bug, which was unfixable. The only work-around was to
re-issue all outstanding all floating-point advance-load instruction
after each call returned. The effective code density went down further,
and there were lots of extra read instructions issued.

I guess it is more of an open question of what would have happened,
say, if Intel had gone for an ISA design more like ARM64 or RISC-V
or something.

ARM64 seems to me to be the product of a lot more experience with speculatively-executing processors than was available in 1998. RISC-V has
not demonstrated really high performance yet, and it's been around long
enough that I'm starting to doubt it ever will.

Well, or something like PowerPC, but then again, IBM still had
difficulty keeping PPC competitive, so dunno. Then again, I think
IBM's PPC issues were more related to trying to keep up in the chip
fab race that was still going strong at the time, rather than an
ISA design issue.

I think that was fabs, rather than architecture. While I was providing libraries for PowerPC (strictly, POWER4, POWER5 and POWER6, one after
another) it always had rather decent performance for its clockspeed and process.

John
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


jgd@cix.co.uk (John Dallman) posted:

They did. They really did.

I guess one question is if they had any other particular drawbacks
other than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;

Those huge register files had a lot to do with the low code density. They
had two much bigger problems, though.

They'd correctly understood that the low speed of affordable dynamic RAM
as compared to CPUs running at hundreds of MHz was the biggest barrier to making code run fast. Their solution was have the compiler schedule loads well in advance. They assumed, without evidence, that a compiler with
plenty of time to think could schedule loads better than hardware doing
it dynamically. It's an appealing idea,

possibly

but it's wrong.

at best we can say that their version failed to provide performance.
The future may well prove it flat-out wrong at some point.

It might be possible to do that effectively in a single-core,
single-thread, single-task system that isn't taking many (if any)
interrupts. In a multi-core system, running a complex operating system, several multi-threaded applications, and taking frequent interrupts and context switches, it is _not possible_. There is no knowledge of any of
the interrupts, context switches or other applications at compile time,
so the compiler has no idea what is in cache and what isn't. I don't understand why HP and Intel didn't realise this. It took me years, but I
am no CPU designer.

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out. Now, 30 years later
the compilers are still in the position of having made LITTLE progress.

I suspect a big part of the problem was tension between Intel and HP
were the only political solution was allowing the architects from both
sides to "dump in" their favorite ideas. A recipe for disaster.

Speculative execution addresses that problem quite effectively. We don't
have a better way, almost thirty years after Itanium design decisions
were taken. They didn't want to do speculative execution, and they close
an instruction format and register set that made adding it later hard. If
it was ever tried, nothing was released that had it AFAIK.

The other problem was that they had three (or six, or twelve) in-order pipelines running in parallel. That meant the compilers had to provide
enough ILP to keep those pipelines fed, or they'd just eat cache capacity
and memory bandwidth executing no-ops ... in a very bulky instruction set. They didn't have a general way to extract enough ILP. Nobody does,

Reservation stations* provide such--but they do not use a multiplicity of
in order pipelines.

(*) and similar.

even
now. They just assumed that with an army of developers they'd find enough heuristics to make it work well enough. They didn't.

There was also an architectural misfeature with floating-point advance
loads that could make them disappear entirely if there was a call
instruction between an advance-load instruction and the corresponding check-load instruction. That cost me a couple of weeks working out and reporting the bug, which was unfixable. The only work-around was to
re-issue all outstanding all floating-point advance-load instruction
after each call returned. The effective code density went down further,
and there were lots of extra read instructions issued.

LoL, I guess I am surprised that the same could not happen at interrupt
or exception....

I guess it is more of an open question of what would have happened,
say, if Intel had gone for an ISA design more like ARM64 or RISC-V
or something.

ARM64 seems to me to be the product of a lot more experience with speculatively-executing processors than was available in 1998. RISC-V has
not demonstrated really high performance yet, and it's been around long enough that I'm starting to doubt it ever will.

In my humble opinion, there is a lot less wrong with ARM than RISC-V

Well, or something like PowerPC, but then again, IBM still had
difficulty keeping PPC competitive, so dunno. Then again, I think
IBM's PPC issues were more related to trying to keep up in the chip
fab race that was still going strong at the time, rather than an
ISA design issue.

I think that was fabs, rather than architecture.

I suspect it was the cash-flow the product produced that limited
"development" ... Whereas x86 and ARM have the kind of cash flow
that allows/supports whatever the designers can invent that adds
performance.

While I was providing libraries for PowerPC (strictly, POWER4, POWER5 and POWER6, one after another) it always had rather decent performance for its clockspeed and process.

John

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Now, 30 years later the compilers are still in the position of having
made LITTLE progress.

And, to be honest, compiler people had been working on similar problems
for 30 years already, so most compiler people aren't surprised that 30
more made no significant difference.

I suspect a big part of the problem was tension between Intel and HP
were the only political solution was allowing the architects from both
sides to "dump in" their favorite ideas. A recipe for disaster.

The odd thing is that these were hardware companies betting on "someone
else" solving their problem, yet if compiler people truly had managed to
solve those problems, then other hardware companies could have taken
advantage just as well.

So from a commercial strategy it made very little sense.

To me the main question is whether they were truly confused and just got
lucky (lucky because they still managed to sell their idea enough that
most RISC companies folded), or whether they truly understood that the
actual technical success of the architecture didn't matter and that it
was just a clever way to kill the RISC architectures.


=== Stefan
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

BGB wrote:

On 2/19/2026 1:59 PM, John Levine wrote:

According to BGB  <cr88192@gmail.com>:

/Early/ MS-DOS. That used CPM-like File Control Blocks, and didn't have >>>> hierarchical directories. ...

My own limited experience with MS-DOS programming mostly showed them
using integer file-handles an a vaguely Unix-like interface for file IO
at the "int 21h" level.

Yeah, Mark Zbikowski added them along with the tree structred file
system in DOS 2.0.
He was at Yale when I was, using a Unix 7th edition system I was
supporting.

Looks it up...

Yeah, my case, I didn't exist yet when the MS-DOS 2.x line came out...

Did exist for the 3.x line though.
I don't remember much from those years though.

Some fragmentary memories implied that (in that era) had mostly been watching shows like Care Bears and similar (but, looking at it at a
later age, found it mostly unwatchable). I think also shows like Smurfs
and Ninja Turtles and similar, etc.

Like, at some point, memory breaking down into sort of an amorphous mass
of things from TV shows all just sort of got mashed together. Not much > stable memory of things other than fragments of TV shows and such.

Not sure what the experience is like for most people though.

My memory from before the age of 4 is extremely spotty, just a couple of situations that made a lasting impact.
By the time MSDOS 2.0 came out I had already handed in my MSEE thesis. :-) Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/19/2026 5:10 PM, John Dallman wrote:

My own limited experience with MS-DOS programming mostly showed
them using integer file-handles an a vaguely Unix-like interface
for file IO at the "int 21h" level.

Which is, ironically, in conflict with the "FILE *" interface used
by C's stdio API.

However, it's entirely concordant with Unix's lower-level file
descriptors, as used in the read() and write() calls.

<https://en.wikipedia.org/wiki/File_descriptor> <https://en.wikipedia.org/wiki/Read_(system_call)>

The FILE* interface is normally implemented on top of the lower-level
calls, with a buffer in the process' address space, managed by the C
run-time library. The file descriptor is normally a member of the FILE structure.

MS-DOS is not a great design, but it isn't crazy either.

Yeah.

Well, apart from some vague (unconfirmed) memories of being exposed
to Pascal via the "Mac Programmer's Workbench" thing at one point
and being totally lost (was very confused, used a CLI but the CLI
commands didn't make sense).

I used it very briefly. It was a very weird CLI, seemingly designed by someone opposed to the basic idea of a CLI.

My vague memories was that its commands were just sort of straight up paradoxical. I don't remember much about them now though, other than
being confused trying to look at them (or getting anything to happen).


But, yeah, at my level of mental development at the time, whole
experience was confusing. Also it using external drives (sorta like on
the Apple II) but connected up with what looked like printer cables.

But, I don't really know exactly why the guy with the computer showed
up, or why he left, but he didn't seem pleased in any case.


Exact timeline is fuzzy, but I do remember enough familiarity with
MS-DOS to recognize they were almost completely different.

And, unlike the Apple II/e, which had essentially used BASIC.


But, either way, the experience (of MPW weirdness) was not something I
would have been ready for at that stage of development.

Well, and apparently a detail I missed in all of this, being that one
didn't just do a SHIFT+RETURN, but it was apparently necessary to select
the text for the command one wanted to run (with the mouse) before
hitting SHIFT+RETURN (or, hitting the keys without selecting something
first does nothing). Could be related to my difficulties/bewilderment at
the time (compared with DOS, which was more like "type command and hit ENTER").

Somehow I didn't remember anything about the "select command first"
part. More seeing it like "click on the command window and do keyboard shortcuts" and then having it not work.


But, I guess, some memories of mine, namely the thing of needing to do a ritual of dragging the drive to the trash-can and then also push a
button on the front of the drive, is reasonably correct for those drives.

Well, vs the 3.5" drive: Drag to trash, it ejects itself.

Or, DOS/Windows/etc, wait until drive stops, press button to eject disk.
Was very important in this case though to drag the drive to the trash
and then wait for the light on the drive to go off, then press the eject button (and with a good solid press, the disk ejects).

Also, it using a black-and-white monitor in an era where most others
around were color (though with a typically lower screen resolution).



Does seem like a sort of weird almost surreal memory.

Does imply that my younger self was notable, and not seen as just some otherwise worthless nerd.

Even if I totally failed at the tasks the guy had wanted from me.

So, I was confused, and the guy left in frustration.

In a way, it showed that they screwed up the design pretty hard
that x86-64 ended up being the faster and more efficient option...

They did. They really did.

Yeah.

I guess one question is if they had any other particular drawbacks
other than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;

Those huge register files had a lot to do with the low code density. They
had two much bigger problems, though.

They'd correctly understood that the low speed of affordable dynamic RAM
as compared to CPUs running at hundreds of MHz was the biggest barrier to making code run fast. Their solution was have the compiler schedule loads well in advance. They assumed, without evidence, that a compiler with
plenty of time to think could schedule loads better than hardware doing
it dynamically. It's an appealing idea, but it's wrong.

My CPU core doesn't do speculative prefetch either, but this seems more
like a "big OoO CPU" feature.

There is a sort of form of very limited/naive prefetch, where if it
guesses that one line of a like pair is likely to be followed by an
access to the following line in the pair (via heuristics), it will
prefetch the following line. This can help with things like linear
memory walks.


Could be better if there was a good/reliable way to detect linear walks.

Say, ideal case would be that in linear walk scenarios, most of the
memory fetches for the walk are via prefetches (while limiting the
number of hard misses).

For the L1 I$, one can assume linear walking by default.

Though, arguably the effectiveness of a prefetch is reduced in cases
where the hard-miss is likely to happen before the result of the
prefetch arrives (even if it is an L2 hit), but does maybe give the L2
cache a few cycles of "heads up" in the case of an L2 miss.


In my case, as noted, I ended up using 64 registers, but can note:
32 is near-optimal for generic code;
Works well for 32-bit instruction words;
64 deals better with high-pressure scenarios;
Is a little tight for 32-bit instruction words;
128 is likely invariably overkill
Not particularly viable with 32-bit instruction words.


Using register-paired types does result in "spikes" in register
pressure, and is a strong case where supporting 64 registers makes sense
(eg, so code generation doesn't get "owned"/"pwnt" when dealing with
int128 or paired-128-bit-SIMD).

Though, in the case of paired 128-bit ops, the even-registers-only rule
does have a side benefit of allowing for use of 5-bit register fields
while accessing all 64 registers (though still leaves a pain point when accessing one of the 64-bit halves of the pair, say if it happens to be
on the "wrong side" in the case of an ISA like RISC-V).


For 128 predicate registers, this part doesn't make as much sense:
Typically, 1 predicate bit is sufficient;
When exploring schemes for more advanced predication (Eg, 2 or 7/8
predicate registers), they didn't really even hit break-even.

Even if going for an IA64 like approach, probably made more sense to
have gone with an 8-register config, say:
P0: Hard-wired to 1/True
P1..P7: Dynamic Predicates


But, as noted, it was uncommon to find scenarios where having more than
a single predicate bit offered enough of an advantage over 1 predicated
bit to make it worthwhile, so the single-bit scheme seemed to remain the
most viable (with some more complex scenarios instead using GPRs for
boolean logic tasks, even if using a GPR for boolean logic tasks is
arguably wasteful).

For XG3, had ended up with a scenario where directing Boolean operations
to X0/RO was understood as updating the predicate bit:
SLT, SGE, SEQ, SNE: Rd=X0, Sets/Clears SR.T
AND/OR: Rd=X0, Also modifies SR.T (understood as a Boolean op).
Contrast (Rd=X0):
ADD/ADDI: NOP
LHU/LWU: Reserved for Mode-Hops (XG3 supported) / NOP (unsupported).
LHU: Jumps to RV64GC Mode (behaves like a JALR with Rd=X0)
LWU: Jumps to XG3 Mode (behaves like a JALR with Rd=X0)
Both being fall-through if XG3 is not supported.
If it doesn't branch, it means only RISC-V ops are supported.


Currently, the detection features are not used, as they only really make
sense in a mixed-mode binary that could potentially be used on a plain
RISC-V target.

But, in other contexts, the typical pattern is to use pointer tagging,
where:
(0)=0: Jump to an address within the same mode, (63:48) ignored
(1)=1: Jump with possible mode change, (63:48)=mode

One other special feature is that the mode bits also encode a tag, which
can be used to mark a pointer with the current process (with a value
assigned by an RNG), with the LSB also being required to be set, if Rs1==X1.

This can be used to add resistance against stack-stomping via buffer overflows, but is potentially risky with RISC-V:
AUIPC X1, AddrHi
JALR X0, AddrLo(X1)
Can nuke the process, when officially it is allowed (vs forcing the use
of a different register to encode a long branch).

Where, for other contexts, AUIPC would necessarily need to produce an
untagged address.

It might be possible to do that effectively in a single-core,
single-thread, single-task system that isn't taking many (if any)
interrupts. In a multi-core system, running a complex operating system, several multi-threaded applications, and taking frequent interrupts and context switches, it is _not possible_. There is no knowledge of any of
the interrupts, context switches or other applications at compile time,
so the compiler has no idea what is in cache and what isn't. I don't understand why HP and Intel didn't realise this. It took me years, but I
am no CPU designer.

No idea there, but either way, seems like a difficult problem.

Speculative execution addresses that problem quite effectively. We don't
have a better way, almost thirty years after Itanium design decisions
were taken. They didn't want to do speculative execution, and they close
an instruction format and register set that made adding it later hard. If
it was ever tried, nothing was released that had it AFAIK.

The other problem was that they had three (or six, or twelve) in-order pipelines running in parallel. That meant the compilers had to provide
enough ILP to keep those pipelines fed, or they'd just eat cache capacity
and memory bandwidth executing no-ops ... in a very bulky instruction set. They didn't have a general way to extract enough ILP. Nobody does, even
now. They just assumed that with an army of developers they'd find enough heuristics to make it work well enough. They didn't.

Yeah...

In my case, there is only 1 pipeline per core for now.
But ISA is still mostly RISC-like.


Not so much the 128-bits with 3-instructions thing, and then needing to
NOP pad if one can't find 3 useful instructions which fit into the pipeline.

My compiler would probably also be pretty awful if trying to target IA64.


Though did get around to re-adding a repurposed version of the WEXifier
for XG3 and RV, though its purpose was a little different in that these
ISA's have no way to flag for parallel execution, so the purpose is more
to shuffle instructions around to try to reduce register-RAW
dependencies and to help out the in-order superscalar stuff.

There was also an architectural misfeature with floating-point advance
loads that could make them disappear entirely if there was a call
instruction between an advance-load instruction and the corresponding check-load instruction. That cost me a couple of weeks working out and reporting the bug, which was unfixable. The only work-around was to
re-issue all outstanding all floating-point advance-load instruction
after each call returned. The effective code density went down further,
and there were lots of extra read instructions issued.

I guess it is more of an open question of what would have happened,
say, if Intel had gone for an ISA design more like ARM64 or RISC-V
or something.

ARM64 seems to me to be the product of a lot more experience with speculatively-executing processors than was available in 1998. RISC-V has
not demonstrated really high performance yet, and it's been around long enough that I'm starting to doubt it ever will.

There seem to be some questionable design choices here, and also a lot
of foot dragging for things that could help.


They also seem to be relatively focused on the assumption of CPUs having low-latency ALU and Memory-Load ops, which seems like a dangerous
assumption to make.


Like, how about one not try to bake in assumptions about 1-cycle ALU and 2-cycle Load being practical?...

Vs, say, 2-cycle ALU ops and 3-cycle Loads; with an ideal of putting 5 instructions between an instruction that generates a result and the instruction that consumes the result as this is more likely to work with in-order superscalar.


But, then one runs into the issue that if a basic operation then
requires a multi-op sequence, the implied latency goes up considerably
(say, could call this "soft latency", or SL).

So, for example, it means that, say:
2-instruction sign extension:
RV working assumption: 2 cycles
Hard latency (2c ALU): 4 cycles
Soft latency: 12 cycles.
For a 3-op sequence, the effective soft-latency goes up to 18, ...

And, in cases where the soft-latency significantly exceeds the total
length of the loop body, it is no longer viable to schedule the loop efficiently.

So, in this case, an indexed-load instruction has an effective 9c SL,
whereas SLLI+ADD+LD has a 21 cycle SL.


where, in this case, the goal of something like the WEXifier is to
minimize this soft-latency cost (in cases where a dependency is seen,
any remaining soft-latency is counted as penalty).

But, then again, maybe the concept of this sort of "soft latency" seems
a bit alien.


Granted, not sure how this maps over to OoO, but had noted that even
with modern CPUs, there still seems to be benefit from assuming a sort
of implicit high latency for instructions over assuming a lower latency.

Well, or something like PowerPC, but then again, IBM still had
difficulty keeping PPC competitive, so dunno. Then again, I think
IBM's PPC issues were more related to trying to keep up in the chip
fab race that was still going strong at the time, rather than an
ISA design issue.

I think that was fabs, rather than architecture. While I was providing libraries for PowerPC (strictly, POWER4, POWER5 and POWER6, one after another) it always had rather decent performance for its clockspeed and process.

OK.

I guess it is a question here of what if IBM had outsourced their fab
stuff earlier.

Though, there is still the potential downside of licensing based
production (say, if they went for something more like in the ARM model),
which is possibly worse than the argued threat of vendor-based market fragmentation (the usual counter-argument against RISc-V, *1).

*1: Where people argue that if each vendor can do a CPU with their own
custom ISA variants and without needing to license or get approval from
a central authority, that invariably everything would decay into an
incoherent mess where there is no binary compatibility between
processors from different vendors (usual implication being that people
are then better off staying within the ARM ecosystem to avoid RV's lawlessness).

John

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


BGB <cr88192@gmail.com> posted:

On 2/19/2026 5:10 PM, John Dallman wrote: ------------------------------------
This can be used to add resistance against stack-stomping via buffer overflows, but is potentially risky with RISC-V:
AUIPC X1, AddrHi
JALR X0, AddrLo(X1)
Can nuke the process, when officially it is allowed (vs forcing the use
of a different register to encode a long branch).

That should be:
AUPIC x1,hi(offset)
JALR x0,lo(offset)

using:
SETHI x1,AddrHi
JALR x0,AddrLo

would work.

---------------------

Like, how about one not try to bake in assumptions about 1-cycle ALU and 2-cycle Load being practical?...

for the above to work::
ALU is < ½ cycle leaving ¼ cycle output drive and ¼ cycle input mux
SRAM is ½ cycle, AGEN to SRAM decode is ¼ cycle, SRAM output to shifter
is < ¼ cycle, and set-selection is ½ cycle; leaving ¼ cycle for output drive.

Vs, say, 2-cycle ALU ops and 3-cycle Loads; with an ideal of putting 5 instructions between an instruction that generates a result and the instruction that consumes the result as this is more likely to work with in-order superscalar.

1-cycle ALU with 3 cycle LD is not very hard at 16-gates per cycle.
2-cycle LD is absolutely impossible with 1-cycle addr-in to data-out
SRAM. So, we generally consider any design with 2-cycle LD to be
frequency limited.

But, then one runs into the issue that if a basic operation then
requires a multi-op sequence, the implied latency goes up considerably
(say, could call this "soft latency", or SL).

So, for example, it means that, say:
2-instruction sign extension:
RV working assumption: 2 cycles
Hard latency (2c ALU): 4 cycles
Soft latency: 12 cycles.
For a 3-op sequence, the effective soft-latency goes up to 18, ...

One of the reasons a 16-gate design works better in practice than
a 12-gate design. And why a 1-cycle ALU, 3-cycle LD runs at higher
frequency.

And, in cases where the soft-latency significantly exceeds the total
length of the loop body, it is no longer viable to schedule the loop efficiently.

In software, there remains no significant problem running the loop
in HW.

So, in this case, an indexed-load instruction has an effective 9c SL, whereas SLLI+ADD+LD has a 21 cycle SL.

3-cycle indexed LD with cache hit in may µArchitectures--with scaled
indexing. This is one of the driving influences of "raising" the
semantic content of LD/ST instructions to [Rbase+Rindex<<sc+Disp]

where, in this case, the goal of something like the WEXifier is to
minimize this soft-latency cost (in cases where a dependency is seen,
any remaining soft-latency is counted as penalty).

But, then again, maybe the concept of this sort of "soft latency" seems
a bit alien.

Those ISAs without scaled indexing have longer effective latency through
cache than those with: those without full range Dsip have similar problems: those without both are effectively adding 3-4 cycles to LD latency.

Which is why the size of the execution windows grew from 60-ish to 300-ish
to double performance--the ISA is adding latency and the size of execution window is the easiest way to absorb such latency.
{{60-ish ~= Athlon; 300-ish ~= M4}}

Granted, not sure how this maps over to OoO, but had noted that even
with modern CPUs, there still seems to be benefit from assuming a sort
of implicit high latency for instructions over assuming a lower latency.

Execution window size is how it maps.

*1: Where people argue that if each vendor can do a CPU with their own custom ISA variants and without needing to license or get approval from
a central authority, that invariably everything would decay into an incoherent mess where there is no binary compatibility between
processors from different vendors (usual implication being that people
are then better off staying within the ARM ecosystem to avoid RV's lawlessness).

RISC-V seems to be "eating" a year (or a bit more) to bring this mess into
a coherent framework.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/20/2026 5:49 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 2/19/2026 5:10 PM, John Dallman wrote:
------------------------------------
This can be used to add resistance against stack-stomping via buffer
overflows, but is potentially risky with RISC-V:
AUIPC X1, AddrHi
JALR X0, AddrLo(X1)
Can nuke the process, when officially it is allowed (vs forcing the use
of a different register to encode a long branch).

That should be:
AUPIC x1,hi(offset)
JALR x0,lo(offset)

using:
SETHI x1,AddrHi
JALR x0,AddrLo

would work.

Usual notation seems to be that AUIPC uses a direct-immediate notation
(eg "AUIPC X1, 0x12345"), and "JALR X0, 0x678(X1)".

Though, GAS and friends can use:
AUIPC X1, %hi(symbol)
JALR X0, X1, %lo(symbol)

Well, and for JALR:
JALR Xd, Disp(Xs)
JALR Xd, Xs, Disp
Being basically equivalent.
...

If expressing it using a symbol rather than a literal displacement...

But, either way, it is using X1 that was the relevant point here, which
is technically allowed in RISC-V, but would explode if one tries to
constrain X1 to being used as a link register and then also uses
enforced tag checking in this case.

In BGBCC's native ASM notation, the symbol case would typically be
expressed as:
BRA symbol
Which them implies the 2-op form if the "symbol is within +/- 1MB check" fails. But, would differ in that this pseudo-op will stomp X5.



But, yeah, RISC-V ASM notation conventions seem to get a little
confusing sometimes...

But, errm, my point wasn't so much about RISC-V's ASM syntax patterns.


There is a non-zero risk though when one disallows uses that are
theoretically allowed in the ISA, even if GCC doesn't use them.


Though, the reason to sanity-check X1 is that it is pretty much
universally used as the link register, and sanitizing the link-register
can be used to trap on potential stack-corruption in buffer overflow
exploits (more so with a compiler that tends not to use stack canary
checks).


Well, and in terms of typical ASM notation, there is this mess:
(Rb) / @Rb / @(Rb) //load/store register
(Rb, Disp) / Disp(Rb) //load/store disp
@(Rb, Disp) / @(Disp, Rb) //load/store disp (but with @)
Then:
(Rb, Ri) //indexed (element sized index)
Ri(Rb) //indexed (byte-scaled index)
(Rb, Ri, Sc) //indexed with scale
Disp(Rb, Ri) //indexed with displacement
Disp(Rb, Ri, Sc) //indexed with displacement and scale
Then:
@Rb+ / (Rb)+ //post-increment
@-Rb / -(Rb) //pre-decrement
@Rb- / (Rb)- //post-decrement
@+Rb / +(Rb) //pre-increment

And, in some variants, all the registers prefixed with '%'.

Comparably, the Intel style notation is more consistent, but don't
necessarily want to also throw Intel notation into this particular mix.


Well, more so as there is an implicit visual hint, say in x86:
movl 128(%ebx), %eax
mov eax, [ebx+128]
Where the notation partly also keys one into the register ordering, but
if on had Intel style memory notation while using AT&T style ordering,
this would be a problem (confusing mess).


Well, or the other messy feature that BGBCC tries to infer the register
order based on which nmemonics are used:
OP Rd, Rs1, Rs2 //used in RV mnemonics dominate
OP Rs1, Rs2, Rd //otherwise

Likely, if [] notation were supported then it would likely signal "dest, source" ordering (like Intel x86, and ARM), though in this case
[Rb+Disp] and [Rb,Disp] likely being treated as analogous.


But, alas, kind of a mess...

And, if trying to mix/match styles, "there be dragons here"...

---------------------

Like, how about one not try to bake in assumptions about 1-cycle ALU and
2-cycle Load being practical?...

for the above to work::
ALU is < ½ cycle leaving ¼ cycle output drive and ¼ cycle input mux
SRAM is ½ cycle, AGEN to SRAM decode is ¼ cycle, SRAM output to shifter
is < ¼ cycle, and set-selection is ½ cycle; leaving ¼ cycle for output drive.

Vs, say, 2-cycle ALU ops and 3-cycle Loads; with an ideal of putting 5
instructions between an instruction that generates a result and the
instruction that consumes the result as this is more likely to work with
in-order superscalar.

1-cycle ALU with 3 cycle LD is not very hard at 16-gates per cycle.
2-cycle LD is absolutely impossible with 1-cycle addr-in to data-out
SRAM. So, we generally consider any design with 2-cycle LD to be
frequency limited.

My stuff mostly assumes:
ADD and similar: 2 cycles
Load: 3 cycles.

In this case, some 1 cycle ops exist:
MOV Rs, Rd / MV Xd, Xs
MOV Imm, Rd / LI Xd, Imm

For the RV and XG3 decoders, some special instructions are decoded as
one of the above:
ADDI Xd, Xs, 0 => MV
ADDI Xd, X0, Imm => LI

But, most remain as 2/3 cycle.

A few instructions had a 4 cycle latency, mostly those which combined a
Load with a format-conversion or similar.

But, then one runs into the issue that if a basic operation then
requires a multi-op sequence, the implied latency goes up considerably
(say, could call this "soft latency", or SL).

So, for example, it means that, say:
2-instruction sign extension:
RV working assumption: 2 cycles
Hard latency (2c ALU): 4 cycles
Soft latency: 12 cycles.
For a 3-op sequence, the effective soft-latency goes up to 18, ...

One of the reasons a 16-gate design works better in practice than
a 12-gate design. And why a 1-cycle ALU, 3-cycle LD runs at higher
frequency.

OK.

I ended up going for a slightly lower clock speed and slightly more
complex operations because often this resulted in better performance.

And, while I could probably run an RV32IM core at 100 MHz, I would need
to pay in other areas.

And, in cases where the soft-latency significantly exceeds the total
length of the loop body, it is no longer viable to schedule the loop
efficiently.

In software, there remains no significant problem running the loop
in HW.

Another traditional option is modulo scheduling, but actually doing so
in the compiler is more complex (and BGBCC does not do so).

Can often do a "poor man's" version in C, which while a less elegant
solution, often works out better in practice.


One can try to effectively unroll the loop enough that the latency can
be covered efficiently, but then the issue may become one of running out
of working registers, and one doesn't want to unroll so much that the
code starts thrashing, which tends to hurt worse than the potential loss
of ILP by being narrower.

So, in this case, an indexed-load instruction has an effective 9c SL,
whereas SLLI+ADD+LD has a 21 cycle SL.

3-cycle indexed LD with cache hit in may µArchitectures--with scaled indexing. This is one of the driving influences of "raising" the
semantic content of LD/ST instructions to [Rbase+Rindex<<sc+Disp]

Yeah, pretty much, or at lease [Rb+Ri<<Sc], but more of the full [Rb+Ri<<Sc+Disp] scenario often being uncommon IME.

Well, with a possible exception of [GP+Ri<<Sc+Disp] which would see a localized spike due to:
someGlobalArray[index]

As-is, this case tends to manifest in my case as, say:
LEA.Q (GP, Disp), R5
MOV.Q (R5, R10), R11

where, in this case, the goal of something like the WEXifier is to
minimize this soft-latency cost (in cases where a dependency is seen,
any remaining soft-latency is counted as penalty).

But, then again, maybe the concept of this sort of "soft latency" seems
a bit alien.

Those ISAs without scaled indexing have longer effective latency through cache than those with: those without full range Dsip have similar problems: those without both are effectively adding 3-4 cycles to LD latency.

Which is why the size of the execution windows grew from 60-ish to 300-ish
to double performance--the ISA is adding latency and the size of execution window is the easiest way to absorb such latency.
{{60-ish ~= Athlon; 300-ish ~= M4}}

OK.

FWIW, there are reasons I have indexed addressing and jumbo-prefixes for larger immediate values and displacements.

But, seemingly, the idea of deviating from 2R1W and 16/32 instruction encodings fills the RISC-V people with fear.

Granted, not sure how this maps over to OoO, but had noted that even
with modern CPUs, there still seems to be benefit from assuming a sort
of implicit high latency for instructions over assuming a lower latency.

Execution window size is how it maps.

OK.

*1: Where people argue that if each vendor can do a CPU with their own
custom ISA variants and without needing to license or get approval from
a central authority, that invariably everything would decay into an
incoherent mess where there is no binary compatibility between
processors from different vendors (usual implication being that people
are then better off staying within the ARM ecosystem to avoid RV's
lawlessness).

RISC-V seems to be "eating" a year (or a bit more) to bring this mess into
a coherent framework.

Yeah, and while ARC drags their feet,
Qualcomm/Huawei/ByteDance/T-Head/... each go off and do similar things
but in different ways...

If I were organizing it, would likely handle it differently, by having a nested structure:
Formal / Frozen //parts of the ISA that are fully settled.
Semi-formal / non-frozen //details subject to change.
provisional / experimental //very unstable.
vendor-specific //excluded from standardization.


In the provisional space, encodings could be defined, but could be
reclaimed if the feature is "dead"; but would be in encoding blocks
where they could be standardized later.

The main difference being that the provisional space, there would be a semi-official website listing registered encodings. Rather than these encodings being scattered in the ISA documentation for the various
vendor processors (requiring digging though a bunch of PDFs and so on to
try to figure out which encodings are already in-use).


Then sometimes there are encodings that are defined in way that don't
make sense, like apparently there is a RISC-V core from MIPS
Technologies, where they went and added Load/Store Pair, but with two
data source/dest register fields and a very small displacement.

This contrast strongly with, say, having even-pair registers and a
non-tiny displacement (displacement needs to be at least big enough to
cover a typical load/store area for a prolog/epilog).


I had at first reused LDU/SDU encodings, but then the proposal for
Load/Store indexed didn't go with my encoding scheme, but a different
one that also used LDU/SDU (but, maybe this is ultimately a better place
to put them; vs my approach of shoving them in an odd corner within the
'A' extension's block).



I ended up migrating Load/Store pair to the FLQ/FSQ encodings, partly as
I had no intention to implement the Q extension as-is (and I needed
somewhere to relocate them to). But, then this led to the "Pseudo Q" idea.


In my case, there is XG3, but I consider this in a different category
as, while it retains compatibility with RV64G and partial with RV64GC
(mostly by providing for interoperability); it is in some ways a notable departure from "pure" RISC-V (well, in that modes, tagged pointers, and swapping out RV-C encodings for a different 32-bit encoding space, are
not particularly small additions if one didn't already have a CPU
designed in this way).


...

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

jgd@cix.co.uk (John Dallman) writes:
[some unattributed source writes:]

In a way, it showed that they screwed up the design pretty hard
that x86-64 ended up being the faster and more efficient option...

They did. They really did.

I guess one question is if they had any other particular drawbacks
other than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;

IA-64 certainly had significantly larger code sizes than others, but I
think that they expected it and found it acceptable. And a
software-pipelined loop on IA-64 is probably smaller than an
auto-vectorized loop on AMD64+AVX, thanks to their predication
features that allowed them to avoid extra code for the ramp-up and
ramp-down of the software-pipelined loops, whereas auto-vectorized
code usually requires ramp-down, plus quite a bit of other overhead.
Clang seems to be significantly better at keeping such loops small
than gcc.

They
had two much bigger problems, though.

They'd correctly understood that the low speed of affordable dynamic RAM
as compared to CPUs running at hundreds of MHz was the biggest barrier to >making code run fast.

They may have "understood" it, as have many others who have read
"Hitting the memory wall", but I have disputed in 2001 that this is
correct in general:
https://www.complang.tuwien.ac.at/anton/memory-wall.html

[Looking at that text again, I see the claims "On current
high-performance machines this time [for compulsory cache misses] is
limited to a few seconds if the process stays in physical RAM" and
"Memory bandwidth tends to grow with memory size, so this won't change
much"; as it happens, I recently measured the memory bandwidth of my
PC with a Ryzen 8700G and 64GB RAM (whereas my machine in 2001 had
192MB): it is 64GB/s when read sequentially, i.e., it can read all its
RAM in 1s. For random accesses, performance is significantly worse,
however.]

McKee has written a retrospective of the paper in 2004 <http://svmoore.pbworks.com/w/file/fetch/59055930/p162-mckee.pdf>, but
has not cited my reaction (but she apparently had a wealth of
reactions to select from, so that's excusable),

Anyway, my point is that there are many programs that are not
memory-bound, and my convenience benchmarks I usually use (a LaTeX run
and Gforth's small benchmarks) are among them. Itanium II sucks on
them compared to its contemporary (or even older) competition; numbers
are times in seconds (lower means faster):

LaTeX <https://www.complang.tuwien.ac.at/franz/latex-bench>
- HP workstation 900MHz Itanium II, Debian Linux 3.528
- Athlon (Thunderbird) 1200C, VIA KT133A, PC133 SDRAM, RedHat7.1 1.68
- Pentium 4 2.66GHz, 512KB L2, Debian 3.1 1.31
- Athlon 64 3200+, 2000MHz, 1MB L2, Fedora Core 1 (64-bit) 0.76

Gforth <https://cgit.git.savannah.gnu.org/cgit/gforth.git/tree/Benchres>:
sieve bubble matrix fib fft release; CPU; gcc
0.708 0.780 0.484 1.028 0.552 20250201 Itanium II 900MHz (HP rx2600); gcc-4.3.2
0.192 0.276 0.108 0.360 0.7.0; K8 2GHz (Opteron 270); gcc-4.3.1

Their solution was have the compiler schedule loads
well in advance. They assumed, without evidence, that a compiler with
plenty of time to think could schedule loads better than hardware doing
it dynamically. It's an appealing idea, but it's wrong.

Actually, other architectures also added prefetching instructions for
dealing with that problem. All I have read about that was that there
were many disappointments when using these instructions. I don't know
if there were any successes, and how frequent they were compared to
the disappointments. So I don't see that IA-64 was any different from
other architectures in that respect.

My explanations for the disappointments are:

* Hardware prefetchers (typically stride-based) already cover a lot of
the cases where prefetch instructions would otherise help. In that
case memory-bound programs are limited by bandwidth, not by latency.

* When dealing with pointer-chasing in linked lists and such, unless
the linked list entries usually happen to be a fixed stride apart
(where the stride predictor helps), the pointer-chasing limits the
performance in any case; for an in-order uarch, prefetching or
scheduling the fetching of the next pointer ahead may save a cycles,
but typically few compared to the memory access latency; for OoO
uarchs, OoO usually will result in a bunch of instructions (among
them the load of the next pointer) waiting for the result of the RAM
access).

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

It might be possible to do that effectively in a single-core,
single-thread, single-task system that isn't taking many (if any)
interrupts. In a multi-core system, running a complex operating system, >several multi-threaded applications, and taking frequent interrupts and >context switches, it is _not possible_. There is no knowledge of any of
the interrupts, context switches or other applications at compile time,
so the compiler has no idea what is in cache and what isn't.

I don't think that's a big issue. Sure, a context switch in one core
results in the need to refill most of the L1 and L2 caches, and maybe
even a part of the L3 cache, but that's the cost of the context
switches, and the prefetching (whether by the compiler or the
programmer) is usually not designed to mitigate that. That's because
context switches are rare; e.g., when I run an 8-thread DGEMM (using
libopenmp) for 16000x16000 matrices on my 8-core desktop system (with
other stuff working (but consuming little CPU) at the same time, I see:

# perf stat -e sched:sched_switch,task-clock,context-switches,cpu-migrations,page-faults,cycles,instructions openblas 16000

Performance counter stats for 'openblas 16000':

14811 sched:sched_switch # 82.470 /sec
179592.12 msec task-clock # 7.444 CPUs utilized
14811 context-switches # 82.470 /sec
5 cpu-migrations # 0.028 /sec
9789 page-faults # 54.507 /sec
548255317659 cycles # 3.053 GHz
936546607037 instructions # 1.71 insn per cycle

24.125989128 seconds time elapsed

173.502827000 seconds user
6.016053000 seconds sys

I.e., one context switch every 37M cycles (or 63M instructions).
Refilling the 1MB L2 (Zen4) from RAM at 64GB/s costs about 47k cycles,
i.e., less than 0.2% of the time between context switches.

[You may wonder why the processor is only running at 3GHz; I have
power-limited it to 25W; it tends to do the same task close to 5GHz in
its default setting (88W power limit).]

Speculative execution addresses that problem quite effectively.

I have certainly read about interesting results for binary search (in
an array) where the branching version outperforms the branchless
version because the branching version speculatively executes several
followup loads, and even in unpredictable cases the speculation should
be right in 50% of the cases, resulting in an effective doubling of memory-level parallelism (but at a much higher cost in memory
subsystem load). But other than that, I don't see that speculative
execution helps with memory latency.

OoO helps in several ways: it will do some work in the shadow of the
load (although the utilization will still be abysmal even with
present-day schedulers and ROBs [1]); but more importantly, it can
dispatch additional loads that may also miss the cache, resulting in
more memory-level parallelism. To some extent that also happens with
in-order uarchs where the in-order aspect only takes effect when using
the result of an instruction, but OoO provides more cases (especially
if you do not know which loads will miss, which often is the case).

[1] With 50ns DRAM latency (somewhat optimistic) and 5GHz CPU with 6
rename slots per cycle, 1500 instructions could be executed (at its
most extreme) while a load is served from DRAM, but the scheduling
(and non-scheduler) slots tend to be ~100, and the ROB entries tend to
be ~500.

But I don't see that multi-core, multi-threaded, multi-tasking makes a significant difference here.

We don't
have a better way, almost thirty years after Itanium design decisions
were taken. They didn't want to do speculative execution

They wanted to do it (and did it) in the compiler; the corresponding architectural feature is IIRC the advanced load.

and they close
an instruction format and register set that made adding it later hard.

The instruction format makes no difference. Having so many registers
may have mad it harder than otherwise, but SPARC also used many
registers, and we have seen OoO implementations (and discussed them a
few months ago). The issue is that speculative execution and OoO
makes all the EPIC features of IA-64 unnecessary, so if they cannot do
a fast in-order implementation of IA-64 (and they could not), they
should just give up and switch to an architecture without these
features, such as AMD64. And Intel did, after a few years of denying.
The remainder of IA-64 was just to keep it alive for the customers who
had bought into it.

The other problem was that they had three (or six, or twelve) in-order >pipelines running in parallel. That meant the compilers had to provide
enough ILP to keep those pipelines fed, or they'd just eat cache capacity
and memory bandwidth executing no-ops ...

No, IA-64 has groups (sets of instructions that are allowed to start
within the same cycle) down to one instruction. Many people think
that the bundles (3 instructions encoded in 128 bits) are the same as
groups, but that's not the case. There can be stops (boundaries
between groups) within a bundle. The only thing the bundle format
limits is that branch targets may only start at a 128-bit boundary.

The IA-64 instruction format is still not particularly compact, but
it's not as bad as you indicate.

They didn't have a general way to extract enough ILP.

For a few cases, they have. But the problem is that these cases are
also vectorizable.

Their major problem was that they did not get enough ILP from
general-purpose code.

And even where they had enough ILP, OoO CPUs with SIMD extensions ate
their lunch.

I guess it is more of an open question of what would have happened,
say, if Intel had gone for an ISA design more like ARM64 or RISC-V
or something.

ARM64 seems to me to be the product of a lot more experience with >speculatively-executing processors than was available in 1998.

OoO processors with speculative execution have been widely available
since 1995 (Pentium Pro, PA 8000; actually PPC 603 preceded that in
1994, but made less of a splash than the Pentium Pro, and the ES/9000
H2 was available in 1991, but was confined to the IBM world; did they
ever submit SPEC results for that?). And the experience is that EPIC architectural features (beyond SIMD) are unnecessary, and the result
of that is indeed ARM64, but also AMD64 and RISC-V.

RISC-V has
not demonstrated really high performance yet, and it's been around long >enough that I'm starting to doubt it ever will.

In a world where we see convergence on fewer and fewer architecture
styles and on fewer and fewer architectures, you only see the
investment necessary for high-performance implementations of a new
architecture if there is a very good reason not to use one of the
established architectures (for ARM T32 and ARM A64 the smartphone
market was that reason). It may be that politics will provide that
reason for another architecture, but even then it's hard. But RISC-V
seems to have the most mindshare among the alternatives, so if any
architecture will catch up, it looks like the best bet.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Stefan Monnier <monnier@iro.umontreal.ca> writes:

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Actually, the IA-64 people could point to the work on VLIW (in
particular, Multiflow (trace scheduling) and Cydrome (software
pipelining)), which in turn is based on the work on compilers for
microcode.

That did not solve memory latency, but that's a problem even for OoO
cores.

I suspect a big part of the problem was tension between Intel and HP
were the only political solution was allowing the architects from both
sides to "dump in" their favorite ideas. A recipe for disaster.

The HP side had people like Bob Rau (Cydrome) and Josh Fisher
(Multiflow), and given their premise, the architecture is ok; somewhat
on the complex side, but they wanted to cover all the good ideas from
earlier designs; after all, it was to be the one architecture to rule
them all (especially performancewise). You cannot leave out a feature
that a competitor could then add to outperform IA-64.

The major problem was that the premise was wrong. They assumed that
in-order would give them a clock rate edge, but that was not the case,
right from the start (The 1GHz Itanium II (released July 2002)
competed with 2.53GHz Pentium 4 (released May 2002) and 1800MHz Athlon
XP (released June 2002)). They also assumed that explicit parallelism
would provide at least as much ILP as hardware scheduling of OoO CPUs,
but that was not the case for general-purpose code, and in any case,
they needed a lot of additional ILP to make up for their clock speed disadvantage.

The odd thing is that these were hardware companies betting on "someone
else" solving their problem, yet if compiler people truly had managed to >solve those problems, then other hardware companies could have taken >advantage just as well.

I am sure they had patents on stuff like the advanced load and the
ALAT, so no, other hardware companies would have had a hard time.

To me the main question is whether they were truly confused and just got >lucky (lucky because they still managed to sell their idea enough that
most RISC companies folded),

I think most RISC companies had troubles scaling. They were used to
small design teams spinning out simple RISCs in a short time, and did
not have the organization to deal with the much larger projects that
OoO superscalars required. And while everybody inventing their own architecture may have looked like a good idea when developing an
architecture and its implementations was cheap, it looked like a bad
deal when development costs started to ramp up in the mid-90s. That's
why HP went to Intel, and other companies (in particular, SGI) took
this as an exit strategy from the own-RISC business.

DEC had increasing delays in their chips, and eventually could not
make enough money with them and had to sell themselves to Compaq (who
also could not sustain the effort and sold themselves to HP (who
canceled Alpha development)). I doubt that IA-64 played a big role in
that game.

Back to IA-64: At the time, when OoO was just starting, the premise of
IA-64 looked plausible. Why wouldn't they see a fast clock rate and
higher ILP from explicit parallelism than conventional architectures
would see from OoO (apparently complex, and initially without anything
like IA-64's ALAT)?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


BGB <cr88192@gmail.com> posted:

On 2/20/2026 5:49 PM, MitchAlsup wrote:

----------------------------

There is a non-zero risk though when one disallows uses that are theoretically allowed in the ISA, even if GCC doesn't use them.

This is why one must decode all 32-bits of each instruction--so that
there is no hole in the decoder that would allow the core to do some-
thing not directly specified in ISA. {And one of the things that make
an industrial quality ISA so hard to fully specify.}}
---------------------

Well, and in terms of typical ASM notation, there is this mess:
(Rb) / @Rb / @(Rb) //load/store register
(Rb, Disp) / Disp(Rb) //load/store disp
@(Rb, Disp) / @(Disp, Rb) //load/store disp (but with @)
Then:
(Rb, Ri) //indexed (element sized index)
Ri(Rb) //indexed (byte-scaled index)
(Rb, Ri, Sc) //indexed with scale
Disp(Rb, Ri) //indexed with displacement
Disp(Rb, Ri, Sc) //indexed with displacement and scale
Then:
@Rb+ / (Rb)+ //post-increment
@-Rb / -(Rb) //pre-decrement
@Rb- / (Rb)- //post-decrement
@+Rb / +(Rb) //pre-increment

And, in some variants, all the registers prefixed with '%'.

Leading to SERIAL DECODE--which is BAD.
-----------------------
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

jgd@cix.co.uk (John Dallman) writes:
[some unattributed source writes:]

----------------

Actually, other architectures also added prefetching instructions for
dealing with that problem. All I have read about that was that there
were many disappointments when using these instructions. I don't know
if there were any successes, and how frequent they were compared to
the disappointments. So I don't see that IA-64 was any different from
other architectures in that respect.

If there had been any significant successes, you would have heard about them.

-------------------------------

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

Array and Matrix scientific codes with datasets bigger than cache.

----------------------------
I have certainly read about interesting results for binary search (in
an array) where the branching version outperforms the branchless
version because the branching version speculatively executes several
followup loads, and even in unpredictable cases the speculation should
be right in 50% of the cases, resulting in an effective doubling of memory-level parallelism (but at a much higher cost in memory
subsystem load). But other than that, I don't see that speculative
execution helps with memory latency.

At the cost of opening the core up to Spectré-like attacks. ------------------------

The instruction format makes no difference. Having so many registers
may have mad it harder than otherwise, but SPARC also used many
registers, and we have seen OoO implementations (and discussed them a
few months ago). The issue is that speculative execution and OoO
makes all the EPIC features of IA-64 unnecessary, so if they cannot do
a fast in-order implementation of IA-64 (and they could not), they
should just give up and switch to an architecture without these
features, such as AMD64. And Intel did, after a few years of denying.
The remainder of IA-64 was just to keep it alive for the customers who
had bought into it.

IA-64 was to prevent AMD (and others) from clones--that is all. Intel/HP
would have had a patent wall 10 feet tall.

It did not fail by being insufficiently protected, it failed because it
did not perform.
-----------------

For a few cases, they have. But the problem is that these cases are
also vectorizable.

Their major problem was that they did not get enough ILP from
general-purpose code.

And even where they had enough ILP, OoO CPUs with SIMD extensions ate
their lunch.

And that should have been the end of the story. ... Sorry Ivan.

- anton

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Actually, the IA-64 people could point to the work on VLIW (in
particular, Multiflow (trace scheduling) and Cydrome (software
pipelining)), which in turn is based on the work on compilers for
microcode.

That did not solve memory latency, but that's a problem even for OoO
cores.

I suspect a big part of the problem was tension between Intel and HP
were the only political solution was allowing the architects from both
sides to "dump in" their favorite ideas. A recipe for disaster.

The HP side had people like Bob Rau (Cydrome) and Josh Fisher
(Multiflow), and given their premise, the architecture is ok; somewhat
on the complex side, but they wanted to cover all the good ideas from
earlier designs; after all, it was to be the one architecture to rule
them all (especially performancewise). You cannot leave out a feature
that a competitor could then add to outperform IA-64.

In this time period, performance was doubling every 14 months, so if a
feature added x performance it MUST avoid adding more than x/14 months
to the schedule. If IA-64 was 2 years earlier, it would have been com- petitive--sadly it was not.
---------------------

To me the main question is whether they were truly confused and just got >lucky (lucky because they still managed to sell their idea enough that
most RISC companies folded),

I think most RISC companies had troubles scaling. They were used to
small design teams spinning out simple RISCs in a short time, and did
not have the organization to deal with the much larger projects that
OoO superscalars required.

Most RISC teams did not have the cubic dollars of revenue to afford the
team size needed for GBOoO design--nor, BTW, the management expertise
to run such a large organization efficiently.

And while everybody inventing their own architecture may have looked like a good idea when developing an
architecture and its implementations was cheap,

1-wide, and a bit of 2-wide.

it looked like a bad
deal when development costs started to ramp up in the mid-90s. That's
why HP went to Intel, and other companies (in particular, SGI) took
this as an exit strategy from the own-RISC business.

DEC had increasing delays in their chips, and eventually could not
make enough money with them and had to sell themselves to Compaq (who
also could not sustain the effort and sold themselves to HP (who
canceled Alpha development)). I doubt that IA-64 played a big role in
that game.

Back to IA-64: At the time, when OoO was just starting, the premise of
IA-64 looked plausible. Why wouldn't they see a fast clock rate and
higher ILP from explicit parallelism than conventional architectures
would see from OoO (apparently complex, and initially without anything
like IA-64's ALAT)?

- anton

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/21/2026 2:15 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 2/20/2026 5:49 PM, MitchAlsup wrote:

----------------------------

There is a non-zero risk though when one disallows uses that are
theoretically allowed in the ISA, even if GCC doesn't use them.

This is why one must decode all 32-bits of each instruction--so that
there is no hole in the decoder that would allow the core to do some-
thing not directly specified in ISA. {And one of the things that make
an industrial quality ISA so hard to fully specify.}}
---------------------

Sometimes there is a tension:
What is theoretically allowed in the ISA;
What is the theoretically expected behavior in some abstract model;
What stuff is actually used by compilers;
What features or behaviors does one want;
...

Implementing RISC-V strictly as per an abstract model would limit both efficiency and hinder some use-cases.

Then it comes down to "what do compilers do" and "what unintentional
behaviors could an ASM programmer stumble onto unintentionally".

Stuff like "Program misbehaves or crashes on a fairly mundane piece of
code" are preferably avoided.


Alternatives being, say:
Define behaviors what programs are allowed to rely on;
Be slightly conservative with how one defines edge cases;
Avoid over-defining things too far outside the scope of what is actually relevant.

Sometimes design elegance can become a trap.


But, OTOH, having special cases for some instructions based on which
registers or immediate values are used isn't exactly clean or elegant.

Like, yeah:
Using X0 or X1 here invokes magic;
Instruction doesn't work unless X0 or X1;
...

Well, and in terms of typical ASM notation, there is this mess:
(Rb) / @Rb / @(Rb) //load/store register
(Rb, Disp) / Disp(Rb) //load/store disp
@(Rb, Disp) / @(Disp, Rb) //load/store disp (but with @)
Then:
(Rb, Ri) //indexed (element sized index)
Ri(Rb) //indexed (byte-scaled index)
(Rb, Ri, Sc) //indexed with scale
Disp(Rb, Ri) //indexed with displacement
Disp(Rb, Ri, Sc) //indexed with displacement and scale
Then:
@Rb+ / (Rb)+ //post-increment
@-Rb / -(Rb) //pre-decrement
@Rb- / (Rb)- //post-decrement
@+Rb / +(Rb) //pre-increment

And, in some variants, all the registers prefixed with '%'.

Leading to SERIAL DECODE--which is BAD.
-----------------------

Depends on what ISA the ASM syntax is actually attached to...
If it is a VAX, yeah, true enough.

Seemingly most of these syntax variants go back to PDP-11 and VAX origins.

Then some quirks, like '%' on register names, apparently mostly came
from the M68K branch:
PDP/VAX: No '%'
M68K: Added '%'
GAS on x86: Mostly kept using M68K notation.


Then apparently the '@' thing was partly a thing originating either in
Hitachi or Texas Instruments (along with putting '.' in many of the instruction mnemonics).

So, if working backwards, could drop all the '@' variants, along with
'%', ...


Where, apparently, the syntax scheme I had mostly ended up using for
BGBCC and my own stuff, ended up partly mutating back towards the
original PDP/VAX style syntax.

Namely, was using:
(Rb)
(Rb, Rb)
(Rb, Disp) | Disp(Rb)
...

Though, had mostly kept the dotted names vs reverting to dot-free names.


--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


BGB <cr88192@gmail.com> posted:

On 2/21/2026 2:15 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 2/20/2026 5:49 PM, MitchAlsup wrote:

----------------------------

There is a non-zero risk though when one disallows uses that are
theoretically allowed in the ISA, even if GCC doesn't use them.

This is why one must decode all 32-bits of each instruction--so that
there is no hole in the decoder that would allow the core to do some-
thing not directly specified in ISA. {And one of the things that make
an industrial quality ISA so hard to fully specify.}}
---------------------

Sometimes there is a tension:
What is theoretically allowed in the ISA;
What is the theoretically expected behavior in some abstract model;
What stuff is actually used by compilers;
What features or behaviors does one want;
...

Whether your ISA can be attacked with Spectré and/or Meltdown;
Whether your DFAM can be attacked with RowHammer;
Whether your call/return interface can be attacked with:
{ Return Orienter Programmeing, Buffer Overflows, ...}

That is; whether you care if your system provides a decently robust
programming environment.

I happen to care. Apparently, most do not.

Implementing RISC-V strictly as per an abstract model would limit both efficiency and hinder some use-cases.

One can make an argument that it is GOOD to limit attack vectors, and
provide a system that is robust in the face of attacks.

Then it comes down to "what do compilers do" and "what unintentional behaviors could an ASM programmer stumble onto unintentionally".

Nïeve at best.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Actually, the IA-64 people could point to the work on VLIW (in
particular, Multiflow (trace scheduling) and Cydrome (software
pipelining)), which in turn is based on the work on compilers for
microcode.

I knew the Multiflow people pretty well when I was at Yale. Trace
scheduling was inspired by the FPS AP-120B, which had wide
instructions issuing multiple operations and was extremely hard to
program efficiently.

Multiflow's compiler worked pretty well and did a good job of static
scheduling memory operations when the access patterns weren't too data dependent. It was good enough that Intel and HP both licensed it and
used it in their VLIW projects. It was a good match for the hardware
in the 1980s.

But as computer hardware got faster and denser, it became possible to
do the scheduling on the fly in hardware, so you could get comparable performance with conventional instruction sets in a microprocessor.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

But as computer hardware got faster and denser, it became possible to
do the scheduling on the fly in hardware, so you could get comparable >performance with conventional instruction sets in a microprocessor.

Actually, OoO microprocessors appeared before IA-64 implementations
were originally planned to be released, and were implemented in larger processes, i.e., they consumed fewer hardware resources.

The Pentium Pro was implemented with 5.5M transistors in a 0.35um
process (with 8+8KB L1 cache) and a die area of 306mm^2 (probably
including the separate L2 cache chip). Later Intel released the
Klamath Pentium II also in 0.35um, but with 16+16KB L1, with 7.5M
transistors and a die size of 203mm^2 (the die should be larger than
the CPU die of the Pentium Pro, that's why I think that the Pentium
Pro number includes the L2 cache die); die size numbers from https://pc.watch.impress.co.jp/docs/2008/1027/kaigai_5.pdf

The PA-8000 is a 4-wide OoO CPU implemented with 3.8M transistors in a
0.5um process in 337.69mm^2. It has all caches off-chip.

The Merced Itanium and McKinley Itanium II were 6-wide and implemented
in 180nm, the same feature size as the Willamette Pentium 4 and
Thunderbird Athlon. The Merced is reported as having 25.4M
transistors (with 16+16KB L1 and 96KB of L2 cache plus 295M
transistors for 4MB external L3 cache). The McKinley is reported as
having a die size of 421mm^2 and a transistor count of 221M (with
16+16KB L1, 256KB L2 and 3MB L3).

Looking at <https://en.wikipedia.org/wiki/Itanium#Design_and_delays:_1994%E2%80%932001>,
I read:

|When Merced was floorplanned for the first time in mid-1996, it turned
|out to be far too large [...]. The designers had to reduce the
|complexity (and thus performance) of subsystems, including the x86
|unit and cutting the L2 cache to 96 KB.[d] Eventually it was agreed
|that the size target could only be reached by using the 180 nm process |instead of the intended 250 nm.

For comparison, in the same 0.18um process the Willamette included
8+8KB L1 and 256KB L2 cache in 217mm^2, and in the same-sized process
the AMD Thunderbird and Palomino included 64+64KB L1 and 256KB L2
cache.

Unfortunately, the caches dominate the transistor counts, so one
cannot tell how many transistors were needed for implementing the data
path and cotrol stuff.

We do have in-order CPUs such as the 4-wide 21164: 9.3M transistors
(with 8+8KB L1 and 96KB L2), 299mm^2 in a 0.5um process.

So the OoOness of the PA-8000 may have cost around as much area as the
caches of the 21164 (and the higher clock rate of the 21164 compared
to the PA-8000 and the Pentium Pro supported the theory that OoO is
inherently slower).

Comparing the 21164 to the Merced, the L2 cache sizes are the same and
the L1 size of Merced is twice that of the 21164, yet the Merced takes
2.7x the number of transistors of the 21164, and probably a lot of the additional transistors are not for the additional L1 caches. It seems
that the architectural features and/or maybe the 6-wide implementation
of the Merced cost a lot of transistors and thus die area, whereas a
sales pitch for EPIC was that thanks to the explicit grouping of
instructions, the supposedly quadratic cost of checking for register-to-register dependences would be eliminated, resulting in
more area for additional functional units.

Bottom line: If EPIC is easier to fit on a microprocessor, there is no
evidence for that.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

[1) stride-based. 2) pointer-chasing]

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

Array and Matrix scientific codes with datasets bigger than cache.

The dense cases are covered by stride-based hardware predictors, so
they are not "otherwise". I am not familiar enough with sparse
scientific codes to comment on whether they are 1), 2), or
"otherwise".

I have certainly read about interesting results for binary search (in
an array) where the branching version outperforms the branchless
version because the branching version speculatively executes several
followup loads, and even in unpredictable cases the speculation should
be right in 50% of the cases, resulting in an effective doubling of
memory-level parallelism (but at a much higher cost in memory
subsystem load). But other than that, I don't see that speculative
execution helps with memory latency.

At the cost of opening the core up to Spectré-like attacks.

There may be a way to avoid the side channel while still supporting
this scenario. But I think that there are better ways to speed up
such a binary search:

Here software prefetching can really help: prefetch one level ahead (2 prefetches), or two levels ahead (4 prefetches), three levels (8
prefetches), or four levels (16 prefetches), etc., whatever gives the
best performance (which may be hardware-dependent). The result is a
speedup of the binary search by (in the limit) levels+1.

By contrast, the branch prediction "prefetching" provides a factor 1.5
at twice the number of loads when one branch is predicted, 1.75 at 3x
the number of loads when two branches are predicted, etc. up to a
speedup factor of 2 with an infinite of loads and predicted branches;
that's for completely unpredictable lookups, with some predictability
the branch prediction approach performs better, and with good
predictability it should outdo the software-prefetching approach for
the same number of additional memory accesses.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

The HP side had people like Bob Rau (Cydrome) and Josh Fisher
(Multiflow), and given their premise, the architecture is ok; somewhat
on the complex side, but they wanted to cover all the good ideas from
earlier designs; after all, it was to be the one architecture to rule
them all (especially performancewise). You cannot leave out a feature
that a competitor could then add to outperform IA-64.

In this time period, performance was doubling every 14 months, so if a >feature added x performance it MUST avoid adding more than x/14 months
to the schedule. If IA-64 was 2 years earlier, it would have been com- >petitive--sadly it was not.

No, if a feature adds a year in development time, you start a year
earlier (or alternatively target a release a year later).

Intel adds features to AMD64 (or "Intel 64", as they call it) all the
time, usually with little immediate performance impact, but they
managed to keep their schedules, at least while the process advances
also kept to their schedules (which broke down around 2016).

For IA-64, Intel/HP later did not add ISA features, and still did not
result in competetive performance for general-purpose code.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Sun, 22 Feb 2026 13:17:30 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

[1) stride-based. 2) pointer-chasing]

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come
to mind, but are they really common, apart from programming
classes?

Array and Matrix scientific codes with datasets bigger than cache.

The dense cases are covered by stride-based hardware predictors, so
they are not "otherwise". I am not familiar enough with sparse
scientific codes to comment on whether they are 1), 2), or
"otherwise".

BLAS Level 3 is not particularly external/LLC bandwidth intensive even
without hardware predictors. Overwhelming majority of data served from
L2 cache.
That's with classic SIMD. It's possible that with AMX units it's no
longer true.

I have certainly read about interesting results for binary search
(in an array) where the branching version outperforms the
branchless version because the branching version speculatively
executes several followup loads, and even in unpredictable cases
the speculation should be right in 50% of the cases, resulting in
an effective doubling of memory-level parallelism (but at a much
higher cost in memory subsystem load). But other than that, I
don't see that speculative execution helps with memory latency.

At the cost of opening the core up to Spectr_�-like attacks.

There may be a way to avoid the side channel while still supporting
this scenario. But I think that there are better ways to speed up
such a binary search:

Here software prefetching can really help: prefetch one level ahead (2 prefetches), or two levels ahead (4 prefetches), three levels (8
prefetches), or four levels (16 prefetches), etc., whatever gives the
best performance (which may be hardware-dependent). The result is a
speedup of the binary search by (in the limit) levels+1.

By contrast, the branch prediction "prefetching" provides a factor 1.5
at twice the number of loads when one branch is predicted, 1.75 at 3x
the number of loads when two branches are predicted, etc. up to a
speedup factor of 2 with an infinite of loads and predicted branches;
that's for completely unpredictable lookups, with some predictability
the branch prediction approach performs better, and with good
predictability it should outdo the software-prefetching approach for
the same number of additional memory accesses.

- anton

The recent comparisons of branchy vs branchless binary search that we
carried on RWT forum seems to suggest that on modern CPUs branchless
variant is faster even when the table does not fit in LLC.
Branchy variant manages to pull ahead only when TLB misses can't be
served from L2$.
At least that how I interpreted it.
Here is result on very modern CPU: https://www.realworldtech.com/forum/?threadid=223776&curpostid=223974
And here is older gear: https://www.realworldtech.com/forum/?threadid=223776&curpostid=223895
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Anton Ertl [2026-02-21 18:41:12] wrote:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

MitchAlsup <user5857@newsgrouper.org.invalid> wrote:

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Actually, the IA-64 people could point to the work on VLIW (in
particular, Multiflow (trace scheduling) and Cydrome (software
pipelining)), which in turn is based on the work on compilers for
microcode.

Of course, compiler people have worked on such problems and solved some
cases. But what I wrote above is that "I can't remember seeing
... compiler people" claiming that "{sooner or later} compilers COULD
figure stuff like this out".

The major problem was that the premise was wrong. They assumed that
in-order would give them a clock rate edge, but that was not the case,
right from the start (The 1GHz Itanium II (released July 2002)
competed with 2.53GHz Pentium 4 (released May 2002) and 1800MHz Athlon
XP (released June 2002)). They also assumed that explicit parallelism
would provide at least as much ILP as hardware scheduling of OoO CPUs,
but that was not the case for general-purpose code, and in any case,
they needed a lot of additional ILP to make up for their clock speed disadvantage.

Definitely.

The odd thing is that these were hardware companies betting on "someone >>else" solving their problem, yet if compiler people truly had managed to >>solve those problems, then other hardware companies could have taken >>advantage just as well.

I am sure they had patents on stuff like the advanced load and the
ALAT, so no, other hardware companies would have had a hard time.

I'm pretty sure that if compiler people ever solve the problems that
plagued the Itanium, those same solutions can bring similar benefits to architectures using other (non-patented) mechanisms.


=== Stefan
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch


John Levine <johnl@taugh.com> posted:

According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:

Stefan Monnier <monnier@iro.umontreal.ca> writes:

At the time of conception, there were amny arguments that {sooner or
later} compilers COULD figure stuff like this out.

I can't remember seeing such arguments comping from compiler people, tho.

Actually, the IA-64 people could point to the work on VLIW (in
particular, Multiflow (trace scheduling) and Cydrome (software >pipelining)), which in turn is based on the work on compilers for >microcode.

I knew the Multiflow people pretty well when I was at Yale. Trace
scheduling was inspired by the FPS AP-120B, which had wide
instructions issuing multiple operations and was extremely hard to
program efficiently.

Multiflow's compiler worked pretty well and did a good job of static scheduling memory operations when the access patterns weren't too data dependent. It was good enough that Intel and HP both licensed it and
used it in their VLIW projects. It was a good match for the hardware
in the 1980s.

But as computer hardware got faster and denser, it became possible to
do the scheduling on the fly in hardware, so you could get comparable performance with conventional instruction sets in a microprocessor.

Not comparable; superior.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

According to Stefan Monnier <monnier@iro.umontreal.ca>:

particular, Multiflow (trace scheduling) and Cydrome (software
pipelining)), which in turn is based on the work on compilers for
microcode.

Of course, compiler people have worked on such problems and solved some >cases. But what I wrote above is that "I can't remember seeing
... compiler people" claiming that "{sooner or later} compilers COULD
figure stuff like this out".

I recall Multiflow people telling me that trace scheduling did a great job
of scheduling memory accesses when the patterns were predictable and that it didn't when they weren't, i.e., data dependent.

Apropos another thread I can believe that IA-64 was obsolete before it was shipped
for that reason, static scheduling will never keep up with dynamic except in applications where the access patterns are predictable.

Are there enough applications like that to make VLIWs worth it? Some kinds of DSP?
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <10nak0a$nrac$2@dont-email.me>, cr88192@gmail.com (BGB) wrote:

Does imply that my younger self was notable, and not seen as just
some otherwise worthless nerd.

Educators who are any good notice the weird kids who are actually smart.

For 128 predicate registers, this part doesn't make as much sense:

I suspect they wanted to re-use some logic.

The tricks Itanium could do with combinations of predicate registers were pretty weird. There was at least one instruction for manipulating them
which I was entirely unable to understand, with the manual in front of me
and pencil and paper to try examples. Fortunately, it never occurred in
code generated by any of the compilers I used.

*1: Where people argue that if each vendor can do a CPU with their
own custom ISA variants and without needing to license or get
approval from a central authority, that invariably everything would
decay into an incoherent mess where there is no binary
compatibility between processors from different vendors (usual
implication being that people are then better off staying within
the ARM ecosystem to avoid RV's lawlessness).

The importance of binary compatibility is very much dependent on the
market sector you're addressing. It's absolutely vital for consumer apps
and games. It's much less important for current "AI" where each vendor
has their own software stack anyway. RISC-V seems to be far more
interested in the latter at present.

John
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

Apropos another thread I can believe that IA-64 was obsolete before it was shipped
for that reason, static scheduling will never keep up with dynamic except in >applications where the access patterns are predictable.

Concerning the scheduling, hardware scheduling looked pretty dumb at
the time (always schedule the oldest ready instruction(s)), and
compilers could pick the instructions on the critical path in their
scheduling, but given the scheduling barriers in compilers (e.g.,
calls and returns), and the window sizes in current hardware, even
dumb is superior to smart.

Another aspect where hardware is far superior is branch prediction.

Are there enough applications like that to make VLIWs worth it? Some kinds of DSP?

There have certainly been DSPs from TI (C60 series IIRC), and Phillips (TriMedia) that have VLIW architectures, so at least for a while, VLIW
was competetive there.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:

John Levine <johnl@taugh.com> writes:

Apropos another thread I can believe that IA-64 was obsolete before it was shipped
for that reason, static scheduling will never keep up with dynamic except in >>applications where the access patterns are predictable.

Concerning the scheduling, hardware scheduling looked pretty dumb at
the time (always schedule the oldest ready instruction(s)), ...

I was thinking of memory scheduling. You have multiple banks of memory
each of which can only do one fetch or store at a time, and the goal
was to keep all of the banks as busy as possible. If you're accessing
an array in predictable order, trace scheduling works well, but if
you're fetching a[b[i]] where b varies at runtime, it doesn't.

Another aspect where hardware is far superior is branch prediction.

I gather speculative execution of both branch paths worked OK if the
branch tree wasn't too bushy. There were certainly ugly details, e.g.,
if there's a trap on a path that turns out not to be taken.
--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

John Levine <johnl@taugh.com> writes:

According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:

John Levine <johnl@taugh.com> writes:

Apropos another thread I can believe that IA-64 was obsolete before it was shipped
for that reason, static scheduling will never keep up with dynamic except in >>>applications where the access patterns are predictable.

Concerning the scheduling, hardware scheduling looked pretty dumb at
the time (always schedule the oldest ready instruction(s)), ...

I was thinking of memory scheduling. You have multiple banks of memory
each of which can only do one fetch or store at a time, and the goal
was to keep all of the banks as busy as possible. If you're accessing
an array in predictable order, trace scheduling works well, but if
you're fetching a[b[i]] where b varies at runtime, it doesn't.

More advanced in-order uarchs have dealt with this by submitting
requests to the load-store unit in-order, performing the requests as
the resources and the memory model allow, and only letting uses of the
loads wait for the results (Mitch Alsup has been calling such things
OoO, too, but that's far from the modern OoO with speculative
execution and in-order completion; in particular, there is no
speculative execution).

Plus, there is the option of inserting prefetch instructions, which
give the same memory-level parallelism on in-order CPUs as on OoO
CPUs; for a[b[i]] patterns they might be useful, unless the hardware prefetchers also know how to prefetch that.

Moreover, AVX-512 has a gathering load instruction (and a scattering
store instruction) that were designed for an optimized in-order
implementation in Knights Ferry.

Another aspect where hardware is far superior is branch prediction.

I gather speculative execution of both branch paths worked OK if the
branch tree wasn't too bushy.

If one goes that way, if-conversion (conversion to predicated
execution) looked like the way to go, but it turns a control
dependency (which vanishes if the branch is predicted correctly) into
a data dependency. Even without that, pulling instructions from all
ways up across branches soon runs into resource limitations. Static
branch prediction is not great (~20% mispredicts when using
heuristics, ~10% when using profile feedback), but it is still far
better than assuming that all branches go both ways equally likely.

Augustus K. Uht suggested that one keeps track of the likelyhood of
statically not-predicted branches; after following a few prediction,
the likelyhood of the path to the currently predicted branch would be
smaller than the likelyhood of one of the earlier not-predicted
branches. He suggested that the compiler should use these likelyhoods
to guide speculation decisions.

But in the early 1990s dynamic (hardware) branch prediction started
producing significantly lower misprediction rates than static and even semi-static branch prediction, and branch predictors have improved
since then; e.g., for our LaTeX benchmark Zen 4 produces the following
results:

1_325_396_218 cycles 4.961 GHz ( +- 0.12% )
3_565_310_588 instructions 2.69 insn per cycle
656_903_470 branches 2.459 G/sec ( +- 0.01% )
8_417_229 branch-misses 1.28% of all branches ( +- 0.21% )

That's not just 1.28% branch mispredictions, but also 2.36 branch mispredictions per 1000 instruction (MPKI), or 423 instructions
between branch mispredictions on average. This means that the
hardware scheduler can schedule across hundreds of instructions before
hitting a scheduling barrier. It also means that all the speculation
within those 423 instructions will actually be useful, whereas
speculating on both sides of a branch (or if-conversion) guarantees
that most of the speculated instructions will be useless.

But yes, for instructions from behind an if that do not depend on the
values computed in the if, one can schedule them above the if without duplication along both paths, and this looked like one of the
smartness advantages of compilers over OoO hardware. But given the
very high branch prediction accuracies that hardware exhibits, this
advantage is small, and as IA-64 demonstrated, does not outweigh the disadvantages of EPIC by far.

There were certainly ugly details, e.g.,
if there's a trap on a path that turns out not to be taken.

IA-64 (and EPIC in general) has the advanced load for that; IA-64 also
does not implement division in hardware (i.e., division by zero is
checked by software). This means that any trapping can happen once
the branch is guaranteed to be taken, but the speculative execution
happens earlier. If static branch prediction worked as well as
dynamic branch prediction, that would have been one of the important
parts in making IA-64 have as much ILP as OoO.

I have actually written a paper on the topic:

@InProceedings{ertl&krall94,
author = "M. Anton Ertl and Andreas Krall",
title = "Delayed Exceptions --- Speculative Execution of
Trapping Instructions",
booktitle = "Compiler Construction (CC '94)",
year = "1994",
publisher = "Springer LNCS~786",
address = "Edinburgh",
month = "April",
pages = "158--171",
url = "https://www.complang.tuwien.ac.at/papers/ertl-krall94cc.ps.gz",
abstract = "Superscalar processors, which execute basic blocks
sequentially, cannot use much instruction level
parallelism. Speculative execution has been proposed
to execute basic blocks in parallel. A pure software
approach suffers from low performance, because
exception-generating instructions cannot be executed
speculatively. We propose delayed exceptions, a
combination of hardware and compiler extensions that
can provide high performance and correct exception
handling in compiler-based speculative execution.
Delayed exceptions exploit the fact that exceptions
are rare. The compiler assumes the typical case (no
exceptions), schedules the code accordingly, and
inserts run-time checks and fix-up code that ensure
correct execution when exceptions do happen."
}

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Sun, 22 Feb 2026 13:17:30 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted: =20

[1) stride-based. 2) pointer-chasing]

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come
to mind, but are they really common, apart from programming
classes? =20

Array and Matrix scientific codes with datasets bigger than cache. =20 >>=20

The dense cases are covered by stride-based hardware predictors, so
they are not "otherwise". I am not familiar enough with sparse
scientific codes to comment on whether they are 1), 2), or
"otherwise".
=20

BLAS Level 3 is not particularly external/LLC bandwidth intensive even >without hardware predictors.

There are HPC applications that are bandwidth limited; that's why they
have the roofline performance model (e.g., <https://docs.nersc.gov/tools/performance/roofline/>). Of course for
the memory-bound applications the uarch style is not particularly
important, as long as it allows to exploit the memory-level
parallelism in some way; prefetching (by hardware or software) is a
way that can be performed by any kind of uarch to exploit MLP.

IA-64 implementations have performed relatively well for SPECfp. I
don't know how memory-bound these applications were, though.

For those applications that benefit from caches (e.g., matrix
multiplication), memory-level parallelism is less important.

Overwhelming majority of data served from
L2 cache.
That's with classic SIMD. It's possible that with AMX units it's no
longer true.

I very much doubt that. There is little point in adding an
instruction that slows down execution by turning it from compute-bound
to memory-bound.

The recent comparisons of branchy vs branchless binary search that we
carried on RWT forum seems to suggest that on modern CPUs branchless
variant is faster even when the table does not fit in LLC.=20

Only two explanations come to my mind:

1) The M3 has a hardware prefetcher that recognizes the pattern of a
binary array search and prefetches accordingly. The cache misses from
page table accesses might confuse the prefetcher, leading to worse
performance eventually.

2) (doubtful) The compiler recognizes the algorithm and inserts
software prefetch instructions.

Branchy variant manages to pull ahead only when TLB misses can't be
served from L2$.
At least that how I interpreted it.

Here is result on very modern CPU: >https://www.realworldtech.com/forum/?threadid=3D223776&curpostid=3D223974

And here is older gear: >https://www.realworldtech.com/forum/?threadid=3D223776&curpostid=3D223895

I tried to run your code <https://www.realworldtech.com/forum/?threadid=223776&curpostid=223955>
on Zen4, but clang-14 converts uut2.c into branchy code. I could not
get gcc-12 to produce branchless code from slightly adapted source
code, either. My own attempt of using extended asm did not pass your
sanity checks, so eventually I used the assembly code produced by
clang-19 through godbolt. Here I see that branchy is faster for the
100M array size on Zen4 (i.e., where on the M3 branchless is faster):

[~/binary-search:165562] perf stat branchless 100000000 10000000 10
4041.093082 msec. 0.404109 usec/point
Performance counter stats for 'branchless 100000000 10000000 10':

45436.88 msec task-clock 1.000 CPUs utilized
276 context-switches 6.074 /sec
0 cpu-migrations 0.000 /sec
1307 page-faults 28.765 /sec 226091936865 cycles 4.976 GHz
1171349822 stalled-cycles-frontend 0.52% frontend cycles idle
34666912723 instructions 0.15 insn per cycle
0.03 stalled cycles per insn
5829461905 branches 128.298 M/sec
45963810 branch-misses 0.79% of all branches

45.439541729 seconds time elapsed

45.397207000 seconds user
0.040008000 seconds sys


[~/binary-search:165563] perf stat branchy 100000000 10000000 10
3051.269998 msec. 0.305127 usec/point
Performance counter stats for 'branchy 100000000 10000000 10':

34308.48 msec task-clock 1.000 CPUs utilized
229 context-switches 6.675 /sec
0 cpu-migrations 0.000 /sec
1307 page-faults 38.096 /sec 172472673652 cycles 5.027 GHz
49176146462 stalled-cycles-frontend 28.51% frontend cycles idle
33346311766 instructions 0.19 insn per cycle
1.47 stalled cycles per insn
10322173655 branches 300.864 M/sec
1583842955 branch-misses 15.34% of all branches

34.311432848 seconds time elapsed

34.264437000 seconds user
0.044005000 seconds sys

If you have recommendations what to use for the other parameters, I
can run other sizes as well.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Sun, 22 Feb 2026 13:17:30 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted: =20

[1) stride-based. 2) pointer-chasing]

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays
come to mind, but are they really common, apart from programming
classes? =20

Array and Matrix scientific codes with datasets bigger than
cache. =20

=20
The dense cases are covered by stride-based hardware predictors, so
they are not "otherwise". I am not familiar enough with sparse
scientific codes to comment on whether they are 1), 2), or
"otherwise".
=20

BLAS Level 3 is not particularly external/LLC bandwidth intensive
even without hardware predictors.

There are HPC applications that are bandwidth limited; that's why they
have the roofline performance model (e.g., <https://docs.nersc.gov/tools/performance/roofline/>).

Sure. But that's not what I would call "dense".
In my vocabulary "dense" starts at matmul(200x200,x200) or at LU
decomposition of matrix of similar dimensions.
I don't consider anything in BLAS Level 2 as "dense".
May be, my definitions of terms are unusual.

Of course for
the memory-bound applications the uarch style is not particularly
important, as long as it allows to exploit the memory-level
parallelism in some way; prefetching (by hardware or software) is a
way that can be performed by any kind of uarch to exploit MLP.

IA-64 implementations have performed relatively well for SPECfp. I
don't know how memory-bound these applications were, though.

SPECfp2006 was mostly not memory-bound on CPUs of that era.
OTOH, SPECfp_rate2006 for n>4 was memory-bound rather heavily.

For those applications that benefit from caches (e.g., matrix multiplication), memory-level parallelism is less important.

Overwhelming majority of data served from
L2 cache.
That's with classic SIMD. It's possible that with AMX units it's no
longer true.

I very much doubt that. There is little point in adding an
instruction that slows down execution by turning it from compute-bound
to memory-bound.

It does not slow down the execution. To the contrary, it speeds it up
so much that speed of handling of L2 misses begins to matter.
Pay attention that it's just my speculation that can be wrong.
IIRC, right now binary64-capable AMX is available only on Apple Silicon
(via SME) and may be on IBM Z. I didn't play with either.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

The recent comparisons of branchy vs branchless binary search that we >carried on RWT forum seems to suggest that on modern CPUs branchless >variant is faster even when the table does not fit in LLC.=20

Only two explanations come to my mind:

1) The M3 has a hardware prefetcher that recognizes the pattern of a
binary array search and prefetches accordingly. The cache misses from
page table accesses might confuse the prefetcher, leading to worse performance eventually.

Coffee Lake certainly has no such prefetcher and nevertheless exhibits
similar behavior.

2) (doubtful) The compiler recognizes the algorithm and inserts
software prefetch instructions.

Branchy variant manages to pull ahead only when TLB misses can't be
served from L2$.
At least that how I interpreted it.

Here is result on very modern CPU: >https://www.realworldtech.com/forum/?threadid=3D223776&curpostid=3D223974

And here is older gear: >https://www.realworldtech.com/forum/?threadid=3D223776&curpostid=3D223895

I tried to run your code <https://www.realworldtech.com/forum/?threadid=223776&curpostid=223955>
on Zen4, but clang-14 converts uut2.c into branchy code. I could not
get gcc-12 to produce branchless code from slightly adapted source
code, either. My own attempt of using extended asm did not pass your
sanity checks, so eventually I used the assembly code produced by
clang-19 through godbolt.

I suppose that you have good reason for avoiding installation of clang17
or later on one of your computers.

Here I see that branchy is faster for the
100M array size on Zen4 (i.e., where on the M3 branchless is faster):

[~/binary-search:165562] perf stat branchless 100000000 10000000 10 4041.093082 msec. 0.404109 usec/point
Performance counter stats for 'branchless 100000000 10000000 10':

45436.88 msec task-clock 1.000 CPUs utilized
276 context-switches 6.074 /sec
0 cpu-migrations 0.000 /sec
1307 page-faults 28.765 /sec 226091936865 cycles 4.976 GHz
1171349822 stalled-cycles-frontend 0.52% frontend cycles idle 34666912723 instructions 0.15 insn per cycle
0.03 stalled cycles per insn
5829461905 branches 128.298 M/sec
45963810 branch-misses 0.79% of all branches


45.439541729 seconds time elapsed

45.397207000 seconds user
0.040008000 seconds sys

[~/binary-search:165563] perf stat branchy 100000000 10000000 10
3051.269998 msec. 0.305127 usec/point
Performance counter stats for 'branchy 100000000 10000000 10':

34308.48 msec task-clock 1.000 CPUs utilized
229 context-switches 6.675 /sec
0 cpu-migrations 0.000 /sec
1307 page-faults 38.096 /sec 172472673652 cycles 5.027 GHz
49176146462 stalled-cycles-frontend 28.51% frontend cycles idle 33346311766 instructions 0.19 insn per cycle
1.47 stalled cycles per insn
10322173655 branches 300.864 M/sec
1583842955 branch-misses 15.34% of all branches


34.311432848 seconds time elapsed

34.264437000 seconds user
0.044005000 seconds sys

If you have recommendations what to use for the other parameters, I
can run other sizes as well.

- anton

Run for every size from 100K to 2G in increments of x sqrt(2).
BTW, I prefer odd number of iterations.
The point at which majority of look-ups misses L3$ at least once
hopefully will be seen as change of slop on log(N) vs duration
graph for branchless variant.
I would not bother with performance counters. At least for me they
bring more confusion than insite.

According to my understanding, on Zen4 the ratio of main DRAM
latency to L3 latency is much higher than on either Coffee Lake or M3,
both of which have unified LLC instead of split L3$.
So, if on Zen2 branchy starts to win at ~2x L3 size, I will not be
shocked. But I will be somewhat surprised.

I actually have access to Zen3-based EPYC, where the above mentioned
ratio is supposed much bigger than on any competent client CPU (Intel's Lunar/Arrow Lake do not belong to this category) but this server is
currently powered down and it's a bit of a hassle to turn it on.


--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/21/2026 8:18 AM, Anton Ertl wrote:

big snip

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

It is probably useful to distinguish between latency bound and bandwidth bound. An example of each -

Many occur in commercial (i.e. non scientific) programs, such as
database systems. For example, imagine a company employee file (table),
with a (say 300 byte) record for each of its many thousands of employees
each containing typical employee stuff). Now suppose someone wants to
know "What is the total salary of all the employees in the "Sales"
department. With no index on "department", but it is at a fixed
displacement within each record, the code looks at each record, does a
trivial test on it, perhaps adds to a register, then goes to the next
record. This it almost certainly memory latency bound.

For a memory bandwidth bound example, consider comparing two large text documents for equality.
--
- Stephen Fuld
(e-mail address disguised to prevent spam)
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <10ngao4$d5o$1@gal.iecc.com>, johnl@taugh.com (John Levine)
wrote:

I gather speculative execution of both branch paths worked OK if the
branch tree wasn't too bushy. There were certainly ugly details,
e.g., if there's a trap on a path that turns out not to be taken.

Found a good CPU bug like that on an old AMD chip, the K6-II.

It happened with a floating point divide by zero in the x87 registers,
guarded by a test for division by zero, with floating-point traps enabled.
The divide got speculatively executed, the trap was stored, the test
revealed the divide would be by zero, the CPU tried to clean up, hit its
bug, and just stopped. Power switch time.

This only happened with the reverse divide instruction, which took the
operands off the x87 stack in the opposite order from the usual FDIV. It
was rarely used, so the bug didn't become widely known. But Microsoft's compiler used it occasionally.

John
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

IA-64 was to prevent AMD (and others) from clones--that is all. Intel/HP would have had a patent wall 10 feet tall.

It did not fail by being insufficiently protected, it failed because it
did not perform.

What did they (try to) patent?

-----------------

For a few cases, they have. But the problem is that these cases are
also vectorizable.

Their major problem was that they did not get enough ILP from
general-purpose code.

And even where they had enough ILP, OoO CPUs with SIMD extensions ate
their lunch.

And that should have been the end of the story. ... Sorry Ivan.

Things have been very quiet there. The last post in their
forum talks about the Mill trying to get to the same level as
Intel/AMD with Coremark, and they say they are going to go to
other microbenchmarks, where the Mill is supposed to be better.

I'm not sure...
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/18/26 3:45 PM, BGB wrote:

On 2/16/2026 3:14 PM, Paul Clayton wrote:

On 11/5/25 2:00 AM, BGB wrote:

On 11/4/2025 3:44 PM, Terje Mathisen wrote:

MitchAlsup wrote:

anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:

[snip]

Branch prediction is fun.

When I looked around online before, a lot of stuff about
branch prediction was talking about fairly large and
convoluted schemes for the branch predictors.

You might be interested in looking at the 6th Championship
Branch Prediction (2025): https://ieeetcca.org/2025/02/18/6th-
championship-branch-prediction-cbp2025/

Quick look, didn't see much information about who entered or won...

This presentation (PDF) presents the winners: https://ericrotenberg.wordpress.ncsu.edu/files/2025/06/CBP2025-Closing-Remarks.pdf

1st Place: Toru Koizumi et al.'s "RUNLTS: Register-value-aware
predictor Utilizing Nested Large TableS"
PDF of paper: https://ericrotenberg.wordpress.ncsu.edu/files/2025/06/cbp2025-final44-Koizumi.pdf


2nd Place: André Seznec's "TAGE-SC for CBP2025"
PDF of paper: https://ericrotenberg.wordpress.ncsu.edu/files/2025/06/cbp2025-final37-Seznec.pdf

3rd Place: Yang Man, el. al's "LVCP: A Load-Value Correlated
Predictor for TAGE-SC-L"
PDF of paper: https://ericrotenberg.wordpress.ncsu.edu/files/2025/06/cbp2025-final15-Man.pdf

The program lists the competitors and provides links to papers,
presentations, video, and code: https://ericrotenberg.wordpress.ncsu.edu/cbp2025-workshop-program/

I probably should have provided the link to the program to save
any readers time and effort. (I had not remembered how many link
traversals were required and just picked a url from my Firefox
history.)

(One nice aspect of this workshop/competition is that one can
reproduce the results and try one's own designs. As long as one
can trust that the traces are representative of the workloads
one cares about, this seems significant.)

TAgged GEometric length predictors (TAGE) seem to the current
"hotness" for branch predictors. These record very long global
histories and fold them into shorter indexes with the number of
history bits used varying for different tables.

(Because the correlation is less strong, 3-bit counters are
generally used as well as a useful bit.)

When I messed with it, increasing the strength of the saturating
counters was not effective.

But, increasing the ability of them to predict more complex
patterns did help.

Branch prediction is heuristic and the tradeoffs change based on
the workload and the storage (and latency) budget.

Saturating counters record localized bias not a pattern, so
fuzzy behavior might be more accurately predicted on average
while (as you noted) repeated patterns are less likely to be
predicted accurately.

Larger counters can even out some irregularity in the bias but
increase training time. (With tags, a new entry can be
initialized to a decent state, which can reduce training time.)

For per-address prediction, there are ways of reducing the
overhead for tagging each entry. If a branch target buffer (BTB)
is used, one is already storing a target address (or at least an
offset/cache index) so adding some tag bits is not quite as
expensive and allows associativity; placing a per-address
prediction in a BTB was a common design. Per-address predictions
can also be associated with the Icache, in which case they can
reuse the Icache tagging. Tagging reduces aliases, but obviously
bits spent on tags cannot be spent on prediction entries
themselves (fewer entries means evictions that reduce training
time).

Aliasing is a major issue even with per-address prediction; with
global branch history aliasing is even more likely. Several
techniques have been proposed (besides tagging) to reduce
aliasing such as multiple diversely indexed predictors with a
majority vote. (The never manufactured Alpha 21464 design used
three differently indexed tables to produce a majority vote and
a fourth table to choose whether to use the majority vote or the
prediction form a specific table. See "Design Tradeoffs for the
Alpha EV8 Conditional Branch Predictor" for details.)

(Mitch Alsup would, of course, mention his agree predictor which
uses a second source such as a per-address prediction or a
static prediction to exploit that predictions are likely to
agree with their local prediction and two branches that use the
same index could have different direction biases. In addition,
if the global predictor is used as a complement to a per-address
predictor, different branches with the same global index may be
likely to disagree with a per-address predictor.)

Capacity issues can be so significant that for some workloads
single bit predictors outperform two-bit counters. Predicting
more static (per-address) branches somewhat accurately can be
more important than predicting fewer branches more accurately.

Counters also have the minor advantage of providing a confidence
estimate that can be used for things like prediction selection,
checkpoint selection (doing a renaming snapshot to speed
misprediction recovery), dynamic predication, prefetch
throttling, or execution throttling (to save power/energy).

But, then always at the end of it using 2-bit saturating
counters:
   weakly taken, weakly not-taken, strongly taken, strongly
not taken.

But, in my fiddling, there was seemingly a simple but
moderately effective strategy:
   Keep a local history of taken/not-taken;
   XOR this with the low-order-bits of PC for the table index;
   Use a 5/6-bit finite-state-machine or similar.
     Can model repeating patterns up to ~ 4 bits.

Indexing a predictor by _local_ (i.e., per instruction address)
history adds a level of indirection; once one has the branch
(fetch) address one needs to index the local history and then
use that to index the predictor.

[snip]

OK, seems I wrote it wrong:
I was using a global branch history.

The terminology can be tricky. The worst is probably the
difference between bimode and bimodal; for former is a similar
to agree prediction in attempting to separate bias, the latter
is a name for per-address prediction (two modes, taken or not
taken).

But, either way, the history is XOR'ed with the relevant bits
from PC to generate the index.

This is called a gshare predictor as distinguished from a
gselect predictor which indexes with just the global history.
(There is also a distinction of path history — address bits
rather than taken/not-taken — and global branch history.) As you
probably discovered in your experimentation, hashing in the
address bits provides significantly better prediction.

I do not know if 5/6-bit state machines have been academically
examined for predictor entries. I suspect the extra storage is a
significant discouragement given one often wants to cover more
different correlations and branches.

If the 5/6-bit FSM can fit more patterns than 3x 2-bit
saturating counters, it can be a win.

I suspect it very much depends on whether bias or pattern is
dominant. This would depend on the workload (Doom?) and the
table size (and history length). I do not know that anyone in
academia has explored this, so I think you should be proud of
your discovery even if it has limited application.

A larger table (longer history) can mean longer training, but
such also discovers more patterns and longer patterns (e.g.,
predicting a fixed loop count). However, correlation strength
tends to decrease with increasing distance (having multiple
history lengths and hashings helps to find the right history).

As noted, the 5/6 bit FSM can predict arbitrary 4 bit patterns.

When the pattern is exactly repeated this is great, but if the
correlation with global history is fuzzy (but biased) a counter
might be better.

I get the impression that branch prediction is complicated
enough that even experts only have a gist of what is actually
happening, i.e., there is a lot of craft and experimentation and
less logical derivation (I sense).

With the PC XOR Hist, lookup, there were still quite a few
patterns, and not just contiguous 0s or 1s that the saturating
counter would predict, nor just all 0s, all 1s, or ...101010...
that the 3-bit FSM could deal with.

But, a bigger history could mean less patterns and more
contiguous bits in the state.

TAGE has the advantage that the tags reduce branch aliases and
the variable history length (with history folding/compression)
allows using less storage (when a prediction only benefits from
a shorter history) and reduces training time.

In my case, was using 6-bit lookup mostly to fit into LUT6 based
LUTRAM.

Going bigger than 6 bits here is a pain point for FPGAs, more so
as BRAM's don't support narrow lookups, so the next size up
would likely be 2048x but then inefficiently using the BRAM
(there isn't likely a particularly good way to make use of 512x
18-bits).

Presumably selecting specific bits of the 18 (shifting/alignment
network) is expensive in an FPGA? With more bits per index, it
might also make sense to use associativity with partial tags. It
might be practical with two-way associativity to use different
numbers of tag bits (with different address hashings) in
different ways and different state sizes.

[snip]

Local history patterns may also be less common that statistical
correlation after one has extracted branches predicted well by
global history. (For small-bodied loops, a moderately long
global history provides substantial local history.)

It seems what I wrote originally was inaccurate, I don't store a
history per-target, merely it was recent taken/not-taken branches.

Well, I mixed up way and set in one of my comp.arch postings,
and this was after (if I recall correctly) having read Computer
Architecture: A Quantitative Approach as well as more than a
couple of papers and web articles and comp.arch postings.

But, I no longer remember what I was thinking at the time, or
why I had written local history rather than global history
(unless I meant "local" in terms of recency or something, I
don't know).

"Local" is not really a good term for per-address because of the
potential confusion with temporal locality and the generality (a
local branch prediction is not about predicting branches with
nearby addresses — I am skeptical that there is much "spatial
locality" for branch direction).

(Terminology in computer architecture is not very well
organized, consistent, or insightful. I feel "Instruction
Pointer" is a better term than "Program Counter" and
"Translation Cache" is a better term than "Translation Lookaside
Buffer"; the former is still strong because of x86, but the
latter had Itanium as a "backer"☹. In terms of historical
precedence, "elbow cache" should be preferred for a cache that
uses different indexing methods to find an alternative index for
an evicted block rather than "cuckoo cache" which seems more
evocative and was used for hash tables. Then there is "block"
(IBM) versus "line" (Intel) and whether a "sector" is larger or
smaller than a line/block and what pipeline stage is "issue" and
which "dispatch".)

[snip]

A lot of this seems a lot more complex though than what would be
all that practical on a Spartan or Artix class FPGA.

Modern high performance branch predictors are huge! The branch
prediction section for AMD's Zen 4 is larger than the
instruction cache and is close to the size of (possibly larger
than) the instruction cache and decode sections: https://substackcdn.com/image/fetch/$s_!Ak84!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F9d037035-aad5-4ff5-931b-c51f0409e9f3_787x378.jpeg
(from the Chips & Cheese article "Zen 5’s 2-Ahead Branch
Predictor Unit: How a 30 Year Old Idea Allows for New Tricks" https://chipsandcheese.com/p/zen-5s-2-ahead-branch-predictor-unit-how-30-year-old-idea-allows-for-new-tricks
)

I was mostly using 5/6 bit state machines as they gave better
results than 2-bit saturating counters, and fit nicely within
the constraints of a "history XOR PC" lookup pattern.

I think it is very neat that you were experimenting with such.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/19/26 6:10 PM, John Dallman wrote:
[snip]

On 2/19/26 6:04 PM, BGB wrote:

In a way, it showed that they screwed up the design pretty hard
that x86-64 ended up being the faster and more efficient option...

They did. They really did.

I guess one question is if they had any other particular drawbacks
other than, say:
Their code density was one of the worst around;
128 registers is a little excessive;
128 predicate register bits is a bit WTF;

Those huge register files had a lot to do with the low code density. They
had two much bigger problems, though.

The large register count seems to have been a result of both the
integer-side register stack idea — if one is going to lazily
save registers one might as well be able to use those registers
within a single function — and the rejection of pipeline-
dependent binaries where a result does not use a register name
until the result is produced (Itanium code was defined to be
executable by single stepping through operations).

The hidden pipeline architectural choice also seems to have
meant that operations using the results of non-single-cycle
operations have to check for availability. Since the register
number does not communicate the latency, all register sources
would have to check a scoreboard-like structure (I think).

(The Mill at least recognized that compiling a distribution
format to work on the specific pipeline makes sense for static
scheduling.)

Loop unrolling combined with software pipelining presumably also
motivated larger register files.

The lack of base+immediate addressing — to avoid address
generation latency when not necessary — also hurt code density
even though one could sometimes use post-increment addressing to
generate a later-used address. This probably also tended to
increase register use as two parallel address computations would
have to have different destination registers.

The template system also seems to have bloated the code,
introducing unnecessary nops. This is also a consequence of not
exposing the pipeline; with an exposed microarchitecture the
encoding of instruction routing could be simplified.

They'd correctly understood that the low speed of affordable dynamic RAM
as compared to CPUs running at hundreds of MHz was the biggest barrier to making code run fast. Their solution was have the compiler schedule loads well in advance. They assumed, without evidence, that a compiler with
plenty of time to think could schedule loads better than hardware doing
it dynamically. It's an appealing idea, but it's wrong.

They had 'evidence'. From the Oral history of Robert P. Colwell:

| He said, well that's true we don't have a compiler yet, so I
| hand assembled my simulations. I asked "How did you do
| thousands of line of code that way?" He said “No, I did 30
| lines of code”. Flabbergasted, I said, "You're predicting the
| entire future of this architecture on 30 lines of hand
| generated code?"

That oral history has a lot of pieces that pointed to major
organizational issues (e.g., the two people with VLIW experience
at Intel were not involved in the project, not even for initial
consultation).

One implementation flaw (in my opinion) for Itanium 2 was the
use of peak register file ports. With in-order execution and a
decent compiler there should be (I suspect/feel) very few cases
where ILP is hurt by substantially reducing the register file
port count (relying on forwarding, immediates, etc. to reduce
demand for register reads). For the FP-side, the architecture
already implied two-wide banking for load-pair which were
required to be even/odd pairs even with rotation. Even without
expensive optimization, register file banking might have reduced
port demand for such wide execution without much if any ILP
loss.

(I admit my feeling about register file ports is just a feeling,
but it would have been fairly easy to test whether much existing
code suffered lower ILP from having, e.g., only 8 read ports
instead of 12.)

I suspect an exposed pipeline architecture might also allow a
compiler to schedule result forwarding such that a full all-to-
all network might be avoided.

It might be possible to do that effectively in a single-core,
single-thread, single-task system that isn't taking many (if any)
interrupts. In a multi-core system, running a complex operating system, several multi-threaded applications, and taking frequent interrupts and context switches, it is _not possible_. There is no knowledge of any of
the interrupts, context switches or other applications at compile time,
so the compiler has no idea what is in cache and what isn't. I don't understand why HP and Intel didn't realise this. It took me years, but I
am no CPU designer.

For simple interrupts, the 16 "banked" GPRs (similar to ARM's
fast interrupt limited register set) might have been enough to
avoid having to save the context for most interrupts. I would
have guessed that 32 GPRs, to match the static (not
rotating/stacked) GPRs would have been better, particularly with
the 3D register file mechanism to hide the area cost under the
wires of a highly ported register file, which mechanism was used
for the multithreaded Itanium. On the other hand, to use so many
registers for interrupt handling, it might have been necessary
to provide a static-only calling convention.

I suspect context switches were expected to be rare. If one is
chasing ILP to the maximum extent, Thread-Level Parallelism may
be ignored. Even at a low bandwidth 32-bytes per cycle, a
context swap would take (I think) less than 150 cycles; with 1
GHz frequency and 1 ms OS time slice this would be 0.015% of a
time slice used by context switch overhead. If the extra state
allowed the program to run even a tiny bit faster, that overhead
would not be significant.

System calls that cannot be run entirely in the banked registers
might be more frequent than time slice thread switches, and
blocking system calls would result in more thread switches. Yet
it is not obvious to me that the context switch overhead was
necessarily a major roadblock to system performance.

There are other reasons (besides code density) to keep the most
active set of data small, e.g., storage area and access power.

Speculative execution addresses that problem quite effectively. We don't
have a better way, almost thirty years after Itanium design decisions
were taken. They didn't want to do speculative execution, and they close
an instruction format and register set that made adding it later hard. If
it was ever tried, nothing was released that had it AFAIK.

The other problem was that they had three (or six, or twelve) in-order pipelines running in parallel. That meant the compilers had to provide
enough ILP to keep those pipelines fed, or they'd just eat cache capacity
and memory bandwidth executing no-ops ... in a very bulky instruction set. They didn't have a general way to extract enough ILP. Nobody does, even
now. They just assumed that with an army of developers they'd find enough heuristics to make it work well enough. They didn't.

There was also an architectural misfeature with floating-point advance
loads that could make them disappear entirely if there was a call
instruction between an advance-load instruction and the corresponding check-load instruction.

Was this really architectural in terms of initial design intent
or a "won't fix" bug that became a de facto architectural
feature? Based on the special case nature and your calling it a
bug, I am guessing the latter (which I would tend to view as
worse).

By the way, the Mill has, in my opinion, a better design for
hoisted loads. The loads are not speculative (though they can
return a not-a-thing result) and the state is saved on function
calls. The variable latency loads do require a second load
commit operation, but a "fixed" latency load could be, e.g., two
cycles after a function call return (which is a highly variable
actual latency). I think a better design is possible when
targeting out-of-order execution. A hoisted load can be
automatically reissued so the hardware does not have to track
all of the "active" loads.

If I recall correctly, Itanium required holding the destination
register unused for the duration of the load operation (so very
long hoisting of many loads would be expensive). Itanium also
did not distinguish between thread-local load speculation (which
could ignore cache snooping traffic) and speculation across
threads. (If Itanium had been designed for TLP, it might have
included transactional memory.)

That cost me a couple of weeks working out and
reporting the bug, which was unfixable. The only work-around was to
re-issue all outstanding all floating-point advance-load instruction
after each call returned. The effective code density went down further,
and there were lots of extra read instructions issued.

I guess it is more of an open question of what would have happened,
say, if Intel had gone for an ISA design more like ARM64 or RISC-V
or something.

ARM64 seems to me to be the product of a lot more experience with speculatively-executing processors than was available in 1998.

ARM64 is a little conservative/traditional (e.g., no variable-
length encoding), but it was also a product of experience and
some familiarity with compilers and hardware design. Since it is
intended for in-order cores as well, it is not explicitly
designed for speculative execution or even superscalar
execution.

RISC-V has
not demonstrated really high performance yet, and it's been around long enough that I'm starting to doubt it ever will.

I do not think there is anything technically preventing RISC-V
from having a high performance implementation; it is in some
ways substantially more sane than x86. However, high performance
processor design is expensive.

Look at how slow ARM is in gaining server market share even for
cloud computing dominated by open source software. If it was not
for Apple, one might well doubt that a fast ARM implementation
was possible.

I get the impression that ARM, the company, emphasizes design
flexibility over design efficiency. I doubt a pipeline can be
optimized to support, e.g., 32 KiB and 64 KiB L1 caches.

I do not know how much efficiency AMD sacrifices with its shrunk
low-frequency cores; perhaps the tools are good enough that
almost all of the optimization opportunities are automated. I
*guess* it is more the case that the savings from reduced
frequency targets are so large that even a 10% loss of
efficiency would not be problematic.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

John Dallman wrote:

In article <10ngao4$d5o$1@gal.iecc.com>, johnl@taugh.com (John Levine)
wrote:

I gather speculative execution of both branch paths worked OK if the
branch tree wasn't too bushy. There were certainly ugly details,
e.g., if there's a trap on a path that turns out not to be taken.

Found a good CPU bug like that on an old AMD chip, the K6-II.

It happened with a floating point divide by zero in the x87 registers, guarded by a test for division by zero, with floating-point traps enabled. The divide got speculatively executed, the trap was stored, the test
revealed the divide would be by zero, the CPU tried to clean up, hit its
bug, and just stopped. Power switch time.

This only happened with the reverse divide instruction, which took the operands off the x87 stack in the opposite order from the usual FDIV. It
was rarely used, so the bug didn't become widely known. But Microsoft's compiler used it occasionally.

Still an impressive find!

I can see that since it would be (almost?) 100% reproducible, you could
bisect the executable (in a debugger) to hone in on where it froze?

Trying to single-step up to the crash would negate the required
speculation, right?

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

The recent comparisons of branchy vs branchless binary search that we
carried on RWT forum seems to suggest that on modern CPUs branchless
variant is faster even when the table does not fit in LLC.=20

Only two explanations come to my mind:

1) The M3 has a hardware prefetcher that recognizes the pattern of a
binary array search and prefetches accordingly. The cache misses from
page table accesses might confuse the prefetcher, leading to worse
performance eventually.

Coffee Lake certainly has no such prefetcher and nevertheless exhibits >similar behavior.

I have now looked more closely, and the npoints parameter has a
significant influence. If it is small enough, branchless fits into
caches while branchy does not (see below), which might be one
explanation for the results. Given that I have not seen npoints
specified in any of the postings that mention branchless winning for
veclen sizes exceeding the L3 cache size, it could be this effect. Or
maybe some other effect. Without proper parameters one cannot
reproduce the experiment to investigate it.

I tried to run your code
<https://www.realworldtech.com/forum/?threadid=223776&curpostid=223955>
on Zen4, but clang-14 converts uut2.c into branchy code. I could not
get gcc-12 to produce branchless code from slightly adapted source
code, either. My own attempt of using extended asm did not pass your
sanity checks, so eventually I used the assembly code produced by
clang-19 through godbolt.

I suppose that you have good reason for avoiding installation of clang17
or later on one of your computers.

Sure. It costs time.

If you have recommendations what to use for the other parameters, I
can run other sizes as well.

- anton

Run for every size from 100K to 2G in increments of x sqrt(2).

There is no integer n where 2G=100k*sqrt(2)^n. So I used the numbers
shown below. You did not give any indication on npoints, so I
investigated myself, and found that branchless will miss the L3 cache
with npoints=100000, so I used that and used reps=200.

BTW, I prefer odd number of iterations.

You mean odd reps? Why?

Anyway, here are the usec/point numbers:

Zen4 8700G Tiger Lake 1135G7
veclen branchless branchy branchless branchy
100000 0.030945 0.063620 0.038220 0.080542
140000 0.031035 0.068244 0.034315 0.084896
200000 0.038302 0.073819 0.045602 0.089972
280000 0.037056 0.079651 0.042108 0.096271
400000 0.046685 0.081895 0.055457 0.104561
560000 0.043028 0.088356 0.055095 0.113646
800000 0.051180 0.092201 0.074570 0.123403
1120000 0.048806 0.096621 0.088121 0.142758
1600000 0.060206 0.101069 0.131099 0.172171
2240000 0.073547 0.115428 0.167353 0.205602
3200000 0.094561 0.139996 0.208903 0.234939
4500000 0.121049 0.162757 0.244457 0.268286
6400000 0.152417 0.178611 0.292024 0.295204
9000000 0.189134 0.192100 0.320426 0.327127
12800000 0.219408 0.208083 0.372084 0.353530
18000000 0.237684 0.222140 0.418645 0.389785
25000000 0.270798 0.236786 0.462689 0.415937
35000000 0.296994 0.254001 0.526235 0.451467
50000000 0.330582 0.268768 0.599331 0.478667
70000000 0.356788 0.288526 0.622659 0.522092
100000000 0.388326 0.305980 0.698470 0.562841
140000000 0.407774 0.321496 0.737884 0.609814
200000000 0.442434 0.336242 0.848403 0.654830
280000000 0.455125 0.356382 0.902886 0.729970
400000000 0.496894 0.372735 1.120986 0.777920
560000000 0.520664 0.393827 1.173606 0.855461
800000000 0.544343 0.412087 1.759271 0.901011
1100000000 0.584389 0.431854 1.862866 0.965724
1600000000 0.614764 0.455844 2.046371 1.027111
2000000000 0.622513 0.467445 2.149251 1.089775

So branchy surpasses branchless at veclen=12.8M on both machines, for npoints=100k.

Concerning the influence of npoints, I have worked with veclen=20M in
the following.

1) If <npoints> is small, for branchy the branch predictor will
learn the pattern on the first repetition, and predict correctly in
the following repetitions; on Zen4 and Tiger Lake I see the
following percentage of branch predictions (for
<npoints>*<rep>=20_000_000, <veclen>=20_000_000):

npoints Zen4 Tiger Lake
250 0.03% 0.51%
500 0.03% 10.40%
1000 0.03% 13.51%
2000 0.07% 13.84%
4000 13.45% 12.61%
8000 15.26% 12.31%
16000 15.56% 12.26%
32000 15.60% 12.23%
80000 15.59% 12.24%

Tiger Lake counts slightly more branches than Zen4 (for the same
binary): 1746M vs. 1703M, but there is also a real lower number of
mispredictions on Tiger Lake for high npoints; at npoints=80000:
214M on Tiger Lake vs. 266M on Zen4. My guess is that in Zen4 the
mispredicts of the deciding branch interfere with the prediction of
the loop branches, and that the anti-interference measures on Tiger
Lake results in the branch predictor being less effective at
npoints=500..2000.

2) If <npoints> is small all the actually accessed array elements
will fit into some cache. Also, even if npoints and veclen are
large enough that they do not all fit, with a smaller <npoints> a
larger part of the accesses will happen to a cache, and a larger
part to a lower-level cache. With the same parameters as above,
branchy sees on a Ryzen 8700G (Zen4 with 16MB L3 cache) the
following numbers of ls_any_fills_from_sys.all_dram_io
(LLC-load-misses and l3_lookup_state.l3_miss result in <not
supported> on this machine), and on a Core i5-1135G (Tiger Lake with
8MB L3) the following number of LLC-load-misses:

branchy branchless
8700G 1135G7 8700G 1135G7
npoints fills LLC-load-misses fills LLC-load-misses
250 1_156_206 227_274 1_133_672 39_212
500 1_189_372 19_820_264 1_125_836 47_994
1000 1_170_829 125_727_181 1_130_941 96_516
2000 1_310_015 279_063_572 1_173_501 299_297
4000 73_528_665 452_147_169 1_151_042 5_661_917
8000 195_883_759 501_433_404 1_248_638 58_877_208
16000 301_559_180 511_420_040 2_688_530 101_811_222
32000 389_512_147 511_713_759 29_799_206 116_312_019
80000 402_131_449 512_460_513 91_276_752 118_762_341

The 16MB L3 of the 8700G cache has 262_144 cache lines, the 8MB L3
of the 1135G7 has 131_072 cache lines. How come branchy has so many
cache misses already at relatively low npoints? Each search
performs ~25 architectural memory accesses; in addition, in branchy
we see a number of misspeculated memory accesses for each
architectural access, resulting in the additional memory accesses.

For branchless the 8700G sees a ramp-up of memory accesses more than
the factor of 2 later compared to the 1135G7 that the differences in
cache sizes would suggest. The 1135G7 cache is divided into 4 2MB
slices, and accesses are assigned by physical address (i.e., the L3
cache does not function like an 8MB cache with a higher
associativity), but given the random-access nature of this workload,
I would expect the accesses to be distributed evenly across the
slices, with little bad effects from this cache organization.

Given the memory access numbers of branchy and branchless above, I
expected to see a speedup of branchy in those cases where branchless
has a lot of L3 misses, so I decided to use npoints=100k and rep=200
in the experiments further up. And my expectations turned out to be
right, at least on these two machines.

- anton

The point at which majority of look-ups misses L3$ at least once
hopefully will be seen as change of slop on log(N) vs duration
graph for branchless variant.
I would not bother with performance counters. At least for me they
bring more confusion than insite.

According to my understanding, on Zen4 the ratio of main DRAM
latency to L3 latency is much higher than on either Coffee Lake or M3,
both of which have unified LLC instead of split L3$.
So, if on Zen2 branchy starts to win at ~2x L3 size, I will not be
shocked. But I will be somewhat surprised.

I actually have access to Zen3-based EPYC, where the above mentioned
ratio is supposed much bigger than on any competent client CPU (Intel's >Lunar/Arrow Lake do not belong to this category) but this server is
currently powered down and it's a bit of a hassle to turn it on.

--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Sun, 22 Feb 2026 13:17:30 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

Array and Matrix scientific codes with datasets bigger than
cache. =20

=20
The dense cases are covered by stride-based hardware predictors, so
they are not "otherwise". I am not familiar enough with sparse
scientific codes to comment on whether they are 1), 2), or
"otherwise".
=20

BLAS Level 3 is not particularly external/LLC bandwidth intensive
even without hardware predictors.

There are HPC applications that are bandwidth limited; that's why they
have the roofline performance model (e.g.,
<https://docs.nersc.gov/tools/performance/roofline/>).

Sure. But that's not what I would call "dense".
In my vocabulary "dense" starts at matmul(200x200,x200) or at LU >decomposition of matrix of similar dimensions.

"Dense matrices" vs. "sparse matrices", not in terms of FLOPS/memory
access.

So adding two dense matrices tends to be memory bandwidth bound, but stride-based prefetchers help to avoid getting any extra latency
beyond that coming from the bandwidth limits (if any).

Likewise, John McCalpin's Stream benchmark uses dense vectors IIRC,
but is memory bandwidth limited.

Overwhelming majority of data served from
L2 cache.
That's with classic SIMD. It's possible that with AMX units it's no
longer true.

I very much doubt that. There is little point in adding an
instruction that slows down execution by turning it from compute-bound
to memory-bound.

It does not slow down the execution. To the contrary, it speeds it up
so much that speed of handling of L2 misses begins to matter.
Pay attention that it's just my speculation that can be wrong.
IIRC, right now binary64-capable AMX is available only on Apple Silicon
(via SME) and may be on IBM Z. I didn't play with either.

AMX is an Intel extension of AMD64 (and IA-32); ARM's SME also has
"matrix" in its name, but is not AMX. Looking at <https://en.wikipedia.org/wiki/Advanced_Matrix_Extensions>, it seems
to me that the point of AMX is to deal with small matrices (16x64
times 64x16 for Int8, 16x32 times 32x16 for 16-bit types) of small
elements (INT8, BF16, FP16 and complex FP16 numbers) in a special
unit. Apparently the AMX unit in Granite Rapids consumes 2048 bytes
in 16 cycles, i.e., 128 bytes per cycle and produces 256 or 512 bytes
in these 16 cycles. If every of these matrix multiplication happens
happens on its own, the result will certainly be bandwidth-bound to L2
and maybe already to L1. If, OTOH, these operations are part of a
larger matrix multiplication, then cache blocking can probably lower
the bandwidth to L2 enough, and reusing one of the operands in
registers can lower the bandwidth to L1 enough.

In any case, Intel will certainly not add hardware that exceeds the
bandwidth boundaries in all common use cases.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

On 2/21/2026 8:18 AM, Anton Ertl wrote:

big snip

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

It is probably useful to distinguish between latency bound and bandwidth >bound.

If a problem is bandwidth-bound, then differences between conventional architectures and EPIC play no role, and microarchitectural
differences in the core play no role, either; they all have to wait
for memory.

For latency various forms of prefetching (by hardware or software) can
help.

Many occur in commercial (i.e. non scientific) programs, such as
database systems. For example, imagine a company employee file (table), >with a (say 300 byte) record for each of its many thousands of employees >each containing typical employee stuff). Now suppose someone wants to
know "What is the total salary of all the employees in the "Sales" >department. With no index on "department", but it is at a fixed >displacement within each record, the code looks at each record, does a >trivial test on it, perhaps adds to a register, then goes to the next >record. This it almost certainly memory latency bound.

If the records are stored sequentially, either because the programming
language supports that arrangement and the programmer made use of
that, or because the allocation happened in a way that resulted in
such an arrangement, stride-based prefetching will prefetch the
accessed fields and reduce the latency to the one due to bandwidth
limits.

If the records are stored randomly, but are pointed to by an array,
one can prefetch the relevant fields easily, again turning the problem
into a latency-bound problem. If, OTOH, the records are stored
randomly and are in a linked list, this problem is a case of
pointer-chasing and is indeed latency-bound.

BTW, thousands of employee records, each with 300 bytes, fit in the L2
or L3 cache of modern processors.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:

So adding two dense matrices tends to be memory bandwidth bound, but stride-based prefetchers help to avoid getting any extra latency
beyond that coming from the bandwidth limits (if any).

Likewise, John McCalpin's Stream benchmark uses dense vectors IIRC,
but is memory bandwidth limited.

CFD codes are usually memory bandwidth limited; they use sparse
matrices.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 24 Feb 2026 09:50:43 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

The recent comparisons of branchy vs branchless binary search
that we carried on RWT forum seems to suggest that on modern CPUs
branchless variant is faster even when the table does not fit in
LLC.=20

Only two explanations come to my mind:

1) The M3 has a hardware prefetcher that recognizes the pattern of
a binary array search and prefetches accordingly. The cache
misses from page table accesses might confuse the prefetcher,
leading to worse performance eventually.

Coffee Lake certainly has no such prefetcher and nevertheless
exhibits similar behavior.

I have now looked more closely, and the npoints parameter has a
significant influence. If it is small enough, branchless fits into
caches while branchy does not (see below), which might be one
explanation for the results. Given that I have not seen npoints
specified in any of the postings that mention branchless winning for
veclen sizes exceeding the L3 cache size, it could be this effect.

I think that it was said more than once throughout the thread that all measurements were taken with npoints=1M and rep=11.

Or
maybe some other effect. Without proper parameters one cannot
reproduce the experiment to investigate it.

I tried to run your code
<https://www.realworldtech.com/forum/?threadid=223776&curpostid=223955>
on Zen4, but clang-14 converts uut2.c into branchy code. I could
not get gcc-12 to produce branchless code from slightly adapted
source code, either. My own attempt of using extended asm did not
pass your sanity checks, so eventually I used the assembly code
produced by clang-19 through godbolt.

I suppose that you have good reason for avoiding installation of
clang17 or later on one of your computers.

Sure. It costs time.

If you have recommendations what to use for the other parameters, I
can run other sizes as well.

- anton

Run for every size from 100K to 2G in increments of x sqrt(2).

There is no integer n where 2G=100k*sqrt(2)^n. So I used the numbers
shown below. You did not give any indication on npoints, so I
investigated myself, and found that branchless will miss the L3 cache
with npoints=100000, so I used that and used reps=200.

BTW, I prefer odd number of iterations.

You mean odd reps? Why?

Because I like quick tests. Since I always use large npoints, for test
to finish quickly I have to use small rep. And for small rep
even-size median has non-negligible bias.

Anyway, here are the usec/point numbers:

Zen4 8700G Tiger Lake 1135G7
veclen branchless branchy branchless branchy
100000 0.030945 0.063620 0.038220 0.080542
140000 0.031035 0.068244 0.034315 0.084896
200000 0.038302 0.073819 0.045602 0.089972
280000 0.037056 0.079651 0.042108 0.096271
400000 0.046685 0.081895 0.055457 0.104561
560000 0.043028 0.088356 0.055095 0.113646
800000 0.051180 0.092201 0.074570 0.123403
1120000 0.048806 0.096621 0.088121 0.142758
1600000 0.060206 0.101069 0.131099 0.172171
2240000 0.073547 0.115428 0.167353 0.205602
3200000 0.094561 0.139996 0.208903 0.234939
4500000 0.121049 0.162757 0.244457 0.268286
6400000 0.152417 0.178611 0.292024 0.295204
9000000 0.189134 0.192100 0.320426 0.327127
12800000 0.219408 0.208083 0.372084 0.353530
18000000 0.237684 0.222140 0.418645 0.389785
25000000 0.270798 0.236786 0.462689 0.415937
35000000 0.296994 0.254001 0.526235 0.451467
50000000 0.330582 0.268768 0.599331 0.478667
70000000 0.356788 0.288526 0.622659 0.522092
100000000 0.388326 0.305980 0.698470 0.562841
140000000 0.407774 0.321496 0.737884 0.609814
200000000 0.442434 0.336242 0.848403 0.654830
280000000 0.455125 0.356382 0.902886 0.729970
400000000 0.496894 0.372735 1.120986 0.777920
560000000 0.520664 0.393827 1.173606 0.855461
800000000 0.544343 0.412087 1.759271 0.901011
1100000000 0.584389 0.431854 1.862866 0.965724
1600000000 0.614764 0.455844 2.046371 1.027111
2000000000 0.622513 0.467445 2.149251 1.089775

So branchy surpasses branchless at veclen=12.8M on both machines, for npoints=100k.

Concerning the influence of npoints, I have worked with veclen=20M in
the following.

1) If <npoints> is small, for branchy the branch predictor will
learn the pattern on the first repetition, and predict correctly in
the following repetitions; on Zen4 and Tiger Lake I see the
following percentage of branch predictions (for
<npoints>*<rep>=20_000_000, <veclen>=20_000_000):

npoints Zen4 Tiger Lake
250 0.03% 0.51%
500 0.03% 10.40%
1000 0.03% 13.51%
2000 0.07% 13.84%
4000 13.45% 12.61%
8000 15.26% 12.31%
16000 15.56% 12.26%
32000 15.60% 12.23%
80000 15.59% 12.24%

Tiger Lake counts slightly more branches than Zen4 (for the same
binary): 1746M vs. 1703M, but there is also a real lower number of
mispredictions on Tiger Lake for high npoints; at npoints=80000:
214M on Tiger Lake vs. 266M on Zen4. My guess is that in Zen4 the
mispredicts of the deciding branch interfere with the prediction of
the loop branches, and that the anti-interference measures on Tiger
Lake results in the branch predictor being less effective at
npoints=500..2000.

2) If <npoints> is small all the actually accessed array elements
will fit into some cache. Also, even if npoints and veclen are
large enough that they do not all fit, with a smaller <npoints> a
larger part of the accesses will happen to a cache, and a larger
part to a lower-level cache. With the same parameters as above,
branchy sees on a Ryzen 8700G (Zen4 with 16MB L3 cache) the
following numbers of ls_any_fills_from_sys.all_dram_io
(LLC-load-misses and l3_lookup_state.l3_miss result in <not
supported> on this machine), and on a Core i5-1135G (Tiger Lake
supported> with
8MB L3) the following number of LLC-load-misses:

branchy branchless
8700G 1135G7 8700G 1135G7
npoints fills LLC-load-misses fills LLC-load-misses
250 1_156_206 227_274 1_133_672 39_212
500 1_189_372 19_820_264 1_125_836 47_994
1000 1_170_829 125_727_181 1_130_941 96_516
2000 1_310_015 279_063_572 1_173_501 299_297
4000 73_528_665 452_147_169 1_151_042 5_661_917
8000 195_883_759 501_433_404 1_248_638 58_877_208
16000 301_559_180 511_420_040 2_688_530 101_811_222
32000 389_512_147 511_713_759 29_799_206 116_312_019
80000 402_131_449 512_460_513 91_276_752 118_762_341

The 16MB L3 of the 8700G cache has 262_144 cache lines, the 8MB L3
of the 1135G7 has 131_072 cache lines. How come branchy has so many
cache misses already at relatively low npoints? Each search
performs ~25 architectural memory accesses; in addition, in branchy
we see a number of misspeculated memory accesses for each
architectural access, resulting in the additional memory accesses.

For branchless the 8700G sees a ramp-up of memory accesses more than
the factor of 2 later compared to the 1135G7 that the differences in
cache sizes would suggest. The 1135G7 cache is divided into 4 2MB
slices, and accesses are assigned by physical address (i.e., the L3
cache does not function like an 8MB cache with a higher
associativity), but given the random-access nature of this workload,
I would expect the accesses to be distributed evenly across the
slices, with little bad effects from this cache organization.

Given the memory access numbers of branchy and branchless above, I
expected to see a speedup of branchy in those cases where branchless
has a lot of L3 misses, so I decided to use npoints=100k and rep=200
in the experiments further up. And my expectations turned out to be
right, at least on these two machines.

- anton

Intuitively, I don't like measurements with so smal npoints parameter,
but objectively they are unlikely to be much different from 1M points.
Looking at your results do not differ radically from those we do on
RWT forum.

CPU LLC Cross Point sz/LLC
TGL 8 12.8 12.8
CFL 12 30.0 15.0
Zen4 16 12.8 6.4
M3 24 200.0 66.7
RPT 33 1300.0 315.2

The last line is Intel Raptor Lake (i7-14700). On this CPU I had to use
1/3rd of installed memory in order to find a cross point.
Here at vecsize=41M, which is ten times bigger than LLC, branchless is
still almost 1.5x faster than branchy (0.216 vs 0.315 usec/point)

In all cases ratio of vector size at cross-point to LLC size is much
bigger than 1.
On Tiger Lake ratio is smaller than on others, probably because of
Intel's slow "mobile" memory controller, but even here it is
significantly above 1.

So far I don't see how your measurements disprove my theory of page
table not fitting in L2 cache.







--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/24/2026 3:25 AM, Anton Ertl wrote:

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

On 2/21/2026 8:18 AM, Anton Ertl wrote:

big snip

Otherwise what kind of common code do we have that is
memory-dominated? Tree searching and binary search in arrays come to
mind, but are they really common, apart from programming classes?

It is probably useful to distinguish between latency bound and bandwidth
bound.

If a problem is bandwidth-bound, then differences between conventional architectures and EPIC play no role, and microarchitectural
differences in the core play no role, either; they all have to wait
for memory.

For latency various forms of prefetching (by hardware or software) can
help.

Many occur in commercial (i.e. non scientific) programs, such as
database systems. For example, imagine a company employee file (table),
with a (say 300 byte) record for each of its many thousands of employees
each containing typical employee stuff). Now suppose someone wants to
know "What is the total salary of all the employees in the "Sales"
department. With no index on "department", but it is at a fixed
displacement within each record, the code looks at each record, does a
trivial test on it, perhaps adds to a register, then goes to the next
record. This it almost certainly memory latency bound.

If the records are stored sequentially, either because the programming language supports that arrangement and the programmer made use of
that, or because the allocation happened in a way that resulted in
such an arrangement, stride-based prefetching will prefetch the
accessed fields and reduce the latency to the one due to bandwidth
limits.

Let me better explain what I was trying to set up, then you can tell me
where I went wrong. I did expect the records to be sequential, and
could be pre-fetched, but with the inner loop so short, just a few instructions, I thought that it would quickly "get ahead" of the
prefetch. That is, that there was a small limit on the number of
prefetches that could be in process simultaneously, and with such a
small CPU loop, it would quickly hit that limit, and thus be latency bound.

If the records are stored randomly, but are pointed to by an array,
one can prefetch the relevant fields easily, again turning the problem
into a latency-bound problem. If, OTOH, the records are stored
randomly and are in a linked list, this problem is a case of
pointer-chasing and is indeed latency-bound.

BTW, thousands of employee records, each with 300 bytes, fit in the L2
or L3 cache of modern processors.

Yes, I miscalculated. My intent was to force a DRAM access for each
record, which would make the problem worse (DRAM access time versus L3
access time). But I think the same issue would apply, even it it fits
in an L3 cache, but if it doesn't, increase the record size or number of records so that it doesn't fit in L3. But this just changes the number
of prefetches in process needed to prevent it from becoming latency bound.

Thanks.
--
- Stephen Fuld
(e-mail address disguised to prevent spam)
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 24 Feb 2026 10:46:32 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Sun, 22 Feb 2026 13:17:30 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

MitchAlsup <user5857@newsgrouper.org.invalid> writes:

Array and Matrix scientific codes with datasets bigger than
cache. =20

=20
The dense cases are covered by stride-based hardware
predictors, so they are not "otherwise". I am not familiar
enough with sparse scientific codes to comment on whether they
are 1), 2), or "otherwise".
=20

BLAS Level 3 is not particularly external/LLC bandwidth intensive
even without hardware predictors.

There are HPC applications that are bandwidth limited; that's why
they have the roofline performance model (e.g.,
<https://docs.nersc.gov/tools/performance/roofline/>).

Sure. But that's not what I would call "dense".
In my vocabulary "dense" starts at matmul(200x200,x200) or at LU >decomposition of matrix of similar dimensions.

"Dense matrices" vs. "sparse matrices", not in terms of FLOPS/memory
access.

So adding two dense matrices tends to be memory bandwidth bound, but stride-based prefetchers help to avoid getting any extra latency
beyond that coming from the bandwidth limits (if any).

Likewise, John McCalpin's Stream benchmark uses dense vectors IIRC,
but is memory bandwidth limited.

Overwhelming majority of data served from
L2 cache.
That's with classic SIMD. It's possible that with AMX units it's
no longer true.

I very much doubt that. There is little point in adding an
instruction that slows down execution by turning it from
compute-bound to memory-bound.

It does not slow down the execution. To the contrary, it speeds it up
so much that speed of handling of L2 misses begins to matter.
Pay attention that it's just my speculation that can be wrong.
IIRC, right now binary64-capable AMX is available only on Apple
Silicon (via SME) and may be on IBM Z. I didn't play with either.

AMX is an Intel extension of AMD64 (and IA-32); ARM's SME also has
"matrix" in its name, but is not AMX.

Apple's extension was called AMX back when it was accessible only
through close-source library calls and had no instruction-level
documentation. Later on Apple pushed it through Arm's standardization
process and since than everybody call it SME. But it is the same thing.

Looking at
<https://en.wikipedia.org/wiki/Advanced_Matrix_Extensions>, it seems
to me that the point of AMX is to deal with small matrices (16x64
times 64x16 for Int8, 16x32 times 32x16 for 16-bit types) of small
elements (INT8, BF16, FP16 and complex FP16 numbers) in a special
unit. Apparently the AMX unit in Granite Rapids consumes 2048 bytes
in 16 cycles, i.e., 128 bytes per cycle and produces 256 or 512 bytes
in these 16 cycles. If every of these matrix multiplication happens
happens on its own, the result will certainly be bandwidth-bound to L2
and maybe already to L1. If, OTOH, these operations are part of a
larger matrix multiplication, then cache blocking can probably lower
the bandwidth to L2 enough, and reusing one of the operands in
registers can lower the bandwidth to L1 enough.

The question is not whether bandwidth from L2 to AMX is sufficient. It
is.
The interesting part is what bandwidth from LLC *into* L2 is needed in
scenario of multiplication of big matrices.
Supposedly 1/3rd of L2 is used for matrix A that stays here for very
long time, another 1/3rd holds matrix C that remains here for, say, 8 iterations and remaining 1/3rd is matrix B that should be reloaded on
every iteration. AMX increases the frequency at which we have to reload
B and C.
Assuming L2 = 2MB and square matrices , N = sqrt(2MB/8B/3) = 295,
rounded down to 288. Each step takes 288**3= 24M FMA operations. If
future AMX does 128 FMA per clock then the iteration take 188K clocks.
288**2 * 8B / 188K = 3.5 B/clock. That's easy for 1 AMX/L2 combo, but
very hard when you have 64 units like those competing on the same
LLC.
Yes, suggestion of 128 FMA/clock was exaggerated, but 64 is realistic
and 32 is an absolute minimum. Building double-precision capable AMX is
not worth the trouble if it can not do at least 32 FMAs.

In any case, Intel will certainly not add hardware that exceeds the
bandwidth boundaries in all common use cases.

- anton

I wouldn't be so sure.
In relatively recent history Intel released Knights Landing which was unbalanced to extreme. Neither instruction decoders nor register ports
nor caches were sufficient to feed its vector units at any workload
that even remotely resembled useful algorithm.










--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Tue, 24 Feb 2026 09:50:43 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

[...]

I think that it was said more than once throughout the thread that all >measurements were taken with npoints=1M and rep=11.

I obviously missed it, that's why I asked for the parameters earlier.

And for small rep
even-size median has non-negligible bias.

Even-size median is the arithmetic mean between the (n-1)/2-lowest and
the (n+1)/2-lowest result. What bias do you have in mind?

Here are the results with npoints=1M reps=11:

Zen4 8700G Tiger Lake 1135G7
veclen branchless branchy branchless branchy
100000 0.030187 0.063023 0.038614 0.081332
140000 0.029779 0.066112 0.034797 0.085259
200000 0.037532 0.072898 0.045945 0.090583
280000 0.036677 0.078795 0.042678 0.097386
400000 0.045777 0.084639 0.055256 0.104249
560000 0.043092 0.086424 0.055677 0.112252
800000 0.050325 0.091714 0.078172 0.123927
1120000 0.048855 0.095756 0.091508 0.141819
1600000 0.061101 0.099660 0.133560 0.168403
2240000 0.082970 0.113055 0.166363 0.205129
3200000 0.120834 0.137753 0.211253 0.235155
4500000 0.149028 0.160359 0.241716 0.268885
6400000 0.178675 0.177070 0.294336 0.294931
9000000 0.219919 0.195292 0.322921 0.326113
12800000 0.240604 0.209397 0.380076 0.352707
18000000 0.257400 0.224952 0.409813 0.388834
25000000 0.293160 0.239217 0.472999 0.413559
35000000 0.307939 0.257587 0.522223 0.450754
50000000 0.346399 0.271420 0.595265 0.478713
70000000 0.375525 0.286462 0.626350 0.516533
100000000 0.401462 0.305444 0.699097 0.555928
140000000 0.419590 0.322480 0.732551 0.611815
200000000 0.451003 0.337880 0.854034 0.647795
280000000 0.468193 0.359133 0.914159 0.729234
400000000 0.506300 0.372219 1.150605 0.773266
560000000 0.520346 0.390277 1.167567 0.851592
800000000 0.556292 0.412035 1.799293 0.899768
1100000000 0.572654 0.432598 1.861136 0.963649
1600000000 0.618735 0.450526 2.062255 1.026560
2000000000 0.629088 0.465219 2.132035 1.073728

Intuitively, I don't like measurements with so smal npoints parameter,
but objectively they are unlikely to be much different from 1M points.

It's pretty similar, but the first point where branchy is faster is
veclen=6.4M for the 8700G and still 12.8M for the 1135G7; on the
1135G7 the 6.4M and 9M veclens are pretty close for both npoints.

My current theory why the crossover is so late is twofold:

1) branchy performs a lot of misspeculated accesses, which reduce the
cache hit rate (and increasing the cache miss rate) already at
relatively low npoints (as shown in <2026Feb24.105043@mips.complang.tuwien.ac.at>), and likely also for
low veclen with high npoints. E.g., already npoints=4000 has a >2M
fills from memory on the 8700G, and npoints=500 has >2M
LLC-load-misses at 1135G7, whereas the corresponding numbers for
branchless are npoints=16000 and npoints=4000. This means that
branchy does not just suffer from the misprediction penalty, but also
from fewer cache hits for the middle stages of the search. How strong
this effect is depends on the memory subsystem of the CPU core.

2) In the last levels of the larger searches the better memory-level parallelism of branchy leads to branchy catching up and eventually
overtaking branchless, but it has to first compensate for the slowness
in the earlier levels before it can reach crossover. That's why we
see the crossover point at significantly larger sizes than L3.

On Tiger Lake ratio is smaller than on others, probably because of
Intel's slow "mobile" memory controller

This particular machine has 8GB DDR4 soldered in plus 32GB DDR4 on a
separate DIMM, so the memory controller may be faultless.

So far I don't see how your measurements disprove my theory of page
table not fitting in L2 cache.

I did not try to disprove that; if I did, I would try to use huge
pages (the 1G ones if possible) and see how that changes the results.

But somehow I fail to see why the page table walks should make much of
a difference.

If I find the time, I would like to see how branchless with software prefetching performs. And I would like to put all of that, including
your code, online. Do I have your permission to do so?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 24 Feb 2026 17:30:31 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

If I find the time, I would like to see how branchless with software prefetching performs. And I would like to put all of that, including
your code, online. Do I have your permission to do so?

- anton

No problems.

--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/21/2026 4:56 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 2/21/2026 2:15 PM, MitchAlsup wrote:

BGB <cr88192@gmail.com> posted:

On 2/20/2026 5:49 PM, MitchAlsup wrote:

----------------------------

There is a non-zero risk though when one disallows uses that are
theoretically allowed in the ISA, even if GCC doesn't use them.

This is why one must decode all 32-bits of each instruction--so that
there is no hole in the decoder that would allow the core to do some-
thing not directly specified in ISA. {And one of the things that make
an industrial quality ISA so hard to fully specify.}}
---------------------

Sometimes there is a tension:
What is theoretically allowed in the ISA;
What is the theoretically expected behavior in some abstract model;
What stuff is actually used by compilers;
What features or behaviors does one want;
...

Whether your ISA can be attacked with Spectré and/or Meltdown;
Whether your DFAM can be attacked with RowHammer;
Whether your call/return interface can be attacked with:
{ Return Orienter Programmeing, Buffer Overflows, ...}

That is; whether you care if your system provides a decently robust programming environment.

I happen to care. Apparently, most do not.

There is a way at least, as noted, to optionally provide some additional protection against buffer overflows (in a compiler that does not use
stack canaries, eg, GCC).

But, as-noted, it disallows AUIPC+JALR to use X1 in this way.
Even if compiler output does generally use X5 for this case.

Implementing RISC-V strictly as per an abstract model would limit both
efficiency and hinder some use-cases.

One can make an argument that it is GOOD to limit attack vectors, and
provide a system that is robust in the face of attacks.

This was a partial motivation for deviating from the abstract model.

Deviating from the abstract model in some cases allows closing down
attack vectors.

Then it comes down to "what do compilers do" and "what unintentional
behaviors could an ASM programmer stumble onto unintentionally".

Nïeve at best.

Possibly, but there are some things a case can be made for disallowing:
Using X1 for things other than as a Link Register;
Disallowing JAL and JALR with Rd other than X0 or X1;
Disallowing most instructions, other than a few special cases, from
having X0 or X1 as a destination.

RISC-V has a lot of "Hint" instructions, but a case can be made for
making many of them illegal (where trying to use them will result in an exception; rather than simply ignoring them).

In some other cases, it may be justified to disallow (and generate an exception for) things which can be expressed in the ISA, technically,
but don't actually make sense for a program to make use of (some amount
of edge cases that result in NOPs, or sometimes non-NOP behaviors which
don't actually make sense); but are more likely to appear in undesirable
cases (such as the CPU executing random garbage as instructions).

...


Say, for example, the normal/canonical RISC-V NOP can't be expressed
without 0x00 (NUL) bytes, whereas many other HINT type instructions can
be encoded without NUL bytes.

If someone can't as easily compose a NUL-byte-free NOP-slide, it makes
it harder to inject shell code via ASCII strings (as does hindering the ability to tamper with return addresses), avoiding casual use of RWX
memory, etc.


The JAL/JALR Rd=X0|X1 only case, is one of those cases where one can
argue a use-case exists, but is so rarely used as to make its native
existence in hardware (or in an ISA design) difficult to justify. In
effect, supporting it in HW adds non-zero cost, programs don't actually
use it, and it burns 4 bits of encoding space you aren't really getting
back (and they could have used it for something more useful, say, making
JAL has a 16MB range or something).

While one can't change the encoding now, they can essentially just turn
the generic case into a trap and call it done.

...



Though. yes, even if one nails all this down, there are still often
other (nor-memory) attack vectors (such as attacking program logic).

Saw something not too long ago where there was an RCE exploit for some
random system (which operated via an HTTP servers and HTTP requests; I
think for "enterprise supply-chain stuff" or something), where the
exploit was basically the ability to execute arbitrary shell commands
via expressing them as an HTTP request (with said server effectively
running as "setuid root" or similar).

Or, basically, something so insecure that someone could (in theory) hack
it by typing specific URLs into a web browser or something (or maybe
using "wget" via a bash script).

Like, something like:
http : //someaddress/cgi-bin/system.cgi?cmd=sshd%20...
(Say, spawn an SSH server so they can stop using HTTP requests).
Leaving people to just ROFLOL about how bad it was...

And, how did the original product operate?... Mostly by sending
unsecured shell commands over HTTP.


So, alas...


--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Stephen Fuld <sfuld@alumni.cmu.edu.invalid> writes:

Let me better explain what I was trying to set up, then you can tell me >where I went wrong. I did expect the records to be sequential, and
could be pre-fetched, but with the inner loop so short, just a few >instructions, I thought that it would quickly "get ahead" of the
prefetch. That is, that there was a small limit on the number of
prefetches that could be in process simultaneously, and with such a
small CPU loop, it would quickly hit that limit, and thus be latency bound.

I think that it's bandwidth-bound, because none of the memory (or
outer-level cache) accesses depend on the results of previous ones; so
the loads can be started right away, up to the limit of memory-level parallelism of the hardware. If the records are in RAM, the hardware prefetcher can help to avoid running into the scheduler and ROB limits
of the OoO engine.

I have not looked closely at hardware prefetchers, but I am sure that
their designers have taken into account how far they have to prefetch
such that the loads they prefetch for usually see a short latency.

But prefetchers may not play a role anyway: A large number of (more
important) demand loads will probably suppress the prefetcher. But
that's no problem: modern uarchs tend to support enough outstanding
loads to utilize the full bandwidth available to the core. E.g., Zen4
has 64GB/s bandwidth from one core (actually one CCX) to the memory controllers, i.e., it can deliver 1 cache line/ns to the core from
RAM. It also has 88 entries in the load-execution queue, which are
good to cover 88*1ns=88ns of latency, which is roughly the latency one
sees from DDR5 DIMMs; with the higher-latency LPDDR5 a single core may
not be able to make use of all available latency.

If there are enough instructions between the loads such that the ROB
fills before the load-execution queue, demand loads may not be able to
fully utilize the bandwidth, but that leaves slots open for the
prefetcher, so the core will still make use of the available
bandwidth.

Of course, once you reach the bandwidth limit, loads that queue up
behind other loads for attention from the memory subsystem will see
more latency than in an uncongested memory system, but one does not
consider that to be latency-bound.

But that's all theoretical considerations; you could try to write a
program with these characteristics, and see how it performs.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Tue, 24 Feb 2026 10:46:32 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
The question is not whether bandwidth from L2 to AMX is sufficient. It
is.
The interesting part is what bandwidth from LLC *into* L2 is needed in >scenario of multiplication of big matrices.
Supposedly 1/3rd of L2 is used for matrix A that stays here for very
long time, another 1/3rd holds matrix C that remains here for, say, 8 >iterations and remaining 1/3rd is matrix B that should be reloaded on
every iteration. AMX increases the frequency at which we have to reload
B and C.
Assuming L2 = 2MB and square matrices , N = sqrt(2MB/8B/3) = 295,
rounded down to 288. Each step takes 288**3= 24M FMA operations. If
future AMX does 128 FMA per clock then the iteration take 188K clocks.
288**2 * 8B / 188K = 3.5 B/clock. That's easy for 1 AMX/L2 combo, but
very hard when you have 64 units like those competing on the same
LLC.

The 64 units are from 64 cores? I have not looked at the kind of
bandwidth that the 2D grid interconnect between the cores and their L3
cache slices offers to the cores of the big Xeons, but assuming that
the bandwidth is insufficient for that, one will probably buy a chip
with fewer cores if all that the cores are intended to do is to
multiply matrices.

Given that these cores are also used for applications other than
matrix multiplication, and for some of those it makes sense to have
that many cores (or more) even with that bandwidth limit to L3, I
cannot fault Intel for building such CPUs. And I also cannot fault
them for designing cores in a way that some hardware cannot be fully
utilized by some applications in some of the CPU configurations that
use that core. As long as there is an application where the hardware
can be fully utilized for some CPU configuration, and the additional
hardware benefits this application enough, the hardware feature
technically makes sense (for commercial sense additional
considerations apply).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 24 Feb 2026 17:30:31 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Tue, 24 Feb 2026 09:50:43 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Michael S <already5chosen@yahoo.com> writes:

On Mon, 23 Feb 2026 08:06:20 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

[...]

I think that it was said more than once throughout the thread that
all measurements were taken with npoints=1M and rep=11.

I obviously missed it, that's why I asked for the parameters earlier.

And for small rep
even-size median has non-negligible bias.

Even-size median is the arithmetic mean between the (n-1)/2-lowest and
the (n+1)/2-lowest result. What bias do you have in mind?

You had seen my code. It has no special handling for even nrep.
It simply takes dt[nrep/2], like in odd case.

Here are the results with npoints=1M reps=11:

Zen4 8700G Tiger Lake 1135G7
veclen branchless branchy branchless branchy
100000 0.030187 0.063023 0.038614 0.081332
140000 0.029779 0.066112 0.034797 0.085259
200000 0.037532 0.072898 0.045945 0.090583
280000 0.036677 0.078795 0.042678 0.097386
400000 0.045777 0.084639 0.055256 0.104249
560000 0.043092 0.086424 0.055677 0.112252
800000 0.050325 0.091714 0.078172 0.123927
1120000 0.048855 0.095756 0.091508 0.141819
1600000 0.061101 0.099660 0.133560 0.168403
2240000 0.082970 0.113055 0.166363 0.205129
3200000 0.120834 0.137753 0.211253 0.235155
4500000 0.149028 0.160359 0.241716 0.268885
6400000 0.178675 0.177070 0.294336 0.294931
9000000 0.219919 0.195292 0.322921 0.326113
12800000 0.240604 0.209397 0.380076 0.352707
18000000 0.257400 0.224952 0.409813 0.388834
25000000 0.293160 0.239217 0.472999 0.413559
35000000 0.307939 0.257587 0.522223 0.450754
50000000 0.346399 0.271420 0.595265 0.478713
70000000 0.375525 0.286462 0.626350 0.516533
100000000 0.401462 0.305444 0.699097 0.555928
140000000 0.419590 0.322480 0.732551 0.611815
200000000 0.451003 0.337880 0.854034 0.647795
280000000 0.468193 0.359133 0.914159 0.729234
400000000 0.506300 0.372219 1.150605 0.773266
560000000 0.520346 0.390277 1.167567 0.851592
800000000 0.556292 0.412035 1.799293 0.899768
1100000000 0.572654 0.432598 1.861136 0.963649
1600000000 0.618735 0.450526 2.062255 1.026560
2000000000 0.629088 0.465219 2.132035 1.073728

Intuitively, I don't like measurements with so smal npoints
parameter, but objectively they are unlikely to be much different
from 1M points.

It's pretty similar, but the first point where branchy is faster is veclen=6.4M for the 8700G and still 12.8M for the 1135G7; on the
1135G7 the 6.4M and 9M veclens are pretty close for both npoints.

Here are my Raptor Lake results (Raptor Cove and Gracemont)
i7-14700-P i7-14700-E
veclen branchless branchy branchless branchy
100000 0.025580 0.065588 0.055901 0.084580
140000 0.022006 0.067718 0.055513 0.088897
200000 0.029240 0.071393 0.066058 0.092738
280000 0.026032 0.074760 0.065444 0.096932
400000 0.034791 0.082914 0.076366 0.101067
560000 0.033920 0.089877 0.078420 0.107085
800000 0.046743 0.098518 0.086972 0.115900
1120000 0.045401 0.108028 0.088823 0.125935
1600000 0.059368 0.119298 0.112489 0.139820
2240000 0.060052 0.127647 0.121007 0.154747
3200000 0.081294 0.140325 0.151804 0.173241
4500000 0.090567 0.158380 0.169017 0.198011
6400000 0.134527 0.184986 0.221871 0.228213
9000000 0.139166 0.216010 0.247091 0.265844
12800000 0.158295 0.244137 0.314549 0.302832
18000000 0.198464 0.275680 0.342068 0.336601
25000000 0.232103 0.296431 0.425518 0.369543
35000000 0.249135 0.318954 0.431165 0.404154
50000000 0.291809 0.342103 0.537924 0.441044
70000000 0.312596 0.366850 0.548441 0.473681
100000000 0.366150 0.390468 0.672164 0.511968
140000000 0.365590 0.418052 0.684060 0.547667
200000000 0.414727 0.453255 0.814007 0.592588
280000000 0.470445 0.476864 0.841394 0.642071
400000000 0.497190 0.511605 0.975004 0.702385
560000000 0.524168 0.545820 1.006532 0.771940
800000000 0.555521 0.577105 1.178287 0.857243
900000000 0.587890 0.595592 1.197315 0.881594
1000000000 0.605113 0.605211 1.221586 0.901517
1100000000 0.582061 0.632543 1.228431 0.939851
1200000000 0.623949 0.641601 1.262782 0.953194
1300000000 0.653287 0.649376 1.283567 0.971780
1400000000 0.758616 0.651059 1.363853 0.990429
1500000000 0.675992 0.656111 1.387015 1.009316
1600000000 0.686154 0.680118 1.424667 1.025686
1700000000 0.692339 0.693832 1.428070 1.036490
1800000000 0.703114 0.694311 1.440372 1.054245
1900000000 0.693015 0.690148 1.446149 1.063155
2000000000 0.688864 0.714125 1.468993 1.088992

And here is Coffee Lake
Xeon E-2176G
veclen branchless branchy
100000 0.047010 0.091787
140000 0.045510 0.097623
200000 0.055983 0.104018
280000 0.055245 0.109927
400000 0.067691 0.116034
560000 0.070107 0.121319
800000 0.082146 0.127841
1120000 0.086229 0.138181
1600000 0.111000 0.153429
2240000 0.120780 0.175006
3200000 0.151256 0.199086
4500000 0.164724 0.223560
6400000 0.202989 0.244470
9000000 0.215630 0.268854
12800000 0.268318 0.290898
18000000 0.281772 0.315263
25000000 0.340269 0.336805
35000000 0.350421 0.360242
50000000 0.426758 0.385225
70000000 0.432946 0.411350
100000000 0.509785 0.441351
140000000 0.528119 0.472827
200000000 0.618676 0.510482
280000000 0.643984 0.548418
400000000 0.747189 0.590660
560000000 0.782344 0.628088
800000000 0.897024 0.671247
900000000 0.911065 0.682892
1000000000 0.930987 0.692015
1100000000 0.920161 0.708865
1200000000 0.940487 0.718227
1300000000 0.966389 0.728277
1400000000 0.984855 0.737065
1500000000 1.025050 0.745294
1600000000 1.048256 0.756237
1700000000 1.064021 0.761571
1800000000 1.063617 0.765608
1900000000 1.068122 0.773536
2000000000 1.074109 0.778483

My current theory why the crossover is so late is twofold:

1) branchy performs a lot of misspeculated accesses, which reduce the
cache hit rate (and increasing the cache miss rate) already at
relatively low npoints (as shown in <2026Feb24.105043@mips.complang.tuwien.ac.at>), and likely also for
low veclen with high npoints. E.g., already npoints=4000 has a >2M
fills from memory on the 8700G, and npoints=500 has >2M
LLC-load-misses at 1135G7, whereas the corresponding numbers for
branchless are npoints=16000 and npoints=4000. This means that
branchy does not just suffer from the misprediction penalty, but also
from fewer cache hits for the middle stages of the search. How strong
this effect is depends on the memory subsystem of the CPU core.

2) In the last levels of the larger searches the better memory-level parallelism of branchy leads to branchy catching up and eventually
overtaking branchless, but it has to first compensate for the slowness
in the earlier levels before it can reach crossover. That's why we
see the crossover point at significantly larger sizes than L3.

On Tiger Lake ratio is smaller than on others, probably because of
Intel's slow "mobile" memory controller

This particular machine has 8GB DDR4 soldered in plus 32GB DDR4 on a
separate DIMM, so the memory controller may be faultless.

Do you mean that dealing with two different types of memory is
objectively hard job?
Or that latency of 1135G7 is not to bad?
I can agree with the former, but not with the latter.
"Branchles" results for veclen in range 2M-10M that should be
good indication of latency of main RAM are just not good on
this gear. And slop of duration vs log(veclen) graph taken at this
range, which is probably even better indication of memory latency,
is also not good.
It all looks lake memory latency on this TGL is ~90ns, much higher than
the rest of them. That is, except for Gracemont, where very high
measured latency is probably cupped by some sort of power-saving policy
and not related to memory controller itself.

So far I don't see how your measurements disprove my theory of page
table not fitting in L2 cache.

I did not try to disprove that; if I did, I would try to use huge
pages (the 1G ones if possible) and see how that changes the results.

That sounds like an excellent idea.

But somehow I fail to see why the page table walks should make much of
a difference.

If I find the time, I would like to see how branchless with software prefetching performs. And I would like to put all of that, including
your code, online. Do I have your permission to do so?

- anton

Does not SW prefetch turn itself into NOP on TLB miss?
I remember reading something of that sort, but don't remember what CPU
was discussed.
Unfortunately, documentation rarely provide this sort of details.





--- Synchronet 3.21b-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <already5chosen@yahoo.com> writes:

On Tue, 24 Feb 2026 17:30:31 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

This particular machine has 8GB DDR4 soldered in plus 32GB DDR4 on a
separate DIMM, so the memory controller may be faultless.

Do you mean that dealing with two different types of memory is
objectively hard job?

I think that this setup is likely to provide less memory-level
parallelism, because probably 80% of the accesses go to only one DRAM
channel (on the 32GB DIMM), whereas on the 8700G the accesses
distribute evenly across 4 channels.

Or that latency of 1135G7 is not to bad?

I have not measured that before, let's see: Using bplat (pointer
chasing in a randomized cycle of pointers), I see for the 8700G
machine with DDR5-5200 and this 1135G7 machine the following
latencies (in ns):

size (B) 8700G 1135G7
1024 0.8 1.2
2048 0.8 1.2
4096 0.8 1.2
8192 0.8 1.2
16384 0.8 1.2
32768 0.8 1.2
65536 2.8 3.3
131072 2.8 3.4
262144 2.8 3.4
524288 3.6 4.2
1048576 4.5 5.0
2097152 10.0 11.9
4194304 10.4 14.6
8388608 10.3 34.9
16777216 25.1 72.9
33554432 77.4 90.4
67108864 86.8 93.6

So the main memory latency does not look much worse for the 1135G7
than for the 8700G. However, in <https://www.complang.tuwien.ac.at/anton/bplat/Results> there are a
number of machines with significantly better main memory latencies; interestingly, the best result comes from a Rocket Lake machine, a
close relative of the Tiger Lake in the 1135G7. So you may be right
about Intel's mobile memory controller configuration.

It all looks lake memory latency on this TGL is ~90ns

Right on target:-)

If I find the time, I would like to see how branchless with software
prefetching performs. And I would like to put all of that, including
your code, online. Do I have your permission to do so?

- anton

Does not SW prefetch turn itself into NOP on TLB miss?

I don't know. If the prefetch is for something that will actually be
fetched, a TLB miss would make the prefetch even more urgent.

What I expect is that a prefetch to a virtual address that cannot be
read becomes a noop. Of course, if you are a hardware engineer under
time pressure, you may take the shortcut of considering the absence
from the TLB to be an indication of unaccessability.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>
--- Synchronet 3.21c-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2/23/2026 4:17 PM, Paul Clayton wrote:

On 2/18/26 3:45 PM, BGB wrote:

snip, not feeling up to responding to everything at the moment.

So, for now, reevaluating things more narrowly.

I do not know if 5/6-bit state machines have been academically
examined for predictor entries. I suspect the extra storage is a
significant discouragement given one often wants to cover more
different correlations and branches.

If the 5/6-bit FSM can fit more patterns than 3x 2-bit saturating
counters, it can be a win.

I suspect it very much depends on whether bias or pattern is
dominant. This would depend on the workload (Doom?) and the
table size (and history length). I do not know that anyone in
academia has explored this, so I think you should be proud of
your discovery even if it has limited application.

A larger table (longer history) can mean longer training, but
such also discovers more patterns and longer patterns (e.g.,
predicting a fixed loop count). However, correlation strength
tends to decrease with increasing distance (having multiple
history lengths and hashings helps to find the right history).

Yeah.

I just decided to go off and to some slightly more extensive testing.

As noted, the 5/6 bit FSM can predict arbitrary 4 bit patterns.

When the pattern is exactly repeated this is great, but if the
correlation with global history is fuzzy (but biased) a counter
might be better.

I get the impression that branch prediction is complicated
enough that even experts only have a gist of what is actually
happening, i.e., there is a lot of craft and experimentation and
less logical derivation (I sense).

I decided to try comparing a few options by sampling branch data and
then testing against it offline.

Though, the current empirically-sampled data is limited in scope
(currently covering running the Doom game loop, and with enough
sample-points to cover roughly 2 seconds of running time).

Even for a 50 MHz CPU, sampling more than a few seconds worth of
branches would eat a significant chunk of RAM and make for a fairly
large file.


Recording the startup process, launching Doom, and running part of the
game loop, while preferable, will take up too much space (if one is
recording both the PC address and branch direction).

In some other past contexts, it looked like the 5/6 bit FSM was the
clear winner. But, with Doom samples and offline testing, not so clear.


Here, context is the low-order bits of PC XORed with the recent branch history.


Miss rate from the collected data (with a 6-bit context):
1-bit, last bit : ~ 19.14%
2-bit, sat counter : ~ 14.87% (2nd place)
3-bit, sat counter : ~ 18.24%
5/6-bit, GA evolved : ~ 14.25% (winner)

3/4-bit, alternating (hand): ~ 35.95% (bad)
4/5-bit, 2/3 bit pat (hand): ~ 38.75% (bad)
5/6 (hand) : Untested (too much effort)
(Will leave out the hand-written FSMs as they seem to suck).
...

If context is reduced to 5 bits:
1-bit, last bit : ~ 30.55%
2-bit, sat counter : ~ 17.37% (2nd place)
3-bit, sat counter : ~ 21.69%
5/6-bit FSM : ~ 15.86% (winner)

If context is reduced to 4 bits:
1-bit, last bit : ~ 30.55%
2-bit, sat counter : ~ 22.15% (2nd place)
3-bit, sat counter : ~ 29.04%
5/6-bit FSM : ~ 19.25% (winner)


If context is increased to 8 bits:
1-bit, last bit : ~ 13.07%
2-bit, sat counter : ~ 12.32% (winner)
3-bit, sat counter : ~ 13.96%
5/6-bit FSM : ~ 12.79% (2nd place)

If context is increased to 12 bits:
1-bit, last bit : ~ 9.46% (winner)
2-bit, sat counter : ~ 9.85% (2nd place)
3-bit, sat counter : ~ 10.38%
5/6-bit FSM : ~ 10.70%


So, it seems increasing the context size causes the FSM to lose its
advantage (mostly as more of the context seems to be dominated by
single-bit patterns; and accuracy based on how quickly it can adapt).

the 3-bit saturating counter here is nearly always worse than the 2-bit saturating counter.


If optimizing for "most effectiveness per bit of storage":
8-bit context + 2-bit sat counter would win;
If optimizing for FPGA resource cost: 5 and 6 bit contexts would win.



Did go any modify the GA table evolver to also use the sampled data as reference for the initial evolver step (along with the original purely synthetic patterns). This appears to have maybe helped.

Slightly faster adaptation and noise tolerance; but margins seem small
(can't rule out the possibility of the difference being due to
RNG/"butterfly effect" or similar, rather than due to training on "real
world" data vs purely synthetic patterns).


With 6-bit context, sampled data vs pure synthetic:
5/6-bit, GA evolved (real) : ~ 14.25% (winner)
5/6-bit, GA evolved (synth): ~ 15.33%

Where, the inclusion of real sampled data in the training process does
appear to improve accuracy over a version trained purely on synthetic patterns.



The using a genetic algorithm to generate the tables seems to vastly outperform my ability to naively hand-fill the tables.

I suspect this is because the GA is able to generate tables which adapt
to changing patterns more quickly.


The hand-filled tables tend to need a to get back to "hub states" which
then migrate to the target state for the pattern. The GA-generated
tables seem able to side-step the need for hub-states and adapt to the
change in pattern within around a few bits (if incrementing the
bit-pattern, is seems to have a 2-bit lead-in).


But, the need for hub states does put the hand-filled patterns at a disadvantage relative to the saturating counters, which as noted, does
not apply to whatever the genetic-algorithm is doing.

So, it seems like the hand-written tables are at a serious disadvantage
here.


I did verify that it was still able to adapt to arbitrary repeating 3
and 4 bit patterns (and accurately express these patterns).

with the main variability being that the GA-evolved patterns seem to
adapt more quickly and are also better able to tolerate "noise".


But, alas, this doesn't exactly mean that a 5/6 bit FSM is a clear
winner over a 2-bit saturating counter in the general case.

Comparing against branch values from initial boot process (6b ctx):
1-bit, last bit : ~ 11.39%
2-bit, sat counter : ~ 6.48%
3-bit, sat counter : ~ 33.86%
5/6-bit, GA evolved (real) : ~ 4.90%
5/6-bit, GA evolved (synth): ~ 5.02%


Granted, this was the context that originally led me to choose the 5/6
bit FSM as the clear winner over the 2-bit saturating counter.


And, for reasons, I mostly ended up not using hand-written FSMs in any
of these cases as, I don't understand whatever black arts the GA is
using here, nor can I replicate the same level of performance (also,
even if I have since figured out how to do so, writing out such an FSM
by hand is still a PITA).

So, alas, the use of a genetic algorithm seems superior at this task...


In this case, a C version of the 5/6 bit FSM looking like:
static byte fsmtab_5b[64]={
0x32, 0x20, 0x3E, 0x3B, 0x18, 0x02, 0x31, 0x13,
0x0C, 0x10, 0x06, 0x16, 0x1E, 0x24, 0x06, 0x12,
0x0F, 0x0B, 0x01, 0x2B, 0x34, 0x19, 0x1D, 0x2C,
0x33, 0x37, 0x26, 0x1B, 0x0D, 0x11, 0x08, 0x03,
0x0D, 0x39, 0x3D, 0x2A, 0x01, 0x13, 0x26, 0x37,
0x34, 0x36, 0x3F, 0x2D, 0x15, 0x21, 0x0E, 0x2B,
0x29, 0x2E, 0x38, 0x04, 0x0C, 0x25, 0x00, 0x17,
0x30, 0x2F, 0x09, 0x03, 0x14, 0x05, 0x3D, 0x23,
};

With the input/output data bit in the LSB (other 5 bits being state).


...


--- Synchronet 3.21c-Linux NewsLink 1.2