Combination loops and false paths

Rob Doyle <radioengr@gmail.com> wrote:

(snip)

> I guess I'm using term ALU and am2901 interchangeably.  
> I'll be more specific.
 
> There is nothing wrong with the am2901 proper.  It is what it is.

I suppose, but it was designed way before the tools we use now.
 
(snip)

> The problems is that am2901 output goes to a bus that eventually routes
> back to the am2901 input for some unused (as best I can tell)
> configuration of the microcode.  This all happens with no registers in
> the loop.
 
(snip)

> I guess that it is just a design from another day - a whole lot less
> synchronous than anything I've done in an FPGA before.
 
> I have enjoyed going back through that all.   I even found my "Mick and
> Brick" book.  I'll probably do a VAX 11/780 next which also used
> bit-sliced parts.

Years ago, maybe just about when it was new, I bought "Mick and Brick."

Then, about 20 years ago, it got lost in a move. A few weeks ago I
bought a used one from half.com for a low price. (In case I decide
to do some 2901 designs in FPGAs.)

The discussion on combinatorial loops reminds me of the wrap around
carry on ones complement adders. If done the obvious way, it is a
combinatorial loop, but hopefully one that, in actual use, resolves
itself. 

-- glen

rickman <gnuarm@gmail.com> wrote:

(snip, I wrote)

>> The BRAM on most FPGAs are synchronous (clocked). That might not
>> match what you need for some older designs. If it isn't too big,
>> and you really need asynchronous RAM, you have to make it out
>> of CLB logic.
 
> Yes, not only are the block RAMs synchronous, the LUT RAMs (distributed) 
> are also synchronous.  That is why I say you have to make async RAM out 
> of latches.

The are now? They didn't used to be. I am somewhat behind in the
generations of FPGAs.
 
(snip, I also wrote)

>> I believe that the KA-10 was done in asynchronous (non-clocked) logic.
>> That might make an interesting FPGA project.
 
> Doing async logic in an FPGA is not so easy.  You need timing info that 
> is hard to get.

The whole idea behind asynchronous logic is that you don't need to know
any timing information. Otherwise known as self-timed logic, there is
enough hand-shaking such that every signal changes when it is ready, no
sooner and no later. If you use dual-rail logic:

http://en.wikipedia.org/wiki/Asynchronous_system#Asynchronous_datapaths

then all timing just works.

If you mix synchronous and asynchronous logic, then things get more
interesting.

-- glen

On 1/17/2013 8:57 PM, glen herrmannsfeldt wrote:
> Rob Doyle<radioengr@gmail.com>  wrote:
>
> (snip)
>
>> I guess I'm using term ALU and am2901 interchangeably.
>> I'll be more specific.
>
>> There is nothing wrong with the am2901 proper.  It is what it is.
>
> I suppose, but it was designed way before the tools we use now.
>
> (snip)
>
>> The problems is that am2901 output goes to a bus that eventually routes
>> back to the am2901 input for some unused (as best I can tell)
>> configuration of the microcode.  This all happens with no registers in
>> the loop.
>
> (snip)
>
>> I guess that it is just a design from another day - a whole lot less
>> synchronous than anything I've done in an FPGA before.
>
>> I have enjoyed going back through that all.   I even found my "Mick and
>> Brick" book.  I'll probably do a VAX 11/780 next which also used
>> bit-sliced parts.
>
> Years ago, maybe just about when it was new, I bought "Mick and Brick."
>
> Then, about 20 years ago, it got lost in a move. A few weeks ago I
> bought a used one from half.com for a low price. (In case I decide
> to do some 2901 designs in FPGAs.)
>
> The discussion on combinatorial loops reminds me of the wrap around
> carry on ones complement adders. If done the obvious way, it is a
> combinatorial loop, but hopefully one that, in actual use, resolves
> itself.

Mick and Brick was not just about the 2901, it covered the basic 
concepts of designing a processor.  One of the things that stuck with me 
was the critical path they described, which I believe was in a 
conditional branch calculating the next address (I guess it finally got 
away from me again).  I found that to be true on every processor design 
I looked at, including the MISC designs I did in FPGAs on my own.  These 
guys had some pretty good insight into processor design.

I had my own book too and will have to dig around for it.  But I am 
pretty sure it is gone as I haven't seen it in other searches I've done 
for other books the last ten years or so.  I think I got it free from 
AMD at one point.  Now they are over $100 for one in good condition. 
I'm not sure what "adequate" means for a book condition.  They say it is 
all legible, but I've seen some pretty rough books in "good" condition.

Rick

On 1/17/2013 9:09 PM, glen herrmannsfeldt wrote:
> rickman<gnuarm@gmail.com>  wrote:
>
> (snip, I wrote)
>
>>> The BRAM on most FPGAs are synchronous (clocked). That might not
>>> match what you need for some older designs. If it isn't too big,
>>> and you really need asynchronous RAM, you have to make it out
>>> of CLB logic.
>
>> Yes, not only are the block RAMs synchronous, the LUT RAMs (distributed)
>> are also synchronous.  That is why I say you have to make async RAM out
>> of latches.
>
> The are now? They didn't used to be. I am somewhat behind in the
> generations of FPGAs.

Actually, I think Xilinx made their XC4000 series with clocks for 
writing the distributed RAM.  They had too much trouble with poor 
designs trying to generate a write pulse with good timing and decided 
they were better off giving the user a clock.  I used the ACEX from 
Altera in 2000 or so which had an async read block RAM.  It made a 
processor easier to design saving a clock cycle on reads.  Block RAMs 
have always been synchronous on the writes and now they are synchronous 
on reads as well... so many generations of FPGAs...


> (snip, I also wrote)
>
>>> I believe that the KA-10 was done in asynchronous (non-clocked) logic.
>>> That might make an interesting FPGA project.
>
>> Doing async logic in an FPGA is not so easy.  You need timing info that
>> is hard to get.
>
> The whole idea behind asynchronous logic is that you don't need to know
> any timing information. Otherwise known as self-timed logic, there is
> enough hand-shaking such that every signal changes when it is ready, no
> sooner and no later. If you use dual-rail logic:
>
> http://en.wikipedia.org/wiki/Asynchronous_system#Asynchronous_datapaths
>
> then all timing just works.

You need to read that section again...  Nowhere does it say the timing 
"just works".  It describes two ways to communicate a signal, one is to 
send one of two pulses for a 1 or a 0 and the other is to use a 
handshake signal which has a delay longer than the data it is clocking. 
  In both cases you have to use timing to generate the control signal 
(or combined data and control in the first case).  The advantage is that 
the timing issues are "localized" to the unit rather than being global.

The problem with doing this in an FPGA is that the tools are all 
designed for fully synchronous systems.  This sort of local timing with 
an emphasis on relative delays rather than simple maximum delays is 
difficult to do using the standard tools.


> If you mix synchronous and asynchronous logic, then things get more
> interesting.

All real time systems are at some point synchronous.  They have 
deadlines to meet and often there are recurring events that have to be 
synced to a clock such as an interface or an ADC.  In the end an async 
processor buys you very little other than saving power in the clock 
tree.  Even this is just a strawman as the real question is the power it 
takes to get the job done, not how much power is used to distribute the 
clock.

The GA144 is an array of 144 fully async processors.  I have looked at 
using the GA144 for real world designs twice.  In each case the I/O had 
to be clocked which is awkwardly supported in the chip.  In the one case 
the limitations made it very difficult to even analyze timing of a 
clocked interface, much less meet timing.  In the other case low power 
was paramount and the GA144 could not match the power requirements while 
I am pretty sure I can do the job with a low power FPGA.  Funny 
actually, the GA144 has an idle current of just 55 nA per processor or 
just 7 uA for the chip.  The FPGA I am working with has an idle current 
of some 40 uA but including the processing the total should be under 100 
uA.  In the GA144 I calculated over 100 uA just driving the ADC not 
counting any real processing.  Actually, most of the power is used in 
timing the ADC conversion.  Without a high resolution clock the only way 
to time the ADC conversion is to put the processor in an idle loop...

There is many a slip 'twixt cup and lip.

Rick

rickman <gnuarm@gmail.com> wrote:

(snip)
> Mick and Brick was not just about the 2901, it covered the basic 
> concepts of designing a processor.  One of the things that stuck with me 
> was the critical path they described, which I believe was in a 
> conditional branch calculating the next address (I guess it finally got 
> away from me again).  I found that to be true on every processor design 
> I looked at, including the MISC designs I did in FPGAs on my own.  These 
> guys had some pretty good insight into processor design.

Yes, but with 29xx for all the examples. I also have some books
on microprogramming, independent of the processor. Well, maybe
not completely independent.
 
> I had my own book too and will have to dig around for it.  But I am 
> pretty sure it is gone as I haven't seen it in other searches I've done 
> for other books the last ten years or so.  I think I got it free from 
> AMD at one point.  Now they are over $100 for one in good condition. 
> I'm not sure what "adequate" means for a book condition.  They say it is 
> all legible, but I've seen some pretty rough books in "good" condition.

half.com has $1.49 (plus shipping) for acceptable condition, $5.52 for
good condition, and $8.88 for very good condition.

The one I got has the dust jacket a little worn and torn, and the
spine might be a little weak, but plenty usable. 

-- glen

rickman <gnuarm@gmail.com> wrote:

(snip)
>>> Yes, not only are the block RAMs synchronous, the LUT RAMs (distributed)
>>> are also synchronous.  That is why I say you have to make async RAM out
>>> of latches.

>> The are now? They didn't used to be. I am somewhat behind in the
>> generations of FPGAs.
 
> Actually, I think Xilinx made their XC4000 series with clocks for 
> writing the distributed RAM.  They had too much trouble with poor 
> designs trying to generate a write pulse with good timing and decided 
> they were better off giving the user a clock.  I used the ACEX from 
> Altera in 2000 or so which had an async read block RAM.  It made a 
> processor easier to design saving a clock cycle on reads.  Block RAMs 
> have always been synchronous on the writes and now they are synchronous 
> on reads as well... so many generations of FPGAs...

I am not sure about writes now. BRAMs are synchronous read, but LUT
RAM better not be, as the LUTs are the same as used for logic.

Some designs just won't work with a synchronous read RAM (which
is sometimes a ROM). 
 
(snip on asynchronous logic)

> You need to read that section again...  Nowhere does it say the timing 
> "just works".  It describes two ways to communicate a signal, one is to 
> send one of two pulses for a 1 or a 0 and the other is to use a 
> handshake signal which has a delay longer than the data it is clocking. 
>  In both cases you have to use timing to generate the control signal 
> (or combined data and control in the first case).  The advantage is that 
> the timing issues are "localized" to the unit rather than being global.

I meant the one they call dual rail logic. There are two wires sending
the signal, in one of three states, 0, 1, or none, and one coming
back acknowledging the signal. The generate a signal, either the 0
or 1 goes active, until the ack comes back, at which time the output
signal is removed until the ack goes away. Full handshake both ways.

> The problem with doing this in an FPGA is that the tools are all 
> designed for fully synchronous systems.  This sort of local timing with 
> an emphasis on relative delays rather than simple maximum delays is 
> difficult to do using the standard tools.

Yes. Besides all those useless FF's in each cell. 
 
>> If you mix synchronous and asynchronous logic, then things get more
>> interesting.
 
> All real time systems are at some point synchronous.  They have 
> deadlines to meet and often there are recurring events that have to be 
> synced to a clock such as an interface or an ADC.  In the end an async 
> processor buys you very little other than saving power in the clock 
> tree.  Even this is just a strawman as the real question is the power it 
> takes to get the job done, not how much power is used to distribute the 
> clock.

As I understand it, there are some current processors with asynchronous
logic blocks, such as a multiplier. The operands are clocked in and,
an unknown (data dependent) number of cycles later the result comes
out, is latched, and sent on. So, 0*0 might be very fast, were
full width operands might be much slower. 
 
> The GA144 is an array of 144 fully async processors.  I have looked at 
> using the GA144 for real world designs twice.  In each case the I/O had 
> to be clocked which is awkwardly supported in the chip.  In the one case 
> the limitations made it very difficult to even analyze timing of a 
> clocked interface, much less meet timing.  In the other case low power 
> was paramount and the GA144 could not match the power requirements while 
> I am pretty sure I can do the job with a low power FPGA.  Funny 
> actually, the GA144 has an idle current of just 55 nA per processor or 
> just 7 uA for the chip.  The FPGA I am working with has an idle current 
> of some 40 uA but including the processing the total should be under 100 
> uA.  In the GA144 I calculated over 100 uA just driving the ADC not 
> counting any real processing.  Actually, most of the power is used in 
> timing the ADC conversion.  Without a high resolution clock the only way 
> to time the ADC conversion is to put the processor in an idle loop...

Sounds like an interesting design.

-- glen

On 1/19/2013 5:35 PM, glen herrmannsfeldt wrote:
> rickman<gnuarm@gmail.com>  wrote:
>
> (snip)
>>>> Yes, not only are the block RAMs synchronous, the LUT RAMs (distributed)
>>>> are also synchronous.  That is why I say you have to make async RAM out
>>>> of latches.
>
>>> The are now? They didn't used to be. I am somewhat behind in the
>>> generations of FPGAs.
>
>> Actually, I think Xilinx made their XC4000 series with clocks for
>> writing the distributed RAM.  They had too much trouble with poor
>> designs trying to generate a write pulse with good timing and decided
>> they were better off giving the user a clock.  I used the ACEX from
>> Altera in 2000 or so which had an async read block RAM.  It made a
>> processor easier to design saving a clock cycle on reads.  Block RAMs
>> have always been synchronous on the writes and now they are synchronous
>> on reads as well... so many generations of FPGAs...
>
> I am not sure about writes now. BRAMs are synchronous read, but LUT
> RAM better not be, as the LUTs are the same as used for logic.
>
> Some designs just won't work with a synchronous read RAM (which
> is sometimes a ROM).

That's right.  My processor design on the ACEX with async reads had to 
be modified to work in nearly any other part with fully sync block RAM. 
  I could possibly clock the RAM on the negative edge with the rest of 
the design clocked on the positive.  Or I could do a read on every clock 
using the address precursor which is available on the prior clock cycle 
at the input to the address register.  Both methods reduce timing 
margins along with other tradeoffs.


>> You need to read that section again...  Nowhere does it say the timing
>> "just works".  It describes two ways to communicate a signal, one is to
>> send one of two pulses for a 1 or a 0 and the other is to use a
>> handshake signal which has a delay longer than the data it is clocking.
>>   In both cases you have to use timing to generate the control signal
>> (or combined data and control in the first case).  The advantage is that
>> the timing issues are "localized" to the unit rather than being global.
>
> I meant the one they call dual rail logic. There are two wires sending
> the signal, in one of three states, 0, 1, or none, and one coming
> back acknowledging the signal. The generate a signal, either the 0
> or 1 goes active, until the ack comes back, at which time the output
> signal is removed until the ack goes away. Full handshake both ways.

I haven't seen the logic, but how do they generate the timing for the 
handshakes?  I don't think it "just works".  My understanding is that 
the handshakes are generated by a delay line that is designed to have a 
longer delay than the logic.  This is hard to do with the timing tools 
designed for synchronous systems.


>> The problem with doing this in an FPGA is that the tools are all
>> designed for fully synchronous systems.  This sort of local timing with
>> an emphasis on relative delays rather than simple maximum delays is
>> difficult to do using the standard tools.
>
> Yes. Besides all those useless FF's in each cell.

I don't follow.  I think typical async logic still has FFs, they just 
don't use a global clock.  I suppose if you have handshakes back and 
forth you are making latches in the combinatorial logic if nothing else.


>>> If you mix synchronous and asynchronous logic, then things get more
>>> interesting.
>
>> All real time systems are at some point synchronous.  They have
>> deadlines to meet and often there are recurring events that have to be
>> synced to a clock such as an interface or an ADC.  In the end an async
>> processor buys you very little other than saving power in the clock
>> tree.  Even this is just a strawman as the real question is the power it
>> takes to get the job done, not how much power is used to distribute the
>> clock.
>
> As I understand it, there are some current processors with asynchronous
> logic blocks, such as a multiplier. The operands are clocked in and,
> an unknown (data dependent) number of cycles later the result comes
> out, is latched, and sent on. So, 0*0 might be very fast, were
> full width operands might be much slower.

I haven't heard of that.  How would that benefit a sync processor?  I 
can only think that would be useful if the design were compared to one 
with a very slow multiplier which required the processor to wait for 
many clock cycles.  A multiplier with a "ready" flag could shorten the 
wait.  But that can also be done for a fully sync multiplier.  In fact, 
in the async GA144 there is no multiply instruction.  Instead there is a 
multiply step instruction which can be used to do multiplies in a loop. 
  The loop can be terminated when the multiply has detected the rest of 
the bits are all zero (or all ones maybe?).  I haven't seen the code 
that does this, but this is reported in some of their white papers.


>> The GA144 is an array of 144 fully async processors.  I have looked at
>> using the GA144 for real world designs twice.  In each case the I/O had
>> to be clocked which is awkwardly supported in the chip.  In the one case
>> the limitations made it very difficult to even analyze timing of a
>> clocked interface, much less meet timing.  In the other case low power
>> was paramount and the GA144 could not match the power requirements while
>> I am pretty sure I can do the job with a low power FPGA.  Funny
>> actually, the GA144 has an idle current of just 55 nA per processor or
>> just 7 uA for the chip.  The FPGA I am working with has an idle current
>> of some 40 uA but including the processing the total should be under 100
>> uA.  In the GA144 I calculated over 100 uA just driving the ADC not
>> counting any real processing.  Actually, most of the power is used in
>> timing the ADC conversion.  Without a high resolution clock the only way
>> to time the ADC conversion is to put the processor in an idle loop...
>
> Sounds like an interesting design.

I still need to verify that the LVDS input will detect the still very 
low level signal from the antenna.  Once I show that to work, I've got 
the rest covered.  If it doesn't work, I'll either need to use a 
separate comparator or if that won't work I might be able to provide 
some feedback to keep the detector on it's sensitive edge.

All the other parts have been analyzed well enough that I am very 
confident I'll meet my goal.

BTW, I am thinking of using a cheap analog battery driven clock as an 
output device.  So I bought one for $4 and took it apart.  It has the 
tiny circuit board for the clock chip and crystal and a very simple coil 
driving a gear that turns 180&#4294967295; each tick.  The rest of the clock is the 
same as any analog clock except it is *all* plastic.  Plastic gears, 
plastic pivot, plastic box.  I guess once you do the timing with 
electronics there is no longer a need for the fancy stuff in the 
mechanism.  Checking on Aliexpress I found the mechanisms for only $2! 
Sometimes technology is amazing in just how cheaply it can be produced.

Rick

Rob Doyle wrote:


> 
> I guess that it is just a design from another day - a whole lot less
> synchronous than anything I've done in an FPGA before.
> 
Yes, some PDP-10s were not rigidly clocked at all, so that when there were
no carries from the ALU after a few ns, the operation was considered
complete and the result stored.  Really nasty way to design a machine!

> I have enjoyed going back through that all.   I even found my "Mick and
> Brick" book.  I'll probably do a VAX 11/780 next which also used
> bit-sliced parts.
No, not true.  The 780 was all 74S chips (some LS on non-critical paths)
but nothing LSI at all.  The 730 and 750 used TI mask-programmed logic
array parts.  I actually read the print set of a 780 about 30 years ago
and at one time knew the design pretty well.

Jon

Jon Elson <jmelson@wustl.edu> wrote:

(snip)
>> I guess that it is just a design from another day - a whole lot less
>> synchronous than anything I've done in an FPGA before.
 
> Yes, some PDP-10s were not rigidly clocked at all, so that when there were
> no carries from the ALU after a few ns, the operation was considered
> complete and the result stored.  Really nasty way to design a machine!
 
>> I have enjoyed going back through that all.   I even found my "Mick and
>> Brick" book.  I'll probably do a VAX 11/780 next which also used
>> bit-sliced parts.

> No, not true.  The 780 was all 74S chips (some LS on non-critical paths)
> but nothing LSI at all.  The 730 and 750 used TI mask-programmed logic
> array parts.  I actually read the print set of a 780 about 30 years ago
> and at one time knew the design pretty well.

Story I knew from about 30 years ago was that the 730 was build
from 2900 series parts. That was supposed to be related to 
H-float being included, (no extra charge) when it wasn't for
the earlier models. So, H-float on the 730 was faster than the
software emulation on the 750. (But then again, I never tried.)

-- glen