On Friday, July 16, 2021 at 11:07:13 AM UTC-5, luke.l...@gmail.com wrote:
> On Thursday, July 15, 2021 at 9:37:02 PM UTC+1, MitchAlsup wrote:
> > On Thursday, July 15, 2021 at 1:51:55 PM UTC-5, luke.l...@gmail.com wrote:
> > > *however*.... what if there was a "hint" from the compiler? an instruction which
> > > informed the hardware, "it is absolutely 100% guaranteed to be the case that
> > > 8 elements can be parallelised".
> > <
> > Mostly the HW can figure this out by examining the register dependencies at
> > loop install time, and by performing AGENs in program order. When memory
> > references are dense the problem is actually easy. The AGENs in program
> > order is what causes minimal partial order.
<
> ok, so i am slowly trying to narrow down on the circumstances to describe,
> where hints would be useful.
>
> let us imagine that it is 10,000 instructions into the loop before an address
> read is encountered, and that the loop itself is 100,000. this is (deliberately)
> far beyond what any system may successfully identify the maximum safe
> element-level parallelism through looking for AGEN'd opportunities.
<
Instead, imaging a hard limit of 100 instructions in the loop.............
But try an imaging doing something for more than 20 instructions that does
not contain a memory reference !?! what kind of calculation could those be?
and how often are these going to occur ??
<
From my side, I cannot imagine an execution window of more than 100-200
instructions being profitable, and if profitable, there will be resources to back
up precisely to an exception.
<
What VVM essentially does is to add an iteration tag to the register tags in
a reservation station (or scoreboard entry) so that the station can fire once
per loop, and while the loop is running, FETCH-PARSE-DECODE is idle.
Scalar operand reside in the station (or file for the SB), vector operands
arrive each loop. So the firing mechanism is "the same" but the entries
remain in the station/SB for the next iteration.
<
You never let the calculation[k] in one loop begin before the calculation[k]
of the previous iteration so you don't get so far OoO that the cleanup is
a big hairy mess. Further, each calculation unit (and AGEN in particular)
are in program order per unit relative to themselves. The partial order is
only across the units. {This can be relaxed after deciding on what kind
of implementation one cares about.}
>
> so let us then imagine that the hardware goes, "hmmm, i have not yet
> encountered a LD/ST but i am going to continue assuming that 64
> elements in parallel is perfectly acceptable".
<
Where are you finding these large loops ? Notice that VVM only vectorizes
the innermost loop (no nesting). Now I know the loop in FPPPP is more
than 8K instructions--but this loop is NOT the innermost loop !! But Still
where are you fining a loop of 100,000 instructions ???
>
> it also goes, "hmmm i simply cannot possibly create in-flight buffers for
> 10,000 instructions so i am forced to write most of the 10,000 instructions
> data into actual registers"
<
The inflight buffers would be bigger than the rest of the entire machine !!
So, don't do that, but give the architecture a means of giving up and dropping
back to what it already knows how to do !! Just DO NOT mandate that different
instruction streams are required for different implementations. This is what is
WRONG with SIMD.
<
Realistically, the stations in Opteron were 2× the size of the integer calculation units.
{And FP was done differently--more like a dispatch stack.....}
>
> it then encounters the LD/ST, performs the analysis of 64 LD/ST AGENs
> and finds, oh s***, 33 of them are overlapping memory addresses.
<
Realistically, as you have found out, the size of the memory disambiguation
table (MDM) is on the order of ½ of the execution window. In Mc 88120
the condition cache was 48 entries, 3 entries for each packet in the window..
And entry[0] could cause entry[47] to be dependent upon him. Meaning
only that AGEN[47] cannot retire before AGEN[0] ! Proper configurations of
these buffers are self limiting and the partial order (as opposed to OoO)
saves the day.
>
> by this time it is far, far too late: it's already written to the regfile and the
> "damage" is impossible to unwind.
<
Which is why you don't do it that way in an implementation,
AND ESPECIALLY
Why you don't specify it to allow such in an architecture !!
Architecture is not implementation ! Architecture has to span implementations.
>
> if however there was a "hint" (in this case "31 elements may be performed in
> parallel perfectly safely") it would *never hit* the 33 cases that were impossible
> to detect without an in-flight buffer of size 10,000.
<
I still don't see how the compiler can figure out the Thomas example::
a(s1:s2;S3) = a(s4:s5:s6)
when s1,s2,s3,s4,s5,s6 are parameters to the function being separately compiled.
>
> l.

> What concerns me is the amount of tracking information required
> to do this in-flight alias detection.

I thought the idea was that the this tracking is already done for the
GBOoO core anyway.

Stefan

On Friday, July 16, 2021 at 12:36:18 PM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Thursday, July 15, 2021 at 1:51:55 PM UTC-5, luke.l...@gmail.com wrote:
> >> On Monday, July 12, 2021 at 8:55:42 PM UTC+1, MitchAlsup wrote:
> >>

> > <
> > Mostly the HW can figure this out by examining the register dependencies at
> > loop install time, and by performing AGENs in program order. When memory
> > references are dense the problem is actually easy. The AGENs in program
> > order is what causes minimal partial order.
<
> What concerns me is the amount of tracking information required
> to do this in-flight alias detection. Traditional OoO needs to
> track data flow dependencies, but that information is instantaneous
> and can be disposed of as soon as dependent executes.
<
Yes, and these dependencies are via registers (which are renamed) and
memory references (which are harder to rename).
<
Now imagine the renamed register has an iteration count concatenated
to track that it is to fire when result[k] of iteration[j] is delivered. Result[k]
is constant over the loop while iteration[j] increments by 1 every loop.
So, tracking register dependencies is straightforward in VVM--a straight
forward extension to typical reservation stations or scoreboards.
<
Memory references are conceptually AGENed in program order. Lesser
implementations will actually AGEN in program order making memory
alias tracking straightforward. Greater implementations will relax this
architectural rule and AGEN is in some reasonable partial order, but this
never gets harder than BigO( windowsize^2 ) in gates, and is in fact
just a dependency matrix (almost exactly like a scoreboard)........
>
> VVM needs to correlate every original source address to a version of
<
Do you mean "source address" as memory or as register--the response
is different for each.
<
> a register, then track all the dependencies on that source as it
> flows through the operations and merges with other dependencies,
> and hold onto all that tracking info while any dependent
> is still in flight.
<
Yes, dependencies have to be obeyed or garbage falls out the back end.
>
> Maybe something like...
>
> Detecting writes to prior memory address with in-flight dependents
> could be done with a TCAM.
<
First you know that there is a ST at DECODE time, and it is entered
into a memory dependency matrix in the "unknown address" state.
Younger LDs cannot deliver their result with an older ST in the UA
state--OR--the LD can deliver its result but is subject to being replayed
should the ST actually alias the LD. {This can get messy if the HW
is designed to prevent Spectré attacks.}
<
> Maybe include a Bloom filter reset at
> LOOP start to limit TCAM lookups and power usage.
> Nicer if data addresses are all naturally aligned too.
>
> Something like a scoreboard but which retains historical versions
> could track in-flight dependencies from source to sink.
>
> Then we need some way to detect that there are no in-flight
> dependencies remaining and recover above resources.
<
This is not usefully different than a GBOoO machine deciding that
inst[k..j] can all retire simultaneously. It is a solved (if complicated)
problem.
<
> So some way to backtrack through the dependency network
> and determine that the last consumer has retired,
<
In a SB design this is a big (BIG) OR gate,
In an RS design this is an OR gate across all instructions issued together.
<
> and recover all the tracking nodes and TCAM entries.
<
OK, I give up what the frack is a TCAM ?
<
> And ideally do all that resource recovery in parallel in 1 clock.
<As long as stuff can be staged in at 1/clock and staged out at 1/clock;
all of this does not have to be done in exactly 1 clock !!
<
> >> with such a hint available, even VVM LOOPs of 100,000 instructions in length
> >> could still be performed with (up to) 8 elements at a time being thrown at the
> >> back-end ALUs.
> >>
> >> l.

On Friday, July 16, 2021 at 12:57:46 PM UTC-5, Stefan Monnier wrote:
> > What concerns me is the amount of tracking information required
> > to do this in-flight alias detection.
<
> I thought the idea was that the this tracking is already done for the
> GBOoO core anyway.
<
For the GBOoO the only difference is that the renamed registers have an
iteration count concatenated.
>
>
> Stefan

On Friday, July 16, 2021 at 12:03:32 PM UTC-6, MitchAlsup wrote:

> OK, I give up what the frack is a TCAM ?

A Ternary Content-Addressable Memory.

It can search its entire contents directly in a single cycle... and the search
term can contain don't care bits, hence the name.

John Savard

On Friday, July 16, 2021 at 6:41:54 PM UTC+1, MitchAlsup wrote:

> Instead, imaging a hard limit of 100 instructions in the loop.............
> But try an imaging doing something for more than 20 instructions that does
> not contain a memory reference !?! what kind of calculation could those be?
> and how often are these going to occur ??

i'm always concerned if a system that is designed for general purpose compute has a limitation of some kind, even though i personally cannot imagine something explicit that would tax those boundaries: "someone else will".

that said, there is almost certainly going to be cryptographic applications which perform well in parallel with initialisation not reading heavily from memory.

i _would_ suggest that the start of the loop could receive some computations in a vector of registers, such that no LD is needed, which brings me on to another issue: *passing in vector registers isn't possible*.

to perform vectorised computation it would appear that VVM *has* to operate from memory, and that only scalar registers may be passed in to the loop.

sorry, i would likely have pointed these things out 2 years ago if i had undersood VVM then! better late than never

l.

On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
> On Friday, July 16, 2021 at 6:41:54 PM UTC+1, MitchAlsup wrote:
>
> > Instead, imaging a hard limit of 100 instructions in the loop.............
> > But try an imaging doing something for more than 20 instructions that does
> > not contain a memory reference !?! what kind of calculation could those be?
> > and how often are these going to occur ??
> i'm always concerned if a system that is designed for general purpose compute has a limitation of some kind, even though i personally cannot imagine something explicit that would tax those boundaries: "someone else will".
>
> that said, there is almost certainly going to be cryptographic applications which perform well in parallel with initialisation not reading heavily from memory.
>
> i _would_ suggest that the start of the loop could receive some computations in a vector of registers, such that no LD is needed, which brings me on to another issue: *passing in vector registers isn't possible*.
<
If the register operand is "busy" when the loop starts, certainly one can
guarantee that the dependent instruction will wait for its operand to
arrive before entering calculation.
<
The VEC instruction tells which scalar registers are alive outside of the loop,
so when it terminated, the scalar registers receive the last value calculated.
>
> to perform vectorised computation it would appear that VVM *has* to operate from memory, and that only scalar registers may be passed in to the loop.
<
My 66000 only has scalar registers. VVM is a concept whereby we use those
scalar names and figure out the iteration register and inbound memory
dependencies during installation. During iteration of the loop, register
and memory dependencies are obeyed. There is no mandate on memory
being inside a VVM loop.
<
I just can't see many useful loops devoid of memory references.
>
> sorry, i would likely have pointed these things out 2 years ago if i had undersood VVM then! better late than never
>
> l.

On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
> On Friday, July 16, 2021 at 6:41:54 PM UTC+1, MitchAlsup wrote:
>
> > Instead, imaging a hard limit of 100 instructions in the loop.............
> > But try an imaging doing something for more than 20 instructions that does
> > not contain a memory reference !?! what kind of calculation could those be?
> > and how often are these going to occur ??
> i'm always concerned if a system that is designed for general purpose compute has a limitation of some kind, even though i personally cannot imagine something explicit that would tax those boundaries: "someone else will".
>
> that said, there is almost certainly going to be cryptographic applications which perform well in parallel with initialisation not reading heavily from memory.
<
I also fail to see the need to completely unroll cryptographic calculations,
turning 7 instructions into 435.
>
> i _would_ suggest that the start of the loop could receive some computations in a vector of registers, such that no LD is needed, which brings me on to another issue: *passing in vector registers isn't possible*.
>
> to perform vectorised computation it would appear that VVM *has* to operate from memory, and that only scalar registers may be passed in to the loop.
>
> sorry, i would likely have pointed these things out 2 years ago if i had undersood VVM then! better late than never
>
> l.

MitchAlsup wrote:
> On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
>> On Friday, July 16, 2021 at 6:41:54 PM UTC+1, MitchAlsup wrote:
>>
>>> Instead, imaging a hard limit of 100 instructions in the loop.............
>>> But try an imaging doing something for more than 20 instructions that does
>>> not contain a memory reference !?! what kind of calculation could those be?
>>> and how often are these going to occur ??
>> i'm always concerned if a system that is designed for general purpose compute has a limitation of some kind, even though i personally cannot imagine something explicit that would tax those boundaries: "someone else will".
>>
>> that said, there is almost certainly going to be cryptographic applications which perform well in parallel with initialisation not reading heavily from memory.
> <
> I also fail to see the need to completely unroll cryptographic calculations,
> turning 7 instructions into 435.

We did have to do this for DFC, one of the AES competition entrants:

The plain/optimized C version ran at 1/3 the speed of the faster
algorithms, including an inner loop that ran the feistel network 8 times.

For our asm version we did achieve speed parity with the fastest
algorithms, including Rijndael, the eventual winner, but to do so we did
have to unroll all 8 iterations and manually schedule some operations
across those iterations, even thought the target machine was an OoO
PentiumPro-200.

BTW, the speed we did achieve was sufficient to run 100 Mbit/s
(FastEthernet at the time) full duplex on a single core. I.e. one byte
encrypted/decrypted per clock cycle.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, July 16, 2021 at 2:43:30 PM UTC-5, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
> >> On Friday, July 16, 2021 at 6:41:54 PM UTC+1, MitchAlsup wrote:
> >>
> >>> Instead, imaging a hard limit of 100 instructions in the loop.............
> >>> But try an imaging doing something for more than 20 instructions that does
> >>> not contain a memory reference !?! what kind of calculation could those be?
> >>> and how often are these going to occur ??
> >> i'm always concerned if a system that is designed for general purpose compute has a limitation of some kind, even though i personally cannot imagine something explicit that would tax those boundaries: "someone else will".
> >>
> >> that said, there is almost certainly going to be cryptographic applications which perform well in parallel with initialisation not reading heavily from memory.
> > <
> > I also fail to see the need to completely unroll cryptographic calculations,
> > turning 7 instructions into 435.
<
> We did have to do this for DFC, one of the AES competition entrants:
>
> The plain/optimized C version ran at 1/3 the speed of the faster
> algorithms, including an inner loop that ran the feistel network 8 times.
<
Yes, but we are talking about a machine where the ADD/CMP/BC takes
zero cycles per iteration, and performs exactly zero iterations too many.
<
I can see that other machines might want to do that, but there are machines
where it should become unnecessary. And when unnecessary, it should not
be done as it wastes code space and cache performance.
>
> For our asm version we did achieve speed parity with the fastest
> algorithms, including Rijndael, the eventual winner, but to do so we did
> have to unroll all 8 iterations and manually schedule some operations
> across those iterations, even thought the target machine was an OoO
> PentiumPro-200.
<
PP-200 took handful of cycles to perform the ADD/CMP/BC and looping was
far from free.
>
> BTW, the speed we did achieve was sufficient to run 100 Mbit/s
> (FastEthernet at the time) full duplex on a single core. I.e. one byte
> encrypted/decrypted per clock cycle.
>
> Terje
>
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

> What concerns me is the amount of tracking information required
> to do this in-flight alias detection.

Consider a loop like

for (i=1; i<n; i++)
a[n[i]] = a[n[i-1]] + 1;

which basically makes this impossible, it _has_ to be
executed sequentially.

Or, different semantics, if you take Fortran's

a(n(2:)) = a(n(1:size(n-1))

you need a temporary.

If anybody wanted to do this kind of alias analysis, you would have
to restrict yourself to a subset of all the possible loops that
VVM can do, probably the stride+offset model. Possible, but better
done in the compiler, and the compiler is also better equipped to
do something like

if (stuff_can_alias (a,i))
use_ivdep_loop();
else
use_scalar_loop();

If the programmer writes

#pragma ivdep
for (i=1; i<n; i++)
a[n[i]] = a[n[i-1]] + 1;

then the compiler should be able to tell the hardware to go wild.

On Friday, July 16, 2021 at 9:02:47 PM UTC+1, Thomas Koenig wrote:

> Consider a loop like
>
> for (i=1; i<n; i++)
> a[n[i]] = a[n[i-1]] + 1;
>
> which basically makes this impossible, it _has_ to be
> executed sequentially.

that looks very much like a traditional vector indexed load... oh wait, nope, it's an overwrite version.

if i may lob in a curveball here: SVP64 REMAP for FFT Triple loop butterfly i *have* to provide a Hint. the reason is that whilst the vector loop is N log2 N, you would think that full parallelism is possible, but it is not true: only the *two innermost* loops may be parallelised: on the next iteration round the outer loop there would be overwrites.

the "Hint" in effect greatly reduces the size of Dependency Matrix entries required, because all elements within the exact same "hint block" only need one single Hazard bit.

l.

On Friday, July 16, 2021 at 3:02:47 PM UTC-5, Thomas Koenig wrote:
> EricP <ThatWould...@thevillage.com> schrieb:
> > What concerns me is the amount of tracking information required
> > to do this in-flight alias detection.
> Consider a loop like
>
> for (i=1; i<n; i++)
> a[n[i]] = a[n[i-1]] + 1;
<
I should point out that you are using 'n' as the loop maximum, and as an array
in the calculation at the same time:: no-no. SO let us change it into::
for (i=1; i<k; i++)
a[n[i]] = a[n[i-1]] + 1;
>
> which basically makes this impossible, it _has_ to be
> executed sequentially.
<
Not sequentially: but memory dependencies must be obeyed (doubly so
if a[] and n[] are aliased to each other !! )
<
Sequentially is the easiest way to obey memory dependencies.
But a memory dependence matrix can allow these references
to be calculated in a reasonable partial order and either delay or
re-run aliasing references (transitively).
>
> Or, different semantics, if you take Fortran's
>
> a(n(2:)) = a(n(1:size(n-1))
>
> you need a temporary.
>
> If anybody wanted to do this kind of alias analysis, you would have
> to restrict yourself to a subset of all the possible loops that
> VVM can do, probably the stride+offset model. Possible, but better
> done in the compiler, and the compiler is also better equipped to
> do something like
>
> if (stuff_can_alias (a,i))
> use_ivdep_loop();
> else
> use_scalar_loop();
<
But VVM does obey program order memory dependencies allowing the loop to
be expressed as::

VEC Ri,{Ri}
LDD R7,[Rn+Ri<<3]
LDD R8,[Rn+Ri<<3-8]
LDD R9,[Ra+R8<<3]
STD R9,[Ra+R7<<3]
LOOP LE,Ri,Rk,#1 // type 1 loop
<
and in the absence of aliasing, this runs as fast as the memory system can
push data through, while in the presence of aliasing it runs as fast as the
dependencies can be obeyed. What is better still is that is migrates from
as fast as memory to as fast as dependencies, back and forth, based on the
actual dependencies. When absent==fast, when present==sane. No change
code needed.
>
> If the programmer writes
>
> #pragma ivdep
> for (i=1; i<n; i++)
> a[n[i]] = a[n[i-1]] + 1;
<
That n duplicate problem again.
>
> then the compiler should be able to tell the hardware to go wild.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Friday, July 16, 2021 at 3:02:47 PM UTC-5, Thomas Koenig wrote:
>> EricP <ThatWould...@thevillage.com> schrieb:
>> > What concerns me is the amount of tracking information required
>> > to do this in-flight alias detection.
>> Consider a loop like
>>
>> for (i=1; i<n; i++)
>> a[n[i]] = a[n[i-1]] + 1;
><
> I should point out that you are using 'n' as the loop maximum, and as an array
> in the calculation at the same time:: no-no.

Which is what I get for not running the code through a compiler first :)

>SO let us change it into::
> for (i=1; i<k; i++)
> a[n[i]] = a[n[i-1]] + 1;
>>
>> which basically makes this impossible, it _has_ to be
>> executed sequentially.
><
> Not sequentially: but memory dependencies must be obeyed (doubly so
> if a[] and n[] are aliased to each other !! )
><
> Sequentially is the easiest way to obey memory dependencies.
> But a memory dependence matrix can allow these references
> to be calculated in a reasonable partial order and either delay or
> re-run aliasing references (transitively).

So, what would you do for a test case like

#include <stdio.h>
#include <stdlib.h>

int main()
{ int n;
int i,j,k,m;
int *ind;
double *a;
scanf ("%d",&n);

ind = malloc(n*sizeof *ind);
a = malloc(n*sizeof a);
for (i=0; i<n; i++)
{
scanf ("%d",ind+i);
a[i] = i;
}

for (i=0; i<n; i++)
{
j = ind[i];
k = ind[j];
m = ind[k];
a[i] += a[m];
}
for (i=0; i<n; i++)
printf (" %f",a[i]);
printf ("\n");
free (ind);
free(a);
return 0;
}

Is this also expressed in VVM, is this handled in a parallel
fashion fashion in (simulated) hardware, and do you get results
that agree with the serial execution?

$ echo "4 1 2 0 3" | ./a.out
0.000000 2.000000 4.000000 6.000000
$ echo "4 4 3 2 1" | ./a.out
0.000000 4.000000 4.000000 7.000000
$ echo "4 1 1 2 0" | ./a.out
1.000000 2.000000 4.000000 5.000000
$

Or do the hardware or the compiler have a heuristic to give
up cheaply i a case like that?

(It is, of course, possible to make this sort of test case into
something arbitrarily complex; I would not expect excellent
performance for this because this is of course artificial, but I
would expect that the execution is always correct, and not (much)
worse than a straight scalar execution).

On Saturday, July 17, 2021 at 2:20:41 AM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > On Friday, July 16, 2021 at 3:02:47 PM UTC-5, Thomas Koenig wrote:
> >> EricP <ThatWould...@thevillage.com> schrieb:
> >> > What concerns me is the amount of tracking information required
> >> > to do this in-flight alias detection.
> >> Consider a loop like
> >>
> >> for (i=1; i<n; i++)
> >> a[n[i]] = a[n[i-1]] + 1;
> ><
> > I should point out that you are using 'n' as the loop maximum, and as an array
> > in the calculation at the same time:: no-no.
> Which is what I get for not running the code through a compiler first :)
> >SO let us change it into::
> > for (i=1; i<k; i++)
> > a[n[i]] = a[n[i-1]] + 1;
> >>
> >> which basically makes this impossible, it _has_ to be
> >> executed sequentially.
> ><
> > Not sequentially: but memory dependencies must be obeyed (doubly so
> > if a[] and n[] are aliased to each other !! )
> ><
> > Sequentially is the easiest way to obey memory dependencies.
> > But a memory dependence matrix can allow these references
> > to be calculated in a reasonable partial order and either delay or
> > re-run aliasing references (transitively).
> So, what would you do for a test case like
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main()
> {
> int n;
> int i,j,k,m;
> int *ind;
> double *a;
> scanf ("%d",&n);
>
> ind = malloc(n*sizeof *ind);
> a = malloc(n*sizeof a);
> for (i=0; i<n; i++)
> {
> scanf ("%d",ind+i);
> a[i] = i;
> }
>
> for (i=0; i<n; i++)
> {
> j = ind[i];
> k = ind[j];
> m = ind[k];
> a[i] += a[m];
> }
> for (i=0; i<n; i++)
> printf (" %f",a[i]);
> printf ("\n");
> free (ind);
> free(a);
> return 0;
> }
>
> Is this also expressed in VVM, is this handled in a parallel
> fashion fashion in (simulated) hardware, and do you get results
> that agree with the serial execution?
<
You get results that agree with (serial) scalar execution.
<
A more advanced machine will recognize that each loop starts
out with 4-level indirect fetch and the addresses of three of the
fetches (LD) are unknown at the beginning of the loop, so these
go on hold due to a data dependency (can't calculate the address).
So the fetches are performed sequentially (necessarily).
<
>
> $ echo "4 1 2 0 3" | ./a.out
> 0.000000 2.000000 4.000000 6.000000
> $ echo "4 4 3 2 1" | ./a.out
> 0.000000 4.000000 4.000000 7.000000
> $ echo "4 1 1 2 0" | ./a.out
> 1.000000 2.000000 4.000000 5.000000
> $
>
> Or do the hardware or the compiler have a heuristic to give
> up cheaply i a case like that?
>
> (It is, of course, possible to make this sort of test case into
> something arbitrarily complex; I would not expect excellent
> performance for this because this is of course artificial, but I
> would expect that the execution is always correct, and not (much)
> worse than a straight scalar execution).
<
It is actually better than scalar performance because LOOP
executes in zero effective cycles whereas ADD/CMP/BC will
take at least 2. But, it is completely dependent on cache perf.

MitchAlsup wrote:
> On Friday, July 16, 2021 at 12:36:18 PM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>>>> On Monday, July 12, 2021 at 8:55:42 PM UTC+1, MitchAlsup wrote:
>>>>
>
>>> <
>>> Mostly the HW can figure this out by examining the register dependencies at
>>> loop install time, and by performing AGENs in program order. When memory
>>> references are dense the problem is actually easy. The AGENs in program
>>> order is what causes minimal partial order.
> <
>> What concerns me is the amount of tracking information required
>> to do this in-flight alias detection. Traditional OoO needs to
>> track data flow dependencies, but that information is instantaneous
>> and can be disposed of as soon as dependent executes.
> <
> Yes, and these dependencies are via registers (which are renamed) and
> memory references (which are harder to rename).
> <
> Now imagine the renamed register has an iteration count concatenated
> to track that it is to fire when result[k] of iteration[j] is delivered. Result[k]
> is constant over the loop while iteration[j] increments by 1 every loop.
> So, tracking register dependencies is straightforward in VVM--a straight
> forward extension to typical reservation stations or scoreboards.
> <
> Memory references are conceptually AGENed in program order. Lesser
> implementations will actually AGEN in program order making memory
> alias tracking straightforward. Greater implementations will relax this
> architectural rule and AGEN is in some reasonable partial order, but this
> never gets harder than BigO( windowsize^2 ) in gates, and is in fact
> just a dependency matrix (almost exactly like a scoreboard)........

> First you know that there is a ST at DECODE time, and it is entered
> into a memory dependency matrix in the "unknown address" state.
> Younger LDs cannot deliver their result with an older ST in the UA
> state--OR--the LD can deliver its result but is subject to being replayed
> should the ST actually alias the LD. {This can get messy if the HW
> is designed to prevent Spectré attacks.}

Ok, yes its a standard load-store queue with store to load
forwarding and cache line disambiguation.

What was confusing me is automatically packing multiple operands
together as elements in a single SIMD register "packet",
then what happens if the elements start to interact?

But I see elsewhere you answer that VVM is scalar only:

MitchAlsup wrote:
> On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
>> to perform vectorised computation it would appear that VVM *has* to operate from
memory, and that only scalar registers may be passed in to the loop.
> <
> My 66000 only has scalar registers. VVM is a concept whereby we use those
> scalar names and figure out the iteration register and inbound memory
> dependencies during installation. During iteration of the loop, register
> and memory dependencies are obeyed. There is no mandate on memory
> being inside a VVM loop.
> <

On Monday, July 19, 2021 at 11:15:39 AM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Friday, July 16, 2021 at 12:36:18 PM UTC-5, EricP wrote:
> >> MitchAlsup wrote:
> >>>> On Monday, July 12, 2021 at 8:55:42 PM UTC+1, MitchAlsup wrote:
> >>>>
> >
> >>> <
> >>> Mostly the HW can figure this out by examining the register dependencies at
> >>> loop install time, and by performing AGENs in program order. When memory
> >>> references are dense the problem is actually easy. The AGENs in program
> >>> order is what causes minimal partial order.
> > <
> >> What concerns me is the amount of tracking information required
> >> to do this in-flight alias detection. Traditional OoO needs to
> >> track data flow dependencies, but that information is instantaneous
> >> and can be disposed of as soon as dependent executes.
> > <
> > Yes, and these dependencies are via registers (which are renamed) and
> > memory references (which are harder to rename).
> > <
> > Now imagine the renamed register has an iteration count concatenated
> > to track that it is to fire when result[k] of iteration[j] is delivered.. Result[k]
> > is constant over the loop while iteration[j] increments by 1 every loop..
> > So, tracking register dependencies is straightforward in VVM--a straight
> > forward extension to typical reservation stations or scoreboards.
> > <
> > Memory references are conceptually AGENed in program order. Lesser
> > implementations will actually AGEN in program order making memory
> > alias tracking straightforward. Greater implementations will relax this
> > architectural rule and AGEN is in some reasonable partial order, but this
> > never gets harder than BigO( windowsize^2 ) in gates, and is in fact
> > just a dependency matrix (almost exactly like a scoreboard)........
> > First you know that there is a ST at DECODE time, and it is entered
> > into a memory dependency matrix in the "unknown address" state.
> > Younger LDs cannot deliver their result with an older ST in the UA
> > state--OR--the LD can deliver its result but is subject to being replayed
> > should the ST actually alias the LD. {This can get messy if the HW
> > is designed to prevent Spectré attacks.}
> Ok, yes its a standard load-store queue with store to load
> forwarding and cache line disambiguation.
>
> What was confusing me is automatically packing multiple operands
> together as elements in a single SIMD register "packet",
> then what happens if the elements start to interact?
<
It runs slower than if all the lanes are independent.
>
> But I see elsewhere you answer that VVM is scalar only:
> MitchAlsup wrote:
> > On Friday, July 16, 2021 at 1:44:03 PM UTC-5, luke.l...@gmail.com wrote:
> >> to perform vectorised computation it would appear that VVM *has* to operate from
> memory, and that only scalar registers may be passed in to the loop.
> > <
> > My 66000 only has scalar registers. VVM is a concept whereby we use those
> > scalar names and figure out the iteration register and inbound memory
> > dependencies during installation. During iteration of the loop, register
> > and memory dependencies are obeyed. There is no mandate on memory
> > being inside a VVM loop.
> > <

On Friday, July 16, 2021 at 10:02:42 AM UTC-6, Quadibloc wrote:
> On Wednesday, July 14, 2021 at 5:33:36 PM UTC-6, Quadibloc wrote:

> > So I should simplify down and reduce what I offer in that area to merely a single
> > bit per instruction to indicate groups of instructions that can be executed in
> > parallel without any checking.

> As the changes required were extensive, I have only now gotten around to
> making them, and posting the updated pages to

> http://www.quadibloc.com/arch/ct14int.htm

> and succeeding pages.

Except for adding conditional jump and subroutine jump instructions to the
mostly 16-bit instruction format on the page

http://www.quadibloc.com/arch/cp0101.htm

I haven't been making other changes to the instruction formats over the
last few days. While this is partly due to being busy with other distractions,
perhaps at this point I'm no longer seriously dissatisfied with any aspect
of the instruction formats, and so when I have the energy for the work,
perhaps now I'll proceed to filling in details like the opcodes someday
soon.

John Savard

On Saturday, July 24, 2021 at 12:26:55 AM UTC+1, Quadibloc wrote:

> Except for adding conditional jump and subroutine jump instructions to the
> mostly 16-bit instruction format on the page
>
> http://www.quadibloc.com/arch/cp0101.htm

"As all the 16-bit instructions begin with 0, and the first half of a 32-bit instruction always begins with 10 while the second half of a 32-bit instruction always begins with 11, fully parallel decoding is possible."

niiice. that's a really neat trick.

one of our team (Jacob) noted that if you have a prefix which easily identifies the size (16 bit starts with 0 for example) you can use a variant of carry propagation for multi issue length detection.

however i think it only works with two instruction lengths: if you mix 16 32 and 64 for example it is no longer O log N

what you csme up with is O(1) i love it.

l.

On Friday, July 23, 2021 at 6:14:11 PM UTC-6, luke.l...@gmail.com wrote:

> what you csme up with is O(1) i love it.

Of course, it _is_ wasteful of space in order to be O(1). But the whole ISA is O(1).

The default is that all instructions are 32 bits long, although a 32-bit slot can contain
a pair of 16 bit instructions instead.

A few unused instruction codes instead are headers - and every header indicates
some O(1) format; this 16-bit mostly format, formats with all the instructions 32 bits
long, or variable-length instruction formats with some other scheme of indicating
the length.

John Savard

On 2021-07-24 03:43, Quadibloc wrote:
> On Friday, July 23, 2021 at 6:14:11 PM UTC-6, luke.l...@gmail.com wrote:
>
>> what you csme up with is O(1) i love it.
>
> Of course, it _is_ wasteful of space in order to be O(1). But the whole ISA is O(1).
>
> The default is that all instructions are 32 bits long, although a 32-bit slot can contain
> a pair of 16 bit instructions instead.

Question: Do 16-bit instructions need to come in pairs, aligned to a
32-bit boundary (because it sounded like you said that)?

If so, you wouldn't need "10" and "11" headers for 16-bit instructions,
but "1" would be enough, no?

>
> A few unused instruction codes instead are headers - and every header indicates
> some O(1) format; this 16-bit mostly format, formats with all the instructions 32 bits
> long, or variable-length instruction formats with some other scheme of indicating
> the length.
>
> John Savard
>

On Tuesday, July 27, 2021 at 10:20:53 AM UTC-6, Marcus wrote:

> Question: Do 16-bit instructions need to come in pairs, aligned to a
> 32-bit boundary (because it sounded like you said that)?

> If so, you wouldn't need "10" and "11" headers for 16-bit instructions,
> but "1" would be enough, no?

Ah; I didn't make one thing clear.

In the instruction format where 16-bit instructions start with 0
and 32-bit instructions start with 10 for their first half and 11
for their second half, no such restriction is present.

In _another_ instruction format, the 16-bit instructions need
to come in pairs. Here, they also start with 0, but any 32-bit
instruction slot that doesn't begin with 0 in both its halves
contains a single 32-bit instruction.

That other instruction format is the _default_. However, some
instruction codes are unused... as instructions, and instead
act as headers for a 256-bit block. Which may contain instructions
in one of four formats, the two that have been described, and
two others. Plus additional modifier information.

John Savard

On Friday, July 23, 2021 at 6:14:11 PM UTC-6, luke.l...@gmail.com wrote:
> On Saturday, July 24, 2021 at 12:26:55 AM UTC+1, Quadibloc wrote:
>
> > Except for adding conditional jump and subroutine jump instructions to the
> > mostly 16-bit instruction format on the page
> >
> > http://www.quadibloc.com/arch/cp0101.htm

> "As all the 16-bit instructions begin with 0, and the first half of a 32-bit instruction always begins with 10 while the second half of a 32-bit instruction always begins with 11, fully parallel decoding is possible."

> niiice. that's a really neat trick.

> one of our team (Jacob) noted that if you have a prefix which easily identifies the size (16 bit starts with 0 for example) you can use a variant of carry propagation for multi issue length detection.

> however i think it only works with two instruction lengths: if you mix 16 32 and 64 for example it is no longer O log N

That may be, but I think Mitch Alsup noted that even with three instruction lengths - if a
very simple scheme is used like that of the IBM System/360 and its successors -
something similarly efficient can be achieved.

> what you csme up with is O(1) i love it.

I've been doing some more thinking, and I've come up with a way to reduce the needed
overhead, and still remain O(1). Soon I'll be updating the page to show the new scheme.

Basically:

Each 16-bit instruction slot has its first bit reserved for length indication.

What to _do_ with each 16-bit slot can be directly determined without having to go
sequentially through all the preceding slots... _but_ it is necessary to peek at the
first bit of the preceding slot and the following slot.

The instructions have the first bits of their parts like this:

0 if 16 bits
1 0 if 32 bits
1 1 0 if 48 bits.

Decoding of an instruction is initiated at the decoder which processes
the first 16 bits of the instruction. Here is what it is to do, based on the
three first bits of the preceding, current, and following slots (the first
slot in a block is treated as though it's preceded by a slot with a 0 in
the first bit position):

0 0 - Process a 16-bit instruction
1 0 - Take no action
0 1 0 Process a 32-bit instruction
0 1 1 Process a 48-bit instruction
1 1 - Take no action (only 1 1 0, never 1 1 1, should occur)

Perhaps in the 1 1 1 case, it should be - don't take the action of
decoding an instruction, but do signal an exception.

This also solves the issue of having to split up the address field, as a
nice bonus!

John Savard

On Saturday, August 7, 2021 at 8:02:09 AM UTC+1, Quadibloc wrote:

> Each 16-bit instruction slot has its first bit reserved for length indication.
>
> What to _do_ with each 16-bit slot can be directly determined without having to go
> sequentially through all the preceding slots... _but_ it is necessary to peek at the
> first bit of the preceding slot and the following slot.

yes, and then you can use a variant of carry-propagation which istr is O(log(N))
> The instructions have the first bits of their parts like this:
>
> 0 if 16 bits
> 1 0 if 32 bits
> 1 1 0 if 48 bits.

this is remarkably similar to the RISC-V ISA encoding, which they extended
to 192+ bits and beyond. 1110 is 64-bit, 11110NNN is 80-192 bit and
1111110 is reserved for future.

actually it's not quite like that, what it is, is:

* 0b00 is 16-bit Quadrant 0
* 0b01 is 16-bit Quadrant 1
* 0b10 is 16-bit Quadrant 2
* 0b11 is 32-bit:
- 0bNNNNN11 is Major opcodes 0-30
- 0b11111111 is further escape-sequenced

something like that, it's basically the same principle except the
major opcodes are spaced in between.

what i really like about what you came up with (the original version)
is that the number of bits used for signalling sizes is a completely
parallel one... but it's also about the same number of bits used *for*
signalling as in RISC-V.

l.

On Saturday, August 7, 2021 at 4:17:11 AM UTC-6, luke.l...@gmail.com wrote:

> what i really like about what you came up with (the original version)
> is that the number of bits used for signalling sizes is a completely
> parallel one... but it's also about the same number of bits used *for*
> signalling as in RISC-V.

Thank you. Of course, though, I'm only able to do this because a
signalling bit intrudes on every 16-bit instruction slot.

That is possible because in this restricted 16-bit instruction format,
I am not using displacements longer than 15 bits.

When I use full 16-bit displacements, and I also have immediates
that might be 16, 32, or 64 bits, with no possibility of a signalling
bit intruding on that space, normally I would have no option of using
a completely parallel scheme - at least, not one of this general kind.

In some previous incarnations of Concertina II, I switched to 18-bit
instruction slots so I could combine 16-bit displacements with parallel
encoding. (Immediates, though, were handled through block headers.)

So this is why the other instruction formats use block headers to
attain O(1) decoding instead.

John Savard