Re: The variable bit cpu

Ok I have been travelling around the newgroups to digest the feedback :)

How about this scheme/encoding ;)

type field + type marker

followed by
interleaved data bit + meta bit (original idea)
or
followed by
interleaved length bit + length marker. (new encoding)

The length prefix field indicates the length of the next field which is the
data.

Bitstream: 1100011010101001110011100010101000
Metadata: 0001 001 0001

This would mean:

length data length length
data
12 - 6
5 -
Bitstream: 1100#011010101001#110#011100#0101#01000
Metadata: 0001# #001# #0001#

The meta data bits could be grouped together into a seperate bitstream
or
The meta data bits could be interleaved with the length data

(little correction to another post)
one bit of data, one bit of meta data, one bit of data, one bit of meta
data.

This last option would be good for communication protocols where otherwise
packets might go lost and important length data might go lost ;)

The final interleaved bit stream would look like:

Interleaved Bitstream: 10100001#011010101001#101001#011100#00100011#01000

45 bits in total.

11 bits for length data
11 bits for meta data
23 bits for data

Suppose there would be 1 milion bits of data then only 20 bits would be
require for the length field and 20 bits for the length markers.

Another 2 bits for the type field.

The total overhead would be 42 bits for 1000000 data bits.

A reduction of almost 1 milion bits of overhead compared to the original
idea ;)

Not bad :)

Though this is not completely fair... since the data now has to be one big
data field.

In reality the data might be many different small values... so then this new
encoding won't save that much overhead... but it could still save some... it
depends on how big the values are really ;)

So with this new encoding the encoder has options :D ;) use the original
idea for small values where it could be more efficient... use the new
encoding for big values which should be
more efficient...

Small value example: 7

original encoding:

data bits: 3
meta bits: 3
overhead: 3

new encoding:

length bits: 2
length markers: 2
overhead: 4

Original encoding would have been a little bit more efficient ;)

Let's see where it changes

data bits: 1,2,3,4,5,6,7,8,9
meta bits: 1,2,3,4,5,6,7,8,9

length bits: 1,2,2,3,3,3,3,4,4
length mrk: 1,2,2,3,3,3,3,4,4
total: 2,4,4,6,6,6,6,8,8

data bits 7 would be more efficient with new encoding

let's see for the next ones

data bits: 8,9,10,11,12,13,14,15,16
meta bits: 8,9,10,11,12,13,14,15,16

length bits: 4,4,4,4,4,4,4,4,5
length marker: 4,4,4,4,4,4,5
total bits: 8,8,8,8,8,8,8,8,10

Indeed... if I am not mistaking... and I don't think I am...

The original idea/encoding is only more efficient up to 6 data bits.

If a value requires 7 bits or more the new encoding should be used ;)

Cool :)

Now I'll respond to the rest of your kinda vague stuff :)

<randyhyde@xxxxxxxxxxxxx> wrote in message
news:1122771278.366122.118350@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Skybuck Flying wrote:
> >
> > However looking at the big picture the effort to scale fixed bit
hardware
> > and fixed bit software around the planet and maybe even in space
requires
> > much more effort and could be described as even more expensive ;)
>
> Not really. The "scaling" is already done in fact. However, instead of
> associating the "bit size" information with memory data, it's
> associated with the instruction. E.g., most 32-bit CPUs (x86 is the
> obvious exception) use 2 (or more) bits to determine the operand size.
> However, those bits are kept in the opcode rather than in each memory
> location.

Ok this is now probably irrelevant thx to my new encoding idea ;)

>
> Consider this, if you want bit address and bit sizing, it will take up
> to six bits to describe an arbitrary size between 1 and 64 bits. With
> eight bits you can go all the way to 256 bits. By your scheme, you can
> only specify sizes up to eight bits in length with eight size bits.

Ok point taken see new encoding :)

> And while a *few* applications might need to scale beyond 256 bits,
> they're going to be very rare. For that matter, few apps are going to
> need to scale beyond 64 bits.

This remains to be seen ;)

There are many algorithms which can scale to infinite bits... RSA is an
example.

Other encryption and compression algorithms are examples too.

These algorithms would be very simple to program thanks to variable bit
fields and variable bit operations.

Current implementations are very complex ;)

>
>
> >
> > As I already described the scanning can be done while the cpu loads or
even
> > executes the variable bit fields/instructions.
>
> Don't think that it's free, though. That's the one main thing that came
> out of the RISC vs. CISC debate -- you can't stick arbitrary hardware
> on your CPU, even operating in parallel, and not have it affect CPU
> performance.

I don't think it's free ;)

>
> >
> > I think as a software programmer I have reached my goal in describing a
> > variable bit field format.
> >
> > The variable bit field format could be used to described:
> >
> > cpu instructions
> > memory locations
> > anything really.
>
> A better solution, based on huffman encoding, is to embed the size
> information in the data stream itself rather than using "tag" bits.
> E.g.,
>
> $00..$7f -- Values in the range 0.127 or -64..+64,

Is this the size information ?

> $8000..$bfff -- Values in the range 0..16384 or +/- 8192.

Is this the data information ?

>
> etc. (Note that this require big endian encoding to make sense).
>
> Same sort of trick used by UTF-8 and other variable length encodings.
> Fairly easy to extend from byte address to bit addressing actually. And
> relatively memory efficient.

I think my new encoding is great :) don't know how it compares efficiency
wise to utf encoding since utf encoding at this level I don't understand...
but it probably has a fixed size and data field.... and that's bad ;) <-
inflexible :D

>
> >
> > The implementation of variable bit cpu/hardware (using this variable bit
> > field format or a similiar design) is left as an exercise to the
> > hardware/software reader/implementator ;)
>
> Of course it is. But keep in mind that the devil is in the details.
> Tag bits have been used in memory systems for various purposes over the
> years. They've never proven very popular in mass-produced products
> because of the cost and complexity involved. But look up "associative
> memory" on the Internet if you want to read some fascinating ideas.

I think my new encoding is looking kinda nice etc ;)

What's associative memory about, can you explain in short ? ;) is it more
efficient than my new encoding ? does it have other interesting properties
or offer solutions for bit variable related problems in hard/software ? ;)

>
> > >
> > > It won't save cost, it will be far more expensive. At the very least,
> > > you've doubled the memory requirements. How much you'll save by not
> > > having to waste a few bits in certain data types is questionable. Most
> > > applications will continue to use data sizes that are powers of two,
> > > anyway.
> >
> > In the long run it will prove to be cheaper since the software will be
able
> > to scale indefinetly.
>
> But do we need this?
> Already, few applications are going to benefit by having greater than
> 32-bits available for anything beyond addresses. And 64 bits of address
> is pretty much infinity as far as memory is concerned (keep in mind, 64
> bits of address space will handle byte addressing on something like *4
> BILLION* DVD-ROM disks!). Somewhere around 2**80 you've accounted for
> all the bits in the known universe. Certainly we don't need much in the
> way of addressability beyond 64 bits. And already, few apps need
> integer numeric values beyond 32 bits, much less 64. The idea might
> have been cool back in the days of eight-bit processors, but we've
> already scaled about as far as we're going to. No doubt, 128 bit
> processors will come along, maybe even 256 bit processors. But we're
> not scaling much farther than we are today.

The question is how much will those few applications benefit us ;) :)

Think big lol.

The internet is only one tiny little fucking application but it's impact on
the world has been big ;)

And now it has a tiny little fixed bit problem :D which is proving to be a
bitch to solve any time soon ;) :)

>
>
> > >
> > > There are other ways to do this. See the address displacement values
> > > found on the National 32000 series family (I think the VAX did this,
> > > too, but I'm not sure).
> >
> > Yes, there might be other ways to do this but are they as simple as this
?
>
> Conceptually, the idea is simple. But the hardware support is not. As I
> said earlier, the devil is in the details (of the hardware
> implementation).

Scew details... let's talk about concepts first and then we'll get to
details ;) :D

>
> >
> > The idea is about flexbility, scalability and easy of use.
>
> Except we don't need that kind of scalability today.

Oh yes we do I only need one little tiny example: THEZ INTERNET :D ;)

Want another one ?

Harddisks... boundary after boundary after boundary ;)

The list goes on and on and on :)

>
> >
> > With these three properties combined and new ways of thinking comes pure
> > power :D
>
> No doubt, those tag bits could be used for some very interesting
> things. Indeed, tag bits *have* been used for interesting thing. But
> those things were never economic and, dare I say it?, they didn't scale
> well to different systems.
>
>
> > >
> > >
> > > >
> > > > Example are windows xp 32 to 64 bit, the internet IPv4 to IPv6.
> > >
> > > That won't fix the problem where the code assumes a certain bit size.
> >
> > "Code assuming a certain bit size" is part of the problem.
>
> You're either burying the size in memory as part of the data, or in
> memory as part of the opcode. Either way, someone has to make the
> decision about the size. And dynamic sizing is going to be difficult
> to pull off. What happens when you have this:
>
> 0000001000000010000001
> xxxxxxxyyyyyyyyzzzzzzz
>
> And you decide you really need this:
>
> 000000000001000000010000001
> xxxxxxxxxxxxyyyyyyyyzzzzzzz
>
> then what? Are you going to shift everything around in memory? As I
> said, someone's got to make the size decisions at some point and
> changing them later is going to be a problem.

There can only be one change at a time one a single cpu.

The x grew... the x's will simply have to be copied to a big enough location
in memory.

No biggie ;)

>
>
> >
> > The whole point is more flexibility in the software.
>
> But the hardware costs aren't going to allow it. Your's is the CISC
> approach -- have the hardware do everything. We've learned the hardware
> that having the hardware do everything winds up slowing things down
> tremendously.

You mention CISC...

A quick look up reveals CISC should be re-evaluated ;)

http://www.sunderland.ac.uk/~ts0jti/comparch/ciscrisc.htm

>
> >
> > The variable bit format is to be used to make the software scale to (in
> > theory) unlimited bit size.
>
> But is unlimited bit size necessary?
> 80% of the integer numeric data I process can be handled by 16-bit
> integers. 98% can be handled by 32-bit integers. 99.9% by 64-bit
> integers.

Flexible bit fields that's what's needed ;)

>
> And even if that were the case, I don't see your scheme scaling up any
> better than using traditional approaches to multi-precision arithmetic.
> In those few instances where I need 128-bit integer arithmetic, it's
> easy enough to do on a 32-bit or 64-bit CPU.

The traditional approaches are failing big time since they are not flexible,
see the internet protocol just to name a example ;)

Sure given enough tries you can program anything you want... but try to do
it right the first time ;)

That's what this is about :)

> And one *big* thing you're missing here is that have a variable-bit
> size in memory *doesn't* give you a variable-sized ALU for arithmetic
> operations. Therefore, you can't have unlimited size arithmetic
> operations without having the hardware do the multiprecision operations
> for you (slow).

You assume it will be slow, this is unproven and remains to be seen ;)

Infact a variable bit system might even prove to be much faster since it can
use multi threading and multiple bit streams which are transmitted serial...
multiple task can therefore be easily done at the same time... no sharing of
memory bus is needed... each task can have it's own bitstream via a single
wire ;)

>
> The advantage to your scheme is not that it allows unlimited precision
> arithmetic, but that it lets you *exactly* specify an operand's size
> down to the bit, without wasting any bits. That is, at first blush it
> would seem to be very memory efficient. Until, of course, you remember
> that it takes two bits of memory for each bit you want to represent.
> At which point it's clearly more space efficient to use nice
> Power-Of-Two sizes.

See my new encoding scheme which uses both techniques ;)
"Power-Of-Two sizes" plus markers/meta bits but only for the type and length
field ;)

> >
> > Using this variable bit format requires the programmer to think a little
bit
> > different about programming and formats etc.
>
> Sure. They have to pick their *exact* bit sizes ahead of time, allowing
> for overflow and the like. And in the end, they're probably going to
> pick sizes like 8, 16, 32, and 64 bits. At which point all that tag
> memory will go to waste.

No they don't have to pick the exact bit sizes...

The variable bit fields can easily grow and shrink in size.

The cpu and/or software can handle this.

No biggie ;)

Bye,
Skybuck :D


.